University of Nizhni Novgorod

Faculty of Computational Mathematics & Cybernetics

Teaching Course: CS338. Introduction to Parallel Programming


Objectives:

The goal of the course is to study the mathematical models, methods and technologies of parallel programming for multiprocessor systems. Learning the course is sufficient for a successful start to practise in the area of parallel programming.

Course Overview:

The spectrum of knowledge and skills presented in the course provides the solid basis for developing parallel software system and includes the following topics:

1.      Overview of parallel computer architectures,

2.      Modeling and analysis of parallel computations,

3.      Parallel algorithm and software design,

4.      Technologies of parallel program development,

5.  nbsp;   Parallel algorithms for solving time-consuming problems.

The theoretical lessons are accompanied by an enhanced laboratory practicum.

Author:

Gergel P. Victor, Prof., D.Sc.

http://www.software.unn.ac.ru/?dir=17 (in Russian)

E-mail: gergel@unn.ru
Author's Team

Prerequisites:

The students are supposed to know the following:

-        CS101 "Introduction to Programming ",

-        CS105 "Discrete mathematics",

-        CS220 "Computer Architecture",

-        CS225"Operating Systems",

-        CS304 "Numerical Methods ".

Experience with programming in C is required in order to carry out the laboratory works.

Course Syllabus: (36 hours)

·        Introduction to Parallel Programming (1 hour)

·        Overview of Parallel System Architectures (3 hours)

·        Modeling and Analysis of Parallel Computations (4 hours)

·        Communication Complexity Analysis of Parallel Algorithms (4 hours)

·        Parallel Programming with MPI (6 hours)

·        Parallel Programming with OpenMP (4 hours)

·        Principles of Parallel Algorithm Design (2 hours)

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

·        Modeling the parallel program executing (4 hours)

See Extended Course Syllabus

Overview of Laboratory Works:

·        Parallel Programming with MPI  (4 hours)

·        Parallel Programming with OpenMP  (4 hours)

·        Laboratory works for estimating the parallel method efficiency with the use of the ParaLab system (2 hours)

·        Laboratory works for developing the parallel algorithms and programs (14 hours)

·        Laboratory works for parallel solving partial differential equations (4 hours)

·        Laboratory works for studying the parallel method libraries (4 hours)

·        Laboratory works for parallel solving the problem of multidimensional multiextremal optimization  (4 hours)

See Extended Overview of Laboratory Works

Laboratory Works with the use of the system ParaLab.

Questions for Discussions.

Exercises.

Assignments:

Besides doing exercises after detailed explanation given by the instructor, each student is supposed to solve independently 3 problems of different level of complexity while doing the laboratory works (self-study training):

·        Two of these exercises should be intended for the development of parallel programs for shared and distributed memory systems and are aimed at mastering the technologies OpenMP and MPI correspondingly. The problems for these type of assignments can be taken in Sections 4 and 5 of the educational materials of the course.

·        The third exercise should consist in the development of parallel program for any algorithm of those discussed in Sections 7-12 of the educational materials of the course.

Course project:

The work on the course project is the final stage of studies within the frames of the course. Doing this work each student should carry out the complete cycle of the parallel software development for soling the problems of sufficiently high level of complexity:

See Project Requirements

Exams:

The course ends up with an oral examination. The questions and the problems for the exam are formulated on the basis of the course content. The final grade is given to students with regard to all the results achieved:

-        Attendance of lectures – 10%,

-        Participation in practical and laboratory works - 10%,

-        Assignments - 20%,

-        Project - 30%,

-        Exam - 30%.

References:

Educational materials for the course.

Quinn, M. J. (2004). Parallel Programming in C with MPI and OpenMP.New York, NY: McGraw-Hill.

Grama, A., Gupta, A., Kumar V. (2003, 2nd edn.). Introduction to Parallel Computing.Harlow, England: Addison-Wesley.

Pacheco, P. (1996). Parallel Programming with MPI. - Morgan Kaufmann.

Chandra, R., Dagum, L., Kohr, D., Maydan, D., McDonald, J., and Melon, R. (2000). Parallel Programming in OpenMP. Morgan Kaufmann Publishers.

Culler, D., Singh, J.P., Gupta, A. (1998) Parallel Computer Architecture: A Hardware/Software Approach. - Morgan Kaufmann.

Tanenbaum, A. (2001). Modern Operating System. 2nd edn. – Prentice Hall

The complete survey of the publications, which may be useful in studying the course, is given in the educational materials of the course.

Course description in accordance with the recommendations CC 2001:

AL4     Distributed algorithms                                                  3 hours (out of 3)

AL11   Parallel algorithms                                                                   4 hours

AR7     Multiprocessor architectures                                                   1 hours (out of 3)

AR8     Performance enhancements                                                     2 hours

OS3     Concurrency                                                                           4 hours (out of 6)

NC1    Introduction to net-centric computing                           2 hours (out of 2)

CN1    Numeric analysis                                                                     4 hours 

CN4    High-performance computing                                      12 hours