Dependency-Aware Data Parallelism on Spatial CGRA via Constraint Satisfaction and Graph Coloring
- 10 December 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. PP (02780070) , 1
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.Keywords
Funding Information
- National Natural Science Foundation of China (62174035)
This publication has 32 references indexed in Scilit:
- PACE: A Scalable and Energy Efficient CGRA in a RISC-V SoC for Edge Computing Applications2024
- PresCount: Effective Register Allocation for Bank Conflict Reduction2024
- Pipeline Balancing for Integrated Mapping in High Performance Spatial Programmable Architecture2023
- DARIC: A Data Reuse-Friendly CGRA for Parallel Data Access via Elastic FIFOs2023
- Formulating Data-arrival Synchronizers in Integer Linear Programming for CGRA Mapping2021
- OpenCGRA: Democratizing Coarse-Grained Reconfigurable Arrays2021
- Graph Theory with Algorithms and its Applications2013
- Livermore Loops2011
- Graph Coloring for class scheduling2010
- Exploiting loop-level parallelism on coarse-grained reconfigurable architectures using modulo scheduling2003