Title Details

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.

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