Parallel Systems and Algorithms

Semestr: Summer

Range: 19+6c

Completion:

Credits: 7

Programme type: Undefined

Study form: Parttime

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. 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.

Keywords:

Course syllabus:

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

Seminar syllabus:

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

Literature:

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

Examiners:

Lecturers:

Instructors: