This book presents the most recent advances in parallel and distributed computing from experts in the field. Serves as a unique format for professionals to present, discuss, and exchange their recent advances, new ideas, results, works-in-progress, and experiences in the areas of parallel and distributed computing for science and engineering applications. All chapters written with introduction, detailed background, and in-depth discussion.
The state of the art of high-performance computing
Prominent researchers from around the world have gathered to present the state-of-the-art techniques and innovations in high-performance computing (HPC), including:
- Programming models for parallel computing: graph-oriented programming (GOP), OpenMP, the stages and transformation (SAT) approach, the bulk-synchronous parallel (BSP) model, Message Passing Interface (MPI), and Cilk
- Architectural and system support, featuring the code tiling compiler technique, the MigThread application-level migration and checkpointing package, the new prefetching scheme of atomicity, a new "receiver makes right" data conversion method, and lessons learned from applying reconfigurable computing to HPC
- Scheduling and resource management issues with heterogeneous systems, bus saturation effects on SMPs, genetic algorithms for distributed computing, and novel task-scheduling algorithms
- Clusters and grid computing: design requirements, grid middleware, distributed virtual machines, data grid services and performance-boosting techniques, security issues, and open issues
- Peer-to-peer computing (P2P) including the proposed search mechanism of hybrid periodical flooding (HPF) and routing protocols for improved routing performance
- Wireless and mobile computing, featuring discussions of implementing the Gateway Location Register (GLR) concept in 3G cellular networks, maximizing network longevity, and comparisons of QoS-aware scatternet scheduling algorithms
- High-performance applications including partitioners, running Bag-of-Tasks applications on grids, using low-cost clusters to meet high-demand applications, and advanced convergent architectures and protocols
High-Performance Computing: Paradigm and Infrastructure is an invaluable compendium for engineers, IT professionals, and researchers and students of computer science and applied mathematics.
Inhaltsverzeichnis
Preface. < p/> Contributors. < p/> PART 1. PROGRAMMING MODEL. < p/> 1. ClusterGOP: A High-Level Programming Environment for Clusters (Fan Chan, Jiannong Cao and Minyi Guo). < p/> 1. 1 Introduction. < p/> 1. 2 GOP Model and ClusterGOP Architecture. < p/> 1. 3 VisualGOP. < p/> 1. 4 The ClusterGOP Library. < p/> 1. 5 MPMD Programming Support. < p/> 1. 6 Programming Using ClusterGOP. < p/> 1. 7 Summary. < p/> 2. The Challenge of Providing A High-Level Programming Model for High-Performance Computing (Barbara Chapman). < p/> 2. 1 Introduction. < p/> 2. 2 HPC Architectures. < p/> 2. 3 HPC Programming Models: The First Generation. < p/> 2. 4 The Second generation of HPC Programming Models. < p/> 2. 5 OpenMP for DMPs. < p/> 2. 6 Experiments with OpenMP on DMPs. < p/> 2. 7 Conclusions. < p/> 3. SAT: Toward Structured Parallelism Using Skeletons (Sergei Gorlatch). < p/> 3. 1 Introduction. < p/> 3. 2 SAT: A Methodology Outline. < p/> 3. 3 Skeletons and Collective Operations. < p/> 3. 4 Case Study: Maximum Segment SUM (MSS). < p/> 3. 5 Performance Aspect in SAT. < p/> 3. 6 Conclusions and Related Work. < p/> 4. Bulk-Synchronous Parallelism: An Emerging Paradigm of High-Performance Computing (Alexander Tiskin). < p/> 4. 1 The BSP Model. < p/> 4. 2 BSP Programming. < p/> 4. 3 Conclusions. < p/> 5. Cilk Versus MPI: Comparing Two Parallel Programming Styles on Heterogenous Systems (John Morris, KyuHo Lee and JunSeong Kim). < p/> 5. 1 Introduction. < p/> 5. 2 Experiments. < p/> 5. 3 Results. < p/> 5. 4 Conclusion. < p/> 6. Nested Parallelism and Pipelining in OpenMP (Marc Gonzalez, E. Ayguade, X. Martorell and J. Labarta). < p/> 6. 1 Introduction. < p/> 6. 2 OpenMP Extensions for Nested Parallelism. < p/> 6. 3 OpenMP Extensions for Thread Synchronization. < p/> 6. 4 Summary. < p/> 7. OpenMP for Chip Multiprocessors (Feng Liu and Vipin Chaudhary). < p/> 7. 1 Introduction. < p/> 7. 2 3SoC Architecture Overview. < p/> 7. 3 The OpenMP Conpiler/Translator. < p/> 7. 4 Extensions to OpenMP for DSEs. < p/> 7. 5 Optimization for OpenMP. < p/> 7. 6 Implementation. < p/> 7. 7 Performance Evaluation. < p/> 7. 8 Conclusions. < p/> PART 2. ARCHITECTURAL AND SYSTEM SUPPORT. < p/> 8. Compiler and Run-Time Parallelization Techniques for Scientific Computations on Distributed-Memory Parallel Computers (PeiZong Lee, Cheien-Min Wang and Jan-Jan Wu). < p/> 8. 1 Introduction. < p/> 8. 2 Background Material. < p/> 8. 3 Compiling Regular Programs on DMPCs. < p/> 8. 4 Compiler and Run-Time Support for Irregular Programs. < p/> 8. 5 Library Support for Irregular Applications. < p/> 8. 6 Related Works. < p/> 8. 7 Concluding Remarks. < p/> 9. Enabling Partial-Cache Line Prefetching Through Data Compression (Youtao Zhang and Rajiv Gupta). < p/> 9. 1 Introduction. < p/> 9. 2 Motivation of Partial Cache-Line Perfetching. < p/> 9. 3 Cache Design Details. < p/> 9. 4 Experimental Results. < p/> 9. 5 Related Work. < p/> 9. 6 Conclusion. < p/> 10. MPI Atomicity and Concurrent Overlapping I/O (Wei-Keng Liao, Alok Choudhary, Kenin Coloma, Lee Ward, Eric Russell and Neil Pundit). < p/> 10. 1 Introduction. < p/> 10. 2 Concurrent Overlapping I/O. < p/> 10. 3 Implementation Strategies. < p/> 10. 4 Experiment Results. < p/> 10. 5 Summary. < p/> 11. Code Tiling: One Size Fits All (Jingling Xue and Qingguang Huang). < p/> 11. 1 Introduction. < p/> 11. 2 Cache Model. < p/> 11. 3 Code Tiling. < p/> 11. 4 Data Tiling. < p/> 11. 5 Finding Optimal Tile Sizes. < p/> 11. 6 Experimental Results. < p/> 11. 7 Related Work. < p/> 11. 8 Conclusion. < p/> 12. Data Conversion for Heterogeneous Migration/Checkpointing (Hai Jiang, Vipin Chaudhary and John Paul Walters). < p/> 12. 1 Introduction. < p/> 12. 2 Migration and Checkpointing. < p/> 12. 3 Data Conversion. < p/> 12. 4 Coarse-Grain Tagged RMR in MigThread. < p/> 12. 5 Microbenchmarks and Experiments. < p/> 12. 6 Related Work. < p/> 12. 7 Conclusions and Future Work. < p/> 13. Receiving-Message Prediction and Its Speculative Execution (Takanobu Baba, Takashi Yokota, Kamemitsu Ootsu, Fumihitto Furukawa and Yoshiyuki Iwamoto). < p/> 13. 1 Background. < p/> 13. 2 Receiving-Message Prediction Method. < p/> 13. 3 Implementation of the Method in the MIPI Libraries. < p/> 13. 4 Experimental Results. < p/> 13. 5 Conclusing Remarks. < p/> 14. An Investigation of the Applicability of Distributed FPGAs to High-Performance Computing (John P. Morrison, Padraig O'Dowd and Philip D. Healy). < p/> 14. 1 Introduction. < p/> 14. 2 High Performance Computing with Cluster Computing. < p/> 14. 3 Reconfigurable Computing with EPGAs. < p/> 14. 4 DRMC: A Distributed Reconfigurable Metacomputer. < p/> 14. 5 Algorithms Suited to the Implementation on FPGAs/DRMC. < p/> 14. 6 Algorithms Not Suited to the Implementation on FPGAs/DRMC. < p/> 14. 7 Summary. < p/> PART 3. SCHEDULING AND RESOURCE MANAGEMENT. < p/> 15. Bandwidth-Aware Resource Allocation for Heterogeneous Computing Systems to Maximize Throughput (Bo Hong and Viktor K. Prasanna). < p/> 15. 1 Introduction. < p/> 15. 2 Related Work. < p/> 15. 3 Systems Model and Problem Statement. < p/> 15. 4 Resource Allocation to Maximize System Throughput. < p/> 15. 5 Experimental Results. < p/> 15. 6 Conclusion. < p/> 16. Scheduling Algorithms with Bus Bandwidth Considerations for SMPs (Christos D. Antonopoulos, Dimitrios S. , Nikolopoulos and Theeodore S. Papatheodorou). < p/> 16. 1 Introduction. < p/> 16. 2 Related Work. < p/> 16. 3 The Implications of Bus Bandwidth for Application Performance. < p/> 16. 4 Scheduling Policies for Preserving Bus Bandwidth. < p/> 16. 5 Experimental Evaluation. < p/> 16. 6 Conclusions. < p/> 17. Toward Performance Guarantee of Dynamic Task Scheduling of a Parameter-Sweep Application onto a Computational Grid (Noriyuki Fujimoto and Kenichi Hagihara). < p/> 17. 1 Introduction. < p/> 17. 2 A Grid Scheduling Model. < p/> 17. 3 Related Works. < p/> 17. 4 The Proposed Algorithm RR. < p/> 17. 5 The Performance Guarantee of the Proposed Algorithm. < p/> 17. 6 Conclusion. < p/> 18. Performance Study of Reliability Maximization and Turnaround Minimization with GA-based Task Allocation in DCS (Deo Prakash Vidyarthi, Anil Kumar Tripathi, Biplab Kumer Sarker, Kirti Rani and Laurence T. Yang). < p/> 18. 1 Introduction. < p/> 18. 2 GA for Task Allocation. < p/> 18. 3 The Algorithm. < p/> 18. 4 Illustrative Examples. < p/> 18. 5 Discussions and Conclusion. < p/> 19. Toward Fast and Efficient Compile-Time Task Scheduling in Heterogeneous Computing Systems (Tarek Hagras and Jan Janecek). < p/> 19. 1 Introduction. < p/> 19. 2 Problem Definition. < p/> 19. 3 The Suggested Algorithm. < p/> 19. 4 Heterogeneous Systems Scheduling Heuristics. < p/> 19. 5 Experimental Results and Discussion. < p/> 19. 6 Conclusion. < p/> 20. An On-Line Approach for Classifying and Extracting Application Behavior on Linux (Luciano José Senger, Rodrigo Fernandes de Mello, Marcos José Santana, Regina Helena Carlucci Santana and Laurence Tianruo Yang). < p/> 20. 1 Introduction. < p/> 20. 2 Related Work. < p/> 20. 3 Information Acquisition. < p/> 20. 4 Linux Process Classification Model. < p/> 20. 5 Results. < p/> 20. 6 Evaluation of The Model Intrusion on the System Performance. < p/> 20. 7 Conclusions. < p/> PART 4. CLUSTERS AND GRID COMPUTING. < p/> 21. Peer-to-Peer Grid Computing and a . NET-Based Alchemi Framework (Akshay Luther, Rajkumar Buyya, Rajiv Ranjan and Srikumar Venugopal). < p/> 21. 1 Introduction. < p/> 21. 2 Background. < p/> 21. 3 Desktop Grid Middleware Considerations. < p/> 21. 4 Representation Desktop Grid Systems. < p/> 21. 5 Alchemi Desktop Grid Framework. < p/> 21. 6 Alchemi Design and Implementation. < p/> 21. 7 Alchemi Performance Evaluation. < p/> 21. 8 Summary and Future Work. < p/> 22. Global Grids and Software Toolkits: A Study of Four Grid Middleware Technologies (Parvin Asadzadeh, Rajkumar Buyya, Chun Ling Kei, Deepa Nayar and Srikumar Venugopal). < p/> 22. 1 Introduction. < p/> 22. 2 Overview of Grid Middleware Systems. < p/> 22. 3 Unicore. < p/> 22. 4 Globus. < p/> 22. 5 Legion. < p/> 22. 6 Gridbus. < p/> 22. 7 Implementation of UNICORE Adaptor for Gridbus Broker. < p/> 22. 8 Comparison of Middleware Systems. < p/> 22. 9 Summary. < p/> 23. High-Performance Computing on Clusters: The Distributed JVM Approach (Wenzhang Zhu, Weijian Fang, Cho-Li Wang and Francis C. M. Lau). < p/> 23. 1 Background. < p/> 23. 2 Distributed JVM. < p/> 23. 3 JESSICA2 Distributed JVM. < p/> 23. 4 Performance Analysis. < p/> 23. 5 Related Work. < p/> 23. 6 Summary. < p/> 24. Data Grids: Supporting Data-Intensive Applications in Wide-Area Networks (Xiao Qin and Hong Jiang). < p/> 24. 1 Introduction. < p/> 24. 2 Data Grid Services. < p/> 24. 3 High-Performance Data Grid. < p/> 24. 4 Security Issues. < p/> 24. 5 Open Issues. < p/> 24. 6 Conclusions. < p/> 25. Application I/O on a Parallel File System for Linux Clusters (Dheeraj Bhaardwaj). < p/> 25. 1 Introduction. < p/> 25. 2 Application I/O. < p/> 25. 3 Parallel I/O System Software. < p/> 25. 4 Standard Unix & Parallel I/O. < p/> 25. 5 Example: Seismic Imaging. < p/> 25. 6 Discussion and Conclusion. < p/> 26. One Teraflop Achieved with a Geographically Distributed Linux Cluster (Peng Wang, George Turner, Steven Simms, Dave Hart, Mary Papakhiam and Craig Stewart). < p/> 26. 1 Introduction. < p/> 26. 2 Hardware and Software Setup. < p/> 26. 3 System Tuning and Benchmark Results. < p/> 26. 4 Performance Costs and Benefits. < p/> 27. A Grid-Based Distributed Simulation of Plasma Turbulence (Beniamino Di Martino, Salvatore Venticinque, Sergio Criguglio, Giulana Fogaccia and Gregorio Vlad). < p/> 27. 1 Introduction. < p/> 27. 2 MPI Implementation of The Internode Domain Decomposition. < p/> 27. 3 Integration of The Internode Domain Decomposition with Intranode Particle Decomposition Strategies. < p/> 27. 4 The MPICH-G2 Implementation. < p/> 27. 5 Conclusions. < p/> 28. Evidence-Aware Trust Model for Dynamic Services (Ali Shaikh Ali, Omer F. Rana and Rashid J. Al-Ali). < p/> 28. 1 Motivation For Evaluating Trust. < p/> 28. 2 Service Trust-What Is It? < p/> 28. 3 Evidence-Aware Trust Model. < p/> 28. 4 The System Life Cycle. < p/> 28. 5 Conclusion. < p/> PART 5. PEER-TO-PEER COMPUTING. < p/> 29. Resource Discovery in Peer-to-Peer Infrastructures (Huang-Chang Hsiao and Chung-Ta King). < p/> 29. 1 Introduction. < p/> 29. 2 Design Requirements. < p/> 29. 3 Unstructured P2P Systems 4. < p/> 29. 4 Structured P2P Systems. < p/> 29. 5 Advanced Resource Discovery for Structured P2P Systems. < p/> 29. 6 Summary. < p/> 30. Hybrid Periodical Flooding in Unstructured Peer-to-Peer Networks (Yunhao Liu, Li Xiao, Lionel M. Ni and Zhenyun Zhuang). < p/> 30. 1 Introduction. < p/> 30. 2 Serarch Mechanisms. < p/> 30. 3 Hybrid Periodical Flooding. < p/> 30. 4 Simulation Methodology. < p/> 30. 5 Performance Evaluation. < p/> 30. 6 Conclusion. < p/> 31. HIERAS: A DHT-Based Hierarchical P2P Routing Algorithm (Zhiyong Xu, Yiming Hu and Laxmi Bhuyan). < p/> 31. 1 Introduction. < p/> 31. 2 Hierarchical P2P Architecture. < p/> 31. 3 System Design. < p/> 31. 4 Performance Evaluation. < p/> 31. 5 Related Works. < p/> 31. 6 Summary. < p/> 32. Flexible and Scalable Group Communication Model for Peer-to-Peer Systems (Tomoya Enokido and Makoto Takizawa). < p/> 32. 1 Introduction. < p/> 32. 2 Group of Agents. < p/> 32. 3 Functions of Group Protocol. < p/> 32. 4 Autonomic Group Protocol. < p/> 32. 5 Retransmission. < p/> 32. 6 Conclusion. < p/> PART 6. WIRELESS AND MOBILE COMPUTING. < p/> 33. Study of Cache-Enhanced Dynamic Movement-Based Location Management Schemes for 3G Cellular Networks (Krishna Priya Patury, Yi Pan, Xiaola Lin, Yang Xiao and Jie Li). < p/> 33. 1 Introduction. < p/> 33. 2 Location Management with and without Cache. < p/> 33. 3 The Cache-Enhanced Location Management Scheme. < p/> 33. 4 Simulation Results and Analysis. < p/> 33. 5 Conclusion. < p/> 34. Maximizing Multicast Lifetime in Wireless Ad Hoc Networks (Guofeng Deng and Sandeep K. S. Gupta). < p/> 34. 1 Introduction. < p/> 34. 2 Energy Consumption Model In WANETs. < p/> 34. 3 Definitions of Maximum Multicast Lifetime. < p/> 34. 4 Maximum Multicast Lifetime of The Network Using Single Tree (MMLM). < p/> 34. 5 Maximum Multicast Lifetime of The Network Using Multiple Trees (MMLM). < p/> 34. 6 Summary. < p/> 35. A QoS-Aware Scheduling Algorithm for Bluetooth Scatternets (Young Man Kim, Ten H. Lai and Anish Arora). < p/> 35. 1 Introduction. < p/> 35. 2 Perfect Scheduling Problem for Bipartite Scatternet. < p/> 35. 3 Perfect Assignment Scheduling Algorithm for Bipartite Scatternets. < p/> 35. 4 Distributed, Local, and Incremental Scheduling Algorithms. < p/> 35. 5 Performance and QOS Analysis. < p/> 35. 6 Conclusion. < p/> PART 7. HIGH PERFORMANCE APPLICATIONS. < p/> 36. A Workload Partitioner for Heterogeneous Grids (Daniel J. Harvey, Sajal K. Das and Rupak Biswas). < p/> 36. 1 Introduction. < p/> 36. 2 Preliminaries. < p/> 36. 3 The MinEX Partitioner. < p/> 36. 4 N-Body Application. < p/> 36. 5 Experimental Study. < p/> 36. 6 Conclusion. < p/> 37. Building a User-Level Grid for Bag-of-Tasks Applications (Walfredo Cirne, Francisco Brasileiro, Daniel Paranhos, Lauro Costa, Elizeu Santos-Neto and Carla Osthoff). < p/> 37. 1 Introduction. < p/> 37. 2 Design Goals. < p/> 37. 3 Architecture. < p/> 37. 4 Working Environment. < p/> 37. 5 Scheduling. < p/> 37. 6 Implementation. < p/> 37. 7 Performance Evaluation. < p/> 37. 8 Conclusions and Future Work. < p/> 38. An Efficient Parallel Method for Calculating the Smarandache Function (Sabin Tabirca, Tatiana Tabirca, Kieran Reynolds and Laurence T. Yang). < p/> 38. 1 Introduction. < p/> 38. 2 Computing in Parallel. < p/> 38. 3 Experimental Results. < p/> 38. 4 Conclusion. < p/> 39. Design, Implementation and Deployment of a Commodity Cluster for Peirodic Comparison of Gene Sequences (Anita M. Orendt, Brian Haymore, David Richardson, Sofia Robb, Alejandro Sanchez Alvarado and Julio C. Facelli). < p/> 39. 1 Introduction. < p/> 39. 2 System Requirements and Design. < p/> 39. 3 Performance. < p/> 39. 4 Conclusions. < p/> 40. A Hierarchical Distributed Shared-Memory Parallel Branch & Bound Application with PVM and OpenMP on Multiprocessor Clusters (Rocco Aversa, Beniamino Di Martino, Nicola Mazzocca and Salvatore Venticinque). < p/> 40. 1 Introduction. < p/> 40. 2 The B&B Parallel Application. < p/> 40. 3 The OpenMP Extension. < p/> 40. 4 Experimental Results. < p/> 40. 5 Conclusions. < p/> 41. IP Based Telecommunication Services (Anna Bonifacio and G. Spinillo). < p/> 41. 1 Introduction. < p/> Index.