Modeling and Optimization of Parallel and Distributed Embedded Systems

Arslan Munir, University of Nevada, Reno (UNR), USA Arslan Munir is currently an Assistant Professor in the Department of Computer Science and Engineering (CSE) at the UNR. Before then he was a postdoctoral research associate in the Electrical and Computer Engineering (ECE) department at Rice University (Houston, Texas) between May 2012 and June 2014. He received his M.A.Sc. in ECE from the University of British Columbia (Vancouver, Canada) in 2007 and his Ph.D. in ECE from the University of Florida (Gainesville, Florida) USA in 2012. Between 2007 and 2008, he worked as a software development engineer at Mentor Graphics in the Embedded Systems Division. His current research interests include embedded and cyber-physical systems, computer architecture, parallel computing, fault-tolerance, and computer security. Ann Gordon-Ross, University of Florida, USA Ann Gordon-Ross is currently an Associate Professor of Electrical and Computer Engineering at the University of Florida and is a member of the NSF Center for High Performance Reconfigurable Computing (CHREC) at the University of Florida. She is also the faculty advisor for the Women in Electrical and Computer Engineering (WECE) and the Phi Sigma Rho National Society for Women in Engineering and Engineering Technology. Her research interests include embedded systems, computer architecture, low-power design, reconfigurable computing, dynamic optimizations, hardware design, real-time systems, and multi-core platforms. Sanjay Ranka, University of Florida, USA Sanjay Ranka researches energy efficient computing, high performance computing, data mining and informatics at the University of Florida's Department of Computer Science. He has coauthored two books, 75 journal articles and 125 refereed conference articles. He is a fellow of the IEEE and AAAS, and a member of IFIP Committee on System Modeling and Optimization.

Preface xv

Acknowledgment xxi

Part I OVERVIEW

1 Introduction 3

1.1 Embedded Systems Applications 6

1.1.1 Cyber-Physical Systems 6

1.1.2 Space 6

1.1.3 Medical 7

1.1.4 Automotive 8

1.2 Characteristics of Embedded Systems Applications 9

1.2.1 Throughput-Intensive 9

1.2.2 Thermal-Constrained 9

1.2.3 Reliability-Constrained 10

1.2.4 Real-Time 10

1.2.5 Parallel and Distributed 10

1.3 Embedded Systems—Hardware and Software 11

1.3.1 Embedded Systems Hardware 11

1.3.2 Embedded Systems Software 14

1.4 Modeling—An Integral Part of the Embedded Systems Design Flow 15

1.4.1 Modeling Objectives 16

1.4.2 Modeling Paradigms 18

1.4.3 Strategies for Integration of Modeling Paradigms 20

1.5 Optimization in Embedded Systems 21

1.5.1 Optimization of Embedded Systems Design Metrics 23

1.5.2 Multiobjective Optimization 26

1.6 Chapter Summary 27

2 Multicore-Based EWSNs—An Example of Parallel and Distributed Embedded Systems 29

2.1 Multicore Embedded Wireless Sensor Network Architecture 31

2.2 Multicore Embedded Sensor Node Architecture 33

2.2.1 Sensing Unit 34

2.2.2 Processing Unit 34

2.2.3 Storage Unit 34

2.2.4 Communication Unit 35

2.2.5 Power Unit 35

2.2.6 Actuator Unit 35

2.2.7 Location Finding Unit 36

2.3 Compute-Intensive Tasks Motivating the Emergence of MCEWSNs 36

2.3.1 Information Fusion 36

2.3.2 Encryption 38

2.3.3 Network Coding 38

2.3.4 Software-Defined Radio (SDR) 38

2.4 MCEWSN Application Domains 38

2.4.1 Wireless Video Sensor Networks (WVSNs) 39

2.4.2 Wireless Multimedia Sensor Networks (WMSNs) 39

2.4.3 Satellite-Based Wireless Sensor Networks (SBWSN) 40

2.4.4 Space Shuttle Sensor Networks (3SN) 41

2.4.5 Aerial–Terrestrial Hybrid Sensor Networks (ATHSNs) 42

2.4.6 Fault-Tolerant (FT) Sensor Networks 43

2.5 Multicore Embedded Sensor Nodes 43

2.5.1 InstraNode 43

2.5.2 Mars Rover Prototype Mote 43

2.5.3 Satellite-Based Sensor Node (SBSN) 44

2.5.4 Multi-CPU-Based Sensor Node Prototype 44

2.5.5 Smart Camera Mote 44

2.6 Research Challenges and Future Research Directions 45

2.7 Chapter Summary 47

Part II MODELING

3 An Application Metrics Estimation Model for Embedded Wireless Sensor Networks 51

3.1 Application Metrics Estimation Model 52

3.1.1 Lifetime Estimation 53

3.1.2 Throughput Estimation 56

3.1.3 Reliability Estimation 57

3.1.4 Models Validation 57

3.2 Experimental Results 58

3.2.1 Experimental Setup 58

3.2.2 Results 59

3.3 Chapter Summary 61

4 Modeling and Analysis of Fault Detection and Fault Tolerance in Embedded Wireless Sensor Networks 63

4.1 Related Work 67

4.1.1 Fault Detection 67

4.1.2 Fault Tolerance 68

4.1.3 WSN Reliability Modeling 69

4.2 Fault Diagnosis in WSNs 70

4.2.1 Sensor Faults 70

4.2.2 Taxonomy for Fault Diagnosis Techniques 72

4.3 Distributed Fault Detection Algorithms 74

4.3.1 Fault Detection Algorithm 1: The Chen Algorithm 74

4.3.2 Fault Detection Algorithm 2: The Ding Algorithm 76

4.4 Fault-Tolerant Markov Models 77

4.4.1 Fault-Tolerance Parameters 77

4.4.2 Fault-Tolerant Sensor Node Model 79

4.4.3 Fault-Tolerant WSN Cluster Model 81

4.4.4 Fault-Tolerant WSN Model 83

4.5 Simulation of Distributed Fault Detection Algorithms 85

4.5.1 Using ns−2 to Simulate Faulty Sensors 85

4.5.2 Experimental Setup for Simulated Data 86

4.5.3 Experiments Using Real-World Data 86

4.6 Numerical Results 91

4.6.1 Experimental Setup 91

4.6.2 Reliability and MTTF for an NFT and an FT Sensor Node 91

4.6.3 Reliability and MTTF for an NFT and an FT WSN Cluster 95

4.6.4 Reliability and MTTF for an NFT and an FT WSN 98

4.7 Research Challenges and Future Research Directions 101

4.7.1 Accurate Fault Detection 101

4.7.2 Benchmarks for Comparing Fault Detection Algorithms 101

4.7.3 Energy-Efficient Fault Detection and Tolerance 101

4.7.4 Machine-Learning-Inspired Fault Detection 102

4.7.5 FT in Multimedia Sensor Networks 102

4.7.6 Security 102

4.7.7 WSN Design and Tuning for Reliability 104

4.7.8 Novel WSN Architectures 104

4.8 Chapter Summary 105

5 A Queueing Theoretic Approach for Performance Evaluation of Low-Power Multicore-Based Parallel Embedded Systems 107

5.1 Related Work 110

5.2 Queueing Network Modeling of Multicore Embedded Architectures 112

5.2.1 Queueing Network Terminology 112

5.2.2 Modeling Approach 113

5.2.3 Assumptions 119

5.3 Queueing Network Model Validation 120

5.3.1 Theoretical Validation 120

5.3.2 Validation with a Multicore Simulator 120

5.3.3 Speedup 124

5.4 Queueing Theoretic Model Insights 125

5.4.1 Model Setup 125

5.4.2 The Effects of Cache Miss Rates on Performance 129

5.4.3 The Effects of Workloads on Performance 132

5.4.4 Performance per Watt and Performance per Unit Area Computations 135

5.5 Chapter Summary 139

Part III OPTIMIZATION

6 Optimization Approaches in Distributed Embedded Wireless Sensor Networks 143

6.1 Architecture-Level Optimizations 144

6.2 Sensor Node Component-Level Optimizations 146

6.2.1 Sensing Unit 146

6.2.2 Processing Unit 148

6.2.3 Transceiver Unit 148

6.2.4 Storage Unit 148

6.2.5 Actuator Unit 148

6.2.6 Location Finding Unit 149

6.2.7 Power Unit 149

6.3 Data Link-Level Medium Access Control Optimizations 149

6.3.1 Load Balancing and Throughput Optimizations 149

6.3.2 Power/Energy Optimizations 150

6.4 Network-Level Data Dissemination and Routing Protocol Optimizations 152

6.4.1 Query Dissemination Optimizations 152

6.4.2 Real-Time Constrained Optimizations 154

6.4.3 Network Topology Optimizations 154

6.4.4 Resource-Adaptive Optimizations 154

6.5 Operating System-Level Optimizations 155

6.5.1 Event-Driven Optimizations 155

6.5.2 Dynamic Power Management 155

6.5.3 Fault Tolerance 155

6.6 Dynamic Optimizations 156

6.6.1 Dynamic Voltage and Frequency Scaling 156

6.6.2 Software-Based Dynamic Optimizations 156

6.6.3 Dynamic Network Reprogramming 157

6.7 Chapter Summary 157

7 High-Performance Energy-Efficient Multicore-Based Parallel Embedded Computing 159

7.1 Characteristics of Embedded Systems Applications 163

7.1.1 Throughput-Intensive 163

7.1.2 Thermal-Constrained 165

7.1.3 Reliability-Constrained 165

7.1.4 Real-Time 165

7.1.5 Parallel and Distributed 165

7.2 Architectural Approaches 166

7.2.1 Core Layout 166

7.2.2 Memory Design 168

7.2.3 Interconnection Network 170

7.2.4 Reduction Techniques 172

7.3 Hardware-Assisted Middleware Approaches 173

7.3.1 Dynamic Voltage and Frequency Scaling 174

7.3.2 Advanced Configuration and Power Interface 174

7.3.3 Gating Techniques 175

7.3.4 Threading Techniques 176

7.3.5 Energy Monitoring and Management 177

7.3.6 Dynamic Thermal Management 178

7.3.7 Dependable Techniques 179

7.4 Software Approaches 180

7.4.1 Data Forwarding 180

7.4.2 Load Distribution 180

7.5 High-Performance Energy-Efficient Multicore Processors 182

7.5.1 ARM11 MPCore 183

7.5.2 ARM Cortex A-9 MPCore 184

7.5.3 MPC8572E PowerQUICC III 184

7.5.4 Tilera TILEPro64 and TILE-Gx 184

7.5.5 AMD Opteron Processor 185

7.5.6 Intel Xeon Processor 185

7.5.7 Intel Sandy Bridge Processor 185

7.5.8 Graphics Processing Units 186

7.6 Challenges and Future Research Directions 186

7.7 Chapter Summary 189

8 An MDP-Based Dynamic Optimization Methodology for Embedded Wireless Sensor Networks 191

8.1 Related Work 193

8.2 MDP-Based Tuning Overview 195

8.2.1 MDP-Based Tuning Methodology for Embedded Wireless Sensor Networks 195

8.2.2 MDP Overview with Respect to Embedded Wireless Sensor Networks 197

8.3 Application-Specific Embedded Sensor Node Tuning Formulation as an MDP 200

8.3.1 State Space 200

8.3.2 Decision Epochs and Actions 200

8.3.3 State Dynamics 201

8.3.4 Policy and Performance Criterion 201

8.3.5 Reward Function 202

8.3.6 Optimality Equation 204

8.3.7 Policy Iteration Algorithm 205

8.4 Implementation Guidelines and Complexity 205

8.4.1 Implementation Guidelines 205

8.4.2 Computational Complexity 206

8.4.3 Data Memory Analysis 207

8.5 Model Extensions 207

8.6 Numerical Results 210

8.6.1 Fixed Heuristic Policies for Performance Comparisons 210

8.6.2 MDP Specifications 210

8.6.3 Results for a Security/Defense System Application 213

8.6.4 Results for a Healthcare Application 216

8.6.5 Results for an Ambient Conditions Monitoring Application 220

8.6.6 Sensitivity Analysis 222

8.6.7 Number of Iterations for Convergence 223

8.7 Chapter Summary 223

9 Online Algorithms for Dynamic Optimization of Embedded Wireless Sensor Networks 225

9.1 Related Work 227

9.2 Dynamic Optimization Methodology 228

9.2.1 Methodology Overview 228

9.2.2 State Space 229

9.2.3 Objective Function 229

9.2.4 Online Optimization Algorithms 230

9.3 Experimental Results 233

9.3.1 Experimental Setup 233

9.3.2 Results 235

9.4 Chapter Summary 239

10 A Lightweight Dynamic Optimization Methodology for Embedded Wireless Sensor Networks 241

10.1 Related Work 243

10.2 Dynamic Optimization Methodology 244

10.2.1 Overview 244

10.2.2 State Space 246

10.2.3 Optimization Objection Function 246

10.3 Algorithms for Dynamic Optimization Methodology 248

10.3.1 Initial Tunable Parameter Value Settings and Exploration Order 248

10.3.2 Parameter Arrangement 249

10.3.3 Online Optimization Algorithm 251

10.3.4 Computational Complexity 252

10.4 Experimental Results 252

10.4.1 Experimental Setup 253

10.4.2 Results 255

10.5 Chapter Summary 266

11 Parallelized Benchmark-Driven Performance Evaluation of Symmetric Multiprocessors and Tiled Multicore Architectures for Parallel Embedded Systems 269

11.1 Related Work 271

11.2 Multicore Architectures and Benchmarks 272

11.2.1 Multicore Architectures 272

11.2.2 Benchmark Applications and Kernels 273

11.3 Parallel Computing Device Metrics 275

11.4 Results 277

11.4.1 Quantitative Comparison of SMPs and TMAs 277

11.4.2 Benchmark-Driven Results for SMPs 278

11.4.3 Benchmark-Driven Results for TMAs 280

11.4.4 Comparison of SMPs and TMAs 282

11.5 Chapter Summary 285

12 High-Performance Optimizations on Tiled Manycore Embedded Systems: A Matrix Multiplication Case Study 287

12.1 Related Work 290

12.1.1 Performance Analysis and Optimization 290

12.1.2 Parallelized MM Algorithms 290

12.1.3 Cache Blocking 291

12.1.4 Tiled Manycore Architectures 292

12.2 Tiled Manycore Architecture (TMA) Overview 293

12.2.1 Intel’s TeraFLOPS Research Chip 294

12.2.2 IBM’s Cyclops-64 (C64) 296

12.2.3 Tilera’s TILEPro64 297

12.2.4 Tilera’s TILE64 300

12.3 Parallel Computing Metrics and Matrix Multiplication (MM) Case Study 301

12.3.1 Parallel Computing Metrics for TMAs 301

12.3.2 Matrix Multiplication (MM) Case Study 302

12.4 Matrix Multiplication Algorithms’ Code Snippets for Tilera’s TILEPro64 303

12.4.1 Serial Non-blocked Matrix Multiplication Algorithm 303

12.4.2 Serial Blocked Matrix Multiplication Algorithm 304

12.4.3 Parallel Blocked Matrix Multiplication Algorithm 307

12.4.4 Parallel Blocked Cannon’s Algorithm for Matrix Multiplication 309

12.5 Performance Optimization on a Manycore Architecture 314

12.5.1 Performance Optimization on a Single Tile 314

12.5.2 Parallel Performance Optimizations 315

12.5.3 Compiler-Based Optimizations 319

12.6 Results 323

12.6.1 Data Allocation, Data Decomposition, Data Layout, and Communication 324

12.6.2 Performance Optimizations on a Single Tile 327

12.6.3 Parallel Performance Optimizations 332

12.7 Chapter Summary 339

13 Conclusions 343

References 349

Index 369