💻 computer science

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

This paper introduces NEURO-MAPP, a distributed shortest path algorithm implemented on SpiNNaker 2 neuromorphic hardware that demonstrates superior scalability and energy efficiency compared to traditional CPU-based Dijkstra's algorithm for various graph types.

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

Published 2026-06-30

📖 5 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: Finding the Fastest Route in a Crowd

Imagine you are in a massive, crowded city and you need to find the shortest path from your house to a friend's house. You have two ways to do this:

The "Super-Planner" (The CPU): You hire one incredibly smart, fast-talking person (a traditional computer processor). They sit at a desk, look at a giant map, and methodically check every possible route one by one, keeping a running list of the best options. They are very good, but they can only do one thing at a time.
The "Hive Mind" (The Neuromorphic Chip): Instead of one person, you hire 152 tiny, low-energy workers (the cores of a SpiNNaker 2 chip). You give each worker a small neighborhood of the city. Instead of talking to a central boss, they just shout to their immediate neighbors, "Hey, I found a shortcut!" If a neighbor hears a better route, they shout it to their neighbors. Everyone works at the same time, passing messages like a game of "telephone" but with math.

This paper introduces a new way to play this "telephone" game, called NEURO-MAPP. The researchers wanted to see if this "Hive Mind" approach could find the shortest path faster and use less energy than the "Super-Planner."

How NEURO-MAPP Works: The "Add and Min" Game

In the traditional "Super-Planner" method (Dijkstra's algorithm), the computer has to constantly stop, organize its list, and pick the best option. It's like a librarian who has to walk to every single shelf to find the right book before moving to the next one.

NEURO-MAPP changes the rules to fit the "Hive Mind" hardware:

The Add: When a worker finds a path, they add the "cost" (distance) of the road they just walked to their current total.
The Min: When a worker receives a message from a neighbor saying, "I can get there in 10 steps," they compare it to what they already know. If 10 is better than their current best, they update their number and shout it to their neighbors.

Because every worker does this simultaneously, the "best path" ripples through the entire city at once, without anyone needing to stop and organize a master list.

The Race: Who Wins?

The researchers tested this on a single chip (SpiNNaker 2) against a modern computer processor (CPU). They ran the race on four different types of "cities":

Random Cities: Where roads connect randomly.
- Result: For small cities, the Super-Planner was faster. But as the city got huge (over 30,000 intersections), the Hive Mind took the lead, finishing about 25% faster.
Small-World Cities: Like social networks or power grids, where most neighbors are close, but a few "express lanes" connect distant parts.
- Result: The Hive Mind was much faster for large versions of these cities.
Grid Cities: Like a perfect city with straight streets (2D or 3D grids).
- Result: In simple 3D grids, the Super-Planner was still slightly faster. However, in complex 5D grids (which represent very complicated data), the Hive Mind became the winner.
Real-World Cities:
- Roads: On actual German road maps, the Super-Planner was currently faster because the maps weren't big enough yet to show the Hive Mind's full power.
- Drones in a City: When mapping a 3D urban environment for drones (avoiding buildings), the Hive Mind was significantly faster and used 10 times less energy.
- Protein Networks: In biological maps of how proteins interact, the Hive Mind used much less energy, even if it took a little longer to finish the job.

The Energy Factor: The Battery Test

The most exciting finding wasn't just speed; it was energy.

The "Super-Planner" (CPU) is like a high-performance sports car: it goes fast, but it guzzles gas (electricity).
The "Hive Mind" (SpiNNaker 2) is like a fleet of electric scooters: individually they might seem slower, but because there are so many of them working together efficiently, the whole group uses a tiny fraction of the energy.

In almost every test, the Hive Mind used less energy per query than the CPU, even when the CPU finished the task slightly faster.

Why This Matters (According to the Paper)

The paper claims that this "Hive Mind" approach is a scalable solution.

Scalability: If you need to solve a problem for a city the size of a whole country, you can just add more chips (more workers) to the network. The system grows naturally.
Versatility: The researchers showed this works not just for driving directions, but also for:
- Planning drone flights through skyscrapers.
- Analyzing how proteins interact in the human body.
- Simplifying complex data (like turning a 10-dimensional shape into a 3D map) using a method called Isomap.

The Bottom Line

The paper argues that for massive, complex problems, the old way of thinking (one brain doing everything) is hitting a wall. The new way (many tiny brains talking to each other locally) is the future. It's not just about being faster; it's about being able to solve huge problems without burning through all the world's electricity.

Note: The authors emphasize that while their current chip (SpiNNaker 2) is specific, the idea of this algorithm could work on any system that has many independent processors that can talk to each other quickly, such as other specialized computer chips designed for brain-like computing.

Technical Summary: Road to Scalability for Efficient Graph Search on Massively Parallel Neuromorphic Hardware

Problem Statement
The computation of shortest paths in weighted graphs is a fundamental problem with critical applications in route planning, network routing, robotic action planning, and nonlinear dimensionality reduction (e.g., Isomap). While established sequential algorithms like Dijkstra's algorithm are effective on conventional hardware, they face scalability and energy efficiency challenges when applied to large-scale graphs or multi-user environments. Existing parallel approaches for GPUs and CPUs often rely on global coordination mechanisms that are costly in distributed or event-driven architectures. Neuromorphic hardware, characterized by co-localized computation and memory and event-based communication, offers a potential solution but requires algorithms that minimize global synchronization to leverage its inherent strengths.

Methodology: NEURO-MAPP
The authors introduce NEURO-MAPP (Neuromorphic-based Min-Add Parallel Propagation), a distributed shortest-path algorithm designed specifically for neuromorphic systems. The core concept involves embedding a weighted graph into a computational graph where:

Local Operations: Vertices perform local minimization over incoming distance signals to select the smallest candidate distance.
Edge Operations: Edges propagate distance updates by adding their associated weights to the incoming signal.
Dynamics: Shortest paths emerge through purely local, parallel update dynamics without requiring global coordination.

The algorithm was implemented on the SpiNNaker 2 platform, a massively parallel neuromorphic system featuring 152 ARM cores per chip, each with dedicated SRAM and connected via a low-latency network-on-chip (NoC). Key implementation strategies included:

Vertex Partitioning: To address load imbalances caused by skewed degree distributions (e.g., "hubs" in protein networks), the authors developed a vertex-degree-aware partitioning strategy. This assigns vertices to cores to minimize cumulative degree per core, preventing bottlenecks. For other graph types, randomized or bandwidth-minimizing assignments were used.
Message Passing Optimization: Two methods for encoding distance updates were compared. A "predecessor-based" approach, which stores outgoing edges directly on the source core and performs constant-time lookups, was found to significantly outperform the default "successor-based" approach (which requires binary search on incoming edges) for sparse and high-connectivity graphs, reducing search time by up to a factor of 10.
Dynamic Iteration Scheduling: To mitigate idle time caused by variable workloads across cores, a lightweight global coordinator was implemented. Cores signal completion to a scheduler, which triggers the next iteration only when all cores are ready, ensuring synchronization without fixed, wasteful time steps.

Key Results
The performance of NEURO-MAPP on a single SpiNNaker 2 chip was evaluated against Dijkstra's algorithm on a modern CPU (M1 Pro) across synthetic and real-world graph types:

Scalability and Runtime:
- Random and Small-World Graphs: NEURO-MAPP demonstrated superior scaling. While Dijkstra's algorithm performed better on small graphs, NEURO-MAPP's runtime grew logarithmically with graph size, outperforming Dijkstra's for graphs exceeding ~30,000–38,000 vertices.
- Grid Graphs: For 3D grid graphs, Dijkstra's algorithm remained faster due to the larger diameter of these graphs requiring more iterations for NEURO-MAPP. However, for higher-dimensional grids (e.g., 5D), NEURO-MAPP showed a ~20% runtime advantage.
- Real-World Applications: In 3D aerial navigation (Manhattan urban environment), NEURO-MAPP solved the problem in 6.1 ms compared to Dijkstra's 6.8 ms. Conversely, for road network navigation (German districts), NEURO-MAPP was currently slower (by an order of magnitude) due to the specific topology and size of the tested networks, though the authors project it would surpass Dijkstra's at larger scales.
- Protein Interaction Networks: Despite longer runtimes on current network sizes, NEURO-MAPP showed favorable trends for larger networks with similar topologies.
Energy Efficiency:
- Across all tested graph types, NEURO-MAPP consumed significantly less energy per shortest-path query than the CPU implementation.
- The SpiNNaker 2 chip consumed less than 500 mW during execution, compared to approximately 4 W for the CPU. Even in cases where NEURO-MAPP had a longer runtime, the lower power draw resulted in lower total energy consumption (e.g., 2.4 mJ vs. 25.5 mJ for the aerial navigation task).
Integration with Isomap:
- The authors integrated NEURO-MAPP into the Isomap dimensionality reduction framework to compute the all-pairs shortest path (APSP) matrix. NEURO-MAPP demonstrated superior performance for larger datasets and higher numbers of nearest neighbors ( $k$ ), validating its utility as a component in larger algorithmic pipelines.

Significance and Claims
The paper claims that NEURO-MAPP demonstrates the potential of neuromorphic hardware featuring sparse, spike-based communication as a scalable and energy-efficient platform for graph search. The authors emphasize that while comparing a single-core sequential algorithm to a massively parallel system might seem unfair, the metric of interest is the total runtime and energy required to complete a task.

Key claims include:

Energy Efficiency: Neuromorphic hardware can solve shortest-path problems with significantly lower energy consumption than conventional CPUs, even when the parallel algorithm is not yet the fastest in absolute runtime for all graph sizes.
Scalability: The algorithm scales favorably for graph families with low diameters (random, small-world, high-dimensional grids), suggesting that multi-chip neuromorphic systems could solve problems currently intractable for energy-constrained applications.
Hardware Agnosticism: While implemented on SpiNNaker 2, the authors note that the algorithm is applicable to any system with sufficient independent parallel units, local memory, and low-latency communication, including other neuromorphic platforms like Loihi 2 or Graphcore IPUs.

The authors remain modest regarding current limitations, acknowledging that for specific graph types (like 2D road networks) and current single-chip constraints, Dijkstra's algorithm remains faster. However, they posit that the energy advantages and logarithmic scaling trends indicate a clear path toward superior performance on larger, multi-chip neuromorphic systems.