CS2024 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.