PARALLEL PROGRAMMING

The course presents both the hardware and software aspects of parallel programming. Related to the hardware aspect, the course covers the fundamental architecture models of the Flynn taxonomy and the data organization principles for each category. Related to the software aspect, the course firstly provides the general principles of parallel algorithm design. Afterwards, in a more specific way, the course describes how to design and implement programs in a shared-memory programming model using POSIX threads, OpenMP and Java multi-threading. Also the course describes how to design and implement programs in a distributed-memory programming model using MPI. Finally some advanced applications of parallel programming are studied, including the n body problem, sorting and graph problems.

Course aims is to teach students the principles, models, and techniques of parallel programming, enabling them to design, implement, and analyze efficient parallel programs on shared- and distributed-memory systems.

1. Concurrency vs Parallelism
2. Task vs Data Parallelism
3. Synchronization and Mutual Exclusion
4. Racing Condition Control
5. Amdahl’s Law
6. Taxonomy and Memory Types
7. Message Passing Models
8. Computer Architecture Taxonomy (Flynn)

1. Understand and explain the difference between concurrency and parallelism and identify types of parallelism.
2. Implement mutexes, critical sections, and barriers to avoid race conditions in parallel programs.
3. Compare shared, distributed, and hybrid memory systems, and select appropriate message passing strategies for a given problem.
4. Identify computer architectures using Flynn’s Taxonomy (SISD, SIMD, MIMD) and explain their suitability for parallel applications.
5. Implement and develop parallel versions of standard algorithms (sorting, matrix multiplication, reductions) and evaluate their efficiency.
6. Undestand and develop simple programs using shared memory (OpenMP) and message passing (MPI) paradigms.

Primary textbook: "Introduction to Parallel Programming book" by Peter Pacheco. Additinal textbook: "Introduction to Parallel Computing" by A.Grama, A.Gupta, G.Karypis, V.Kumar