DISC: Exploiting Data Parallelism of Non-Stencil Computations on CGRAs via Dynamic Iteration Scheduling

Memory partitioning is commonly used to enhance data parallelism of Coarse-grain reconfigurable arrays (CGRAs), typically targeting stencil computation with regular memory access patterns. However, many important workloads, such as linear algebra and signal processing, include non-stencil computation with irregular memory access patterns where memory partitioning is not feasible, leading to memory access conflicts and poor data parallelism. In this paper, we propose a Dynamic Iteration Scheduling CGRA (DISC) that can dynamically exploit data parallelism from non-stencil computations. Via dynamic scheduling on loop iterations, DISC can select conflict-free iterations from an iteration buffer for parallel data access, while holding data dependence. To further enhance the ability to find conflict-free iterations, dynamic data reuse is also introduced to reduce the number of memory references. The experimental results show that DISC can achieve 1.41× performance and 2.75× energy efficiency while consuming much less area and power overhead, as compared to dynamic-scheduling CGRA which supports dynamic operator scheduling.