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 metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/hal-01466669
Contributor : Hal Ifip <>
Submitted on : Monday, February 13, 2017 - 4:38:29 PM
Last modification on : Friday, December 1, 2017 - 1:09:40 AM
Long-term archiving on : Sunday, May 14, 2017 - 2:50:16 PM

File

978-3-642-38853-8_14_Chapter.p...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

158

Files downloads

100