A Tabu Search Heuristic for Scratch-Pad Memory Management

Maha Idrissi Aouad; René Schott; Olivier Zendra

inria-00491191, version 1

A Tabu Search Heuristic for Scratch-Pad Memory Management

Maha Idrissi Aouad () ¹, René Schott () ^2, 3, Olivier Zendra () ¹

ICSET 2010 - International Conference on Software Engineering and Technology 64 (2010) 386-390

Résumé : 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.

1 : TRIO (INRIA Lorraine - LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
2 : Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
3 : Institut Elie Cartan Nancy (IECN)
CNRS : UMR7502 – INRIA – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)

inria-00491191, version 1
http://hal.inria.fr/inria-00491191
oai:hal.inria.fr:inria-00491191
Contributeur : Maha Idrissi Aouad <>
Soumis le : Jeudi 10 Juin 2010, 17:54:20
Dernière modification le : Mardi 22 Juin 2010, 12:12:20

Voir la fiche détaillée

Documents associés

Texte intégral chez l'éditeur

Exporter

Bibtex EndNote TEI RefWorks

%% inria-00491191, version 1
%% http://hal.inria.fr/inria-00491191
@inproceedings{idrissiaouad:inria-00491191,
    hal_id = {inria-00491191},
    url = {http://hal.inria.fr/inria-00491191},
    title = {{A Tabu Search Heuristic for Scratch-Pad Memory Management}},
    author = {Idrissi Aouad, Maha and Schott, Ren{\'e} and Zendra, Olivier},
    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.},
    language = {Anglais},
    affiliation = {TRIO - INRIA Lorraine - LORIA , Laboratoire Lorrain de Recherche en Informatique et ses Applications - LORIA , Institut Elie Cartan Nancy - IECN},
    booktitle = {{ICSET 2010 - International Conference on Software Engineering and Technology}},
    publisher = {WASET},
    pages = {386-390},
    address = {Rome, Italie},
    organization = {WASET - World Academy of Science, Engineering and Technology},
    volume = {64},
    editor = {WASET },
    audience = {internationale },
    year = {2010},
    month = Apr,
}

%F inria-00491191, version 1
%0 Conference Proceedings
%U http://hal.inria.fr/inria-00491191
%2 INFO:INFO_ES;INFO:INFO_AI;INFO:INFO_PL;MATH:MATH_OC;INFO:INFO_MO
%T A Tabu Search Heuristic for Scratch-Pad Memory Management
%A Idrissi Aouad, Maha
%A Schott, René
%A Zendra, Olivier
%+ TRIO - INRIA Lorraine - LORIA , Laboratoire Lorrain de Recherche en Informatique et ses Applications - LORIA , Institut Elie Cartan Nancy - IECN
%X 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.
%2 B.: Hardware/B.3: MEMORY STRUCTURES/B.3.2: Design Styles/B.3.2.1: Cache memories, B.: Hardware/B.3: MEMORY STRUCTURES/B.3.1: Semiconductor Memories/B.3.1.2: Static memory (SRAM), G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.1: Combinatorics/G.2.1.0: Combinatorial algorithms, 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, D.: Software/D.2: SOFTWARE ENGINEERING/D.2.8: Metrics/D.2.8.1: Performance measures, D.: Software/D.1: PROGRAMMING TECHNIQUES/D.1.0: General
%G Anglais
%8 2010-04-00
%2 internationale
%B ICSET 2010 - International Conference on Software Engineering and Technology
%2 Rome
%2 Italie
%8 2010-04-28
%8 2010-04-30
%2 WASET - World Academy of Science, Engineering and Technology
%E WASET
%I WASET
%V 64
%P 386-390
%2 http://www.waset.org/journals/waset/v64.php
%K Energy consumption, memory allocation management, optimization, Tabu Search heuristic.

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inproceedings"><head>Communications avec actes</head>
<biblStruct type="inproceedings" xml:id="inria-00491191"><analytic>
<author><persName><forename>Maha</forename><surname>Idrissi Aouad</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">TRIO</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>René</forename><surname>Schott</surname></persName>
<affiliation>
<orgName type="laboratory">LORIA</orgName>
<orgName type="team">Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">IECN</orgName>
<orgName type="team">Institut Elie Cartan Nancy</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7502</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>Olivier</forename><surname>Zendra</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">TRIO</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<title type="main" level="a">A Tabu Search Heuristic for Scratch-Pad Memory Management</title></analytic><monogr><meeting>ICSET 2010 - International Conference on Software Engineering and Technology</meeting><imprint><publisher>WASET</publisher><pubPlace><settlement>Rome</settlement><country>Italie</country></pubPlace><biblScope type="publicationDate">2010-04-00</biblScope><biblScope type="vol">64</biblScope><biblScope type="pp">386-390</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00491191</idno></biblStruct>
</listBibl>
</listBibl>