M1: Foundations

M1: Foundations #

This module establishes how to measure ML system performance, identify bottlenecks, and decide which work can run in parallel. It connects algorithmic complexity with the capabilities and limits of CPUs, GPUs, and clusters.

Module coverage:

• Performance Metrics and Complexity Analysis: time and space complexity, throughput, latency, and speedup through Amdahl’s Law.
• Parallelisation Paradigms: data-level, task-level, and algorithm-specific parallelism.
• Modern Hardware Architectures: multi-core CPUs, GPGPUs, GPU/CPU clusters, and resource management.

Learning Objectives #

• Distinguish complexity from measured running time, throughput, and latency.
• Explain the limits of speedup and the cost of communication.
• Choose between data, task, and request parallelism for a workload.
• Relate memory hierarchy, bandwidth, and hardware organisation to performance.

Pages #

Topic Outline #

1. ML and DL System Performance #

• Time complexity of algorithms and running time
• Performance scaling and tuning
• Training versus deployment
• Distributed and cloud environments, embedded devices, and mobile systems
• Throughput and response time

2. Parallel and Distributed Algorithms #

• Systems and performance
• Speedup: approaches, issues, and Amdahl’s Law ☆
• Data parallelism, task parallelism, and request parallelism
• Scale-out clusters: communication cost and its impact on speedup
• Scale-up versus scale-out

3. Parallel Programming Models #

• Parallel programming models and the MapReduce pattern
• Task-parallel and request-parallel execution
• Multi-core and GPGPU parallelism: SIMD versus MIMD
• Memory hierarchies and bandwidth considerations
• CPU-only and GPU-accelerated distributed clusters
• Horizontal and vertical data sharding
• Parameter-server and all-reduce paradigms

How This Module Connects #

Performance measurement and parallel execution provide the basis for M2: Distributed ML Algorithms. Communication and memory limits remain relevant throughout the later modules.

ML and DL System Performance

ML and DL System Performance #

Machine learning system optimisation begins with measurement. Before changing an algorithm, adding processors, or moving work to a GPU, we need to understand what is slow, which resource is limiting performance, and how performance changes as the workload grows.

Course coverage:

1. Metrics: time complexity, running time, space, throughput, latency, and response time
2. Performance scaling and tuning: measuring bottlenecks and predicting how a workload grows
3. Training versus deployment: different objectives, workloads, and constraints
4. Deployment environments: distributed and cloud systems, embedded devices, and mobile systems

Learning Objectives #

By the end of this page, you should be able to:

M2: Distributed ML Algorithms

M2: Distributed ML Algorithms #

This module applies parallel and distributed computing to ML algorithms. It examines how to divide computation, combine results, and balance communication against useful work during training.

Module coverage:

• Parallel ML Algorithms: CNNs, gradient descent and SGD, SVM, k-means, k-nearest neighbours, decision trees, and random forests.
• Distributed Training Strategies: data parallelism, model parallelism, pipeline parallelism, gradient checkpointing, and mixed-precision training.

Learning Objectives #

• Decompose ML algorithms into independent and dependent work.
• Explain how local results are aggregated and where communication is required.
• Compare distributed execution through Hadoop and Spark.
• Choose training strategies that address compute and memory constraints.

Pages #

Topic Outline #

4. Parallelisation of ML Algorithms #

• Problem decomposition and parallelisation
• Ensemble methods and XGBoost on CPUs
• k-means
• Distributed decision trees and random forests
• Distributed implementations using Spark ML and XGBoost
• Parallel SVM kernel computation using block-wise and MapReduce-style methods

5. Communication-Aware Distributed ML #

• Communication overhead in distributed algorithms
• Distributed k-means and model parallelism
• k-NN: data partitioning, locality-sensitive hashing, and distributed indexing
• KD-tree and Ball-tree indexing versus brute-force MapReduce
• Accuracy–latency trade-offs in approximate k-NN
• Gradient descent and SGD: mini-batch, synchronous, and asynchronous variants

6. Clusters, Hadoop, and Spark #

• Cluster computing with Hadoop and Spark
• Lloyd’s k-means algorithm in MapReduce
• Mini-batch k-means and streaming variants
• Convergence criteria and communication reduction through compressed updates
• CNN data and model parallelism, including layer splitting and tensor slicing
• Mixed precision, pipeline parallelism, and distributed training frameworks

7. Distributed Training Strategies ☆ #

• Data parallelism
• Model parallelism
• Pipeline parallelism
• Gradient checkpointing
• Mixed-precision training

How This Module Connects #

Use M1: Foundations to interpret complexity and speedup. Continue to M3: Scale-Out Systems for the platforms and communication mechanisms that support larger training runs.

Parallel and Distributed Algorithms

Parallel and Distributed Algorithms #

Parallelisation divides computational work into parts that can execute concurrently. The purpose is to reduce completion time or increase throughput, but the gain depends on how much work is genuinely independent and how much overhead is introduced.

Course coverage:

1. Systems and performance: execution time, throughput, efficiency, and bottlenecks
2. Speedup—approaches and issues: Amdahl’s Law, serial work, overhead, and load imbalance
3. Data parallelism versus task parallelism versus request parallelism
4. Scale-out clusters: communication cost and its impact on speedup

The worked algorithms also show how divide-and-conquer and matrix operations expose parallel work.

M3: Scale-Out Systems

M3: Scale-Out Systems #

This module examines the platforms, communication patterns, and hardware organisation used to train across larger systems. It extends distributed algorithms into coordinated training services and federated settings.

Module coverage:

• ML Platforms and Frameworks: the Parameter Server model, Spark MLlib, and TensorFlow/PyTorch distributed training.
• Distributed Deep Learning: decentralised SGD, all-reduce, asynchronous parallelism, and large-scale neural networks.
• Federated Learning: training that preserves data privacy, communication efficiency, and hardware utilisation.

Learning Objectives #

• Explain how training platforms organise model state, workers, and updates.
• Compare centralised parameter services with collective communication.
• Assess the effects of bandwidth, latency, locality, and stale updates.
• Relate federated training to data distribution, privacy goals, and communication limits.

Pages and Planned Topics #

The outline below describes the full module scope. Planned topics have no chapter page yet. Chapter 9 currently covers parameter-server execution policies and communication optimisation; collective communication, matrix multiplication, and Local SGD remain to be added from their source material.

Parallel Programming Models

Parallel Programming Models #

Parallel algorithms need hardware that can execute independent work efficiently. Modern systems therefore combine multiple CPU cores, memory hierarchies, threads, instruction pipelines, GPUs, clusters, and specialised matrix processors.

Course coverage:

1. Parallel programming models for expressing independent work
2. MapReduce, task-parallel, and request-parallel patterns
3. Multi-core CPUs and GPGPUs: SIMD, MIMD, SIMT, memory hierarchy, and bandwidth
4. Distributed clusters: CPU-only and GPU-accelerated systems, data sharding, parameter servers, and all-reduce

The hardware sections also cover specialised matrix processors and the performance limits introduced by memory and communication.

M4: Constrained Systems

M4: Constrained Systems #

This module considers how to make models practical when memory, compute, latency, and energy are limited. It connects model compression with edge deployment and the trade-offs required to retain useful prediction quality.

Module coverage:

• Model Optimisation Techniques: model compression, structured and unstructured pruning, post-training quantisation, and quantisation-aware training.
• Edge Deployment: TinyML, TensorFlow Lite, ONNX Runtime, and knowledge distillation.
• Performance Trade-offs: accuracy versus latency, model size versus throughput, and energy consumption optimisation.

Learning Objectives #

• Compare methods for reducing model size, computation, and memory use.
• Distinguish different quantisation and pruning approaches.
• Explain the role of knowledge distillation and deployment frameworks.
• Evaluate accuracy, latency, throughput, model size, and energy together.

Planned Topics #

This index records the module scope. Chapter pages can be added here as their source material becomes available.

Parallelisation of ML Algorithms

Parallelisation of ML Algorithms #

Machine-learning algorithms expose different kinds of parallel work. The correct decomposition depends on whether independent work occurs across records, features, trees, clusters, kernel entries, or optimisation steps.

Course coverage:

1. Problem decomposition for parallel machine learning
2. Ensemble methods and XGBoost-style tree ensembles
3. Parallel k-means assignment and centroid reduction
4. Distributed decision trees and random forests
5. Support vector machine parallelisation using block and MapReduce-style computation

Learning Objectives #

By the end of this page, you should be able to:

Communication-Aware Distributed ML

Communication-Aware Distributed ML #

Distributed machine learning is effective only when saved computation exceeds the cost of moving data and synchronising workers. Algorithm design must therefore account for message size, message frequency, barriers, and parameter placement.

Course coverage:

1. Communication overhead, illustrated through distributed k-means
2. Model parallelism when parameters do not fit or compute must be divided
3. Distributed k-nearest neighbours: partitioning, indexing, and approximate search
4. Gradient descent, SGD, and mini-batch optimisation
5. Synchronous versus asynchronous updates

Learning Objectives #

By the end of this page, you should be able to:

Clusters, Hadoop, and Spark

Clusters, Hadoop, and Spark #

Scale-out frameworks distribute data and computation across networked machines. Their value comes from aggregate compute and storage, while their main costs are communication, scheduling, serialisation, and repeated synchronisation.

Course coverage:

1. Cluster computing with Hadoop and Spark
2. MapReduce k-means, mini-batch and streaming variants
3. Convergence and communication reduction
4. Distributed convolutional neural networks: data and model parallelism
5. Layer or tensor slicing, mixed precision, pipelining, and distributed execution frameworks

Learning Objectives #

By the end of this page, you should be able to: