460-4118/01 – Parallel Algorithms II (PA II)

Gurantor departmentDepartment of Computer ScienceCredits4
Subject guarantordoc. Ing. Petr Gajdoš, Ph.D.Subject version guarantordoc. Ing. Petr Gajdoš, Ph.D.
Study levelundergraduate or graduateRequirementChoice-compulsory
YearSemestersummer
Study languageCzech
Year of introduction2015/2016Year of cancellation
Intended for the facultiesFEIIntended for study typesFollow-up Master
Instruction secured by
LoginNameTuitorTeacher giving lectures
GAJ03 doc. Ing. Petr Gajdoš, Ph.D.
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Graded credit 2+2
Combined Graded credit 10+5

Subject aims expressed by acquired skills and competences

The main goal consists in the knowledge extension in the area of programming of parallel applications. The lessons extend an existing subject (Parallel Algorithms I). All topics will be focused on usage of graphic processor units (GPU). Students will be familiar with existing architectures of GPUs and frameworks for parallel programming. The CUDA architecture will be explained in more detail with the respect to the fact, that nVidia Research Center has arisen on VŠB-TU Ostrava. Students get necessary knowledge to be able to solve practical tasks with the usage of GPU. They can use it in their diploma work or in several grant projects running on VŠB-TU Ostrava. Knowledge and skills: - orientation in the basic concept of architecture of graphic processors - knowledge in software architecture of parallel program, problem decomposition into grids, blocks and threads - knowledge in selected framework for parallel programming on GPU - understanding of algorithm conversion from serial to parallel form - task distribution over several GPUs, clusters - students should be able to solve practical tasks in the area of data processing

Teaching methods

Lectures
Individual consultations
Tutorials

Summary

The subject follows an existing one called Parallel Algorithms I. Acquired knowledge makes a presumption for understanding of new topics. Selected lecture notes give a ground for practical exercises. nVidia CUDA architecture will be presented in more detail will related tools for parallel programming on GPU. Assumption of parallel programming technics in combination with solving of practical tasks makes the most important premises to pass the final exam.

Compulsory literature:

[1] Bjarne Stroustrup. The C++ Programming Language, 4th Edition. Addison-Wesley Professional, 4th edition, 5 2013. [2] Graham Sellers, Richard S. Wright, and Nicholas Haemel. OpenGL SuperBible: Comprehensive Tutorial and Reference (6th Edition). Addison-Wesley Professional, 6th edition, 7 2013. [3] John Cheng, Max Grossman, and Ty McKercher. Professional CUDA C Programming. Wrox, 1st edition, 9 2014.

Recommended literature:

[1] Bjarne Stroustrup. The C++ Programming Language, 4th Edition. Addison-Wesley Professional, 4th edition, 5 2013. [2] Graham Sellers, Richard S. Wright, and Nicholas Haemel. OpenGL SuperBible: Comprehensive Tutorial and Reference (6th Edition). Addison-Wesley Professional, 6th edition, 7 2013. [3] John Cheng, Max Grossman, and Ty McKercher. Professional CUDA C Programming. Wrox, 1st edition, 9 2014. [4] Shane Cook. CUDA Programming: A Developer's Guide to Parallel Computing with GPUs (Applications of Gpu Computing). Morgan Kaufmann, 1st edition, 11 2012. [5] Anton Gerdelan. Anton's opengl 4 tutorials, 6 2014. [6] Volodymyr Kindratenko, editor. Numerical Computations with GPUs. Springer, 2014 edition, 7 2014. [7] David B. Kirk and Wen mei W. Hwu. Programming Massively Parallel Processors, Second Edition: A Hands-on Approach. Morgan Kaufmann, 2nd edition, 12 2012. [8] Timothy G. Mattson, Beverly A. Sanders, and Berna L. Massingill. Patterns for Parallel Programming. Addison-Wesley Professional, 1st edition, 9 2004. [9] Michael McCool, James Reinders, and Arch Robison. Structured Parallel Programming: Patterns for Ecient Computation. Morgan Kaufmann, 1st edition, 7 2012. [10] Peter Pacheco. An Introduction to Parallel Programming. Morgan Kaufmann, 1st edition, 1 2011. [11] Jason Sanders and Edward Kandrot. CUDA by Example: An Introduction to General-Purpose GPU Programming. Addison-Wesley Professional, 1st edition, 7 2010. [12] Jung W. Suh and Youngmin Kim. Accelerating MATLAB with GPU Computing: A Primer with Examples. Morgan Kaufmann, 1st edition, 12 2013. [13] Tom White. Hadoop: The Definitive Guide. Yahoo Press, 3rd edition, 5 2012. [14] Nicholas Wilt. CUDA Handbook: A Comprehensive Guide to GPU Programming, The. Addison-Wesley Professional, 1st edition, 6 2013.

Way of continuous check of knowledge in the course of semester

A Student will work alone on an associated task/project. The solution of the project will be checked during semester. The final evaluation of all achieved results will be done at the end of semester.

E-learning

Další požadavky na studenta

It is supposed that the student has knowledge in C, C++ programming. Good knowledge of C++

Prerequisities

Subject has no prerequisities.

Co-requisities

Subject has no co-requisities.

Subject syllabus:

The lecture notes are designed such that they can make the basis for practical exercising on computer labs. The outline of lessons: 1. Introduction to parallel programming on GPU, a brief history, CUDA 2. CUDA architecture and its integration within standard C++ project 3. Threads and kernel functions 4. CUDA memories, patterns and usage 5. Memory bank conflicts 6. Program execution control, distribution of an algorithm 7. Algorithm performance with respect to its parallelization on GPU 9. Optimization on the data level, effective data structures. 10. Optimization of programs with respect to the maximum GPU performance 11. Support library CUBLAS 12. The Case study The outline of exercises (exercises are on computer labs): 1. The first application in CUDA 2. Data transfers to/from GPU 3. Threads hierarchy, basic thread life cycle, limits, calling of kernel functions, parameters and restrictions 4. CUDA memories, patterns and usage 5. Memory bank conflicts, access optimization, suitable data structures 6. Streams, parallel calling of kernel functions, synchronization on several levels 7. The case study, experiment with more variants of the same program 8. Vectors and matrices, the case study, large data processing, parallel reduction 9. Introduction to several support libraries for linear algebra 10. The case study, image manipulation, double buffering, optimization at the level of blocks, registers, etc. 11. The case study, Interesting research topics, outline of possible Solutions, experiments 12. Program tuning, debugging with nVidia nSight

Conditions for subject completion

Combined form (validity from: 2015/2016 Winter semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Graded credit Graded credit 100  51
Mandatory attendence parzicipation:

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.FormStudy language Tut. centreYearWSType of duty
2019/2020 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava Choice-compulsory study plan
2019/2020 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava Choice-compulsory study plan
2019/2020 (N0541A170007) Computational and Applied Mathematics (S01) Applied Mathematics P Czech Ostrava 1 Optional study plan
2019/2020 (N0541A170007) Computational and Applied Mathematics (S02) Computational Methods and HPC P Czech Ostrava 1 Optional study plan
2019/2020 (N0541A170007) Computational and Applied Mathematics (S01) Applied Mathematics K Czech Ostrava 1 Optional study plan
2019/2020 (N0541A170007) Computational and Applied Mathematics (S02) Computational Methods and HPC K Czech Ostrava 1 Optional study plan
2018/2019 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava Choice-compulsory study plan
2018/2019 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava Choice-compulsory study plan
2017/2018 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava Choice-compulsory study plan
2017/2018 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava Choice-compulsory study plan
2016/2017 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava Choice-compulsory study plan
2016/2017 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava Choice-compulsory study plan
2015/2016 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava Choice-compulsory study plan
2015/2016 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava Choice-compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner