På datavetenskapsspråk, grafer är strukturer av noder och anslutande linjer som används för att kartlägga mängder av komplexa datarelationer. Att analysera grafer är användbart för ett brett spektrum av applikationer, som att rangordna webbsidor, analysera sociala nätverk för politiska insikter, eller plotta neuronstrukturer i hjärnan.

Består av miljarder noder och linjer, dock, stora grafer kan nå terabyte i storlek. Grafdata bearbetas vanligtvis i dyrt dynamiskt minne med direktåtkomst (DRAM) över flera kraftkrävande servrar.

Forskare från MIT:s Computer Science and Artificial Intelligence Laboratory (CSAIL) har nu designat en enhet som använder billig flashlagring – den typ som används i smartphones – för att bearbeta massiva grafer med bara en enda persondator.

Flash-lagring är vanligtvis mycket långsammare än DRAM vid bearbetning av grafdata. Men forskarna utvecklade en enhet bestående av en flash-chip-array och beräkningsaccelerator, "som hjälper flash att uppnå DRAM-liknande prestanda.

Drivning av enheten är en ny algoritm som sorterar alla åtkomstbegäranden för grafdata i en sekventiell ordning som flash kan komma åt snabbt och enkelt. Den slår också samman vissa förfrågningar för att minska overheaden – den kombinerade beräkningstiden, minne, bandbredd, och andra datorresurser - sortering.

Forskarna körde enheten mot flera traditionella högpresterande system som behandlar flera stora grafer, inklusive den massiva Web Data Commons Hyperlink Graph, som har 3,5 miljarder noder och 128 miljarder anslutningslinjer. För att bearbeta den grafen, de traditionella systemen krävde alla en server som kostade tusentals dollar och innehöll 128 gigabyte DRAM. Forskarna uppnådde samma prestanda genom att ansluta två av deras enheter - totalt 1 gigabyte DRAM och 1 terabyte flash - till en stationär dator. Dessutom, genom att kombinera flera enheter, de kunde bearbeta massiva grafer-upp till 4 miljarder noder och 128 miljarder anslutningslinjer-som inget annat system kunde hantera på 128-gigabyte-servern.

"Slutsatsen är att vi kan behålla prestanda med mycket mindre, färre, och svalare - som i temperatur och strömförbrukning - maskiner, " säger Sang-Woo Jun, en CSAIL doktorand och första författare på ett papper som beskriver enheten, som presenteras på International Symposium on Computer Architecture (ISCA).

Enheten kan användas för att minska kostnader och energi i samband med grafanalys, och till och med förbättra prestanda, i ett brett spektrum av applikationer. Forskarna, till exempel, håller på att skapa ett program som kan identifiera gener som orsakar cancer. Stora teknikföretag som Google kan också utnyttja enheterna för att minska sitt energifotavtryck genom att använda mycket färre maskiner för att köra analys.

"Grafbehandling är en sådan allmän idé, säger medförfattaren Arvind, Johnson -professorn i datavetenskap. "Vad har sidrankning gemensamt med genupptäckt? För oss, det är samma beräkningsproblem – bara olika grafer med olika betydelser. Vilken typ av applikation någon utvecklar kommer att avgöra vilken inverkan den har på samhället."

Papperets medförfattare är CSAIL-doktorand Shuotao Xu, och Andy Wright och Sizhuo Zhang, två doktorander i CSAIL och Institutionen för elektroteknik och datavetenskap.

Sortera och minska

I grafanalys, ett system kommer i princip att söka efter och uppdatera en nods värde baserat på dess anslutningar med andra noder, bland andra mätvärden. I webbrankning, till exempel, varje nod representerar en webbsida. Om nod A har ett högt värde och ansluter till nod B, då kommer också nod B:s värde att öka.

Traditionella system lagrar all grafdata i DRAM, vilket gör dem snabba att bearbeta data men också dyra och energisugna. Vissa system laddar ner lite datalagring för att blixt, som är billigare men långsammare och mindre effektivt, så de kräver fortfarande betydande mängder DRAM.

Forskarnas enhet körs på vad forskarna kallar en "sort-reducera"-algoritm, vilket löser ett stort problem med att använda blixt som primär lagringskälla:avfall.

Grafanalyssystem kräver åtkomst till noder som kan vara mycket långt från varandra över en massiv, gles grafstruktur. System kräver i allmänhet direkt tillgång till, säga, 4 till 8 byte med data för att uppdatera en nods värde. DRAM ger den direktåtkomsten mycket snabbt. Blixt, dock, har endast åtkomst till data i 4- till 8-kilobyte bitar, men uppdaterar fortfarande bara några byte. Att upprepa den åtkomsten för varje begäran samtidigt som du hoppar över grafen slösar bort bandbredd. "Om du behöver komma åt hela 8 kilobyte, och använd bara 8 byte och släng resten, det slutar med att du kastar 1, 000 gånger prestanda borta, säger Jun.

Sorteringsreduceringsalgoritmen tar istället alla direktåtkomstförfrågningar och sorterar dem i sekventiell ordning efter identifierare, som visar destinationen för begäran – som att gruppera alla uppdateringar för nod A, allt för nod B, och så vidare. Flash kan sedan komma åt kilobytestora bitar av tusentals förfrågningar på en gång, gör det mycket mer effektivt.

För att ytterligare spara beräkningskraft och bandbredd, algoritmen slår samtidigt samman data till de minsta möjliga grupper. Närhelst algoritmen noterar matchande identifierare, den summerar dessa till ett enda datapaket – som att A1 och A2 blir A3. Det fortsätter att göra så, skapa allt mindre datapaket med matchande identifierare, tills det producerar minsta möjliga paket att sortera. Detta minskar drastiskt mängden dubbla förfrågningar att få tillgång till.

Genom att använda sorteringsreduceringsalgoritmen på två stora grafer, forskarna minskade den totala data som behövde uppdateras i flash med cirka 90 procent.

Avlastningsberäkning

Sorteringsreduceringsalgoritmen är beräkningskrävande för en värddator, dock, så forskarna implementerade en anpassad accelerator i enheten. Acceleratorn fungerar som en mittpunkt mellan värden och flashchips, exekvera all beräkning för algoritmen. Detta avlastar så mycket ström till acceleratorn att värden kan vara en lågdriven dator eller bärbar dator som hanterar sorterad data och utför andra mindre uppgifter.

"Acceleratorer ska hjälpa värden att beräkna, men vi har kommit så långt [med beräkningarna] att värden blir oviktig, Säger Arvind.

"MIT-arbetet visar ett nytt sätt att utföra analyser på mycket stora grafer:Deras arbete utnyttjar flashminne för att lagra graferna och utnyttjar fältprogrammerbara grindmatriser [anpassade integrerade kretsar] på ett genialt sätt för att utföra både analys och databehandling som krävs för att använda flashminnet effektivt, " säger Keshav Pingali, professor i datavetenskap vid University of Texas i Austin. "I det långa loppet, detta kan leda till system som effektivt kan bearbeta stora mängder data på bärbara datorer eller stationära datorer, vilket kommer att revolutionera hur vi gör stordatabearbetning. "

Eftersom värden kan ha så låg effekt, Jun säger, ett långsiktigt mål är att skapa en allmän plattform och ett mjukvarubibliotek för konsumenter att utveckla sina egna algoritmer för applikationer bortom grafanalys. "Du kan ansluta denna plattform till en bärbar dator, ladda ner [mjukvaran], och skriva enkla program för att få prestanda i serverklass på din bärbara dator, " han säger.

Den här historien återpubliceras med tillstånd av MIT News (web.mit.edu/newsoffice/), en populär webbplats som täcker nyheter om MIT -forskning, innovation och undervisning.