Birla Institute of Technology & Science, Pilani – K K Birla Goa Campus

First Semester: 2024-2025

Course Handout
August 6, 2024
Course No. : CS F422
Course Title: Parallel Computing
Instructor-in-Charge: Dr. Gargi Prabhu
E-mail: gargia@goa.bits-pilani.ac.in

Course Description:

This course provides an introduction to parallel computing, covering various mod-

els of parallel computers and their interconnection networks. Key topics include basic
communication operations and parallel algorithms, along with programming paradigms
specific to parallel systems. Students will explore the implementation challenges of
algorithms on parallel computers, learn parallel programming using the Message Pass-
ing Interface (MPI), and perform performance and scalability analyses. The course
also delves into fundamental design techniques for parallel algorithms and examines
parallel algorithms for tasks such as sorting, searching, merging, matrix algebra, graph
problems, discrete optimization, and computational geometry.

Scope & Objective:

This course offers a comprehensive, in-depth exploration of techniques for designing

and analyzing parallel algorithms, as well as programming them on available parallel
platforms. Key objectives include:
• Understanding the principles of parallel algorithm design and various parallel
programming models.
• Gaining proficiency in parallel programming languages such as MPI, OpenMP,
and CUDA.
• Developing skills necessary to design and analyze parallel algorithms.
• Appreciating the advantages and challenges of adapting algorithms to parallel or
distributed paradigms.
• Completing significant assignments outside of class time to apply theoretical
knowledge.
• Presenting and defending designed solutions, enhancing communication and crit-
ical thinking skills.
• Exploring the practical applications and real-world implications of parallel com-
puting in various domains.
• Enhancing problem-solving abilities through hands-on experience with complex
parallel computing tasks.

1
3. TextBook:

T1. Ananth Grama, Anshul Gupta, George Karypis and Vipin Kumar, Introduction to
Parallel Computing, Second Edition, Pearson Education

3. Reference Books:

R1. M J Quinn, Parallel Computing: Theory and Practice, Second Edition, Tata
McGraw-Hill
R2. David B. Kirk and Wen-mei W. Hwu, Programming Massively Parallel Proces-
sors, A Hands-on Approach, Second Edition, Elseveir
R3. J. Jaja, An Introduction to Parallel Algorithms, Addison-Wesley Professional
R4. M J Quinn, Parallel Programming in C with MPI and OpenMP, Tata McGraw-Hill
* Other reference books will be indicated as and when the context arises

4. Tentative Course Plan:

Learning Objectives Topics to be covered References Lecture No.

Introduction to parallel processing and parallel
processing terminology R1 , Class
1,2
Models of Parallel Computation: SIMD, MIMD Notes
Introduction to parallel computing,
PRAM (EREW, CREW,CRCW), NC
serial to parallel thinking
Contrast between Data Parallelism & Control R1, Class
3
Parallelism Notes
R1, Class
PRAM Algorithms 4-6
Notes
T1, Class
Physical Organization of parallel computer 7-8
Notes
Performance metrics for parallel Isoefficeincy function
Performance metrics for T1, Class
& system, scalability issues, Pipelining and Throughput, 9-12
parallel systems Notes
Latency and Latency hiding, Other scalability metrics
Multi-Core CPU programming OpenMP, MPI T1, Class Notes 13-17
Pointer Jumping, Divide-and-Conquer, Partitioning,
Basic Parallel Algorithmic R3, Class
Pipelining, Accelerated Cascading, Symmetry Breaking, 18-26
Techniques Notes
Synchronization (Locked, Lock-free), Example Applications
Introduction to CUDA Programming,
R2,
CUDA Programming CUDA Thread & Memory Organization, 27-31
Class Notes
Performance Considerations, Optimizations, Profiling
Studying & Analyzing
parallel versions of Min/Max,Sum T1, Class
32-40
standard sequential Searching, Merging, Sorting, Matrix Multiplication Notes
algorithms

2
5. Evaluation Scheme:

No. Evaluation Component Wt Date Time Details

1 Quiz 5% Announced later
1 Lab 10% Announced later
2 Assignment 20% Announced later
3 Mid Semester 25% Monday, 07/10/2024 Closed Book
4 Comprehensive 40% Monday, 09/12/2024 FN Cheat Sheet

6. Chamber Consultation: You can visit my office at D-159 on Tuesdays and Thurs-
days (excluding institute holidays) from 4:00 PM to 5:00 PM. Sending a prior email to
gargia@goa.bits-pilani.ac.in is appreciated.

7. Notices: All notices concerning this course will primarily be announced in class or
updated on the LMS as needed. For any clarifications, please contact gargia@goa.bits-
pilani.ac.in.

8. Assignment Policy: All assignments must be completed individually, reflecting

your own understanding and effort. Plagiarism will result in severe penalties. A viva
will be conducted to assess your grasp of the topics, significantly impacting your as-
signment grade.

9. Make-up Policy: Prior permission is required for genuine cases to qualify for a
make-up. Otherwise, zero marks will be awarded for that component without make-up.
Granting make-up is at the sole discretion of the IC.

Instructor-In-Charge, CS F422
Gargi Prabhu