INTRODUCTION TO PARALLEL PROGRAMMING
CONTENTS CHAPTER WHY PARALLEL COMPUTING WHY WE NEED EVER-INCREASING PERFORMANCE WHY WE’RE BUILDING PARALLEL SYSTEMS WHY WE NEED TO WRITE PARALLEL PROGRAMS HOW DO WE WRITE PARALLEL PROGRAMS? WHAT WE’LL BE DOING CONCURRENT, PARALLEL, DISTRIBUTED THE REST OF THE BOOK A WORD OF WARNING TYPOGRAPHICAL CONVENTIONS 110 SUMMARY 111 EXERCISES CHAPTER PARALLEL HARDWARE AND PARALLEL SOFTWARE SOME BACKGROUND THE VON NEUMANN ARCHITECTURE PROCESSES, MULTITASKING, AND THREADS MODI?CATIONS TO THE VON NEUMANN MODEL THE BASICS OF CACHING CACHE MAPPINGS CACHES AND PROGRAMS: AN EXAMPLE VIRTUAL MEMORY INSTRUCTION-LEVEL PARALLELISM HARDWARE MULTITHREADING PARALLEL HARDWARE CLASSI?CATIONS OF PARALLEL COMPUTERS SIMD SYSTEMS MIMD SYSTEMS INTERCONNECTION NETWORKS CACHE COHERENCE SHARED-MEMORY VS DISTRIBUTED-MEMORY PARALLEL SOFTWARE CAVEATS COORDINATING THE PROCESSES/THREADS SHARED-MEMORY DISTRIBUTED-MEMORY GPU PROGRAMMING PROGRAMMING HYBRID SYSTEMS INPUT AND OUTPUT GPUS PERFORMANCE SPEEDUP AND EF?CIENCY IN MIMD SYSTEMS AMDAHL’S LAW SCALABILITY IN MIMD SYSTEMS TAKING TIMINGS OF MIMD PROGRAMS GPU PERFORMANCE PARALLEL PROGRAM DESIGN AN EXAMPLE WRITING AND RUNNING PARALLEL PROGRAMS ASSUMPTIONS 210 SUMMARY 2101 SERIAL SYSTEMS 2102 PARALLEL HARDWARE 2103 PARALLEL SOFTWARE 2104 INPUT AND OUTPUT 2105 PERFORMANCE 2106 PARALLEL PROGRAM DESIGN 2107 ASSUMPTIONS 211 EXERCISES DISTRIBUTED MEMORY PROGRAMMING WITH MPI GETTING STARTED COMPILATION AND EXECUTION MPI PROGRAMS MPI_INIT AND MPI_FINALIZE COMMUNICATORS, MPI_COMM_SIZE, AND MPI_COMM_RANK SPMD PROGRAMS COMMUNICATION MPI_SEND MPI_RECV MESSAGE MATCHING 3110 THE STATUS_P ARGUMENT 3111 SEMANTICS OF MPI_SEND AND MPI_RECV 3112 SOME POTENTIAL PITFALLS THE TRAPEZOIDAL RULE IN MPI THE TRAPEZOIDAL RULE PARALLELIZING THE TRAPEZOIDAL RULE DEALING WITH I/O OUTPUT INPUT COLLECTIVE COMMUNICATION TREE-STRUCTURED COMMUNICATION MPI_REDUCE COLLECTIVE VS POINT-TO-POINT COMMUNICATIONS MPI_ALLREDUCE BROADCAST DATA DISTRIBUTIONS SCATTER GATHER ALLGATHER MPI-DERIVED DATATYPES PERFORMANCE EVALUATION OF MPI PROGRAMS TAKING TIMINGS RESULTS SPEEDUP AND EF?CIENCY SCALABILITY A PARALLEL SORTING ALGORITHM SOME SIMPLE SERIAL SORTING ALGORITHMS PARALLEL ODD-EVEN TRANSPOSITION SORT SAFETY IN MPI PROGRAMS FINAL DETAILS OF PARALLEL ODD-EVEN SORT SUMMARY EXERCISES 310 PROGRAMMING ASSIGNMENTS SHARED-MEMORY PROGRAMMING WITH PTHREADS PROCESSES, THREADS, AND PTHREADS HELLO, WORLD EXECUTION PRELIMINARIES STARTING THE THREADS RUNNING THE THREADS STOPPING THE THREADS ERROR CHECKING OTHER APPROACHES TO THREAD STARTUP MATRIX-VECTOR MULTIPLICATION CRITICAL SECTIONS BUSY-WAITING MUTEXES PRODUCER–CONSUMER SYNCHRONIZATION AND SEMAPHORES BARRIERS AND CONDITION VARIABLES BUSY-WAITING AND A MUTEX SEMAPHORES CONDITION VARIABLES PTHREADS BARRIERS READ-WRITE LOCKS SORTED LINKED LIST FUNCTIONS A MULTITHREADED LINKED LIST PTHREADS READ-WRITE LOCKS PERFORMANCE OF THE VARIOUS IMPLEMENTATIONS IMPLEMENTING READ-WRITE LOCKS 410 CACHES, CACHE-COHERENCE, AND FALSE SHARING 411 THREAD-SAFETY 4111 INCORRECT PROGRAMS CAN PRODUCE CORRECT OUTPUT 412 SUMMARY 413 EXERCISES 414 PROGRAMMING ASSIGNMENTS SHARED-MEMORY PROGRAMMING WITH OPENMP COMPILING AND RUNNING OPENMP PROGRAMS THE PROGRAM A ?RST OPENMP VERSION SCOPE OF VARIABLES THE REDUCTION CLAUSE THE PARALLEL FOR DIRECTIVE DATA DEPENDENCES FINDING LOOP-CARRIED DEPENDENCES ESTIMATING ? MORE ON SCOPE MORE ABOUT LOOPS IN OPENMP: SORTING BUBBLE SORT ODD-EVEN TRANSPOSITION SORT SCHEDULING LOOPS THE SCHEDULE CLAUSE THE STATIC SCHEDULE TYPE THE DYNAMIC AND GUIDED SCHEDULE TYPES THE RUNTIME SCHEDULE TYPE WHICH SCHEDULE? PRODUCERS AND CONSUMERS QUEUES MESSAGE-PASSING SENDING MESSAGES RECEIVING MESSAGES TERMINATION DETECTION STARTUP THE ATOMIC DIRECTIVE CRITICAL SECTIONS AND LOCKS USING LOCKS IN THE MESSAGE-PASSING PROGRAM CRITICAL DIRECTIVES, ATOMIC DIRECTIVES, OR LOCKS? 5811 SOME CAVEATS CACHES, CACHE COHERENCE, AND FALSE SHARING 510 TASKING 511 THREAD-SAFETY 5111 INCORRECT PROGRAMS CAN PRODUCE CORRECT OUTPUT 512 SUMMARY 513 EXERCISES 514 PROGRAMMING ASSIGNMENTS GPU PROGRAMMING WITH CUDA GPUS AND GPGPU GPU ARCHITECTURES HETEROGENEOUS COMPUTING CUDA HELLO THE SOURCE CODE COMPILING AND RUNNING THE PROGRAM A CLOSER LOOK THREADS, BLOCKS, AND GRIDS NVIDIA COMPUTE CAPABILITIES AND DEVICE ARCHITECTURES VECTOR ADDITION THE KERNEL GET_ARGS ALLOCATE_VECTORS AND MANAGED MEMORY OTHER FUNCTIONS CALLED FROM MAIN EXPLICIT MEMORY TRANSFERS RETURNING RESULTS FROM CUDA KERNELS 610 CUDA TRAPEZOIDAL RULE I 6101 THE TRAPEZOIDAL RULE 6102 A CUDA IMPLEMENTATION 6103 INITIALIZATION, RETURN VALUE, AND ?NAL UPDATE 6104 USING THE CORRECT THREADS 6105 UPDATING THE RETURN VALUE AND ATOMICADD 6106 PERFORMANCE OF THE CUDA TRAPEZOIDAL RULE 611 CUDA TRAPEZOIDAL RULE II: IMPROVING PERFORMANCE 6111 TREE-STRUCTURED COMMUNICATION 6112 LOCAL VARIABLES, REGISTERS, SHARED AND GLOBAL MEMORY 6113 WARPS AND WARP SHUF?ES 6114 IMPLEMENTING TREE-STRUCTURED GLOBAL SUM WITH A WARP SHUF?E 6115 SHARED MEMORY AND AN ALTERNATIVE TO THE WARP SHUF?E CONTENTS 612 IMPLEMENTATION OF TRAPEZOIDAL RULE WITH WARPSIZE THREAD BLOCKS 6121 HOST CODE 6122 KERNEL WITH WARP SHUF?E 6123 KERNEL WITH SHARED MEMORY 6124 PERFORMANCE 613 CUDA TRAPEZOIDAL RULE III: BLOCKS WITH MORE THAN ONE WARP __SYNCTHREADS 6132 MORE SHARED MEMORY 6133 SHARED MEMORY WARP SUMS 6134 SHARED MEMORY BANKS 6135 FINISHING UP 6136 PERFORMANCE 614 BITONIC SORT 6141 SERIAL BITONIC SORT 6142 BUTTER?IES AND BINARY REPRESENTATIONS 6143 PARALLEL BITONIC SORT I 6144 PARALLEL BITONIC SORT II 6145 PERFORMANCE OF CUDA BITONIC SORT 615 SUMMARY 616 EXERCISES 617 PROGRAMMING ASSIGNMENTS PARALLEL PROGRAM DEVELOPMENT TWO N-BODY SOLVERS THE PROBLEM TWO SERIAL PROGRAMS PARALLELIZING THE N-BODY SOLVERS A WORD ABOUT I/O PARALLELIZING THE BASIC SOLVER USING OPENMP PARALLELIZING THE REDUCED SOLVER USING OPENMP EVALUATING THE OPENMP CODES PARALLELIZING THE SOLVERS USING PTHREADS PARALLELIZING THE BASIC SOLVER USING MPI 7110 PARALLELIZING THE REDUCED SOLVER USING MPI 7111 PERFORMANCE OF THE MPI SOLVERS 7112 PARALLELIZING THE BASIC SOLVER USING CUDA 7113 A NOTE ON COOPERATIVE GROUPS IN CUDA 7114 PERFORMANCE OF THE BASIC CUDA N-BODY SOLVER 7115 IMPROVING THE PERFORMANCE OF THE CUDA N-BODY SOLVER 7116 USING SHARED MEMORY IN THE N-BODY SOLVER SAMPLE SORT SAMPLE SORT AND BUCKET SORT CHOOSING THE SAMPLE A SIMPLE IMPLEMENTATION OF THE MAP FUNCTION AN ALTERNATIVE IMPLEMENTATION OF MAP PARALLELIZING SAMPLE SORT IMPLEMENTING SAMPLE SORT WITH OPENMP IMPLEMENTING SAMPLE SORT WITH PTHREADS IMPLEMENTING SAMPLE SORT WITH MPI IMPLEMENTING SAMPLE SORT WITH CUDA A WORD OF CAUTION WHICH API? MPI PROGRAMMING ASSIGNMENTS WHERE TO GO FROM HERE