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.

Distributed Training Strategies

Distributed Training Strategies #

Distributed training combines devices to increase throughput, fit larger models, or shorten time to solution. The central design question is what to partition: examples, model parameters, layers, tensors, or the training schedule.

Course coverage:

1. Data parallelism
2. Model parallelism
3. Pipeline parallelism and micro-batches
4. Gradient checkpointing
5. Mixed-precision training and loss scaling

Learning Objectives #

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

• compare data, model, and pipeline parallelism
• calculate global batch size, speedup, efficiency, and effective throughput
• explain gradient aggregation through all-reduce
• calculate simple pipeline time and utilisation
• quantify the memory–computation trade-off of checkpointing
• explain mixed precision and loss scaling

Big Picture #

flowchart TD
    A["Training Constraint"] --> B["More Data Throughput"]
    A --> C["Model Too Large"]
    A --> D["Activation Memory Too High"]
    B --> E["Data Parallelism"]
    C --> F["Model or Pipeline Parallelism"]
    D --> G["Checkpointing or Mixed Precision"]

    style A fill:#E1F5FE
    style B fill:#C8E6C9
    style C fill:#FFF9C4
    style D fill:#EDE7F6
    style E fill:#E1F5FE
    style F fill:#C8E6C9
    style G fill:#FFF9C4

1. Data Parallelism ☆ #

Each worker holds a complete model replica and processes a different shard of the mini-batch.