CS352

DESIGN AND ANALYSIS OF PARALLEL ALGORITHMS

Objectives

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

 

Outcomes

  • To enable the student to design and analyze parallel algorithms 

 

Unit – I

Introduction to Parallel Computers- SIMD - EREW, CREW - SM-SIMD algorithms - Shared memory SIMD - Tree and mesh interconnection computers.

 

Unit – II

Sorting- Sorting on a linear array - Sorting on a mesh - Sorting on EREW SIMD computer - MIMD enumeration sort - MIMD quick sort - Sorting on other networks.

 

Unit – III

Matrix operations- Mesh transpose - Shuffle transpose - EREW transpose - Mesh multiplication - Cube multiplication - Matrix by vector multiplication - Tree multiplication.

 

Unit – IV

Numerical problems- Linear equations - SIMD algorithm - Roots of nonlinear equations - MIMD algorithm - Partial differential equations - Computing Eigen values.

 

Unit – V

Graph problems- Computing the connectivity matrix - Finding connected components - Traversal - Minimal alpha-beta tree - Storage requirements.

 

TEXT BOOKS

  • S. G. Akl, "The Design and Analysis of Parallel Algorithms", Prentice Hall of India, 1989.

REFERENCE

  • S. Lakshmivarahan and S. K. Dhall, "Analysis and Design of Parallel Algorithms - Arithmetic and Matrix Problems", McGraw Hill, 1990