Abstract
Coarse-grained Reconfigurable Architecture (CGRA) is a competitive accelerator architecture for computation-intensive loop kernels. Spatial CGRA is a typical CGRA that performs all the operations spatially to reduce reconfiguration costs within a single iteration, demanding high data parallelism. To achieve this goal, one of the main challenges is the loop-carried dependency between memory accesses. Many existing CGRA compilers struggle to precisely analyze the dependency distance, especially when accesses involve complex address patterns. Consequently, these compilers often default to setting the distance to one, based on a worst-case assumption, leading to degraded performance. However, we observe that a precise distance can improve performance significantly, raising the requirement for an efficient distance calculation approach. Another challenge is the performance constraints of single-bank memory, which necessitate the designer partitioning the original data into a multi-bank memory. However, we observe that the mapping result can cause the inter-iteration conflict, thereby invalidating the memory partition scheme. Therefore, an efficient post-mapping conflict detection is required. In this paper, we develop a constraint satisfaction problem (CSP)-based approach for calculating dependency distance and detecting conflicts, which determines the maximum available dependency distance and identifies conflicts within both intra- and inter-iterations. Besides, we formulate access scheduling as a graph coloring problem, which can minimize conflicts and improve performance. Overall, we develop a comprehensive end-to-end framework with architectural and compiler support for efficient data parallelism on spatial CGRA. We conduct extensive experiments to systematically evaluate the impact of different approaches on performance and compilation. Evaluation results show that our architecture can achieve 13.16× and 1.19× (up to 1.68×) average performance improvements compared to a RISC-V CPU and a state-of-the-art CGRA SoC, respectively. Besides, our architecture has 7.38× and 1.18× (up to 1.65×) average energy efficiency gains compared to these two architectures.
Funding Information
  • National Natural Science Foundation of China (62174035)