Accelerating graph algorithms with priority queue processor
Graphs are a pervasive data structure in computer science, and algorithms working with them are fundamental to the field. Of the various graph algorithms, techniques for searching a graph are the heart of graph algorithms. Many graph algorithms are organized as simple elaborations of basic graph se...
Saved in:
Main Authors: | , , , |
---|---|
Format: | Article |
Language: | English |
Published: |
School of Postgraduate Studies, UTM
2006
|
Subjects: | |
Online Access: | http://eprints.utm.my/id/eprint/1689/1/sh-nasir06_Accelerating_graph_algorithm.pdf http://eprints.utm.my/id/eprint/1689/ |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
id |
my.utm.1689 |
---|---|
record_format |
eprints |
spelling |
my.utm.16892012-04-16T03:30:51Z http://eprints.utm.my/id/eprint/1689/ Accelerating graph algorithms with priority queue processor Heng Sun, Ch'ng Eik Wee, Chew Shaikh-Husin, Nasir Hani, Mohamed Khalil TK Electrical engineering. Electronics Nuclear engineering Graphs are a pervasive data structure in computer science, and algorithms working with them are fundamental to the field. Of the various graph algorithms, techniques for searching a graph are the heart of graph algorithms. Many graph algorithms are organized as simple elaborations of basic graph searching algorithms. For the searching of a graph, Priority Queue is used to maintain the tentative search result and choice of priority queue implementation would significantly affect the run-time and memory consumption of a graph algorithm. In this work, we demonstrate how to accelerate graph algorithms using priority queue processor. DijkstraÂ’s algorithm is chosen as the target implementation, as many state-of-the-art graph algorithms use DijkstraÂ’s algorithm at the heart of their computational engine. Assuming embedded hardware-software codesign, results show that our priority queue processor performs better than software implementation, and the run-time complexity of DijkstraÂ’s algorithm is reduced from O(n lg n) in software implementation to O(n) with our priority queue processor. School of Postgraduate Studies, UTM 2006-07-26 Article NonPeerReviewed application/pdf en http://eprints.utm.my/id/eprint/1689/1/sh-nasir06_Accelerating_graph_algorithm.pdf Heng Sun, Ch'ng and Eik Wee, Chew and Shaikh-Husin, Nasir and Hani, Mohamed Khalil (2006) Accelerating graph algorithms with priority queue processor. Regional Postgraduate Conference on Engineering and Science . pp. 257-262. |
institution |
Universiti Teknologi Malaysia |
building |
UTM Library |
collection |
Institutional Repository |
continent |
Asia |
country |
Malaysia |
content_provider |
Universiti Teknologi Malaysia |
content_source |
UTM Institutional Repository |
url_provider |
http://eprints.utm.my/ |
language |
English |
topic |
TK Electrical engineering. Electronics Nuclear engineering |
spellingShingle |
TK Electrical engineering. Electronics Nuclear engineering Heng Sun, Ch'ng Eik Wee, Chew Shaikh-Husin, Nasir Hani, Mohamed Khalil Accelerating graph algorithms with priority queue processor |
description |
Graphs are a pervasive data structure in computer science, and algorithms working with them are fundamental to the
field. Of the various graph algorithms, techniques for searching a graph are the heart of graph algorithms. Many graph algorithms are organized as simple elaborations of basic graph searching algorithms. For the searching of a graph, Priority Queue is used to maintain the tentative search result and choice of priority queue implementation would significantly affect the run-time and memory consumption of a graph algorithm. In this work, we demonstrate how to accelerate graph algorithms using priority queue processor. DijkstraÂ’s algorithm is chosen as the target implementation, as many state-of-the-art graph algorithms use DijkstraÂ’s algorithm at the heart of their computational engine. Assuming embedded hardware-software codesign, results show that our priority queue processor performs better than software implementation, and the run-time complexity of DijkstraÂ’s algorithm is reduced from O(n lg n) in software implementation to O(n) with our priority queue processor. |
format |
Article |
author |
Heng Sun, Ch'ng Eik Wee, Chew Shaikh-Husin, Nasir Hani, Mohamed Khalil |
author_facet |
Heng Sun, Ch'ng Eik Wee, Chew Shaikh-Husin, Nasir Hani, Mohamed Khalil |
author_sort |
Heng Sun, Ch'ng |
title |
Accelerating graph algorithms with priority queue processor |
title_short |
Accelerating graph algorithms with priority queue processor |
title_full |
Accelerating graph algorithms with priority queue processor |
title_fullStr |
Accelerating graph algorithms with priority queue processor |
title_full_unstemmed |
Accelerating graph algorithms with priority queue processor |
title_sort |
accelerating graph algorithms with priority queue processor |
publisher |
School of Postgraduate Studies, UTM |
publishDate |
2006 |
url |
http://eprints.utm.my/id/eprint/1689/1/sh-nasir06_Accelerating_graph_algorithm.pdf http://eprints.utm.my/id/eprint/1689/ |
_version_ |
1643643392051118080 |
score |
13.160551 |