Given the widespread use of real-time multitasking systems, there are tremendous optimization opportunities if reconfigurable computing can be effectively incorporated while maintaining performance and other design constraints of typical applications. The focus of this book is to describe the dynamic reconfiguration techniques that can be safely used in real-time systems. This book provides comprehensive approaches by considering synergistic effects of computation, communication as well as storage together to significantly improve overall performance, power, energy and temperature.
This book describes the challenges in performing dynamic reconfigurations in real-time systems. It shows how to design efficient support architectures—including dynamic cache reconfiguration, hardware/software partitioning and task mapping and scheduling.
|
|
|
1 | (14) |
|
|
|
1 | (3) |
|
|
|
4 | (2) |
|
1.3 Optimization in Embedded Systems |
|
|
6 | (2) |
|
1.4 Opportunities and Challenges |
|
|
8 | (3) |
|
1.4.1 Dynamic Reconfiguration Techniques |
|
|
9 | (1) |
|
1.4.2 Potential Optimization Opportunities |
|
|
9 | (1) |
|
|
|
10 | (1) |
|
|
|
11 | (4) |
|
2 Modeling of Real-Time and Reconfigurable Systems |
|
|
15 | (8) |
|
|
|
15 | (1) |
|
|
|
16 | (3) |
|
2.2.1 Processor Energy Model |
|
|
16 | (1) |
|
|
|
17 | (1) |
|
2.2.3 Main Memory Energy Model |
|
|
18 | (1) |
|
|
|
18 | (1) |
|
|
|
19 | (1) |
|
|
|
19 | (3) |
|
|
|
20 | (2) |
|
|
|
22 | (1) |
|
|
|
22 | (1) |
|
3 Dynamic Cache Reconfiguration in Real-Time Systems |
|
|
23 | (40) |
|
|
|
24 | (3) |
|
3.1.1 Caches in Real-Time Systems |
|
|
24 | (1) |
|
3.1.2 Reconfigurable Cache Architectures |
|
|
25 | (1) |
|
3.1.3 Cache Tuning Techniques |
|
|
26 | (1) |
|
3.2 SACR: Scheduling-Aware Cache Reconfiguration |
|
|
27 | (13) |
|
|
|
27 | (1) |
|
3.2.2 Phase-Based Optimal Cache Selection |
|
|
28 | (5) |
|
3.2.3 Statically Scheduled Systems |
|
|
33 | (1) |
|
3.2.4 Dynamically Scheduled Systems |
|
|
33 | (6) |
|
3.2.5 Impact of Storing Multiple Cache Configurations |
|
|
39 | (1) |
|
3.3 Design Space Exploration for Two-Level Cache Reconfiguration |
|
|
40 | (5) |
|
3.3.1 Exhaustive Exploration |
|
|
41 | (1) |
|
3.3.2 Same Level One Cache Tuning: SLOT |
|
|
42 | (1) |
|
3.3.3 Two-Step Tuning: TST |
|
|
42 | (1) |
|
3.3.4 Independent Level One Cache Tuning: ILOT |
|
|
43 | (1) |
|
3.3.5 Interlaced Tuning: ILT |
|
|
44 | (1) |
|
|
|
45 | (16) |
|
|
|
45 | (1) |
|
|
|
46 | (11) |
|
|
|
57 | (4) |
|
|
|
61 | (2) |
|
4 Energy Optimization of Cache Hierarchy in Multicore Real-Time Systems |
|
|
63 | (22) |
|
|
|
64 | (1) |
|
4.2 Background and Motivation |
|
|
64 | (4) |
|
|
|
65 | (1) |
|
|
|
66 | (2) |
|
4.3 Dynamic Cache Reconfiguration and Partitioning |
|
|
68 | (11) |
|
4.3.1 Problem Formulation |
|
|
68 | (1) |
|
|
|
69 | (1) |
|
|
|
70 | (2) |
|
|
|
72 | (4) |
|
4.3.5 Varying Cache Partitioning Scheme |
|
|
76 | (2) |
|
4.3.6 Gated-Vdd Shared Cache Lines |
|
|
78 | (1) |
|
|
|
79 | (5) |
|
|
|
79 | (1) |
|
|
|
79 | (1) |
|
|
|
80 | (1) |
|
4.4.4 Task Mapping Effect |
|
|
81 | (2) |
|
4.4.5 Effect of Varying Cache Partitioning |
|
|
83 | (1) |
|
4.4.6 Gated-Vdd Cache Lines Effect |
|
|
83 | (1) |
|
|
|
84 | (1) |
|
5 Energy-Aware Scheduling with Dynamic Voltage Scaling |
|
|
85 | (44) |
|
|
|
86 | (2) |
|
5.2 PreDVS: Preemptive Dynamic Voltage Scaling |
|
|
88 | (17) |
|
|
|
88 | (1) |
|
5.2.2 Problem Formulation |
|
|
89 | (2) |
|
5.2.3 Approximation Scheme |
|
|
91 | (11) |
|
5.2.4 Efficient PreDVS Heuristics |
|
|
102 | (3) |
|
5.3 DSR: Dynamic Slack Reclamation |
|
|
105 | (9) |
|
|
|
105 | (1) |
|
5.3.2 Dynamic Slack Reclamation Algorithm |
|
|
106 | (6) |
|
|
|
112 | (2) |
|
|
|
114 | (12) |
|
|
|
114 | (6) |
|
|
|
120 | (6) |
|
|
|
126 | (3) |
|
6 System-Wide Energy Optimization with DVS and DCR |
|
|
129 | (36) |
|
|
|
130 | (1) |
|
6.2 System-Wide Leakage-Aware DVS and DCR |
|
|
131 | (11) |
|
6.2.1 Power Estimation Framework |
|
|
132 | (1) |
|
6.2.2 Two-Level Cache Tuning Heuristic |
|
|
133 | (1) |
|
|
|
134 | (5) |
|
6.2.4 Real-Time Voltage Scaling and Cache Reconfiguration |
|
|
139 | (2) |
|
|
|
141 | (1) |
|
6.3 A General Dynamic Reconfiguration Algorithm |
|
|
142 | (7) |
|
|
|
142 | (1) |
|
|
|
143 | (6) |
|
|
|
149 | (12) |
|
6.4.1 System-Wide Energy Optimization |
|
|
149 | (5) |
|
6.4.2 General Algorithm for Dynamic Reconfiguration |
|
|
154 | (7) |
|
|
|
161 | (4) |
|
7 Temperature- and Energy-Constrained Scheduling |
|
|
165 | (28) |
|
|
|
166 | (1) |
|
|
|
167 | (2) |
|
|
|
169 | (1) |
|
7.4 TCEC Modeling with Timed Automaton |
|
|
170 | (3) |
|
|
|
170 | (1) |
|
7.4.2 Modeling with Extended Timed Automata |
|
|
170 | (3) |
|
7.5 Approximation Algorithm for TCEC Scheduling |
|
|
173 | (11) |
|
|
|
173 | (1) |
|
|
|
173 | (3) |
|
7.5.3 An Exact Algorithm for MCP |
|
|
176 | (2) |
|
7.5.4 Approximation Algorithm |
|
|
178 | (6) |
|
|
|
184 | (2) |
|
|
|
186 | (6) |
|
|
|
186 | (1) |
|
7.7.2 TCEC Versus TC or EC |
|
|
186 | (2) |
|
7.7.3 TCEC with UPPAAL Model Checker |
|
|
188 | (1) |
|
7.7.4 TCEC Using Approximation Algorithm |
|
|
189 | (3) |
|
|
|
192 | (1) |
|
|
|
193 | (4) |
|
|
|
193 | (1) |
|
|
|
194 | (3) |
| Appendix Acknowledgments of Copyrighted Materials |
|
197 | (2) |
| References |
|
199 | (10) |
| About the Authors |
|
209 | (2) |
| Index |
|
211 | |
WeixunWang is a software engineer in Amazon.com, Seattle,WA. He received his B.E. degree in software engineering from the Software Institute, Nanjing University, China, in 2007, and a Ph.D. degree in computer engineering from the University of Florida in 2011. His research interests include energy-aware computing, design automation of embedded systems, computer architecture, reconfigurable architectures and real-time scheduling. He has published more than 10 papers in these fields. He is a member of IEEE.
Prabhat Mishra is an Associate Professor in the Department of Computer and Information Science and Engineering (CISE) at the University of Florida. His research interests include design automation of embedded systems, hardware/software verification, VLSI CAD, and low-power reconfigurable architectures. He received his B.E. from Jadavpur University, Kolkata, in 1994, M.Tech. from the Indian Institute of Technology, Kharagpur in 1996, and Ph.D. from the University of California, Irvine, in 2004 all in Computer Science. Prior to joining University of Florida, he spent several years in various semiconductor and design automation companies, including Intel, Motorola, Synopsys and Texas Instruments. He has published two books (Springer 2005 and MK 2008), nine book chapters and more than 80 research articles in premier journals and conferences. His research has been recognized by several awards including the NSF CAREER Award from the National Science Foundation, two best paper awards (VLSI Design 2011 and CODES+ISSS 2003), several best paper award nominations, and 2004 EDAA Outstanding Dissertation Award from the European Design Automation Association. He has also received the 2007 International Educator of the Year Award from the UF College of Engineering for his significant international research and teaching contributions. He currently serves as an Associate Editor of IEEE Design & Test of Computers (D&T), Guest Editor of IEEE Transactionson Computers (TC), the Information Director of ACM Transactions on Design Automation of Electronic Systems (TODAES), and as a program/organizing committee member of several ACM and IEEE conferences including ICCAD, DATE, ASPDAC, CODES+ISSS, and VLSI Design. He has also served as General Chair of IEEE High Level Design Validation and Test (HLDVT) 2010, Program Chair of HLDVT 2009, and Guest Editor of IEEE Design & Test of Computers (D&T), Journal of Electronic Testing (JETTA) and International Journal of Parallel Programming (IJPP). He is a senior member of ACM and a senior member of IEEE.
Sanjay Ranka is a Professor in the Department of Computer Information Science and Engineering at University of Florida. His current research interests are energy efficient computing, high performance computing, data mining and informatics. Most recently he was the Chief Technology Officer at Paramark where he developed real-time optimization software for optimizing marketing campaigns. Sanjay has also held positions as a tenured faculty member at Syracuse University and as a researcher/visitor at IBM T.J. Watson Research Labs and Hitachi America Limited. Sanjay earned his Ph.D. (Computer Science) from the University of Minnesota and a B. Tech. in Computer Science from IIT, Kanpur, India. He has coauthored two books: Elements of Neural Networks (MIT Press) and Hypercube Algorithm (Springer Verlag), 75 journal articles and 125 refereed conference articles. His recent work has received a student best paper award at ACM-BCB 2010, best paper runner up award at KDD-2009, a nomination for the Robbins Prize for the best paper in journal of Physics in Medicine and Biology for 2008, and a best paper award at ICN 2007. He is a fellow of the IEEE and AAAS and a member of IFIP Committee on System Modeling and Optimization. He is the associate Editor-in-Chief of the Journal of Parallel and Distributed Computing and an associate editor for IEEE Transactions onParallel and Distributed Computing, IEEE Transactions on Computers, Sustainable Computing: Systems and Informatics, Knowledge and Information Systems, and International Journal of Computing. He was a past member of the Parallel Compiler Runtime Consortium, the Message Passing Initiative Standards Committee and Technical Committee on Parallel Processing. He was the program chair for 2010 International Conference on Contemporary Computing and co-general chair for 2009 International Conference on Data Mining and 2010 International Conference on Green Computing.
