Parallelize This Algorithm

Merge sort, taken apart the way you would take apart any algorithm before parallelising it: which operations are independent, what the dependency structure is, what the critical path costs, and what synchronization is genuinely required. The answer to the last question is smaller than most people expect, and the reason is the lesson.

The algorithm

Read it with one question in mind: which two lines could run at the same time?

1function mergeSort(a) {
2  if (a.length <= 1) return a
3  const mid = a.length >> 1
4  const left  = mergeSort(a.slice(0, mid))   // independent of right
5  const right = mergeSort(a.slice(mid))      // independent of left
6  return merge(left, right)                  // depends on BOTH
7}

Every parallelisation starts here, not at a thread API. The four questions below are the ones worth asking of any algorithm — a sort, a graph traversal, a physics step, a batch of API calls. Answer all four before you write a single line of concurrent code.

Question 1

open

Which operations in merge sort are independent of each other?

Independent means neither reads what the other writes. Look at what each recursive call touches.

Nothing below is shown until you commit. Deciding wrong and being told why is the exercise.

Question 2

open

What is the dependency structure?

Draw it as a graph before you answer. What must finish before what?

Nothing below is shown until you commit. Deciding wrong and being told why is the exercise.

Question 3

open

What is the critical path — the span — of parallel merge sort with unlimited processors?

The span is the longest chain of dependent operations. Ask what still has to happen in order even if every independent task gets its own core.

Nothing below is shown until you commit. Deciding wrong and being told why is the exercise.

Question 4

open

What synchronization does this actually need?

Ask what is shared and mutable. If nothing is, the answer is smaller than you expect.

Nothing below is shown until you commit. Deciding wrong and being told why is the exercise.

The task graph

Locked until all four questions are answered.

0 of 4 answered

The scheduler is worth watching only once you have committed to a description of the dependencies. Otherwise it is an animation.