Parallel algorithms

Garant předmětu:

Přemysl Šůcha

Lecturer:

Přemysl Šůcha

Tutor:

Nikolai Antonov, Michal Bouška, Jan Dvořák, Martin Henych, István Módos, Petr Stejskal, Přemysl Šůcha

Supervisor:

Department of Control Engineering

Synopsis:

In the introductory lectures, we will focus on general approaches to design of parallel algorithms and their properties important for understanding the fundamental principles of parallel and distributed algorithms. Subsequently we will talk about fundamental parallel algorithms; typically, constituting cornerstones of algorithms for real-world problems. The laboratory exercise will be aimed at hardware platform commonly used in practice.

Requirements:

Basic competence in C++ programming and algorithmization.

Syllabus of lectures:

1. Introduction to parallel computing

2. Principles of parallel and distributed algorithms design

3. Basic communication operations

4. Properties of parallel algorithms

5. Matrix Algorithms

6. Algorithms for Linear Algebra

7. Sorting, TEST

8. Parallel accelerators

9. Graph algorithms I.

10. Graph algorithms II.

11. Combinatorial algorithms

12. Dynamic programming

13. Fast Fourier transform

Syllabus of tutorials:

1. Introduction to parallel programming, environment setting

2. Introduction to Cpp11 threads

3. Advanced constructs in Cpp11

4. Assignment of the semestral work + homework 1

5. OpenMP - basic constructs

6. OpenMP - vectorization, parallel sort

7. Homework 2, deadline for homework 1

8. Semestral work - consultation

9. OpenMPI - distributed algorithms

10. Homework 3, deadline for homework 2

11. Semestral work - consultation

12. Presentations of semestral works

13. deadline for homework 3, student assessment

Study Objective:

Study materials:

[1] Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar: Introduction to Parallel Computing, Second Edition, Addison Wesley, 2003.

[2] Georg Hager, Gerhard Wellein: Introduction to High Performance Computing for Scientists and Engineers, CRC Press, 2011.

[3] James Reinders, Jim Jeffers: Intel Xeon Phi Coprocessor High-Performance Programming, Newnes, 2013.

Note:

Further information:

https://cw.fel.cvut.cz/wiki/courses/b4m35pag/start

Time-table for winter semester 2024/2025:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon
Tue	roomT2:C3-132 Šůcha P. 12:45–14:15 (lecture parallel1) Dejvice T2:C3-132
Wed	roomT2:H1-131 Stejskal P. 09:15–10:45 (lecture parallel1 parallel nr.101) Dejvice haly AlgDejviceroomT2:H1-131 Antonov N. 11:00–12:30 (lecture parallel1 parallel nr.102) Dejvice haly AlgDejviceroomT2:H1-131 16:15–17:45 (lecture parallel1 parallel nr.104) Dejvice haly AlgDejvice
Thu
Fri

Time-table for summer semester 2024/2025:

Time-table is not available yet

The course is a part of the following study plans:

• Open Informatics - Computer Engineering (compulsory course of the specialization)
• Open Informatics - Software Engineering (compulsory course of the specialization)