Hardware and Software Implementations of Prim’s Algorithm for Efficient Minimum Spanning Tree Computation - Embedded Systems: Design, Analysis and Verification Access content directly
Conference Papers Year : 2013

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).
Fichier principal
Vignette du fichier
978-3-642-38853-8_14_Chapter.pdf (337.45 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01466669 , version 1 (13-02-2017)

Licence

Attribution

Identifiers

Cite

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⟩
138 View
142 Download

Altmetric

Share

Gmail Facebook X LinkedIn More