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