Modeling and Optimization of Parallel and Distributed Embedded Systems

Arslan Munir, University of Nevada, Reno (UNR), USAArslan 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, USAAnn 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, USASanjay 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 xvAcknowledgment xxiPart I OVERVIEW1 Introduction 31.1 Embedded Systems Applications 61.1.1 Cyber-Physical Systems 61.1.2 Space 61.1.3 Medical 71.1.4 Automotive 81.2 Characteristics of Embedded Systems Applications 91.2.1 Throughput-Intensive 91.2.2 Thermal-Constrained 91.2.3 Reliability-Constrained 101.2.4 Real-Time 101.2.5 Parallel and Distributed 101.3 Embedded Systems—Hardware and Software 111.3.1 Embedded Systems Hardware 111.3.2 Embedded Systems Software 141.4 Modeling—An Integral Part of the Embedded Systems Design Flow 151.4.1 Modeling Objectives 161.4.2 Modeling Paradigms 181.4.3 Strategies for Integration of Modeling Paradigms 201.5 Optimization in Embedded Systems 211.5.1 Optimization of Embedded Systems Design Metrics 231.5.2 Multiobjective Optimization 261.6 Chapter Summary 272 Multicore-Based EWSNs—An Example of Parallel and Distributed Embedded Systems 292.1 Multicore Embedded Wireless Sensor Network Architecture 312.2 Multicore Embedded Sensor Node Architecture 332.2.1 Sensing Unit 342.2.2 Processing Unit 342.2.3 Storage Unit 342.2.4 Communication Unit 352.2.5 Power Unit 352.2.6 Actuator Unit 352.2.7 Location Finding Unit 362.3 Compute-Intensive Tasks Motivating the Emergence of MCEWSNs 362.3.1 Information Fusion 362.3.2 Encryption 382.3.3 Network Coding 382.3.4 Software-Defined Radio (SDR) 382.4 MCEWSN Application Domains 382.4.1 Wireless Video Sensor Networks (WVSNs) 392.4.2 Wireless Multimedia Sensor Networks (WMSNs) 392.4.3 Satellite-Based Wireless Sensor Networks (SBWSN) 402.4.4 Space Shuttle Sensor Networks (3SN) 412.4.5 Aerial–Terrestrial Hybrid Sensor Networks (ATHSNs) 422.4.6 Fault-Tolerant (FT) Sensor Networks 432.5 Multicore Embedded Sensor Nodes 432.5.1 InstraNode 432.5.2 Mars Rover Prototype Mote 432.5.3 Satellite-Based Sensor Node (SBSN) 442.5.4 Multi-CPU-Based Sensor Node Prototype 442.5.5 Smart Camera Mote 442.6 Research Challenges and Future Research Directions 452.7 Chapter Summary 47Part II MODELING3 An Application Metrics Estimation Model for Embedded Wireless Sensor Networks 513.1 Application Metrics Estimation Model 523.1.1 Lifetime Estimation 533.1.2 Throughput Estimation 563.1.3 Reliability Estimation 573.1.4 Models Validation 573.2 Experimental Results 583.2.1 Experimental Setup 583.2.2 Results 593.3 Chapter Summary 614 Modeling and Analysis of Fault Detection and Fault Tolerance in Embedded Wireless Sensor Networks 634.1 Related Work 674.1.1 Fault Detection 674.1.2 Fault Tolerance 684.1.3 WSN Reliability Modeling 694.2 Fault Diagnosis in WSNs 704.2.1 Sensor Faults 704.2.2 Taxonomy for Fault Diagnosis Techniques 724.3 Distributed Fault Detection Algorithms 744.3.1 Fault Detection Algorithm 1: The Chen Algorithm 744.3.2 Fault Detection Algorithm 2: The Ding Algorithm 764.4 Fault-Tolerant Markov Models 774.4.1 Fault-Tolerance Parameters 774.4.2 Fault-Tolerant Sensor Node Model 794.4.3 Fault-Tolerant WSN Cluster Model 814.4.4 Fault-Tolerant WSN Model 834.5 Simulation of Distributed Fault Detection Algorithms 854.5.1 Using ns−2 to Simulate Faulty Sensors 854.5.2 Experimental Setup for Simulated Data 864.5.3 Experiments Using Real-World Data 864.6 Numerical Results 914.6.1 Experimental Setup 914.6.2 Reliability and MTTF for an NFT and an FT Sensor Node 914.6.3 Reliability and MTTF for an NFT and an FT WSN Cluster 954.6.4 Reliability and MTTF for an NFT and an FT WSN 984.7 Research Challenges and Future Research Directions 1014.7.1 Accurate Fault Detection 1014.7.2 Benchmarks for Comparing Fault Detection Algorithms 1014.7.3 Energy-Efficient Fault Detection and Tolerance 1014.7.4 Machine-Learning-Inspired Fault Detection 1024.7.5 FT in Multimedia Sensor Networks 1024.7.6 Security 1024.7.7 WSN Design and Tuning for Reliability 1044.7.8 Novel WSN Architectures 1044.8 Chapter Summary 1055 A Queueing Theoretic Approach for Performance Evaluation of Low-Power Multicore-Based Parallel Embedded Systems 1075.1 Related Work 1105.2 Queueing Network Modeling of Multicore Embedded Architectures 1125.2.1 Queueing Network Terminology 1125.2.2 Modeling Approach 1135.2.3 Assumptions 1195.3 Queueing Network Model Validation 1205.3.1 Theoretical Validation 1205.3.2 Validation with a Multicore Simulator 1205.3.3 Speedup 1245.4 Queueing Theoretic Model Insights 1255.4.1 Model Setup 1255.4.2 The Effects of Cache Miss Rates on Performance 1295.4.3 The Effects of Workloads on Performance 1325.4.4 Performance per Watt and Performance per Unit Area Computations 1355.5 Chapter Summary 139Part III OPTIMIZATION6 Optimization Approaches in Distributed Embedded Wireless Sensor Networks 1436.1 Architecture-Level Optimizations 1446.2 Sensor Node Component-Level Optimizations 1466.2.1 Sensing Unit 1466.2.2 Processing Unit 1486.2.3 Transceiver Unit 1486.2.4 Storage Unit 1486.2.5 Actuator Unit 1486.2.6 Location Finding Unit 1496.2.7 Power Unit 1496.3 Data Link-Level Medium Access Control Optimizations 1496.3.1 Load Balancing and Throughput Optimizations 1496.3.2 Power/Energy Optimizations 1506.4 Network-Level Data Dissemination and Routing Protocol Optimizations 1526.4.1 Query Dissemination Optimizations 1526.4.2 Real-Time Constrained Optimizations 1546.4.3 Network Topology Optimizations 1546.4.4 Resource-Adaptive Optimizations 1546.5 Operating System-Level Optimizations 1556.5.1 Event-Driven Optimizations 1556.5.2 Dynamic Power Management 1556.5.3 Fault Tolerance 1556.6 Dynamic Optimizations 1566.6.1 Dynamic Voltage and Frequency Scaling 1566.6.2 Software-Based Dynamic Optimizations 1566.6.3 Dynamic Network Reprogramming 1576.7 Chapter Summary 1577 High-Performance Energy-Efficient Multicore-Based Parallel Embedded Computing 1597.1 Characteristics of Embedded Systems Applications 1637.1.1 Throughput-Intensive 1637.1.2 Thermal-Constrained 1657.1.3 Reliability-Constrained 1657.1.4 Real-Time 1657.1.5 Parallel and Distributed 1657.2 Architectural Approaches 1667.2.1 Core Layout 1667.2.2 Memory Design 1687.2.3 Interconnection Network 1707.2.4 Reduction Techniques 1727.3 Hardware-Assisted Middleware Approaches 1737.3.1 Dynamic Voltage and Frequency Scaling 1747.3.2 Advanced Configuration and Power Interface 1747.3.3 Gating Techniques 1757.3.4 Threading Techniques 1767.3.5 Energy Monitoring and Management 1777.3.6 Dynamic Thermal Management 1787.3.7 Dependable Techniques 1797.4 Software Approaches 1807.4.1 Data Forwarding 1807.4.2 Load Distribution 1807.5 High-Performance Energy-Efficient Multicore Processors 1827.5.1 ARM11 MPCore 1837.5.2 ARM Cortex A-9 MPCore 1847.5.3 MPC8572E PowerQUICC III 1847.5.4 Tilera TILEPro64 and TILE-Gx 1847.5.5 AMD Opteron Processor 1857.5.6 Intel Xeon Processor 1857.5.7 Intel Sandy Bridge Processor 1857.5.8 Graphics Processing Units 1867.6 Challenges and Future Research Directions 1867.7 Chapter Summary 1898 An MDP-Based Dynamic Optimization Methodology for Embedded Wireless Sensor Networks 1918.1 Related Work 1938.2 MDP-Based Tuning Overview 1958.2.1 MDP-Based Tuning Methodology for Embedded Wireless Sensor Networks 1958.2.2 MDP Overview with Respect to Embedded Wireless Sensor Networks 1978.3 Application-Specific Embedded Sensor Node Tuning Formulation as an MDP 2008.3.1 State Space 2008.3.2 Decision Epochs and Actions 2008.3.3 State Dynamics 2018.3.4 Policy and Performance Criterion 2018.3.5 Reward Function 2028.3.6 Optimality Equation 2048.3.7 Policy Iteration Algorithm 2058.4 Implementation Guidelines and Complexity 2058.4.1 Implementation Guidelines 2058.4.2 Computational Complexity 2068.4.3 Data Memory Analysis 2078.5 Model Extensions 2078.6 Numerical Results 2108.6.1 Fixed Heuristic Policies for Performance Comparisons 2108.6.2 MDP Specifications 2108.6.3 Results for a Security/Defense System Application 2138.6.4 Results for a Healthcare Application 2168.6.5 Results for an Ambient Conditions Monitoring Application 2208.6.6 Sensitivity Analysis 2228.6.7 Number of Iterations for Convergence 2238.7 Chapter Summary 2239 Online Algorithms for Dynamic Optimization of Embedded Wireless Sensor Networks 2259.1 Related Work 2279.2 Dynamic Optimization Methodology 2289.2.1 Methodology Overview 2289.2.2 State Space 2299.2.3 Objective Function 2299.2.4 Online Optimization Algorithms 2309.3 Experimental Results 2339.3.1 Experimental Setup 2339.3.2 Results 2359.4 Chapter Summary 23910 A Lightweight Dynamic Optimization Methodology for Embedded Wireless Sensor Networks 24110.1 Related Work 24310.2 Dynamic Optimization Methodology 24410.2.1 Overview 24410.2.2 State Space 24610.2.3 Optimization Objection Function 24610.3 Algorithms for Dynamic Optimization Methodology 24810.3.1 Initial Tunable Parameter Value Settings and Exploration Order 24810.3.2 Parameter Arrangement 24910.3.3 Online Optimization Algorithm 25110.3.4 Computational Complexity 25210.4 Experimental Results 25210.4.1 Experimental Setup 25310.4.2 Results 25510.5 Chapter Summary 26611 Parallelized Benchmark-Driven Performance Evaluation of Symmetric Multiprocessors and Tiled Multicore Architectures for Parallel Embedded Systems 26911.1 Related Work 27111.2 Multicore Architectures and Benchmarks 27211.2.1 Multicore Architectures 27211.2.2 Benchmark Applications and Kernels 27311.3 Parallel Computing Device Metrics 27511.4 Results 27711.4.1 Quantitative Comparison of SMPs and TMAs 27711.4.2 Benchmark-Driven Results for SMPs 27811.4.3 Benchmark-Driven Results for TMAs 28011.4.4 Comparison of SMPs and TMAs 28211.5 Chapter Summary 28512 High-Performance Optimizations on Tiled Manycore Embedded Systems: A Matrix Multiplication Case Study 28712.1 Related Work 29012.1.1 Performance Analysis and Optimization 29012.1.2 Parallelized MM Algorithms 29012.1.3 Cache Blocking 29112.1.4 Tiled Manycore Architectures 29212.2 Tiled Manycore Architecture (TMA) Overview 29312.2.1 Intel’s TeraFLOPS Research Chip 29412.2.2 IBM’s Cyclops-64 (C64) 29612.2.3 Tilera’s TILEPro64 29712.2.4 Tilera’s TILE64 30012.3 Parallel Computing Metrics and Matrix Multiplication (MM) Case Study 30112.3.1 Parallel Computing Metrics for TMAs 30112.3.2 Matrix Multiplication (MM) Case Study 30212.4 Matrix Multiplication Algorithms’ Code Snippets for Tilera’s TILEPro64 30312.4.1 Serial Non-blocked Matrix Multiplication Algorithm 30312.4.2 Serial Blocked Matrix Multiplication Algorithm 30412.4.3 Parallel Blocked Matrix Multiplication Algorithm 30712.4.4 Parallel Blocked Cannon’s Algorithm for Matrix Multiplication 30912.5 Performance Optimization on a Manycore Architecture 31412.5.1 Performance Optimization on a Single Tile 31412.5.2 Parallel Performance Optimizations 31512.5.3 Compiler-Based Optimizations 31912.6 Results 32312.6.1 Data Allocation, Data Decomposition, Data Layout, and Communication 32412.6.2 Performance Optimizations on a Single Tile 32712.6.3 Parallel Performance Optimizations 33212.7 Chapter Summary 33913 Conclusions 343References 349Index 369