Parallel Computing

Course Title: Parallel Computing

Course No: CSIT.421

Nature of the Course: Theory + Lab

Semester: 8

Full Marks: 60 + 20 + 20

Pass Marks: 24 + 10 + 10

Credit Hours: 3

Course Description

In a parallel computation, multiple processors work together to solve a given problem. This course will describe different techniques used to solve the problems, in order to develop efficient parallel algorithms for a variety of problems. We will also pay much attention to practical aspects of implementing parallel code that actually yields good performance on real parallel machines.

Course Objectives

Describe different parallel architectures; inter-connect networks, programming models, and algorithms for common operations. Develop an efficient parallel algorithm to solve a problem and analyze its time complexity. Implement parallel algorithms using MPI, OpenMP, pthreads. Analyze parallel code performance, determine computational bottlenecks, and optimize the code.

Course Contents

1. Parallel Programming

5 hrs

1.1. Introduction to parallel programming, data parallelism, functional parallelism, pipelining

1.2. Flynn's taxonomy, parallel algorithm design – task/channel model , Foster's design methodology

1.3. Case studies

boundary value problem

finding the, maximum – Speedup and efficiency

Amdahl's law

Gustafson Barsis's Law

Karp-Flatt Metric

Isoefficiency metric

2. Message Passing Programming

10 hrs

2.1. The message-passing model, the message-passing interface, MPI standard, basic concepts of MPI

2.2. Timing the MPI programs: MPI_Wtime, MPI_Wtick, collective, communication: MPI_Reduce, MPI_Barrier, MPI_Bcast, MPI_Gather, MPI_Scatter

2.3. Case studies

the sieve of Eratosthenes

Floyd's algorithm

Matrix-vector multiplication

3. Shared Memory Programming

10 hrs

3.1. Shared-memory model, OpenMP standard, parallel for loops, parallel for pragma, private variables, critical sections

3.2. Reductions, parallel loop optimizations, general, data parallelism, functional parallelism

3.3. Case studies

the sieve of Eratosthenes

Floyd's algorithm

matrix-vector multiplication

distributed shared-memory programming

DSM primitives

4. Parallel Algorithms I

10 hrs

4.1. Monte Carlo methods, parallel random number generators, random number distributions

4.2. Case studies

Matrix multiplication

row-wise block-stripped algorithm

Cannon's algorithm

solving linear systems

back substitution

Gaussian elimination

iterative methods

conjugate gradient method

5. Parallel Algorithms II

10 hrs

5.1. Sorting algorithms

quicksort

parallel quicksort

hyper quicksort

sorting by regular sampling

5.2. Fast fourier transform, combinatorial search, divide and conquer, parallel backtrack search, parallel branch and bound, parallel alpha-beta search.

Laboratory Works

Students should practice small scale parallel programs, message passing programs, and shared memory programs. Besides this student should implement parallel algorithms discussed in the course.

1.Small Scale Parallel Programs
2.Algorithm Implementation

Text Books

1.Michael J. Quinn, 'Parallel Programming in C with MPI and OpenMP', Tata McGraw-Hill Publishing Company Ltd., 2003.

Reference Books

1.B. Wilkinson and M. Allen, 'Parallel Programming – Techniques and applications using networked workstations and parallel computers', Second Edition, Pearson Education, 2005.
2.M. J. Quinn, 'Parallel Computing – Theory and Practice', Second Edition, Tata McGraw-Hill Publishing Company Ltd., 2002.

Notes:

This syllabus follows the official CSIT curriculum of Far Western University. In case of any doubt or revision, the university's published syllabus shall be considered authoritative. https://cdc.fwu.edu.np/faculties.html

Parallel Computing

Parallel Computing

Select University

Select Program

TabFlux . Parallel Computing . FWU . BSc. CSIT