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...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
School of Postgraduate Studies, UTM
2006
|
| Subjects: | |
| Online Access: | http://eprints.utm.my/1689/1/sh-nasir06_Accelerating_graph_algorithm.pdf |
| _version_ | 1825909108768768000 |
|---|---|
| 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 |
| collection | ePrints |
| 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. |
| first_indexed | 2024-03-05T17:57:17Z |
| format | Article |
| id | utm.eprints-1689 |
| institution | Universiti Teknologi Malaysia - ePrints |
| language | English |
| last_indexed | 2024-03-05T17:57:17Z |
| publishDate | 2006 |
| publisher | School of Postgraduate Studies, UTM |
| record_format | dspace |
| spelling | utm.eprints-16892012-04-16T03:30:51Z http://eprints.utm.my/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/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. |
| 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 |
| title | 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_short | Accelerating graph algorithms with priority queue processor |
| title_sort | accelerating graph algorithms with priority queue processor |
| topic | TK Electrical engineering. Electronics Nuclear engineering |
| url | http://eprints.utm.my/1689/1/sh-nasir06_Accelerating_graph_algorithm.pdf |
| work_keys_str_mv | AT hengsunchng acceleratinggraphalgorithmswithpriorityqueueprocessor AT eikweechew acceleratinggraphalgorithmswithpriorityqueueprocessor AT shaikhhusinnasir acceleratinggraphalgorithmswithpriorityqueueprocessor AT hanimohamedkhalil acceleratinggraphalgorithmswithpriorityqueueprocessor |