Nothing Special   »   [go: up one dir, main page]

skip to main content
article

EMBARC: an efficient memory bank assignment algorithm for retargetable compilers

Published: 11 June 2004 Publication History

Abstract

Many architectures today, especially embedded systems, have multiple memory partitions, each with potentially different performance and energy characteristics. To meet the strict time-to-market requirements of systems containing these chips, compilers require retargetable alogrithms for effectively assigning values to the memory partitions. The EMBARC algorithm described in this paper is the first algorithm to attempt to realize a comprehensive, retargetable algorithm for effective partition assignment of variables in an arbitrary memory hierarchy. It supports a wide variety of memory models including on-chip SRAMs, multiple layers of caches, and even uncached DRAM partitions. Even though it is designed to handle such a range of memory hierarchies, EMBARC is capable of generating partition assignments of similar quality to algorithms designed for specific memory hierarchies. We use a large range of benchmarks and memory models to demonstrate the effectiveness of the EMBARC algorithm. We found that EMBARC can achieve 99% of the improvement of a dedicated algorithm for cacheless systems without SRAM. Also, for cacheless systems with SRAM, EMBARC generated the optimal partition assignment for benchmarks that were simple enough to hand-generate an optimal partition assignment. As further proof of EMBARC's generality, we also show how EMBARC can be used to generate partition assignments for a memory hierarchies with two on-chip caches that can be accessed in parallel.

References

[1]
Trimaran test suite. World Wide Web, http://www.trimaran.org/
[2]
University of tortono dsp benchmark suite. World Wide Web, http://www.eecg.toronto.edu/~corinna/DSP/infrastructure/UTDSP.tar.gz
[3]
O. Avissar and R. Barua. An optimal memory allocation scheme for scratch-pad-based embedded systems. ACM Transactions on Embedded Computing Systems, 1(1):6--26, 2002.
[4]
O. Avissar, R. Barua, and D. Stewart. Heterogeneous memory management for embedded systems. In Proceedings of the International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, pages 34--43. ACM Press, 2001.
[5]
R. Banakar, S. Steinke, B.-S. Lee, M. Balakrishnan, and P. Marwedel. Scratchpad memory: design alternative for cache on-chip memory in embedded systems. In Proceedings of the tenth international symposium on Hardware/software codesign, pages 73--78. ACM Press, 2002.
[6]
M. E. Benitez and J. W. Davidson. A portable global optimizer and linker. In Proceedings of the SIGPLAN '88 Conference on Programming Language Design and Implementation, pages 329--338, 1988.
[7]
D. Brooks, V. Tiwari, and M. Martonosi. Wattch: a framework for architectural-level power analysis and optimizations. In Proceedings of the 27th annual international symposium on Computer architecture, pages 83--94. ACM Press, 2000.
[8]
D. Burger, T. M. Austin, and S. Bennett. Evaluating future microprocessors: The simplescalar tool set. Technical Report CS-TR-1996-1308, University of Wisconsin, Madison, 1996.
[9]
B. Calder, C. Krintz, S. John, and T. Austin. Cache-conscious data placement. In Proceedings of the eighth international conference on Architectural support for programming anguages and operating systems, pages 139--149. ACM Press, 1998.
[10]
V. Delaluz, M. Kandemir, N. Vijaykrishnan, and M. J. Irwin. Energy-oriented compiler optimizations for partitioned memory architectures. In Proceedings of the international conference on Compilers, architectures, and synthesis for embedded systems, pages 138--147. ACM Press, 2000.
[11]
M. R. Guthaus, J. S. Ringenberg, D. Ernst, T. M. Austin, T. Mudge, and R. B. Brown. Mibench: A free, commercially representative embedded benchmark suite.
[12]
M. Kandemir, J. Ramanujam, J. Irwin, N. Vijaykrishnan, I. Kadayif, and A. Parikh. Dynamic management of scratch-pad memory space. In Proceedings of the 38th conference on Design automation, pages 690--695. ACM Press, 2001.
[13]
S. Lee, J. Lee, S. L. Min, J. D. Hiser, and J. W. Davidson. Code optimizations for a dual instruction set processor based on selective code transformations. In Proceedings of 7th International Workshop on Software and Compilers for Embedded Systems, 2003.
[14]
P. R. Panda, F. Catthoor, N. D. Dutt, K. Danckaeart, E. brockmeyer, C. Kulkarni, A. Vandercappelle, and P. G. Kjeldsberg. Data and memory optimization techniques for embedded systems. ACM Transactions on Design Automation of Electronic Systems, 6(2):149--206, April 2001.
[15]
P. R. Panda, N. D. Dutt, and A. Nicolau. On-chip vs. off-chip memory: The data partitioning problem in embedded process r-based systems. ACM Transactions on Design Automation of Electronic Systems, 5(3):682--704, 2000.
[16]
M. A. R. Saghir, P. Chow, and C. G. Lee. Exploiting dual data-memory banks in digital signal processors. In Proceedings of the SIGPLAN '96 International Conference on Architectural Support for Programming Languages and Operating Systems, pages 234--243, 1996.
[17]
S. Udayakumaran and R. Barua. Compiler-decided dynamic memory allocation for scratch-pad based embedded systems. In Proceedings of the SIGPLAN '03 Conference on Compiler and Architecture Support for Embedded Systems, October 2003.
[18]
W. Zhao, B. Cai, D. Whalley, M. W. Bailey, R. van Engelen, X. Yuan, J. D. Hiser, J. W. Davidson, K. Gallivan, and D. L. Jones. Vista: a system for interactive code improvement. In Proceedings of the Joint Conference on Languages, Compilers and Tools for Embedded Systems, pages 155--164, 2002.

Cited By

View all
  • (2020)Local Memory Mapping of Multicore Processors on an Automatic Parallelizing CompilerIEICE Transactions on Electronics10.1587/transele.2019LHP0010E103.C:3(98-109)Online publication date: 1-Mar-2020
  • (2011)Compiler-assisted dynamic scratch-pad memory management with space overlapping for embedded systemsSoftware—Practice & Experience10.1002/spe.102041:7(737-752)Online publication date: 1-Jun-2011
  • (2010)DARTSProceedings of the 2010 16th IEEE Real-Time and Embedded Technology and Applications Symposium10.1109/RTAS.2010.36(333-342)Online publication date: 12-Apr-2010
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices
ACM SIGPLAN Notices  Volume 39, Issue 7
LCTES '04
July 2004
265 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/998300
Issue’s Table of Contents
  • cover image ACM Conferences
    LCTES '04: Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems
    June 2004
    276 pages
    ISBN:1581138067
    DOI:10.1145/997163
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

Publication History

Published: 11 June 2004
Published in SIGPLAN Volume 39, Issue 7

Check for updates

Author Tags

  1. embedded systems
  2. partition assignment
  3. retargetable compilers

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)5
  • Downloads (Last 6 weeks)0
Reflects downloads up to 19 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2020)Local Memory Mapping of Multicore Processors on an Automatic Parallelizing CompilerIEICE Transactions on Electronics10.1587/transele.2019LHP0010E103.C:3(98-109)Online publication date: 1-Mar-2020
  • (2011)Compiler-assisted dynamic scratch-pad memory management with space overlapping for embedded systemsSoftware—Practice & Experience10.1002/spe.102041:7(737-752)Online publication date: 1-Jun-2011
  • (2010)DARTSProceedings of the 2010 16th IEEE Real-Time and Embedded Technology and Applications Symposium10.1109/RTAS.2010.36(333-342)Online publication date: 12-Apr-2010
  • (2009)Runtime Memory Allocation in a Heterogeneous Reconfigurable PlatformProceedings of the 2009 International Conference on Reconfigurable Computing and FPGAs10.1109/ReConFig.2009.38(71-76)Online publication date: 9-Dec-2009
  • (2008)Efficient dynamic heap allocation of scratch-pad memoryProceedings of the 7th international symposium on Memory management10.1145/1375634.1375640(31-40)Online publication date: 7-Jun-2008
  • (2007)An array allocation scheme for energy reduction in partitioned memory architecturesProceedings of the 16th international conference on Compiler construction10.5555/1759937.1759941(32-47)Online publication date: 26-Mar-2007
  • (2007)An Array Allocation Scheme for Energy Reduction in Partitioned Memory ArchitecturesCompiler Construction10.1007/978-3-540-71229-9_3(32-47)Online publication date: 2007
  • (2013)SPM-SieveProceedings of the 2013 International Conference on Compilers, Architectures and Synthesis for Embedded Systems10.5555/2555729.2555750(1-10)Online publication date: 29-Sep-2013
  • (2013)SPM-Sieve: A framework for assisting data partitioning in scratch pad memory based systems2013 International Conference on Compilers, Architecture and Synthesis for Embedded Systems (CASES)10.1109/CASES.2013.6662527(1-10)Online publication date: Sep-2013
  • (2012)On-chip memory architecture exploration framework for DSP processor-based embedded system on chipACM Transactions on Embedded Computing Systems10.1145/2146417.214642211:1(1-25)Online publication date: 5-Apr-2012
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media