mca Syllabus

Parallel Computing
Code: PGCS105D
Weekly Contact Hour: 3L
Credit: 3

Course Contents
Fundamental theoretical issues in designing parallel algorithms and architectures. Parallel computers based on interconnection networks such as hyper cubes, shuffle-exchanges, trees, meshes and butterfly networks. Parallel algorithms for arithmetic, linear algebra, sorting, Fourier Transform, recurrence evaluation, and dense graph problems. Use of graph embedding techniques to compare different networks. Shared memory based parallel computers. Algorithms for list ranking, maximal independent set, arithmetic expression evaluation, convex hull problems and others. Message routing on multidimensional meshes, Butterfly networks, Hyper cubes, Shuffle Exchange networks, Fat-trees and others. Simulation of shared memory on networks. Routing onexpander-based networks. Limits to parallelizability and P-completeness. Thompson grid model for VLSI. Layouts for standard interconnection networks. Lower bound techniques for area and area time-squared tradeoffs. Area-Universal networks.

Books
1. Introduction to Parallel Algorithms and Architectures : Arrays, Trees, Hypercubes. F. T. Leighton. Morgan Kaufmann Publishers,
2. San Mateo, California. 1991. An Introduction to Parallel Algorithms. Joseph JaJa. PEARSON Education.