An optimal algorithm for minimizing run-time reconfiguration delay
Authors:
Open Access
- 1 May 2004
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Embedded Computing Systems
- Vol. 3 (2) , 237-256
Abstract
Reconfiguration delay is one of the major barriers in the way of dynamically adapting a system to its application requirements. The run-time reconfiguration delay is quite comparable to the application latency for many classes of applications and might even dominate the application run-time. In this paper, we present an efficient optimal algorithm for minimizing the run-time reconfiguration (context switching) delay of executing an application on a dynamically adaptable system. The system is composed of a number of cameras with embedded reconfigurable resources collaborating in order to track an object. The operations required to execute in order to track the object are revealed to the system at run-time and can change according to a number of parameters, such as the target shape and proximity. Similarly, we can assume that the applications comprising tasks are already scheduled and each of them has to be realized on the reconfigurable fabric in order to be executed.The modeling and the algorithm are both applicable to partially reconfigurable platforms as well as multi-FPGA systems. The algorithm can be directly applied to minimize the application run-time for the typical classes of applications, where the actual execution delay of the basic operations is negligible compared to the reconfiguration delay. We prove the optimality and the efficiency of our algorithm. We report the experimental results, which demonstrate a 2.5--40% improvement on the total run-time reconfiguration delay as compared to other heuristics.Keywords
This publication has 10 references indexed in Scilit:
- Budget Management with ApplicationsAlgorithmica, 2002
- Reconfigurable computingACM Computing Surveys, 2002
- Dynamic hardware plugins: exploiting reconfigurable hardware for high-performance programmable routersComputer Networks, 2002
- Dynamic hardware plugins in an FPGA with partial run-time reconfigurationProceedings of the 39th conference on Design automation - DAC '02, 2002
- Page Replacement with Multi-Size Pages and Applications to Web CachingAlgorithmica, 2002
- A framework for reconfigurable computing: task scheduling and context managementIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2001
- On the complexity of loop fusionParallel Computing, 2000
- Strongly Competitive Algorithms for Paging with Locality of ReferenceSIAM Journal on Computing, 1996
- Competitive Paging with Locality of ReferenceJournal of Computer and System Sciences, 1995
- A study of replacement algorithms for a virtual-storage computerIBM Systems Journal, 1966