Reconfiguration and Communication-Aware Task Scheduling for High-Performance Reconfigurable Computing
Open Access
- 1 November 2010
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Reconfigurable Technology and Systems
- Vol. 3 (4) , 1-25
Abstract
High-performance reconfigurable computing involves acceleration of significant portions of an application using reconfigurable hardware. When the hardware tasks of an application cannot simultaneously fit in an FPGA, the task graph needs to be partitioned and scheduled into multiple FPGA configurations, in a way that minimizes the total execution time. This article proposes the Reduced Data Movement Scheduling (RDMS) algorithm that aims to improve the overall performance of hardware tasks by taking into account the reconfiguration time, data dependency between tasks, intertask communication as well as task resource utilization. The proposed algorithm uses the dynamic programming method. A mathematical analysis of the algorithm shows that the execution time would at most exceed the optimal solution by a factor of around 1.6, in the worst-case. Simulations on randomly generated task graphs indicate that RDMS algorithm can reduce interconfiguration communication time by 11% and 44% respectively, compared with two other approaches that consider data dependency and hardware resource utilization only. The practicality, as well as efficiency of the proposed algorithm over other approaches, is demonstrated by simulating a task graph from a real-life application - N-body simulation - along with constraints for bandwidth and FPGA parameters from existing high-performance reconfigurable computers. Experiments on SRC-6 are carried out to validate the approach.Keywords
Funding Information
- Division of Industrial Innovation and Partnerships (IIP-0706352)
This publication has 19 references indexed in Scilit:
- RDMS: A hardware task scheduling algorithm for Reconfigurable Computing2009
- Automatic Software Hardware Co-Design for Reconfigurable Computing Systems2007
- Open Source High Performance Floating-Point Modules2006
- Worst-case analysis of the subset sum algorithm for bin packingOperations Research Letters, 2004
- Knapsack Problems2004
- Configuration relocation and defragmentation for run-time reconfigurable computingIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2002
- Fast template placement for reconfigurable computing systemsIEEE Design & Test of Computers, 2000
- Dynamic scheduling of tasks on partially reconfigurable FPGAsIEE Proceedings - Computers and Digital Techniques, 2000
- Linear Time Algorithms for Knapsack Problems with Bounded WeightsJournal of Algorithms, 1999
- A numerical approach to the testing of the fission hypothesisThe Astronomical Journal, 1977