BFT: a placement algorithm for non‐rectangle task model in reconfigurable computing system. Issue 3 (1st May 2016)

• Record Type: Journal Article
• Authors: Wang, Chaohui; Wu, Weiguo; Nie, Shiqiang; Qian, Depei
• Is Part Of: IET computers & digital techniques. Volume 10:Issue 3(2016)
• Page Start: 128
• Page End: 137
• Publication Date: 2016-05-01
• Subjects: 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; Computers -- Periodicals; Digital electronics -- Periodicals; Computer engineering -- Periodicals; Computer architecture -- Periodicals; Computer organization -- Periodicals; 621.39
• DOI: 10.1049/iet-cdt.2015.0095
• Languages: English
• ISSNs: 1751-8601

Abstract

Abstract : 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%.