💻 computer science

Road to scalability for efficient graph search on massively parallel neuromorphic hardware

Questo articolo introduce NEURO-MAPP, un algoritmo di percorso minimo distribuito implementato sull'hardware neuromorfico SpiNNaker 2 che dimostra una scalabilità e un'efficienza energetica superiori rispetto al tradizionale algoritmo di Dijkstra basato su CPU per vari tipi di grafi.

Autori originali: Oskar von Seeler, Elena C. Offenberg, Carlo Michaelis, Tomas Kulvicius, Jannik Luboeinski, Andrew B. Lehr, Christian Tetzlaff

Pubblicato 2026-06-30

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Oskar von Seeler, Elena C. Offenberg, Carlo Michaelis, Tomas Kulvicius, Jannik Luboeinski, Andrew B. Lehr, Christian Tetzlaff

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

L'Idea Centrale: Trovare la Rotta Più Veloce in una Folla

Immagina di essere in una città enorme e affollata e di dover trovare il percorso più breve dalla tua casa a quella di un amico. Hai due modi per farlo:

Il "Super-Pianificatore" (La CPU): Assumi una persona incredibilmente intelligente e veloce a parlare (un processore informatico tradizionale). Si siede alla sua scrivania, guarda una mappa gigante e controlla metodicamente ogni possibile percorso uno alla volta, tenendo un elenco aggiornato delle migliori opzioni. È molto bravo, ma può fare solo una cosa alla volta.
La "Mente Alveare" (Il Chip Neuromorfico): Invece di una sola persona, assumi 152 piccoli lavoratori a basso consumo energetico (i core di un chip SpiNNaker 2). Assegni a ogni lavoratore un piccolo quartiere della città. Invece di parlare con un capo centrale, si limitano a gridare ai loro vicini immediati: "Ehi, ho trovato una scorciatoia!". Se un vicino sente un percorso migliore, lo grida ai propri vicini. Tutti lavorano contemporaneamente, scambiandosi messaggi come in un gioco del "telefono senza fili", ma usando la matematica.

Questo documento presenta un nuovo modo di giocare a questo gioco del "telefono senza fili", chiamato NEURO-MAPP. I ricercatori volevano vedere se questo approccio a "Mente Alveare" potesse trovare il percorso più breve più velocemente e consumando meno energia rispetto al "Super-Pianificatore".

Come Funziona NEURO-MAPP: Il Gioco dell' "Aggiungi e Minimo"

Nel metodo tradizionale del "Super-Pianificatore" (l'algoritmo di Dijkstra), il computer deve fermarsi continuamente, organizzare il suo elenco e scegliere l'opzione migliore. È come un bibliotecario che deve camminare verso ogni singolo scaffale per trovare il libro giusto prima di passare al successivo.

NEURO-MAPP cambia le regole per adattarsi all'hardware della "Mente Alveare":

L'Aggiunta: Quando un lavoratore trova un percorso, aggiunge il "costo" (distanza) della strada appena percorsa al suo totale attuale.
Il Minimo: Quando un lavoratore riceve un messaggio da un vicino che dice: "Posso arrivarci in 10 passi", lo confronta con ciò che sa già. Se 10 è meglio del suo record attuale, aggiorna il suo numero e lo grida ai suoi vicini.

Poiché ogni lavoratore fa questo contemporaneamente, il "percorso migliore" si propaga attraverso l'intera città in un colpo solo, senza che nessuno debba fermarsi a organizzare un elenco maestro.

La Corsa: Chi Vince?

I ricercatori hanno testato questo sistema su un singolo chip (SpiNNaker 2) contro un moderno processore per computer (CPU). Hanno corso la gara su quattro diversi tipi di "città":

Città Casuali: Dove le strade si collegano in modo casuale.
- Risultato: Per le città piccole, il Super-Pianificatore è stato più veloce. Ma man mano che la città diventava enorme (oltre i 30.000 incroci), la Mente Alveare ha preso il comando, finendo circa il 25% più velocemente.
Città "Small-World": Come le reti sociali o le reti elettriche, dove la maggior parte dei vicini è vicina, ma poche "corsie preferenziali" collegano parti distanti.
- Risultato: La Mente Alveare è stata molto più veloce per le versioni grandi di queste città.
Città a Griglia: Come una città perfetta con strade dritte (griglie 2D o 3D).
- Risultato: Nelle griglie 3D semplici, il Super-Pianificatore era ancora leggermente più veloce. Tuttavia, in griglie 5D complesse (che rappresentano dati molto complicati), la Mente Alveare è diventata la vincitrice.
Città del Mondo Reale:
- Strade: Sulle mappe stradali tedesche reali, il Super-Pianificatore è attualmente più veloce perché le mappe non erano ancora abbastanza grandi da mostrare tutto il potenziale della Mente Alveare.
- Droni in una Città: Mappando un ambiente urbano 3D per i droni (evitando gli edifici), la Mente Alveare è stata significativamente più veloce e ha usato 10 volte meno energia.
- Reti Proteiche: Nelle mappe biologiche di come interagiscono le proteine, la Mente Alveare ha usato molta meno energia, anche se ha impiegato un po' più tempo per finire il lavoro.

Il Fattore Energia: Il Test della Batteria

La scoperta più entusiasmante non è stata solo la velocità; è stata l'energia.

Il "Super-Pianificatore" (CPU) è come un'auto sportiva ad alte prestazioni: va veloce, ma consuma tantissima benzina (elettricità).
La "Mente Alveare" (SpiNNaker 2) è come una flotta di scooter elettrici: singolarmente possono sembrare più lenti, ma poiché ci sono così tanti di loro che lavorano insieme in modo efficiente, l'intero gruppo utilizza una frazione minima dell'energia.

In quasi tutti i test, la Mente Alveare ha utilizzato meno energia per query rispetto alla CPU, anche quando la CPU terminava il compito leggermente più velocemente.

Perché Questo è Importante (Secondo il Documento)

Il documento sostiene che questo approccio a "Mente Alveare" sia una soluzione scalabile.

Scalabilità: Se hai bisogno di risolvere un problema per una città grande quanto un intero paese, puoi semplicemente aggiungere altri chip (più lavoratori) alla rete. Il sistema cresce naturalmente.
Versatilità: I ricercatori hanno dimostrato che questo funziona non solo per le indicazioni stradali, ma anche per:
- Pianificare i voli dei droni tra i grattacieli.
- Analizzare come le proteine interagiscono nel corpo umano.
- Semplificare dati complessi (come trasformare una forma a 10 dimensioni in una mappa 3D) usando un metodo chiamato Isomap.

In Sintesi

Il documento sostiene che, per problemi massicci e complessi, il vecchio modo di pensare (un unico cervello che fa tutto) sta raggiungendo un limite. Il nuovo modo (molti piccoli cervelli che comunicano localmente tra loro) è il futuro. Non si tratta solo di essere più veloci; si tratta di essere in grado di risolvere problemi enormi senza bruciare tutta l'elettricità del mondo.

Nota: Gli autori sottolineano che, sebbene il loro chip attuale (SpiNNaker 2) sia specifico, l'idea di questo algoritmo potrebbe funzionare su qualsiasi sistema che abbia molti processori indipendenti che possono comunicare rapidamente tra loro, come altri chip specializzati progettati per il calcolo di tipo cerebrale.

Sintesi Tecnica: La strada verso la scalabilità per la ricerca efficiente su grafi su hardware neuromorfico massivamente parallelo

Problema
Il calcolo dei cammini minimi in grafi pesati è un problema fondamentale con applicazioni critiche nella pianificazione dei percorsi, il routing di rete, la pianificazione delle azioni robotiche e la riduzione della dimensionalità non lineare (ad esempio, Isomam). Sebbene gli algoritmi sequenziali stabiliti come l'algoritmo di Dijkstra siano efficaci su hardware convenzionale, essi affrontano sfide di scalabilità ed efficienza energetica quando applicati a grafi su larga scala o in ambienti multi-utente. Gli approcci paralleli esistenti per GPU e CPU spesso si affidano a meccanismi di coordinamento globale che sono costosi in architetture distribuite o basate su eventi. L'hardware neuromorfico, caratterizzato da computazione e memoria co-localizzate e comunicazione basata su eventi, offre una potenziale soluzione ma richiede algoritmi in grado di minimizzare la sincronizzazione globale per sfruttare i suoi vantaggi intrinseci.

Metodologia: NEURO-MAPP
Gli autori introducono NEURO-MAPP (Neuromorphic-based Min-Add Parallel Propagation), un algoritmo di cammino minimo distribuito progettato specificamente per sistemi neuromorfici. Il concetto centrale consiste nell'incorporare un grafo pesato in un grafo computazionale dove:

Operazioni Locali: I vertici eseguono una minimizzazione locale sui segnali di distanza in ingresso per selezionare la distanza candidata più piccola.
Operazioni di Arco: Gli archi propagano gli aggiornamenti di distanza aggiungendo i loro pesi associati al segnale in ingresso.
Dinamiche: I cammini minimi emergono attraverso dinamiche di aggiornamento puramente locali e parallele, senza richiedere coordinamento globale.

L'algoritmo è stato implementato sulla piattaforma SpiNNaker 2, un sistema neuromorfico massivamente parallelo che presenta 152 core ARM per chip, ciascuno con SRAM dedicata e collegato tramite una rete on-chip (NoC) a bassa latenza. Le strategie di implementazione chiave hanno incluso:

Partizionamento dei Vertici: Per affrontare gli squilibri di carico causati da distribuzioni di grado asimmetriche (ad esempio, i "hub" nelle reti proteiche), gli autori hanno sviluppato una strategia di partizionamento consapevole del grado del vertice. Questa assegna i vertici ai core per minimizzare il grado cumulativo per core, prevenendo colli di bottiglia. Per altri tipi di grafi, sono stati utilizzati assegnazioni casuali o a minimizzazione di banda.
Ottimizzazione del Passaggio di Messaggi: Sono stati confrontati due metodi per codificare gli aggiornamenti di distanza. Un approccio "basato sul predecessore", che memorizza direttamente gli archi uscenti sul core sorgente ed esegue ricerche a tempo costante, si è rivelato significativamente superiore all'approccio predefinito "basato sul successore" (che richiede una ricerca binaria sugli archi in ingresso) per grafi sparsi e ad alta connettività, riducendo il tempo di ricerca fino a un fattore di 10.
Scheduling delle Iterazioni Dinamico: Per mitigare i tempi di inattività causati dai carichi di lavoro variabili tra i core, è stato implementato un coordinatore globale leggero. I core segnalano il completamento a uno scheduler, il quale innesca l'iterazione successiva solo quando tutti i core sono pronti, garantendo la sincronizzazione senza passi temporali fissi e dispendiosi.

Risultati Chiave
Le prestazioni di NEURO-MAPP su un singolo chip SpiNNaker 2 sono state valutate rispetto all'algoritmo di Dijkstra su una CPU moderna (M1 Pro) attraverso grafi sintetici e reali:

Scalabilità e Tempo di Esecuzione:
- Grafi Casuali e Small-World: NEURO-MAPP ha dimostrato una scalabilità superiore. Mentre l'algoritmo di Dijkstra ha performato meglio su grafi piccoli, il tempo di esecuzione di NEURO-MAPP è cresciuto logaritmicamente con la dimensione del grafo, superando Dijkstra per grafi con oltre ~30.000–38.000 vertici.
- Grafi a Griglia: Per i grafi a griglia 3D, l'algoritmo di Dijkstra è rimasto più veloce a causa del diametro maggiore di questi grafi, che richiede più iterazioni per NEURO-MAPP. Tuttavia, per griglie a dimensionalità superiore (es. 5D), NEURO-MAPP ha mostrato un vantaggio nel tempo di esecuzione di circa il 20%.
- Applicazioni Reali: Nella navigazione aerea 3D (ambiente urbano tipo Manhattan), NEURO-MAPP ha risolto il problema in 6,1 ms rispetto ai 6,8 ms di Dijkstra. Al contrario, per la navigazione in reti stradali (distretti tedeschi), NEURO-MAPP era attualmente più lento (di un ordine di grandezza) a causa della topologia specifica e delle dimensioni delle reti testate, sebbene gli autori prevedano che supererà Dijkstra a scale più ampie.
- Reti di Interazione Proteica: Nonostante i tempi di esecuzione più lunghi sulle attuali dimensioni di rete, NEURO-MAPP ha mostrato tendenze favorevoli per reti più grandi con topologie simili.
Efficienza Energetica:
- In tutti i tipi di grafi testati, NEURO-MAPP ha consumato significativamente meno energia per query di cammino minimo rispetto all'implementazione CPU.
- Il chip SpiNNaker 2 ha consumato meno di 500 mW durante l'esecuzione, rispetto ai circa 4 W della CPU. Anche nei casi in cui NEURO-MAPP aveva un tempo di esecuzione più lungo, il minor assorbimento di potenza ha garantito un consumo energetico totale inferiore (ad esempio, 2,4 mJ contro 25,5 mJ per il compito di navigazione aerea).
Integrazione con Isomap:
- Gli autori hanno integrato NEURO-MAPP nel framework di riduzione della dimensionalità Isomap per calcolare la matrice dei cammini minimi tra tutte le coppie (APSP). NEURO-MAPP ha dimostrato prestazioni superiori per dataset più grandi e un numero maggiore di vicini più prossimi ( $k$ ), validando la sua utilità come componente in pipeline algoritmiche più ampie.

Significato e Rivendicazioni
L'articolo sostiene che NEURO-MAPP dimostra il potenziale dell'hardware neuromorfico dotato di comunicazione sparsa e basata su spike come piattaforma scalabile ed efficiente dal punto di vista energetico per la ricerca su grafi. Gli autori sottolineano che, sebbene confrontare un algoritmo sequenziale a singolo core con un sistema massivamente parallelo possa sembrare ingiusto, la metrica di interesse è il tempo di esecuzione totale e l'energia necessaria per completare un compito.

Le rivendicazioni principali includono:

Efficienza Energetica: L'hardware neuromorfico può risolvere problemi di cammino minimo con un consumo energetico significativamente inferiore rispetto alle implementazioni CPU, anche quando l'algoritmo parallelo non è ancora il più veloce in termini di tempo assoluto per tutte le dimensioni dei grafi.
Scalabilità: L'algoritmo scala favorevolmente per famiglie di grafi con diametri bassi (grafi casuali, small-world, griglie ad alta dimensionalità), suggerendo che sistemi neuromorfici multi-chip potrebbero risolvere problemi attualmente proibitivi per applicazioni con vincoli energetici.
Agnosticismo Hardware: Sebbene implementato su SpiNNaker 2, gli autori notano che l'algoritmo è applicabile a qualsiasi sistema con sufficienti unità parallele indipendenti, memoria locale e comunicazione a bassa latenza, inclusi altri sistemi neuromorfici come Loihi 2 o Graphcore IPU.

Gli autori rimangono modesti riguardo alle attuali limitazioni, riconoscendo che per specifici tipi di grafi (come le reti stradali 2D) e per gli attuali vincoli del singolo chip, l'algoritmo di Dijkstra rimane più veloce. Tuttavia, essi sostengono che i vantaggi energetici e le tendenze di scalabilità logaritmica indichino una chiara strada verso prestazioni superiori su sistemi multi-chip neuromorfici più grandi.