Parallel algorithms
Code  Completion  Credits  Range  Language 

BE4M35PAG  Z,ZK  6  2P+2S 
 Lecturer:
 Přemysl Šůcha (guarantor)
 Tutor:
 Přemysl Šůcha (guarantor), Michal Bouška, István Módos
 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 realworld 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 Algorithms Design
3. Basic Communication Operations
4. Analytical Modeling 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. Kayhan Erciyes: Distributed Graph Algorithms for Computer Networks, Springer, 2013.
3. Georg Hager, Gerhard Wellein: Introduction to High Performance Computing for Scientists and Engineers, CRC Press, 2011.
 Note:
 Further information:
 https://cw.fel.cvut.cz/wiki/courses/b4m35pag/start
 Timetable for winter semester 2019/2020:

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 Fri Thu Fri  Timetable for summer semester 2019/2020:
 Timetable is not available yet
 The course is a part of the following study plans:

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