C-MAP: Improving the Effectiveness of Mapping Method for CGRA by Reducing NoC Congestion

Abstract

The Coarse-Grained Reconfigurable Architecture (CGRA) is considered as one of the most potential candidates for big data applications, which provides significant throughput improvement and high energy efficiency. Unlike the dynamic issue superscalar method in conventional processors, the CGRA architecture uses the static placement dynamic issue (SPDI) execution method in which the compiler decides how to map the instructions onto the distributed processing elements (PEs) and the PEs executes one instruction when the required data is ready. Since the dataflow of the program is determined in the logical view, an improper mapping of instructions may leads to more network congestion and hurts the performance. Furthermore, the exploration for most optimized mapping in CGRA is proved to a NPC problem and can hardly be achieved in limited time. In this paper, we propose a novel mapping algorithm named Congestion-MAP (C-MAP). C-Map improves the effectiveness of CGRA mapping in the perspective of reducing network congestion and enhancing the continuity of the data-flow. Furthermore, C-Map also accelerates the mapping optimization for CGRA by using network analysis method, which supports the fast comparison of mapping plan and parallel exploration. Additionally, with C-Map, we also analyze the impact of several key considerations in CGRA instruction mapping, such as NoC workload reduction and workload balance. The experiment result shows that C-Map improves the performance by 2.2× as a geometric mean.