Compiler-decided dynamic memory allocation for scratch-pad based embedded systems

ABSTRACT

This paper presents a highly predictable, low overhead and yet dynamic, memory allocation strategy for embedded systems with scratch-pad memory. A scratch-pad is a fast compiler-managed SRAM memory that replaces the hardware-managed cache. It is motivated by its better real-time guarantees vs cache and by its significantly lower overheads in energy consumption, area and overall runtime, even with a simple allocation scheme [4].Existing scratch-pad allocation methods are of two types. First, software-caching schemes emulate the workings of a hardware cache in software. Instructions are inserted before each load/store to check the software-maintained cache tags. Such methods incur large overheads in runtime, code size, energy consumption and SRAM space for tags and deliver poor real-time guarantees just like hardware caches. A second category of algorithms partitionsm variables at compile-time into the two banks. For example, our previous work in [3] derives a provably optimal static allocation for global and stack variables and achieves a speedup over all earlier methods. However, a drawback of such static allocation schemes is that they do not account for dynamic program behavior. It is easy to see why a data allocation that never changes at runtime cannot achieve the full locality benefits of a cache.In this paper we present a dynamic allocation method for global and stack data that for the first time, (i) accounts for changing program requirements at runtime (ii) has no software-caching tags (iii) requires no run-time checks (iv) has extremely low overheads, and (v) yields 100% predictable memory access times. In this method data that is about to be accessed frequently is copied into the SRAM using compiler-inserted code at fixed and infrequent points in the program. Earlier data is evicted if necessary. When compared to a provably optimal static allocation our results show runtime reductions ranging from 11% to 38%, averaging 31.2%, using no additional hardware support. With hardware support for pseudo-DMA and full DMA, which is already provided in some commercial systems, the runtime reductions increase to 33.4% and 34.2% respectively.

REFERENCES

• 1: Andrew W. Appel , Maia Ginsburg, Modern Compiler Implementation in C, Press Syndicate of the University of Cambridge, 1998
• 2: Oren Avissar , Rajeev Barua , Dave Stewart, Heterogeneous memory management for embedded systems, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA [doi>10.1145/502217.502223]
• 3: Oren Avissar , Rajeev Barua , Dave Stewart, An optimal memory allocation scheme for scratch-pad-based embedded systems, ACM Transactions on Embedded Computing Systems (TECS), v.1 n.1, p.6-26, November 2002 [doi>10.1145/581888.581891]
• 4: Rajeshwari Banakar , Stefan Steinke , Bo-Sik Lee , M. Balakrishnan , Peter Marwedel, Scratchpad memory: design alternative for cache on-chip memory in embedded systems, Proceedings of the tenth international symposium on Hardware/software codesign, May 06-08, 2002, Estes Park, Colorado [doi>10.1145/774789.774805]
• 5: L. A. Belady. A study of replacement algorithms for virtual storage. In IBM Systems Journal, pages 5: 78--101, 1966.
• 6: John K. Bennett , John B. Carter , Willy Zwaenepoel, Adaptive software cache management for distributed shared memory architectures, Proceedings of the 17th annual international symposium on Computer Architecture, p.125-134, May 28-31, 1990, Seattle, Washington, United States
• 7: A. Bestavros , R. L. Carter , M. E. Crovella , C. R. Cunha , A. Heddaya , S. A. Mirdad, Application-level document caching in the Internet, Proceedings of the 2nd International Workshop on Services in Distributed and Networked Environments, p.166, June 05-08, 1995
• 8: David Brash. The ARM architecture Version 6 (ARMv6). ARM Ltd., January 2002. White Paper.
• 9: Martin C. Carlisle , Anne Rogers, Software caching and computation migration in Olden, Journal of Parallel and Distributed Computing, v.38 n.2, p.248-255, Nov. 1, 1996 [doi>10.1006/jpdc.1996.0145]
• 10: Document No. ARM DDI 0084D, ARM Ltd. ARM7TDMI-S Data sheet, October 1998.
• 11: Erik G. Hallnor , Steven K. Reinhardt, A fully associative software-managed cache design, Proceedings of the 27th annual international symposium on Computer architecture, p.107-116, June 2000, Vancouver, British Columbia, Canada
• 12: John L. Hennessy , David A. Patterson, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 02
• 13: Chad M. Huneycutt , Joshua B. Fryman , Kenneth M. Mackenzie, Software Caching using Dynamic Binary Rewriting for Embedded Devices, Proceedings of the 2002 International Conference on Parallel Processing (ICPP'02), p.621, August 18-21, 2002
• 14: ILOG Corporation. The CPLEX optimization suite. http://www.ilog.com/products/cplex/, 2001.
• 15: Martin C. Carlisle , Anne Rogers, Software caching and computation migration in Olden, Journal of Parallel and Distributed Computing, v.38 n.2, p.248-255, Nov. 1, 1996 [doi>10.1006/jpdc.1996.0145]
• 16: Mike Tien-Chien Lee , Masahiro Fujita , Vivek Tiwari , Sharad Malik, Power analysis and minimization techniques for embedded DSP software, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.5 n.1, p.123-135, March 1997 [doi>10.1109/92.555992]
• 17: Matlab 6.1. The Math Works, Inc., 2001. http://www.mathworks.com/products/matlab/.
• 18: M. Kandemir , J. Ramanujam , J. Irwin , N. Vijaykrishnan , I. Kadayif , A. Parikh, Dynamic management of scratch-pad memory space, Proceedings of the 38th conference on Design automation, p.690-695, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379049]
• 19: Csaba Andras Moritz , Matthew Frank , Saman P. Amarasinghe, FlexCache: A Framework for Flexible Compiler Generated Data Caching, Revised Papers from the Second International Workshop on Intelligent Memory Systems, p.135-146, November 12, 2000
• 20: CPU12 Reference Manual. Motorola Corporation, 2000. (A 16-bit processor). http://e-www.motorola.com/brdata/PDFDB/MICROCONTROLLERS/16 BIT/68HC12FAMILY/REFMAT/CPU12RM.pdf.
• 21: M-CORE - MMC2001 Reference Manual. Motorola Corporation, 1998. (A 32-bit processor). http://www.motorola.com/SPS/MCORE/infodocumentation.htm.
• 22: Ioannis Schoinas , Babak Falsafi , Alvin R. Lebeck , Steven K. Reinhardt , James R. Larus , David A. Wood, Fine-grain access control for distributed shared memory, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.297-306, October 05-07, 1994, San Jose, California, United States
• 23: Jan Sjodin, Bo Froderberg, and Thomas Lindgren. Allocation of Global Data Objects in On-Chip RAM. Compiler and Architecture Support for Embedded Computing Systems, December 1998.
• 24: Jan Sjödin , Carl von Platen, Storage allocation for embedded processors, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA [doi>10.1145/502217.502221]
• 25: Osman S. Unsal , Raksit Ashok , Israel Koren , C. Mani Krishna , Csaba Andras Moritz, Cool-cache for hot multimedia, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 26: TMS370Cx7x 8-bit microcontroller. Texas Instruments, Revised Feb. 1997. http://www-s.ti.com/sc/psheets/spns034c/spns034c.pdf.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Performance

Keywords:
compiler, embedded systems, memory allocation, scratch-pad