Parallel Systems and Algorithms

Course guarantor:

Lecturer:

Tutor:

Supervisor:

Department of Computer Science

Synopsis:

Complexity measures and scalability of parallel algorithms. Parallel computer architectures, models, PRAM, APRAM. Direct and indirect interconnection networks, embeddings, simulations. Communication algorithms - routing, switching techniques, deadlock problem, permutation routing, collective communication

operations. Fundamental parallel algorithms - reduction, prefix

computation, Euler tour technique. Parallel sorting. Parallel linear algebra algorithms. Parallel combinatorial search. Parallel complexity theory

Graduates of engineering studies in specialization Computer Science and

Informatics FEE CTU cannot register.

Requirements:

Syllabus of lectures:

Syllabus of tutorials:

Study Objective:

Study materials:

Pavel Tvrdík: Paralelní systémy a algoritmy, Vydavatelství ČVUT, Praha. 2000.

Vipin Kumar, et al.: Introduction to parallel computing, The Benjamin/Cummings Publ. Co., 1994, ISBN 0-8053-3170

R. Greenlaw, et al.: Limits to parallel computation, Oxford University Press, 1995, ISBN 0-19-508591-4

J. Ja'Ja': An introduction to parallel algorithms, Addison-Wesley, 1992, ISBN 0-201-54856-9

T.Leighton: Introduction to parallel algorithms and architectures, Morgan Kaufmann Publ., 1992, ISBN 1-55860-117-1

J.Duato et al.: Interconnection networks: An engineering approach, IEEE CS Press, 1997, ISBN 0-8186-78003

Note:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans:

• Doctoral studies, daily studies (compulsory elective course)
• Doctoral studies, combined studies (compulsory elective course)
• Doctoral studies, structured daily studies (compulsory elective course)
• Doctoral studies, structured combined studies (compulsory elective course)