Parallel Systems and Algorithms
Semestr: Summer
Range: 3+3c
Completion:
Credits: 7
Programme type: Undefined
Study form: Fulltime
Course language:
Summary:
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.
Keywords:
parallel computers, computing and algorithms, scalability and isoefficiency, interconnection networks, embedding and simulations, routing, permutation routing, collective communication operations, clusters of workstations.
Course syllabus:
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
Seminar syllabus:
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
Literature:
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