Offensive Security Researcher & Quantum Cryptography Analyst

Multithreaded Algorithms: A Comprehensive Guide to Parallel Computing

Abdul Wahab Junaid
Multithreaded Algorithms: A Comprehensive Guide

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

How It Works

I typically design a multithreaded algorithm using a divide-and-conquer strategy adapted for parallel execution:

  1. I identify a way to split the problem into independent (or mostly independent) subproblems.
  2. I “spawn” one or more subproblems to run in parallel (conceptually, on separate threads).
  3. I recursively continue splitting until subproblems are small enough to solve directly (a base case).
  4. I “sync,” waiting for all spawned subtasks to complete before combining their results.
  5. 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].

  1. I split into [5, 2, 9] and [1, 6, 3], spawning the first half to sort in parallel with the second.
  2. 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]).
  3. At the base cases, single-element arrays are trivially sorted.
  4. I merge back up: [2] and [9] merge to [2, 9]; [6] and [3] merge to [3, 6].
  5. I merge [5] and [2, 9] to get [2, 5, 9]; I merge [1] and [3, 6] to get [1, 3, 6].
  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

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

Disadvantages

Applications

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

Common Mistakes

Further Reading

Exit mobile version