SecBCache: Evaluating Banked Interleaved Word-Granularity Sector Cache for gather/scatter Operations on Sparse Data

Moderne computers worden vaak niet beperkt door hoe snel ze kunnen rekenen, maar door hoe snel ze gegevens kunnen verplaatsen. In de wereld van high-performance computing, waar machines complexe problemen aanpakken zoals het in kaart brengen van de verspreiding van ziekten, het analyseren van sociale netwerken of het simuleren van klimaatverandering, is de meest voorkomende taak niet het verwerken van getallen, maar het ophalen ervan uit het geheugen. Dit is vooral het geval bij het werken met "sparse" (ijle) data, een term die informatie beschrijft waarbij de meeste potentiële ruimte leeg is. Stel je een enorme spreadsheet voor waarin slechts een paar verspreide cellen getallen bevatten, terwijl de rest leeg is. Wanneer een computer deze verspreide getallen probeert te lezen, moet hij vaak op onvoorspelbare manieren door het geheugensysteem springen, een proces dat indirecte toegang wordt genoemd. Omdat deze sprongen willekeurig zijn, kan de computer niet gemakkelijk voorspellen welke gegevens als volgende nodig zullen zijn, waardoor het verplaatsen van informatie van opslag naar de processor een grote flessenhals wordt die het hele systeem vertraagt en energie verspilt.

Om te begrijpen waarom dit moeilijk is, moet men kijken naar hoe computers momenteel gegevens opslaan. Standaard computergeheugen is georganiseerd in blokken van vaste grootte, vergelijkbaar met een bibliotheek die alleen hele boeken uitleent, zelfs als een lezer slechts één pagina nodig heeft. Wanneer een computer een specifiek stukje data opvraagt, haalt het geheugensysteem een heel blok op, een zogena나mede cache line, die doorgaans zesentwintig bytes groot is. Als de computer slechts één of twee getallen uit dat blok nodig heeft, wordt de rest van de data onnodig opgehaald en opgeslagen, wat energie verbruikt en de datapaden verstopt. Deze inefficiëntie wordt een ernstig probleem voor "sparse" workloads, waarbij de computer mogelijk tientallen ongerelateerde getallen uit verschillende delen van het geheugen moet verzamelen om een enkele berekening uit te voeren. In deze scenario's besteedt de computer meer tijd aan het verplaatsen van nutteloze data dan aan het daadwerkelijke werk.

Een team van onderzoekers van New Mexico State University, Lawrence Berkeley National Laboratory en Florida International University heeft een nieuwe manier voorgesteld om dit probleem aan te pakken, genaamd SecBCache. Hun werk richt zich op een specif kind van computerarchitectuur die wordt gebruikt voor wetenschappelijke simulaties en machine learning, waarbij gegevens vaak op een verspreide, onregelmatige manier worden geraadpleegd. De onderzoekers hebben een gespecialiseerd geheugencomponent ontworpen dat de regels verandert voor hoe gegevens worden opgehaald en opgeslagen. In plaats van telkens een groot, vast blok data te pakken, staat hun ontwerp de computer toe om alleen de kleine, specifieke stukjes informatie op te halen en op te slaan die hij daadwerkelijk nodig heeft. Ze testten dit idee met behulp van een gedetailleerde computersimulatie van een moderne processor, waarbij ze deze draaiden tegen real-world datasets die worden gebruikt bij graafanalyse en matrixvermenigvuldiging. De resultaten toonden aan dat deze nieuwe aanpak de hoeveelheid data die de computer naar zijn geheugen schrijft aanzienlijk kan verminderen, de energie die nodig is om deze taken uit te voeren kan verlagen en potentieel de tijd kan verkorten om informatie te ontsluiten, zonder dat daar wijzigingen voor nodig zijn in de programmeertalen of de fundamentele instructies die de computer begrijpt.

De kern van de innovatie van de onderzoekers ligt in de manier waarop zij de geheugenopslag hebben geherorganiseerd. Ze hebben de standaard grote geheugenblokken opgedeeld in kleinere stukjes van acht bytes, die ze subsectors noemen. In een traditioneel systeem, als een computer één getal uit een blok nodig heeft, moet hij het hele blok laden. In het nieuwe SecBCache-systeem is het geheugen verdeeld in acht afzonderlijke secties, of banks, die gelijktijdig kunnen worden geraadpleegd. Wanneer de computer een lijst met verspreide getallen moet verzamelen, kan hij verzoeken naar deze verschillende banks tegelijk sturen, waarbij alleen de specifieke acht-byte stukjes wordt opgehaald die vereist zijn. Dit is vergelijkbaar met een bibliotheek die, in plaats van je een heel boek te geven, acht verschillende medewerkers heeft die elk op exact hetzelfde moment een enkele pagina kunnen pakken die je nodig hebt uit verschillende boeken. Dit ontwerp stelt de computer in staat om de verspilling van het ophalen van ongebruikte data te vermijden, terwijl het de snelheid en organisatie van een standaard geheugensysteem behoudt.

Om te zien of dit idee in de praktijk zou werken, bouwden de onderzoekers een virtuele versie van een computerprocessor met behulp van een tool genaamd gem5, die simuleert hoe hardware zich op een zeer gedetailleerd niveau gedraagt. Ze programmeerden deze virtuele computer om twee veelvoorkomende wetenschappelijke taken uit te voeren: een breadth-first search, een methode voor het verkennen van netwerken zoals sociale mediaconnecties of wegenkaarten, en een sparse matrix multiplication, een berekening gebruikt in natuurkunde en techniek die betrokken is bij het vermenigvuldigen van grote rasters van getallen waarbij de meeste vermeldingen nul zijn. Ze testten deze taken met zestien verschillende real-world datasets, variërend van e-mailnetwerken tot elektriciteitsnetmodellen. Voor elke taak vergeleken ze de prestaties van hun nieuwe SecBCache-ontwerp met een standaard, conventionele geheugencache die de traditionele grote blokken gebruikt.

De simulaties toonden een opvallend verschil in efficiëntie. In het standaard systeem haalde de computer vaak een volledig blok data op, maar gebruikte hij minder dan de helft ervan, en in sommige gevallen zelfs slechts achttien procent. Dit betekent dat voor elk nuttig stukje opgehaalde data het systeem energie en bandbreedte verspilde aan het verplaatsen van meerdere stukjes nutteloze data. Het SecBCache-ontwerp elimineerde deze verspilling door alleen de specifieke acht-byte stukjes op te halen die nodig waren. Voor de graafzoektaken verminderde het nieuwe ontwerp de hoeveelheid data die naar de geheugenopslag werd geschreven met een mediaan van drieenzestig procent. Voor de matrixvermenigvuldigingstaken was de reductie nog dramatischer, met een mediane afname van tachtig procent in de geschreven data. Dit betekent dat voor veel van de geteste datasets het nieuwe systeem slechts een fractie van de data schreef die het oude systeem deed, wat het interne verkeer dat computers vertraagt drastisch verminderde.

Naast het besparen van ruimte, keken de onderzoekers ook naar hoe dit ontwerp de snelheid van geheugentoegang beïnvloedde. Omdat het nieuwe systeem meerdere banks tegelijk kan raadplegen, heeft het de potentie om veel verzoeken parallel te bedienen. De onderzoekers merkten echter op dat de werkelijke snelheidswinst afhangt van hoe de data is verdeeld. Ze creëerden een wiskundig model om de tijd te schatten die nodig is om gegevens te ontsluiten, waarbij ze zowel een best-case scenario berekenden waarin alles perfect verloopt, als een worst-case scenario waarin verzoeken vastlopen op dezelfde bank. Onder de conservatieve, worst-case aannames, voorspelde het model dat het nieuwe systeem de vertragingen in geheugentoegang met zesentwintig procent zou verminderen voor de graafzoektaken en met vijftig procent voor de matrixvermenigvuldigingstaken. Deze cijfers vertegenwoordigen de tijd die het geheugensysteem zelf nodig heeft om te reageren, niet de totale tijd die de computer nodig heeft om het volledige programma te voltooien, maar ze duiden op een significante verbetering in de snelheid waarmee de processor de benodigde data kan verkrijgen.

De onderzoekers onderzochten ook de fysieke kosten van het bouwen van een dergelijk systeem. Ze gebruikten een standaard industrieel hulpmiddel om de grootte en het energieverbruik van het nieuwe geheugendesign te schatten. Ze ontdekten dat de extra hardware die nodig is om deze kleinere, gebankte stukjes data te beheren, maximaal 2,46 procent van het totale oppervlak van de geheugenhiërarchie van de computer zou beslaan. Dit is een zeer kleine voetafdruk, wat suggereert dat het ontwerp aan moderne processors kan worden toegevoegd zonder aanzienlijke ruimte in beslag te nemen. Bovendien verbruikt het nieuwe systeem minder energie omdat het veel minder data naar de geheugenarrays schrijft. De simulaties toonden aan dat de dynamische energie die door het geheugensysteem werd verbruikt, daalde voor elke geteste dataset, met reducties variërend van enkele procenten tot meer dan tachtig procent, afhankelijk van hoe "sparse" de data was.

Een van de belangrijkste aspecten van dit werk is dat het geen programmeurs vereist om hun code te herschrijven of nieuwe manieren te leren om de computer instructies te geven. De onderzoekers ontwierpen SecBCache om te werken met bestaande instructies die computers al gebruiken voor het verzamelen en verspreiden van data. In moderne processors zijn er specifieke commando's die een enkele instructie in staat stellen om meerdere niet-aangrenzende stukjes data te laden. Het nieuwe geheugensysteem maakt deze bestaande commando's simpelweg efficiënter door ervoor te zorgen dat alleen de noodzakelijke data wordt verplaatst. De enige vereiste wijziging zou een eenvoudige softwaremarker zijn die de computer vertelt welke delen van het geheugen dit type verspreide data bevatten, waardoor de hardware de verzoeken automatisch naar het nieuwe systeem kan routeren. Deze aanpak voorkomt de noodzaak van complexe nieuwe programmeermodellen of gespecialiseerde hardwareversnellers die vaak niet door de bredere industrie worden geadopteerd.

De studie benadrukte ook waar deze aanpak minder effectief zou zijn. In gevallen waarin de geaccesseerde data zeer dicht en voorspelbaar is, zoals wanneer een computer een lange lijst met getallen leest die direct naast elkaar staan, werkt het traditionele systeem van het ophalen van grote blokken zeer goed. In deze specifieke scenario's presteerde het nieuwe systeem soms iets slechter omdat het elk stukje afzonderlijk moest ophalen, waardoor het voordeel van de "gratis" data die met een groot blok gepaard gaat, verloren ging. De onderzoekers benadrukten echter dat hun ontwerp specifiek gericht is op de groeiende klasse van problemen die te maken hebben met sparse, onregelmatige data-access, die steeds gebruikelijker worden in velden zoals kunstmatige intelligentie en big data-analyse. Voor deze toepassingen weegt het vermogen om alleen te halen wat nodig is zwaarder dan het voordeel van het in één keer alles ophalen.

De onderzoekers waren zorgvuldig in het onderscheid tussen wat ze direct hebben gemeten en wat ze hebben geschat. De reducties in geschreven data en de energiebesparingen werden direct gemeten vanuit de simulatie van het geheugensysteem. De verbeteringen in toegangssnelheid waren echter afgeleid van een wiskundig model dat schatte hoe het systeem zou reageren als het meerdere verzoeken tegelijkertijd kon afhandelen. Hoewel de simulatie aantoonde dat de hardware de verzoeken kon afhandelen, bood het model een bereik van mogelijke vertragingen op basis van hoe vaak verschillende delen van het geheugen tegelijkertijd gevraagd zouden worden. De onderzoekers merkten op dat dit gemodelleerde vertragingen zijn en geen gegarandeerde versnellingen voor de uiteindelijke applicatie, maar ze bieden een sterke indicatie dat de geheugen-subsystem minder een flessenhals zal zijn.

In de bredere context van de computerwetenschap adresseert dit werk een fundamentele verschuiving in hoe computing evolueert. Naarmate machines bewegen van eenvoudige, lineaire berekeningen naar complexe, datagestuurde taken, worden de oude aannames over hoe geheugen zou moeten werken steeds minder relevant. Het idee dat een computer altijd een groot blok data moet ophalen, is een erfenis van een tijdperk waarin data dicht en voorspelbaar was. Het SecBCache-ontwerp biedt een blik op een toekomst waarin geheugensystemen flexibeler zijn en in staat zijn zich aan te passen aan de onregelmatige behoeften van moderne algoritmen. Door te bewijzen dat het mogelijk is om een geheugensysteem te bouwen dat zowel zeer efficiënt als compatibel is met bestaande software, hebben de onderzoekers een praktisch pad naar de verbetering van de prestaties van de volgende generatie wetenschappelijke en analytische tools geëffend.

De studie concludeert dat hoewel geen enkele oplossing bij elke computerprobleem past, de specifieke uitdaging van het afhandelen van sparse, indirecte data-access kan worden opgelost met een gerichte architecturale wijziging. De onderzoekers hebben aangetoond dat het door het geheugen op te delen in kleinere, onafhankelijk toegankelijke stukken en het te organiseren op een manier die parallelle toegang mogelijk maakt, mogelijk is om de verspilling van energie en bandbreedte die huidige systemen teisteren drastisch te verminderen. Deze aanpak vereist geen revolutie in hoe we computers programmeren, maar eerder een evolutie in hoe de hardware de data afhandelt die we er al aan vragen. Naarmate de vraag naar het verwerken van grote, complexe datasets blijft groeien, kunnen ontwerpen zoals SecBCache essentieel worden om computers snel en energiezuinig te houden, zodat de flessenhals van het verplaatsen van data het potentieel van de berekeningen zelf niet in de weg staat.