Parallel Computing

AY2015/2016 Semester 1

This course provides students with an understanding of the concepts and techniques of parallel computing. This includes an understanding of the interaction between hardware and software, the power and limitations of parallelism and its benefits and challenges. Examples are used throughout the course to illustrate concepts and issues in parallel computing. 1. Introduction and Motivation. Motivation for Parallelism: parallel computing, speed up, Moore's law, grand challenge problems, trends. 2. Parallel Computing Systems. Flynn's taxonomy, shared memory architectures, distributed memory architectures, clusters, networks of workstations, heterogeneous architectures. 3. Performance Analysis. Performance Measures: speed up, efficiency, cost. Amdahl's law, Gustafson's law. Parallel Computational Models: PRAM, BSP, Cluster cost model. 4. Shared Memory Parallelism. Threads. OpenMP Compiler Directives. Partitioning Techniques. Examples: Mandelbrot set, Monte Carlo methods, N-body problem, Barnes Hut algorithm. 5. Distributed Memory Parallelism. Message Passing Libraries: processes, point-to-point and collective communication. MPI message passing routines. Data Partitioning. Examples: bucket sort, numerical integration. Divide-and-Conquer. Examples: merge sort, adaptive quadrature. Pipelining: Type 1, 2 and 3 pipelines. Examples: sum of sequence, insertion sort, prime number generation, back substitution. 6. Synchronous Computations. Data Parallel Programming, Global and Local Synchronization. Examples: solving linear equations, cellular automata. 7. Scheduling and Load Balancing. Scheduling. Static Load Balancing. Dynamic Load Balancing. Example: Moore's Algorithm. Performance Tools. 8. Applications. Sorting Algorithms. Examples: rank sort, compare and exchange, bubble sort, quicksort, bitonic mergesort. Numerical Algorithms. Examples: matrix algorithms, solving linear equations, Gaussian elimination; Jacobi iteration.