This book provides an overview of and essential insights on invasive computing. Pursuing a comprehensive approach, it addresses proper concepts, invasive language constructs, and the principles of invasive hardware. The main focus is on the important topic of how to map task-parallel applications to future multi-core architectures including 1,000 or more processor units. A special focus today is the question of how applications can be mapped onto such architectures while not only taking into account functional correctness, but also non-functional execution properties such as execution times and security properties.
The book provides extensive experimental evaluations, investigating the benefits of applying invasive computing and hybrid application mapping to give guarantees on non-functional properties such as timing, energy, and security. The techniques in this book are presented in a step-by-step manner, supported by examples and figures. All proposed ideas for providing guarantees on performance, energy consumption, and security are enabled by using the concept of invasive computing and the exclusive usage of resources.
|
|
|
1 | (8) |
|
|
|
3 | (2) |
|
1.1.1 (A) Decentralized Application Mapping |
|
|
3 | (1) |
|
1.1.2 (B) Hybrid Application Mapping |
|
|
4 | (1) |
|
1.1.3 (C) Nonfunctional Properties |
|
|
5 | (1) |
|
|
|
5 | (4) |
|
|
|
6 | (3) |
|
|
|
9 | (36) |
|
2.1 Principles of Invasive Computing |
|
|
9 | (2) |
|
2.2 Invasive Programming Language |
|
|
11 | (8) |
|
2.2.1 Invade, Infect, Retreat, and Claims |
|
|
12 | (1) |
|
2.2.2 Communication-Aware Programming |
|
|
13 | (2) |
|
2.2.3 Actor Model and Nonfunctional Properties |
|
|
15 | (4) |
|
2.3 Overhead Analysis of Invasive Computing |
|
|
19 | (5) |
|
2.3.1 Invasive Speedup and Efficiency Analysis |
|
|
21 | (3) |
|
2.4 Invasive Hardware Architectures |
|
|
24 | (4) |
|
2.4.1 Invasive Tightly Coupled Processor Arrays |
|
|
25 | (2) |
|
2.4.2 The Invasive Core---i-Core |
|
|
27 | (1) |
|
2.4.3 Dynamic Many-Core Met Controller---CiC |
|
|
27 | (1) |
|
2.5 Invasive Network on Chip---i-NoC |
|
|
28 | (6) |
|
|
|
30 | (1) |
|
2.5.2 Invasive Network Adapter---i-NA |
|
|
31 | (2) |
|
2.5.3 Control Network Layer |
|
|
33 | (1) |
|
2.6 Invasive Run-Time and Operating System |
|
|
34 | (1) |
|
|
|
35 | (10) |
|
|
|
39 | (6) |
|
|
|
45 | (12) |
|
|
|
45 | (2) |
|
|
|
47 | (3) |
|
|
|
50 | (1) |
|
|
|
50 | (1) |
|
|
|
51 | (6) |
|
|
|
52 | (3) |
|
|
|
55 | (2) |
|
|
|
57 | (28) |
|
4.1 Self-embedding Algorithm |
|
|
59 | (4) |
|
4.2 Incarnations of Embedding Algorithms |
|
|
63 | (4) |
|
4.2.1 Path Load and Best Neighbor |
|
|
64 | (1) |
|
|
|
65 | (2) |
|
|
|
67 | (1) |
|
|
|
67 | (1) |
|
4.4 Hardware-Based Acceleration for Self-embedding |
|
|
68 | (6) |
|
4.4.1 Application Graph Preprocessing |
|
|
69 | (1) |
|
|
|
70 | (2) |
|
|
|
72 | (1) |
|
|
|
73 | (1) |
|
|
|
74 | (6) |
|
|
|
74 | (1) |
|
|
|
75 | (1) |
|
|
|
76 | (1) |
|
4.5.4 Random Walk with Weighted Probabilities |
|
|
77 | (2) |
|
4.5.5 Hardware-Based Self-embedding |
|
|
79 | (1) |
|
|
|
80 | (1) |
|
|
|
81 | (4) |
|
|
|
82 | (3) |
|
5 Hybrid Application Mapping |
|
|
85 | (52) |
|
|
|
86 | (5) |
|
5.2 Static Performance Analysis |
|
|
91 | (5) |
|
5.2.1 Composable Communication Scheduling |
|
|
92 | (2) |
|
5.2.2 Composable Task Scheduling |
|
|
94 | (2) |
|
5.3 Design Space Exploration |
|
|
96 | (5) |
|
5.3.1 Generation of Feasible Application Mappings |
|
|
98 | (1) |
|
5.3.2 Optimization Objectives and Evaluation |
|
|
99 | (2) |
|
5.4 Run-Time Constraint Solving |
|
|
101 | (10) |
|
|
|
101 | (1) |
|
5.4.2 Run-Time Mapping of Constraint Graphs |
|
|
102 | (3) |
|
5.4.3 Backtracking Algorithm |
|
|
105 | (1) |
|
5.4.4 Run-Time Management and System Requirements |
|
|
106 | (5) |
|
|
|
111 | (16) |
|
5.5.1 Comparison Run-Time Management |
|
|
112 | (2) |
|
5.5.2 MMKP-Based Run-Time Heuristic |
|
|
114 | (3) |
|
5.5.3 Considering Communication Constraints |
|
|
117 | (2) |
|
5.5.4 Objectives Related to Embeddability and Communication |
|
|
119 | (2) |
|
5.5.5 Temporal Isolation Versus Spatial Isolation |
|
|
121 | (2) |
|
|
|
123 | (2) |
|
|
|
125 | (2) |
|
|
|
127 | (5) |
|
5.6.1 Techniques for Static, Dynamic, and Hybrid Application Mapping |
|
|
127 | (1) |
|
5.6.2 Communication Models in Hybrid Application Mapping |
|
|
128 | (4) |
|
|
|
132 | (5) |
|
|
|
133 | (4) |
|
6 Hybrid Mapping for Increased Security |
|
|
137 | (20) |
|
6.1 Hybrid Mapping for Security |
|
|
138 | (4) |
|
|
|
140 | (1) |
|
|
|
141 | (1) |
|
6.2 Shape-Based Design-Time Optimization |
|
|
142 | (3) |
|
|
|
145 | (3) |
|
6.3.1 First-Fit Mapping Heuristic |
|
|
146 | (1) |
|
6.3.2 SAT-Based Run-Time Mapping |
|
|
147 | (1) |
|
|
|
148 | (3) |
|
6.5 Region-Based Run-Time Mapping in the i-NoC |
|
|
151 | (2) |
|
|
|
153 | (1) |
|
|
|
154 | (3) |
|
|
|
154 | (3) |
|
7 Conclusions and Future Work |
|
|
157 | (6) |
|
|
|
157 | (2) |
|
7.2 Future Research Directions |
|
|
159 | (4) |
|
|
|
160 | (3) |
| Index |
|
163 | |
Andreas Weichslgartner is currently working as a software developer at Audi Electronic Ventures GmbH. Before, he had been a researcher at the Department of Computer Science, Friedrich-Alexander University Erlangen-Nürnberg (FAU), Germany, from 2010 to 2017. He received his diploma degree (Dipl.-Ing.) in Information and Communication Technology and his Ph.D. (Dr.-Ing.) in Computer Science from the FAU, Germany, in 2010 and 2017, respectively. His research interests include network on chip, many-core architectures, security, machine learning, and design automation. Stefan Wildermann is a postdoctoral researcher at the Department of Hardware/Software Co-Design at Friedrich-Alexander University Erlangen-Nürnberg (FAU), Germany. He received his Diploma and Doctorate degrees in Computer Science from the FAU in 2006 and 2012. Since 2012, Stefan has been a research assistant, lecturer, and group leader at the FAUs Department of Hardware/SoftwareCo-Design. Michael Glaß is a Professor at the Institute of Embedded Systems/Real-Time Systems, Ulm University, Germany. From 2011 to 2016, he was an assistant professor and head of the System-level Design Automation group at the Department of Hardware/Software Co-Design, Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Germany. He received his Diploma degree and Doctorate degree in Computer Science from the FAU, Germany, in 2006 and 2011, respectively. Michaels main research interests are dependability engineering for embedded systems and system-level design automation, with a particular focus on formal analysis and design space exploration. Jürgen Teich has headed the Department of Hardware/Software Co-Design at Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Germany, since 2003. He received his M.S. degree (Dipl.-Ing. with honors) from the University of Kaiserslautern, Germany in 1989 and his Ph.D. degree (Dr.-Ing., summa cum laude) from the University of Saarland, Germany, in 1993. In 1994, he joined the DSP design group under Prof. E. A. Lee at the Department of Electrical Engineering and Computer Sciences (EECS), University of California at Berkeley (postdoc). From 1995 to 1998, he held a position at the Institute of Computer Engineering and Communications Networks Laboratory (TIK), ETH Zurich, Switzerland. From 1998 to 2002, he was a Full Professor at the Electrical Engineering and Information Technology Department, University of Paderborn, Germany. His current research focuses on the electronic design automation of embedded systems with an emphasis on hardware/software co-design, reconfigurable computing and multi-core systems. Prof. Teich has organized various ACM/IEEE conferences/symposia as Program Chair including CODES+ISSS´07, FPL´08, ASAP´10, and DATE´16. He regularly serves as a TPC member of many program committees. He has also served on the editorial board of journals including IEEE Design & TEST, ACM TODAES and JES, and has edited two textbooks on Hardware/Software Co-Design (Springer).
