Parallel Systems and Algorithms

Semestr: Summer

Range: 3+2s


Credits: 4

Programme type:

Study form:

Course language:


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.


Course syllabus:

Seminar syllabus:


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