![]() |
University of Nizhni NovgorodFaculty of Computational Mathematics & CyberneticsTeaching 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.
·
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.
·
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.
·
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.
·
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.