460-4117/02 – Parallel Algorithms I (PA I)

Gurantor departmentDepartment of Computer ScienceCredits4
Subject guarantordoc. Ing. Pavel Krömer, Ph.D.Subject version guarantordoc. Ing. Pavel Krömer, Ph.D.
Study levelundergraduate or graduateRequirementChoice-compulsory
YearSemesterwinter
Study languageEnglish
Year of introduction2015/2016Year of cancellation
Intended for the facultiesFEIIntended for study typesFollow-up Master
Instruction secured by
LoginNameTuitorTeacher giving lectures
KRO080 doc. Ing. Pavel Krömer, 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+0

Subject aims expressed by acquired skills and competences

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.

Teaching methods

Lectures
Tutorials

Summary

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.

Compulsory literature:

1. Using OpenMP: Portable Shared Memory Parallel Programming, Volume 10, Barbara Chapman, Gabriele Jost, Ruud van der Pas, MIT Press, 2008 2. Introduction to Parallel Computing (2nd Edition). Ananth Grama, George Karypis, Vipin Kumar, Anshul Gupta, Addison-Wesley, 2003 Parallel algorithms I lecture notes.

Recommended literature:

1. Distributed Computing Principles, Algorithms, and Systems, Ajay D. Kshemkalyani, Mukesh Singhal, Cambridge, 2008 2. Distributed Systems: Principles and Paradigms, Andrew S. Tanenbaum, Maarten van Steen, Pearson Prentice Hall, 2007 3. Patterns for parallel programming. Timothy Mattson, Beverly Sanders, Berna Massingill, Addison-Wesley, 2004

Way of continuous check of knowledge in the course of semester

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 application of different methods and parallel algorithm 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.

E-learning

Další požadavky na studenta

No additional requirements.

Prerequisities

Subject has no prerequisities.

Co-requisities

Subject has no co-requisities.

Subject syllabus:

Lectures: ========= 1. Introduction to parallel programming. Processes and threads. Processes and threads from the operating system perspective. 2. Sequential vs. parallel programming. Parallel programming caveats. Deadlock (definition, properties, conditions, detection, elimination). 3. Parallel vs. distributed applications. Classification of parallel systems. Shared memory systems and distributed memory systems. Flynn's taxonomy. 4. Shared memory systems programming. Programming with threads. The pthreads library, Threads in Java and C#. Synchronization and exclusion, deadlock. 5. The OpenMP interface. OpenMP support in modern compilers. OpenMP directives and functions. Reduction in OpenMP. 6. Fork-join model, Cilk and Cilk++ languages. Parallel Matlab. Parallel programming in Python, the NumPy library. 7. Distributed memory systems programming. Message passing. Posix queues, sockets. The MPI interface, fundamental MPI functions. MPI libraries. 8. Partitioned Global Address Space (PGAS) model. The Unified Parallel C (UPC) language. 9. Batch (non-interactive) task execution. Schedulers PBSPro and Torque. 10. Grid and cloud programming. Web services and distributed applications using web services. Map-reduce paradigm and Hadoop framework. 11. Introduction to accelerator programming. GPGPU architecture (program organization, memory organization). Data parallelism. CUDA platform and CUDA-C language. 12. Other interfaces for accelerator programming: OpenCL, OpenACC, OpenMP 4. 13. Intel MIC architecture. Programming the MIC and Intel Xeon Phi. Emerging platforms. 14. Hybrid applications. MPI-OpenMP programming, hybrid CPU-GPU architectures. Tutorials: ========== The topics and tasks dealt with at the tutorials will correspond to the topics presented at the lectures. 1. Overview of environments for parallel programming. SIMD instructions. 2. Implementation of a simple multithreaded program. 3. Implementation of a simple multiprocess program. Inter process communication with the help of sockets and queues. 4. Debugging a profiling of parallel programs. 5. Implementation of a simple OpenMP program. Parallelization of a sequential program by OpenMP. 6. Implementation of a simple program in Cilk++. A demonstration of parallel programming in Matlab. 7. Implementation of a simple MPI program. 8. Implementation of a simple program in UPC. 9. The use of PBS, PBSPro, and Torque schedulers; qsub command and QSUB directives. 10. Implementation of a simple map-reduce application under the Hadoop framework. 11. Implementation of a simple data-parallel program in CUDA-C. 12. A demonstration of OpenCL, OpenACC, and OpenMP 4. 13. Intel MIC programming. Implementation of a simple Intel MIC program. 14. Implementation of a simple hybrid MPI - OpenMP program.

Conditions for subject completion

Full-time 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 English Ostrava Choice-compulsory study plan
2019/2020 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K English Ostrava Choice-compulsory study plan
2019/2020 (N0541A170008) Computational and Applied Mathematics (S01) Applied Mathematics P English Ostrava 1 Compulsory study plan
2019/2020 (N0541A170008) Computational and Applied Mathematics (S02) Computational Methods and HPC P English Ostrava 1 Optional study plan
2018/2019 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P English Ostrava Choice-compulsory study plan
2018/2019 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K English Ostrava Choice-compulsory study plan
2017/2018 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P English Ostrava Choice-compulsory study plan
2017/2018 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K English Ostrava Choice-compulsory study plan
2016/2017 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P English Ostrava Choice-compulsory study plan
2016/2017 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K English Ostrava Choice-compulsory study plan
2015/2016 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P English Ostrava Choice-compulsory study plan
2015/2016 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K English Ostrava Choice-compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner