Tsinghua Science and Technology  2021, Vol. 26 Issue (5): 724-735    doi: 10.26599/TST.2020.9010035
 Regular Articles
Efficient Scheduling Mapping Algorithm for Row Parallel Coarse-Grained Reconfigurable Architecture
Naijin Chen(),Zhen Wang*(),Ruixiang He(),Jianhui Jiang(),Fei Cheng(),Chenghao Han()
School of Computer and Information Science, Anhui Polytechnic University, Wuhu 241000, China
School of Computer Science and Technology, Shanghai University of Electric Power, Shanghai 200090, China
School of Software Engineering, Tongji University, Shanghai 201804, China

Abstract

Row Parallel Coarse-Grained Reconfigurable Architecture (RPCGRA) has the advantages of maximum parallelism and programmable flexibility. Designing an efficient algorithm to map the diverse applications onto RPCGRA is difficult due to a number of RPCGRA hardware constraints. To solve this problem, the nodes of the data flow graph must be partitioned and scheduled onto the RPCGRA. In this paper, we present a Depth-First Greedy Mapping (DFGM) algorithm that simultaneously considers the communication costs and the use times of the Reconfigurable Cell Array (RCA). Compared with level breadth mapping, the performance of DFGM is better. The percentage of maximum improvement in the use times of RCA is 33% and the percentage of maximum improvement in non-original input and output times is 64.4% (Given Discrete Cosine Transfor 8 (DCT8), and the area of reconfigurable processing unit is 56). Compared with level-based depth mapping, DFGM also obtains the lowest averages of use times of RCA, non-original input and output times, and the reconfigurable time.

Received: 30 July 2020      Published: 30 April 2021
Fund:  Natural Science Foundation of Anhui Province(1808085MF203);National Natural Science Foundation of China(61432017)
Corresponding Authors: Zhen Wang     E-mail: chennaijin@ict.ac.cn;wangzhenqq@hotmail.com;809031856@qq.com;jhjiang@tongji.edu.cn;957189105@qq.com;1048551181@qq.com
About author: Naijin Chen received the PhD degree in computer science and technology from Tongji University, Shanghai, China in 2013. He obtained postdoctoral certificate from Tianjin University, Tianjin, China in 2016. He is a member of China Computer Federation. He is currently a professor in Anhui Polytechnic University, Wuhu, China. His current research interests include reconfigurable computing and compiling, fault tolerant computing, reliability evaluation of high-level circuits, approximate computing, formal verification, semantic big data representation and reasoning, and pattern recognition and image processing.|Zhen Wang received the PhD degree in computer science and technology from Tongji University in 2008. She ever worked as a senior engineer in Synopsys from 2008 to 2013. She is a member of China Computer Federation. She is now working in Shanghai University of Electric Power. Her main research interests include fault tolerant computing, reliability evaluation of high-level circuits, and approximate computing.|Ruixiang He received the MS degree from Anhui Polytechnic University, Wuhu, China in 2018. He is currently an engineer in Paneng Electric Power Technology Co. Ltd, Nanjing, China. His current research interests include reconfigurable computing and compiling, fault tolerant computing, reliability evaluation of high-level circuits, and approximate computing.|Jianhui Jiang received the PhD degree in traffic information engineering and control from Shanghai Tiedao University (in April 2000, it was merged to Tongji University) in 1999. Since 2011, he has been the associate dean of the School of Software Engineering, Tongji University. He is a professor and PhD supervisor in Tongji University. He is a senior member of China Computer Federation. His main research interests include reconfigurable computing and compiling, dependable systems and networks, software reliability engineering, and VLSI test and fault tolerance.|Fei Cheng received the BS degree from Anhui Polytechnic University, Wuhu, China in 2019. He is now a master student at School of Computer and Information Science, Anhui Polytechnic University, Wuhu, China. His current research interests include reconfigurable computing and compiling, formal verification, fault tolerant computing, semantic big data representation and reasoning, and pattern recognition and image processing.|Chenghao Han received the BS degree from Suzhou University, Suzhou, China in 2020. He is now a master student at School of Computer and Information Science, Anhui Polytechnic University, Wuhu, China. His current research interests include reconfigurable computing and compiling, formal verification, and fault tolerant computing.
 Fig.?1 General RPCGRA architecture. Fig.?2 Illustration of misplacement, direct cross-level, and interlaced modes mapped in one RCA. Fig.?3 Comparison of DFGs. Table?1 Mapping parameter comparison of LBM, LBDM, and DFGM. Table?2 Set of benchmarks. Fig.?4 Two kinds of PEA interconnection. Fig.?5 Sub-DFG of DCT32. Table?3 Mapping parameter comparison of grid PEA and row router PEA. Table?5 Comparison of DFGM and LBM (M, N1, and N2). Table?6 Comparison of DFGM and LBM (S$𝐒𝐃$, C$𝐂𝐎𝐍$, and T$𝐓𝐎𝐓𝐀𝐋$). Table?7 Comparison of DFGM and LBDM (M, N1, and N2). Table?8 Comparison of DFGM and LBDM (S$𝐒𝐃$, C$𝐂𝐎𝐍$, and T$𝐓𝐎𝐓𝐀𝐋$).