Article

Optimal reconfiguration sequence management

Authors:

Majid SarrafzadehAuthors Info & Claims

ASP-DAC '03: Proceedings of the 2003 Asia and South Pacific Design Automation Conference

Pages 359 - 365

https://doi.org/10.1145/1119772.1119843

Published: 21 January 2003 Publication History

Abstract

In this paper, we present an efficient optimal algorithm for minimizing runtime reconfiguration (context switching) delay of executing an application on a reconfigurable system. We assume that the basic operations of the application are already scheduled and each of them has to be realized on the reconfigurable fabric in order to be executed. The modeling and algorithm are both applicable to partially reconfigurable platforms as well as Multi-FPGA systems. The algorithm can be directly applied to minimize the application runtime for many typical classes of applications, where the actual execution delay of basic operations is negligible compared to reconfiguration delay. We prove the optimality and efficiency of our algorithm and report experimental results, which demonstrate 40% to 2.5% improvement in total runtime reconfiguration delay.

References

[1]

L. Belady, "A Study of Replacement Algorithms for Virtual-Storage Computer", IBM Systems Journal, vol 5, no 2, pp. 78--101, 1966

Digital Library

[2]

A. DeHon, J. Wawrzynek, "Reconfigurable Computing: What, Why, Design Automation Requirements" Design Automation Conference, 1999.

Digital Library

[3]

A. DeHon. "DPGA-Coupled Microprocessors: Commodity ICs for the Early 21st Century". In Proceedings of the IEEE Workshop on FPGAs for Custom Computing Machines, April 1994.

[4]

D. Taylor, J. Turner, J. Lockwood, E. Horta, "Dynamic Hardware Plugins (DHP): Exploiting Reconfigurable Hardware for High-Performance Programmable Routers", Computer Networks, vol. 38, no. 3, pp. 295--310, Feb 2002.

Digital Library

[5]

S. Sezer, J. Heron, R. Woods, R. Turner, A. Marshall, "Fast Partial Reconfiguration for FCCMs", IEEE Symposium on for Custom Computing Machines, 1998.

Digital Library

[6]

J. Burns, A. Donlin, J. Hogg, S. Singh, M. Wit. "A Dynamic Reconfiguration Run-Time System", IEEE Symposium on FPGAs for Custom Computing Machines, 1997.

Digital Library

[7]

A. Adario, E. Roehe, S. Bampi, "Dynamically Reconfigurable Architecture for Image Processor Applications", Design Automation Conference, 1999.

Digital Library

[8]

J. Hauser, J. Wawrzynek, "Garp: A MIPS Processor with a Reconfigurable Coprocessor", IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM), 1997.

Digital Library

[9]

Xilinx Inc. online documentaion, http://www.xilinx.com/.

[10]

S. Ogrenci Memik, E. Bozorgzadeh, R. Kastner, M. Sarrafzadeh. "A Super-Scheduler for Embedded Reconfigurable Systems", International Conference on Computer-Aided Design (ICCAD), November 2001.

Digital Library

[11]

P. Schaumont, I. Verbauwhede, K. Keutzer, M. Sarrafzadeh, "A Quick Safari through the Reconfigurable Jungle", Design Automation Conference, 2001.

Digital Library

[12]

Altera Inc. online documentaion, http://www.altera.com/

[13]

E. Horta, J. Lockwood, D. Taylor, D. Parlour, "Dynamic Hardware Plugins in an FPGA with Partial Run-time Reconfiguration", Design Automation Conference, 2002

Digital Library

[14]

Z. Li, S. Hauck, "Configuration Prefetching Techniques for Partial Reconfigurable Coprocessor with Relocation and Defragmentation", ACM/SIGDA Symposium on Field-Programmable Gate Arrays, pp. 187--195, 2002

Digital Library

[15]

Z. Li, S. Hauck, "Configuration Compression for Virtex FPGAs", IEEE Symposium on FPGAs for Custom Computing Machines, 2001.

Digital Library

[16]

Z. Li, K. Compton, S. Hauck, "Configuration Cache Management Techniques for FPGAs", IEEE Symposium on FPGAs for Custom Computing Machines, pp. 22--36, 2000

Digital Library

[17]

K. Compton, S. Hauck, "Reconfigurable Computing: A Survey of Systems and Software", ACM Computing Surveys, Vol. 34, No. 2. pp. 171--210. June 2002.

Digital Library

[18]

Z. Li, K. Compton, S. Hauck, "Configuration Caching Management Techniques for Reconfigurable Computing", Symposium on Field-Programmable Custom Computing Machines, 2000.

Digital Library

Cited By

He RMa YZhao KBian JHu A(2012)ISBAProceedings of the International Conference on Computer-Aided Design10.1145/2429384.2429491(500-507)Online publication date: 5-Nov-2012
https://dl.acm.org/doi/10.1145/2429384.2429491
Banerjee SBozorgzadeh ENoguera JDutt N(2010)Bandwidth Management in Application Mapping for Dynamically Reconfigurable ArchitecturesACM Transactions on Reconfigurable Technology and Systems10.1145/1839480.18394883:3(1-30)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.1145/1839480.1839488
Sirowy SHuang CVahid FSapatnekar S(2010)Online SystemC emulation accelerationProceedings of the 47th Design Automation Conference10.1145/1837274.1837284(30-35)Online publication date: 13-Jun-2010
https://dl.acm.org/doi/10.1145/1837274.1837284
Show More Cited By

Recommendations

FASTER run-time reconfiguration management
ICS '13: Proceedings of the 27th international ACM conference on International conference on supercomputing

The FASTER project Run-Time System Manager offloads programmers from low-level operations by performing task placement, scheduling, and dynamic FPGA reconfiguration. It also manages device fragmentation, configuration caching, pre-fetching and reuse, ...
An optimal algorithm for minimizing run-time reconfiguration delay

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 ...
Development of a Run-Time Reconfiguration System with Low Reconfiguration Overhead

The concept of using a microcontroller coupled to re-programmable FPGAs is being used at the heart of Run-Time Reconfigurable (RTR) systems. This paper presents the development of an RTR system for DSP and telecommunication applications. It differs from ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASP-DAC '03: Proceedings of the 2003 Asia and South Pacific Design Automation Conference

January 2003

865 pages

ISBN:0780376609

DOI:10.1145/1119772

General Chair:
Hiroto Yasuura

Copyright © 2003 ACM.

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]

Sponsors

IPSJ: Information Processing Society of Japan
IEEE Circuits and Systems Society
SIGDA: ACM Special Interest Group on Design Automation
IEICE: Institute of Electronics, Information and Communication Engineers

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 January 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 466 of 1,454 submissions, 32%

Upcoming Conference

ASPDAC '25

Sponsor:
sigda

30th Asia and South Pacific Design Automation Conference

January 20 - 23, 2025

Tokyo , Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
159
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

He RMa YZhao KBian JHu A(2012)ISBAProceedings of the International Conference on Computer-Aided Design10.1145/2429384.2429491(500-507)Online publication date: 5-Nov-2012
https://dl.acm.org/doi/10.1145/2429384.2429491
Banerjee SBozorgzadeh ENoguera JDutt N(2010)Bandwidth Management in Application Mapping for Dynamically Reconfigurable ArchitecturesACM Transactions on Reconfigurable Technology and Systems10.1145/1839480.18394883:3(1-30)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.1145/1839480.1839488
Sirowy SHuang CVahid FSapatnekar S(2010)Online SystemC emulation accelerationProceedings of the 47th Design Automation Conference10.1145/1837274.1837284(30-35)Online publication date: 13-Jun-2010
https://dl.acm.org/doi/10.1145/1837274.1837284
Kooti HBozorgzadeh ELiao SBao L(2010)Reconfiguration-aware spectrum sharing for FPGA based software defined radio2010 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW)10.1109/IPDPSW.2010.5470744(1-4)Online publication date: Apr-2010
https://doi.org/10.1109/IPDPSW.2010.5470744
Hsiung PSantambrogio MHuang C(2009)ReferencesReconfigurable System Design and Verification10.1201/9781420062670.bmatt(225-244)Online publication date: 10-Nov-2009
https://doi.org/10.1201/9781420062670.bmatt
Santambrogio MRedaelli MMaggioni MLombardi FBhanja SMassoud YBahar R(2009)Task graph scheduling for reconfigurable architectures driven by reconfigurations hiding and resources reuseProceedings of the 19th ACM Great Lakes symposium on VLSI10.1145/1531542.1531552(21-26)Online publication date: 10-May-2009
https://dl.acm.org/doi/10.1145/1531542.1531552
Cordone RRedaelli FRedaelli MSantambrogio MSciuto D(2009)Partitioning and scheduling of task graphs on partially dynamically reconfigurable FPGAsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2009.201573928:5(662-675)Online publication date: 1-May-2009
https://dl.acm.org/doi/10.1109/TCAD.2009.2015739
Yuh PYang CChang Y(2007)Temporal floorplanning using the three-dimensional transitive closure subGraphACM Transactions on Design Automation of Electronic Systems10.1145/1278349.127835012:4(37-es)Online publication date: 1-Sep-2007
https://dl.acm.org/doi/10.1145/1278349.1278350
Singhal LBozorgzadeh E(2006)Physically-aware exploitation of component reuse in a partially reconfigurable architectureProceedings of the 20th international conference on Parallel and distributed processing10.5555/1898953.1899147(197-197)Online publication date: 25-Apr-2006
https://dl.acm.org/doi/10.5555/1898953.1899147
Banerjee SBozorgzadeh EDutt N(2006)Integrating physical constraints in HW-SW partitioning for architectures with partial dynamic reconfigurationIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2006.88641114:11(1189-1202)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/TVLSI.2006.886411
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents