Optimal static WCET-aware scratchpad allocation of program code

ABSTRACT

Caches are notorious for their unpredictability. It is difficult or even impossible to predict if a memory access will result in a definite cache hit or miss. This unpredictability is highly undesired especially when designing real-time systems where the worst-case execution time (WCET) is one of the key metrics. Scratchpad memories (SPMs) have proven to be a fully predictable alternative to caches. In contrast to caches, however, SPMs require dedicated compiler support.

This paper presents an optimal static SPM allocation algorithm for program code. It minimizes WCETs by placing the most beneficial parts of a program's code in an SPM. Our results underline the effectiveness of the proposed techniques. For a total of 73 realistic benchmarks, we reduced WCETs on average by 7.4% up to 40%. Additionally, the run times of our ILP-based SPM allocator are negligible.

REFERENCES

• 1: AbsInt Angewandte Informatik GmbH. aiT: Worst-Case Execution Time Analyzers. www.absint.com/ait, 2009.
• 2: A. M. Campoy, I. Puaut, A. P. Ivars, et al. Cache contents selection for statically-locked instruction caches: An Algorithm Comparison. In Proceedings of ECRTS, Palma de Mallorca, July 2005.
• 3: J.-F. Deverge and I. Puaut. WCET-Directed Dynamic Scratchpad Memory Allocation of Data. In Proceedings of ECRTS, Pisa, July 2007.
• 4: J. Engblom. Static Properties of Commercial Embedded Real-Time Programs, and Their Implication for Worst-Case Execution Time Analysis. In Proceedings of RTAS, Vancouver, 1999.
• 5: H. Falk, P. Lokuciejewski, and H. Theiling. Design of a WCET-Aware C Compiler. In Proceedings of ESTIMedia, Seoul, Oct. 2006. ls12- www.cs.tu-dortmund.de/research/activities/wcc.
• 6: H. Falk, S. Plazar, and H. Theiling. Compile Time Decided Instruction Cache Locking Using Worst-Case Execution Paths. In Proceedings of CODES+ISSS, Salzburg, Oct. 2007.
• 7: C. Lee, M. Potkonjak, and W. H. Mangione-Smith. MediaBench: A Tool for Evaluating and Synthesizing Multimedia and Communications Systems. In Proceedings of MICRO 30, Washington DC, 1997.
• 8: P. Lokuciejewski, D. Cordes, H. Falk, and P. Marwedel. A Fast and Precise Static Loop Analysis based on Abstract Interpretation, Program Slicing and Polytope Models. In Proceedings of CGO, Mar. 2009.
• 9: Mälardalen WCET Research Group. WCET Benchmarks. www.mrtc.mdh.se/projects/wcet, Sept. 2008.
• 10: I. Puaut. WCET-centric Software-controlled Instruction Caches for Hard Real-Time Systems. In Proceedings of ECRTS, July 2006.
• 11: S. Steinke, L. Wehmeyer, B.-S. Lee, et al. Assigning Program and Data Objects to Scratchpad for Energy Reduction. In Proceedings of DATE, Paris, Mar. 2002.
• 12: V. Suhendra, T. Mitra, A. Roychoudhury, et al. WCET Centric Data Allocation to Scratchpad Memory. In Proceedings of RTSS, Miami, Dec. 2005.
• 13: UTDSP Benchmark Suite. www.eecg.toronto.edu/~corinna/DSP/infrastructure/UTDSP.html, Sept. 2008.
• 14: M. Verma and P. Marwedel. Advanced Memory Optimization Techniques for Low-Power Embedded Processors. Springer, 2007.
• 15: V. Živojnović, J. M. Velarde, C. Schläger, and H. Meyr. DSPstone: A DSP-Oriented Benchmarking Methodology. In Proceedings of ICSPAT '94, Dallas, 1994.
• 16: L. Wehmeyer and P. Marwedel. Influence of Onchip Scratchpad Memories on WCET Prediction. In Proceedings of WCET, Catania, June 2004.
• 17: L. Wehmeyer and P. Marwedel. Influence of Memory Hierarchies on Predictability for Time Constrained Embedded Software. In Proceedings of DATE, Munich, Mar. 2005.
• 18: L. Wehmeyer and P. Marwedel. Fast, Efficient and Predictable Memory Accesses -- Optimization Algorithms for Memory Architecture Aware Compilation. Springer, 2006.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

General Terms:
Algorithms, Performance

Keywords:
WCET, scratchpad allocation