Pipelining Kruskal's: A Neuromorphic Approach for Minimum Spanning Tree

Young-Sook Chong, Peng Qu, Yuchen Li, Youhui ZhangarXiv 2025 · DOI · arXiv

Abstract

Neuromorphic computing, characterized by its event-driven computation and massive parallelism, is particularly effective for handling data-intensive tasks in low-power environments, such as computing the minimum spanning tree (MST) for large-scale graphs. The introduction of dynamic synaptic modifications provides new design opportunities for neuromorphic algorithms. Building on this foundation, we propose an SNN-based union-sort routine and a pipelined version of Kruskal's algorithm for MST computation. The event-driven nature of our method allows for the concurrent execution of two completely decoupled stages: neuromorphic sorting and union-find. Our approach demonstrates superior performance compared to state-of-the-art Prim's-based methods on large-scale graphs from the DIMACS10 dataset, achieving speedups by 269.67x to 1283.80x, with a median speedup of 540.76x. We further evaluate the pipelined implementation against two serial variants of Kruskal's algorithm, which rely on neuromorphic sorting and neuromorphic radix sort, showing significant performance advantages in most scenarios.

Introduction

Neuromorphic computing utilizes Spiking Neural Networks (SNNs) to perform highly parallel, low-power, event-driven computation. However, mapping traditional graph algorithms to this hardware remains a significant challenge. Current neuromorphic MST algorithms typically rely on Prim's algorithm, which often fails to fully exploit the inherent parallelism of SNNs.

Kruskal's algorithm offers a compelling alternative but traditionally requires sequential execution: first sorting all edges by weight, then running a Union-Find routine to construct the tree while preventing cycles. This sequential dependency creates a performance bottleneck. Furthermore, standard theoretical models for neuromorphic complexity often overlook the overhead of "structural plasticity"—the ability to dynamically rewire synapses during runtime—making it difficult to accurately evaluate advanced algorithmic designs.

The Pipelined Neuromorphic Architecture

To address these challenges, we introduce a novel, pipelined version of Kruskal's algorithm (Pipe) that leverages structural plasticity to overlap event-driven sorting with cycle detection. Our approach is built on three main contributions:

  1. Revised Complexity Model: We updated the standard neuromorphic complexity framework to explicitly include the overhead of structural plasticity, accounting for the cost of briefly pausing the network to rewire synapses.
  2. Neuromorphic Union-Find: We implemented a disjoint-set data structure using SNN primitives. By treating synaptic rewiring as pointer manipulation, we successfully implemented union and find operations, including path compression.
  3. Event-Driven Pipelining: Instead of waiting for the SNN to finish sorting all edges, our algorithm pipelines the process. As soon as the sorting SNN emits a spike (indicating the next smallest edge), the edge is immediately passed to the Union-Find SNN via dynamically delayed synapses. This allows the sorting and cycle-checking stages to run concurrently.
The pipelined architecture showing the sorting kernel and union-find routine running concurrently.

Experimental Results

We evaluated our algorithms using 20 large-scale graphs from the DIMACS10 dataset, each containing approximately 1 million or more nonzero elements. The pipelined Kruskal's algorithm achieved massive speedups, ranging from 269.67x to 1283.80x (median 540.76x) compared to state-of-the-art neuromorphic Prim's implementations.

When compared against sequential neuromorphic Kruskal variants—Serial NeuroSort and Serial RadixSort—the Pipe implementation demonstrated superior performance on 14 out of 20 tested graphs.

Speedup comparison of Serial NeuroSort, Serial RadixSort, and the Pipelined (Pipe) approach across various DIMACS10 datasets.

In the instances where Pipe underperformed Serial RadixSort, the bottleneck was identified as the time required to naturally enumerate the MST's maximum edge weight via spiking. If a graph has a very large maximum MST edge weight, the pipeline must wait for that specific spike, whereas a highly optimized sequential radix sort on the entire edge list may finish faster.

Discussion and Future Work

Structural plasticity unlocks the ability to build complex, dynamic data structures in SNNs, moving beyond static neural weights to create adaptive algorithms. The asynchronous nature of SNNs is ideally suited for pipelining decoupled algorithmic stages, maximizing hardware utilization by processing spikes exactly as they arrive.

However, this approach relies heavily on hardware that supports dynamic synaptic modification (e.g., SpiNNaker or BrainScaleS-2). Additionally, modifying synapses requires temporary execution pauses to avoid race conditions, which remains a strict computational bottleneck. Future research will explore heuristics for dynamically choosing between pipelined and sequential execution based on a graph's specific edge weight distribution to further optimize performance.

Summary updated

Abstract

Neuromorphic computing, characterized by its event-driven computation and massive parallelism, is particularly effective for handling data-intensive tasks in low-power environments, such as computing the minimum spanning tree (MST) for large-scale graphs. The introduction of dynamic synaptic modifications provides new design opportunities for neuromorphic algorithms. Building on this foundation, we propose an SNN-based union-sort routine and a pipelined version of Kruskal's algorithm for MST computation. The event-driven nature of our method allows for the concurrent execution of two completely decoupled stages: neuromorphic sorting and union-find. Our approach demonstrates superior performance compared to state-of-the-art Prim 's-based methods on large-scale graphs from the DIMACS10 dataset, achieving speedups by 269.67x to 1283.80x, with a median speedup of 540.76x. We further evaluate the pipelined implementation against two serial variants of Kruskal's algorithm, which rely on neuromorphic sorting and neuromorphic radix sort, showing significant performance advantages in most scenarios.
BibTeX
@misc{chong2025pipelining,
  author = {Young-Sook Chong and Peng Qu and Yuchen Li and Youhui Zhang},
  title = {{Pipelining Kruskal's: A Neuromorphic Approach for Minimum Spanning Tree}},
  year = {2025},
  eprint = {2505.10771},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.10771},
  howpublished = {arXiv},
}
Figure