Elements of Parallel Computing

Overview of Parallel Computing INTRODUCTION TERMINOLOGY EVOLUTION OF PARALLEL COMPUTERS EXAMPLE: WORD COUNT PARALLEL PROGRAMMING MODELS Implicit Models Semi-Implicit Models Explicit Models Thinking in Parallel PARALLEL DESIGN PATTERNS Structural Patterns Computational Patterns Patterns in the Lower Layers WORD COUNT IN PARALLEL OUTLINE OF THE BOOK Parallel Machine and Execution Models PARALLEL MACHINE MODELS SIMD Shared Memory and Distributed Memory Computers Distributed Memory Execution Shared Memory Execution Summary PARALLEL EXECUTION MODEL Task Graph Model Examples Summary FURTHER READING EXERCISES Parallel Algorithmic Structures HISTOGRAM EXAMPLE Guidelines for Parallel Algorithm Design EMBARRASSINGLY PARALLEL REDUCTION SCAN DIVIDE AND CONQUER PIPELINE DATA DECOMPOSITION SUMMARY FURTHER READING EXERCISES Parallel Program Structures LOAD BALANCE SIMD: STRICTLY DATA PARALLEL FORKJOIN PARALLEL LOOPS AND SYNCHRONIZATION Shared and Private Variables Synchronization Thread Safety TASKS WITH DEPENDENCIES SINGLE PROGRAM MULTIPLE DATA MASTERWORKER DISTRIBUTED MEMORY PROGRAMMING Distributed Arrays Message Passing Map-Reduce CONCLUSION FURTHER READING EXERCISES Performance Analysis and Optimization WORKDEPTH ANALYSIS PERFORMANCE ANALYSIS Performance Metrics Communication Analysis BARRIERS TO PERFORMANCE MEASURING AND REPORTING PERFORMANCE FURTHER READING EXERCISES Single Source Shortest Path SEQUENTIAL ALGORITHMS Data Structures Bellman-Ford Algorithm Dijkstra's Algorithm Delta-Stepping Algorithm PARALLEL DESIGN EXPLORATION PARALLEL ALGORITHMS Shared Memory Delta-Stepping SIMD Bellman-Ford for GPU Message Passing Algorithm CONCLUSION FURTHER READING EXERCISES The Eikonal Equation NUMERICAL SOLUTION Fast Sweeping Method Fast Marching Method PARALLEL DESIGN EXPLORATION Parallel Fast Sweeping Methods Parallel Fast Marching Methods PARALLEL ALGORITHMS Parallel Fast Sweeping Methods Parallel Fast Marching Methods FURTHER READING EXERCISES Planar Convex Hull SEQUENTIAL ALGORITHMS PARALLEL DESIGN EXPLORATION Parallel Hull Merge PARALLEL ALGORITHMS SIMD QuickHull Coarse-grained Shared Memory MergeHull Distributed Memory MergeHull CONCLUSION FURTHER READING EXERCISES Index