Title :
Partitioning and Scheduling of Task Graphs on Partially Dynamically Reconfigurable FPGAs
Author :
Cordone, Roberto ; Redaelli, Francesco ; Redaelli, Massimo Antonio ; Santambrogio, Marco Domenico ; Sciuto, Donatella
Author_Institution :
Dipt. di Tecnol. dell´´Inf., Univ. degli Studi di Milano, Crema
fDate :
5/1/2009 12:00:00 AM
Abstract :
This paper proposes a new model for the partitioning and scheduling of a specification on partially dynamically reconfigurable hardware. Although this problem can be solved optimally only by tackling its subproblems jointly, the exceeding complexity of such a task leads to a decomposition into two phases. The partitioning phase is based on a new graph-theoretic approach, which aims to obtain near optimality even if performed independently from the subsequent phase. For the scheduling phase, a new integer linear programming formulation and a heuristic approach are developed. Both take into account configuration prefetching and module reuse. The experimental results show that the proposed method compares favorably with existing solutions.
Keywords :
field programmable gate arrays; graph theory; integer programming; linear programming; reconfigurable architectures; scheduling; FPGA; field programmable gate array; graph-theoretic approach; heuristic approach; integer linear programming formulation; partially dynamically reconfigurable hardware; partitioning phase; scheduling phase; Field-programmable gate array (FPGA); partitioning; reconfigurable hardware (HW); scheduling;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
DOI :
10.1109/TCAD.2009.2015739