A Tabu Search Heuristic for Scratch-Pad Memory Management

Autor: Maha Idrissi Aouad, René Schott, Olivier ZENDRA
Přispěvatelé: Real time and interoperability (TRIO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Institut Élie Cartan de Nancy (IECN), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), WASET - World Academy of Science, Engineering and Technology, WASET, Idrissi Aouad, Maha, Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)-Institut National de Recherche en Informatique et en Automatique (Inria)
Jazyk: angličtina
Rok vydání: 2010
Předmět:
[INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI]
[INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL]
[MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC]
Tabu Search heuristic
memory allocation management
ACM: B.: Hardware/B.3: MEMORY STRUCTURES/B.3.2: Design Styles/B.3.2.1: Cache memories
ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.1: Combinatorics/G.2.1.0: Combinatorial algorithms
[INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation
[INFO.INFO-ES] Computer Science [cs]/Embedded Systems
[INFO.INFO-PL] Computer Science [cs]/Programming Languages [cs.PL]
ACM: B.: Hardware/B.3: MEMORY STRUCTURES/B.3.1: Semiconductor Memories/B.3.1.2: Static memory (SRAM)
[INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Energy consumption
ACM: I.: Computing Methodologies/I.2: ARTIFICIAL INTELLIGENCE/I.2.8: Problem Solving
Control Methods
and Search/I.2.8.3: Graph and tree search strategies
[INFO.INFO-ES]Computer Science [cs]/Embedded Systems
[INFO.INFO-MO] Computer Science [cs]/Modeling and Simulation
ACM: D.: Software/D.1: PROGRAMMING TECHNIQUES/D.1.0: General
[MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
optimization
ACM: D.: Software/D.2: SOFTWARE ENGINEERING/D.2.8: Metrics/D.2.8.1: Performance measures
Zdroj: ICSET 2010-International Conference on Software Engineering and Technology
ICSET 2010-International Conference on Software Engineering and Technology, WASET-World Academy of Science, Engineering and Technology, Apr 2010, Rome, Italy. pp.386-390
HAL
Popis: 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.
{"references":["R. Graybill and R. Melhem, Power aware computing, R. Graybill and\nR. Melhem, Eds. Norwell, MA, USA: Kluwer Academic Publishers,\n2002.","L. Benini and G. D. Micheli, \"System-level power optimization: Techniques\nand tools.\" in ISLPED-99:ACM/IEEE, 1999, pp. 288-293.","A. Tanenbaum, Architecture de l-ordinateur 5e 'edition, P. Education,\nEd., November 2005.","M. Idrissi Aouad and O. Zendra, \"A Survey of Scratch-Pad Memory\nManagement Techniques for low-power and -energy.\" in 2nd ECOOP\nWorkshop on Implementation, Compilation, Optimization of Object-\nOriented Languages, Programs and Systems (ICOOOLPS-2007), July\n2007.","R. Banakar, S. Steinke, B. Lee, M. Balakrishnan, and P. Marwedel,\n\"Scratchpad memory: design alternative for cache on-chip memory in\nembedded systems,\" in CODES. New York, NY, USA: ACM Press,\n2002, pp. 73-78.","H. Ben Fradj, A. E. Ouardighi, C. Belleudy, and M. Auguin, \"Energy\naware memory architecture configuration,\" vol. 33, no. 3. ACM\nSIGARCH Computer Architecture News, 2005, pp. 3-9.","J. Absar and F. Catthoor, \"Analysis of scratch-pad and data-cache\nperformance using statistical methods,\" in ASP-DAC, 2006, pp. 820-\n825.","J. Sj¨odin, B. Fr¨oderberg, and T. Lindgren, \"Allocation of global data\nobjects in on-chip ram,\" in Workshop on Compiler and Architectural\nSupport for Embedded Computer Systems. ACM, December 1998.","S. Steinke, L. Wehmeyer, B. Lee, and P. Marwedel, \"Assigning program\nand data objects to scratchpad for energy reduction.\" in DATE. IEEE\nComputer Society, 2002, p. 409.\n[10] U. P. H. Kellerer and D. Pisinger, Knapsack Problems. Springer, Berlin,\nGermany, 2004.\n[11] M. Gendreau, An introduction to tabu search, e. F. Glover, G. Kochenberger,\nEd. Boston, MA: Kluwer Academic Publishers, 2003, vol. 57.\n[12] M. R. Guthaus, J. S. Ringenberg, D. Ernst, T. M. Austin, T. Mudge,\nand R. B. Brown, \"Mibench: A free, commercially representative\nembedded benchmark suite,\" in WWC -01: Proceedings of the Workload\nCharacterization, 2001. WWC-4. 2001 IEEE International Workshop.\nWashington, DC, USA: IEEE Computer Society, 2001, pp. 3-14.\n[13] H. Cass'e and C. Rochange, \"OTAWA, Open Tool for Adaptative\nWCET Analysis,\" in Design, Automation and Test in Europe\n(Poster session \"University Booth\") (DATE), Nice, 17/04/07-\n19/04/07. http://www.date-conference.com/: DATE, avril 2007,\np. (electronic medium), poster session. (Online). Available:\nftp://ftp.irit.fr/IRIT/TRACES/7722 date2007.pdf\n[14] S. Wilton and N. Jouppi, \"Cacti: An enhanced cache access and cycle\ntime model.\" IEEE Journal of Solid-State Circuits, 1996."]}
Databáze: OpenAIRE
Externí odkaz: