Main purpose of parallel processing is to perform computation faster, than can be done with a single processor,
by using a number of processors concurrently. Faster solutions, solutions for large-size problems arise
from many applications: weather prediction, artificial intelligence, medicines, modeling
of human organs, fluid dynamics and turbulence, wherever physical
experiments are expensive, time consuming, may be unethical, or
even impossible. High speed computation allows scientists
to validate hypothesis by simulations: which are fast and accurate.
Parallel computers emerged to cater to the need for parallel processing,
mainly because of three factors: hardware cost has reduced drammatically,
phenomenal development of VLSI integration, fastest compute time
of a sequential machine of Von Neumann type processors are reaching fundamental
limits. So, what is a parallel computer and how do we design and analyze
algorithms for them? This course is an introduction to the
discourse on answering these questions. It covers the most
important techniques and paradigms for parallel algorithm design.
A wide range of topics would be discussed in depth, including
lists and trees, searching and sorting, graphs, pattern matching,
and arithmetic computations.
The formal model used is the shared-memory model, though all the algorithms
are described in the work-time presentation framework, which is architecture
independent. The performance would be measured in terms of two
parameters: 1. the total number of operations, and 2. the
parallel time. The framework is closely related to the data-parallel
environment, which is shown to be effective on both SIMD or
MIMD, shared memory or distributed memory architectures.
Detailed Syllabus:
The Idea of Parallelism: A Parallelised version of the Sieve of Eratosthenes
PRAM Model of Parallel Computation
Pointer Jumping and Divide & Conquer: Useful Techniques for Parallelization
PRAM Algorithms: Parallel Reduction, Prefix Sums, List Ranking, Preorder Tree Traversal, Merging Two Sorted Lists, Graph Coloring
Reducing the Number of Processors and Brent's Theorem
Dichotomoy of Parallel Computing Platforms
Cost of Communication
Parallel Complexity: The P-Complete Class
Mapping and Scheduling
Elementary Parallel Algorithms
Sorting
Dictionary Operations: Parallel Search
Graph Algorithms
Matrix Multiplication
Distributed Algorithms: models and complexity measures.
Safety, liveness, termination, logical time and event ordering
Global state and snapshot algorithms
Mutual exclusion and Clock Synchronization
Distributed Graph algorithms
Text Books:
Michael J Quinn, Parallel Computing, TMH
Joseph Jaja, An Introduction to Parallel Algorithms, Addison Wesley
Reference Books/Notes:
To be annouced
Presentations for the class:
Overview: The Idea of Parallelism
Parallel Thinking: Sieve of Eratosthenes
PRAM Algorithms
Shared Memory Parallel Programming
Pointer Jumping and Preorder Tree Traversal
Merging, Brent's Theorem, Few Applications
Optimal Merging
List Ranking and Coloring
Independent Sets for List Ranking and Euler Tour Technique (Introduction)
Evaluating Tree Expressions: Tree Contraction and Raking
Evaluating Tree Expressions (contd.)
Programmer's View of Multi-core Processors and Compiler's role in writing efficient serial programs
Some Example Applications of Prefix-Sums to Solve Recurrences in Parallel
Parallel Search, Faster Merge
Pipelined Merge-Sort Algorithm
Distributed Programming with MPI
Bitonic Sort
Parallel Processor Organization
Mapping Parallel Algorithms to Parallel Platforms
Communications on Hypercube Platforms
Parallel Recursive Programs