A Tabu Search Heuristic for Scratch-Pad Memory Management

Reducing energy consumption of embedded systems requires careful memory management. It has been shown that Scratch- Pad Memories (SPMs) are low size, low cost, efficient (i.e. energy saving) data structures directly managed at the software level. In this paper, the focus is on heuristic methods for SPMs management. A method is efficient if the number of accesses to SPM is as large as possible and if all available space (i.e. bits) is used. A Tabu Search (TS) approach for memory management is proposed which is, to the best of our knowledge, a new original alternative to the best known existing heuristic (BEH). In fact, experimentations performed on benchmarks show that the Tabu Search method is as efficient as BEH (in terms of energy consumption) but BEH requires a sorting which can be computationally expensive for a large amount of data. TS is easy to implement and since no sorting is necessary, unlike BEH, the corresponding sorting time is saved. In addition to that, in a dynamic perspective where the maximum capacity of the SPM is not known in advance, the TS heuristic will perform better than BEH.

• Maha Idrissi Aouad
• Rene Schott
• Olivier Zendra

• Energy consumption
• memory allocation management
• optimization
• tabu search heuristic.

[1] R. Graybill and R. Melhem, Power aware computing, R. Graybill and
R. Melhem, Eds. Norwell, MA, USA: Kluwer Academic Publishers,
2002.
[2] L. Benini and G. D. Micheli, "System-level power optimization: Techniques
and tools." in ISLPED-99:ACM/IEEE, 1999, pp. 288-293.
[3] A. Tanenbaum, Architecture de l-ordinateur 5e 'edition, P. Education,
Ed., November 2005.
[4] M. Idrissi Aouad and O. Zendra, "A Survey of Scratch-Pad Memory
Management Techniques for low-power and -energy." in 2nd ECOOP
Workshop on Implementation, Compilation, Optimization of Object-
Oriented Languages, Programs and Systems (ICOOOLPS-2007), July
2007.
[5] R. Banakar, S. Steinke, B. Lee, M. Balakrishnan, and P. Marwedel,
"Scratchpad memory: design alternative for cache on-chip memory in
embedded systems," in CODES. New York, NY, USA: ACM Press,
2002, pp. 73-78.
[6] H. Ben Fradj, A. E. Ouardighi, C. Belleudy, and M. Auguin, "Energy
aware memory architecture configuration," vol. 33, no. 3. ACM
SIGARCH Computer Architecture News, 2005, pp. 3-9.
[7] J. Absar and F. Catthoor, "Analysis of scratch-pad and data-cache
performance using statistical methods," in ASP-DAC, 2006, pp. 820-
825.
[8] J. Sj¨odin, B. Fr¨oderberg, and T. Lindgren, "Allocation of global data
objects in on-chip ram," in Workshop on Compiler and Architectural
Support for Embedded Computer Systems. ACM, December 1998.
[9] S. Steinke, L. Wehmeyer, B. Lee, and P. Marwedel, "Assigning program
and data objects to scratchpad for energy reduction." in DATE. IEEE
Computer Society, 2002, p. 409.
[10] U. P. H. Kellerer and D. Pisinger, Knapsack Problems. Springer, Berlin,
Germany, 2004.
[11] M. Gendreau, An introduction to tabu search, e. F. Glover, G. Kochenberger,
Ed. Boston, MA: Kluwer Academic Publishers, 2003, vol. 57.
[12] 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," in WWC -01: Proceedings of the Workload
Characterization, 2001. WWC-4. 2001 IEEE International Workshop.
Washington, DC, USA: IEEE Computer Society, 2001, pp. 3-14.
[13] H. Cass'e and C. Rochange, "OTAWA, Open Tool for Adaptative
WCET Analysis," in Design, Automation and Test in Europe
(Poster session "University Booth") (DATE), Nice, 17/04/07-
19/04/07. http://www.date-conference.com/: DATE, avril 2007,
p. (electronic medium), poster session. (Online). Available:
ftp://ftp.irit.fr/IRIT/TRACES/7722 date2007.pdf
[14] S. Wilton and N. Jouppi, "Cacti: An enhanced cache access and cycle
time model." IEEE Journal of Solid-State Circuits, 1996.