| Presentation | 2014-06-12 Design of an FPGA-Based Accelerator for Shortest-Path Search over Large-Scale Graphs Yasuhiro TAKEI, Masanori HARIYAMA, Michitaka KAMEYAMA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Shortest-path search over large scale graphs plays an important role in various applications. However, shortest path algorithms such as the Dijkstra's algorithm include complex processings. It is difficult for accelerators such as GPUs to accelerate these algorithms. This paper presents the FPGA-based accelerator for the shortest-paths algorithm. In order to design the efficient architecture for large scale graphs, we consider about the task-parallelized scheduling and data structures on the memory. From the result of the evaluation, the proposed architecture is able to deal with graphs with about 800,000 nodes on the Altera StratixV. The proposed architecture is better performance per cycles than that of the Intel Core i7. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | FPGA / Shortest path ploblem / Dijkstra' argorithm / Hardware accelerator |
| Paper # | RECONF2014-15 |
| Date of Issue |
| Conference Information | |
| Committee | RECONF |
|---|---|
| Conference Date | 2014/6/4(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Reconfigurable Systems (RECONF) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Design of an FPGA-Based Accelerator for Shortest-Path Search over Large-Scale Graphs |
| Sub Title (in English) | |
| Keyword(1) | FPGA |
| Keyword(2) | Shortest path ploblem |
| Keyword(3) | Dijkstra' argorithm |
| Keyword(4) | Hardware accelerator |
| 1st Author's Name | Yasuhiro TAKEI |
| 1st Author's Affiliation | Graduate School of Information Sciences, Tohoku University() |
| 2nd Author's Name | Masanori HARIYAMA |
| 2nd Author's Affiliation | Graduate School of Information Sciences, Tohoku University |
| 3rd Author's Name | Michitaka KAMEYAMA |
| 3rd Author's Affiliation | Graduate School of Information Sciences, Tohoku University |
| Date | 2014-06-12 |
| Paper # | RECONF2014-15 |
| Volume (vol) | vol.114 |
| Number (no) | 75 |
| Page | pp.pp.- |
| #Pages | 5 |
| Date of Issue | |