Course Details
Subject {L-T-P / C} : CS4435 : Parallel Algorithms { 3-0-0 / 3}
Subject Nature : Theory
Coordinator : Prof.(Ms.) Sujata Mohanty
Syllabus
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
Course Objectives
- To introduce classical results on parallel algorithmic design
- To establish principles and design techniques of parallel algorithms and data structures for various parallel architectures.
Course Outcomes
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.
Essential Reading
- M.J. Quinn, Designing Efficient Algorithms for Parallel Computer, McGraw-Hill
- J. Jaja, An Introduction to Parallel Algorithms, Addison Wesley
Supplementary Reading
- F. T. Leighton, Introduction to Parallel Algorithms and Architectures, MorganKaufmann Publishers
- S. G. Akl, Parallel Computation: Models and Methods, Prentice Hall