Skip to content
Tutorials Center
My learning

Topics

Lesson 199 of 225 ยท Advanced Topics

Parallel and External Algorithms

Learn external merge sort, the MapReduce idea, work and span for parallel algorithms, and the cache-oblivious trick, with Python simulations you can run.

Everything so far assumed a tidy machine: one processor, all the data in fast memory, and every memory access costing the same. Real systems break each of those assumptions. Your data may be bigger than RAM and live on disk. You may have eight cores, or eight hundred machines. And memory itself is a hierarchy where a nearby byte is far cheaper to read than a distant one.

This lesson introduces the three standard answers. External algorithms minimize disk transfers when data does not fit in memory. Parallel algorithms split work so many workers can run at once. Cache-aware and cache-oblivious algorithms arrange memory access so the hardware cache helps instead of hurting. We will simulate each idea in plain Python, counting operations rather than timing anything, so the results are exact and repeatable.

A different cost model

When a dataset lives on disk, reading one number costs almost nothing extra compared to reading its neighbors: the disk hands you a whole block at once. So the model changes. Instead of counting comparisons, we count block transfers (also called I/Os).

TEXT
        fast, small                 slow, huge
  +------------------+         +-----------------------------+
  |  memory: M items |  <----> |  disk: N items, in blocks   |
  +------------------+  block  | [B][B][B][B][B][B][B][B]... |
                        of B    +-----------------------------+

With block size B and memory size M, scanning N items costs about N / B transfers, not N. An algorithm that jumps around randomly can cost one transfer per item, which is B times worse. Algorithms in this model are designed to scan and to merge, never to hop.

External merge sort

Suppose you must sort a file with a billion numbers but memory holds only a million. Quick sort and heap sort jump around randomly, so they are terrible here. Merge sort is almost perfectly suited, because merging two sorted sequences only ever reads each of them from front to back.

External merge sort has two phases:

  1. Run formation. Read as many items as fit in memory, sort them with any in-memory sort, and write the sorted chunk back to disk as a run. After this phase the file is a list of sorted runs.
  2. Merging. Merge several runs at once into one longer run, repeating until one run remains. Memory can hold one buffer per input run, so you can merge many runs at a time, not just two.

Here is a simulation. The "disk" is a list of runs and the "memory" limit is a small number of items:

Python External merge sort: run formation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Twenty items with memory for six gives four runs (6, 6, 6 and 2 items). heapq.merge is exactly the k-way merge from merging k sorted lists: it keeps one candidate per run in a small heap and always emits the smallest.

How many passes?

In real life you cannot merge every run at once, because each run needs its own buffer in memory. If memory holds k buffers, each merge pass combines up to k runs into one, so the number of runs shrinks by a factor of k each pass:

TEXT
runs:   64  ->  8  ->  1        (fan-in k = 8, two merge passes)
runs:   64  -> 32 -> 16 -> 8 -> 4 -> 2 -> 1   (fan-in k = 2, six passes)

The number of merge passes is ceil(log_k(runs)), and every pass reads and writes the whole file once. The total cost is therefore about (N / B) * (1 + ceil(log_k(N / M))) block transfers. That is the optimal bound for sorting in this model up to constant factors, and it explains why a larger fan-in matters: it cuts whole passes over the data.

Python Multi-pass merging with limited fan-in

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With 20 initial runs, merging two at a time needs five passes, four at a time needs three, and ten at a time needs two. Each pass would be a full read and write of a huge file, so saving passes saves real time.

Real database engines and tools such as the Unix sort command do precisely this when their input exceeds memory. They also use a trick called replacement selection to produce runs about twice as long as memory, which cuts the number of runs in half.

Work and span: measuring parallel algorithms

Now suppose you have many workers (cores, or machines). Running time is no longer one number. Two quantities describe a parallel algorithm:

  • Work T1: the total number of operations, the time on a single worker.
  • Span Tโˆž (also called depth or critical path length): the time with unlimited workers, set by the longest chain of operations that must happen one after another.

With p workers, the running time can never be better than max(work / p, span). A good parallel algorithm keeps the work close to the best sequential algorithm and makes the span tiny.

Take summing n numbers. A loop with one running total has work n and span n: every addition waits for the previous one. A tree reduction adds pairs at the same time, then pairs of pairs:

TEXT
values:   3   1   4   1   5   9   2   6
round 1:    4       5      14       8      (4 additions at once)
round 2:        9              22          (2 additions at once)
round 3:                31                 (1 addition)
Python Tree reduction: work versus span

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The work is n - 1 additions, the same as the sequential loop, but the span is only ceil(log2 n) rounds. With enough workers, a thousand numbers are added in 10 steps instead of 999. That is the pattern behind most parallel algorithms: restructure the computation as a tree, not a chain.

Not everything parallelizes. Operations that depend on the previous result (such as a running hash chain) have a long span no matter how many workers you add. Amdahl's law states the practical limit: if a fraction s of the program is inherently sequential, the speedup with any number of workers is at most 1 / s. If 10% must run in sequence, you can never go more than 10 times faster.

Python note: CPython threads do not run Python code truly in parallel because of the global interpreter lock (recent versions can optionally disable it). To use several cores for CPU-heavy work you normally use processes, for example concurrent.futures.ProcessPoolExecutor. Our in-browser Python runs in a single worker, so these examples simulate the splitting but do not actually run in parallel.

The MapReduce idea

When the data is spread across many machines, moving it is expensive, so you want to send small functions to the data instead. MapReduce is a pattern with three steps:

  1. Map: each worker processes its own slice and emits (key, value) pairs, completely independently.
  2. Shuffle: pairs with the same key are routed to the same worker (this is hashing at work: hash(key) % workers).
  3. Reduce: each worker combines all values for each of its keys.

Counting words across a huge text collection is the classic example. The map step is fully parallel, and each key's reduce step is independent of every other key.

Python MapReduce word count, simulated

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Real systems add two refinements. A combiner pre-adds counts inside each mapper (so a mapper sends ("the", 3) instead of three ("the", 1) pairs), shrinking the shuffle. And they handle skew: if one key is extremely common, its reducer becomes the bottleneck, the same problem as a bad hash function piling everything into one bucket.

Cache-aware and cache-oblivious algorithms

Even in RAM, memory is a hierarchy: registers, L1/L2/L3 caches, then main memory. The cache loads whole lines (say 64 bytes), so touching consecutive addresses is cheap and striding through memory is expensive. This is the same block model as the disk, one level up. See memory and data layout for the basics.

A cache-aware algorithm is tuned to specific values of B and M (for example, blocking a matrix into tiles that fit in cache). A cache-oblivious algorithm never mentions B or M, yet is efficient for every level of the hierarchy at once. The usual trick is divide and conquer: keep splitting the problem in half until the pieces are small enough to fit in whatever cache exists, without knowing its size.

Transposing a matrix shows the effect clearly. A matrix is stored row by row, so reading rows is sequential but reading columns is a stride. Below we simulate a tiny cache with least-recently-used replacement and count misses for a naive transpose and a recursive one:

Python Counting cache misses in a matrix transpose

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The naive version writes down a column, so each write lands on a different line and the 16-line cache keeps evicting lines before their neighbors are used. The recursive version works on ever smaller square-ish blocks, so once a block fits in the cache every line it touches is reused. It never needed to know the cache size, and here it reaches the minimum: every line is loaded exactly once. (Real hardware prefetching and associativity make real numbers messier, but the principle holds.)

Common mistakes

  • Counting comparisons for disk data. Sorting 100 GB with an algorithm that seeks randomly can be thousands of times slower than one that scans, even if both do O(n log n) comparisons.
  • Forgetting the merge buffers. Fan-in is limited by memory: k input buffers plus one output buffer must fit.
  • Assuming more workers always helps. Span, shuffle cost and the sequential fraction (Amdahl) set hard limits, and coordination has its own costs.
  • Ignoring skew. One hot key or one huge partition leaves every other worker idle.
  • Parallelizing the wrong thing. Make the algorithm correct and efficient sequentially first, then look for independent pieces.

When to use these ideas

Reach for external algorithms when data is much larger than memory (large sorts, joins and indexes in databases; this is why B-trees have very wide nodes). Reach for parallel and MapReduce-style designs when the work divides into independent pieces whose results combine with an associative operation (sum, max, merge, count). Think about cache behavior in tight loops over big arrays: prefer sequential access and blocking, and treat divide and conquer as a free locality bonus. For most everyday programs, none of this matters until profiling shows it does.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is merge sort a good fit for sorting data that does not fit in memory?

    Merging only moves forward through each run, which matches how disks work (whole blocks, sequential access). Quick sort and heap sort jump around and would cause many more transfers.
  2. 2. Memory holds 5 items, there are 100 items, and each merge pass combines 10 runs at a time. How many merge passes follow run formation?

    100 / 5 gives 20 runs. One pass with fan-in 10 leaves 2 runs, and a second pass leaves 1. That is ceil(log10 20) = 2 passes.
  3. 3. What is the span of a tree reduction that sums 1,024 numbers, assuming unlimited workers?

    Each round halves the number of values, so 1,024 values need log2(1024) = 10 rounds. The work is still 1,023 additions.
  4. 4. In MapReduce, what is the purpose of the shuffle step?

    Reducers need all values for a key in one place. The shuffle routes pairs by a function of the key, typically a hash modulo the number of reducers.
  5. 5. What makes an algorithm cache-oblivious?

    Cache-oblivious algorithms, usually recursive divide and conquer, adapt automatically to every level of the memory hierarchy. Tuning to a specific line size would be cache-aware instead.

Summary

  • When data lives on disk, count block transfers, not comparisons: scan and merge, never hop.
  • External merge sort forms memory-sized sorted runs, then merges k runs per pass; passes = ceil(log_k(runs)).
  • A parallel algorithm is described by its work (total operations) and span (longest dependent chain); tree reductions turn span n into log n.
  • Amdahl's law: the sequential fraction limits speedup to 1 / s however many workers you add.
  • MapReduce = independent map, a shuffle by key hash, then independent reduce; watch for skew and use combiners.
  • Cache-oblivious divide and conquer gets good locality at every memory level without knowing cache sizes.

Next: Advanced Amortized Structures