Parallel Systems and Algorithms

The course is a substitute for:

Parallel Systems and Algorithms (XD36PAR)

Lecturer:

Tutor:

Supervisor:

Department of Computer Science and Engineering

Synopsis:

The course is focussed on architectures and methods of effective usage of parallel systems. The aim is to explain how the basic problems of parallelization of algorithms are related to architectures of parallel systems. The first part is devoted to the theory of parallel computation complexity and to shared memory models. The second part deals with distributed memory architectures, namely architectures of communication networks and methods how computing nodes communicate via an interconnection network. The last part surveys basic parallel algorithms, namely fundamental parallel algorithms such as prefix computations, parallel sorting and algorithms for computational geometry and finally 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

11. Parallel algorithms for computational geometry

12. Parallel algorithms for linear algebra

13. Parallel algorithms for linear algebra

14. Parallel programming environments

Syllabus of tutorials:

1. Introduction

2. Performance metrics for parallel computations

3. Scalability and isoefficiency of algorithms

4. NC a P-complete algorithms

5. Topological properties of interconnection networks

6. Embeddings - case studies

7. Network simulations - case studies

8. Routing algorithms a 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 analysisof parallel matrix algorithms

14. Complexity analysis of parallel algorithms for solving equations

Labs: 2 hours/week

1.- 2. Introduction to the PVM parallel programming system

3. Assignment of term projects

4.-13. Solving term projects

14. Giving over term projects and assignments

Study Objective:

Study materials:

Note:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans: