460-4040/01 – Parallel Programming I (PPA I)

Gurantor departmentDepartment of Computer ScienceCredits4
Subject guarantordoc. Ing. Pavel Krömer, Ph.D.Subject version guarantordoc. Ing. Pavel Krömer, Ph.D.
Study levelundergraduate or graduate
Study languageCzech
Year of introduction2010/2011Year of cancellation2015/2016
Intended for the facultiesFEIIntended for study typesFollow-up Master
Instruction secured by
LoginNameTuitorTeacher giving lectures
KRO080 doc. Ing. Pavel Krömer, Ph.D.
PLA06 doc. Ing. Jan Platoš, Ph.D.
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Credit and Examination 2+2
Combined Credit and Examination 18+18

Subject aims expressed by acquired skills and competences

Survey in the field of design, realization and evaluation of parallel algorithms. Practical experience in parallel programming of selected multiprocessor computer systems. Working knowledge in the field of parallel systems and their programming, including: Design of parallel algorithms, parallelization of sequential algorithms. Practical realization of a parallel algorithm based on the message passing model. Analysis of the algorithm, evaluation of its implementation. Optimization and increasing of efficiency.

Teaching methods

Lectures
Individual consultations
Tutorials
Project work
Other activities

Summary

The course provides the students with working knowledge in the area of parallel systems, algorithms and programming. It concentrates on practical development of parallel codes so that the students can make effective use of the modern powerful hardware, from supercomputers to multicore notebooks, for solution of demanding tasks from various application fields. The so-called multicomputers, where the interaction of parallel processes is based on message passing, are focused on, but the specifics of shared-memory systems (symmetric multiprocessors) are discussed as well. Such a traditional techniques of parallel programming will be supplemented by an introduction to advanced technologies that were recently introduced, (e.g. GPGPU programming and parallel Matlab). Exercises are devoted to the design of parallel algorithms and their implementation in the PVM, MPI, OpenMP environment or possibly parallel Matlab, on the most powerful computer systems of VŠB-TUO/CVT, nowadays on the network of workstations Ultra with remote access to the 32-processor cluster Teri (128 cores) and to the four-processor symmetric multiprocessor Quad.

Compulsory literature:

Syllabus I. Foster: Designing and building of parallel programs. Addison-Wesley, 1995 Al Geist et al.: PVM: Parallel Virtual Machine. A User's Guide and Tutorial for Networked Parallel Computing. The MIT Press, 1994. MPI: A Message-Passing Interface Standard. Message Passing Interface Forum, University of Tennessee, June 1995.

Recommended literature:

K. Ježek et al.: Paralelní architektury a programy. ZČU Plzeň, 1997. (In Czech) B. Wilkinson, M. Allen: Parallel Programming. Prentice Hall, 1999. R. Chandra et al.: Parallel Programming in OpenMP. Morgan Kaufmann Publishers, 2001.

Way of continuous check of knowledge in the course of semester

E-learning

Další požadavky na studenta

Additional requirements are placed on the student.

Prerequisities

Subject has no prerequisities.

Co-requisities

Subject has no co-requisities.

Subject syllabus:

Lectures: Introduction. Motivation, historical remarks, actual trends. Relation to High Performance Computing. Area of interest. Assumed knowledge. Parallel computer systems. Flynn's classification and memory-related categories. Used terminology. Review of architectures. Examples of supercomputers. Clusters. Interconnection subsystems. Technical solutions (bus, hypercube, multistage network, etc.). Consequences for the design of parallel algorithms. Introduction to parallel programming. Parallel programming models (overview): message passing, shared variables, data parallel approach. Examples. Implementation tools. Building a parallel application. Message passing model. Principles and characteristics. Types of communication, basic concepts. Implementation conditions. Message passing systems, major representatives. Parallel Virtual Machine. Introduction to PVM. Historical remarks. Components and user's interface. Available implementations (Quad, Ultra). Illustrative example. Parallel Virtual Machine (continued). Overview of constructs and library routines: process control, information retrieval, message passing, etc. Collective communication. Advanced techniques. Development of parallel algorithms. Domain, functional decomposition. Communication analysis. Agglomeration. Mapping onto processors. Load-balancing techniques. Examples, perfectly parallel problems. Application in semester projects. Message Passing Interface. Development of the MPI standard. Comparison with PVM, specific features (derived datatypes, virtual topologies, etc.). Analysis of parallel algorithms. Performance models, metrics. Parallel execution time. Speedup, efficiency, cost. Superlinear speedup. Amdahl's law. Experimental studies. Analysis of parallel algorithms (continued). Scalability, fixed and variable problem size. Asymptotic analysis. Programming of symmetric processors. Technical conditions. Low-level tools, operating system bindings. Thread-based programming. The OpenMP standard. Motivation and historical remarks. Constructs (parallel regions, load-balancing directives, synchronization, locking...). Example. Selected parallel algorithms. Numerical algorithms, sorting, graph algorithms and other applications. Summary and trends. Alternative tools for the development of parallel applications (High Performance Fortran, Parallel Matlab, etc.). Developments in hardware. Parallel programming on personal computers. Computer labs: Tutorial organization. "Parallel thinking". Working environment. Multiprocesor Quad and network of workstations Ultra. Building parallel codes in PVM. Simple programs under PVM. Domain decomposition. Project consultations (throughout all labs). Domain decomposition (cont.). Functional decomposition. Collective communication in v PVM. XPVM. Analysis of algorithms. MPI. MPICH, LAM implementations. MPI (cont.). Collective communication. Advanced techniques. Presentations. Projects.

Conditions for subject completion

Conditions for completion are defined only for particular subject version and form of study

Occurrence in study plans

Academic yearProgrammeField of studySpec.FormStudy language Tut. centreYearWSType of duty
2014/2015 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 1 Optional study plan
2014/2015 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Optional study plan
2014/2015 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 1 Optional study plan
2014/2015 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Optional study plan
2013/2014 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 1 Optional study plan
2013/2014 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 1 Optional study plan
2013/2014 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Optional study plan
2013/2014 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Optional study plan
2012/2013 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 1 Optional study plan
2012/2013 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Optional study plan
2012/2013 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Optional study plan
2012/2013 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 1 Optional study plan
2011/2012 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 1 Optional study plan
2011/2012 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2011/2012 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2011/2012 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 1 Optional study plan
2010/2011 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 1 Optional study plan
2010/2011 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 1 Optional study plan
2010/2011 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2010/2011 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner