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

I computer moderni sono spesso frenati non da quanto velocemente possano calcolare, ma da quanto velocemente possano spostare i dati. Nel mondo dell'informatica ad alte prestazioni, dove le macchine affrontano problemi complessi come la mappatura della diffusione delle malattie, l'analisi delle reti sociali o la simulazione del cambiamento climatico, il compito più comune non è elaborare numeri, ma prelevarli dalla memoria. Ciò è particolarmente vero quando si trattano dati "sparsi", un termine che descrive informazioni in cui la maggior parte dello spazio potenziale è vuota. Immaginate un enorme foglio di calcolo in cui solo alcune celle sparse contengono numeri, mentre il resto è vuoto. Quando un computer cerca di leggere questi numeri sparsi, spesso deve saltare in modo imprevedibile nel sistema di memoria, un processo noto come accesso indiretto. Poiché questi salti sono casuali, il computer non può prevedere facilmente quali dati saranno necessari successivamente, rendendo il compito di spostare le informazioni dall'archiviazione al processore un importante collo di bottiglia che rallenta l'intero sistema e spreca energia.

Per capire perché questo sia difficile, bisogna osservare come i computer memorizzano attualmente i dati. La memoria standard dei computer è organizzata in blocchi di dimensioni fisse, molto simile a una biblioteca che presta solo interi libri alla volta, anche se un lettore ne ha bisogno solo di una singola pagina. Quando un computer richiede uno specifico pezzo di dati, il sistema di memoria recupera un intero blocco, noto come cache line, che è tipicamente di sessantaquattro byte. Se il computer ha bisogno solo di uno o due numeri da quel blocco, il resto dei dati viene recuperato e memorizzato inutilmente, consumando energia e intasando i percorsi dei dati. Questa inefficienza diventa un problema grave per i carichi di lavoro "sparsi", dove il computer potrebbe dover raccogliere decine di numeri non correlati da diverse parti della memoria per eseguire un singolo calcolo. In questi scenari, il computer passa più tempo a spostare dati inutili che a svolgere il lavoro effettivo.

Un team di ricercatori della New Mexico State University, del Lawrence Berkeley National Laboratory e della Florida International University ha proposto un nuovo modo per gestire questo problema, chiamato SecBCache. Il loro lavoro si concentra su un tipo specifico di architettura informatica utilizzata per le simulazioni scientifiche e l'apprendimento automatico, dove i dati vengono spesso acceduti in un modello sparso e irregolare. I ricercatori hanno progettato un componente di memoria specializzato che cambia le regole di come i dati vengono recuperati e memorizzati. Invece di prendere un grande blocco di dati di dimensioni fisse, il loro design consente al computer di recuperare e memorizzare solo i minuscoli pezzi specifici di informazioni di cui ha realmente bisogno. Hanno testato questa idea utilizzando una simulazione dettagliata di un processore moderno, eseguendola contro dataset reali utilizzati nell'analisi dei grafi e nella moltiplicazione di matrici. I risultati hanno mostrato che questo nuovo approccio può ridurre significativamente la quantità di dati che il computer scrive nella sua memoria, abbassare l'energia richiesta per eseguire questi compiti e potenzialmente velocizzare il tempo necessario per accedere alle informazioni, il tutto senza richiedere modifiche ai linguaggi di programmazione o alle istruzioni fondamentali che il computer comprende.

Il nucleo dell'innovazione dei ricercatori risiede in come hanno riorganizzato l'archiviazione della memoria. Hanno suddiviso lo standard grande blocco di memoria in pezzi più piccoli da otto byte, che chiamano sottosettori. In un sistema tradizionale, se un computer ha bisogno di un numero da un blocco, deve caricare l'intero blocco. Nel sistema SecBCache, la memoria è divisa in otto sezioni separate, o bank, che possono essere accedute simultaneamente. Quando il computer ha bisogno di raccogliere un elenco di numeri sparsi, può inviare richieste a questi diversi bank contemporaneamente, recuperando solo i pezzi specifici da otto byte richiesti. Questo è simile a una biblioteca che, invece di consegnarti un intero libro, ha otto impiegati diversi che possono estrarre una singola pagina di cui hai bisogno da libri diversi esattamente nello stesso momento. Questo design permette al computer di evitare lo spreco di recuperare dati inutilizzati pur mantenendo la velocità e l'organizzazione di un sistema di memoria standard.

Per vedere se questa idea funzionerebbe in pratica, i ricercatori hanno costruito una versione virtuale di un processore per computer utilizzando uno strumento chiamato gem5, che simula il comportamento dell'hardware a un livello molto dettagliato. Hanno programmato questo computer virtuale per eseguire due tipi comuni di compiti scientifici: una ricerca in ampiezza (breadth-first search), che è un metodo per esplorare reti come le connessioni dei social media o le mappe stradali, e una moltiplicazione di matrici sparse, un calcolo usato nella fisica e nell'ingegneria che coinvolge la moltiplicazione di grandi griglie di numeri dove la maggior parte delle voci è zero. Hanno testato questi compiti utilizzando sedici diversi dataset reali, che vanno dalle reti di email ai modelli di reti elettriche. Per ogni compito, hanno confrontato le prestazioni del loro nuovo design SecBCache rispetto a una cache di memoria convenzionale standard che utilizza i tradizionali grandi blocchi.

Le simulazioni hanno rivelato una differenza sorprendente di efficienza. In un sistema standard, il computer spesso recuperava un intero blocco di dati ma finiva per usarne meno della metà, e in alcuni casi, solo il diciotto percento. Ciò significa che, per ogni pezzo di dato utile recuperato, il sistema stava sprecando energia e larghezza di banda spostando diversi pezzi di dati inutili. Il design SecBCache ha eliminato questo spreco recuperando solo i pezzi specifici da otto byte necessari. Per i compiti di ricerca nei grafi, il nuovo design ha ridotto la quantità di dati scritti nella memoria di un valore mediano del sessantatré percento. Per i compiti di moltiplicazione di matrici, la riduzione è stata ancora più drammatica, con una diminuzione mediana dell'ottanta percento dei dati scritti. Ciò significa che per molti dei dataset testati, il nuovo sistema ha scritto solo una frazione dei dati che il vecchio sistema ha scritto, riducendo drasticamente il traffico interno che rallenta i computer.

Oltre al semplice risparmio di spazio, i ricercatori hanno anche esaminato come questo design influenzi la velocità di accesso alla memoria. Poiché il nuovo sistema può accedere a più bank contemporaneamente, ha il potenziale per servire molte richieste in parallelo. Tuttavia, i ricercatori hanno notato che il guadagno effettivo di velocità dipende da come i dati sono distribuiti. Hanno creato un modello matematico per stimare il tempo necessario per accedere ai dati, calcolando sia uno scenario ottimale in cui tutto funziona perfettamente, sia uno scenario peggiore in cui le richieste rimangono bloccate in attesa dello stesso bank. Sotto le assunzioni conservative dello scenario peggiore, il modello ha previsto che il nuovo sistema avrebbe ridotto i ritardi di accesso alla memoria del ventisei percento per i compiti di ricerca nei grafi e del cinquanta percento per la moltiplicazione di matrici. Questi numeri rappresentano il tempo che il sistema di memoria impiega per rispondere, non il tempo totale che il computer impiega per finire l'intero programma, ma indicano un miglioramento significativo di quanto velocemente il processore può ottenere i dati di cui ha bisogno.

I ricercatori hanno anche esaminato il costo fisico della costruzione di un tale sistema. Hanno utilizzato uno standard strumento del settore per stimare la dimensione e il consumo energetico del nuovo design della memoria. Hanno scoperto che l'hardware aggiuntivo richiesto per gestire questi pezzi più piccoli e suddivisi occuperebbe al massimo il 2,46 percento dell'area totale della gerarchia di memoria del computer. Questa è un'impronta molto piccola, il che suggerisce che il design potrebbe essere aggiunto ai moderni processori senza occupare spazio significativo. Inoltre, poiché il nuovo sistema scrive molti meno dati nelle matrici di memoria, consuma anche meno energia. Le simulazioni hanno mosto che l'energia dinamica utilizzata dal sistema di memoria è diminuita per ogni singolo dataset testato, con riduzioni che vanno da pochi percento a oltre l'ottanta percento a seconda di quanto i dati fossero sparsi.

Uno degli aspetti più importanti di questo lavoro è che non richiede ai programmatori di riscrivere il proprio codice o di imparare nuovi modi per dire al computer cosa fare. I ricercatori hanno progettato SecBCache affinché funzioni con le istruzioni esistenti che i computer usano già per raccogliere e disperdere i dati. Nei moderni processori, esistono comandi specifici che permettono a una singola istruzione di caricare molteplici pezzi di dati non contigui. Il nuovo sistema di memoria rende semplicemente questi comandi esistenti più efficienti, assicurando che vengano spostati solo i dati necessari. L'unica modifica richiesta sarebbe un semplice marcatore software che dice al computer quali parti della memoria contengono questo tipo di dati sparsi, permettendo all'hardware di instradare automaticamente quelle richieste verso il nuovo sistema. Questo approccio evita la necessità di complessi nuovi modelli di programmazione o di acceleratori hardware specializzati che spesso falliscono nell'essere adottati dall'industria più ampia.

Lo studio ha anche evidenziato dove questo approccio potrebbe non essere altrettanto efficace. Nei casi in cui i dati acceduti sono molto densi e prevedibili, come quando un computer legge una lunga lista di numeri che si trovano l'uno accanto all'altro, il sistema tradizionale di recupero di grandi blocchi funziona molto bene. In questi scenari specifici, il nuovo sistema a volte ha performato leggermente peggio perché doveva recuperare ogni pezzo individualmente, perdendo il beneficio dei dati "gratuiti" che derivano da un grande blocco. Tuttavia, i ricercatori hanno sottolineato che il loro design è mirato specificamente alla classe crescente di problemi che coinvolgono dati sparsi e irregolari, che stanno diventando sempre più comuni nei campi dell'intelligenza artificiale e dell'analisi dei big data. Per queste applicazioni, la capacità di recuperare solo ciò che è necessario supera i benefici del recuperare tutto in una volta.

I ricercatori sono stati attenti a distinguere tra ciò che hanno misurato direttamente e ciò che hanno stimato. Le riduzioni nei dati scritti e i risparmi energetici sono stati misurati direttamente dalla simulazione del sistema di memoria. I miglioramenti nella velocità di accesso, tuttavia, sono stati derivati da un modello matematico che stimava come il sistema si sarebbe comportato se potesse gestire più richieste contemporaneamente. Mentre la simulazione mostrava che l'hardware poteva gestire le richieste, il modello forniva un intervallo di possibili ritardi basati sulla frequenza con cui diverse parti della memoria verrebbero interrogate contemporaneamente. I ricercatori hanno notato che questi sono ritardi modellati e non accelerazioni garantite per l'applicazione finale, ma forniscono un forte indizio del fatto che il sottosistema di memoria sarebbe meno soggetto a colli di bottiglia.

Nel contesto più ampio dell'informatica, questo lavoro affronta un cambiamento fondamentale nel modo in cui l'informatica si sta evolvendo. Mentre le macchine si allontanano dai semplici calcoli lineari verso compiti complessi guidati dai dati, le vecchie assunzioni su come la memoria dovrebbe funzionare stanno diventando meno rilevanti. L'idea che un computer debba sempre recuperare un grande blocco di dati è un'eredità di un'era in cui i dati erano densi e prevedibili. Il design SecBCache offre uno sguardo verso un futuro in cui i sistemi di memoria sono più flessibili, capaci di adattarsi alle esigenze irregolari degli algoritmi moderni. Dimostrando che è possibile costruire un sistema di memoria che sia allo stesso tempo altamente efficiente e compatibile con il software esistente, i ricercatori hanno fornito un percorso pratico per migliorare le prestazioni della prossima generazione di strumenti scientifici e analitici.

Lo studio conclude che, sebbene non esista una soluzione unica che si adatti a ogni problema informatico, la sfida specifica del trattamento dell'accesso ai dati sparsi e indiretti può essere risolta con un cambiamento architettonico mirato. I ricercatori hanno dimostrato che, scomponendo la memoria in pezzi più piccoli e indipendentemente accessibili e organizzandoli in modo da consentire l'accesso parallelo, è possibile ridurre drasticamente lo spreco di energia e larghezza di banda che affligge gli attuali sistemi. Questo approccio non richiede una rivoluzione nel modo in cui programmiamo i computer, ma piuttosto un'evoluzione nel modo in cui l'hardware gestisce i dati che gli chiediamo già di elaborare. Con l'aumento della domanda di elaborazione di grandi e complessi dataset, design come SecBCache potrebbero diventare essenziali per mantenere i computer veloci ed efficienti dal punto di vista energetico, assicurando che il collo di bottiglia del movimento dei dati non freni il potenziale dei calcoli stessi.