Jump to Block: (About) 01 02 03 04 05 06 07 08 09 10 11 (Assessments)
09 Parallel Algorithms
In this block we cover:
- Parallel computation
- CPUs, computers and clusters as parallel processing units
- Formal classes of parallel computer (SISD/SIMD/MISD/MIMD)
- Embarrassingly parallel algorithms
- Vectorisation
- Vectorisation and time complexity
- PyTorch, GPUs and automatic differentiation
- Computational graphs
- Computation dependence
- Distributed computation
- Map/Reduce
- The Map/Reduce parallel framework
- Map/Reduce matrix multiplication
- Loss functions and gradients as map-reduce operations
- Coding parallel algorithms
- Multiprocessing with joblib
- Overheads and chunking
- Asynchronous computation and futures
- Parallel hyperparameter search, and emulating the accuracy-compute trade-off
Lectures:
Introduction to Parallelism:
- 9.1 Introduction to Parallelism
- This week Portfolios are all notebooks:
- 9.1.1 Workshop on Vectorisation and PyTorch
Mapping, Reducing, and Computational Graphs:
- 9.2 Mapping, Reducing, and Computational Graphs
- This week Portfolios are all notebooks:
- 9.2.1 Workshop on Map/Reduce and Computational Graphs
Workshop:
Assessments:
- The main long form portfolio Portfolio 09.
- Block09 on Noteable via Blackboard (2026-27 link)
References
Parallel algorithms
- Chapter 27 of Cormen et al 2010 Introduction to Algorithms covers some of these concepts.
- Guy Blelloch and Bruce Maggs A Brief Overview of Parallel Algorithms
- CSinParallel Parallel computing concepts
- Tutorialspoint on MISD/MIMD/SIMD/SISD and Parallel time complexity
Vectorisation and PyTorch
- Real Python on Numpy vectorisation
- PyTorch and its autograd tutorial
Map/Reduce and parallel Python
- Emory University notes on the MapReduce algorithm for matrix multiplication
- Chrys Woods Parallel Python, including map and reduce
- Beyond one machine: Dask and Ray run the same map and futures patterns over a cluster.