SubMap: A Partial Mapping Strategy for CGRA Based on sub-CGRA Exploration

Coarse-grained reconfigurable array (CGRA) is a quality hardware for compute-intensive loop kernels, with its excellent balance of performance, energy efficiency, and reconfigurability. However, the efficiency of CGRA depends heavily on how the compiler maps the data flow graph (DFG) extracted from application kernels onto the target architecture. Most existing CGRA compilers encounter the challenge of long compilation times due to excessive exploration space. To reduce the exploration space and compilation time, we propose SubMap, which adaptively explores a suitable sub-CGRA for different DFGs in a target CGRA and efficiently performs the mapping process. The experimental results show that SubMap greatly reduces the compilation time compared to the latest methods while maintaining the mapping quality. On HyCube <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$4\times 4$ </tex-math></inline-formula>, SubMap has an average performance improvement of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$9.47 \times $ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$11.67 \times $ </tex-math></inline-formula>, respectively, compared with Morpher (Pathfinder) and Morpher (SA). As the scale of the target CGRA increases, the performance improvement of SubMap becomes more pronounced.