Research And Implementation Of Loop Scheduling And Mapping Algorithm On Coarse-grained Reconfigurable Architecture

Coarse-grained reconfigurable architecture(CGRA)has been widely studied and applied as a computing architecture with flexibility of general purpose processor and high efficiency of Application Specific Integrated Circuit.CGRA is designed to accelerate structures with computation-intensive loops and achieves good result.However,loop scheduling and mapping algorithm onto CGRA needs further research to improve the hardware resources utilization,flexibility and computing efficiency.This paper focuses on scheduling and mapping loops on CGRA.Loops can be divided into perfect loops and imperfect loops according to the code of different structures.For the issue of scheduling and mapping perfect loops,we propose a separated sub-DFG scheduling and mapping algorithm.The algorithm firstly adopts the method of loop unrolling or loop fusion to perfect loops to generate multiple separated sub-DFGs inside a DFG.Then the algorithm sorts sub-DFGs according to their numbers of operations,and sequentially schedules each sub-DFG.At last,we use a method combining the thought of backtracking and foreseeing to map these perfect loops.For the issue of scheduling and mapping imperfect loops,we propose a virtual configuration package combination technique.We redesign the model of configuration information by distinguishing common part and individual part for this technique.Moreover,we propose a complete flow of mapping perfect and imperfect loops.At last,we implement the proposed perfect loop and imperfect loop scheduling and mapping algorithm on GRVM compiler and perform the verification on GReP coarse-grained reconfigurable platform.As for the issue of scheduling and mapping perfect loops,the result shows that our method can schedule and map loop with optimal initiation interval and guarantee high utilization rate of reconfigurable hardware resources.As for the issue of scheduling and mapping imperfect loops,we compare our method with recent dual-pipelining mapping method in the literature.The result shows our method generates 24.2% more PEA utilization rate.Moreover,our method decreases 28.5% latency,61.4% configuration information amount and 61.7% times of reconfiguration.