PARALLEL PROGRAMMING Syllabus

CS2024 PARALLEL PROGRAMMING L T P C
3 0 0 3
UNIT I PARALLEL PROGRAMMING 9
Introduction to parallel programming – data parallelism – functional parallelism –
pipelining – Flynn's taxonomy – parallel algorithm design – task/channel model –
Foster's design methodology – case studies: boundary value problem – finding the
maximum – n-body problem – Speedup and efficiency – Amdahl's law – Gustafson-
Barsis's Law – Karp-Flatt Metric – Isoefficiency metric
UNIT II MESSAGE-PASSING PROGRAMMING 9
The message-passing model – the message-passing interface – MPI standard – basic
concepts of MPI: MPI_Init, MPI_Comm_size, MPI_Comm_rank, MPI_Send, MPI_Recv,
MPI_Finalize – timing the MPI programs: MPI_Wtime, MPI_Wtick – collective
communication: MPI_Reduce, MPI_Barrier, MPI_Bcast, MPI_Gather, MPI_Scatter –
case studies: the sieve of Eratosthenes, Floyd's algorithm, Matrix-vector multiplication
UNIT III SHARED-MEMORY PROGRAMMING 9
Shared-memory model – OpenMP standard – parallel for loops – parallel for pragma –
private variables – critical sections – reductions – parallel loop optimizations – general
data parallelism – functional parallelism – case studies: the sieve of Eratosthenes,
Floyd's algorithm, matrix-vector multiplication – distributed shared-memory programming
– DSM primitives
UNIT IV PARALLEL ALGORITHMS – I 9
Monte Carlo methods – parallel random number generators – random number
distributions – case studies – Matrix multiplication – rowwise block-stripped algorithm –
Cannon's algorithm – solving linear systems – back substitution – Gaussian elimination –
iterative methods – conjugate gradient method
UNIT V PARALLEL ALGORITHMS – II 9
Sorting algorithms – quicksort – parallel quicksort – hyperquicksort – sorting by regular
sampling – Fast fourier transform – combinatorial search – divide and conquer – parallel
backtrack search – parallel branch and bound – parallel alpha-beta search.
TOTAL: 45 PERIODS
TEXT BOOK:
1. Michael J. Quinn, “Parallel Programming in C with MPI and OpenMP”, Tata
McGraw-Hill Publishing Company Ltd., 2003.
REFERENCES:
1. B. Wilkinson and M. Allen, “Parallel Programming – Techniques and applications
using networked workstations and parallel computers”, Second Edition, Pearson
Education, 2005.
2. M. J. Quinn, “Parallel Computing – Theory and Practice”, Second Edition, Tata
McGraw-Hill Publishing Company Ltd., 2002.