Research On Task Mapping Based On Coarse-Grained Reconfigurable Architecture

As a new high-performance computing architecture,coarse-grained reconfigurable architecture(CGRA)has both advantages of general computing and specific computing.It has a good compromise in terms of programming flexibility and energy efficiency.The performance advantages of CGRA mainly rely on advanced compilers to map compute-intensive applications to abundant parallel computing resources,while the task mapping strategy in the compiler determines the execution performance of applications.Therefore,the research on task mapping technology has always been the hot topic in the field of reconfigurable computing and has attracted the attention of many scholars.With the continuous development of reconfigurable field,task mapping has many achievements,but the following problems still exist:(1)in the process of mapping,the insufficient parallel ability of the operators in subtasks after task partitioning;(2)the lack of considering data access conflict in loop mapping;(3)the poor overall performance of imperfect nested loop mapping.In view of the above issues,firstly,this thesis starts from the characteristics of CGRA's efficient parallel computing architecture,abstracts tasks into data flow graphs and considers the constraints of data dependence and hardware resources.Secondly,mainly from three aspects of the high parallelism degree of the multi-objective task partitioning,avoiding data access conflict in loop mapping and the improvment of overall mapping performance in imperfect nested loop,this thesis constructs the problem model and designs optimization algorithm.Ultimately,the task mapping performance is improved and the overall application execution time on CGRA is reduced.Specifically,its main innovations are as follows:1.In the process of mapping,to solve the problem that insufficient parallel processing ability of the operators in subtasks after task partitioning,a multi-objective optimization task partitioning algorithm based on parallelism maximization is proposed.The proposed algorithm uses a breadth-first search method to maximize the parallelism of operators in subtasks under the strategy of using the hardware resources reasonably and without increasing the communication overhead among subtasks.The simulation results show that the algorithm reduces the execution delay of each subtask,at the same time achieves multiple goals of reducing configuration overhead and communication overhead.2.Data access conflicts results in low mapping performance in CGRA loop mapping.To address this problem,a joint optimization model is proposed.For a CGRA with a multi-bank structure,the proposed model takes into account the problem of memory access conflicts in the the loop mapping,and also constructs routing overhead function to select routing mode.According to the joint optimization model,the corresponding algorithm is designed.The algorithm uses fine-grain memory partitioning to improve the parallelism of data access,and the path reuse strategy is introduced to optimize the routing resource.Experiments show that this method can effectively avoid the memory access conflicts and improve the performance of loop mapping.3.To address the problem of poor overall mapping performance of CGRA imperfect nested loop,an imperfect loop mapping optimization model combining operator level affine transformation with multi-pipelining is proposed.In this model,the operator level affine transformation is applied to preprocess the imperfect loop,and the multi pipeline method is used to pipeline the inner and outer iteration simultaneousiy.The designed algorithm uses the resource constraint and minimizes the overall execution delay to guide the search space,simplifying the difficulty of model solution.Experimental results show that the proposed model can effectively improve the overall mapping performance of imperfect nested loops.