PadhaikoAll subjects

Parallel and Distributed Algorithms

Advanced Algorithms (ENCT 467)

Open in the Padhaiko app

5.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.

Definition

Work, Span, Speedup, and Efficiency

Using the DAG (work-span) model of multithreaded computation:

Theorem

Brent's Theorem and Amdahl's Law

  1. Work and Span Laws: For any scheduler on processors, and .
  2. Brent's Theorem: Any DAG with work and span can be scheduled on processors in time:
  1. 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:
  1. 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:

Example 1

1

Suppose of an algorithm's execution time () is perfectly parallelizable and () is strictly sequential.

  1. Compute the maximum speedup and parallel efficiency on processors using Amdahl's Law.
  2. 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 ):
Answer:

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

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:

  1. Up-Sweep (Reduce Pass): Bottom-up pairs sum into a binary tree of height .
  2. 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.

Work and Span of Parallel Divide-and-Conquer Algorithms
AlgorithmWork ()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.

Definition

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

  1. 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.
  2. 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.
  3. Shuffle & Sort: Hash-partitions intermediate keys (hash(k2) mod R) to reducers and merge-sorts keys at each reducer.
  4. Reduce Phase & Fault Tolerance: Each reducer iterates over (k2, list(v2)) and writes final outputs. Because map and reduce are 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).
MapReduce Word Count with Local Combiner LogicPython
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))
Example 2

2

Two document splits are processed by a MapReduce Word Count job:

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 .)

Answer:

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.

Definition

Think-Like-a-Vertex (BSP / Pregel) Model

In the Bulk Synchronous Parallel (BSP) vertex-centric model, computation proceeds in a sequence of synchronized supersteps :

  1. 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 .
  2. Barrier Synchronization: Workers exchange messages and wait at a global barrier before starting superstep .
  3. Termination (voteToHalt): A vertex marks itself inactive via voteToHalt(), 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

Example 3

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 calls voteToHalt().

Superstep 1:

  • wakes on message 4: , sends (D, 4 + 5 = 9) to , and calls voteToHalt().
  • wakes on message 2: , sends (B, 2 + 1 = 3) to , and calls voteToHalt().

Superstep 2:

  • wakes on message 3: relaxes , sends improved (D, 3 + 5 = 8) to , and calls voteToHalt().
  • wakes on message 9: (no outgoing edges), and calls voteToHalt().

Superstep 3 and Termination:

  • wakes on message 8: relaxes , sends no messages, and calls voteToHalt().
  • At the barrier after Superstep 3, all vertices have halted and no messages remain in flight, so the algorithm terminates.
Answer:

The Pregel SSSP job completes in supersteps ( through ) with final shortest distances , , , and .


Exercises

Practice Exercises — Parallel and Distributed Algorithms

Question 1

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 , ().
Answer:

For and , speedup is with efficiency. Limiting asymptotic speedup to corresponds to a sequential fraction.

Question 2

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).

Answer:

Sequential merge creates an span bottleneck, whereas parallel merge reduces span to . By Brent's Theorem, (at most under ).

Question 3

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.

Answer:

Blelloch's scan runs in work and span, producing exclusive prefix sums (and inclusive sums ).

Question 4

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:

MapReduce Inverted IndexPython
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)))
Answer:

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.

Question 5

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.
Answer:

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.

← String and Pattern Matching AlgorithmsApproximation and Optimization Algorithms →