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!
|
Summary: | 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. |
---|