9600-1006/01 – Parallel Algorithms (PAL)

Gurantor departmentIT4InnovationsCredits4
Subject guarantorRNDr. Ondřej Jakl, CSc.Subject version guarantorRNDr. Ondřej Jakl, CSc.
Study levelundergraduate or graduateRequirementCompulsory
Year1Semestersummer
Study languageCzech
Year of introduction2016/2017Year of cancellation
Intended for the facultiesUSPIntended for study typesFollow-up Master
Instruction secured by
LoginNameTuitorTeacher giving lectures
JAK58 RNDr. Ondřej Jakl, CSc.
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Credit and Examination 2+2

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

Další požadavky na studenta

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

Full-time form (validity from: 2016/2017 Summer semester, validity until: 2017/2018 Summer semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Credit and Examination Credit and Examination 100 (100) 51
        Credit Credit 45  20
        Examination Examination 55  25
Mandatory attendence parzicipation: Active participation

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.FormStudy language Tut. centreYearWSType of duty
2018/2019 (N2658) Computational Sciences (2612T078) Computational Sciences P Czech Ostrava 1 Compulsory study plan
2017/2018 (N2658) Computational Sciences (2612T078) Computational Sciences P Czech Ostrava 1 Compulsory study plan
2016/2017 (N2658) Computational Sciences (2612T078) Computational Sciences P Czech Ostrava 1 Compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner