Parallel Systems and Algorithms

The course is a substitute for:

Parallel Systems and Algorithms (XE36PAR)

Lecturer:

Tutor:

Supervisor:

Department of Computer Science and Engineering

Synopsis:

Architectures and methods of effective use of parallel systems. Basic problems of parallelisation of algorithms, their relationship to architectures of parallel systems. Theory of parallel computation complexity and to shared memory models. Distributed memory architectures, namely architectures of communication networks and methods how computing nodes communicate via an interconnection network. Basic parallel algorithms, namely fundamental parallel algorithms such as prefix computations, parallel sorting algorithms, and algorithms in linear algebra.

Requirements:

Syllabus of lectures:

1. Architectures of parallel computers

2. Performance metrics for parallel computations

3. PRAM models of parallel computations

4. Parallel complexity theory

5. Interconnection networks of parallel computers

6. Embeddings and simulations of networks

7. Communication algorithms for routing and permutations

8. Collective communication algorithms

9. Fundamental parallel algorithms

10. Parallel sorting algorithms

11. Parallel sorting algorithms

12. Parallel algorithms for linear algebra

13. Parallel algorithms for linear algebra

14. Parallel programming environments

Syllabus of tutorials:

Labs: 2 hours/week; 1.-2. Introduction to the PVM parallel programming systém. 3. Assignment of term projects. 4.-13. Solving term projects. 14. Giving over term projects and assignments

1. Introduction

2. Performance metrics for parallel computations

3. Scalability and isoefficiency of algorithms

4. NC and PRAM simulations

5. Topological properties of interconnection networks

6. Embeddings - case studies

7. Network simulations - case studies

8. Routing algorithms and deadlocks

9. Permutation routing in hypercubic networks

10. Collective communication in mesh-based networks

11. Complexity analysis of fundamental NC algorithms

12. Complexity analysis of parallel sorting algorithms

13. Complexity analysis of parallel matrix algorithms

14. Complexity analysis of parallel algorithms for solving equations

Study Objective:

Study materials:

[1] Tvrdík, P.: Parallel Systems and Algorithms. Publ.House CTU, Prague 1997

Note:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans: