article

Modeling and optimizing run-time reconfiguration using evolutionary computation

Authors:

T. M. McGinnity,

L. P. MaguireAuthors Info & Claims

ACM Transactions on Embedded Computing Systems (TECS), Volume 3, Issue 4

Pages 661 - 685

https://doi.org/10.1145/1027794.1027795

Published: 01 November 2004 Publication History

Abstract

The hardware--software (HW--SW) partitioning of applications to dynamically reconfigurable embedded systems allows for customization of their hardware resources during run-time to meet the demands of executing applications. The run-time reconfiguration (RTR) of such systems can have an impact on the HW--SW partitioning strategy and the system performance. It is therefore important to consider approaches to optimally reduce the RTR overhead during the HW--SW partitioning stage. In order to examine potential benefits in performance, it is necessary to develop a method to model and evaluate the RTR. In this paper, a novel method of modeling and evaluating such RTR-reduced HW--SW partitions is presented. The techniques of computation-reconfiguration overlap and the retention of circuitry between reconfigurations are used within this model to explore the possibilities of RTR reduction. The integration of this model into the authors' current genetic-algorithm-driven HW--SW partitioner is also presented, with two applications used to illustrate the benefits of RTR-reduced exploration during HW--SW partitioning.

References

[1]

Bakshi, S. and Gajski, D. 1999. Partitioning and pipelining for performance-constrained hardware/software systems. IEEE Trans. VLSI Syst. 7, 4, 419--432.]]

Digital Library

[2]

Balarin, F., Lavagno, L., Murthy, P., and Sangiovanni-vincentelli, A. 1998. Scheduling for embedded real-time systems. IEEE Des. Test Comput. 15, 1, 71--82.]]

Digital Library

[3]

Brebner, G. 1997. Automatic identification of swappable logic units in XC6200 circuitry. In International Conference on Field Programmable Logic and Applications (FPL). 173--182.]]

Digital Library

[4]

Chameleon. 2001. CS2000 Reconfigurable Communication Processor User Guide. Chameleon Systems, Inc., San Jose, CA.]]

[5]

Chatha, K. and Vemuri, R. 2000. An iterative algorithm for HW--SW partitioning, hardware design space exploration and scheduling. Des. Automat. Embedd. Syst. 5, 3--4, 281--293.]]

[6]

Chichkov, A. V. and Almieda, C. 1997. An hardware--software partitioning algorithm for CCM's. In International Conference on Field Programmable Logic and Applications (FPL). 274--283.]]

Digital Library

[7]

Dave, B. P. 1999. CRUSADE: Hardware/software co-synthesis of dynamically reconfigurable heterogeneous real-time distributed embedded systems. In Proceedings of the Design, Automation and Test in Europe Conference. 97--104.]]

Digital Library

[8]

Dehon, A. 1996. Reconfigurable Architecture for General-purpose Computing. Ph.D. Thesis, MIT.]]

Digital Library

[9]

Deller, J. D. and Proakis, J. G. 1997. Discrete-time Processing of Speech Signals, 2nd edition. Prentice-Hall, Englewood Cliffs, NJ.]]

Digital Library

[10]

deMicheli, G. 1994. Synthesis and Optimisation of Digital Circuits. McGraw-Hill, Inc., New York.]]

Digital Library

[11]

deMicheli, G. and Gupta, R. 1997. HW-SW codesign. In Proc. IEEE 85, 3, 349--365.]]

[12]

Fleischmann, J., Buchenrieder, K., and Kress, R. 1999. Codesign of embedded systems based on java and reconfigurable hardware components. In Proceedings of the Design, Automation and Test in Europe Conference. 768--769.]]

Digital Library

[13]

Green, P. and Edwards, M. D. 2000. OO oriented development method for reconfigurable embedded systems. IEE Comput. Digital Tech. 147, 3, 153--158.]]

[14]

Grode, L., Knudsen, P., and Madsen, J. 1998. Hardware resource allocation for hardware--software partitioning in the LYCOS system. In Proceedings of the Design, Automation and Test in Europe Conference. 22--27.]]

Digital Library

[15]

Harkin, J., McGinnity, T. M., and Maguire, L. P. 2001a. Genetic algorithm driven hardware--software partitioning for dynamically reconfigurable embedded systems. Microprocess. Microsyst. 25, 5, 263--274.]]

[16]

Harkin, J., McGinnity, T. M., and Maguire, L. P. 2001b. Hardware--software partitioning: A reconfigurable and evolutionary computing approach. In International Conference on Field Programmable Logic & Applications. 595--600.]]

Digital Library

[17]

Harkin, J., McGinnity, T. M., and Maguire, L. P. 2000a. Partitioning methodology for dynamically reconfigurable embedded systems. IEE Comput. Digital Tech. 147, 6, 391--396.]]

[18]

Harkin, J., McGinnity, T. M., and Maguire, L. P. 2000b. Accelerating embedded applications using dynamically reconfigurable hardware and evolutionary algorithms. In IEEE Field Programmable Custom Computing Machines. 321--322.]]

Digital Library

[19]

Hartenstein, R., Becker, J., and Kress, R. 1996. Two level hardware/software partitioning using CoDe-x. In IEEE Symposium on Engineering of Computer Based Systems, Friedrichshafen, Germany.]]

Digital Library

[20]

Hatha, K. S. and Vemuri, R. 1999. Hardware-software codesign for dynamically reconfigurable architectures. In International Conference on Field Programmable Logic and Applications. 175--184.]]

Digital Library

[21]

Hauck, S., Li, Z., and Schwabe, E. 1999. Configuration compression for the Xilinx XC6200 FPGA. IEEE Trans. CAD Integr. Circ. Syst. 18, 8, 1107--1113.]]

Digital Library

[22]

Heron, J. P. and Woods, R. J. 1998. Accelerating run-time reconfiguration on custom computing machines. In Proceedings of SPIE. 19--24.]]

Digital Library

[23]

Herron, J. P., Woods, R., Sezer, S., and Turner, R. 2001. Development of a runtime reconfigurable system with low reconfiguration overhead. J. VLSI Signal Process. 28, 1--2, 97--113.]]

[24]

Hutchings, B. L. and Wirthlin, M. J. 1995. Implementation approaches for reconfigurable logic applications. In International Conference on Field Programmable Logic & Applications (FPL). 419--428.]]

Digital Library

[25]

Jantsch, A., Ellervee, P., Oberg, J., and Hemani, A. 1994. A case study on hardware--software Partitioning. In IEEE Field Programmable Custom Computing Machines (FCCM). 111--118.]]

[26]

Knudsen, P. and Madsen, J. 1996. PACE: A dynamic programming algorithm for hardware--software partitioning. In 4th International Workshop on Hardware-software Codesign. 85--92.]]

Digital Library

[27]

Li, Y., Callahan, T., Darnell, E., Harr, R., and Stockwood, J. 2000. Hardware--software codesign of embedded reconfigurable architectures. In Proceedings of 37th Design Automation Conference. 507--512.]]

Digital Library

[28]

Luk, W., Shirazi, N., and Cheung, P. 1997. Compilation tools for run-time reconfiguration designs. In IEEE Field Programmable Custom Computing Machines (FCCM). 56--65.]]

Digital Library

[29]

Lysaght, P. and Dunlop, J. 1993. Dynamic reconfiguration of FPGAs. In Proceeding of International Workshop on FPGAs. 82--94.]]

Digital Library

[30]

Michalewicz, Z. 1996. Genetic Algorithms + Data Structures = Evolution Programs. Springer, Berlin.]]

Digital Library

[31]

Noguera, J. and Badia, R. 2001. A HW--SW partitioning algorithm for dynamically reconfigurable architectures. In Proceedings of the Design, Automation and Test in Europe Conference. 729--734.]]

Digital Library

[32]

Parker, J. R. 1997. Algorithms for Image Processing and Computer Vision. John Wiley, New York.]]

[33]

Seals, R. C. and Whapshott, G. F. 1997. Programmable Logic: PLDs and FPGAs. MacMillan.]]

[34]

Sezer, S., Heron, J., Woods, R., Turner, R., and Marshall, A. 1998. Fast partial reconfiguration for FCCMs. In IEEE Symposium on Field Programmable Custom Computing Machines. 318--319.]]

Digital Library

[35]

Shrivastava, A. and Kumar, M. 2000. Optimal hardware--software partitioning for concurrent specification using dynamic programming. In International Conference on VLSI Design. 110--113.]]

Digital Library

[36]

Srinivasan, V., Radhakrishnan, S., and Vemuri, R. 1998. Hardware software partitioning with integrated hardware design space exploration. In Proceedings of the Design, Automation & Test in Europe Conference (DATE). 28--35.]]

Digital Library

[37]

Trimberger, S. 1998. Scheduling designs into a time-multiplexed FPGA. In ACM/SIGDA International Symposium on FPGAs (FPGA). 153--160.]]

Digital Library

[38]

Wirthlin, M. J. 1997. Improving Functional Density Through Run-time Circuit Reconfiguration. Ph.D. Thesis, Brigham Young University.]]

Digital Library

[39]

Xilinx. 1997. XC6216 Data sheet, Version 1.10. Xilinx Corporation, San Jose, CA.]]

Cited By

Vipin KFahmy S(2018)FPGA Dynamic and Partial ReconfigurationACM Computing Surveys10.1145/319382751:4(1-39)Online publication date: 25-Jul-2018
https://dl.acm.org/doi/10.1145/3193827
Wu HShen CKee HSane NPlishker WBhattacharyya S(2014)Mapping Parameterized Dataflow Graphs onto FPGA PlatformsAcademic Press Library in Signal Processing: Volume 4 - Image, Video Processing and Analysis, Hardware, Audio, Acoustic and Speech Processing10.1016/B978-0-12-396501-1.00024-8(643-673)Online publication date: 2014
https://doi.org/10.1016/B978-0-12-396501-1.00024-8
Perng NHung STu C(2010)Task Scheduling for Context Minimization in Dynamically Reconfigurable PlatformsJournal of Signal Processing Systems10.1007/s11265-009-0354-359:1(3-12)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.1007/s11265-009-0354-3
Show More Cited By

Index Terms

Modeling and optimizing run-time reconfiguration using evolutionary computation

Recommendations

Improving functional density using run-time circuit reconfiguration

The ability to provide flexibility and allow fine-grain circuit specialization make field programmable gate arrays (FPGA's) ideal candidates for computing elements within application-specific architectures. The benefits of gate-level specialization and ...
Run-Time Reconfiguration for Automatic Hardware/Software Partitioning
RECONFIG '10: Proceedings of the 2010 International Conference on Reconfigurable Computing and FPGAs

Parameterisable configurations allow very fast run-time reconfiguration in FPGAs. The main advantage of this new concept is the automated tool flow that converts a hardware design into a more resource-efficient run-time reconfigurable design without a ...
Automating reconfiguration chain generation for SRL-Based run-time reconfiguration
ARC'12: Proceedings of the 8th international conference on Reconfigurable Computing: architectures, tools and applications

Run-time reconfiguration (RTR) of FPGAs is mainly done using the configuration interface. However, for a certain group of designs, RTR using the shift register functionality of the LUTs is a much faster alternative than conventional RTR using the ICAP. ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Embedded Computing Systems

ACM Transactions on Embedded Computing Systems Volume 3, Issue 4

November 2004

203 pages

ISSN:1539-9087

EISSN:1558-3465

DOI:10.1145/1027794

Issue’s Table of Contents

Copyright © 2004 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 01 November 2004

Published in TECS Volume 3, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
1,486
Total Downloads

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

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Vipin KFahmy S(2018)FPGA Dynamic and Partial ReconfigurationACM Computing Surveys10.1145/319382751:4(1-39)Online publication date: 25-Jul-2018
https://dl.acm.org/doi/10.1145/3193827
Wu HShen CKee HSane NPlishker WBhattacharyya S(2014)Mapping Parameterized Dataflow Graphs onto FPGA PlatformsAcademic Press Library in Signal Processing: Volume 4 - Image, Video Processing and Analysis, Hardware, Audio, Acoustic and Speech Processing10.1016/B978-0-12-396501-1.00024-8(643-673)Online publication date: 2014
https://doi.org/10.1016/B978-0-12-396501-1.00024-8
Perng NHung STu C(2010)Task Scheduling for Context Minimization in Dynamically Reconfigurable PlatformsJournal of Signal Processing Systems10.1007/s11265-009-0354-359:1(3-12)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.1007/s11265-009-0354-3
Götz MRettberg APereira CRammig F(2009)Run-time reconfigurable RTOS for reconfigurable systems-on-chipJournal of Embedded Computing10.5555/1516712.15167173:1(39-51)Online publication date: 1-Jan-2009
https://dl.acm.org/doi/10.5555/1516712.1516717
Banerjee SBozorgzadeh EDutt N(2009)Exploiting application data-parallelism on dynamically reconfigurable architecturesIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2008.200349017:2(234-247)Online publication date: 1-Feb-2009
https://dl.acm.org/doi/10.1109/TVLSI.2008.2003490
Sima VBertels K(2009)Runtime decision of hardware or software execution on a heterogeneous reconfigurable platformProceedings of the 2009 IEEE International Symposium on Parallel&Distributed Processing10.1109/IPDPS.2009.5161220(1-6)Online publication date: 23-May-2009
https://dl.acm.org/doi/10.1109/IPDPS.2009.5161220
Hasan MSotirios S(2009)Customized kernel execution on reconfigurable hardware for embedded applicationsMicroprocessors & Microsystems10.1016/j.micpro.2008.12.00333:3(211-220)Online publication date: 1-May-2009
https://dl.acm.org/doi/10.1016/j.micpro.2008.12.003
Berthelot FNouvel FHouzet D(2008)A Flexible system level design methodology targeting run-time reconfigurable FPGAsEURASIP Journal on Embedded Systems10.5555/1340444.13879852008(1-18)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.5555/1340444.1387985
Anthony RRettberg AChen DJahnich Ide Boer GEkelin C(2008)A Dynamically Reconfigurable Automotive Control System ArchitectureIFAC Proceedings Volumes10.3182/20080706-5-KR-1001.0157341:2(9308-9313)Online publication date: 2008
https://doi.org/10.3182/20080706-5-KR-1001.01573
Berthelot FNouvel FHouzet D(2008)A Flexible System Level Design Methodology Targeting Run-Time Reconfigurable FPGAsEURASIP Journal on Embedded Systems10.1155/2008/7939192008(1-18)Online publication date: 2008
https://doi.org/10.1155/2008/793919
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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents