Memory Allocation Problems in Embedded Systems

Maria Soto, IUT de Vannes, France.Marc Sevaux, University of South Brittany, Lorient, France.André Rossi, University of South Brittany, Lorient, France.Johann Laurent, University of South Brittany, Lorient, France.

• Introduction ixChapter 1. Context 11.1. Embedded systems 21.1.1. Main components of embedded systems 31.2. Memory management for decreasing power consumption, performance and area in embedded systems 41.3. State of the art in optimization techniques for memory management and data assignment 81.3.1. Software optimization 91.3.2. Hardware optimization 111.3.3. Data binding  161.3.3.1. Memory partitioning problem for low energy 171.3.3.2. Constraints on memory bank capacities and number of accesses to variables 181.3.3.3. Using external memory 191.4. Operations research and electronics 211.4.1. Main challenges in applying operations research to electronics 23Chapter 2. Unconstrained Memory Allocation Problem 272.1. Introduction 282.2. An ILP formulation for the unconstrained memory allocation problem 312.3. Memory allocation and the chromatic number 322.3.1. Bounds on the chromatic number 332.4. An illustrative example 352.5. Three new upper bounds on the chromatic number 382.6. Theoretical assessment of three upper bounds 452.7. Computational assessment of three upper bounds 492.8. Conclusion 53Chapter 3. Memory Allocation Problem With Constraint on the Number of Memory Banks 573.1. Introduction 583.2. An ILP formulation for the memory allocation problem with constraint on the number of memory banks 613.3. An illustrative example 643.4. Proposed metaheuristics 653.4.1. A tabu search procedure 663.4.2. A memetic algorithm 693.5. Computational results and discussion 713.5.1. Instances 723.5.2. Implementation 723.5.3. Results 733.5.4. Discussion 753.6. Conclusion 75Chapter 4. General MemoryAllocation Problem 774.1. Introduction 784.2. ILP formulation for the general memory allocation problem 804.3. An illustrative example 844.4. Proposed metaheuristics 854.4.1. Generating initial solutions 864.4.1.1. Random initial solutions 864.4.1.2. Greedy initial solutions 864.4.2. A tabu search procedure 894.4.3. Exploration of neighborhoods 914.4.4. A variable neighborhood search hybridized with a tabu search 934.5. Computational results and discussion 944.5.1. Instances used 954.5.2. Implementation 954.5.3. Results 964.5.4. Discussion 974.5.5. Assessing TabuMemex 1014.6. Statistical analysis 1054.6.1. Post hoc paired comparisons 1064.7. Conclusion 107Chapter 5. Dynamic Memory Allocation Problem 1095.1. Introduction 1105.2. ILP formulation for dynamic memory allocation problem 1135.3. An illustrative example 1165.4. Iterative metaheuristic approaches 1195.4.1. Long-term approach 1195.4.2. Short-term approach 1225.5. Computational results and discussion 1235.5.1. Results 1245.5.2. Discussion 1255.6. Statistical analysis 1285.6.1. Post hoc paired comparisons 1295.7. Conclusion . 130Chapter 6. MemExplorer: Cases Studies 1316.1. The design flow 1316.1.1. Architecture used 1316.1.2. MemExplorer design flow 1326.1.3. Memory conflict graph 1346.2. Example of MemExplorer utilization 139Chapter 7. General Conclusions and Future Work 1477.1. Summary of the memory allocation problem versions 1477.2. Intensification and diversification 1497.2.1. Metaheuristics for memory allocationproblem with constraint on the number of memory banks 1497.2.1.1. Tabu-Allocation 1497.2.1.2. Evo-Allocation 1517.2.2. Metaheuristic for general memory allocation problem 1517.2.3. Approaches for dynamic memory allocation problem 1527.3. Conclusions 1527.4. Future work 1547.4.1. Theoretical perspectives 1547.4.2. Practical perspectives 156Bibliography 159Index 181