Syllabus
Unit I
Theoretical models of parallel computation: variants of the PRAM model, parallel computational models such as PRAM, LMCC, Hypercube, Cube Connected Cycle, Butterfly, Perfect Shuffle Computers, Tree model, Pyramid model, Fully Connected model, PRAM-CREW, EREW models, interconnection networks, synchronous and asynchronous models.

Unit II
Performance Measures of Parallel Algorithms: Basic techniques of balanced trees, recursive doubling, divide and conquer, partitioning, pipelining, accelerated cascading speed-up, Cost- optimality.

Unit III
Interconnection networks: Graph model of network, Network properties, Searching and sorting on meshes. Parallel merging and sorting algorithms on CREW/EREW. Data Parallel Computation.

Unit IV
Parallel Programming Algorithms: Matrix operations, Sorting, Bubble sort and variants, Quick sort, Bucket sort, Radix sort, Convex Hull

To introduce classical results on parallel algorithmic design

To establish principles and design techniques of parallel algorithms and data structures for various parallel architectures.

Students are able to design, implement and analyze message-passing based parallel algorithms. The students will understand the creation of efficient parallel algorithms in a range of application areas, including sorting, matrix and graph based problems.

M.J. Quinn, Designing Efficient Algorithms for Parallel Computer, McGraw-Hill

J. Jaja, An Introduction to Parallel Algorithms, Addison Wesley

F. T. Leighton, Introduction to Parallel Algorithms and Architectures, MorganKaufmann Publishers

S. G. Akl, Parallel Computation: Models and Methods, Prentice Hall