Pipelining Kruskal's: A Neuromorphic Approach for Minimum Spanning Tree
Yee Hin Chong, Peng Qu, Yuchen Li, Youhui Zhang
神经形态计算以其事件驱动的计算和大规模并行性为特征,对于处理低功耗环境中的数据密集型任务特别有效,例如计算大规模图形的最小生成树(MST)。 动态突触修饰的引入为神经形态算法提供了新的设计机会。 在这一基础上,我们提出了一个基于SNN的工会排序例程和Kruskal用于MST计算的算法的管道版本。 我们的方法的事件驱动性质允许同时执行两个完全解耦的阶段:神经形态排序和联合查找。 与DIMACS10数据集中基于大规模图形的Prim方法相比,我们的方法表现出卓越的性能,实现了269.67x到1283.80x的加速,中位速度为540.76x。 我们进一步评估了Kruskal算法的两个串行变体的管道实现,这些变体依赖于神经形态排序和神经形态径向排序,在大多数场景中显示出显着的性能优势。
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 com...