A time-domain wavefront computing accelerator with a 32 × 32 reconfigurable PE array

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 shortest 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 × 1 mm2 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 achieves 1.6 G edges/second search rate using 1.2-/1.0-V core supply voltages.