skip to main content
research-article

Efficiently scheduling runtime reconfigurations

Published: 03 October 2008 Publication History

Abstract

Due to the emergence of portable devices that must run complex dynamic applications there is a need for flexible platforms for embedded systems. Runtime reconfigurable hardware can provide this flexibility but the reconfiguration latency can significantly decrease the performance. When dealing with task graphs, runtime support that schedules the reconfigurations in advance can drastically reduce this overhead. However, executing complex scheduling heuristics at runtime may generate an excessive penalty. Hence, we have developed a hybrid design-time/runtime reconfiguration scheduling heuristic that generates its final schedule at runtime but carries out most computations at design-time. We have tested our approach in a PowerPC 405 processor embedded on a FPGA demonstrating that it generates a very small runtime penalty while providing almost as good schedules as a full runtime approach.

References

[1]
Belady, L. A. 1966. A study of replacement algorithms for virtual storage computers. IBM Syst. J., 5, 78--101.
[2]
EDK. 2007. Embedded System Tools Manual. http://www.xilinx.com/ise/embedded/edk91i_docs/est_rm.pdf.
[3]
ISE. 2007. http://www.xilinx.com/publications/prod_mktg/pn0010867.pdf.
[4]
Li, Z. and Hauck, S. 2002. Configuration prefetching techniques for partial reconfigurable coprocessor with relocation and defragmentation. In Proceedings of the ACM/SIGDA 10th International Symposium on Field-Programmable Gate Arrays. Monterey, CA, 187--195.
[5]
Lysaght, P., Blodget, B., Mason, J., Young, J., and Bridgford B. 2006. Enhanced architectures, design methodologies and CAD tools for dynamic reconfiguration of Xilinx FPGAs. In Proceedings of the 2006 International Conference on Field Programmable Logic and Applications. Madrid, Spain, 1--6.
[6]
Marescaux, T., Bartic, A., Verkest, D., Vernalde, S., and Lauwereins, R. 2002. Interconnection networks enable fine-grain dynamic multi-tasking FPGAs. In Proceedings of the 12th International Conference on Field-Programmable Logic and Applications. Montpellier, France, 795--805.
[7]
Markovskiy, Y., Caspi, E., Huang, R., Yeh, J., Chu, M., Wawrzynek, J., and Dehon, A. 2006. Analysis of quasi-static scheduling techniques in a virtualized reconfigurable machine. In Proceedings of the ACM/SIGDA 10th International Symposium on Field-Programmable Gate Arrays. Monterey, CA, 196--205.
[8]
Noguera, J. and Badía, R. M. 2004. Multitasking on reconfigurable architectures: Micro architecture support and dynamic scheduling. ACM Trans. Embed. Comput. Syst., 3, 2, 385--406.
[9]
Peng, Y., Wong, Ch., Marchal, P., Catthoor, F., Desmet., D., Verkest, D., and Lauwereins, R. 2001. Energy-aware runtime scheduling for embedded-multiprocessors SOCs. IEEE J. Des. Test Comput. 18, 5, 46--58.
[10]
Pocket G. L. 2007. http:/www.sundialsoft.freeserve.co.uk/pgl.htm.
[11]
Qu, Y., Soininen, J., and Nurmi, J. 2006. A parallel configuration model for reducing the runtime reconfiguration overhead. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE). Munich, Germany, 965--969.
[12]
Resano, J., Mozos D., Verkest, D. Vernalde, S., and Catthoor, F. 2004. A hybrid design-time/run-time scheduling flow to minimize the reconfiguration overhead of FPGAs. J. Microproc. Microarchi. 28, 5--6, 291--301.
[13]
Resano, J., Mozos, D., and Catthoor, F. 2005a. A hybrid prefetch scheduling heuristic to minimize at run-time the reconfiguration overhead of dynamically reconfigurable HW. Proceedings of the Design Automation and Test in Europe Conference. Munich, Germany, 106--111.
[14]
Resano, J., Mozos, D., Catthoor, F., and Verkest, D. 2005b. A reconfiguration manager for dynamically reconfigurable hardware. IEEE Design & Test Comput. 22, 5, 452--460.
[15]
Shang, L. and Niraj K. J. 2002. Hardware-software co-synthesis of low power real-time distributed embedded systems with dynamically reconfigurable FPGAs. In Proceedings of the Conference on Asia South Pacific Design Automation/VLSI Design, Bangalore, India, 345--360.
[16]
Walder, H. and Platzner, M. 2004. A runtime environment for reconfigurable operating systems. In Proceedings of the 14th International Conference on Field-Programmable Logic and Applications, Leuven, Belgium, 831--835.
[17]
Wong, C., Marchal, P., and Yang, P. 2001. Task concurrency management methodology to schedule the MPEG4 IM1 player on a highly parallel processor platform. In Proceedings of the 9th International Symposium on Hardware/Software Codesign, Copenhaguen, Denmark, April, 25--27. 170--175.
[18]
Xilinx. 2007. http://www.xilinx.com/univ/xupv2p.html.
[19]
Yang, P. and Catthoor, F. 2004. Dynamic mapping and ordering tasks of embedded real-time systems on multiprocessor platforms. In Proceedings of Software and Compilers for Embedded Systems 8th International Workshop. 167--181.

Cited By

View all
  • (2018)Towards Dynamically Reconfigurable SoCs (DRSoCs) in industrial automation: State of the art, challenges and opportunitiesMicroprocessors and Microsystems10.1016/j.micpro.2018.07.00262(20-40)Online publication date: Oct-2018
  • (2018)A novel FPGA-based architecture for the estimation of the virtual dimensionality in remotely sensed hyperspectral imagesJournal of Real-Time Image Processing10.1007/s11554-014-0482-215:2(297-308)Online publication date: 1-Aug-2018
  • (2017)Task Transition Scheduling for Data-Adaptable SystemsACM Transactions on Embedded Computing Systems10.1145/304749816:4(1-28)Online publication date: 11-May-2017
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems
ACM Transactions on Design Automation of Electronic Systems  Volume 13, Issue 4
September 2008
328 pages
ISSN:1084-4309
EISSN:1557-7309
DOI:10.1145/1391962
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

Publication History

Published: 03 October 2008
Accepted: 01 April 2008
Revised: 01 November 2007
Received: 01 April 2007
Published in TODAES Volume 13, Issue 4

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. FPGAs
  2. Reconfigurable architectures
  3. hardware multitasking
  4. runtime/design-time scheduling

Qualifiers

  • Research-article
  • Research
  • Refereed

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2018)Towards Dynamically Reconfigurable SoCs (DRSoCs) in industrial automation: State of the art, challenges and opportunitiesMicroprocessors and Microsystems10.1016/j.micpro.2018.07.00262(20-40)Online publication date: Oct-2018
  • (2018)A novel FPGA-based architecture for the estimation of the virtual dimensionality in remotely sensed hyperspectral imagesJournal of Real-Time Image Processing10.1007/s11554-014-0482-215:2(297-308)Online publication date: 1-Aug-2018
  • (2017)Task Transition Scheduling for Data-Adaptable SystemsACM Transactions on Embedded Computing Systems10.1145/304749816:4(1-28)Online publication date: 11-May-2017
  • (2016)A Reconfigurable Framework for Performance Enhancement With Dynamic FPGA Configuration PrefetchingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2015.244869435:1(100-113)Online publication date: Jan-2016
  • (2015)FPGA Implementation of the HySime Algorithm for the Determination of the Number of Endmembers in Hyperspectral DataIEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing10.1109/JSTARS.2015.24257318:6(2870-2883)Online publication date: Jun-2015
  • (2015)FPGA implementation to estimate the number of endmembers in hyperspectral images2015 25th International Conference on Field Programmable Logic and Applications (FPL)10.1109/FPL.2015.7293936(1-8)Online publication date: Sep-2015
  • (2013)The Promise of Reconfigurable Computing for Hyperspectral Imaging Onboard Systems: A Review and TrendsProceedings of the IEEE10.1109/JPROC.2012.2231391101:3(698-722)Online publication date: Mar-2013
  • (2013)Runtime hardware/software task transition scheduling for data-adaptable embedded systems2013 International Conference on Field-Programmable Technology (FPT)10.1109/FPT.2013.6718382(342-345)Online publication date: Dec-2013
  • (2013)Efficient reconfiguration methods to enable rapid deployment of runtime reconfigurable systems2013 Asilomar Conference on Signals, Systems and Computers10.1109/ACSSC.2013.6810401(819-823)Online publication date: Nov-2013
  • (2012)Martian dust devils detector over FPGAGeoscientific Instrumentation, Methods and Data Systems10.5194/gi-1-23-20121:1(23-31)Online publication date: 20-Apr-2012
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media