A Scalable Mapping Method for Elastic CGRAs

There is a growing expectation for accelerating high performance computing (HPC) applications using Coarse-Grained Reconfigurable Arrays (CGRAs). A large processing element (PE) array is necessary in such a scenario. When executing an application on CGRAs, instructions in the application kernel are mapped onto the PEs. The mapping time increases exponentially with the number of PEs and the instructions. Elastic CGRA is a type of CGRA where PEs can exchange data with each other asynchronously using a handshake protocol. Thanks to the scheduling of instructions performed by the hardware, Elastic CGRA possibly improves PE utilization compared to traditional CGRAs. In addition, it alleviates the complexity of the mapping problem since there is no need for explicit timeslot allocation when mapping time. However, given a large PE array suitable for HPC platforms, Elastic CGRA still suffers from a long mapping time. In order to accommodate as many application kernels into the PE array as possible within practical time, we propose a scalable mapping method exploiting data-level parallelism and thread-level parallelism. The proposed method divides the mapping process into two phases. In the first phase, the target application kernel is mapped in a conventional manner while changing the available PE array size, and then each mapping result is stored in a mapping database. The next phase replicates the mapping in the database and relocates them to fill the whole PE array. Instead of mapping pre-unrolled kernels, the proposed method efficiently prunes search space at the slight expense of optimality. The evaluation results demonstrate that the conventional approach can treat up to a 7x7 PE array within a practical time, whereas the proposed method extends the available array size to 80x80.