A Tabu Search Heuristic for Scratch-Pad Memory Management

Authors: Maha Idrissi Aouad, Rene Schott, Olivier Zendra

Abstract:

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.

Keywords: Energy consumption, memory allocation management, optimization, tabu search heuristic.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1084946

References:

[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.