Modeling and optimization of parallel and distributed embedded systems /

Bibliographic Details
Main Authors:	Munir, Arslan (Author), Gordon-Ross, Ann (Author), Ranka, Sanjay (Author)
Corporate Author:	ebrary, Inc
Format:	eBook
Language:	English
Published:	Chichester, West Sussex, United Kingdom : John Wiley & Sons Inc., [2016]
Subjects:	Parallel processing (Electronic computers) Electronic data processing > Distributed processing. Embedded computer systems. Electronic books.
Online Access:	Connect to the full text of this electronic book

Table of Contents:

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.