TY - GEN
T1 - Hash Distributed A∗on an FPGA
AU - Sakamoto, Ryuichi
AU - Ezaki, Yuriko
AU - Kondo, Masaaki
N1 - Funding Information:
The part of this work was supported by JST, CREST Grant Number JPMJCR18K1, Japan. The part of this work was supported by JST, PRESTO Grant Number JPMJPR19M3, Japan.
Publisher Copyright:
© 2022 ACM.
PY - 2022/6/9
Y1 - 2022/6/9
N2 - Shortest path problem is a problem of finding a path that minimizes the cost of connecting two nodes in a weighted graph. A∗algorithm for solving shortest path search has been applied in various fields such as path navigation systems, automatic robot planning and VLSI design. However, in recent years, the scale of graphs has become large. We need to solve the problem faster and with less power consumption. In this study, we propose a hardware accelerator for solving the shortest path problem using A∗algorithm based on HDA∗(Hash Distributed A∗) using FPGA. In evaluation we compare execution time and power consumption between CPU, GPU and FPGA. FPGA was able to solve Maze problem using the least amount of power. The energy efficiency of FPGA was up to 9 times higher than that of CPU.
AB - Shortest path problem is a problem of finding a path that minimizes the cost of connecting two nodes in a weighted graph. A∗algorithm for solving shortest path search has been applied in various fields such as path navigation systems, automatic robot planning and VLSI design. However, in recent years, the scale of graphs has become large. We need to solve the problem faster and with less power consumption. In this study, we propose a hardware accelerator for solving the shortest path problem using A∗algorithm based on HDA∗(Hash Distributed A∗) using FPGA. In evaluation we compare execution time and power consumption between CPU, GPU and FPGA. FPGA was able to solve Maze problem using the least amount of power. The energy efficiency of FPGA was up to 9 times higher than that of CPU.
KW - A
KW - FPGA
KW - HDA
KW - High level synthesis
KW - Shortest path problem
KW - Sorting network
UR - http://www.scopus.com/inward/record.url?scp=85132384707&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85132384707&partnerID=8YFLogxK
U2 - 10.1145/3535044.3535054
DO - 10.1145/3535044.3535054
M3 - Conference contribution
AN - SCOPUS:85132384707
T3 - ACM International Conference Proceeding Series
SP - 76
EP - 83
BT - Proceedings of the 12th International Symposium on Highly Efficient Accelerators and Reconfigurable Technologies, HEART 2022
PB - Association for Computing Machinery
T2 - 12th International Symposium on Highly Efficient Accelerators and Reconfigurable Technologies, HEART 2022
Y2 - 9 June 2022 through 10 June 2022
ER -
