Modeling and Optimization of Parallel and Distributed Embedded Systems

Content: 11.1 Related Work 295 --
11.2 Multicore Architectures and Benchmarks 296 --
11.2.1 Multi-Core Architectures 296 --
11.2.2 Benchmark Applications and Kernels 298 --
11.3 Parallel Computing Device Metrics 299 --
11.4 Results 301 --
11.4.1 Quantitative Comparison of SMPs and TMAs 302 --
11.4.2 Benchmark-Driven Results for SMPs 304 --
11.4.3 Benchmark-Driven Results for TMAs 304 --
11.4.4 Comparison of SMPs and TMAs 313 --
11.5 Chapter Summary 316 --
12 High-Performance Optimizations on Tiled Manycore Embedded Systems: A Matrix Multiplication Case Study 317 --
12.1 Related Work 320 --
12.1.1 Performance Analysis and Optimization 320 --
12.1.2 Parallelized MM Algorithms 321 --
12.1.3 Cache Blocking 322 --
12.1.4 Tiled Many-Core Architectures 322 --
12.2 Tiled Many-Core Architecture (TMA) Overview 324 --
12.2.1 Intel's TeraFLOPS Research Chip 324 --
12.2.2 IBM's Cyclops-64 (C64) 326 --
12.2.3 Tilera's TILEPro64 328 --
12.2.4 Tilera's TILE64 332 --
12.3 Parallel ComputingMetrics and Matrix Multiplication (MM) Case Study 332 --
12.3.1 Parallel ComputingMetrics for TMAs 332 --
12.3.2 Matrix Multiplication (MM) Case Study 334 --
12.4 Performance Optimization on a Many-Core Architecture 335 --
12.4.1 Performance Optimization on a Single Tile 335 --
12.4.2 Parallel Performance Optimizations 336 --
12.4.3 Compiler-Based Optimizations 341 --
12.5 Results 344 --
12.5.1 Data Allocation, Data Decomposition, Data Layout, and Communication 346 --
12.5.2 Performance Optimizations on a Single Tile 349 --
12.5.3 Parallel Performance Optimizations 356 --
12.6 Chapter Summary 364 --
13 Conclusions 369 --
Index 395. 8.3 Application Specific Embedded Sensor Node Tuning Formulation as an MDP 219 --
8.3.1 State Space 219 --
8.3.2 Decision Epochs and Actions 219 --
8.3.3 State Dynamics 220 --
8.3.4 Policy and Performance Criterion 220 --
8.3.5 Reward Function 221 --
8.3.6 Optimality Equation 224 --
8.3.7 Policy Iteration Algorithm 224 --
8.4 Implementation Guidelines and Complexity 225 --
8.4.1 Implementation Guidelines 225 --
8.4.2 Computational Complexity 226 --
8.4.3 Data Memory Analysis 226 --
8.5 Model Extensions 227 --
8.6 Numerical Results 230 --
8.6.1 Fixed Heuristic Policies for Performance Comparisons 230 --
8.6.2 MDP Specifications 231 --
8.6.3 Results for a Security/Defense System Application 234 --
8.6.4 Results for a Health Care Application 238 --
8.6.5 Results for an Ambient Conditions Monitoring Application 241 --
8.6.6 Sensitivity Analysis 244 --
8.6.7 Number of Iterations for Convergence 245 --
8.7 Chapter Summary 245 --
9 Online Algorithms for Dynamic Optimization of Embedded Wireless Sensor Networks 247 --
9.1 Related Work 249 --
9.2 Dynamic Optimization Methodology 250 --
9.2.1 Methodology Overview 250 --
9.2.2 State Space 251 --
9.2.3 Objective Function 252 --
9.2.4 Online Optimization Algorithms 253 --
9.3 Experimental Results 256 --
9.3.1 Experimental Setup 256 --
9.3.2 Results 258 --
9.4 Chapter Summary 262 --
10 A Lightweight Dynamic Optimization Methodology for Embedded Wireless Sensor Networks 263 --
10.1 Related Work 265 --
10.2 Dynamic Optimization Methodology 267 --
10.2.1 Overview 267 --
10.2.2 State Space 269 --
10.2.3 Optimization Objection Function 269 --
10.3 Algorithms for Dynamic Optimization Methodology 271 --
10.3.1 Initial Tunable Parameter Value Settings and Exploration Order 271 --
10.3.2 Parameter Arrangement 272 --
10.3.3 Online Optimization Algorithm 274 --
10.3.4 Computational Complexity 276 --
10.4 Experimental Results 276 --
10.4.1 Experimental Setup 276 --
10.4.2 Results 279 --
10.5 Chapter Summary 291 --
11 Parallelized Benchmark-Driven Performance Evaluation of Symmetric Multiprocessors and Tiled Multicore Architectures for Parallel Embedded Systems 293. 6.4.4 Resource Adaptive Optimizations 168 --
6.5 Operating System-level Optimizations 168 --
6.5.1 Event-Driven Optimizations 168 --
6.5.2 Dynamic Power Management 169 --
6.5.3 Fault Tolerance 169 --
6.6 Dynamic Optimizations 169 --
6.6.1 Dynamic Voltage and Frequency Scaling 170 --
6.6.2 Software-Based Dynamic Optimizations 170 --
6.6.3 Dynamic Network Reprogramming 170 --
6.7 Chapter Summary 171 --
7 High-Performance Energy-Efficient Multicore-based Parallel Embedded Computing 173 --
7.1 Embedded Systems Applications Characteristics 177 --
7.1.1 Throughput-Intensive 178 --
7.1.2 Thermal-Constrained 180 --
7.1.3 Reliability-Constrained 180 --
7.1.4 Real-Time 180 --
7.1.5 Parallel and Distributed 181 --
7.2 Architectural Approaches 181 --
7.2.1 Core Layout 182 --
7.2.2 Memory Design 184 --
7.2.3 Interconnection Network 185 --
7.2.4 Reduction Techniques 188 --
7.3 Hardware-Assisted Middleware Approaches 189 --
7.3.1 Dynamic Voltage and Frequency Scaling 190 --
7.3.2 Advanced Configuration and Power Interface 190 --
7.3.3 Gating Techniques 191 --
7.3.4 Threading Techniques 192 --
7.3.5 Energy Monitoring and Management 193 --
7.3.6 Dynamic Thermal Management 194 --
7.3.7 Dependable Techniques 195 --
7.4 Software Approaches 196 --
7.4.1 Data Forwarding 196 --
7.4.2 Load Distribution 197 --
7.5 High-Performance Energy-Efficient Multicore Processors 199 --
7.5.1 ARM11 MPCore 199 --
7.5.2 ARM Cortex A-9 MPCore 201 --
7.5.3 MPC8572E PowerQUICC III 201 --
7.5.4 Tilera TILEPro64 and TILE-Gx 202 --
7.5.5 AMD Opteron Processor 202 --
7.5.6 Intel Xeon Processor 202 --
7.5.7 Intel Sandy Bridge Processor 203 --
7.5.8 Graphics Processing Units 203 --
7.6 Challenges and Future Research Directions 204 --
7.7 Chapter Summary 207 --
8 An MDP-based Dynamic Optimization Methodology for Embedded Wireless Sensor Networks 209 --
8.1 Related Work 211 --
8.2 MDP-Based Tuning Overview 214 --
8.2.1 MDP-Based Tuning Methodology for Embedded Wireless Sensor Networks 214 --
8.2.2 MDP Overview with Respect to Embedded Wireless Sensor Networks 216. 4.7 Research Challenges and Future Research Directions 109 --
4.7.1 Accurate Fault Detection 109 --
4.7.2 Benchmarks for Comparing Fault Detection Algorithms 109 --
4.7.3 Energy-Efficient Fault Detection and Tolerance 109 --
4.7.4 Machine-Learning-Inspired Fault Detection 110 --
4.7.5 FT in Multimedia Sensor Networks 110 --
4.7.6 Security 110 --
4.7.7 WSN Design and Tuning for Reliability 112 --
4.7.8 Novel WSN Architectures 113 --
4.8 Chapter Summary 113 --
5 A Queueing Theoretic Approach for Performance Evaluation of Low-Power Multicore-based Parallel Embedded Systems 115 --
5.1 Related Work 118 --
5.2 Queueing Network Modeling of Multi-Core Embedded Architectures 121 --
5.2.1 Queueing Network Terminology 121 --
5.2.2 Modeling Approach 122 --
5.2.3 Assumptions 128 --
5.3 Queueing Network Model Validation 129 --
5.3.1 Theoretical Validation 130 --
5.3.2 Validation with a Multi-Core Simulator 130 --
5.3.3 Speedup 135 --
5.4 Queueing Theoretic Model Insights 136 --
5.4.1 Model Setup 137 --
5.4.2 The Effects of Cache Miss Rates on Performance 140 --
5.4.3 The Effects of Workloads on Performance 144 --
5.4.4 Performance per Watt and Performance per Unit Area Computations 146 --
5.5 Chapter Summary 152 --
Part III Optimization 153 --
6 Optimization Approaches in Distributed Embedded Wireless Sensor Networks 155 --
6.1 Architecture-Level Optimizations 157 --
6.2 Sensor Node Component-Level Optimizations 158 --
6.2.1 Sensing Unit 158 --
6.2.2 Processing Unit 160 --
6.2.3 Transceiver Unit 160 --
6.2.4 Storage Unit 161 --
6.2.5 Actuator Unit 161 --
6.2.6 Location Finding Unit 161 --
6.2.7 Power Unit 162 --
6.3 Data Link-Level Medium Access Control Optimizations 162 --
6.3.1 Load Balancing and Throughput Optimizations 162 --
6.3.2 Power/Energy Optimizations 163 --
6.4 Network-Level Data Dissemination and Routing Protocol Optimizations 165 --
6.4.1 Query Dissemination Optimizations 165 --
6.4.2 Real-Time Constrained Optimizations 167 --
6.4.3 Network Topology Optimizations 167. 2.4.4 Space Shuttle Sensor Networks (3SN) 44 --
2.4.5 Aerial-Terrestrial Hybrid Sensor Networks (ATHSNs) 45 --
2.4.6 Fault-Tolerant (FT) Sensor Networks 46 --
2.5 Multi-core Embedded Sensor Nodes 46 --
2.5.1 InstraNode 47 --
2.5.2 Mars Rover Prototype Mote 47 --
2.5.3 Satellite-Based Sensor Node (SBSN) 47 --
2.5.4 Multi-CPU-based Sensor Node Prototype 48 --
2.5.5 Smart Camera Mote 48 --
2.6 Research Challenges and Future Research Directions 48 --
2.7 Chapter Summary 51 --
Part II Modeling 53 --
3 An Application Metrics Estimation Model for Embedded Wireless Sensor Networks 55 --
3.1 Application Metrics Estimation Model 56 --
3.1.1 Lifetime Estimation 57 --
3.1.2 Throughput Estimation 60 --
3.1.3 Reliability Estimation 61 --
3.1.4 Models Validation 62 --
3.2 Experimental Results 63 --
3.2.1 Experimental Setup 63 --
3.2.2 Results 64 --
3.3 Chapter Summary 66 --
4 Modeling and Analysis of Fault Detection and Fault Tolerance in Embedded Wireless Sensor Networks 67 --
4.1 Related Work 71 --
4.1.1 Fault Detection 71 --
4.1.2 Fault Tolerance 72 --
4.1.3 WSN Reliability Modeling 73 --
4.2 Fault Diagnosis in WSNs 74 --
4.2.1 Sensor Faults 74 --
4.2.2 Taxonomy for Fault Diagnosis Techniques 76 --
4.3 Distributed Fault Detection Algorithms 79 --
4.3.1 Fault Detection Algorithm 1: The Chen Algorithm 79 --
4.3.2 Fault Detection Algorithm 2: The Ding Algorithm 80 --
4.4 Fault-Tolerant Markov Models 81 --
4.4.1 Fault-Tolerance Parameters 82 --
4.4.2 Fault-Tolerant Sensor Node Model 84 --
4.4.3 Fault-Tolerant WSN Cluster Model 86 --
4.4.4 Fault-Tolerant WSN Model 88 --
4.5 Simulation of Distributed Fault Detection Algorithms 90 --
4.5.1 Using ns-2 to Simulate Faulty Sensors 90 --
4.5.2 Experimental Setup for Simulated Data 92 --
4.5.3 Experiments Using Real-World Data 92 --
4.6 Numerical Results 95 --
4.6.1 Experimental Setup 96 --
4.6.2 Reliability and MTTF for an NFT and an FT Sensor Node 97 --
4.6.3 Reliability and MTTF for an NFT and an FT WSN Cluster 101 --
4.6.4 Reliability and MTTF for an NFT and an FT WSN 106. --
PREFACE xiii --
0.1 About This Book xiv --
0.2 Highlights xvi --
0.2.1 Overview of Parallel and Distributed Embedded Systems xvi --
0.2.2 Modeling of Parallel and Distributed Embedded Systems xvi --
0.2.3 Optimization of Parallel and Distributed Embedded Systems xvii --
0.3 Intended Audience xviii --
0.4 Organization of the Book xviii --
Part I Overview 1 --
1 Introduction 3 --
1.1 Embedded Systems Applications 6 --
1.1.1 Cyber-Physical Systems 6 --
1.1.2 Space 7 --
1.1.3 Medical 8 --
1.1.4 Automotive 9 --
1.2 Embedded Systems Applications Characteristics 10 --
1.2.1 Throughput-Intensive 10 --
1.2.2 Thermal-Constrained 11 --
1.2.3 Reliability-Constrained 11 --
1.2.4 Real-Time 11 --
1.2.5 Parallel and Distributed 12 --
1.3 Embedded Systems --
Hardware and Software 12 --
1.3.1 Embedded Systems Hardware 12 --
1.3.2 Embedded Systems Software 15 --
1.4 Modeling --
An Integral Part of the Embedded System Design Flow 16 --
1.4.1 Modeling Objectives 18 --
1.4.2 Modeling Paradigms 20 --
1.4.3 Strategies for Integration of Modeling Paradigms 22 --
1.5 Optimization in Embedded Systems 23 --
1.5.1 Optimization of Embedded Systems Design Metrics 25 --
1.5.2 Multi-Objective Optimization 28 --
1.6 Chapter Summary 29 --
2 Multicore-based EWSNs --
An Example of Parallel and Distributed Embedded Systems 31 --
2.1 Multicore EmbeddedWireless Sensor Network Architecture 33 --
2.2 Multi-core Embedded Sensor Node Architecture 35 --
2.2.1 Sensing Unit 35 --
2.2.2 Processing Unit 35 --
2.2.3 Storage Unit 37 --
2.2.4 Communication Unit 37 --
2.2.5 Power Unit 37 --
2.2.6 Actuator Unit 38 --
2.2.7 Location Finding Unit 38 --
2.3 Compute-Intensive Tasks Motivating the Emergence of MCEWSNs 38 --
2.3.1 Information Fusion 39 --
2.3.2 Encryption 40 --
2.3.3 Network Coding 41 --
2.3.4 Software Defined Radio (SDR) 41 --
2.4 MCEWSN Application Domains 41 --
2.4.1 Wireless Video Sensor Networks (WVSNs) 41 --
2.4.2 Wireless Multimedia Sensor Networks (WMSNs) 42 --
2.4.3 Satellite-based Wireless Sensor Networks (SBWSN) 43.