Unit I
Motivation for Parallelism: Parallel Computing, Speed Up, Moore's Law, Grand Challenge Problems, Trends Parallel and Distributed Computers: Flynn's Taxonomy, Distributed Memory Multicomputers, Shared Memory Multiprocesors, Networks of Workstations, Cluster and Grid Computing
Unit II
Message Passing Computing: Process Creation, Message Passing Routines, Point-to-Point, Collective Communication MPI and PVM: MPI Model of Computation, Basic Concepts, Message Passing Routines, Point-to-Point, Collective Communication, Comparison of MPI and PVM Performance Measures: Granularity, Speed Up, Efficiency, Cost, Amdahl's Law, Gustafson's Law, Isoefficiency Analysis of Parallel Programs: Parallel Computation Models, PRAM, Modeling Communication, Cluster Cost Model
Unit III
Embarassingly Parallel Computations: Low Level Image Processing, Mandelbrot Set, Monte Carlo Methods Simple Data Partitioning: Sum of Numbers, Bucket Sort, Numerical Integartion, N-Body Problem Divide-and-Conquer: Sum of Numbers, Merge Sort, Adaptive Quadrature, Barnes-Hut Algorithm
Unit IV
Pipelined Computations: Type 1, 2 and 3 Pipelines, Sum of Sequence, Insertion Sort, Prime Number Generation, Back Substitution Scheduling and Load Balancing: List Scheduling, Static Load Balancing, Dynamic Load Balancing, Moore's Algorithm Synchronous Computations: Data Parallel Programming, Global and Local Synchronization, Solving Linear Equations, Cellular Automata Shared Memory Programming: Threads, Compiler Directives, OpenMP
Unit V
Sorting Algorithms: Rank Sort, Compare and Exchange, Bubble Sort, Quicksort, Bitonic Mergesort Numerical Algorithms: Matrix Algorithms, Solving Linear Equations, Gaussian Elimination; Jacobi Iteration Image Processing: Low Level Image Procesing, High Level Image Procesing, Fourier Transform
Text Book(s)
1. Barry Wilkinson and Michael Allen. Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers (2nd Edition), Prentice Hall PTR (2005)
References
1. A. Grama, A. Gupta, G. Karypis and V. Kumar. Introduction to Parallel Computing (2nd edition), Addison Wesley (2002), ISBN 0-201-64865-2.
2. H. El-Rewini and T.G. Lewis. Distributed and Parallel Computing, Manning (1997), ISBN 0-13-795592-8.
3. I. Foster. Designing and Building Parallel Programs, Addison Wesley (1995), ISBN 0-201-57594-9.
4. Kai Hwang and Zhiwei Xu. Scalable Parallel Computing, McGraw Hill (1998), ISBN 0-07-031798-4.