Parallel Systems and Algorithms

The course is a substitute for:

Parallel Systems and Algorithms (D36PAR)

Lecturer:

Pavel Tvrdík, Neurčen (gar.), 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. The course will focus on the analysis of the performance, isoefficiency, and scalability of parallel algorithms. We will consider parallel algorithms for scan, sorting, linear algebra, combinarial search, and graph theory.

Requirements:

Syllabus of lectures:

1. Performance measures of parallel algorithms

2. PRAM and APRAM models

3. Technologies and topologies of interconnection networks

4. Embedding and simulations of interconnection networks

5. Prefix sum and Euler tour techniques

6. Parallel sorting

7. Routing algorithms and permutation routing

8. Collective communication algorithms

9. Parallel algorithms for linear algebra - dense matrices

10. Parallel algorithms for linear algebra - sparse matrices

11. Parallel algorithms for combinatorial search

12. Parallel graph algorithms

13. Computations on clusters of workstations

14. Metacomputers and Internet computing

Syllabus of tutorials:

1. Complexity analysis of a simple parallel algorithm

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

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

4. Analysis of basic characteristics of interconnection network topologies

5. Design of embedding algorithms

6. Interconnection network simulations

7. Isoefficiency and scalability of parallel sorting

8. Design of efficient algorithms for permutation routing

9. Design of efficient collective communication algorithms

10. Isoefficiency and scalability of parallel algorithms for linear algebra

11. Isoefficiency and scalability of parallel algorithms for combinatorial search

12. Isoefficiency and scalability of parallel graph algorithms

13. A case study of a high-performance cluster of workstations

14. A case study of a metacomputer

Study Objective:

Study materials:

1. J.H. Reif: Synthesis of Parallel Algorithms, Morgan Kaufmann, USA, ISBN

1-5586-135-X

Note:

Time-table for winter semester 2011/2012:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon	room Neurčen . 17:00–18:45 (lecture parallel1)
Tue
Fri
Thu
Fri

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)