More Web Proxy on the site http://driver.im/

research-article

WCET-aware data selection and allocation for scratchpad memory

Authors:

Jingling XueAuthors Info & Claims

ACM SIGPLAN Notices, Volume 47, Issue 5

Pages 41 - 50

https://doi.org/10.1145/2345141.2248425

Published: 12 June 2012 Publication History

Abstract

In embedded systems, SPM (scratchpad memory) is an attractive alternative to cache memory due to its lower energy consumption and higher predictability of program execution. This paper studies the problem of placing variables of a program into an SPM such that its WCET (worst-case execution time) is minimized. We propose an efficient dynamic approach that comprises two novel heuristics. The first heuristic iteratively selects a most beneficial variable as an SPM resident candidate based on its impact on the k longest paths of the program. The second heuristic incrementally allocates each SPM resident candidate to the SPM based on graph coloring and acyclic graph orientation. We have evaluated our approach by comparing with an ILP-based approach and a longest-path-based greedy approach using the eight benchmarks selected from Powerstone and Mälardalen WCET Benchmark suites under three different SPM configurations. Our approach achieves up to 21% and 43% improvements in WCET reduction over the ILP-based approach and the greedy approach, respectively.

References

[1]

Angiolini, F., Menichelli, F., Ferrero, A., Benini, L., and Olivieri, M. A post-compiler approach to scratchpad mapping of code. In Proceedings of the 2004 International Cconference on Compilers, Architecture and Synthesis for Embedded Systems (2004), pp. 259--267.

Digital Library

[2]

Deverge, J.-F., and Puaut, I. WCET-directed dynamic scratchpad memory allocation of data. In Proceedings of the 19th Euromicro Conference on Real-Time Systems (2007), pp. 179--190.

Digital Library

[3]

Egger, B., Lee, J., and Shin, H. Dynamic scratchpad memory management for code in portable systems with an MMU. ACM Transactions on Embedded Computing Systems 7, 2 (2008), 11:1--11:38.

Digital Library

[4]

Falk, H., and Kleinsorge, J. C. Optimal static WCET-aware scratchpad allocation of program code. In Proceedings of the 46th Annual Design Automation Conference (2009), pp. 732--737.

Digital Library

[5]

Falk, H., Plazar, S., and Theiling, H. Compile-time decided instruction cache locking using worst-case execution paths. In Proceedings of the 5th IEEE/ACM International Conference on Hardware/Software Codesign and System Synthesis (2007), pp. 143--148.

Digital Library

[6]

Francesco, P., Marchal, P., Atienza, D., Benini, L., Catthoor, F., and Mendias, J. M. An integrated hardware/software approach for run-time scratchpad management. In Proceedings of the 41st annual Design Automation Conference (2004), pp. 238--243.

Digital Library

[7]

Goldberg, A., Wang, T., and Zimmermann, D. Applications of feasible path analysis to program testing. In Proceedings of the 1994 ACM SIGSOFT International Symposium on Software Testing and Analysis (1994), pp. 80--94.

Digital Library

[8]

Gustafsson, J., Betts, A., Ermedahl, A., and Lisper, B. The Mälardalen WCET benchmarks -- past, present and future. In Proceedings of the 10th International Workshop on Worst-Case Execution Time Analysis (2010), pp. 137--147.

[9]

Hennessy, J. L., and Patterson, D. A. Computer Architecture: A Quantitative Approach. Morgan Kaufmann Publishers, 2007.

Digital Library

[10]

Janapsatya, A., Ignjatovic, A., and Parameswaran, S. A novel instruction scratchpad memory optimization method based on concomitance metric. In Proceedings of the 2006 Asia and South Pacific Design Automation Conference (2006), pp. 612--617.

Digital Library

[11]

Janapsatya, A., Parameswaran, S., and Ignjatovic, A. Hardware/software managed scratchpad memory for embedded system. In Proceedings of the 2004 IEEE/ACM International Conference on Computer-Aided Design (2004), pp. 370--377.

Digital Library

[12]

Kandemir, M. T., Ramanujam, J., Irwin, M. J., Vijaykrishnan, N., Kadayif, I., and Parikh, A. Dynamic management of scratch-pad memory space. In Proceedings of the 38th annual Design Automation Conference (2001), pp. 690--695.

Digital Library

[13]

Li, L., Feng, H., and Xue, J. Compiler-directed scratchpad memory management via graph coloring. ACM Transactions on Architecture and Code Optimization 6, 3 (2009), 9:1--9:17.

Digital Library

[14]

Li, L., Nguyen, Q. H., and Xue, J. Scratchpad allocation for data aggregates in superperfect graphs. In Proceedings of the 2007 ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (2007), pp. 207--26.

Digital Library

[15]

Li, L., Xue, J., and Knoop, J. Scratchpad memory allocation for data aggregates via interval coloring in superperfect graphs. ACM Transactions on Embedded Computing Systems 10, 2 (2011), 28:1--28:42.

Digital Library

[16]

Li, X., Liang, Y., Mitra, T., and Roychoudhury, A. Chronos: A timing analyzer for embedded software. Science of Computer Programming 69, 1--3 (2007), 56--67.

Digital Library

[17]

Liu, T., Li, M., and Xue, C. J. Minimizing WCET for real-time embedded systems via static instruction cache locking. In Proceedings of the 15th IEEE Symposium on Real-Time and Embedded Technology and Applications (2009), pp. 35--44.

Digital Library

[18]

Palem, K. V., and Simons, B. B. Scheduling time-critical instructions on risc machines. ACM Transactions on Programming Languages and Systems 15, 4 (1993), 632--658.

Digital Library

[19]

Plazar, S., Falk, H., Kleinsorge, J. C., and Marwedel, P. WCET-aware static locking of instruction caches. In Proceedings of the International Symposium on Code Generation and Optimization (2012), pp. 44--52.

Digital Library

[20]

Puaut, I., and Pais, C. Scratchpad memories vs locked caches in hard real-time systems: a quantitative comparison. In Proceedings of the conference on Design, Automation and Test in Europe (2007), pp. 1484--1489.

Digital Library

[21]

Scott, J., Lee, L. H., Arends, J., and Moyer, B. Designing the low-power M*CORE architecture. In Proceedings of IEEE Power Driven Micro Architecture Workshop (1998), pp. 145--150.

[22]

Suhendra, V., Mitra, T., Roychoudhury, A., and Chen, T. WCET centric data allocation to scratchpad memory. In Proceedings of the 26th IEEE International Real-Time Systems Symposium (2005), pp. 223--232.

Digital Library

[23]

Suhendra, V., Mitra, T., Roychoudhury, A., and Chen, T. Efficient detection and exploitation of infeasible paths for software timing analysis. In Proceedings of the 43rd annual Design Automation Conference (2006), pp. 358--363.

Digital Library

[24]

Udayakumaran, S., and Barua, R. Compiler-decided dynamic memory allocation for scratch-pad based embedded systems. In Proceedings of the 2003 International Conference on Compilers, Architecture and Synthesis for Embedded Systems (2003), pp. 276--286.

Digital Library

[25]

Vera, X., Lisper, B., and Xue, J. Data cache locking for higher program predictability. In Proceedings of the 2003 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (2003), pp. 272--282.

Digital Library

[26]

Vera, X., Lisper, B., and Xue, J. Data cache locking for tight timing calculations. ACM Transactions on Embedded Computing Systems 7, 1 (2007), 4:1--4:38.

Digital Library

[27]

Verma, M., and Marwedel, P. Overlay techniques for scratchpad memories in low power embedded processors. IEEE Transactions on Very Large Scale Integration Systems 14, 8 (2006), 802--815.

Digital Library

[28]

Wu, H., Xue, J., and Parameswaran, S. Optimal WCET-aware code selection for scratchpad memory. In Proceedings of the 10th ACM International Conference on Embedded Software (2010), pp. 59--68.

Digital Library

[29]

Yang, X., Wang, L., Xue, J., Deng, Y., and Zhang, Y. Comparability graph coloring for optimizing utilization of stream register files in stream processors. In Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (2009), pp. 111--120.

Digital Library

Cited By

Zheng WWu H(2015)WCET-Aware Dynamic D-cache Locking for A Single TaskACM SIGPLAN Notices10.1145/2808704.275496550:5(1-10)Online publication date: 4-Jun-2015
https://dl.acm.org/doi/10.1145/2808704.2754965
Zheng WWu HNoh SFischmeister SXue J(2015)WCET-Aware Dynamic D-cache Locking for A Single TaskProceedings of the 16th ACM SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems 2015 CD-ROM10.1145/2670529.2754965(1-10)Online publication date: 4-Jun-2015
https://dl.acm.org/doi/10.1145/2670529.2754965
Segarra JCortadella JTejero RVinals-Yufera V(2020)Automatic Safe Data Reuse Detection for the WCET Analysis of Systems With Data CachesIEEE Access10.1109/ACCESS.2020.30321458(192379-192392)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.3032145
Show More Cited By

Index Terms

WCET-aware data selection and allocation for scratchpad memory
1. Computer systems organization
  1. Embedded and cyber-physical systems
  2. Real-time systems
2. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

WCET-aware data selection and allocation for scratchpad memory
LCTES '12: Proceedings of the 13th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, Tools and Theory for Embedded Systems

In embedded systems, SPM (scratchpad memory) is an attractive alternative to cache memory due to its lower energy consumption and higher predictability of program execution. This paper studies the problem of placing variables of a program into an SPM ...
Endurance-Aware Allocation of Data Variables on NVM-Based Scratchpad Memory in Real-Time Embedded Systems
Nonvolatile memory (NVM) has many benefits compared to the traditional static RAM, such as improved reliability and reduced power consumption, but it has long write latency and limited write endurance. Scratchpad memory (SPM) is software-managed small on-...
WCET-Directed Dynamic Scratchpad Memory Allocation of Data
ECRTS '07: Proceedings of the 19th Euromicro Conference on Real-Time Systems

Many embedded systems feature processors coupled with a small and fast scratchpad memory. To the difference with caches, allocation of data to scratchpad memory must be handled by software. The major gain is to enhance the predictability of memory ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 47, Issue 5

LCTES '12

MAY 2012

152 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/2345141

Issue’s Table of Contents

LCTES '12: Proceedings of the 13th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, Tools and Theory for Embedded Systems
June 2012
153 pages
ISBN:9781450312127
DOI:10.1145/2248418
General Chair:
Reinhard Wilhelm
Saarland University Saarbrücken
,
Program Chairs:
Heiko Falk
Ulm University
,
Wang Yi
Uppsala University

Copyright © 2012 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

Publication History

Published: 12 June 2012

Published in SIGPLAN Volume 47, Issue 5

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Australian Research Council

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
324
Total Downloads

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

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zheng WWu H(2015)WCET-Aware Dynamic D-cache Locking for A Single TaskACM SIGPLAN Notices10.1145/2808704.275496550:5(1-10)Online publication date: 4-Jun-2015
https://dl.acm.org/doi/10.1145/2808704.2754965
Zheng WWu HNoh SFischmeister SXue J(2015)WCET-Aware Dynamic D-cache Locking for A Single TaskProceedings of the 16th ACM SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems 2015 CD-ROM10.1145/2670529.2754965(1-10)Online publication date: 4-Jun-2015
https://dl.acm.org/doi/10.1145/2670529.2754965
Segarra JCortadella JTejero RVinals-Yufera V(2020)Automatic Safe Data Reuse Detection for the WCET Analysis of Systems With Data CachesIEEE Access10.1109/ACCESS.2020.30321458(192379-192392)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.3032145
Li JXue JXie XWan QTan QTan L(2018)EpipeJournal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2013.06.00359:10(1383-1393)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.1016/j.sysarc.2013.06.003
Kim YBroman DShrivastava A(2017)WCET-Aware Function-Level Dynamic Code Management on Scratchpad MemoryACM Transactions on Embedded Computing Systems10.1145/306338316:4(1-26)Online publication date: 11-May-2017
https://dl.acm.org/doi/10.1145/3063383
Zheng WWu H(2017)Dynamic Data-Cache Locking for Minimizing the WCET of a Single TaskACM Transactions on Embedded Computing Systems10.1145/299460216:2(1-29)Online publication date: 2-Jan-2017
https://dl.acm.org/doi/10.1145/2994602
Shrivastava ADutt NCai JShoushtari MDonyanavard BTajik H(2016)Automatic management of Software Programmable Memories in Many-core ArchitecturesIET Computers & Digital Techniques10.1049/iet-cdt.2016.002410:6(288-298)Online publication date: 1-Nov-2016
https://doi.org/10.1049/iet-cdt.2016.0024
Zheng WWu HNoh SFischmeister SXue J(2015)WCET-Aware Dynamic D-cache Locking for A Single TaskProceedings of the 16th ACM SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems 2015 CD-ROM10.1145/2670529.2754965(1-10)Online publication date: 4-Jun-2015
https://dl.acm.org/doi/10.1145/2670529.2754965
Wang ZGu ZShao Z(2015)WCET-Aware Energy-Efficient Data Allocation on Scratchpad Memory for Real-Time Embedded SystemsIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2014.237963523:11(2700-2704)Online publication date: Nov-2015
https://doi.org/10.1109/TVLSI.2014.2379635
Wang ZGu ZYao MShao Z(2015)Endurance-Aware Allocation of Data Variables on NVM-Based Scratchpad Memory in Real-Time Embedded SystemsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2015.242284634:10(1600-1612)Online publication date: Oct-2015
https://doi.org/10.1109/TCAD.2015.2422846
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 Issue’s Table of Contents