Parallel Algorithms

Basic Introduction to Parallel Processing platforms. Preliminaries, Decomposition Techniques, Characteristics of Tasks and Interactions, Mapping Techniques for Load Balancing, Methods for Containing Interaction Overheads, Parallel Algorithm Models.

Basic Communication Operations - One-to-All Broadcast and All-to-One Reduction, All-to-All Broadcast and Reduction, All-Reduce and Prefix-Sum Operations, Scatter and Gather, All-to-All Personalized Communication, Circular Shift, Improving the Speed of Some Communication Operation

Principles of Message-Passing Programming, The Building Blocks: Send and Receive Operations, MPI: The Message Passing Interface, Overlapping Communication with Computation, Collective Communication and Computation Operations, Groups and Communicators.

(7 hours) Thread Basics, Why Threads? The POSIX Thread Application Programme Interface, Synchronization Primitives in POSIX, Controlling Thread and Synchronization Attributes, Thread Cancellation, Composite Synchronization Constructs, OpenMP: a Standard for Directive Based Parallel Programming, Specifying Concurrent Tasks in OpenMP, Synchronization Constructs in OpenMP, Data Handling in OpenMP, OpenMP Library Functions, OpenMP Applications: Parallel algorithm development for Matrix multiplication

Heterogeneous Parallel Computing, Architecture of a Modern GPU, Speeding up Real Applications, Data parallel computing, CUDA C Program Structure, A Vector Addition Kernel, Device Global Memory and Data Transfer, Kernel Functions and Threading, Kernel Launch, CUDA Thread Organization, Mapping Threads to Multidimensional Data, Synchronization and Transparent Scalability, Resource Assignment, Querying Device Properties, Thread Scheduling and Latency Tolerance, Importance of Memory Access Efficiency, Cuda Memory Types, Tiling for Reduced Memory Traffic, Tiled Matrix Multiplication Kernel, Boundary Checks