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).
Type de document :
Communication dans un congrès
Gunar Schirner; Marcelo Götz; Achim Rettberg; Mauro C. Zanella; Franz J. Rammig. 4th International Embedded Systems Symposium (IESS), Jun 2013, Paderborn, Germany. Springer, IFIP Advances in Information and Communication Technology, AICT-403, pp.151-158, 2013, Embedded Systems: Design, Analysis and Verification. 〈10.1007/978-3-642-38853-8_14〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01466669
Contributeur : Hal Ifip <>
Soumis le : lundi 13 février 2017 - 16:38:29
Dernière modification le : vendredi 1 décembre 2017 - 01:09:40
Document(s) archivé(s) le : dimanche 14 mai 2017 - 14:50:16

Fichier

978-3-642-38853-8_14_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Artur Mariano, Dongwook Lee, Andreas Gerstlauer, Derek Chiou. Hardware and Software Implementations of Prim’s Algorithm for Efficient Minimum Spanning Tree Computation. Gunar Schirner; Marcelo Götz; Achim Rettberg; Mauro C. Zanella; Franz J. Rammig. 4th International Embedded Systems Symposium (IESS), Jun 2013, Paderborn, Germany. Springer, IFIP Advances in Information and Communication Technology, AICT-403, pp.151-158, 2013, Embedded Systems: Design, Analysis and Verification. 〈10.1007/978-3-642-38853-8_14〉. 〈hal-01466669〉

Partager

Métriques

Consultations de la notice

138

Téléchargements de fichiers

37