Fast, efficient and predictable memory accesses : optimization algorithms for memory architecture aware compilation

the Memory System Is Increasingly Turning Into A Bottleneck In The Design Of Embedded Systems. The Speed Improvements Of Memory Systems Are Lower Than The Speed Improvements Of Processors, Eventually Leading To Embedded Systems Whose Performance Is Limited By The Memory. This Problem Is Known As The Memory Wall Problem. Furthermore, Memory Systems May Consume The Largest Share Of The System’s Energy Budget And May Be The Source Of Unpredictable Timing Behaviour. Hence, The Design Of The Memory System Deserves An Increasing Amount Of Attention. fast, Efficient And Predictable Memory Accesses Presents Techniques For Designing Fast, Energy-efficient And Timing Predictable Memory Systems. By Using A Careful Combination Of Compiler Optimizations And Architectural Improvements, We Can Achieve More Than What Would Be Feasible At One Of The Levels In Isolation. The Described Optimization Algorithms Achieve The Goals Of High Performance And Low Energy Consumption. In Addition To These Benefits, The Use Of Scratchpad Memories Significantly Improves The Timing Predictability Of The Entire System, Leading To Tighter Worst Case Execution Time Bounds (wcet). The Wcet Is A Relevant Design Parameter For All Timing Critical Systems. In Addition, The Book Covers Algorithms To Exploit The Power Down Modes Of Main Memories In Sdram Technology, As Well As The Execute-in-place Feature Of Flash Memories. The Final Chapter Considers The Impact Of The Register File, Which Is Also Part Of The Memory Hierarchy. Contents......Page 6 Acknowledgements......Page 9 1 Abstract......Page 10 2 Introduction......Page 12 2.1 Motivation......Page 14 2.2 Contributions of this Work......Page 20 2.3 Overview......Page 22 3 Models and Tools......Page 24 3.1 Instruction Set Architecture Model......Page 26 3.2 Memory Models......Page 27 3.2.1 SRAM......Page 28 3.2.2 DRAM......Page 30 3.2.3 Flash Memory......Page 33 3.2.4 Caches......Page 34 3.3.1 Processor and Instruction Timing......Page 38 3.3.2 Memory Timing......Page 40 3.4 Energy Models......Page 45 3.4.1 Sources of Energy Dissipation......Page 46 3.4.2 Processor Energy......Page 49 3.4.3 Memory Energy......Page 54 3.5.1 Processor Simulation Model......Page 70 3.5.2 Memory Simulation Model......Page 75 3.6 The encc Compiler Framework......Page 84 3.6.1 Workflow......Page 86 3.6.2 enprofiler......Page 90 3.6.3 Memory Architecture Aware Compilation......Page 91 4 Scratchpad Memory Optimizations......Page 98 4.1 Related Work......Page 99 4.2 Multi Memory Optimization......Page 106 4.2.1 Memory Objects......Page 108 4.2.2 Prerequisites......Page 109 4.2.3 Energy Functions......Page 110 4.2.4 The Base model......Page 111 4.2.5 The Top-Down Model......Page 113 4.2.6 The Bottom-Up Model......Page 120 4.2.7 The ARM TCM Model......Page 124 4.2.8 Leakage-Energy Aware Memory Configuration......Page 126 4.2.9 Results for Multi Memory Optimization......Page 129 4.3 Impact of Scratchpad Allocation Techniques on WCET......Page 145 4.3.1 Related Work......Page 149 4.3.2 Tools and Workflow......Page 151 4.3.3 Required Annotation Information......Page 154 4.3.4 Benchmarks and Memory Hierarchy Configuration......Page 160 4.3.5 WCET Results for Static Allocation......Page 161 4.3.6 WCET Results for Dynamic Allocation......Page 170 5 Main Memory Optimizations......Page 179 5.1 Related Work......Page 180 5.2 Main Memory Power Management......Page 182 5.2.1 Motivating Example......Page 185 5.2.2 Prerequisites......Page 186 5.2.3 Memory Objects and Energy Functions......Page 187 5.2.4 Binary Decision Variables......Page 190 5.2.6 Constraints......Page 192 5.2.7 Results for Main Memory Power Management......Page 194 5.3 Execute-In-Place using Flash Memories......Page 200 5.3.1 Analysis of the Copy Function......Page 202 5.3.2 Main Memory Partitioning......Page 203 5.3.3 Prerequisites......Page 205 5.3.4 Preselection of Memory Objects to enable Deep Power Down......Page 207 5.3.5 Formalization of the Preselection Algorithm......Page 211 5.3.6 Formalization of the XIP Allocation Problem......Page 212 5.3.7 Results for XIP......Page 215 6 Register File Optimization......Page 225 6.1 Related Work......Page 226 6.2 Implementation of the Register File......Page 227 6.3 Register Allocation and Lifetime Analysis......Page 228 6.4 Workflow and Methodology......Page 230 6.5.1 Results for the Ratio of Spill Code to Total Code Size......Page 232 6.5.2 Results for the Number of Cycles......Page 234 6.5.3 Results for Energy Consumption......Page 237 6.6 Compiler Guided Choice of Register File Size......Page 238 7 Summary......Page 241 8 Future Work......Page 247 References......Page 250 C......Page 261 T......Page 262 X......Page 263 "This book presents techniques for designing fast, energy-efficient and timing predictable memory systems. By using a careful combination of compiler optimizations and architectural improvements, we can achieve more than what would be feasible at one of the levels in isolation. The described optimization algorithms achieve the goals of high performance and low energy consumption. In addition to these benefits, the use of scratchpad memories significantly improves the timing predictability of the entire system, leading to tighter worst case execution time bounds (WCET)."--Résumé de l'éditeur "This book presents techniques for designing fast, energy-efficient and timing predictable memory systems. By using a careful combination of compiler optimizations and architectural improvements, we can achieve more than what would be feasible at one of the levels in isolation. The described optimization algorithms achieve the goals of high performance and low energy consumption. In addition to these benefits, the use of scratchpad memories significantly improves the timing predictability of the entire system, leading to tighter worst case execution time bounds (WCET)."--Jacket Speed improvements in memory systems have not kept pace with the speed improvements of processors, leading to embedded systems whose performance is limited by the memory. This book presents design techniques for fast, energy-efficient and timing-predictable memory systems that achieve high performance and low energy consumption. In addition, the use of scratchpad memories significantly improves the timing predictability of the entire system, leading to tighter worst case execution time bounds.