Introduction to Parallel Computing:
Motivating Parallelism, Scope of Parallel Computing,
Parallel Programming Platforms:
Implicit Parallelism: Trends in Microprocessor Architectures, Limitations of Memory System Performance, Dichotomy of Parallel Computing Platforms, Physical Organization of Parallel Platforms, Communication Costs in Parallel Machines, Routing Mechanisms for Interconnection Networks, Impact of Process-Processor Mapping and Mapping Techniques.
T1: Ch: 1.1, 1.2, 2.1 – 2.7
RBT: L1, L2
Principles of Parallel Algorithm Design:
Preliminaries, Decomposition Techniques, Characteristics of Tasks and Interactions, Mapping Techniques for Load Balancing, Methods for Containing Interaction Overheads, Parallel Algorithm Models.
Basic Communication Operations:
One-to-All Broadcast and All-to-One Reduction, Allto-All Broadcast and Reduction, All-Reduce and Prefix-Sum Operations, Scatter and Gather, All-to-All Personalized Communication, Circular Shift, Improving the Speed of Some Communication Operations
T1: Ch 3, 4
RBT: L1, L2
Analytical Modeling of Parallel Programs:
Sources of Overhead in Parallel Programs, Performance Metrics for Parallel Systems, The Effect of Granularity on Performance, Scalability of Parallel Systems. Minimum Execution Time and Minimum Cost-Optimal Execution Time, Asymptotic Analysis of Parallel Programs Section 5.7. Other Scalability Metrics,
Programming Using the Message-Passing Paradigm:
Principles of Message-Passing Programming, The Building Blocks: Send and Receive Operations, MPI: the Message Passing Interface, Topologies and Embedding, Overlapping Communication with Computation, Collective Communication and Computation Operations, Groups and Communicators
T1: Ch 5, 6
RBT: L1, L2, L3
Programming Shared Address Space Platforms:
Thread Basics, Why Threads?, The POSIX Thread API, Thread Basics: Creation and Termination, Synchronization Primitives in Pthreads, Controlling Thread and Synchronization Attributes, Thread Cancellation, Composite Synchronization Constructs, Tips for Designing Asynchronous Programs,
OpenMP:
a Standard for Directive Based Parallel Programming Dense Matrix Algorithms: Matrix-Vector Multiplication, Matrix-Matrix Multiplication, Solving a System of Linear Equations
Sorting:
Issues in Sorting on Parallel Computers, Sorting Networks, Bubble Sort and its Variants, Quicksort, Bucket and Sample Sort.
T1: Ch 7, 8 9
RBT: L1, L2
Graph Algorithms:
Definitions and Representation, Minimum Spanning Tree: Prim's Algorithm, Single-Source Shortest Paths: Dijkstra's Algorithm, All-Pairs Shortest Paths, Transitive Closure, Connected Components, Algorithms for Sparse Graphs, Search Algorithms for Discrete Optimization Problems: Definitions and Examples, Sequential Search Algorithms, Search Overhead Factor, Parallel Depth-First Search, Parallel Best-First Search, Speedup, Anomalies in Parallel Search Algorithms
T1: Ch10, 11
RBT: L1, L2
Course outcomes:
The students should be able to:
Question paper pattern:
Text Books:
1. Introduction to Parallel Computing, AnanthGrama, Anshul Gupta, George Karypis, and Vipin Kumar, 2nd edition, Addison-Welsey, 2003.
Reference Books:
1. Grama, A. Gupta, G. Karypis, V. Kumar, An Introduction to Parallel Computing, Design and Analysis of Algorithms: 2/e, Addison-Wesley, 2003.
2. G.E. Karniadakis, R.M. Kirby II, Parallel Scientific Computing in C++ and MPI: A Seamless Approach to Parallel Algorithms and their Implementation, Cambridge University Press,2003.
3. Wilkinson and M. Allen, Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers, 2/E, Prentice Hall, 2005.
4. M.J. Quinn, Parallel Programming in C with MPI and OpenMP, McGraw-Hill, 2004.
5. G.S. Almasi and A. Gottlieb, Highly Parallel Computing, 2/E, Addison-Wesley, 1994.
6. David Culler Jaswinder Pal Singh,"Parallel Computer Architecture: A hardware/Software Approach", Morgan Kaufmann, 1999.
7. Kai Hwang, "Scalable Parallel Computing", McGraw Hill 1998.