Il nuovo design del chip rende i programmi paralleli eseguiti molte volte più velocemente e richiede un decimo del codice

I chip dei computer hanno smesso di diventare più veloci. Negli ultimi 10 anni, i miglioramenti delle prestazioni dei chip sono derivati ​​dall’aggiunta di unità di elaborazione note come core.

In teoria, un programma su una macchina a 64 core sarebbe 64 volte più veloce di quanto sarebbe su una macchina a core singolo. Ma raramente funziona così. La maggior parte dei programmi per computer sono sequenziali e suddividerli in modo che parti di essi possano essere eseguiti in parallelo causa tutti i tipi di complicazioni.

Nel numero di maggio/giugno della rivista Micro dell’Institute of Electrical and Electronics Engineers, i ricercatori del Computer Science and Artificial Intelligence Laboratory (CSAIL) del MIT presenteranno un nuovo design di chip che chiamano Swarm, che dovrebbe rendere i programmi paralleli non solo molto più efficienti ma anche più facile da scrivere.

Nelle simulazioni, i ricercatori hanno confrontato le versioni Swarm di sei algoritmi comuni con le migliori versioni parallele esistenti, che erano state progettate individualmente da sviluppatori di software esperti. Le versioni Swarm erano tra le tre e le 18 volte più veloci, ma generalmente richiedevano solo un decimo del codice, o anche meno. E in un caso, Swarm ha ottenuto un’accelerazione di 75 volte su un programma che gli scienziati informatici finora non erano riusciti a parallelizzare.

“I sistemi multicore sono davvero difficili da programmare”, afferma Daniel Sanchez, assistente professore presso il Dipartimento di ingegneria elettrica e informatica del MIT, che ha guidato il progetto. “Devi dividere esplicitamente il lavoro che stai facendo in attività, e quindi devi imporre una certa sincronizzazione tra le attività che accedono ai dati condivisi. Ciò che fa questa architettura, essenzialmente, è rimuovere tutti i tipi di sincronizzazione esplicita, per rendere la programmazione parallela molto più facile. C’è un insieme particolarmente difficile di applicazioni che hanno resistito alla parallelizzazione per molti, molti anni, e questi sono i tipi di applicazioni su cui ci siamo concentrati in questo documento.”

Molte di queste applicazioni implicano l’esplorazione di ciò che gli scienziati informatici chiamano grafici. Un grafico è costituito da nodi, tipicamente rappresentati come cerchi, e bordi, tipicamente rappresentati come segmenti di linea che collegano i nodi. Frequentemente, i bordi hanno numeri associati chiamati “pesi”, che potrebbero rappresentare, ad esempio, la forza delle correlazioni tra i punti dati in un set di dati o le distanze tra le città.

I grafici emergono in una vasta gamma di problemi di informatica, ma il loro uso più intuitivo potrebbe essere quello di descrivere le relazioni geografiche. Infatti, uno degli algoritmi che i ricercatori del CSAIL hanno valutato è l’algoritmo standard per trovare il percorso di guida più veloce tra due punti.

Stabilire le priorità

In linea di principio, esplorare i grafici sembrerebbe qualcosa che potrebbe essere parallelizzato: core diversi potrebbero analizzare diverse regioni di un grafico o percorsi diversi attraverso il grafico contemporaneamente. Il problema è che con la maggior parte degli algoritmi di esplorazione del grafico, diventa gradualmente chiaro che intere regioni del grafico sono irrilevanti per il problema in questione. Se, subito, i nuclei hanno il compito di esplorare quelle regioni, i loro sforzi finiscono per essere inutili.

Naturalmente, l’analisi infruttuosa di regioni irrilevanti è un problema anche per gli algoritmi di esplorazione sequenziale di grafi, non solo per quelli paralleli. Quindi gli scienziati informatici hanno sviluppato una serie di tecniche specifiche per l’applicazione per dare priorità all’esplorazione del grafico. Un algoritmo potrebbe iniziare esplorando solo quei percorsi i cui archi hanno i pesi più bassi, ad esempio, oppure potrebbe esaminare prima quei nodi con il numero più basso di archi.

Ciò che distingue Swarm dagli altri chip multicore è che ha circuiti extra per gestire quel tipo di priorità. Contrassegna le attività in base alle loro priorità e inizia a lavorare sulle attività con la priorità più alta in parallelo. Le attività con priorità più alta possono generare le proprie attività con priorità inferiore, ma Swarm le inserisce automaticamente nella sua coda di attività.

Occasionalmente, le attività in esecuzione in parallelo possono entrare in conflitto. Ad esempio, un task con priorità più bassa può scrivere dati in una particolare posizione di memoria prima che un task con priorità più alta abbia letto la stessa posizione. In questi casi, Swarm annulla automaticamente i risultati delle attività con priorità inferiore. Mantiene così la sincronizzazione tra i core che accedono agli stessi dati di cui i programmatori in precedenza dovevano preoccuparsi.

In effetti, dal punto di vista del programmatore, l’utilizzo di Swarm è piuttosto indolore. Quando il programmatore definisce una funzione, aggiunge semplicemente una riga di codice che carica la funzione nella coda delle attività di Swarm. Il programmatore deve specificare la metrica, come il peso del bordo o il numero di bordi, che il programma utilizza per assegnare la priorità alle attività, ma sarebbe comunque necessario. Di solito, adattare un algoritmo sequenziale esistente a Swarm richiede l’aggiunta di poche righe di codice.

Tenere d’occhio

Il duro lavoro ricade sul chip stesso, che Sanchez ha progettato in collaborazione con Mark Jeffrey e Suvinay Subramanian, entrambi studenti laureati del MIT in ingegneria elettrica e informatica; Cong Yan, che ha conseguito il master come membro del gruppo di Sanchez ed è ora dottoranda presso l’Università di Washington; e Joel Emer, un professore della pratica presso il Dipartimento di Ingegneria Elettrica e Informatica del MIT, e un distinto ricercatore senior presso il produttore di chip NVidia.

Il chip Swarm ha circuiti extra per memorizzare e gestire la sua coda di compiti. Ha anche un circuito che registra gli indirizzi di memoria di tutti i dati su cui stanno lavorando i suoi core. Quel circuito implementa qualcosa chiamato filtro Bloom, che stipa i dati in un’assegnazione fissa di spazio e risponde a domande sì/no sul suo contenuto. Se vengono caricati troppi indirizzi nel filtro, di tanto in tanto produrrà falsi positivi, indicando “sì, sto memorizzando quell’indirizzo”, ma non produrrà mai falsi negativi.

Il filtro Bloom è uno dei numerosi circuiti che aiutano Swarm a identificare i conflitti di accesso alla memoria. I ricercatori sono stati in grado di dimostrare che la marcatura temporale semplifica l’applicazione della sincronizzazione tra i core. Ad esempio, ogni elemento di dati è etichettato con il timestamp dell’ultima attività che lo ha aggiornato, quindi le attività con timestamp successivi sanno che possono leggere quei dati senza preoccuparsi di determinare chi altro li sta usando.

Infine, tutti i core riportano occasionalmente i timestamp delle attività con la priorità più alta che stanno ancora eseguendo. Se un core ha terminato compiti che hanno timestamp precedenti rispetto a quelli riportati dai suoi compagni, sa che può scrivere i suoi risultati nella memoria senza corteggiare alcun conflitto.

“Penso che la loro architettura abbia gli aspetti giusti del lavoro passato sulla memoria transazionale e sulla speculazione a livello di thread”, afferma Luis Ceze, professore associato di informatica e ingegneria all’Università di Washington. “‘Memoria transazionale’ si riferisce a un meccanismo per assicurarsi che più processori che lavorano in parallelo non si calpestino a vicenda. Garantisce che gli aggiornamenti alle posizioni di memoria condivise avvengano in modo ordinato. La speculazione a livello di thread è una tecnica correlata che utilizza idee di memoria transazionale per la parallelizzazione: fallo senza essere sicuro che l’attività sia parallela e, in caso contrario, annulla e riesegui in serie. L’architettura di Sanchez utilizza molti buoni pezzi di quelle idee e tecnologie in modo creativo. ”