Parallel Systems and Algorithms

The course is a substitute for:

Parallel Systems and Algorithms (36PAR)

Lecturer:

Pavel Tvrdík, Michal Šoch

Tutor:

Pavel Tvrdík, Michal Šoch

Supervisor:

Department of Computer Science and Engineering

Synopsis:

The aim of the course is to introduce students to the art of designing efficient algorithms for parallel computers with shared and with distributed memory, which includes massively parallel systems with regular topologies of the interconnection network and clusters of workstations with irregular topologies. We will focus on the analysis of the performance, isoefficiency, and scalability of parallel algorithms. We will study parallel algorithms for reduction, scan, sorting, linear algebra, and combinarial search. An important part of the course is devoted to the theory of interconnection networks, to their topologies and technologies and to algorithms for routing and for collective communication operations.

Requirements:

https://service.felk.cvut.cz

Syllabus of lectures:

1. Complexity measures and scalability of parallel algorithms

2. Parallel algorithms for combinatorial search

3. Parallel architectures and models

4. Interconnection networks

5. Embedding and simulations of interconnection networks

6. Routing algorithms, switching techniques, deadlocks

7. Reduction, prefix sum and Euler tour techniques

8. Parallel sorting

9. Permutation routing

10. Algorithms for collective communication operations I

11. Algorithms for collective communication operations II

12. Parallel algorithms for linear algebra I

13. Parallel algorithms for linear algebra II

14. Parallel complexity theory

Syllabus of tutorials:

1. Complexity analysis of a simple parallel algorithm

2. Design of cost- and time-optimal PRAM algorithms

3.-4. Design of cost- and time-optimal APRAM algorithms

5. Analysis of basic characteristics of interconnection network topologies

6. Design of embedding algorithms and their evaluations

7. Examples of interconnection network simulations

8.-9. Isoefficiency and scalability of parallel sorting

10.-11. Design of efficient collective communication algorithms

12.-13. Parallel algorithms for linear algebra

14. Zapocet

Study Objective:

Study materials:

1. P. Tvrdík: Parallel systems and computing, Lecture notes, ČVUT, 2003.

2. J.H. Reif: Synthesis of Parallel Algorithms, Morgan Kaufmann, USA, ISBN 1-5586-135-X

Note:

Time-table for winter semester 2011/2012:

Time-table is not available yet

Time-table for summer semester 2011/2012:

Time-table is not available yet

The course is a part of the following study plans:

• Computer Technology - Software Engineering- structured studies (compulsory course)
• Computer Technology - System Programming- structured studies (compulsory course)
• Computer Technology - Computer Graphics- structured studies (compulsory course)
• Computer Technology - Computer Network and Internet- structured studies (compulsory course)
• Computer Technology - Designing Digital Systems- structured studies (compulsory course)