Lecture 8: Analysis of Multithreaded Algorithms

What this lecture covers

This lecture reviews the master method for solving divide-and-conquer recurrences, then applies work/span analysis to parallel loops implemented in Cilk, showing how the compiler translates cilk_for into recursive divide-and-conquer code and how grain size trades off scheduling overhead against parallelism. It builds on the previous lecture's definitions of work, span and parallelism and precedes a lecture on further parallel algorithm design.

After watching, you should be able to apply the three cases of the master method to a recurrence, analyze the work and span of nested parallel loops (including how parallelizing inner versus outer loops changes the results), reason about how grain size affects overhead, and follow how a matrix is indexed and recursively divided for a divide-and-conquer matrix multiplication.

Key ideas

• Master method: for recurrences of the form T(n) = a*T(n/b) + f(n), compare f(n) to n^(log_b a); three cases give the solution Θ(n^(log_b a)), Θ(n^(log_b a) log^(k+1) n), or Θ(f(n)) depending on which term dominates.
• Recursion tree: the technique of expanding a recurrence level by level and summing work across each level, used to derive and justify the master method's cases.
• Cilk loops as divide-and-conquer: cilk_for has no dedicated runtime primitive; the compiler translates it into a recursive program that splits the iteration range in half, spawning one half and calling the other, down to a base case.
• Grain size: the number of loop iterations handled serially at each leaf of the recursive splitting; larger grain size amortizes spawn overhead but can reduce parallelism.
• Work-efficient parallelization: a good parallel algorithm keeps work asymptotically the same as the best serial algorithm; parallelizing should mainly reduce span, not add work.
• Parallelizing outer vs. inner loops: parallelizing only the outer loop of a nested loop generally gives better practical performance than parallelizing the inner loop too, once there is enough parallelism relative to the processor count.
• Coarsening with explicit grain size: manually spawning work in chunks of size G trades off work overhead (S, spawn cost) against span, with an optimal chunk size often near sqrt(N) for evenly spread spawns.
• Divide-and-conquer matrix multiply: multiplying two n×n matrices by recursively multiplying four n/2 × n/2 submatrix pairs (eight multiplications) and summing, which requires careful submatrix address indexing within the outer matrix.

Walkthrough

The master method review (1:02)

The lecture reviews divide-and-conquer recurrences T(n) = a*T(n/b) + f(n) using a recursion tree: each level's total work sums to a^k * f(n/b^k), with log_b n levels and n^(log_b a) leaves. It states the three master method cases — leaves dominate, levels are balanced (add a log factor), or the root dominates — and works through several example recurrences by class quiz, including a case where the master method doesn't apply because of a negative log exponent, requiring the more general Akra-Bazzi method.

Parallelizing a matrix transpose (15:18)

An in-place matrix transpose with a triangular iteration space (parallelizing the outer loop only) is used to show how the OpenCilk compiler transforms a cilk_for into a recursive divide-and-conquer splitting structure. The lecture analyzes work as Θ(n²) (same as the serial doubly nested loop) and span as Θ(n) (log n for loop control plus linear span of the row work), giving Θ(n) parallelism, described as good for typical processor counts.

Parallelizing the inner loop too (29:36)

Parallelizing both loops keeps work at Θ(n²) but reduces span to Θ(log n), giving parallelism Θ(n²/log n) — more parallel in theory, but the lecture notes this isn't necessarily a better algorithm in practice, since parallelism only needs to exceed the processor count by enough (the "parallel slackness" idea from the previous lecture) to get good speedup.

Overhead and grain size in vector addition (38:49)

Using a simple vector-add example parallelized with cilk_for, the lecture introduces the OpenCilk grain-size pragma and derives formulas for work (n*I + (n/g - 1)*S, where I is per-iteration cost and S is spawn/return overhead) and span (roughly g*I + log(n/g)*S). It shows algebraically that making the grain size g much larger than S/I amortizes the spawn overhead to near zero, while very small grain sizes waste time on overhead.

An inefficient spawn-per-chunk implementation (54:02)

A second vector-add implementation that spawns a chunk of size G inside a loop is analyzed. With G=1, work is Θ(n) but span is also Θ(n) because the spawns form a long serial chain, giving parallelism Θ(1) — described as "puny." Increasing G gives span Θ(n/G + G), minimized at G ≈ √n, yielding parallelism Θ(√n).

Performance tips and matrix multiplication (1:03:23)

The lecture lists practical tips: minimize span, aim for roughly 10x more parallelism than processors, trade excess parallelism for reduced work overhead via coarsening, prefer divide-and-conquer/parallel loops over spawning individual small tasks, and prefer parallelizing outer loops over inner loops. It then analyzes standard triply nested parallel matrix multiplication (work Θ(n³), span Θ(n), parallelism around Θ(n²)) and introduces a divide-and-conquer alternative that recursively multiplies four submatrix pairs, walking through the indexing arithmetic needed to address submatrices embedded in a larger row-major matrix.

Before you watch

• Review the master method for solving recurrences from a prior algorithms course, since the lecture assumes familiarity and moves through it quickly as review.
• Watch the previous lecture on races and parallelism in this course, since it defines work, span, parallelism and parallel slackness, which this lecture applies throughout.
• Basic comfort with C-style nested loops and matrix indexing will help with the later examples.

Check your understanding

1. In the master method, what distinguishes case 1, case 2 and case 3, and what property of f(n) determines which case applies?
2. Why does the Cilk runtime translate a cilk_for loop into a recursive divide-and-conquer structure instead of using a dedicated loop primitive?
3. In the matrix transpose example, why does parallelizing only the outer loop already give Θ(n) parallelism, and what does parallelizing the inner loop too add or cost?
4. In the grain-size analysis of vector addition, why does increasing the grain size reduce work overhead but also risk reducing parallelism?
5. Why is the naive spawn-per-single-element vector-add implementation described as having "puny" parallelism, and how does increasing the chunk size fix it?