9600-1006/01 – Parallel Algorithms (PAL)
| Gurantor department | IT4Innovations | Credits | 4 |
| Subject guarantor | RNDr. Ondřej Jakl, CSc. | Subject version guarantor | RNDr. Ondřej Jakl, CSc. |
| Study level | undergraduate or graduate | Requirement | Compulsory |
| Year | 1 | Semester | summer |
| | Study language | Czech |
| Year of introduction | 2016/2017 | Year of cancellation | |
| Intended for the faculties | USP | Intended for study types | Follow-up Master |
Subject aims expressed by acquired skills and competences
Upon the successful completion of the course students will be able to actively use new terms in the field of parallel algorithms.
Teaching methods
Lectures
Tutorials
Summary
The course will provide students with an overview of the field of parallel applications development, including models of parallel processing dependant on the target parallel architecture, methods of parallel applications development, implementation methods, or parallel codes evaluation. The theory will be demonstrated on particular practical algorithms.
Compulsory literature:
1. Principles of Parallel Algorithm Design, http://www.parallel-algorithms-book.com/
2. Xavier, S. S. Iyengar, Introduction to Parallel Algorithms, John Wiley & Sons, 1998, pages: 365.
Recommended literature:
Appropriate resources from the Internet.
Way of continuous check of knowledge in the course of semester
E-learning
Other requirements
Knowledge of algorithms development and C/C++.
Prerequisities
Subject has no prerequisities.
Co-requisities
Subject has no co-requisities.
Subject syllabus:
1. Introduction.
Parallel processing and High Performance Computing (HPC). Parallel versus distributed processing. Parallel architectures, classification and impacts on parallel processing.
2. Introduction to Programming Parallel applications.
Parallel Programming models: Message passing, Shared memory, Data-parallel access. Examples of Application, advantages, and disadvantages. Overview of implementation environment and programming tools.
3. Message Passing Model.
Principles and characteristics of Message passing model. Types of Communication, basic terms. Implementation pre-requisites. Message Passing Systems as the model realization. Message Passing Interface (MPI).
4. Methods of Parallel Application Development.
Foster Methods. Data and Functional Decomposition. Communication Analysis, Perfectly Parallel problems. Agglomeration and Granulity, Processor Mapping.
5. Analysis of Parallel Algorithms.
Performance Models and Metrics. Parallel Codes Execution Time. Speed-up, Efficiency, and Costs. Superlinear Speed-up and its Causes. Amdahl’s and Gustafson’s Law.
6. Analysis of Parallel Algorithms (continuation).
Scaleability, Rigid and variable size of a problem. Asymptotic analysis. Experiments, Benchmarking.
7. Perfectly-parallel computations.
Ideal Parallelization. Monte Carlo Methods. Further Examples.
8. Decomposition and a Method called “Divide and Rule”
Decomposition Strategy. Numerical Integration. Further Examples.
9. Pipelining.
Principle of Pipelining. Prime Numbers Generation. Further Examples
10. Synchronized Computations.
Synchronized Constructs. Data-parallel Computations. Heat Transfer Problem. Further Examples.
11. Load Balancing and Termination Detection.
Centralized and Decentralized schemes. Mapping for Load Balancing. Shortest-Way Problem. Further Examples.
12. Shared Memory Programming.
Shared Variables Model. Technical Requirements. Threads and low-level Synchronization Primitives. Standard OpenMP. Automatic Parallelization.
Conditions for subject completion
Conditions for completion are defined only for particular subject version and form of study
Occurrence in study plans
Occurrence in special blocks
Assessment of instruction
Předmět neobsahuje žádné hodnocení.