Loop Subgraph-Level Greedy Mapping Algorithm for Grid Coarse-Grained Reconfigurable Array  

作　　者：Naijin Chen Fei Cheng Chenghao Han Jianhui Jiang Xiaoqing Wen 

机构地区：[1]School of Computer and Information Science,Anhui Polytechnic University,Wuhu 241000,China [2]School of Software Engineering,Tongji University,Shanghai 201804,China [3]Department of Computer Science and Networks,Kyushu Institute of Technology,Fukuoka 820-8502,Japan

出　　处：《Tsinghua Science and Technology》2023年第2期330-343,共14页清华大学学报（自然科学版（英文版）

基　　金：This research was supported by the Natural Science Foundation of Anhui Province(No.1808085MF203);the Natural Science Foundation of China(Nos.61972438 and 61432017).

摘　　要：To solve the problem of grid coarse-grained reconfigurable array task mapping under multiple constraints,we propose a Loop Subgraph-Level Greedy Mapping(LSLGM)algorithm using parallelism and processing element fragmentation.Under the constraint of a reconfigurable array,the LSLGM algorithm schedules node from a ready queue to the current reconfigurable cell array block.After mapping a node,its successor’s indegree value will be dynamically updated.If its successor’s indegree is zero,it will be directly scheduled to the ready queue;otherwise,the predecessor must be dynamically checked.If the predecessor cannot be mapped,it will be scheduled to a blocking queue.To dynamically adjust the ready node scheduling order,the scheduling function is constructed by exploiting factors,such as node number,node level,and node dependency.Compared with the loop subgraph-level mapping algorithm,experimental results show that the total cycles of the LSLGM algorithm decreases by an average of 33.0%(PEA44)and 33.9%(PEA_(7×7)).Compared with the epimorphism map algorithm,the total cycles of the LSLGM algorithm decrease by an average of 38.1%(PEA_(4×4))and 39.0%(PEA_(7×7)).The feasibility of LSLGM is verified.

关 键 词：Grid Coarse-Grained Reconfigurable Array(GCGRA) mapping loop subgraph scheduling 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]