I want to explain how I design algorithms that run across multiple threads of execution simultaneously, rather than sequentially, so I can exploit multi-core hardware to solve problems faster. I focus in this guide on the fork-join model of parallelism, since I find it the cleanest conceptual framework for reasoning about multithreaded algorithms, and I use it to analyze classic examples such as parallel merge sort and parallel matrix multiplication.
History and Background
I see the theoretical roots of multithreaded algorithm analysis in the work on PRAM (Parallel Random Access Machine) models developed in the 1970s and 1980s. The fork-join model I focus on here was popularized through systems like Cilk, developed at MIT in the 1990s by Charles Leiserson and colleagues, which introduced the elegant spawn/sync primitives I still use conceptually today (and which inspired constructs in modern languages and libraries, including OpenMP and the Java Fork/Join framework). As multi-core processors became mainstream in the 2000s, multithreaded algorithm design shifted from a specialized research topic to a mainstream necessity for performance-critical software.
Problem Statement
I want to take a computational problem — for example, sorting an array or multiplying matrices — and design an algorithm that divides the work among multiple threads running concurrently, so that the total wall-clock time decreases as I add more processing cores, while still producing a correct result equivalent to the sequential algorithm.
Core Concepts
- Thread: an independent sequence of execution that can run concurrently with other threads.
- Fork-join parallelism: a model where a computation can “spawn” a new parallel subtask and later “sync” (wait) for it to complete.
- Work: the total amount of computation performed across all threads, denoted $T_1$ (time on 1 processor).
- Span (critical path length): the longest chain of sequentially dependent operations, denoted $T_\infty$ (time on infinite processors).
- Speedup: the ratio $T_1 / T_P$, where $T_P$ is the time using
Pprocessors. - Parallelism: the ratio $T_1 / T_\infty$, representing the maximum possible speedup.
- Race condition: a bug that occurs when multiple threads access shared data concurrently without proper synchronization, leading to nondeterministic results.
How It Works
I typically design a multithreaded algorithm using a divide-and-conquer strategy adapted for parallel execution:
- I identify a way to split the problem into independent (or mostly independent) subproblems.
- I “spawn” one or more subproblems to run in parallel (conceptually, on separate threads).
- I recursively continue splitting until subproblems are small enough to solve directly (a base case).
- I “sync,” waiting for all spawned subtasks to complete before combining their results.
- I combine the results of the subproblems into the solution for the original problem, being careful to avoid race conditions when writing shared data.
Working Principle
I reason about a multithreaded algorithm’s performance using the work-span model. The work $T_1$ is simply the total operations the algorithm would perform if run on a single processor (i.e., the sequential running time). The span $T_\infty$ is the length of the longest path of dependent operations — the part of the computation that cannot be parallelized away, no matter how many processors I have. I know that the actual running time on P processors, $T_P$, is bounded below by both $T_1 / P$ (I cannot go faster than perfectly dividing the work) and $T_\infty$ (I cannot go faster than the critical path).
Mathematical Foundation
I express the key bounds of the work-span model as:
$$ T_P \ge \frac{T_1}{P} \quad \text{(work bound)} $$
$$ T_P \ge T_\infty \quad \text{(span bound)} $$
The parallelism of an algorithm, representing the maximum theoretical speedup regardless of processor count, is:
$$ \text{Parallelism} = \frac{T_1}{T_\infty} $$
For a greedy scheduler, I have the useful bound:
$$ T_P \le \frac{T_1}{P} + T_\infty $$
For parallel merge sort, I can express the recurrences for work and span as:
$$ T_1(n) = 2 T_1(n/2) + O(n) \implies T_1(n) = O(n \log n) $$
$$ T_\infty(n) = T_\infty(n/2) + O(\log n) \implies T_\infty(n) = O(\log^2 n) $$
(using a parallel merge step that itself takes $O(\log n)$ span).
Diagrams
flowchart TD
A["Problem of size n"] --> B["Spawn: solve left half in parallel"]
A --> C["Solve right half"]
B --> D["Sync: wait for both halves"]
C --> D
D --> E["Combine results (e.g., parallel merge)"]
E --> F["Return solution"]
Pseudocode
P-MERGE-SORT(A, p, r)
if p < r
q = (p + r) / 2
spawn P-MERGE-SORT(A, p, q)
P-MERGE-SORT(A, q + 1, r)
sync
P-MERGE(A, p, q, r)
P-MERGE(A, p, q, r)
// I merge two sorted subarrays A[p..q] and A[q+1..r] in parallel
// using a parallel binary-search-based merge (span O(log n))
n1 = q - p + 1
n2 = r - q
if n1 < n2
swap roles of the two subarrays
if n1 == 0
return
mid1 = (p + q) / 2
mid2 = BINARY-SEARCH(A[mid1], A, q+1, r)
place A[mid1] into its correct merged position
spawn P-MERGE(A, p, mid1 - 1, mid2 - 1)
P-MERGE(A, mid1 + 1, q, mid2, r)
sync
Step-by-Step Example
I trace through parallel merge sort on the array [5, 2, 9, 1, 6, 3].
- I split into
[5, 2, 9]and[1, 6, 3], spawning the first half to sort in parallel with the second. - Each half recursively splits further:
[5, 2, 9]becomes[5]and[2, 9](which splits into[2]and[9]);[1, 6, 3]becomes[1]and[6, 3](which splits into[6]and[3]). - At the base cases, single-element arrays are trivially sorted.
- I merge back up:
[2]and[9]merge to[2, 9];[6]and[3]merge to[3, 6]. - I merge
[5]and[2, 9]to get[2, 5, 9]; I merge[1]and[3, 6]to get[1, 3, 6]. - Finally, I merge
[2, 5, 9]and[1, 3, 6], using the parallel merge procedure, to get the fully sorted array[1, 2, 3, 5, 6, 9].
Because I spawned independent subproblems at each level, I know that in principle, with enough processors, the sorts of [5,2,9] and [1,6,3] could have run simultaneously, and within each of those, the further splits could also run simultaneously.
Time Complexity
- Work $T_1$: $O(n \log n)$ for parallel merge sort, matching sequential merge sort, since the total amount of computation does not change — I am only changing how it’s scheduled across processors.
- Span $T_\infty$: $O(\log^2 n)$ when I use a parallel merge subroutine; if I instead use an ordinary sequential merge step, the span degrades to $O(n)$, since the merge itself would become the bottleneck.
- Parallelism: $T_1 / T_\infty = O(n \log n) / O(\log^2 n) = O(n / \log n)$, meaning the theoretical maximum speedup grows almost linearly with
n. - Best/average/worst case: the work and span bounds above hold regardless of the specific input values, since merge sort’s structure doesn’t depend on input order (unlike, say, quicksort).
Space Complexity
I need $O(n)$ auxiliary space for the temporary arrays used during merging, matching sequential merge sort. I also incur some additional overhead per spawned task for thread/task management (stack space, scheduler bookkeeping), which I treat as a constant-factor overhead rather than an asymptotic change.
Correctness Analysis
I justify correctness in two layers. First, the sequential logic of merge sort itself is correct by induction: sorting two halves and merging them produces a fully sorted array, assuming the merge step is correct. Second, I need to ensure that parallel execution introduces no race conditions — in parallel merge sort, the two recursive calls operate on disjoint sub-ranges of the array, and the “sync” step guarantees I never read the results of a spawned subtask before it has completed. Because the subtasks never write to overlapping memory regions, and I always wait for all writes to finish before proceeding to the merge step, the algorithm’s result is identical to the sequential version, regardless of how the scheduler interleaves the threads.
Advantages
- I gain substantial speedups on multi-core hardware for large inputs, since I can exploit available parallelism.
- The work-span model gives me clean, portable tools for reasoning about scalability, independent of the exact number of processors.
- Fork-join frameworks (Cilk, OpenMP, Java Fork/Join, .NET TPL) handle scheduling automatically, so I don’t need to manually manage thread pools in most cases.
- The same divide-and-conquer structure I already use in sequential algorithms often extends naturally to a parallel version.
Disadvantages
- I incur overhead from spawning and synchronizing threads, which can outweigh the benefits for small problem sizes.
- Race conditions and other concurrency bugs are notoriously difficult for me to detect and debug.
- Not all algorithms parallelize well — some have inherently sequential dependencies that keep the span high regardless of how I restructure the work.
- Multithreaded code is generally harder to reason about, test, and maintain than sequential code.
- Speedup is bounded by Amdahl’s Law: if some fraction of the algorithm must run sequentially, that portion limits the maximum achievable speedup no matter how many processors I add.
Applications
- Sorting and searching: parallel merge sort, parallel quicksort, and parallel search algorithms in large datasets.
- Scientific computing: parallel matrix multiplication, numerical simulations, and finite-element methods.
- Machine learning: parallel training algorithms, particularly for large-scale gradient computations.
- Graphics and rendering: ray tracing and rendering pipelines are often massively parallelized.
- Databases: parallel query execution and parallel joins across large tables.
- Compilers and build systems: parallelizing independent compilation units.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#define THRESHOLD 1000 /* below this size, I sort sequentially to avoid thread overhead */
typedef struct {
int *arr;
int left;
int right;
} SortArgs;
void merge(int *arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int *L = malloc(n1 * sizeof(int));
int *R = malloc(n2 * sizeof(int));
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
free(L);
free(R);
}
void sequentialSort(int *arr, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
sequentialSort(arr, left, mid);
sequentialSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
/* I define a thread entry point that recursively parallel-sorts a sub-range */
void *parallelSortThread(void *args);
void parallelSort(int *arr, int left, int right) {
if (right - left < THRESHOLD) {
sequentialSort(arr, left, right);
return;
}
int mid = left + (right - left) / 2;
/* I spawn a thread to sort the left half while I handle the right half myself */
SortArgs leftArgs = { arr, left, mid };
pthread_t thread;
pthread_create(&thread, NULL, parallelSortThread, &leftArgs);
parallelSort(arr, mid + 1, right); /* I sort the right half on the current thread */
pthread_join(thread, NULL); /* this is my "sync" point */
merge(arr, left, mid, right);
}
void *parallelSortThread(void *args) {
SortArgs *sa = (SortArgs *)args;
parallelSort(sa->arr, sa->left, sa->right);
return NULL;
}
int main(void) {
int n = 20;
int arr[20] = {17, 3, 9, 22, 5, 1, 14, 8, 30, 2,
25, 11, 6, 19, 4, 28, 13, 7, 21, 10};
printf("Before sorting: ");
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
parallelSort(arr, 0, n - 1);
printf("After sorting: ");
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
return 0;
}
I used POSIX threads (pthread) to implement the “spawn” and “sync” primitives conceptually: pthread_create corresponds to spawning a subtask, and pthread_join corresponds to syncing. I included a THRESHOLD so that for small sub-arrays, I fall back to sequential sorting, since thread creation overhead would otherwise dominate the actual sorting work. To compile this, I would use gcc -pthread to link the threading library.
Sample Input and Output
Input: [17, 3, 9, 22, 5, 1, 14, 8, 30, 2, 25, 11, 6, 19, 4, 28, 13, 7, 21, 10]
Output:
Before sorting: 17 3 9 22 5 1 14 8 30 2 25 11 6 19 4 28 13 7 21 10
After sorting: 1 2 3 4 5 6 7 8 9 10 11 13 14 17 19 21 22 25 28 30
Optimization Techniques
- Thresholding: I always fall back to sequential execution below a size threshold, since thread creation overhead outweighs the benefit for small inputs — this is essential in practice.
- Thread pools: instead of creating and destroying threads for every spawn, I use a persistent pool of worker threads (as libraries like Cilk, OpenMP, and Java Fork/Join do internally) to reduce overhead.
- Work-stealing schedulers: I let idle processors “steal” pending tasks from busy ones, which balances load automatically without central coordination.
- Cache-aware parallel algorithms: I structure memory access patterns (e.g., parallel merge using blocking) to minimize cache contention between threads.
- Avoiding false sharing: I make sure independent threads don’t write to different variables that happen to sit on the same cache line, since that silently serializes performance.
Common Mistakes
- Forgetting to synchronize (
join/sync) before reading results from a spawned thread, leading to race conditions or reading uninitialized data. - Creating too many threads for small subproblems, causing overhead to dominate and actually slow the program down compared to the sequential version.
- Writing to shared memory from multiple threads without proper synchronization, causing nondeterministic bugs that are hard to reproduce.
- Assuming perfect linear speedup with
Pprocessors, ignoring the span bound and Amdahl’s Law. - Not freeing thread-related resources (like
pthread_joining every created thread), leading to resource leaks.
Further Reading
- Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms, Chapter 27 (Multithreaded Algorithms): https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- Blumofe, Leiserson — “Scheduling Multithreaded Computations by Work Stealing,” Journal of the ACM, 1999: https://dl.acm.org/doi/10.1145/324133.324234
- Frigo, Leiserson, Randall — “The Implementation of the Cilk-5 Multithreaded Language,” PLDI, 1998: https://dl.acm.org/doi/10.1145/277650.277725
- OpenMP Architecture Review Board — OpenMP Specifications: https://www.openmp.org/specifications/
- POSIX Threads Programming Guide (LLNL): https://hpc-tutorials.llnl.gov/posix/
