University of Nizhni Novgorod

Faculty of Computational Mathematics & Cybernetics

Teaching Course: CS338. Introduction to Parallel Programming


Course Syllabus: (36 hours)

·        Introduction to Parallel Programming (1 hour)

Needs for  parallel computations. Challenges of parallel programming.

·        Overview of Parallel System Architectures (3 hours)

Overview of some parallel systems. Multiprocessors and multicomputers. Network topologies. Computer system classification. Clusters.

ppt01, doc01

·        Modeling and Analysis of Parallel Computations (4 hours)

Efficiency characteristics of parallel computation: speedup, efficiency, scalability. Modeling the computations in the form of the "operation-operand" graph. Model analysis: determining the parallel method execution time, estimating the maximum possible parallelization, computational load balancing. The Amdahl's and Gustavson-Barsis's laws. Aggregating the computation model.

ppt02, doc02

·        Communication Complexity Analysis of Parallel Algorithms (4 hours)

Network topology characteristics. Routing algorithms and data communication methods. Main communication operations. Logical (virtual) representation of network topology. Estimating the data communication time for clusters. 

ppt03, doc03

·        Parallel Programming with MPI (6 hours)

Overview of the MPI standard. Point-to-point communication operations. Synchronous and asynchronous modes of data transmission. Collective operations. Derived data types. Process management. Logical topologies. Case studies: matrix computations, solving partial differential equations.

ppt04_1, ppt04_2, ppt04_3, doc04

·        Parallel Programming with OpenMP (4 hours)

Overview of the OpenMP standard. Parallel regions. Computational load distributing among the threads. Shared and private data. Synchronization. OpenMP environment. Comparative consideration of various approaches to parallel programming for distributed and shared memory systems.

·        Principles of Parallel Algorithm Design (2 hours)

Parallel program modeling. Development stages: computation partitioning, analyzing the information dependencies, scaling and distributing computations among the processors. Case study: solving the gravitational problem of N bodies.

ppt06, doc06

·        Parallel algorithms for solving time consuming problems (8 hours)

Matrix computations:

-        Matrix-vector multiplication - ppt07, doc07,

-        Matrix multiplication - ppt08, doc08,

-        Solving the linear equation systems - ppt09, doc09).

Sorting - ppt10, ppt11, doc11.

Solving the partial differential equations - ppt12, doc12.

·        Modeling the parallel program executing (4 hours)

Representation of the parallel program as a system of processes carried out in parallel. Mutual exclusion in using the shared resources. Semaphores and monitors. Modeling the program state in the form of the "process-resource" graph. Model analysis: the detection and exclusion of deadlocks. Petri networks. Case studies: the "producer-consumer" problem, the "dining philosophers” problem etc.