PRISA: A Potential Region-based Intelligent Search Algorithm for Dataflow Graph Mapping in Spatial CGRAs

Coarse-grained Reconfigurable Architectures (CGRAs) offer energy efficiency and programmability, making them integral to modern high-performance computing. However, complicated compilation when mapping the Dataflow Graph (DFG) to CGRA components leads to significant time overhead, area inefficiency, and routing challenges, especially for large-scale applications today. In this article, a fast and accurate DFG mapping approach called PRISA is proposed to reduce the compilation delay and obtain mapping solutions with higher qualities in a more reasonable time. This approach analytically identifies the potential and weak regions in the space of mapping solutions to guide the search algorithm and prevent ineffective examinations. Moreover, using the potential solutions and a novel sparse matrix permutation technique, we introduced Selective Initial Solution (SIS) to further improve the performance of PRISA without needing long-time optimizations. As the computational requirements in the PRISA are performed analytically, there is no additional time overhead. We conducted extensive experiments on the benchmark graphs of CGRA-ME and VPR-8 toolkits and obtained outstanding results compared to integer linear programming, evolutionary, and graph traversal approaches in terms of compilation time and mapping communication cost. Our approach could map the DFGs of VPR-8 toolkit with 3.64 maximal FIFO size requirement and 53.5 ms time overhead, on average.