Network
Table of Contents
Preface xix Contributors xxi
1. Scalable Computing and Communications: Past, Present, and Future 1
Yanhui Wu, Kashif Bilal, Samee U. Khan, Lizhe Wang, and Albert Y. Zomaya
1.1 Scalable Computing and Communications 1
References 4
2. Reliable Minimum Connected Dominating Sets for Topology Control in Probabilistic Wireless Sensor Networks 7
Jing (Selena) He, Shouling Ji, Yi Pan, and Yingshu Li
2.1 Topology Control in Wireless Sensor Networks (WSNs) 7
2.2 DS-Based Topology Control 10
2.3 Deterministic WSNs and Probabilistic WSNs 12
2.4 Reliable MCDS Problem 13
2.5 A GA to Construct RMCDS-GA 17
2.6 Performance Evaluation 26
2.7 Conclusions 27
References 28
3. Peer Selection Schemes in Scalable P2P Video Streaming Systems 31
Xin Jin and Yu-Kwong Kwok
3.1 Introduction 31
3.2 Overlay Structures 32
3.3 Peer Selection for Overlay Construction 34
3.4 A Game Theoretic Perspective on Peer Selection 45
3.5 Discussion and Future Work 47
3.6 Summary 48
References 49
4. Multicore and Many-Core Computing 55
Ioannis E. Venetis
4.1 Introduction 55
4.2 Architectural Options for Multicore Systems 60
4.3 Multicore Architecture Examples 64
4.4 Programming Multicore Architectures 67
4.5 Many-Core Architectures 74
4.6 Many-Core Architecture Examples 75
4.7 Summary 77
References 77
5. Scalable Computing on Large Heterogeneous CPU/GPU Supercomputers 81
Fengshun Lu, Kaijun Ren, Junqiang Song, and Jinjun Chen
5.1 Introduction 81
5.2 Heterogeneous Computing Environments 82
5.3 Scalable Programming Patterns for Large GPU Clusters 84
5.4 Hybrid Implementations 87
5.5 Experimental Results 89
5.6 Conclusions 94
Acknowledgments 94
References 94
6. Diagnosability of Multiprocessor Systems 97
Chia-Wei Lee and Sun-Yuan Hsieh
6.1 Introduction 97
6.2 Fundamental Concepts 98
6.3 Diagnosability of (1,2)-MCNS under PMC Model 103
6.4 Diagnosability of 2-MCNS under MM* Model 105
6.5 Application to Multiprocessor Systems 110
6.6 Concluding Remarks 122
References 122
7. A Performance Analysis Methodology for MultiCore, Multithreaded Processors 125
Miao Ju, Hun Jung, and Hao Che
7.1 Introduction 125
7.2 Methodology 126
7.3 Simulation Tool (ST) 130
7.4 Analytic Modeling Technique 132
7.5 Testing 136
7.6 Related Work 139
7.7 Conclusions and Future Work 141
References 141
8. The Future in Mobile Multicore Computing 145
Blake Hurd, Chiu C. Tan, and Jie Wu
8.1 Introduction 145
8.2 Background 146
8.3 Hardware Initiatives 148
8.4 Software Initiatives 151
8.5 Additional Discussion 152
8.6 Future Trends 153
8.7 Conclusion 154
References 155
9. Modeling and Algorithms for Scalable and Energy-Efficient Execution on Multicore Systems 157
Dong Li, Dimitrios S. Nikolopoulos, and Kirk W. Cameron
9.1 Introduction 157
9.2 Model-Based Hybrid Message-Passing Interface (MPI)/OpenMP Power-Aware Computing 158
9.3 Power-Aware MPI Task Aggregation Prediction 170
9.4 Conclusions 181
References 182
10. Cost Optimization for Scalable Communication in Wireless Networks with Movement-Based Location Management 185
Keqin Li
10.1 Introduction 185
10.2 Background Information 187
10.3 Cost Measure and Optimization for a Single User 190
10.4 Cost Optimization with Location Update Constraint 192
10.5 Cost Optimization with Terminal Paging Constraint 196
10.6 Numerical Data 201
10.7 Concluding Remarks 206
References / 206
11. A Framework for Semiautomatic Explicit Parallelization 209
Ritu Arora, Purushotham Bangalore, and Marjan Mernik
11.1 Introduction 209
11.2 Explicit Parallelization Using MPI 210
11.3 Building Blocks of FraSPA 211
11.4 Evaluation of FraSPA through Case Studies 215
11.5 Lessons Learned 221
11.6 Related Work 222
11.7 Summary 224
References 224
12. Fault Tolerance and Transmission Reliability in Wireless Networks 227
Wolfgang W. Bein and Doina Bein
12.1 Introduction: Reliability Issues in Wireless and Sensor Networks 227
12.2 Reliability and Fault Tolerance of Coverage Models for Sensor Networks 230
12.3 Fault-Tolerant k-Fold Pivot Routing in Wireless Sensor Networks 238
12.4 Impact of Variable Transmission Range in All-Wireless Networks 244
12.5 Conclusions and Open Problems 250
References / 251
13. Optimizing and Tuning Scientifi c Codes 255
Qing Yi
13.1 Introduction 255
13.2 An Abstract View of the Machine Architecture 256
13.3 Optimizing Scientifi c Codes 256
13.4 Empirical Tuning of Optimizations 262
13.5 Related Work 272
13.6 Summary and Future Work 273
Acknowledgments 273
References 273
14. Privacy and Confi dentiality in Cloud Computing 277
Khaled M. Khan and Qutaibah Malluhi
14.1 Introduction 277
14.2 Cloud Stakeholders and Computational Assets 278
14.3 Data Privacy and Trust 280
14.4 A Cloud Computing Example 281
14.5 Conclusion 288
Acknowledgments 288
References 288
15. Reputation Management Systems for Peer-to-Peer Networks 291
Fang Qi, Haiying Shen, Harrison Chandler, Guoxin Liu, and Ze Li
15.1 Introduction 291
15.2 Reputation Management Systems 292
15.3 Case Study of Reputation Systems 307
15.4 Open Problems 316
15.5 Conclusion 316
Acknowledgments 317
References 317
16. Toward a Secure Fragment Allocation of Files in Heterogeneous Distributed Systems 321
Yun Tian, Mohammed I. Alghamdi, Xiaojun Ruan, Jiong Xie, and Xiao Qin
16.1 Introduction 321
16.2 Related Work 323
16.3 System and Threat Models 325
16.4 S-FAS: A Secure Fragment Allocation Scheme 327
16.5 Assurance Models 329
16.6 Sap Allocation Principles and Prototype 332
16.7 Evaluation of System Assurance and Performance 333
16.8 Conclusion 339
Acknowledgments 341
References 341
17. Adopting Compression in Wireless Sensor Networks 343
Xi Deng and Yuanyuan Yang
17.1 Introduction 343
17.2 Compression in Sensor Nodes 345
17.3 Compression Effect on Packet Delay 348
17.4 Online Adaptive Compression Algorithm 350
17.5 Performance Evaluations 360
17.6 Summary 362
References 363
18. GFOG: Green and Flexible Opportunistic Grids 365
Harold Castro, Mario Villamizar, German Sotelo, Cesar O. Diaz, Johnatan Pecero, Pascal Bouvry, and Samee U. Khan
18.1 Introduction 365
18.2 Related Work 366
18.3 UnaGrid Infrastructure 369
18.4 Energy Consumption Model 372
18.5 Experimental Results 374
18.6 Conclusions and Future Work 382
References 382
19. Maximizing Real-Time System Utilization by Adjusting Task Computation Times 387
Nasro Min-Allah, Samee Ullah Khan, Yongji Wang, Joanna Kolodziej, and Nasir Ghani
19.1 Introduction 387
19.2 Expressing Task Schedulability in Polylinear Surfaces 389
19.3 Task Execution Time Adjustment Based on the P-Bound 391
19.4 Conclusions 393
Acknowledgments 393
References 393
20. Multilevel Exploration of the Optimization Landscape through Dynamical Fitness for Grid Scheduling 395
Joanna Kolodziej
20.1 Introduction 395
20.2 Statement of the Problem 397
20.3 General Characteristics of the Optimization Landscape 399
20.4 Multilevel Metaheuristic Schedulers 402
20.5 Empirical Analysis 408
20.6 Conclusions 417
References 417
21. Implementing Pointer Jumping for Exact Inference on Many-Core Systems 419
Yinglong Xia, Nam Ma, and Viktor K. Prasanna
21.1 Introduction 419
21.2 Background 420
21.3 Related Work 422
21.4 Pointer Jumping-Based Algorithms for Scheduling Exact Inference 423
21.5 Analysis with Respect to Many-Core Processors 424
21.6 From Exact Inference to Generic Directed Acyclic Graph (DAG)-Structured Computations 427
21.7 Experiments 428
21.8 Conclusions 434
References 435
22. Performance Optimization of Scientifi c Applications Using an Autonomic Computing Approach 437
Ioana Banicescu, Florina M. Ciorba, and Srishti Srivastava
22.1 Introduction 437
22.2 Scientifi c Applications and Their Performance 439
22.3 Load Balancing via DLS 441
22.4 The Use of Machine Learning in Improving the Performance of Scientifi c Applications 441
22.5 Design Strategies and an Integrated Framework 445
22.6 Experimental Results, Analysis, and Evaluation 455
22.7 Conclusions, Future Work, and Open Problems 462
Acknowledgments 463
References 463
23. A Survey of Techniques for Improving Search Engine Scalability through Profi ling, Prediction, and Prefetching of Query Results 467
C. Shaun Wagner, Sahra Sedigh, Ali R. Hurson, and Behrooz Shirazi
23.1 Introduction 467
23.2 Modeling User Behavior 472
23.3 Grouping Users into Neighborhoods of Similarity 474
23.4 Similarity Metrics 481
23.5 Conclusion and Future Work 497
Appendix A Comparative Analysis of Comparison Algorithms 498
Appendix B Most Popular Searches 501
References 502
24. KNN Queries in Mobile Sensor Networks 507
Wei-Guang Teng and Kun-Ta Chuang
24.1 Introduction 507
24.2 Preliminaries and Infrastructure-Based KNN Queries 509
24.3 Infrastructure-Free KNN Queries 511
24.4 Future Research Directions 519
24.5 Conclusions 519
References 520
25. Data Partitioning for Designing and Simulating Efficient Huge Databases 523
Ladjel Bellatreche, Kamel Boukhalfa, Pascal Richard, and Soumia Benkrid
25.1 Introduction 523
25.2 Background and Related Work 527
25.3 Fragmentation Methodology 532
25.4 Hardness Study 535
25.5 Proposed Selection Algorithms 538
25.6 Impact of HP on Data Warehouse Physical Design 544
25.7 Experimental Studies 549
25.8 Physical Design Simulator Tool 553
25.9 Conclusion and Perspectives 559
References 560
26. Scalable Runtime Environments for Large-Scale Parallel Applications 563
Camille Coti and Franck Cappello
26.1 Introduction 563
26.2 Goals of a Runtime Environment 565
26.3 Communication Infrastructure 567
26.4 Application Deployment 571
26.5 Fault Tolerance and Robustness 577
26.6 Case Studies 582
26.7 Conclusion 586
References 587
27. Increasing Performance through Optimization on APU 591
Matthew Doerksen, Parimala Thulasiraman, and Ruppa Thulasiram
27.1 Introduction 591
27.2 Heterogeneous Architectures 591
27.3 Related Work 597
27.4 OpenCL, CUDA of the Future 600
27.5 Simple Introduction to OpenCL Programming 604
27.6 Performance and Optimization Summary 607
27.7 Application 607
27.8 Summary 609
Appendix 609
References 612
28. Toward Optimizing Cloud Computing: An Example of Optimization under Uncertainty 613
Vladik Kreinovich
28.1 Cloud Computing: Why We Need It and How We Can Make It Most Efficient 613
28.2 Optimal Server Placement Problem: First Approximation 614
28.3 Server Placement in Cloud Computing: Toward a More Realistic Model 618
28.4 Predicting Cloud Growth: Formulation of the Problem and Our Approach to Solving This Problem 620
28.5 Predicting Cloud Growth: First Approximation 621
28.6 Predicting Cloud Growth: Second Approximation 622
28.7 Predicting Cloud Growth: Third Approximation 623
28.8 Conclusions and Future Work 625
Acknowledgments 625
Appendix: Description of Expenses Related to Cloud Computing 626
References 626
29. Modeling of Scalable Embedded Systems 629
Arslan Munir, Sanjay Ranka, and Ann Gordon-Ross
29.1 Introduction 629
29.2 Embedded System Applications 631
29.3 Embedded Systems: Hardware and Software 634
29.4 Modeling: An Integral Part of the Embedded System Design Flow 638
29.5 Single- and Multiunit Embedded System Modeling 644
29.6 Conclusions 654
Acknowledgments 655
References 655
30. Scalable Service Composition in Pervasive Computing 659
Joanna Siebert and Jiannong Cao
30.1 Introduction 659
30.2 Service Composition Framework 660
30.3 Approaches and Techniques for Scalable Service Composition in PvCE 664
30.4 Conclusions 671
References 671
31. Virtualization Techniques for Graphics Processing Units 675
Pavan Balaji, Qian Zhu, and Wu-Chun Feng
31.1 Introduction 675
31.2 Background 677
31.3 VOCL Framework 677
31.4 VOCL Optimizations 682
31.5 Experimental Evaluation 687
31.6 Related Work 696
31.7 Concluding Remarks 696
References 697
32. Dense Linear Algebra on Distributed Heterogeneous Hardware with a Symbolic DAG Approach 699
George Bosilca, Aurelien Bouteiller, Anthony Danalis, Thomas Herault, Piotr Luszczek, and Jack J. Dongara
32.1 Introduction and Motivation 699
32.2 Distributed Datafl ow by Symbolic Evaluation 701
32.3 The DAGuE Datafl ow Runtime 705
32.4 Datafl ow Representation 709
32.5 Programming Linear Algebra with DAGuE 716
32.6 Performance Evaluation 728
32.7 Conclusion 731
32.8 Summary 732
References 733
33. Fault-Tolerance Techniques for Scalable Computing 737
Pavan Balaji, Darius Buntinas, and Dries Kimpe
33.1 Introduction and Trends in Large-Scale Computing Systems 737
33.2 Hardware Features for Resilience 738
33.3 Systems Software Features for Resilience 743
33.4 Application or Domain-Specifi c Fault-Tolerance Techniques 748
33.5 Summary 753
References 753
34. Parallel Programming Models for Scalable Computing 759
James Dinan and Pavan Balaji
34.1 Introduction to Parallel Programming Models 759
34.2 The Message-Passing Interface (MPI) 761
34.3 Partitioned Global Address Space (PGAS) Models 765
34.4 Task-Parallel Programming Models 769
34.5 High-Productivity Parallel Programming Models 772
34.6 Summary and Concluding Remarks 775
Acknowledgment 775
References 775
35. Grid Simulation Tools for Job Scheduling and Data File Replication 777
Javid Taheri, Albert Y. Zomaya, and Samee U. Khan
35.1 Introduction 777
35.2 Simulation Platforms 779
35.3 Problem Statement: Data-Aware Job Scheduling (DAJS) 792
References 795
Index 799
