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.

This page covers:

• speedup, maximum speedup, and processor efficiency
• Amdahl’s Law
• data-level parallelism
• task-level parallelism
• algorithm-specific parallelism
• communication, synchronisation, scheduling, and load-balancing overhead
• parallel merge sort and matrix multiplication

Learning Objectives #

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