A Time-Domain Wavefront Computing Accelerator With a 32 × 32 Reconfigurable PE Array Chengshuo Y u

Abstract

This work presents a hardware accelerator realizing true time-domain wavefront computing in a massive parallel two- dimensional (2-D) processing element (PE) array. The proposed 2-D time-domain PE array is designed for multiple applications based on its scalable and reconfigurable architecture. The short- est path problem (a classical problem in graph theory) is one of the critical problems to solve using the proposed accelerator. Unlike the A ∗ search algorithm, a heuristic method widely used in shortest path searching problems, the proposed accelerator requires only the propagation of rising-edge signals through the PE array without calculating or estimating the distances from the start to the goal. Hence, a single execution of the proposed time-domain wavefront computing provides all the optimal paths from a start point to an arbitrary goal. Besides the King’s graph model used for solving the shortest path searching, the PE array is reconfigured to a simpler lattice graph model and solves other problems, such as maze solving we used in this article as a benchmark. In addition, we used the proposed accelerator to demonstrate a scientific simulation. The propagation of circular or planar wavefronts was simulated using single or multiple start points using King’s graph configuration. A 1 × 1m m 2 test chip with a 32 × 32 reconfigurable time-domain PE array is fabricated using a 65-nm process. For a 2-D map with 32 × 32 vertices, the proposed PE array consumes 776 pJ per task and a