Scalable Computing and Communications

SAMEE U. KHAN, PhD, is Assistant Professor of Electrical and Computer Engineering at North Dakota State University. He is the founding director of the bi-institutional and multi-departmental NDSU-CIIT Green Computing and Communications Laboratory (GCC Lab) and an Adjunct Professor of Computer Science, COMSATS Institute of Information Technology, Pakistan.ALBERT Y. ZOMAYA, PhD, is the Chair Professor of High Performance Computing and Networking, and Australian Research Council Professorial Fellow in the School of Information Technologies, The University of Sydney. He is also the Director of the Centre for Distributed and High Performance Computing as well as the Series Editor for the Wiley Series on Parallel and Distributed Computing.LIZHE WANG, PhD, is a Professor at the Center for Earth Observation and Digital Earth, Chinese Academy of Sciences. He is the ChuTian Scholar Chair Professor in the School of Computer, China University of Geosciences. A senior member of the IEEE, professional member of ACM, and member of the IEEE Computer Society, Dr. Wang has published six books and more than fifty technical papers.

• Preface xix Contributors xxi1. Scalable Computing and Communications: Past, Present, and Future 1Yanhui Wu, Kashif Bilal, Samee U. Khan, Lizhe Wang, and Albert Y. Zomaya1.1 Scalable Computing and Communications 1References 42. Reliable Minimum Connected Dominating Sets for Topology Control in Probabilistic Wireless Sensor Networks 7Jing (Selena) He, Shouling Ji, Yi Pan, and Yingshu Li2.1 Topology Control in Wireless Sensor Networks (WSNs) 72.2 DS-Based Topology Control 102.3 Deterministic WSNs and Probabilistic WSNs 122.4 Reliable MCDS Problem 132.5 A GA to Construct RMCDS-GA 172.6 Performance Evaluation 262.7 Conclusions 27References 283. Peer Selection Schemes in Scalable P2P Video Streaming Systems 31Xin Jin and Yu-Kwong Kwok3.1 Introduction 313.2 Overlay Structures 323.3 Peer Selection for Overlay Construction 343.4 A Game Theoretic Perspective on Peer Selection 453.5 Discussion and Future Work 473.6 Summary 48References 494. Multicore and Many-Core Computing 55Ioannis E. Venetis4.1 Introduction 554.2 Architectural Options for Multicore Systems 604.3 Multicore Architecture Examples 644.4 Programming Multicore Architectures 674.5 Many-Core Architectures 744.6 Many-Core Architecture Examples 754.7 Summary 77References 775. Scalable Computing on Large Heterogeneous CPU/GPU Supercomputers 81Fengshun Lu, Kaijun Ren, Junqiang Song, and Jinjun Chen5.1 Introduction 815.2 Heterogeneous Computing Environments 825.3 Scalable Programming Patterns for Large GPU Clusters 845.4 Hybrid Implementations 875.5 Experimental Results 895.6 Conclusions 94Acknowledgments 94References 946. Diagnosability of Multiprocessor Systems 97Chia-Wei Lee and Sun-Yuan Hsieh6.1 Introduction 976.2 Fundamental Concepts 986.3 Diagnosability of (1,2)-MCNS under PMC Model 1036.4 Diagnosability of 2-MCNS under MM* Model 1056.5 Application to Multiprocessor Systems 1106.6 Concluding Remarks 122References 1227. A Performance Analysis Methodology for MultiCore, Multithreaded Processors 125Miao Ju, Hun Jung, and Hao Che7.1 Introduction 1257.2 Methodology 1267.3 Simulation Tool (ST) 1307.4 Analytic Modeling Technique 1327.5 Testing 1367.6 Related Work 1397.7 Conclusions and Future Work 141References 1418. The Future in Mobile Multicore Computing 145Blake Hurd, Chiu C. Tan, and Jie Wu8.1 Introduction 1458.2 Background 1468.3 Hardware Initiatives 1488.4 Software Initiatives 1518.5 Additional Discussion 1528.6 Future Trends 1538.7 Conclusion 154References 1559. Modeling and Algorithms for Scalable and Energy-Efficient Execution on Multicore Systems 157Dong Li, Dimitrios S. Nikolopoulos, and Kirk W. Cameron9.1 Introduction 1579.2 Model-Based Hybrid Message-Passing Interface (MPI)/OpenMP Power-Aware Computing 1589.3 Power-Aware MPI Task Aggregation Prediction 1709.4 Conclusions 181References 18210. Cost Optimization for Scalable Communication in Wireless Networks with Movement-Based Location Management 185Keqin Li10.1 Introduction 18510.2 Background Information 18710.3 Cost Measure and Optimization for a Single User 19010.4 Cost Optimization with Location Update Constraint 19210.5 Cost Optimization with Terminal Paging Constraint 19610.6 Numerical Data 20110.7 Concluding Remarks 206References / 20611. A Framework for Semiautomatic Explicit Parallelization 209Ritu Arora, Purushotham Bangalore, and Marjan Mernik11.1 Introduction 20911.2 Explicit Parallelization Using MPI 21011.3 Building Blocks of FraSPA 21111.4 Evaluation of FraSPA through Case Studies 21511.5 Lessons Learned 22111.6 Related Work 22211.7 Summary 224References 22412. Fault Tolerance and Transmission Reliability in Wireless Networks 227Wolfgang W. Bein and Doina Bein12.1 Introduction: Reliability Issues in Wireless and Sensor Networks 22712.2 Reliability and Fault Tolerance of Coverage Models for Sensor Networks 23012.3 Fault-Tolerant k-Fold Pivot Routing in Wireless Sensor Networks 23812.4 Impact of Variable Transmission Range in All-Wireless Networks 24412.5 Conclusions and Open Problems 250References / 25113. Optimizing and Tuning Scientifi c Codes 255Qing Yi13.1 Introduction 25513.2 An Abstract View of the Machine Architecture 25613.3 Optimizing Scientifi c Codes 25613.4 Empirical Tuning of Optimizations 26213.5 Related Work 27213.6 Summary and Future Work 273Acknowledgments 273References 27314. Privacy and Confi dentiality in Cloud Computing 277Khaled M. Khan and Qutaibah Malluhi14.1 Introduction 27714.2 Cloud Stakeholders and Computational Assets 27814.3 Data Privacy and Trust 28014.4 A Cloud Computing Example 28114.5 Conclusion 288Acknowledgments 288References 28815. Reputation Management Systems for Peer-to-Peer Networks 291Fang Qi, Haiying Shen, Harrison Chandler, Guoxin Liu, and Ze Li15.1 Introduction 29115.2 Reputation Management Systems 29215.3 Case Study of Reputation Systems 30715.4 Open Problems 31615.5 Conclusion 316Acknowledgments 317References 31716. Toward a Secure Fragment Allocation of Files in Heterogeneous Distributed Systems 321Yun Tian, Mohammed I. Alghamdi, Xiaojun Ruan, Jiong Xie, and Xiao Qin16.1 Introduction 32116.2 Related Work 32316.3 System and Threat Models 32516.4 S-FAS: A Secure Fragment Allocation Scheme 32716.5 Assurance Models 32916.6 Sap Allocation Principles and Prototype 33216.7 Evaluation of System Assurance and Performance 33316.8 Conclusion 339Acknowledgments 341References 34117. Adopting Compression in Wireless Sensor Networks 343Xi Deng and Yuanyuan Yang17.1 Introduction 34317.2 Compression in Sensor Nodes 34517.3 Compression Effect on Packet Delay 34817.4 Online Adaptive Compression Algorithm 35017.5 Performance Evaluations 36017.6 Summary 362References 36318. GFOG: Green and Flexible Opportunistic Grids 365Harold Castro, Mario Villamizar, German Sotelo, Cesar O. Diaz, Johnatan Pecero, Pascal Bouvry, and Samee U. Khan18.1 Introduction 36518.2 Related Work 36618.3 UnaGrid Infrastructure 36918.4 Energy Consumption Model 37218.5 Experimental Results 37418.6 Conclusions and Future Work 382References 38219. Maximizing Real-Time System Utilization by Adjusting Task Computation Times 387Nasro Min-Allah, Samee Ullah Khan, Yongji Wang, Joanna Kolodziej, and Nasir Ghani19.1 Introduction 38719.2 Expressing Task Schedulability in Polylinear Surfaces 38919.3 Task Execution Time Adjustment Based on the P-Bound 39119.4 Conclusions 393Acknowledgments 393References 39320. Multilevel Exploration of the Optimization Landscape through Dynamical Fitness for Grid Scheduling 395Joanna Kolodziej20.1 Introduction 39520.2 Statement of the Problem 39720.3 General Characteristics of the Optimization Landscape 39920.4 Multilevel Metaheuristic Schedulers 40220.5 Empirical Analysis 40820.6 Conclusions 417References 41721. Implementing Pointer Jumping for Exact Inference on Many-Core Systems 419Yinglong Xia, Nam Ma, and Viktor K. Prasanna21.1 Introduction 41921.2 Background 42021.3 Related Work 42221.4 Pointer Jumping-Based Algorithms for Scheduling Exact Inference 42321.5 Analysis with Respect to Many-Core Processors 42421.6 From Exact Inference to Generic Directed Acyclic Graph (DAG)-Structured Computations 42721.7 Experiments 42821.8 Conclusions 434References 43522. Performance Optimization of Scientifi c Applications Using an Autonomic Computing Approach 437Ioana Banicescu, Florina M. Ciorba, and Srishti Srivastava22.1 Introduction 43722.2 Scientifi c Applications and Their Performance 43922.3 Load Balancing via DLS 44122.4 The Use of Machine Learning in Improving the Performance of Scientifi c Applications 44122.5 Design Strategies and an Integrated Framework 44522.6 Experimental Results, Analysis, and Evaluation 45522.7 Conclusions, Future Work, and Open Problems 462Acknowledgments 463References 46323. A Survey of Techniques for Improving Search Engine Scalability through Profi ling, Prediction, and Prefetching of Query Results 467C. Shaun Wagner, Sahra Sedigh, Ali R. Hurson, and Behrooz Shirazi23.1 Introduction 46723.2 Modeling User Behavior 47223.3 Grouping Users into Neighborhoods of Similarity 47423.4 Similarity Metrics 48123.5 Conclusion and Future Work 497Appendix A Comparative Analysis of Comparison Algorithms 498Appendix B Most Popular Searches 501References 50224. KNN Queries in Mobile Sensor Networks 507Wei-Guang Teng and Kun-Ta Chuang24.1 Introduction 50724.2 Preliminaries and Infrastructure-Based KNN Queries 50924.3 Infrastructure-Free KNN Queries 51124.4 Future Research Directions 51924.5 Conclusions 519References 52025. Data Partitioning for Designing and Simulating Efficient Huge Databases 523Ladjel Bellatreche, Kamel Boukhalfa, Pascal Richard, and Soumia Benkrid25.1 Introduction 52325.2 Background and Related Work 52725.3 Fragmentation Methodology 53225.4 Hardness Study 53525.5 Proposed Selection Algorithms 53825.6 Impact of HP on Data Warehouse Physical Design 54425.7 Experimental Studies 54925.8 Physical Design Simulator Tool 55325.9 Conclusion and Perspectives 559References 56026. Scalable Runtime Environments for Large-Scale Parallel Applications 563Camille Coti and Franck Cappello26.1 Introduction 56326.2 Goals of a Runtime Environment 56526.3 Communication Infrastructure 56726.4 Application Deployment 57126.5 Fault Tolerance and Robustness 57726.6 Case Studies 58226.7 Conclusion 586References 58727. Increasing Performance through Optimization on APU 591Matthew Doerksen, Parimala Thulasiraman, and Ruppa Thulasiram27.1 Introduction 59127.2 Heterogeneous Architectures 59127.3 Related Work 59727.4 OpenCL, CUDA of the Future 60027.5 Simple Introduction to OpenCL Programming 60427.6 Performance and Optimization Summary 60727.7 Application 60727.8 Summary 609Appendix 609References 61228. Toward Optimizing Cloud Computing: An Example of Optimization under Uncertainty 613Vladik Kreinovich28.1 Cloud Computing: Why We Need It and How We Can Make It Most Efficient 61328.2 Optimal Server Placement Problem: First Approximation 61428.3 Server Placement in Cloud Computing: Toward a More Realistic Model 61828.4 Predicting Cloud Growth: Formulation of the Problem and Our Approach to Solving This Problem 62028.5 Predicting Cloud Growth: First Approximation 62128.6 Predicting Cloud Growth: Second Approximation 62228.7 Predicting Cloud Growth: Third Approximation 62328.8 Conclusions and Future Work 625Acknowledgments 625Appendix: Description of Expenses Related to Cloud Computing 626References 62629. Modeling of Scalable Embedded Systems 629Arslan Munir, Sanjay Ranka, and Ann Gordon-Ross29.1 Introduction 62929.2 Embedded System Applications 63129.3 Embedded Systems: Hardware and Software 63429.4 Modeling: An Integral Part of the Embedded System Design Flow 63829.5 Single- and Multiunit Embedded System Modeling 64429.6 Conclusions 654Acknowledgments 655References 65530. Scalable Service Composition in Pervasive Computing 659Joanna Siebert and Jiannong Cao30.1 Introduction 65930.2 Service Composition Framework 66030.3 Approaches and Techniques for Scalable Service Composition in PvCE 66430.4 Conclusions 671References 67131. Virtualization Techniques for Graphics Processing Units 675Pavan Balaji, Qian Zhu, and Wu-Chun Feng31.1 Introduction 67531.2 Background 67731.3 VOCL Framework 67731.4 VOCL Optimizations 68231.5 Experimental Evaluation 68731.6 Related Work 69631.7 Concluding Remarks 696References 69732. Dense Linear Algebra on Distributed Heterogeneous Hardware with a Symbolic DAG Approach 699George Bosilca, Aurelien Bouteiller, Anthony Danalis, Thomas Herault, Piotr Luszczek, and Jack J. Dongara32.1 Introduction and Motivation 69932.2 Distributed Datafl ow by Symbolic Evaluation 70132.3 The DAGuE Datafl ow Runtime 70532.4 Datafl ow Representation 70932.5 Programming Linear Algebra with DAGuE 71632.6 Performance Evaluation 72832.7 Conclusion 73132.8 Summary 732References 73333. Fault-Tolerance Techniques for Scalable Computing 737Pavan Balaji, Darius Buntinas, and Dries Kimpe33.1 Introduction and Trends in Large-Scale Computing Systems 73733.2 Hardware Features for Resilience 73833.3 Systems Software Features for Resilience 74333.4 Application or Domain-Specifi c Fault-Tolerance Techniques 74833.5 Summary 753References 75334. Parallel Programming Models for Scalable Computing 759James Dinan and Pavan Balaji34.1 Introduction to Parallel Programming Models 75934.2 The Message-Passing Interface (MPI) 76134.3 Partitioned Global Address Space (PGAS) Models 76534.4 Task-Parallel Programming Models 76934.5 High-Productivity Parallel Programming Models 77234.6 Summary and Concluding Remarks 775Acknowledgment 775References 77535. Grid Simulation Tools for Job Scheduling and Data File Replication 777Javid Taheri, Albert Y. Zomaya, and Samee U. Khan35.1 Introduction 77735.2 Simulation Platforms 77935.3 Problem Statement: Data-Aware Job Scheduling (DAJS) 792References 795Index 799