Gurantor department | Department of Computer Science | Credits | 4 |

Subject guarantor | prof. Ing. Pavel Krömer, Ph.D. | Subject version guarantor | prof. Ing. Pavel Krömer, Ph.D. |

Study level | undergraduate or graduate | Requirement | Optional |

Year | 1 | Semester | winter |

Study language | Czech | ||

Year of introduction | 2022/2023 | Year of cancellation | |

Intended for the faculties | FEI | Intended for study types | Follow-up Master |

Instruction secured by | |||
---|---|---|---|

Login | Name | Tuitor | Teacher giving lectures |

CHV0037 | Ing. Štěpán Chvatík | ||

KRO080 | prof. Ing. Pavel Krömer, Ph.D. |

Extent of instruction for forms of study | ||
---|---|---|

Form of study | Way of compl. | Extent |

Full-time | Graded credit | 2+2 |

Part-time | Graded credit | 18+0 |

An overview of design, implementation, and evaluation of parallel algorithms. Practical use of programming techniques for selected parallel architectures. Working knowledge of parallel systems and programming. In particular, design of parallel algorithms and parallelization of sequential ones. Implementation of parallel algorithms based on message passing. Analysis and evaluation of parallel algorithms. Optimization and improvement of efficiency.

Lectures

Tutorials

This 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 parallel hardware, from supercomputers with distributed memory through multicore processors to floating point accelerators and general purpose graphic processing units, to solve computationally extensive problems from different application areas.
An emphasis is put on the introduction to standard parallel paradigms, interfaces, languages, and libraries, as well as on the reflection of the actual development in the field by providing overview of the latest parallel platforms and environments. Parallel programming of distributed memory systems (i.e. the message passing model), shared memory systems (symmetric multiprocessors), and floating-point accelerators will be presented. However, cloud platforms, map-reduce model, and parallel Matlab will be discussed as well.
The tutorials will be devoted to practical design and implementation of parallel algorithms with the help of MPI, OpenMP, UPC, CUDA-C, or parallel Matlab.

1. PA I lecture notes
2. Introduction to Parallel Computing: From Algorithms to Programming on State-of-the-Art Platforms. Roman Trobec, Boštjan Slivnik, Patricio Bulić, Borut Robič. Springer Nature Switzerland, 2018
3. Parallel Programming for Multicore and Cluster Systems. Thomas Rauber, Gudula Rünger. Springer-Verlag Berlin Heidelberg, 2013
4. Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering. Ian Foster, Addison Wesley, 1995

1. The OpenMP Common Core: Making OpenMP Simple Again, Timothy G. Mattson, Yun He, Alice E. Koniges. MIT Press, 2019
2. Using OpenMP-The Next Step: Affinity, Accelerators, Tasking, and SIMD. Ruud van der Pas, Eric Stotzer, and Christian Terboven. MIT Press, 2017
3. Distributed Systems (3rd ed.), Andrew S. Tanenbaum, Maarten van Steen, 2017
4. Distributed Computing Principles, Algorithms, and Systems, Ajay D. Kshemkalyani, Mukesh Singhal, Cambridge, 2008
5. Patterns for parallel programming. Timothy Mattson, Beverly Sanders, Berna Massingill, Addison-Wesley, 2004
6. Introduction to Parallel Computing (2nd Edition). Ananth Grama, George Karypis, Vipin Kumar, Anshul Gupta, Addison-Wesley, 2003

Each student will conceive and submit three assignments on topics related to parallel algorithms. The topics of the assignments will include parallel solutions to complex problems and the application of different parallel methods and techniques. The students will work on the assignments continuously during the course of the term. There will be a possibility to consult the progress and the solutions at the lectures, seminars, individual consultations, and by email.

No additional requirements.

Subject has no prerequisities.

Subject has no co-requisities.

Lectures:
1. Introduction to parallel programming. Concurrency, pseudoparallelism, parallelism. Processes and threads. Processes and threads from the operating system perspective. SIMD and FMA instructions of modern processors.
2. Sequential vs. parallel programming. Parallel programming caveats. Typical issues of parallel programs. Synchronization and mutual exclusion. Deadlock (definition, properties, conditions, detection, elimination).
3. Classification of parallel systems. Shared memory systems and distributed memory systems. Flynn's taxonomy. Data parallel and task-parallel problems.
4. Shared memory systems programming. Threads in Java, C#, C++11, and Python. The fork-join model and the OpenMP interface.
5. Distributed memory systems programming. Message passing. Posix queues, sockets. The MPI interface, fundamental MPI operations.
6. Other options for distributed memory systems: bulk synchronous parallel and partitioned global address space models.
7. Introduction to the accelerator and co-processor programming. Computation offloading. GPGPU architecture (program organization, memory organization). Data parallelism on the GPU. CUDA platform and CUDA-C language. The OpenACC interface.
8. Parallel algorithm design. Task/channel parallel computation model. Foster's design methodology (partitioning, communication, agglomeration, mapping) and its use.
9. Parallel programming patterns: finding concurrency, algorithm structure, implementation. Typical scenarios: independent tasks, replicable, reduction, divide and conquer, pipeline.
10. Representation and analysis of parallel algorithms (parallel random-access machine, bulk synchronous parallel, informal work depth, etc.). Performance and effectiveness of parallel algorithms.
11. Parallel data structures: stack, queue, pool, linked list, hash table, trees, priorities. Major differences from sequential variants.
12. Algorithms for selected problems: prefix-sum, merging, search (orthogonal trees, sorting networks). Major differences between sequential, naive parallel, and efficient parallel solutions.
13. Data structures and algorithms for parallel search: 2-3 tree, pipelining. Parallel search, insertion, and deletion.
14. Parallel algorithms and data structures for graph problems. Graph traversal, search for shortest paths, connectivity, independent components, etc.
Seminars:
The seminars take place in computer labs and are dedicated to practical examples of the introduced concepts. Students work in the course of the term on the following assignments:
1. Computationally expensive task solved with and without parallelism. The traveling salesman problem: from naive parallelism (brute-force) to more advanced solution with inter-process communication (simple parallel branch-and-bound).
2. Data parallelism and big data processing. Data decomposition, data-parallel approach, vectorization. Parallel matrix operations, clustering.
3. Parallel image processing and the impact of local dependences on parallel algorithms (convolution). Parallel seam carving.
4. A parallel approach to graph algorithms, graphs, and non-linear data structures. Parallel implementation of the iterative version of the PageRank algorithm.

Task name | Type of task | Max. number of points
(act. for subtasks) | Min. number of points | Max. počet pokusů |
---|---|---|---|---|

Graded credit | Graded credit | 100 | 51 | 3 |

Show history

Conditions for subject completion and attendance at the exercises within ISP: Completion of all mandatory tasks within individually agreed deadlines.

Show history

Academic year | Programme | Branch/spec. | Spec. | Zaměření | Form | Study language | Tut. centre | Year | W | S | Type of duty | |
---|---|---|---|---|---|---|---|---|---|---|---|---|

2024/2025 | (N0613A140034) Computer Science | INF | P | Czech | Ostrava | 1 | Compulsory | study plan | ||||

2024/2025 | (N0613A140034) Computer Science | INF | K | Czech | Ostrava | 1 | Compulsory | study plan | ||||

2024/2025 | (N0688A140014) Industry 4.0 | P | Czech | Ostrava | 2 | Choice-compulsory type B | study plan | |||||

2024/2025 | (N0541A170007) Computational and Applied Mathematics | (S01) Applied Mathematics | K | Czech | Ostrava | 1 | Optional | study plan | ||||

2024/2025 | (N0541A170007) Computational and Applied Mathematics | (S01) Applied Mathematics | P | Czech | Ostrava | 1 | Optional | study plan | ||||

2024/2025 | (N0541A170007) Computational and Applied Mathematics | (S02) Computational Methods and HPC | P | Czech | Ostrava | 1 | Optional | study plan | ||||

2024/2025 | (N0541A170007) Computational and Applied Mathematics | (S02) Computational Methods and HPC | K | Czech | Ostrava | 1 | Optional | study plan | ||||

2023/2024 | (N0688A140014) Industry 4.0 | P | Czech | Ostrava | 2 | Choice-compulsory type B | study plan | |||||

2023/2024 | (N0613A140034) Computer Science | INF | K | Czech | Ostrava | 1 | Compulsory | study plan | ||||

2023/2024 | (N0613A140034) Computer Science | INF | P | Czech | Ostrava | 1 | Compulsory | study plan | ||||

2023/2024 | (N0541A170007) Computational and Applied Mathematics | (S01) Applied Mathematics | P | Czech | Ostrava | 1 | Optional | study plan | ||||

2023/2024 | (N0541A170007) Computational and Applied Mathematics | (S01) Applied Mathematics | K | Czech | Ostrava | 1 | Optional | study plan | ||||

2023/2024 | (N0541A170007) Computational and Applied Mathematics | (S02) Computational Methods and HPC | P | Czech | Ostrava | 1 | Optional | study plan | ||||

2023/2024 | (N0541A170007) Computational and Applied Mathematics | (S02) Computational Methods and HPC | K | Czech | Ostrava | 1 | Optional | study plan | ||||

2023/2024 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | P | Czech | Ostrava | Choice-compulsory | study plan | |||||

2023/2024 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | K | Czech | Ostrava | Choice-compulsory | study plan | |||||

2022/2023 | (N0613A140034) Computer Science | INF | K | Czech | Ostrava | 1 | Compulsory | study plan | ||||

2022/2023 | (N0613A140034) Computer Science | INF | P | Czech | Ostrava | 1 | Compulsory | study plan | ||||

2022/2023 | (N0688A140014) Industry 4.0 | P | Czech | Ostrava | 2 | Choice-compulsory type B | study plan | |||||

2022/2023 | (N0541A170007) Computational and Applied Mathematics | (S01) Applied Mathematics | K | Czech | Ostrava | 1 | Optional | study plan | ||||

2022/2023 | (N0541A170007) Computational and Applied Mathematics | (S01) Applied Mathematics | P | Czech | Ostrava | 1 | Optional | study plan | ||||

2022/2023 | (N0541A170007) Computational and Applied Mathematics | (S02) Computational Methods and HPC | K | Czech | Ostrava | 1 | Optional | study plan | ||||

2022/2023 | (N0541A170007) Computational and Applied Mathematics | (S02) Computational Methods and HPC | P | Czech | Ostrava | 1 | Optional | study plan | ||||

2022/2023 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | P | Czech | Ostrava | Choice-compulsory | study plan | |||||

2022/2023 | (N2647) Information and Communication Technology | (2612T025) Computer Science and Technology | K | Czech | Ostrava | Choice-compulsory | study plan |

Block name | Academic year | Form of study | Study language | Year | W | S | Type of block | Block owner |
---|

2023/2024 Winter |

2022/2023 Winter |