Parallel Systems and Algorithms

Semestr: Summer

Range: 3+3s

Completion:

Credits: 8

Programme type: Undefined

Study form:

Course language:

Summary:

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.

Keywords:

parallel computers, computing and algorithms, scalability and isoefficiency, interconnection networks, embedding and simulations, routing, permutation routing and collective communication operations, clusters of workstations.

Course syllabus:

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

Seminar syllabus:

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

Literature:

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

Examiners:

Lecturers:

Instructors: