Enheden tillader en personlig computer at behandle enorme grafer

I datavidenskabelig sprogbrug, grafer er strukturer af noder og forbindelseslinjer, der bruges til at kortlægge snesevis af komplekse datarelationer. Analyse af grafer er nyttig til en bred vifte af applikationer, såsom placering af websider, analyse af sociale netværk for politisk indsigt, eller plotte neuronstrukturer i hjernen.

Bestående af milliarder af noder og linjer, imidlertid, store grafer kan nå terabyte i størrelse. Grafdata behandles typisk i dyr dynamisk random access memory (DRAM) på tværs af flere strømhungrende servere.

Forskere fra MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL) har nu designet en enhed, der bruger billig flashlagring - den type, der bruges i smartphones - til at behandle massive grafer ved hjælp af kun en enkelt personlig computer.

Flash -lagring er typisk langt langsommere end DRAM ved behandling af grafdata. Men forskerne udviklede en enhed bestående af et flashchip -array og beregnings "accelerator, "der hjælper flash med at opnå DRAM-lignende ydeevne.

Strømforsyning til enheden er en ny algoritme, der sorterer alle adgangsanmodninger til grafdata i en sekventiel rækkefølge, som flash hurtigt og nemt kan få adgang til. Det fusionerer også nogle anmodninger om at reducere omkostningerne - den kombinerede beregningstid, hukommelse, båndbredde, og andre databehandlingsressourcer - til sortering.

Forskerne kørte enheden mod flere traditionelle højtydende systemer, der behandler flere store grafer, herunder den massive Web Data Commons Hyperlink -graf, som har 3,5 milliarder noder og 128 milliarder forbindelseslinjer. For at behandle denne graf, de traditionelle systemer krævede alle en server, der kostede tusinder af dollars og indeholdt 128 gigabyte DRAM. Forskerne opnåede den samme ydeevne ved at tilslutte to af deres enheder - i alt 1 gigabyte DRAM og 1 terabyte flash - til en stationær computer. I øvrigt, ved at kombinere flere enheder, de kunne behandle massive grafer-op til 4 milliarder noder og 128 milliarder forbindelseslinjer-som intet andet system kunne håndtere på 128-gigabyte-serveren.

"Bundlinjen er, at vi kan opretholde ydeevne med meget mindre, færre, og køligere - som i temperatur og strømforbrug - maskiner, "siger Sang-Woo Jun, en CSAIL -kandidatstuderende og første forfatter på et papir, der beskriver enheden, som præsenteres på International Symposium on Computer Architecture (ISCA).

Enheden kan bruges til at reducere omkostninger og energi forbundet med grafanalyse, og endda forbedre ydeevnen, i en bred vifte af applikationer. Forskerne, for eksempel, er i øjeblikket ved at oprette et program, der kan identificere gener, der forårsager kræft. Store teknologivirksomheder som Google kunne også udnytte enhederne til at reducere deres energifodaftryk ved at bruge langt færre maskiner til at køre analyser.

"Grafbehandling er sådan en generel idé, "siger medforfatter Arvind, Johnson -professoren i datalogi. "Hvad har sideplacering til fælles med genpåvisning? For os, det er det samme beregningsproblem - bare forskellige grafer med forskellige betydninger. Den type applikation, nogen udvikler, vil bestemme, hvilken indvirkning det har på samfundet. "

Papirmedforfattere er CSAIL-kandidatstuderende Shuotao Xu, og Andy Wright og Sizhuo Zhang, to kandidatstuderende i CSAIL og Institut for Elektroteknik og Datalogi.

Sorter og reducer

I grafanalyse, et system vil grundlæggende søge efter og opdatere en node værdi baseret på dets forbindelser med andre noder, blandt andre målinger. I websiderangering, for eksempel, hver node repræsenterer en webside. Hvis knude A har en høj værdi og opretter forbindelse til knude B, så vil knude B's værdi også stige.

Traditionelle systemer gemmer alle grafdata i DRAM, hvilket gør dem hurtige til at behandle dataene, men også dyre og strøm-sultne. Nogle systemer aflaster noget datalagring for at blinke, som er billigere, men langsommere og mindre effektiv, så de kræver stadig betydelige mængder DRAM.

Forskernes enhed kører på det, forskerne kalder en "sorteringsreducerende" algoritme, som løser et stort problem med at bruge flash som den primære lagerkilde:affald.

Grafanalysesystemer kræver adgang til noder, der kan være meget langt fra hinanden på tværs af en massiv, sparsom grafstruktur. Systemer anmoder generelt om direkte adgang til, sige, 4 til 8 bytes data for at opdatere en node værdi. DRAM giver den direkte adgang meget hurtigt. Blitz, imidlertid, kun adgang til data i 4- til 8-kilobyte bidder, men opdaterer stadig kun et par bytes. Gentagelse af denne adgang for hver anmodning, mens du hopper over grafen, spilder båndbredde. "Hvis du har brug for at få adgang til hele 8 kilobytes, og brug kun 8 bytes og kast resten, du ender med at smide 1, 000 gange ydeevne væk, "Siger Jun.

Sortereduktionsalgoritmen tager i stedet alle anmodninger om direkte adgang og sorterer dem i rækkefølge efter identifikatorer, som viser anmodningens destination - f.eks. at samle alle opdateringer til knude A, alt for knude B, og så videre. Flash kan derefter få adgang til kilobyte-store bidder af tusinder af anmodninger på én gang, gør det langt mere effektivt.

For yderligere at spare computerkraft og båndbredde, algoritmen fusionerer samtidig dataene til de mindst mulige grupper. Når algoritmen noterer matchende identifikatorer, den summerer dem til en enkelt datapakke - f.eks. A1 og A2 bliver til A3. Det fortsætter med at gøre det, skabe stadig mindre pakker med data med matchende identifikatorer, indtil den producerer den mindst mulige pakke til sortering. Dette reducerer drastisk mængden af ​​dublerede anmodninger om adgang.

Brug af sorteringsreduceringsalgoritmen på to store grafer, forskerne reducerede de samlede data, der skulle opdateres i flash med omkring 90 procent.

Aflæsning af beregning

Sortereduktionsalgoritmen er beregningskrævende for en værtscomputer, imidlertid, så forskerne implementerede en brugerdefineret accelerator i enheden. Acceleratoren fungerer som et midtvejspunkt mellem værten og flashchips, udførelse af al beregning til algoritmen. Dette aflaster så meget strøm til acceleratoren, at værten kan være en lavdreven pc eller bærbar computer, der administrerer sorterede data og udfører andre mindre opgaver.

"Acceleratorer formodes at hjælpe værten med at beregne, men vi er nået så langt [med beregningerne], at værten bliver ligegyldig, "Siger Arvind.

"MIT-arbejdet viser en ny måde at udføre analyse på meget store grafer:Deres arbejde udnytter flash-hukommelse til at gemme graferne og udnytter 'feltprogrammerbare gate-arrays' [brugerdefinerede integrerede kredsløb] på en genial måde til at udføre både analyserne og databehandling nødvendig for at bruge flashhukommelse effektivt, "siger Keshav Pingali, professor i datalogi ved University of Texas i Austin. "I det lange løb, dette kan føre til systemer, der effektivt kan behandle store datamængder på laptops eller desktops, som vil revolutionere vores behandling af big data. "

Fordi værten kan have så lav effekt, Jun siger, et langsigtet mål er at skabe en generel platform og softwarebibliotek, hvor forbrugerne kan udvikle deres egne algoritmer til applikationer ud over grafanalyse. "Du kan tilslutte denne platform til en bærbar computer, download [softwaren], og skriv enkle programmer for at få ydeevne i serverklasse på din bærbare computer, " han siger.

Denne historie er genudgivet med tilladelse fra MIT News (web.mit.edu/newsoffice/), et populært websted, der dækker nyheder om MIT -forskning, innovation og undervisning.