Parallel and Distributed Algorithms
Open in the Padhaiko app5.1 Introduction to parallel computing
Parallel algorithms decompose a computation into independent tasks executed simultaneously across multiple processing cores or machines, reducing wall-clock execution time (span) while controlling total operations (work) and communication overhead.
Work, Span, Speedup, and Efficiency
Using the DAG (work-span) model of multithreaded computation:
- Work (): Total time (number of operations) to execute the entire computation on processor.
- Span (, critical-path length): Longest path of sequential dependencies in the computation DAG (minimum possible execution time on infinitely many processors).
- Speedup (): Ratio , where is the execution time on processors. (Parallelism is the upper bound .)
- Efficiency (): Fraction of processor capacity effectively utilized, .
Brent's Theorem and Amdahl's Law
- Work and Span Laws: For any scheduler on processors, and .
- Brent's Theorem: Any DAG with work and span can be scheduled on processors in time:
- Amdahl's Law: If a fraction of a program is strictly sequential and fraction is infinitely parallelizable, the maximum speedup on processors is bounded by:
- Gustafson's Law (Scaled Speedup): For larger problem sizes where parallel workload scales with , scaled speedup grows linearly: .
PRAM Memory-Access Models
The Parallel Random-Access Machine (PRAM) models synchronous processors sharing a single global memory, classified by simultaneous read/write rules:
- EREW (Exclusive Read, Exclusive Write): No two processors may read or write the same memory cell in the same step.
- CREW (Concurrent Read, Exclusive Write): Multiple processors may read the same cell simultaneously, but writes must be exclusive.
- CRCW (Concurrent Read, Concurrent Write): Both simultaneous reads and writes are allowed; write conflicts are resolved by Common (all write same value), Arbitrary (one succeeds), or Priority (lowest-ID processor wins).
1
Suppose of an algorithm's execution time () is perfectly parallelizable and () is strictly sequential.
- Compute the maximum speedup and parallel efficiency on processors using Amdahl's Law.
- Compute the asymptotic ceiling as , and compare with Gustafson's scaled speedup for .
Amdahl's Law for , :
Parallel efficiency:
Asymptotic Amdahl limit and Gustafson's Law:
- As , (no amount of hardware overcomes the serial bottleneck for a fixed problem).
- Under Gustafson's Law (fixing wall time and scaling parallel work by ):
By Amdahl's Law, achieves speedup ( efficiency) and can never exceed as ; Gustafson's scaled speedup for is .
5.2 Parallel divide-and-conquer
Divide-and-conquer naturally exposes parallelism because independent subproblems can be spawned concurrently and synchronized with a sync barrier before combining results.
Parallel Merge Sort
- Version 1 (Sequential Merge): Spawn the two recursive
mergesortcalls of size in parallel, then run standard sequentialmergein time.- Work: .
- Span: .
- Parallelism: — severely limited by the sequential merge!
- Version 2 (Parallel Merge): Replace
merge(A, B)with parallel binary-search splitting: pick the median of the larger sorted array, binary-search its rank in the other array in time, and recursively merge both halves in parallel.- Merge span: .
- Overall Merge Sort span: .
- Parallelism improves dramatically to , while work stays optimal .
Parallel Prefix Sum (Blelloch Scan)
Given and an associative operator , computing all prefix sums appears sequential, yet Blelloch's tree-based scan computes it in two balanced binary-tree passes:
- Up-Sweep (Reduce Pass): Bottom-up pairs sum into a binary tree of height .
- Down-Sweep: Propagates prefix offsets from root back to leaves.
Total work is and span is , making parallel scan a fundamental building block for parallel quicksort partitioning, stream compaction, and radix sort.
| Algorithm | Work () | Span () | Parallelism () |
|---|---|---|---|
| Parallel Reduction (Sum/Max) | |||
| Blelloch Parallel Prefix Sum | |||
| Parallel Merge Sort (Seq. Merge) | |||
| Parallel Merge Sort (Par. Merge) |
5.3 Map Reduce framework
MapReduce (Dean & Ghemawat, 2004) is a distributed data-parallel programming model and runtime for processing massive datasets across clusters of commodity machines with automatic data partitioning, shuffling, and fault tolerance.
Map and Reduce Signatures
A MapReduce computation transforms input key-value pairs through two user-defined pure functions:
Between map and reduce, the framework automatically performs partitioning, sorting, and shuffling, grouping all intermediate values sharing the same key onto a single reducer task.
Execution Pipeline and Optimizations
- Input Split & Map Phase: Input files stored on a distributed file system (HDFS/GFS) are split into blocks (e.g., ); map workers process splits locally (data locality) to minimize network traffic.
- Combiner (Mini-Reducer): Runs optionally on each mapper's local output before network shuffle to pre-aggregate associative/commutative operations (e.g., summing local word counts), drastically reducing shuffle bandwidth.
- Shuffle & Sort: Hash-partitions intermediate keys (
hash(k2) mod R) to reducers and merge-sorts keys at each reducer. - Reduce Phase & Fault Tolerance: Each reducer iterates over
(k2, list(v2))and writes final outputs. Becausemapandreduceare deterministic and side-effect free, failed worker tasks are recovered simply by re-executing the lost task on another node (and speculative execution mitigates slow "straggler" nodes).
def mapper(doc_id, text):
# Emit (word, 1) for every token in the document
for word in text.lower().split():
yield (word, 1)
def combiner(word, counts):
# Local pre-aggregation before network shuffle
yield (word, sum(counts))
def reducer(word, counts):
# Global aggregation across all map partitions
yield (word, sum(counts))2
Two document splits are processed by a MapReduce Word Count job:
- Split 1:
"data graph data stream data" - Split 2:
"graph stream graph"
Compare the total number of (word, count) pairs sent across the network during the Shuffle phase without a combiner vs. with a local combiner, and write the final reducer outputs.
Without a combiner:
- Mapper 1 emits pairs:
("data", 1), ("graph", 1), ("data", 1), ("stream", 1), ("data", 1). - Mapper 2 emits pairs:
("graph", 1), ("stream", 1), ("graph", 1).
Total pairs shuffled over the network pairs.
With a local combiner on each mapper:
- Mapper 1 combines locally to pairs:
("data", 3), ("graph", 1), ("stream", 1). - Mapper 2 combines locally to pairs:
("graph", 2), ("stream", 1).
Total pairs shuffled pairs (reducing shuffle records from to , and by orders of magnitude on large documents).
Final Reducer outputs: After grouping by key:
reducer("data", [3])("data", 3)reducer("graph", [1, 2])("graph", 3)reducer("stream", [1, 1])("stream", 2)
(Total word occurrences across both splits .)
Without a combiner, pairs cross the network; with a combiner, only pairs are shuffled. The final outputs are ("data", 3), ("graph", 3), ("stream", 2).
5.4 Distributed graph processing
MapReduce handles independent record batches well, but iterative graph algorithms (PageRank, BFS, connected components, shortest paths) require shipping the entire static graph structure across the network at every iteration. Distributed graph processing frameworks (such as Google's Pregel, Apache Giraph, and GraphX) keep the graph partitioned in memory across workers.
Think-Like-a-Vertex (BSP / Pregel) Model
In the Bulk Synchronous Parallel (BSP) vertex-centric model, computation proceeds in a sequence of synchronized supersteps :
- Compute: Every active vertex executes a user-defined
compute(messages)function in parallel, reading messages sent to in superstep , updating 's local state, and sending messages along outgoing edges for superstep . - Barrier Synchronization: Workers exchange messages and wait at a global barrier before starting superstep .
- Termination (
voteToHalt): A vertex marks itself inactive viavoteToHalt(), and wakes up again only if it receives a new message in a future superstep. The job terminates when all vertices are inactive and no messages are in flight.
Partitioning Challenges: Edge-Cut vs. Vertex-Cut
- Edge-Cut Partitioning (Pregel): Assigns each vertex (and its adjacency list) to one worker machine, cutting edges that span workers. Works well for low-degree graphs, but high-degree "hub" vertices in real-world power-law graphs cause severe load imbalance and message bottlenecks.
- Vertex-Cut Partitioning (PowerGraph / GraphLab): Assigns each edge to a worker and replicates high-degree vertices across multiple machines (combining partial updates via gather-apply-scatter), balancing work evenly on skewed power-law networks.
3
Trace Pregel Single-Source Shortest Path (SSSP) from source vertex on a directed weighted graph with edges , , , and . Initialize and all other distances to , and show the active vertices, updated distances, and messages sent in each BSP superstep until termination.
Superstep 0:
- Only updates/initializes (others hold and vote to halt).
- sends
(B, 0 + 4 = 4)to and(C, 0 + 2 = 2)to , then callsvoteToHalt().
Superstep 1:
- wakes on message
4: , sends(D, 4 + 5 = 9)to , and callsvoteToHalt(). - wakes on message
2: , sends(B, 2 + 1 = 3)to , and callsvoteToHalt().
Superstep 2:
- wakes on message
3: relaxes , sends improved(D, 3 + 5 = 8)to , and callsvoteToHalt(). - wakes on message
9: (no outgoing edges), and callsvoteToHalt().
Superstep 3 and Termination:
- wakes on message
8: relaxes , sends no messages, and callsvoteToHalt(). - At the barrier after Superstep 3, all vertices have halted and no messages remain in flight, so the algorithm terminates.
The Pregel SSSP job completes in supersteps ( through ) with final shortest distances , , , and .
Exercises
Practice Exercises — Parallel and Distributed Algorithms
State Brent's Theorem and Amdahl's Law. A parallel program has a strictly sequential portion and a parallelizable portion. Calculate its speedup and efficiency on processors, and find the minimum sequential fraction that would cap speedup at regardless of .
Brent's Theorem and Amdahl's Law: Brent's Theorem bounds -processor execution time by , showing linear speedup as long as . Amdahl's Law caps speedup for fixed problem size when a serial fraction cannot be parallelized: .
Speedup, efficiency (), and maximum serial fraction for cap:
- For , , :
- As , ().
For and , speedup is with efficiency. Limiting asymptotic speedup to corresponds to a sequential fraction.
Explain why parallel merge sort with a sequential merge only achieves parallelism, and how parallel merge improves its span to . Using Brent's Theorem, bound the runtime on processors for a computation with work units and span units.
Parallel merge sort span bottleneck: With sequential merging, the final top-level merge of two size- halves takes sequential steps, forcing and capping parallelism . Parallel binary-search merging splits the merge recursively in span, lowering overall sort span to and boosting parallelism to .
Brent's Theorem bound ():
(or using the relaxed bound units).
Sequential merge creates an span bottleneck, whereas parallel merge reduces span to . By Brent's Theorem, (at most under ).
Trace Blelloch's parallel exclusive prefix sum (up-sweep and down-sweep passes) on the -element array , and state its work and span complexities.
Up-Sweep (Reduce Pass) to build pairwise tree sums:
- Level 1 pairs: (stored at indices ).
- Level 2 pairs: (stored at indices ).
- Level 3 root: (stored at index ).
Down-Sweep Pass (set root to ; push left_child = parent, right_child = parent + old_left):
- Root at becomes .
- Split to and : left gets , right gets .
- Split to pairs: , ; , .
- Split to leaves:
- ,
- ,
- ,
- , .
Thus the exclusive prefix sums are (total sum ). Both passes take work and span.
Blelloch's scan runs in work and span, producing exclusive prefix sums (and inclusive sums ).
Describe the MapReduce execution pipeline from input splits to final output, explaining the role of the Combiner, Shuffle/Sort, and how MapReduce achieves fault tolerance without checkpointing intermediate RAM state. Design map and reduce pseudocode to compute an inverted index (word -> list of unique doc_ids).
MapReduce pipeline, combiner, and fault tolerance: Map tasks read local HDFS splits and emit intermediate (k2, v2) pairs. An optional Combiner pre-aggregates identical keys on the mapper node before the Shuffle/Sort phase partitions keys by hash and sorts them by at each reducer. Reducers receive (k2, list(v2)) and write final results to distributed storage. Because mappers write output to local disk and functions are deterministic, failed map or reduce tasks are simply re-executed on healthy workers (with speculative duplicate runs handling slow stragglers).
Inverted Index map and reduce:
def map_inverted_index(doc_id, text):
seen = set()
for word in text.lower().split():
if word not in seen:
seen.add(word)
yield (word, doc_id)
def reduce_inverted_index(word, doc_ids):
yield (word, sorted(set(doc_ids)))MapReduce pipelines Input Split -> Map -> (Combiner) -> Shuffle & Sort -> Reduce, achieving fault tolerance via deterministic task re-execution. The inverted index emits unique (word, doc_id) pairs in map and deduplicates/sorts doc_ids per word in reduce.
Compare MapReduce and Pregel (BSP vertex-centric) for iterative graph algorithms such as PageRank or BFS. Also distinguish between edge-cut and vertex-cut graph partitioning and explain why vertex-cut performs better on power-law graphs.
MapReduce vs. Pregel for iterative graph algorithms: MapReduce is stateless between jobs: each iteration must reload, shuffle, and re-serialize the entire graph structure over disk and network, creating massive I/O overhead. Pregel keeps graph topology resident in worker memory and passes only small state messages along edges across BSP supersteps, running orders of magnitude faster on iterative traversals and PageRank.
Edge-cut vs. vertex-cut partitioning:
- Edge-cut assigns vertices to partitions and cuts cross-partition edges; high-degree hub vertices in power-law graphs create skewed storage, compute, and message bottlenecks on the machine owning the hub.
- Vertex-cut assigns edges evenly across machines and splits/replicates high-degree vertices across workers, balancing memory and communication load across skewed degree distributions.
Pregel avoids MapReduce's per-iteration graph re-shuffling by keeping the graph in memory and exchanging messages in BSP supersteps. Vertex-cut distributes edges rather than vertices, eliminating high-degree hub bottlenecks in power-law graphs.