Nel gergo della scienza dei dati, i grafici sono strutture di nodi e linee di collegamento utilizzate per mappare decine di complesse relazioni di dati. L'analisi dei grafici è utile per un'ampia gamma di applicazioni, come il posizionamento delle pagine web, analizzare i social network per approfondimenti politici, o tracciando strutture neuronali nel cervello.

Composto da miliardi di nodi e linee, però, grafici di grandi dimensioni possono raggiungere dimensioni di terabyte. I dati del grafico vengono in genere elaborati in una costosa memoria DRAM (Dynamic Random Access Memory) su più server assetati di energia.

I ricercatori del Computer Science and Artificial Intelligence Laboratory (CSAIL) del MIT hanno ora progettato un dispositivo che utilizza una memoria flash a basso costo, il tipo utilizzato negli smartphone, per elaborare enormi grafici utilizzando un solo personal computer.

La memoria flash è in genere molto più lenta della DRAM nell'elaborazione dei dati grafici. Ma i ricercatori hanno sviluppato un dispositivo costituito da un array di chip flash e un "acceleratore" di calcolo, " che aiuta il flash a raggiungere prestazioni simili a DRAM.

L'alimentazione del dispositivo è un nuovo algoritmo che ordina tutte le richieste di accesso ai dati del grafico in un ordine sequenziale a cui il flash può accedere rapidamente e facilmente. Unisce anche alcune richieste per ridurre l'overhead:il tempo di calcolo combinato, memoria, larghezza di banda, e altre risorse informatiche, di smistamento.

I ricercatori hanno eseguito il dispositivo su diversi sistemi tradizionali ad alte prestazioni che elaborano diversi grafici di grandi dimensioni, compreso l'enorme Web Data Commons Hyperlink Graph, che ha 3,5 miliardi di nodi e 128 miliardi di linee di collegamento. Per elaborare quel grafico, i sistemi tradizionali richiedevano tutti un server che costava migliaia di dollari e conteneva 128 gigabyte di DRAM. I ricercatori hanno ottenuto le stesse prestazioni collegando due dei loro dispositivi, per un totale di 1 gigabyte di DRAM e 1 terabyte di flash, a un computer desktop. Inoltre, combinando più dispositivi, potevano elaborare grafici enormi, fino a 4 miliardi di nodi e 128 miliardi di linee di connessione, che nessun altro sistema potrebbe gestire sul server da 128 gigabyte.

"La linea di fondo è che possiamo mantenere le prestazioni con molto più piccoli, meno, e più fredde, come in termini di temperatura e consumo energetico, macchine, " dice Sang-Woo Jun, uno studente laureato CSAIL e primo autore su un documento che descrive il dispositivo, presentato all'International Symposium on Computer Architecture (ISCA).

Il dispositivo potrebbe essere utilizzato per ridurre i costi e l'energia associati all'analisi dei grafici, e persino migliorare le prestazioni, in una vasta gamma di applicazioni. I ricercatori, ad esempio, stanno attualmente creando un programma che potrebbe identificare i geni che causano il cancro. Anche le principali aziende tecnologiche come Google potrebbero sfruttare i dispositivi per ridurre il loro impatto energetico utilizzando molte meno macchine per eseguire analisi.

"L'elaborazione del grafico è un'idea così generale, " dice il co-autore Arvind, il Johnson Professor in Ingegneria Informatica. "Che cosa ha in comune il ranking delle pagine con il rilevamento dei geni? Per noi, è lo stesso problema di calcolo, solo grafici diversi con significati diversi. Il tipo di applicazione che qualcuno svilupperà determinerà l'impatto che avrà sulla società".

I coautori dell'articolo sono lo studente laureato CSAIL Shuotao Xu, e Andy Wright e Sizhuo Zhang, due dottorandi del CSAIL e del Dipartimento di Ingegneria Elettrica e Informatica.

Ordina e riduci

Nell'analisi dei grafici, un sistema fondamentalmente cercherà e aggiornerà il valore di un nodo in base alle sue connessioni con altri nodi, tra le altre metriche. Nella classifica delle pagine web, ad esempio, ogni nodo rappresenta una pagina web. Se il nodo A ha un valore alto e si connette al nodo B, quindi aumenterà anche il valore del nodo B.

I sistemi tradizionali memorizzano tutti i dati grafici in DRAM, il che li rende veloci nell'elaborazione dei dati ma anche costosi e affamati di energia. Alcuni sistemi scaricano alcuni dati di archiviazione su flash, che è più economico ma più lento e meno efficiente, quindi richiedono ancora notevoli quantità di DRAM.

Il dispositivo dei ricercatori funziona con quello che i ricercatori chiamano un algoritmo di "riduzione dell'ordinamento", che risolve un grosso problema con l'utilizzo di flash come fonte di archiviazione primaria:i rifiuti.

I sistemi di analisi dei grafici richiedono l'accesso a nodi che possono essere molto distanti l'uno dall'altro attraverso un enorme, struttura del grafo sparso. I sistemi generalmente richiedono l'accesso diretto a, dire, Da 4 a 8 byte di dati per aggiornare il valore di un nodo. La DRAM fornisce questo accesso diretto molto rapidamente. Veloce, però, accede solo ai dati in blocchi da 4 a 8 kilobyte, ma aggiorna ancora solo pochi byte. Ripetere quell'accesso per ogni richiesta mentre si salta attraverso il grafico spreca larghezza di banda. "Se hai bisogno di accedere a tutti gli 8 kilobyte, e usa solo 8 byte e butta il resto, finisci per lanciare 1, 000 volte le prestazioni di distanza, "dice Jun.

L'algoritmo sort-reduce invece prende tutte le richieste di accesso diretto e le ordina in ordine sequenziale per identificatori, che mostrano la destinazione della richiesta, ad esempio raggruppando tutti gli aggiornamenti per il nodo A, tutto per il nodo B, e così via. Flash può quindi accedere a blocchi di migliaia di richieste in kilobyte contemporaneamente, rendendolo molto più efficiente.

Per risparmiare ulteriormente potenza di calcolo e larghezza di banda, l'algoritmo unisce simultaneamente i dati nei raggruppamenti più piccoli possibili. Ogni volta che l'algoritmo rileva identificatori corrispondenti, li somma in un singolo pacchetto di dati, come A1 e A2 che diventano A3. Continua così, creare pacchetti di dati sempre più piccoli con identificatori corrispondenti, finché non produce il pacchetto più piccolo possibile da ordinare. Ciò riduce drasticamente la quantità di richieste duplicate a cui accedere.

Utilizzando l'algoritmo di riduzione dell'ordinamento su due grafici di grandi dimensioni, i ricercatori hanno ridotto il totale dei dati che dovevano essere aggiornati in flash di circa il 90%.

Calcolo dello scarico

L'algoritmo di riduzione dell'ordinamento è ad alta intensità di calcolo per un computer host, però, quindi i ricercatori hanno implementato un acceleratore personalizzato nel dispositivo. L'acceleratore funge da punto intermedio tra l'host e i chip flash, eseguire tutti i calcoli per l'algoritmo. Questo scarica così tanta potenza sull'acceleratore che l'host può essere un PC o un laptop a bassa potenza che gestisce i dati ordinati ed esegue altre attività minori.

"Gli acceleratori dovrebbero aiutare l'host a calcolare, ma siamo arrivati ​​così lontano [con i calcoli] che l'host diventa irrilevante, "dice Arvind.

"Il lavoro del MIT mostra un nuovo modo di eseguire analisi su grafici molto grandi:il loro lavoro sfrutta la memoria flash per archiviare i grafici e sfrutta gli "array di porte programmabili sul campo" [circuiti integrati personalizzati] in un modo ingegnoso per eseguire sia l'analisi che il elaborazione dei dati necessaria per utilizzare efficacemente la memoria flash, "dice Keshav Pingali, un professore di informatica presso l'Università del Texas ad Austin. "A lungo termine, questo può portare a sistemi in grado di elaborare grandi quantità di dati in modo efficiente su laptop o desktop, che rivoluzionerà il modo in cui effettuiamo l'elaborazione dei big data."

Poiché l'host può essere così a bassa potenza, giugno dice, un obiettivo a lungo termine è creare una piattaforma generica e una libreria software per consentire ai consumatori di sviluppare i propri algoritmi per applicazioni oltre l'analisi dei grafi. "Potresti collegare questa piattaforma a un laptop, scaricare [il software], e scrivi semplici programmi per ottenere prestazioni di classe server sul tuo laptop, " lui dice.

Questa storia è stata ripubblicata per gentile concessione di MIT News (web.mit.edu/newsoffice/), un popolare sito che copre notizie sulla ricerca del MIT, innovazione e didattica.