456-0917/01 – Parallel Algorithms (PA)

Gurantor departmentDepartment of Computer ScienceCredits10
Subject guarantorRNDr. Ondřej Jakl, CSc.Subject version guarantorRNDr. Ondřej Jakl, CSc.
Study levelpostgraduateRequirementChoice-compulsory
YearSemesterwinter + summer
Study languageCzech
Year of introduction1997/1998Year of cancellation2009/2010
Intended for the facultiesFEIIntended for study typesDoctoral
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
Part-time Credit and Examination 2+2

Subject aims expressed by acquired skills and competences

A general review of design, realization and evaluation of parallel algorithms, with specifical extensions in the directions matching the student's Ph.D. study. Overview in the field of parallel systems and their programming. Design of parallel algorithms, their analysis, efficient implementation and optimization. Application of those methods and techniques in a specific area.

Teaching methods

Summary

The course provides the students with necessary fundamentals in the area of parallel programming and algorithms, to be able to make effective use of modern multiprocessor hardware (including supercomputers) for solution of demanding task from various application fields. It focuses on the most general parallel architecture, distributed-memory systems, where the interaction of parallel processes is based on message passing, but techniques specific for symmetric multiprocessors (with shared memory) are covered, too. Practical training is provided on the most powerful platforms available at VŠB-TUO, including the Termit cluster having 32 processors. Individual approach, allowing application of the gained knowledge in the student's specific field of study, is supposed.

Compulsory literature:

Recommended literature:

Way of continuous check of knowledge in the course of semester

E-learning

Další požadavky na studenta

Prerequisities

Subject has no prerequisities.

Co-requisities

Subject has no co-requisities.

Subject syllabus:

Lectures: Introduction. Motivation and historical remarks. Basic concepts. Parallel computer systems. Flynn's classification. Interconnection subsystems. Loosely coupled multiprocessors. Computer networks and massively parallel systems. The Termit cluster and IBM SP. Parallel programming models. The message passing model. Design of a parallel algorithm: decomposition, communication analysis, agglomeration, mapping to processors. Load-balancing techniques. Evaluation of parallel algorithms. Speedup, efficiency, cost. Amdahl's law. Scalability of parallel applications. Isoefficiency function. Parallel Virtual Machine (PVM). Application programming interface. PVM (continued). Overview of library routines: process control, information retrieval, message passing, etc. PVM (continued). Collective communication. Debugging issues. Visualization of a parallel execution. Selected algorithms in a chosen application area and their parallelization. Introduction to the Message Passing Interface (MPI). Comparison with PVM, advanced features. Programming of symmetric multiprocessors. Threads and OpenMP. Current developments in high performance computing.

Conditions for subject completion

Full-time form (validity from: 1960/1961 Summer semester, validity until: 2012/2013 Summer semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Exercises evaluation and Examination Credit and Examination 100 (145) 51
        Examination Examination 100  0
        Exercises evaluation Credit 45  0
Mandatory attendence parzicipation:

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.ZaměřeníFormStudy language Tut. centreYearWSType of duty
2009/2010 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2009/2010 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2008/2009 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2008/2009 (P2646) Information Technology K Czech Ostrava Choice-compulsory study plan
2008/2009 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2007/2008 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2006/2007 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2005/2006 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2004/2005 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2003/2004 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2002/2003 (P2612) Electrical Engineering and Computer Science (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2001/2002 (P2612) Electrical Engineering and Computer Science (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner