|
|
马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？注册
x
Advanced Memory Optimization Techniques for Low-Power Embedded Processors
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Design of Consumer Oriented Embedded Devices . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 MemoryWall Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2 Memory Hierarchies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.3 Software Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 RelatedWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1 Power and Energy Relationship . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1 Power Dissipation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.2 Energy Consumption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Survey on Power and Energy Optimization Techniques . . . . . . . . . . . . . . . . . 11
2.2.1 Power vs. Energy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.2 Processor Energy Optimization Techniques . . . . . . . . . . . . . . . . . . . . 12
2.2.3 Memory Energy Optimization Techniques . . . . . . . . . . . . . . . . . . . . . 14
3 Memory Aware Compilation and Simulation Framework . . . . . . . . . . . . . . . . . 17
3.1 Uni-Processor ARM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.1.1 Energy Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.2 Compilation Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.1.3 Instruction Cache Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.4 Simulation and Evaluation Framework . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2 Multi-Processor ARM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2.1 Energy Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.2 Compilation Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3 M5 DSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4 Non-Overlayed Scratchpad Allocation Approaches
for Main / Scratchpad Memory Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
ix
x Contents
4.3 RelatedWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.4 Problem Formulation and Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.4.1 Memory Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.4.2 Energy Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.4.3 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.5 Non-Overlayed Scratchpad Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.5.1 Optimal Non-Overlayed Scratchpad Allocation . . . . . . . . . . . . . . . . . 39
4.5.2 Fractional Scratchpad Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.6 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.6.1 Uni-Processor ARM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.6.2 Multi-Processor ARM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.6.3 M5 DSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5 Non-Overlayed Scratchpad Allocation Approaches for
Main / Scratchpad + Cache Memory Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.2 RelatedWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.3 Motivating Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.3.1 Base Configuration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.3.2 Non-Overlayed Scratchpad Allocation Approach . . . . . . . . . . . . . . . . 55
5.3.3 Loop Cache Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.3.4 Cache Aware Scratchpad Allocation Approach . . . . . . . . . . . . . . . . . . 57
5.4 Problem Formulation and Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.4.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.4.2 Memory Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.4.3 Cache Model (Conflict Graph) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.4.4 Energy Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.4.5 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.5 Cache Aware Scratchpad Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.5.1 Optimal Cache Aware Scratchpad Allocation . . . . . . . . . . . . . . . . . . . 65
5.5.2 Near-Optimal Cache Aware Scratchpad Allocation . . . . . . . . . . . . . . 67
5.6 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.6.1 Uni-Processor ARM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.6.2 Comparison of Scratchpad and Loop Cache Based Systems . . . . . . . 78
5.6.3 Multi-Processor ARM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6 Scratchpad Overlay Approaches for Main / Scratchpad
Memory Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.2 Motivating Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.3 RelatedWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.4 Problem Formulation and Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.4.2 Memory Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
Contents xi
6.4.3 Liveness Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
6.4.4 Energy Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.4.5 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.5 Scratchpad Overlay Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.5.1 Optimal Memory Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.5.2 Optimal Address Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
6.5.3 Near-Optimal Address Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.6 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
6.6.1 Uni-Processor ARM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
6.6.2 Multi-Processor ARM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
6.6.3 M5 DSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
7 Data Partitioning and Loop Nest Splitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
7.2 RelatedWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
7.3 Problem Formulation and Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
7.3.1 Partitioning Candidate Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
7.3.2 Splitting Point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
7.3.3 Memory Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
7.3.4 Energy Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
7.3.5 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
7.4 Data Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
7.4.1 Integer Linear Programming Formulation . . . . . . . . . . . . . . . . . . . . . . 131
7.5 Loop Nest Splitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
7.6 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
7.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
8 Scratchpad Sharing Strategies for Multiprocess Applications . . . . . . . . . . . . . . 141
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
8.2 Motivating Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
8.3 RelatedWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
8.4 Preliminaries for Problem Formulation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
8.4.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
8.4.2 System Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
8.4.3 Memory Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
8.4.4 Energy Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
8.5 Scratchpad Non-Saving/Restoring Context Switch (Non-Saving)
Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
8.5.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
8.5.2 Algorithm for Non-Saving Approach . . . . . . . . . . . . . . . . . . . . . . . . . . 149
8.6 Scratchpad Saving/Restoring Context Switch (Saving) Approach . . . . . . . . . 152
8.6.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
8.6.2 Algorithm for Saving Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
8.7 Hybrid Scratchpad Saving/Restoring Context Switch (Hybrid) Approach . . 156
8.7.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
xii Contents
8.7.2 Algorithm for Hybrid Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
8.8 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
8.9 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
8.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
9 Conclusions and Future Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
9.1 Research Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
9.2 Future Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
A Theoretical Analysis for Scratchpad Sharing Strategies . . . . . . . . . . . . . . . . . . . 171
A.1 Formal Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
A.2 Correctness Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 |
|
/2 
eetop公众号
创芯大讲堂
创芯人才网
发表于 2008-10-22 16:03:25
楼主
