An ILP formulation for the task graph scheduling problem tailored to bi-dimensional reconfigurable architectures

F. Redaelli*, M. D. Santambrogio, S. Ogrenci Memik

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

Abstract

This work proposes an exact ILP formulation for the task scheduling problem on a 2D dynamically and partially reconfigurable architecture. Our approach takes physical constraints of the target device that are relevant for reconfiguration into account. Specifically, we consider the limited number of reconfigurators, which are used to reconfigure the device. This work also proposes a reconfiguration-aware heuristic scheduler, which exploits configuration prefetching, module reuse, and antifragmentation techniques. We experimented with a system employing two reconfigurators. This system can be easily implemented using standard FPGAs. Our proposed ILP model can lead to an overall improvement close to 30% compared to other approaches in literature while the heuristic scheduler obtains the optimal schedule length on 60% of the considered instances.

Original languageEnglish (US)
Title of host publicationProceedings - 2008 International Conference on Reconfigurable Computing and FPGAs, ReConFig 2008
Pages97-102
Number of pages6
DOIs
StatePublished - Dec 1 2008
Event2008 International Conference on Reconfigurable Computing and FPGAs, ReConFig 2008 - Cancun, Mexico
Duration: Dec 3 2008Dec 5 2008

Publication series

NameProceedings - 2008 International Conference on Reconfigurable Computing and FPGAs, ReConFig 2008

Other

Other2008 International Conference on Reconfigurable Computing and FPGAs, ReConFig 2008
CountryMexico
CityCancun
Period12/3/0812/5/08

ASJC Scopus subject areas

  • Hardware and Architecture
  • Software

Fingerprint Dive into the research topics of 'An ILP formulation for the task graph scheduling problem tailored to bi-dimensional reconfigurable architectures'. Together they form a unique fingerprint.

  • Cite this

    Redaelli, F., Santambrogio, M. D., & Memik, S. O. (2008). An ILP formulation for the task graph scheduling problem tailored to bi-dimensional reconfigurable architectures. In Proceedings - 2008 International Conference on Reconfigurable Computing and FPGAs, ReConFig 2008 (pp. 97-102). [4731777] (Proceedings - 2008 International Conference on Reconfigurable Computing and FPGAs, ReConFig 2008). https://doi.org/10.1109/ReConFig.2008.42