Design and Analysis of Parallel Algorithms

Credit: 3

Objective

  • To learn about parallel computing models, design and analyze parallel algorithms for PRAM machines and Interconnection networks.

 

UNIT I

Structures and algorithms for array processors: SIMD Array Processors, Interconnection networks, Parallel algorithms for Array processors. Multiprocessor architecture- Interconnection networks-multiprocessor control and algorithms- parallel algorithms for multiprocessors.

 

UNIT II

Selection - broadcast- all sums- parallel selection. Searching a random sequence, sorted sequence on PRAM models, Tree and Mesh.

 

UNIT III

Merging - A network for merging - merging on PRAM models. Sorting on a linear array, EREW, CREW and CRCW SIMD models, MIMD Enumeration sort.

 

UNIT IV

Matrix operations- Transposition, Matrix by matrix multiplication, matrix by vector multiplication. Numerical problems- solving systems of linear equations, finding roots of non linear equations on PRAM models.

 

UNIT V

Graphs - Connected components- dense graphs- sparse graphs. Minimum spanning tree- Solli’s algorithm, Biconnected components, Ear decomposition, Directed graphs.

 

Outcome:

  • To enable the student to design and analyze parallel algorithms

 

Text book:

  1. Kai Wang and Briggs, “Computer Architecture and Parallel Processing”, McGraw Hill, 1985.

  2. S. G. Akl, “Designa and Analysis of Parallel Algorithms”, Prentice Hall Inc., 1992.

  3. Joseph Jaja, “ An Introduction to parallel Algorithms”, Addison Wesley, 1992.