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

Yee Hin Chong, Peng Qu, Yuchen Li, Youhui Zhang · 2025

Read Pipelining Kruskal’s: A Neuromorphic Approach for Minimum Spanning Tree by Yee Hin Chong, Peng Qu, Yuchen Li, Youhui Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-10771.txt.

Introduction

The minimum spanning tree is a classic graph problem, and Yee Hin Chong and co-authors solve it on neuromorphic hardware — chips that compute with spikes, in parallel, at low power. Their design pipelines Kruskal's algorithm: while one stage sorts edges, another runs union-find checks, and the two stages proceed independently. A spiking routine they call union-sort underpins the sorting side.

On the large graphs of the DIMACS10 collection, their approach beat leading Prim-based neuromorphic methods by hundreds of times, with a median speedup above five hundred. Against serial versions of their own pipeline using other neuromorphic sorts, it also won in most scenarios. Dynamic synapse changes, a feature of the hardware, opened the design space. The authors present the pipeline as proof that event-driven chips suit data-heavy graph work.

Catalog record

CREATORYee Hin Chong, Peng Qu, Yuchen Li, Youhui Zhang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-10771

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Pipelining Kruskal’s: A Neuromorphic Approach for Minimum Spanning Tree Yee Hin Chong, Peng Qu, Yuchen Li, Youhui Zhang 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. I Introduction Neuromorphic computing leverages massive parallelism and event-driven computation, making it an effective paradigm for parallel acceleration, particularly in machine learning and graph learning on non-Von Neumann architectures [ 1 , 2 ] . The simplest design of a neuromorphic algorithm involves embedding the computational kernel directly into a static, non-modifiable spiking neural network (SNN), which is then deployed on neuromorphic hardware [ 3 , 4 ] . This method sacrifices flexibility in exchange for significant gains in energy-efficient execution [ 5 , 6 ] . The introduction of various learning mechanisms, such as synaptic plasticity [ 7 , 8 , 9 ] , has fostered the development of self-adaptive neuromorphic primitives. These strategies not only enhance biological plausibility but also significantly improve computational power. A noteworthy advancement in this field is structural plasticity, which involves the dynamic formation, modification, and elimination of synaptic connections, or in short, synaptic rewiring [ 10 ] . This mechanism creates new opportunities for designing neuromorphic algorithms. With structural plasticity, the local connectivity of an SNN can be dynamically adjusted based on the algorithm’s needs [ 11 ] , similar to pointer manipulation in traditional computing. Such flexibility enables the creation of novel neuromorphic operators and algorithms [ 12 , 13 , 14 , 15 ] . However, existing analyses of computational complexity in neuromorphic algorithms [ 16 , 5 , 6 ] do not account for the overhead introduced by such learning rules. To address this, we propose a revision of the neuromorphic time complexity proposed in [ 16 ] , extending conventional analysis to include the costs associated with structural modifications. This updated framework offers a more accurate characterization of algorithmic performance, which will be further discussed in this section. Building on the concept of structural plasticity, we demonstrate how this learning rule can be used to design more efficient neuromorphic algorithms. We use the minimum spanning tree (MST) construction, specifically the kernel of single-linkage clustering [ 17 , 18 ] in machine learning, as a case study. By leveraging Kruskal’s algorithm [ 19 ] , we develop a union-find routine based on SNN primitives, and evaluate its performance compared to state-of-the-art approaches that use Prim’s algorithm [ 20 , 21 ] in the context of neuromorphic sorting and neuromorphic radix sorting. We explore how spike-driven computation in neuromorphic systems facilitates parallelization opportunities for pipelining Kruskal’s algorithm . This approach helps overcome the performance bottlenecks that arise from the sequential execution of sorting and union-find operations, which are typically independent. We take the initial steps in designing a pipelined version of Kruskal’s algorithm that utilizes neuromorphic primitives along with the principles of structural plasticity. Extensive experiments on the DIMACS10 dataset [ 22 ] show that the pipelined Kruskal’s outperforms the state-of-the-art Prim ’s-based methods with a median speedup of 540.76x. Moreover, the results reveal that, in most cases, pipelining results in significant performance improvements over the sequential approaches. We also examine scenarios when pipelining may face bottlenecks, potentially leading to a decline in performance compared to sequential execution, and propose methods to identify such cases, supported by concrete examples. The remainder of the paper is organized as follows: Section II-A discusses the revision of the complexity framework based on structural plasticity, and Section II-B presents implementations for both neuromorphic sorting and neuromorphic radix sorting. In Section III , we introduce the design of the union-find routine and the pipelined Kruskal’s algorithm, evaluating their operational costs with a summary in Table I . Section IV presents experimental results on the DIMACS10 dataset, highlighting the conditions under which the sequential approach outperforms the pipelined version. Finally, Section V examines the feasibility of implementing these algorithms on neuromorphic hardware. II Background II-A Neuromorphic Computing Complexity The evaluation process on neuromorphic algorithms begins with neuromorphic graph primitives [ 3 , 4 ] , which incorporate a graph of nodes and edges into an SNN using leaky integrate-and-fire (LIF) neurons and static synapses [ 23 ] . This configuration provides a Turing-complete mathematical model for assessing the performance of a neuromorphic algorithm [ 24 ] . Building on earlier research, [ 16 ] introduces a theoretical framework to define the computational complexity of these neuromorphic algorithms. In this model, neurons accumulate signals from incoming synapses until they reach a predefined threshold, denoted \upsilon_{i} . Once this threshold is reached, the neuron emits a spike, transmits signals through outgoing synapses, and resets its state to zero. Each neuron has a leak factor, \lambda_{i} , which indicates how quickly it returns to zero if it does not spike. Both \upsilon_{i} and \lambda_{i} are whole numbers. A synapse processes the incoming signals from the pre-synaptic neuron \mathrm{i} by multiplying them by its weight \omega_{i,j} , applies a delay \delta_{i,j} , and then delivers the signals to the post-synaptic neuron \mathrm{j} . The weights are integers, whereas the delays are non-negative numbers. Despite several variations, the general computing paradigm of a LIF neuron could be summarized as v_{i}=v_{i}/\lambda_{i}+w_{ij} , where v_{i} represents the signal accumulated in the membrane potential [ 2 ] , and the input does not decay. Figure 1 illustrates the symbolic notation for an SNN. The circles labeled \left\{\upsilon_{i},\lambda_{i}\right\} represent neurons, while the arrows \left<\omega_{i,j},\delta_{i,j}\right> represent the synapses that connect them. Each pair of neurons is linked by a single synapse, as dictated by the framework specifications. The complexity reflects the resources required to configure and execute the SNN, consistent with the general definition provided by [ 25 ] . Fig. 1 : Symbolic notation for a typical SNN Fig. 2 : SNN of NeuroSort The time complexity , denoted as T(n) , combines the setup time and the running time using the conventional big-O notation. The setup time refers to the duration required to configure neurons and synapses sequentially, which is proportional to the size of the SNN. In contrast, the run time is the period from when the inputs ( x ’s) are fed into the network until valid outputs ( y ’s) are produced. Space complexity , represented as S(n) , depends on the number of neurons and synapses within the SNN. Furthermore, [ 5 ] proposes the energy complexity , E(n) , to measure the total spike count used in the

Read the complete text