Parallel Programming : For Multicore and Cluster Systems

Innovations in hardware architecture, like hyper-threading or multicore processors, mean that parallel computing resources are available for inexpensive desktop computers. In only a few years, many standard software products will be based on concepts of parallel programming implemented on such hardware, and the range of applications will be much broader than that of scientific computing, up to now the main application area for parallel computing. Rauber and Rünger take up these recent developments in processor architecture by giving detailed descriptions of parallel programming techniques that are necessary for developing efficient programs for multicore processors as well as for parallel cluster systems and supercomputers. Their book is structured in three main parts, covering all areas of parallel computing: the architecture of parallel systems, parallel programming models and environments, and the implementation of efficient application algorithms. The emphasis lies on parallel programming techniques needed for different architectures. The main goal of the book is to present parallel programming techniques that can be used in many situations for many application areas and which enable the reader to develop correct and efficient parallel programs. Many examples and exercises are provided to show how to apply the techniques. The book can be used as both a textbook for students and a reference book for professionals. The presented material has been used for courses in parallel programming at different universities for many years. Springer 364204817X 1 Parallel Programming 4 Preface 6 Contents 8 to 1 Introduction 12 Classical Use of Parallelism 12 Parallelism in Today's Hardware 13 Basic Concepts 14 Overview of the Book 16 to 2 Parallel Computer Architecture 18 Processor Architecture and Technology Trends 18 Flynn's Taxonomy of Parallel Architectures 21 Memory Organization of Parallel Computers 23 Computers with Distributed Memory Organization 23 Computers with Shared Memory Organization 26 Reducing Memory Access Times 28 Thread-Level Parallelism 31 Simultaneous Multithreading 32 Multicore Processors 33 Architecture of Multicore Processors 35 Interconnection Networks 39 Properties of Interconnection Networks 40 Direct Interconnection Networks 43 Embeddings 48 Dynamic Interconnection Networks 51 Routing and Switching 57 Routing Algorithms 57 Routing in the Omega Network 64 Switching 67 Flow Control Mechanisms 74 Caches and Memory Hierarchy 75 Characteristics of Caches 76 Write Policy 84 Cache Coherency 86 Memory Consistency 93 Exercises for Chap. 2 99 to 3 Parallel Programming Models 103 Models for Parallel Systems 103 Parallelization of Programs 106 Levels of Parallelism 108 Parallelism at Instruction Level 108 Data Parallelism 110 Loop Parallelism 112 Functional Parallelism 114 Explicit and Implicit Representation of Parallelism 115 Parallel Programming Patterns 118 Data Distributions for Arrays 123 Data Distribution for One-Dimensional Arrays 123 Data Distribution for Two-Dimensional Arrays 124 Parameterized Data Distribution 126 Information Exchange 127 Shared Variables 127 Communication Operations 128 Parallel Matrix--Vector Product 135 Parallel Computation of Scalar Products 136 Parallel Computation of the Linear Combinations 139 Processes and Threads 140 Processes 140 Threads 142 Synchronization Mechanisms 146 Developing Efficient and Correct Thread Programs 149 Further Parallel Programming Approaches 151 Approaches for New Parallel Languages 152 Transactional Memory 154 Exercises for Chap. 3 157 to 4 Performance Analysis of Parallel Programs 160 Performance Evaluation of Computer Systems 161 Evaluation of CPU Performance 161 MIPS and MFLOPS 163 Performance of Processors with a Memory Hierarchy 164 Benchmark Programs 167 Performance Metrics for Parallel Programs 170 Speedup and Efficiency 171 Scalability of Parallel Programs 174 Asymptotic Times for Global Communication 175 Implementing Global Communication Operations 176 Communications Operations on a Hypercube 182 Analysis of Parallel Execution Times 190 Parallel Scalar Product 190 Parallel Matrix--Vector Product 192 Parallel Computational Models 195 PRAM Model 195 BSP Model 198 LogP Model 200 Exercises for Chap. 4 202 to 5 Message-Passing Programming 206 Introduction to MPI 207 MPI Point-to-Point Communication 208 Deadlocks with Point-to-Point Communications 213 Non-blocking Operations and Communication Modes 217 Communication Mode 221 Collective Communication Operations 222 Collective Communication in MPI 223 Deadlocks with Collective Communication 236 Process Groups and Communicators 238 Process Groups in MPI 238 Process Topologies 243 Timings and Aborting Processes 248 Introduction to MPI-2 249 Dynamic Process Generation and Management 249 One-Sided Communication 252 Exercises for Chap. 5 261 to 6 Thread Programming 266 Programming with Pthreads 266 Creating and Merging Threads 268 Thread Coordination with Pthreads 272 Condition Variables 279 Extended Lock Mechanism 283 One-Time Initialization 285 Implementation of a Task Pool 285 Parallelism by Pipelining 289 Implementation of a Client--Server Model 295 Thread Attributes and Cancellation 299 Thread Scheduling with Pthreads 308 Priority Inversion 312 Thread-Specific Data 315 Java Threads 317 Thread Generation in Java 317 Synchronization of Java Threads 321 Wait and Notify 329 Extended Synchronization Patterns 335 Thread Scheduling in Java 340 Package java.util.concurrent 341 OpenMP 348 Compiler Directives 349 Execution Environment Routines 357 Coordination and Synchronization of Threads 358 Exercises for Chap. 6 362 to 7 Algorithms for Systems of Linear Equations 367 Gaussian Elimination 368 Gaussian Elimination and LU Decomposition 368 Parallel Row-Cyclic Implementation 371 Parallel Implementation with Checkerboard Distribution 375 Analysis of the Parallel Execution Time 381 Direct Methods for Linear Systems with Banded Structure 386 Discretization of the Poisson Equation 386 Tridiagonal Systems 391 Generalization to Banded Matrices 403 Solving the Discretized Poisson Equation 405 Iterative Methods for Linear Systems 407 Standard Iteration Methods 408 Parallel Implementation of the Jacobi Iteration 412 Parallel Implementation of the Gauss--Seidel Iteration 413 Gauss--Seidel Iteration for Sparse Systems 415 Red--Black Ordering 419 Conjugate Gradient Method 425 Sequential CG Method 426 Parallel CG Method 428 Cholesky Factorization for Sparse Matrices 432 Sequential Algorithm 432 Storage Scheme for Sparse Matrices 438 Implementation for Shared Variables 440 Exercises for Chap. 7 445 References 449 Index 457 ISBN-13:,9783642048173 Innovations in hardware architecture, like hyper-threading or multicore processors, mean that parallel computing resources are available for inexpensive desktop computers. In only a few years, many standard software products will be based on concepts of parallel programming implemented on such hardware, and the range of applications will be much broader than that of scientific computing, up to now the main application area for parallel computing. Rauber and Rnger take up these recent developments in processor architecture by giving detailed descriptions of parallel programming techniques that are necessary for developing efficient programs for multicore processors as well as for parallel cluster systems and supercomputers. Their book is structured in three main parts, covering all areas of parallel the architecture of parallel systems, parallel programming models and environments, and the implementation of efficient application algorithms. The emphasis lies on parallel programming techniques needed for different architectures. For this second edition, all chapters have been carefully revised. The chapter on architecture of parallel systems has been updated considerably, with a greater emphasis on the architecture of multicore systems and adding new material on the latest developments in computer architecture. Lastly, a completely new chapter on general-purpose GPUs and the corresponding programming techniques has been added. The main goal of the book is to present parallel programming techniques that can be used in many situations for a broad range of application areas and which enable the reader to develop correct and efficient parallel programs. Many examples and exercises are provided to show how to apply the techniques. The book can be used as both a textbook for students and a reference book for professionals. The material presented has been used for courses in parallel programming at different universities for many years. Front Matter....Pages i-x Introduction....Pages 1-6 Parallel Computer Architecture....Pages 7-91 Parallel Programming Models....Pages 93-149 Performance Analysis of Parallel Programs....Pages 151-196 Message-Passing Programming....Pages 197-256 Thread Programming....Pages 257-357 Algorithms for Systems of Linear Equations....Pages 359-440 Back Matter....Pages 441-455