Parallel and Distributed Computing

Course Title: Parallel and Distributed Computing
Full Marks: 45 + 30
Course No: C.Sc. 544
Pass Marks: 22.5 + 15
Nature of the Course: Theory + Lab
Credit Hrs: 3

Course Description:

This course covers a broad range of topics related to parallel and distributed computing, including foundations, models, and algorithms.

Course Contents:

Unit 1: Foundations:

1.1. Parallel and Distributed Computing: the Scene, the Props, the Players (2 hrs)

A Perspective, Parallel Processing Paradigms, Modeling and Characterizing Parallel Algorithms, Cost vs. Performance Evaluation, Software and General Purpose PDC

1.2. Semantics of Concurrent Programming (2 hrs)

Models of Concurrent Programming, Semantic Definitions, Axiomatic Semantic Definitions, Denotation Semantic Definitions, Operational Semantic Definitions

1.3. Formal Methods: A Petri Nets Bases Approach (2 hrs)

Process Algebras, PETRI Nets, High-Level New Models

1.4. Complexity Issues in Parallel and Distributed Computing ( 3 hrs)

Introduction, Turing Machines as the Basis and Consequences, Complexity Measures for Parallelism, Parallel Complexity Models and Resulting Classes, VLSI Computational Complexity, Complexity Measures for Distributed Systems, Neural Networks and Complexity Issues

1.5. Distributed Computing Theory (3 hrs)

The Computational Model, A Simple Example, Leader Election, Sparse Network Covers and Their Applications, Ordering of Events, Resource Allocation, Tolerating Processor Failures in Synchronous Systems, Tolerating Processor Failures in Asynchronous Systems, Other Types of Failures, Wait-Free Implementations of Shared Objects

Unit 2: Models

2.1. PRAM Models (5hrs)

Introduction; Techniques for the Design of Parallel Algorithms; The PRAM Model; Optimality and Efficiency of Parallel Algorithms; Basic PRAM Algorithms; The NC-Class; P-Completeness: Hardly Parallelizable Problems; Randomized Algorithms and Parallelism; List Ranking Revisited: Optimal O(log n) Deterministic List Ranking; Taxonomy of Parallel Algorithms; Deficiencies of the PRAM Model

2.2. Broadcasting with Selective Reduction: A Powerful Model of Parallel Computation (3 hrs)

Introduction; A Generalized BSR Model; One Criterion BSR Algorithms; Two Criteria BSR Algorithms; Three Criteria BSR Algorithms; Multiple Criteria BSR Algorithms

2.3. Dataflow Models (3 hrs)

Kinds of Data flow; Data-Driven Data flow Computing Models; Demand-driven Data flow Computing Models; Unifying Data-Driven and Demand-Driven

2.4. Partitioning and Scheduling (4 hrs)

Program Partitioning; Task Scheduling; Scheduling System Model; Communication Models; Optimal Scheduling Algorithms; Scheduling Heuristic Algorithms; Scheduling Nondeterministic Task Graphs; Scheduling Tools; Task Allocation; Heterogeneous Environments

2.5. Check pointing in Parallel and Distributed Systems (3 hrs)

Introduction; Check pointing Using Task Duplication; Techniques for Consistent Check pointing

2.6. Architecture for Open Distributed Software Systems (2 hrs)

Introduction to Open Distributed Systems Architecture; Computational Model; Engineering Model; ODP Application

Unit 3: Algorithms

3.1. Fundamentals of Parallel Algorithms (3 hrs)

Introduction; Models of Parallel Computation; Balanced Trees; Divide and Conquer; Partitioning; Combining

3.2. Parallel Graph Algorithms (5 hrs)

Graph-Theoretic Concepts and Notation; Tree Algorithms; Algorithms for General Graphs; Algorithms for Particular Classes of Graphs

3.3. Data Parallel Algorithms (5 hrs)

Chapter Overview; Machine Model; Impact of Data Distribution; CU/PE Overlap; Parallel Reduction Operations; Matrix and Vector Operations; Mapping Algorithms onto Partitionable Machines; Achieving Scalability Using Set of Algorithms

Recommended Books:

1. Parallel and Distributed Computing Handbook, Albert Y. Zomaya, Editor, McGraw-Hill
2. Introduction to Parallel Computing; Ananth Grama, Anshul Gupta, George Kaprypis, Vipin Kumar; Pearson Education
3. An Introduction to Parallel Programming, Peter Pacheco
4. Quinn, Michael J., Parallel Programming in C with MPI and OpenMP, McGraw-Hill, 2004.
5. Quinn, M., Parallel Computing: Theory and Practice, McGraw Hill, 1994.