Loop Subgraph-Level Greedy Mapping Algorithm for Grid Coarse-Grained Reconfigurable Array
作者机构:School of Computer and Information ScienceAnhui Polytechnic UniversityWuhu 241000China School of Software EngineeringTongji UniversityShanghai 201804China Department of Computer Science and NetworksKyushu Institute of TechnologyFukuoka 820-8502Japan
出 版 物:《Tsinghua Science and Technology》 (清华大学学报(自然科学版(英文版))
年 卷 期:2023年第28卷第2期
页 面:330-343页
核心收录:
学科分类:0808[工学-电气工程] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术(可授工学、理学学位)] 081202[工学-计算机软件与理论]
基 金:This research was supported by the Natural Science Foundation of Anhui Province(No.1808085MF203) the Natural Science Foundation of China(Nos.61972438 and 61432017).
主 题:Grid Coarse-Grained Reconfigurable Array(GCGRA) mapping loop subgraph scheduling
摘 要: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.