Available:*
Library | Item Barcode | Call Number | Material Type | Item Category 1 | Status |
---|---|---|---|---|---|
Searching... | 30000010324809 | TK7895.E42 M46 2013 | Open Access Book | Book | Searching... |
On Order
Summary
Summary
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 system's 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.
Author Notes
Mara Soto, University of Technology of Troyes, 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
Table of Contents
Introduction | p. ix |
Chapter 1 Context | p. 1 |
1.1 Embedded systems | p. 2 |
1.1.1 Main components of embedded systems | p. 3 |
1.2 Memory management for decreasing power consumption, performance and area in embedded systems | p. 4 |
1.3 State of the art in optimization techniques for memory management and data assignment | p. 8 |
1.3.1 Software optimization | p. 9 |
1.3.2 Hardware optimization | p. 11 |
1.3.3 Data binding | p. 16 |
1.3.3.1 Memory partitioning problem for low energy | p. 17 |
1.3.3.2 Constraints on memory bank capacities and number of accesses to variables | p. 18 |
1.3.3.3 Using external memory | p. 19 |
1.4 Operations research and electronics | p. 21 |
1.4.1 Main challenges in applying operations research to electronics | p. 23 |
Chapter 2 Unconstrained Memory Allocation Problem | p. 27 |
2.1 Introduction | p. 28 |
2.2 An ILP formulation for the unconstrained memory allocation problem | p. 31 |
2.3 Memory allocation and the chromatic number | p. 32 |
2.3.1 Bounds on the chromatic number | p. 33 |
2.4 An illustrative example | p. 35 |
2.5 Three new upper bounds on the chromatic number | p. 38 |
2.6 Theoretical assessment of three upper bounds | p. 45 |
2.7 Computational assessment of three upper bounds | p. 49 |
2.8 Conclusion | p. 53 |
Chapter 3 Memory Allocation Problem With Constraint on the Number of Memory Banks | p. 57 |
3.1 Introduction | p. 58 |
3.2 An ILP formulation for the memory allocation problem with constraint on the number of memory banks | p. 61 |
3.3 An illustrative example | p. 64 |
3.4 Proposed metaheuristics | p. 65 |
3.4.1 A tabu search procedure | p. 66 |
3.4.2 A memetic algorithm | p. 69 |
3.5 Computational results and discussion | p. 71 |
3.5.1 Instances | p. 72 |
3.5.2 Implementation | p. 72 |
3.5.3 Results | p. 73 |
3.5.4 Discussion | p. 75 |
3.6 Conclusion | p. 75 |
Chapter 4 General Memory Allocation Problem | p. 77 |
4.1 Introduction | p. 78 |
4.2 ILP formulation for the general memory allocation problem | p. 80 |
4.3 An illustrative example | p. 84 |
4.4 Proposed metaheuristics | p. 85 |
4.4.1 Generating initial solutions | p. 86 |
4.4.1.1 Random initial solutions | p. 86 |
4.4.1.2 Greedy initial solutions | p. 86 |
4.4.2 A tabu search procedure | p. 89 |
4.4.3 Exploration of neighborhoods | p. 91 |
4.4.4 A variable neighborhood search hybridized with a tabu search | p. 93 |
4.5 Computational results and discussion | p. 94 |
4.5.1 Instances used | p. 95 |
4.5.2 Implementation | p. 95 |
4.5.3 Results | p. 96 |
4.5.4 Discussion | p. 97 |
4.5.5 Assessing TabuMemex | p. 101 |
4.6 Statistical analysis | p. 105 |
4.6.1 Post hoc paired comparisons | p. 106 |
4.7 Conclusion | p. 107 |
Chapter 5 Dynamic Memory Allocation Problem | p. 109 |
5.1 Introduction | p. 110 |
5.2 ILP formulation for dynamic memory allocation problem | p. 113 |
5.3 An illustrative example | p. 116 |
5.4 Iterative metaheuristic approaches | p. 119 |
5.4.1 Long-term approach | p. 119 |
5.4.2 Short-term approach | p. 122 |
5.5 Computational results and discussion | p. 123 |
5.5.1 Results | p. 124 |
5.5.2 Discussion | p. 125 |
5.6 Statistical analysis | p. 128 |
5.6.1 Post hoc paired comparisons | p. 129 |
5.7 Conclusion | p. 130 |
Chapter 6 MemExplorer: Cases Studies | p. 131 |
6.1 The design flow | p. 131 |
6.1.1 Architecture used | p. 131 |
6.1.2 MemExplorer design flow | p. 132 |
6.1.3 Memory conflict graph | p. 134 |
6.2 Example of MemExplorer utilization | p. 139 |
Chapter 7 General Conclusions and Future Work | p. 147 |
7.1 Summary of the memory allocation problem versions | p. 147 |
7.2 Intensification and diversification | p. 149 |
7.2.1 Metaheuristics for memory allocation problem with constraint on the number of memory banks | p. 149 |
7.2.1.1 Tabu-Allocation | p. 149 |
7.2.1.2 Evo-Allocation | p. 151 |
7.2.2 Metaheuristic for general memory allocation problem | p. 151 |
7.2.3 Approaches for dynamic memory allocation problem | p. 152 |
7.3 Conclusions | p. 152 |
7.4 Future work | p. 154 |
7.4.1 Theoretical perspectives | p. 154 |
7.4.2 Practical perspectives | p. 156 |
Bibliography | p. 159 |
Index | p. 181 |