BFT: a placement algorithm for non-rectangle task model in reconfigurable computing system

作     者：Wang, Chaohui Wu, Weiguo Nie, Shiqiang Qian, Depei 

作者机构：Xi An Jiao Tong Univ Dept Comp Sci & Technol Xian Shaanxi Peoples R China Beihang Univ Sch Comp Sci & Engn Beijing 100191 Peoples R China 

出 版 物：《IET COMPUTERS AND DIGITAL TECHNIQUES》 (IET Comput. Digital Tech.)

年 卷 期：2016年第10卷第3期

页      面：128-137页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National High-Tech Research and Development Plan of China [2012AA01A306] National Natural Science Foundation of China [91330117, 61202041] 

主　　题：reconfigurable architectures field programmable gate arrays processor scheduling BFT nonrectangle task model reconfigurable computing system task scheduling and placement problem RC system field programmable gate array FPGA system complexity reconfigurable resources task model transformation strategy innovative best-fit transformation placement algorithm total execution time rejection rate first-fit algorithm multishape placement algorithm 3D compaction algorithm 

摘      要：Task scheduling and placement problem is one of the most significant and time-consuming parts in reconfigurable computing (RC) system. Many investigators have explored on the subject, and most of the traditional studies are concentrated on the rectangle task model, which is inconsistent with objective task shape placed in a field programmable gate array (FPGA) but simplifies the system complexity. Rectangle task model produces inner fragments which reduces utilisation of reconfigurable resources in an FPGA. In this study, a task model transformation strategy and an innovative best-fit transformation (BFT) placement algorithm are proposed for a non-rectangle task model to improve the performance of an RC system in rejection rate and total execution time. According to simulation experiments, BFT algorithm reduced the rejection rate by 15% and 7% compared with that of the first-fit algorithm and the best-fit algorithm, respectively. Multi-shape placement algorithm and 3D compaction algorithm are also cited to compare with the BFT algorithm. The result shows that the BFT algorithm has less total execution time in short laxity period and lower rejection rate in large laxity period. Compared with 3D compaction algorithm, the proposed algorithm reduced the total execution time up to 10.79%.