Design and Implementation of SSSP Accelerator based-on Reconfigurable and Programmable Computing Array
Junyong Deng, Jingwen Deng, Xiaoyan Xie, Pan Zhang, Junjie Wang, Kai Zhou · 2023
Most of the existing researches only implement one SSSP algorithm, which cannot fit the diversity of applications, since different applications demand implementations with different efficiency and flexibility. The conflict between the requirements of applications and fixed design of accelerators are still one of the main problems currently faced. The reconfigurable array processor can well ease the above problem due to its property of accommodating both flexibility and efficiency. In this paper, we propose an accelerator based on APR-16, a reconfigurable and programmable computing array to realize the Dijkstra algorithm and the Bellman-Ford algorithm for SSSP, which can switch between the two algorithms when facing different graph data. To deal with the problem of graph data's poor locality, preserving node attributes in the frame buffer is proposed to reduce redundant operations in the computing process. To deal with the problem of an unbalanced load, a parallel mapping scheme for the Dijkstra algorithm and Bellman-Ford algorithm is proposed to reduce the impact of an unbalanced load. According to experimental results, we can improve Bellman- Ford's energy efficiency in comparison to the GPU platform by 22 times and the Dijkstra algorithm's energy efficiency by 15 times.