HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Hardware and Software Implementations of Prim’s Algorithm for Efficient Minimum Spanning Tree Computation

Abstract : Minimum spanning tree (MST) problems play an important role in many networking applications, such as routing and network planning. In many cases, such as wireless ad-hoc networks, this requires efficient high-performance and low-power implementations that can run at regular intervals in real time on embedded platforms. In this paper, we study custom software and hardware realizations of one common algorithm for MST computations, Prim’s algorithm. We specifically investigate a performance-optimized realization of this algorithm on reconfigurable hardware, which is increasingly present in such platforms.Prim’s algorithm is based on graph traversals, which are inherently hard to parallelize. We study two algorithmic variants and compare their performance against implementations on desktop-class and embedded CPUs. Results show that the raw execution time of an optimized implementation of Prim’s algorithm on a Spartan-class Xilinx FPGA running at 24 MHz and utilizing less than 2.5% of its logic resources is 20% faster than an embedded ARM9 processor. When scaled to moderate clock frequencies of 150 and 250 MHz in more advanced FPGA technology, speedups of 7x and 12x are possible (at 56% and 94% of the ARM9 clock frequency, respectively).
Document type :
Conference papers
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download

Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Monday, February 13, 2017 - 4:38:29 PM
Last modification on : Thursday, March 5, 2020 - 5:40:30 PM
Long-term archiving on: : Sunday, May 14, 2017 - 2:50:16 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Artur Mariano, Dongwook Lee, Andreas Gerstlauer, Derek Chiou. Hardware and Software Implementations of Prim’s Algorithm for Efficient Minimum Spanning Tree Computation. 4th International Embedded Systems Symposium (IESS), Jun 2013, Paderborn, Germany. pp.151-158, ⟨10.1007/978-3-642-38853-8_14⟩. ⟨hal-01466669⟩



Record views


Files downloads