In het datawetenschappelijke taalgebruik, grafieken zijn structuren van knopen en verbindingslijnen die worden gebruikt om scores van complexe gegevensrelaties in kaart te brengen. Het analyseren van grafieken is nuttig voor een breed scala aan toepassingen, zoals het rangschikken van webpagina's, het analyseren van sociale netwerken voor politieke inzichten, of het plotten van neuronstructuren in de hersenen.

Bestaande uit miljarden knopen en lijnen, echter, grote grafieken kunnen terabytes groot worden. De grafiekgegevens worden doorgaans verwerkt in duur dynamisch willekeurig toegankelijk geheugen (DRAM) over meerdere energieverslindende servers.

Onderzoekers van MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL) hebben nu een apparaat ontworpen dat goedkope flash-opslag gebruikt - het type dat in smartphones wordt gebruikt - om enorme grafieken te verwerken met slechts een enkele personal computer.

Flash-opslag is doorgaans veel langzamer dan DRAM bij het verwerken van grafiekgegevens. Maar de onderzoekers ontwikkelden een apparaat dat bestaat uit een flash-chiparray en een rekenversneller, " die Flash helpt om DRAM-achtige prestaties te bereiken.

Het apparaat wordt aangedreven door een nieuw algoritme dat alle toegangsverzoeken voor grafiekgegevens in een sequentiële volgorde sorteert die Flash snel en gemakkelijk kan openen. Het voegt ook enkele verzoeken samen om de overhead te verminderen:de gecombineerde rekentijd, geheugen, bandbreedte, en andere computerbronnen - van sorteren.

De onderzoekers hebben het apparaat vergeleken met verschillende traditionele krachtige systemen die verschillende grote grafieken verwerken, inclusief de enorme Web Data Commons Hyperlink Graph, die 3,5 miljard knooppunten en 128 miljard verbindingslijnen heeft. Om die grafiek te verwerken, de traditionele systemen hadden allemaal een server nodig die duizenden dollars kostte en 128 gigabyte DRAM bevatte. De onderzoekers bereikten dezelfde prestaties door twee van hun apparaten - in totaal 1 gigabyte DRAM en 1 terabyte flash - op een desktopcomputer aan te sluiten. Bovendien, door meerdere apparaten te combineren, ze konden enorme grafieken verwerken - tot 4 miljard nodes en 128 miljard verbindingslijnen - die geen enkel ander systeem aankan op de 128 gigabyte server.

"Het komt erop neer dat we de prestaties kunnen behouden met veel kleinere, minder, en koeler - zoals in temperatuur en stroomverbruik - machines, " zegt Sang-Woo Jun, een CSAIL-afgestudeerde student en eerste auteur op een paper waarin het apparaat wordt beschreven, die wordt gepresenteerd op het International Symposium on Computer Architecture (ISCA).

Het apparaat kan worden gebruikt om kosten en energie te besparen die verband houden met grafiekanalyses, en zelfs de prestaties verbeteren, in een breed scala aan toepassingen. De onderzoekers, bijvoorbeeld, maken momenteel een programma dat genen kan identificeren die kanker veroorzaken. Grote technologiebedrijven zoals Google zouden de apparaten ook kunnen gebruiken om hun energievoetafdruk te verkleinen door veel minder machines te gebruiken om analyses uit te voeren.

"Grafiekverwerking is zo'n algemeen idee, " zegt co-auteur Arvind, de Johnson Professor in Computer Science Engineering. "Wat heeft paginarangschikking gemeen met gendetectie? Voor ons het is hetzelfde rekenprobleem - alleen verschillende grafieken met verschillende betekenissen. Het type applicatie dat iemand ontwikkelt, bepaalt de impact die het heeft op de samenleving."

Paper co-auteurs zijn CSAIL afgestudeerde student Shuotao Xu, en Andy Wright en Sizhuo Zhang, twee afgestudeerde studenten van CSAIL en de faculteit Elektrotechniek en Informatica.

Sorteren en verkleinen

In grafiekanalyse, een systeem zal in principe de waarde van een knooppunt zoeken en bijwerken op basis van zijn verbindingen met andere knooppunten, onder andere metrieken. Bij het rangschikken van webpagina's, bijvoorbeeld, elk knooppunt vertegenwoordigt een webpagina. Als knooppunt A een hoge waarde heeft en verbinding maakt met knooppunt B, dan zal de waarde van knooppunt B ook toenemen.

Traditionele systemen slaan alle grafiekgegevens op in DRAM, waardoor ze snel zijn in het verwerken van de gegevens, maar ook duur en energieverslindend. Sommige systemen ontlasten wat gegevensopslag om te flashen, dat is goedkoper, maar langzamer en minder efficiënt, dus ze hebben nog steeds aanzienlijke hoeveelheden DRAM nodig.

Het apparaat van de onderzoekers draait op wat de onderzoekers een 'sort-reduce'-algoritme noemen, waarmee een groot probleem wordt opgelost met het gebruik van flash als primaire opslagbron:afval.

Grafiekanalysesystemen hebben toegang nodig tot knooppunten die erg ver van elkaar verwijderd kunnen zijn over een enorm, schaarse grafiekstructuur. Systemen vragen over het algemeen om directe toegang tot, zeggen, 4 tot 8 bytes aan gegevens om de waarde van een knooppunt bij te werken. DRAM biedt die directe toegang heel snel. Flash, echter, heeft alleen toegang tot gegevens in blokken van 4 tot 8 kilobyte, maar werkt nog steeds maar een paar bytes bij. Het herhalen van die toegang voor elk verzoek terwijl u over de grafiek springt, verspilt bandbreedte. "Als je toegang nodig hebt tot de volledige 8 kilobytes, en gebruik slechts 8 bytes en gooi de rest weg, uiteindelijk gooi je er 1, 000 keer prestaties weg, ' zegt Jun.

Het sort-reduce-algoritme neemt in plaats daarvan alle directe toegangsverzoeken en sorteert ze in sequentiële volgorde op identifiers, die de bestemming van het verzoek tonen, zoals het groeperen van alle updates voor knooppunt A, alles voor knooppunt B, enzovoort. Flash heeft dan toegang tot brokken ter grootte van een kilobyte van duizenden verzoeken tegelijk, waardoor het veel efficiënter gaat.

Om nog meer rekenkracht en bandbreedte te besparen, het algoritme voegt de gegevens tegelijkertijd samen in de kleinst mogelijke groeperingen. Telkens wanneer het algoritme overeenkomende identifiers opmerkt, het somt die op in een enkel datapakket, zoals A1 en A2 die A3 worden. Het blijft dit doen, het creëren van steeds kleinere datapakketten met bijpassende identifiers, totdat het het kleinst mogelijke pakket produceert om te sorteren. Dit vermindert het aantal dubbele verzoeken om toegang drastisch.

Met behulp van het sort-reduceer-algoritme op twee grote grafieken, de onderzoekers verminderden de totale gegevens die in flash moesten worden bijgewerkt met ongeveer 90 procent.

Berekening offloaden

Het sort-reduce-algoritme is rekenintensief voor een hostcomputer, echter, dus implementeerden de onderzoekers een aangepaste versneller in het apparaat. De versneller fungeert als een halverwege tussen de host en flash-chips, het uitvoeren van alle berekeningen voor het algoritme. Dit ontlast zoveel stroom aan het gaspedaal dat de host een pc of laptop met laag vermogen kan zijn die gesorteerde gegevens beheert en andere kleine taken uitvoert.

"Versnellers worden verondersteld de host te helpen bij het berekenen, maar we zijn zo ver gekomen [met de berekeningen] dat de host onbelangrijk wordt, ' zegt Arvind.

"Het MIT-werk laat een nieuwe manier zien om analyses uit te voeren op zeer grote grafieken:hun werk maakt gebruik van flash-geheugen om de grafieken op te slaan en exploiteert 'field-programmable gate arrays' [aangepaste geïntegreerde schakelingen] op een ingenieuze manier om zowel de analyses als de gegevensverwerking die nodig is om het flashgeheugen effectief te gebruiken, " zegt Keshav Pingali, een professor in computerwetenschappen aan de Universiteit van Texas in Austin. "Op lange termijn, dit kan leiden tot systemen die grote hoeveelheden data efficiënt kunnen verwerken op laptops of desktops, wat een revolutie teweeg zal brengen in de manier waarop we big data verwerken."

Omdat de host zo laag vermogen kan hebben, Jun zegt, een langetermijndoel is om een ​​platform en softwarebibliotheek voor algemene doeleinden te creëren voor consumenten om hun eigen algoritmen te ontwikkelen voor toepassingen die verder gaan dan grafische analyse. "Je zou dit platform op een laptop kunnen aansluiten, download [de software], en schrijf eenvoudige programma's om prestaties van serverklasse op uw laptop te krijgen, " hij zegt.

Dit verhaal is opnieuw gepubliceerd met dank aan MIT News (web.mit.edu/newsoffice/), een populaire site met nieuws over MIT-onderzoek, innovatie en onderwijs.