💻 computer science

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

Dit artikel introduceert NEURO-MAPP, een gedistribueerd kortste pad-algoritme geïmplementeerd op de SpiNNaker 2 neuromorfische hardware dat een superieure schaalbaarheid en energie-efficiëntie demonstreert vergeleken met het traditionele CPU-gebaseerde Dijkstra-algoritme voor diverse typen grafen.

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

Gepubliceerd 2026-06-30

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

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

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Grote Idee: De Snelste Route Vinden in een Menigte

Stel je voor dat je in een enorme, drukke stad bent en de kortste route van je huis naar het huis van een vriend moet vinden. Je hebt twee manieren om dit te doen:

De "Super-Planner" (De CPU): Je huurt één ongelooflijk slimme, snel pratende persoon in (een traditionele computerprocessor). Deze persoon zit aan een bureau, bekijkt een gigantische kaart en controleert methodisch één voor één alle mogbare routes, terwijl hij een lijst bijhoudt van de beste opties. Ze zijn erg goed, maar kunnen slechts één ding tegelijk doen.
De "Hive Mind" (De Neuromorfe Chip): In plaats van één persoon, huur je 152 kleine, energiezuinige werkers in (de kernen van een SpiNNaker 2-chip). Je geeft elke werker een klein buurtje van de stad. In plaats van met een centrale baas te praten, roepen ze gewoon naar hun directe buren: "Hé, ik heb een kortere weg gevonden!" Als een buurman een betere route hoort, roept hij het door naar zijn buren. Iedereen werkt tegelijkertijd en wisselt berichten uit als een spelletje "telefoontje", maar dan met wiskunde.

Dit papier introduceert een nieuwe manier om dit "telefoontje"-spel te spelen, genaamd NEURO-MAPP. De onderzoekers wilden zien of deze "Hive Mind"-aanpak de kortste route sneller kon vinden en minder energie zou verbruiken dan de "Super-Planner".

Hoe NEURO-MAPP Werkt: Het "Optellen en Minimaliseren"-spel

In de traditionele "Super-Planner"-methode (Dijkstra's algoritme) moet de computer constant stoppen, zijn lijst organiseren en de beste optie kiezen. Het is als een bibliothecaris die naar elke plank moet lopen om het juiste boek te zoeken voordat hij naar de volgende kan gaan.

NEURO-MAPP verandert de regels om aan te sluiten bij de "Hive Mind"-hardware:

Het Optellen: Wanneer een werker een pad vindt, telt hij de "kosten" (afstand) van de weg die hij net heeft afgelegd op bij zijn huidige totaal.
Het Minimaliseren: Wanneer een werker een bericht ontvangt van een buurman die zegt: "Ik kan daar in 10 stappen komen," vergelijkt hij dat met wat hij al weet. Als 10 beter is dan zijn huidige beste optie, werkt hij zijn getal bij en roept hij het door naar zijn buren.

Omdat elke werker dit gelijktijdig doet, golft de "beste route" tegelijkertijd door de hele stad, zonder dat iemand hoeft te stoppen om een meesterlijst te organiseren.

De Race: Wie Wint?

De onderzoekers testten dit op een enkele chip (SpiNNaker 2) tegenover een moderne computerprocessor (CPU). Ze voerden de race op vier verschillende soorten "steden":

Willekeurige Steden: Waar wegen willekeurig met elkaar verbonden zijn.
- Resultaat: Voor kleine steden was de Super-Planner sneller. Maar naarmate de stad enorm groot werd (meer dan 30.000 kruispunten), nam de Hive Mind de leiding en was ongeveer 25% sneller.
Small-World Steden: Zoals sociale netwerken of elektriciteitsnetten, waarbij de meeste buren dichtbij zijn, maar een paar "expressbanen" verre delen met elkaar verbinden.
- Resultaat: De Hive Mind was veel sneller voor grote versies van deze steden.
Grid Steden: Zoals een perfecte stad met rechte straten (2D of 3D rasters).
- Resultaat: In eenvoudige 3D-rasters was de Super-Planner nog steeds iets sneller. Echter, in complexe 5D-rasters (die zeer ingewikkelde data vertegenwoordigen), werd de Hive Mind de winnaar.
Echte Steden:
- Wegen: Op werkelijke Duitse wegenkaarten was de Super-Planner momenteel sneller omdat de kaarten nog niet groot genoeg waren om de volledige kracht van de Hive Mind te tonen.
- Drones in een Stad: Bij het in kaart brengen van een 3D stedelijke omgeving voor drones (om gebouwen te vermijden), was de Hive Mind aanzienlijk sneller en gebruikte hij 10 keer minder energie.
- Eiwitnetwerken: In biologische kaarten van hoe eiwitten met elkaar interageren, gebruikte de Hive Mind veel minder energie, zelfs als het iets langer duurde om de taak te voltooien.

De Energiefactor: De Batterijtest

De meest opwindende bevinding was niet alleen snelheid, maar energie.

De "Super-Planner" (CPU) is als een high-performance sportwagen: hij gaat snel, maar verbruikt veel benzine (elektriciteit).
De "Hive Mind" (SpiNNaker 2) is als een vloot elektrische scooters: individueel lijken ze misschien langzamer, maar omdat er zoveel van hen efficiënt samenwerken, gebruikt de hele groep een fractie van de energie.

In bijna elke test gebruikte de Hive Mind minder energie per query dan de CPU, zelfs wanneer de CPU de taak iets sneller voltooide.

Waarom Dit Belangrijk Is (Volgens het Papier)

Het papier stelt dat deze "Hive Mind"-aanpak een schaalbare oplossing is.

Schaalbaarheid: Als je een probleem moet oplossen voor een stad ter grootte van een heel land, kun je gewoon meer chips (meer werkers) aan het netwerk toevoegen. Het systeem groeit op natuurlijke wijze mee.
Veelzijdigheid: De onderzoekers hebben aangetoond dat dit niet alleen werkt voor rijrichtingen, maar ook voor:
- Het plannen van dronevluchten tussen wolkenkrabbers.
- Het analyseren van hoe eiwitten interageren in het menselijk lichaam.
- Het vereenvoudigen van complexe data (zoals het omzetten van een 10-dimensionale vorm naar een 3D-kaart) met behulp van een methode genaamd Isomap.

De Kern van de Zaak

Het papier betoogt dat voor enorme, complexe problemen de oude manier van denken (één brein dat alles doet) tegen een muur aanloopt. De nieuwe manier (veel kleine breinen die lokaal met elkaar communiceren) is de toekomst. Het gaat niet alleen om sneller zijn; het gaat erom dat je enorme problemen kunt oplossen zonder alle elektriciteit van de wereld te verbranden.

Noot: De auteurs benadrukken dat hoewel hun huidige chip (SpiNNaker 2) specifiek is, het idee van dit algoritme op elk systeem zou kunnen werken dat beschikt over veel onafhankelijke processoren die snel met elkaar kunnen communiceren, zoals andere gespecialiseerde computerchips die ontworpen zijn voor hersenachtige computing.

Technische Samenvatting: De weg naar schaalbaarheid voor efficiënt graafonderzoek op massaal parallelle neuromorfische hardware

Probleemstelling
De berekening van kortste paden in gewogen grafen is een fundamenteel probleem met kritieke toepassingen in routeplanning, netwerkrouting, robotische actieplanning en niet-lineaire dimensionaliteitsreductie (bijv. Isomap). Hoewel gevestigde sequentiële algoritmen zoals Dijkstra's algoritme effectief zijn op conventionele hardware, kampen zij met uitdagingen op het gebied van schaalbaarheid en energie-efficiëntie wanneer ze worden toegepast op grootschalige grafen of multi-user omgevingen. Bestaande parallelle benaderingen voor GPU's en CPU's vertrouwen vaak op globale coördinatiemechanismen die kostbaar zijn in gedistribueerde of event-gestuurde architecturen. Neuromorfische hardware, gekenmerkt door co-gelokaliseerde berekening en geheugen en event-gebaseerde communicatie, biedt een potentiële oplossing, maar vereist algoritmen die globale synchronisatie minimaliseren om optimaal gebruik te maken van de inherente sterktes.

Methodologie: NEURO-MAPP
De auteurs introduceren NEURO-MAPP (Neuromorphic-based Min-Add Parallel Propagation), een gedistribueerd kortste-pad-algoritme dat specifiek is ontworpen voor neuromorfische systemen. Het kernconcept houdt in dat een gewogen graaf wordt ingebed in een computationele graaf waarbij:

Lokale Operaties: Vertices (knopen) voeren lokale minimalisatie uit over inkomende afstandssignalen om de kleinste kandidaat-afstand te selecteren.
Edge Operaties: Edges (randen) propageren afstandupdates door hun bijbehorende gewichten op te tellen bij het inkomende signaal.
Dynamiek: Kortste paden ontstaan door puur lokale, parallelle update-dynamiek zonder dat globale coördinatie vereist is.

Het algoritme werd geïmplementeerd op het SpiNNaker 2 platform, een massaal parallel neuromorfisch systeem met 152 ARM-kernen per chip, waarbij elke kern beschikt over dedicated SRAM en verbonden is via een low-latency network-on-chip (NoC). Belangrijke implementatiestrategieën omvatten:

Vertex Partitioning: Om lastonbalans aan te pakken die wordt veroorzaakt door scheve graadverdelingen (bijv. "hubs" in proteïne-netwerken), hebben de auteurs een vertex-graad-bewuste partitioneringsstrategie ontwikkend. Deze wijst vertices toe aan kernen om de cumulatieve graad per kern te minimaliseren, waardoor bottlenecks worden voorkomen. Voor andere typen grafen werden gerandomiseerde of bandbreedte-minimaliserende toewijzingen gebruikt.
Message Passing Optimalisatie: Twee methoden voor het coderen van afstandupdates werden vergeleken. Een "predecessor-gebaseerde" benadering, die de uitgaande edges direct op de bronkern opslaat en constant-tijd lookups uitvoert, bleek aanzienlijk beter te presteren dan de standaard "successor-gebaseerde" benadering (die binaire zoekopdrachten op inkomende edges vereist) voor ijle en hoog-verbonden grafen, wat de zoektijd met een factor tot wel 10 verminderde.
Dynamische Iteratie Planning: Om de dode tijd te beperken die wordt veroorzaakt door variabele workloads over de kernen, is een lichtgewicht globale coördinator geïmplementeerd. Kernen signaleren voltooiing aan een scheduler, die de volgende iteratie pas triggert wanneer alle kernen gereed zijn, wat synchronisatie garandeert zonder vaste, verspillende tijdstappen.

Belangrijkste Resultaten
De prestaties van NEURO-MAPP op een enkele SpiNNaker 2 chip werden geëvalueerd tegen Dijkstra's algoritme op een moderne CPU (M1 Pro) over synthetische en real-world grafentypes:

Schaalbaarheid en Runtime:
- Random en Small-World Grafen: NEURO-MAPP demonstreerde superieure schaalbaarheid. Terwijl Dijkstra's algoritme beter presteerde op kleine grafen, groeide de runtime van NEURO-MAPP logaritmisch met de grafengrootte, waarmee het Dijkstra's overtrof voor grafen met meer dan ~30.000–38.000 vertices.
- Grid Grafen: Voor 3D grid-grafen bleef Dijkstra's algoritme sneller vanwege de grotere diameter van deze grafen, wat meer iteraties vereist voor NEURO-MAPP. Echter, voor hogere-dimensionale grids (bijv. 5D) toonde NEURO-MAPP een runtime-voordeel van ~20%.
- Real-World Toepassingen: In 3D luchtvaartnavigatie (Manhattan stedelijke omgeving) loste NEURO-MAPP het probleem op in 6,1 ms vergeleken met 6,8 ms voor Dijkstra's. Daarentegen was NEURO-MAPP voor wegnetwerknavigatie (Duitse districten) momenteel langzamer (met een orde van grootte) vanwege de specifieke topologie en omvang van de geteste netwerken, hoewel de auteurs projecteren dat het Dijkstra's zal overtreffen bij grotere schalen.
- Proteïne Interactie Netwerken: Ondanks langere runtimes op huidige netwerkgroottes, vertoonde NEURO-MAPP gunstige trends voor grotere netwerken met vergelijkbare topologieën.
Energie-efficiëntie:
- Over alle geteste grafentypes heen verbruikte NEURO-MAPP aanzienlijk minder energie per kortste-pad-query dan de CPU-implementatie.
- De SpiNNaker 2 chip verbruikte minder dan 500 mW tijdens uitvoering, vergeleken met ongeveer 4 W voor de CPU. Zelfs in gevallen waar NEURO-MAPP een langere runtime had, resulteerde het lagere vermogensverbruik in een lager totaal energieverbruik (bijv. 2,4 mJ vs. 25,5 mJ voor de luchtvaartnavigatie-taak).
Integratie met Isomap:
- De auteurs hebben NEURO-MAPP geïntegreerd in het Isomap dimensionaliteitsreductiekader om de all-pairs shortest path (APSP) matrix te berekenen. NEURO-MAPP demonstreerde superieure prestaties voor grotere datasets en een hoger aantal nearest neighbors ( $k$ ), wat het nut ervan als component in grotere algoritmische pipelines valideert.

Betekenis en Claims
Het artikel claimt dat NEURO-MAPP het potentieel van neuromorfische hardware met ijle, spike-gebaseerde communicatie demonstreert als een schaalbaar en energie-efficiënt platform voor graafonderzoek. De auteurs benadrukken dat hoewel het vergelijken van een single-core sequentieel algoritme met een massaal parallel systeem onrechtvaardig kan lijken, de metriek van belang de totale runtime en energie is die nodig is om een taak te voltooien.

Kernclaims zijn onder meer:

Energie-efficiëntie: Neuromorfische hardware kan kortste-pad-problemen oplossen met aanzienlijk lager energieverbruik dan conventionele CPU's, zelfs wanneer het parallelle algoritme nog niet de snelste is in absolute runtime voor alle grafengroottes.
Schaalbaarheid: Het algoritme schaalt gunstig voor grafenfamilies met lage diameters (random, small-world, hoog-dimensionale grids), wat suggereert dat multi-chip neuromorfische systemen problemen kunnen oplossen die momenteel onuitvoerbaar zijn voor energie-beperkte toepassingen.
Hardware Agnosticisme: Hoewel geïmplementeerd op SpiNNaker 2, merken de auteurs op dat het algoritme toepasbaar is op elk systeem met voldoende onafhankelijke parallelle eenheden, lokaal geheugen en low-latency communicatie, inclusief andere neuromorfische platforms zoals Loihi 2 of Graphcore IPU's.

De auteurs blijven bescheiden over huidige beperkingen en erkennen dat voor specifieke grafentypes (zoals 2D wegennetwerken) en huidige single-chip beperkingen, Dijkstra's algoritme sneller blijft. Ze stellen echter dat de energievoordelen en de logaritmische schaalbaarheidstrends wijzen op een duidelijk pad naar superieure prestaties op grotere, multi-chip neuromorfische systemen.