Memory Allocation Problems in Embedded Systems- Optimization Method

相似文件 换一批

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

Memory Allocation Problems in Embedded Systems- Optimization Method
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
vi Memory Allocation Problems in Embedded Systems
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
Table of Contents vii
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
viii Memory Allocation Problems in Embedded Systems
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

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏2 回帖

关键词：Optimization ALLOCATION Problems Location Embedded management techniques Software systems Memory