You are here: Home Contributors Uncategorised Parallel Algorithms
Print
Details
Hits: 13333

Prof. N. Sairam &     Prof. R. Seethalakshmi

 

Parallel computing has become mainstream and very affordable today. This is mainly because hardware costs have come down rapidly. Processing voluminous datasets is highly computation intensive. Parallel computing has been fruitfully employed in numerous application domains to process large datasets and handle other time-consuming operations of interest.

As a result, unprecedented advances have been made in such areas as biology, scientiļ¬c computing, modeling and simulations, and so forth. Hence the objective of this course is to introduce parallel algorithms and compare it with its sequential equivalent.   The MPI implementation of some algorithms will also be discussed. 
 

Module

Topic

Hours

Total hours per module

Module

I (Introduction)
  • Need for  parallel computers
  • Models of computation
  • Analyzing parallel algorithms
  • Expressing parallel algorithms
1/2 hour
1/2 hour
1/2 hour
1/2 hour

2

Module 1

II (Dense Matrix algorithms)
  • Matrix vector Multiplication
  • Matrix matrix multiplication
1
1
 
 

2

Module 2

III (Decomposition & Mapping techniques)
  • Database query processing
  • 15 puzzle problem
  • Parallel discrete event simulation
  • Image dithering
  • Dense LU factorization
1
1
1
1
1

5

Module 3

IV (Sorting)
  • Hyper quick sort
  • Merge sort
  • Bitonic merge sort
  • odd even transposition
  • Enumeration sort
    (sorting on the CRCW model, CREW model and EREW model)
2
2
2
2
2

10

Module 4

V (Searching and selection)
  • Searching on a sorted sequence
    (EREW,CREW,CRCW)
  • Searching on a random sequence (EREW, CREW, CRCW, Tree and Mesh)
  • Sequential selection algorithm
  • Parallel selection algorithm
    (EREW parallel solution)
4
 
4
 
1
2

11

Module 5

VI (Graph algorithms)
  • Graph coloring
  • Minimal spanning tree
  • Shortest path algorithm
4
3
3

10

Module 6