Embedded systems are everywhere in contemporary life and are supposed to make our lives more comfortable. In industry, embedded systems are used to manage and control complex systems (e.g. nuclear power plants, telecommunications and flight control) and they are also taking an important place in our daily activities (e.g. smartphones, security alarms and traffic lights). In the design of embedded systems, memory allocation and data assignment are among the main challenges that electronic designers have to face. In fact, they impact heavily on the main cost metrics (power consumption, performance and area) in electronic devices. Thus designers of embedded systems have to pay careful attention in order to minimize memory requirements, thus improving memory throughput and limiting the power consumption by the systems memory. Electronic designers attempt to minimize memory requirements with the aim of lowering the overall system costs. A state of the art of optimization techniques for memory management and data assignment is presented in this book.
Introduction ix
Chapter 1. Context 1
1.1. Embedded systems 2
1.1.1. Main components of embedded systems 3
1.2. Memory management for decreasing power consumption, performance and area in embedded systems 4
1.3. State of the art in optimization techniques for memory management and data assignment 8
1.3.1. Software optimization 9
1.3.2. Hardware optimization 11
1.3.3. Data binding 16
1.3.3.1. Memory partitioning problem for low energy 17
1.3.3.2. Constraints on memory bank capacities and number of accesses to variables 18
1.3.3.3. Using external memory 19
1.4. Operations research and electronics 21
1.4.1. Main challenges in applying operations research to electronics 23
Chapter 2. Unconstrained Memory Allocation Problem 27
2.1. Introduction 28
2.2. An ILP formulation for the unconstrained memory allocation problem 31
2.3. Memory allocation and the chromatic number 32
2.3.1. Bounds on the chromatic number 33
2.4. An illustrative example 35
2.5. Three new upper bounds on the chromatic number 38
2.6. Theoretical assessment of three upper bounds 45
2.7. Computational assessment of three upper bounds 49
2.8. Conclusion 53
Chapter 3. Memory Allocation Problem With Constraint on the Number of Memory Banks 57
3.1. Introduction 58
3.2. An ILP formulation for the memory allocation problem with constraint on the number of memory banks 61
3.3. An illustrative example 64
3.4. Proposed metaheuristics 65
3.4.1. A tabu search procedure 66
3.4.2. A memetic algorithm 69
3.5. Computational results and discussion 71
3.5.1. Instances 72
3.5.2. Implementation 72
3.5.3. Results 73
3.5.4. Discussion 75
3.6. Conclusion 75
Chapter 4. General Memory
Allocation Problem 77
4.1. Introduction 78
4.2. ILP formulation for the general memory allocation problem 80
4.3. An illustrative example 84
4.4. Proposed metaheuristics 85
4.4.1. Generating initial solutions 86
4.4.1.1. Random initial solutions 86
4.4.1.2. Greedy initial solutions 86
4.4.2. A tabu search procedure 89
4.4.3. Exploration of neighborhoods 91
4.4.4. A variable neighborhood search hybridized with a tabu search 93
4.5. Computational results and discussion 94
4.5.1. Instances used 95
4.5.2. Implementation 95
4.5.3. Results 96
4.5.4. Discussion 97
4.5.5. Assessing TabuMemex 101
4.6. Statistical analysis 105
4.6.1. Post hoc paired comparisons 106
4.7. Conclusion 107
Chapter 5. Dynamic Memory Allocation Problem 109
5.1. Introduction 110
5.2. ILP formulation for dynamic memory allocation problem 113
5.3. An illustrative example 116
5.4. Iterative metaheuristic approaches 119
5.4.1. Long-term approach 119
5.4.2. Short-term approach 122
5.5. Computational results and discussion 123
5.5.1. Results 124
5.5.2. Discussion 125
5.6. Statistical analysis 128
5.6.1. Post hoc paired comparisons 129
5.7. Conclusion . 130
Chapter 6. MemExplorer: Cases Studies 131
6.1. The design flow 131
6.1.1. Architecture used 131
6.1.2. MemExplorer design flow 132
6.1.3. Memory conflict graph 134
6.2. Example of MemExplorer utilization 139
Chapter 7. General Conclusions and Future Work 147
7.1. Summary of the memory allocation problem versions 147
7.2. Intensification and diversification 149
7.2.1. Metaheuristics for memory allocation
problem with constraint on the number of memory banks 149
7.2.1.1. Tabu-Allocation 149
7.2.1.2. Evo-Allocation 151
7.2.2. Metaheuristic for general memory allocation problem 151
7.2.3. Approaches for dynamic memory allocation problem 152
7.3. Conclusions 152
7.4. Future work 154
7.4.1. Theoretical perspectives 154
7.4.2. Practical perspectives 156
Bibliography 159
Index 181
