Mr_Kru: Accelerator of Kruskal’s Algorithm for Finding Root Node in Parallel
Junyong Deng, Baoxiang Zhang, Xiaoliang Fu, Xiaoyan Xie, Jingwen Deng, Zekun Ye · 2022 7th International Conference on Integrated Circuits and Microsystems (ICICM) · 2022
Minimum Spanning Tree(MST) is widely used in VLSI design, network routing, human brain network analysis and other fields. Kruskal’s algorithm is one of the classical methods to find the minimum spanning tree. Aiming at the problem that the root node search time accounts for a high proportion of the Kruskal’s algorithm, according to the characteristics of real world graph data, this paper presents a hardware accelerator Mr-Kru for the Kruskal’s algorithm to find the root node in parallel based on the Coordinate(COO) compression format. In this paper, the prototype system is built on the Virtex UltraScale+VCU118 evaluation platform, and complete the hardware testing of Mr_Kru based on four different datasets. The experimental results show that the running time of parallel mode is 34.9%~41.6% lower than that of serial mode. The resource cost is 97.6% and 99.6% lower than that of the comparative literature. Vivado simulation power consumption is 2. 671W.