Parallel algorithms

Objectives and outcomes

Developing theoretical foundations and practical skills required for understanding and development of
parallel computer programs. Students will learn the key concepts and issues related to the
implementation of parallel algorithms and will be acquainted with the relevant characteristics of modern
parallel computing systems. They will be capable of designing and using parallel algorithms for problem-solving.


Parallel computing systems and Flynn’s taxonomy. Limits of parallelisation, Amdahl’s and Gustafson’s
laws. Shared, local and distributed memories. Performance of parallel algorithms. Analysing a problem in
order to identify possible routes to parallelisation. Short introduction to Python. Introduction to basic
concepts of parallel programming based on examples in Python. Parallelisation through multithreading.
Parallelisation through multiprocessing. Synchronisation, barriers and semaphores. Manycore and GP-
GPU software development. CUDA and pyCUDA frameworks. Vectorisation through Intel AVX instruction
set. Dataflow programming.

Practical classes

Estimating the speedup and efficiency which can be obtained through parallelisation. Practical
introduction to Python and software development using Jupyter/Google Colab environments.
Parallelisation through multithreading and the limitations of the Python interpreter (Global Interpreter
Lock). Parallelisation through multiprocessing. Synchronisation and inter-process communication.
Examples of parallel algorithms from the domains of scientific computing, business applications and
graph processing. CUDA programming framework. Examples of programs written using CUDA, and
execution through pyCUDA, Jyputer Lab and Google Cloud.