Parallel Reduction

Why Parallel Reduction Matters

Imagine five services report completed orders: [3,1,7,0,4]. You need one total, 15. A sequential accumulator combines each new value with the previous total; later additions wait on earlier additions. A reduction tree first computes independent neighboring subtotals, then combines those subtotals. The available parallelism is widest near the input and narrows toward the single answer.

Parallel reduction combines a sequence into one value using an associative binary operation. Sum, minimum, maximum, Boolean any/all, and fixed-size summary records are common examples. A scan instead returns every prefix result; reduction returns just the aggregate. Computing a whole scan solely to obtain its final value usually performs unnecessary work.

This lesson starts with exact integer addition, explains an order-preserving generic operation, and builds a deterministic worker simulator. You will trace every pair and odd carry, prove that every original value appears exactly once, derive exact operation and round counts, and distinguish theoretical parallel time from the execution time of the teaching program. The code deliberately simulates worker assignments; it creates no threads. Actual scheduling, synchronization, and hardware costs require a parallel implementation and measurement.

Recall algorithm analysis for work/span and queues for the idea that a worker can execute one ready job at a time. The important new constraint is dependency: no job in a later level may consume a subtotal before the producing level finishes.

Core Concepts and Terminology

Let the input be $a=[a_0,a_1,\ldots,a_{n-1}]$ and the combine operation be $\oplus$. For a nonempty input the result is

$$R=a_0\oplus a_1\oplus\cdots\oplus a_{n-1}.$$

The grouping may change, but the operand sequence stays the same. Associativity means

$$(x\oplus y)\oplus z=x\oplus(y\oplus z).$$

It permits a balanced tree in place of a sequential chain. Commutativity, $x\oplus y=y\oplus x$, permits exchanging operands and is a different property. This lesson requires associativity and preserves order, so commutativity is unnecessary. String concatenation is a useful test: ("a"+"b")+("c"+"d") is "abcd", while swapping middle operands produces "acbd".

An identity $e$ satisfies $e\oplus x=x\oplus e=x$. An associative operation with identity is a monoid. We define the empty reduction as $R=e$; addition uses 0, multiplication 1, concatenation the empty string, Boolean OR false, and Boolean AND true. Mathematical maximum has identity $-\infty$ on the extended reals; on a bounded integer domain use its smallest allowed value. Zero is not a valid maximum identity when negative inputs are possible. A nonempty reduction only needs an associative operation, a semigroup; the supplied identity here establishes a meaningful empty case and supports later block/padding variants.

A current entry stores the reduction of one contiguous half-open input interval, $[\ell,r)$, including indices from $\ell$ through $r-1$. Half-open intervals join neatly: $[\ell,m)$ followed by $[m,r)$ becomes $[\ell,r)$. Entries always list these intervals in their original order. This is stronger than merely checking that their numerical sums look plausible.

A job either combines two neighboring entries or copies a lone last entry. Under our teaching model either job costs one unit; a carry performs zero combines. A worker handles at most one job per round. A wave is a group of jobs scheduled concurrently within one level, and a barrier waits for every job of that level. Work counts all elementary operations; span is the longest dependent chain with enough workers. These are properties of a computation, whereas a particular worker schedule can take more rounds than its span.

The first diagram uses eight inputs to show a complete tree. It has seven combines and three dependent levels. With two workers its first level takes two rounds, then each remaining level takes one: four rounds in total. The main worked example later uses five inputs to expose odd carries.

How Parallel Reduction Works, Step by Step

Maintain a source array current and, alongside each entry, the start and stop of its original input interval. Build a separate destination array at every level. The programs keep a trace of finished levels, not snapshots after each individual wave; every wave's job assignment and result is nevertheless recorded.

1. Validate the teaching API. Accept an integer worker count $1\le P\le64$ and length $0\le n\le256$. The sum wrapper additionally requires exact integer values between $-10^6$ and $10^6$. These bounds keep printed traces manageable and all supported language sums exact. The generic core assumes the supplied operation is pure and associative and the values are immutable; it cannot verify those algebraic properties.
2. Handle zero or one entry. Empty input returns the identity; a singleton returns its only value. Neither runs a level or calls the combine operation. A zero modeled round count means no reduction jobs, not zero host setup or validation time.
3. Create the next level. If the source has $q\gt1$ entries, its destination has $b=\lceil q/2\rceil$ entries. For each destination job $j$ take left source $L=2j$. If $L+1\lt q$, combine the two source values left before right and join their intervals. Otherwise copy the unmatched final value and its unchanged interval.
4. Assign workers. Job $j$ runs on worker $j\bmod P$ in wave $\lfloor j/P\rfloor$. For $b$ jobs there are $\lceil b/P\rceil$ modeled rounds. Sources of different jobs are disjoint and each destination has one writer. The programs visit jobs in numerical order to simulate this schedule deterministically; they do not overlap execution.
5. Finish the barrier and publish. Record the source, destination, intervals, jobs, and level counters. Only after the whole level is complete replace the source with the destination. Never let a next-level job read a partially filled array.
6. Repeat until one value remains. Return that value, total combines, total carries, levels, and the sum of modeled rounds. No next-power-of-two padding is needed.

For [3,1,7,0,4], the first level has three jobs. Workers 0 and 1 compute 4 and 7 in wave 0; worker 0 carries the final 4 in wave 1. The resulting [4,7,4] becomes visible after the barrier. A carry is data that still matters, not an idle worker or a zero-valued placeholder.

A separate destination also makes the parallel data ownership easy to prove. A carefully ordered sequential implementation could compact in place, but naive concurrent compaction can overwrite values another job still needs. For example, one job writing destination slot 1 may race with another reading source slot 1. Use distinct source/destination buffers in this scheme.

flowchart TD
    A["Validate input and worker count"] --> B{"Zero or one value?"}
    B -->|Yes| C["Return identity or sole value"]
    B -->|No| D["Allocate next array and pair jobs"]
    D --> E{"Does job have a right neighbor?"}
    E -->|Yes| F["Combine left then right; join intervals"]
    E -->|No| G["Carry left value and interval unchanged"]
    F --> H{"More jobs in this level?"}
    G --> H
    H -->|Yes| E
    H -->|No| I["Barrier; record and publish next array"]
    I --> B

Worked Example with a Full Trace

Use values=[3,1,7,0,4], addition with identity 0, and processors=2. The sequential check is $3+1+7+0+4=15$. Initially the five entries represent $[0,1)$, $[1,2)$, $[2,3)$, $[3,4)$, and $[4,5)$. Worker and wave numbers start at zero. Source indices below refer to the current level, while intervals always refer to the original input.

Level 1: five entries become three. Job 0 on worker 0, wave 0, combines source slots 0 and 1: $3+1=4$, interval $[0,2)$. Job 1 on worker 1, wave 0, combines slots 2 and 3: $7+0=7$, interval $[2,4)$. Job 2 on worker 0, wave 1, carries slot 4: value 4, interval $[4,5)$. After the barrier the destination is [4,7,4]. Cost: two combines, one carry, two modeled rounds.

Level 2: three entries become two. Job 0 on worker 0, wave 0, computes $4+7=11$ over $[0,4)$. Job 1 on worker 1, wave 0, carries the remaining 4 over $[4,5)$. After the barrier the destination is [11,4]. Cost: one combine, one carry, one round.

Level 3: two entries become one. Job 0 on worker 0, wave 0, computes $11+4=15$ over $[0,5)$. Worker 1 is idle. After the barrier [15] is final. Cost: one combine, no carry, one round.

The full parenthesization is $((3+1)+(7+0))+4$. There are $2+1+1=4=n-1$ combines and two carries, for six executed jobs. Three dependency levels become four rounds on two workers because the first level has three jobs. The model's six-job count and four-combine count answer different questions.

Three useful boundary traces are [] → 0, [9] → 9, and [9,-2] → [7]. The first two have no levels, combines, carries, or modeled rounds. Negative numbers, zeros, and duplicates do not change the reduction structure; odd length does.

Implementation in Python, C++, and Java

The three standalone programs use identical adjacent-pair logic, carry handling, intervals, scheduling, validation order, and output. Python needs 3.9 or later; C++ uses C++17; Java uses ordinary classes and runs on Java 8 or later. Save the Java program as Main.java. Run Python with python3 main.py; compile C++ with g++ -std=c++17 -O2 main.cpp -o reduction and run ./reduction; compile Java with javac Main.java and run java Main. Each panel contains its own full program and sample input.

The sum wrapper is sum_reduce in Python/C++ and sumReduce in Java. It reports PROCESSORS, then SIZE, then VALUE on a violated precondition. Python explicitly rejects booleans, floats, and strings as numeric inputs or worker counts. C++ and Java enforce numeric types through the function signatures; Java additionally rejects null numeric elements. The API expects a non-null flat input container. Invalid inputs raise exceptions; the valid sample completes normally. Input containers are left unchanged.

Python integers, C++ long long, and Java long all represent every intermediate sum under these bounds: any subtotal has magnitude at most $256\cdot10^6=256000000$. The generic core is reduce_core or reduceCore and can instead receive the empty string plus concatenation. Its values must be immutable, its combine must have no side effects, and its identity must match the operation. Formatting helpers display integers and simple string tests; they are teaching output, not a general serialization format.

A Job records source positions, worker, and wave; its destination is the job's index. A Level records both arrays, resulting interval starts/stops, jobs, rounds, combines, and carries. A Result records the aggregate and all levels. A right source of -1 means a carry, never an array index to dereference. No operation combines a carried value with itself or with an artificial zero.

Timing model: each pair job and each carry job costs one unit, workers execute one job per wave, and levels have a barrier. Allocation, interval bookkeeping, validation, history copying, printing, memory traffic, and barrier overhead are excluded from model_rounds. The actual host program executes sequentially; its printed schedule is not a benchmark or measured speedup.

Verification: all three implementations passed 6,123 identical test inputs: 4,830 integer cases and 1,293 concatenation cases, including eight rejected inputs. Tests compare each level against independently folded original input intervals, every job's sources and worker/wave, exact combine-call totals, all counters, and input preservation. They include exhaustive small cases, every length from 0 through 256 at several worker counts, boundary magnitudes, and random cases with a fixed seed. Eight additional Python checks reject invalid runtime types. C++ passed with address/undefined-behavior sanitizers; Java compiled with all lint warnings enabled. All three sample outputs match byte for byte.

from dataclasses import dataclass
from typing import Callable, Generic, TypeVar

T = TypeVar("T")

@dataclass
class Job:
    left: int
    right: int  # -1 means carry the unmatched left value
    worker: int
    wave: int

@dataclass
class Level(Generic[T]):
    before: list[T]
    after: list[T]
    starts: list[int]
    stops: list[int]
    jobs: list[Job]
    rounds: int
    combines: int
    carries: int

@dataclass
class Result(Generic[T]):
    value: T
    levels: list[Level[T]]
    combines: int
    carries: int
    rounds: int

def reduce_core(values: list[T], identity: T,
                combine: Callable[[T, T], T], processors: int) -> Result[T]:
    if type(processors) is not int or not 1 <= processors <= 64:
        raise ValueError("PROCESSORS")
    if len(values) > 256:
        raise ValueError("SIZE")
    current = list(values)
    starts = list(range(len(values)))
    stops = [i + 1 for i in range(len(values))]
    levels: list[Level[T]] = []
    total_combines = total_carries = total_rounds = 0
    while len(current) > 1:
        before = current
        after: list[T] = []
        next_starts: list[int] = []
        next_stops: list[int] = []
        jobs: list[Job] = []
        combines = carries = 0
        for j in range((len(before) + 1) // 2):
            left = 2 * j
            right = left + 1 if left + 1 < len(before) else -1
            if right != -1:
                value = combine(before[left], before[right])
                stop = stops[right]
                combines += 1
            else:
                value = before[left]
                stop = stops[left]
                carries += 1
            after.append(value)
            next_starts.append(starts[left])
            next_stops.append(stop)
            jobs.append(Job(left, right, j % processors, j // processors))
        rounds = (len(jobs) + processors - 1) // processors
        levels.append(Level(list(before), list(after), next_starts,
                            next_stops, jobs, rounds, combines, carries))
        total_combines += combines
        total_carries += carries
        total_rounds += rounds
        # A level barrier precedes publishing the new source array.
        current, starts, stops = after, next_starts, next_stops
    return Result(current[0] if current else identity, levels,
                  total_combines, total_carries, total_rounds)

def sum_reduce(values: list[int], processors: int) -> Result[int]:
    if type(processors) is not int or not 1 <= processors <= 64:
        raise ValueError("PROCESSORS")
    if len(values) > 256:
        raise ValueError("SIZE")
    if any(type(x) is not int or not -1_000_000 <= x <= 1_000_000
           for x in values):
        raise ValueError("VALUE")
    return reduce_core(values, 0, lambda a, b: a + b, processors)

def show(value: object) -> str:
    return '""' if value == "" else str(value)

def array_text(values: list[T]) -> str:
    return "[" + ",".join(show(x) for x in values) + "]"

def format_result(result: Result[T]) -> str:
    lines: list[str] = []
    for number, level in enumerate(result.levels, 1):
        lines.append(f"level={number} before={array_text(level.before)}")
        for j, job in enumerate(level.jobs):
            sources = str(job.left)
            if job.right != -1:
                sources += "," + str(job.right)
            lines.append(
                f"  job={j} worker={job.worker} wave={job.wave} "
                f"sources={sources} range=[{level.starts[j]},{level.stops[j]}) "
                f"value={show(level.after[j])}")
        lines.append(f"  after={array_text(level.after)} rounds={level.rounds} "
                     f"combines={level.combines} carries={level.carries}")
    lines.append(f"result={show(result.value)} levels={len(result.levels)} "
                 f"combines={result.combines} carries={result.carries} "
                 f"model_rounds={result.rounds}")
    return "\n".join(lines)

if __name__ == "__main__":
    values = [3, 1, 7, 0, 4]
    processors = 2
    print(f"input={array_text(values)} processors={processors}")
    print(format_result(sum_reduce(values, processors)))

#include <functional>
#include <iostream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>

struct Job {
    int left, right, worker, wave;
};

template<class T> struct Level {
    std::vector<T> before, after;
    std::vector<int> starts, stops;
    std::vector<Job> jobs;
    int rounds, combines, carries;
};

template<class T> struct Result {
    T value;
    std::vector<Level<T>> levels;
    int combines = 0, carries = 0, rounds = 0;
};

template<class T, class Combine>
Result<T> reduce_core(const std::vector<T>& values, T identity,
                      Combine combine, int processors) {
    if (processors < 1 || processors > 64)
        throw std::invalid_argument("PROCESSORS");
    if (values.size() > 256)
        throw std::invalid_argument("SIZE");
    std::vector<T> current = values;
    std::vector<int> starts, stops;
    for (int i = 0; i < static_cast<int>(values.size()); ++i) {
        starts.push_back(i);
        stops.push_back(i + 1);
    }
    Result<T> result{identity, {}, 0, 0, 0};
    while (current.size() > 1) {
        Level<T> level;
        level.before = current;
        level.combines = level.carries = 0;
        int count = static_cast<int>(current.size());
        for (int j = 0; j < (count + 1) / 2; ++j) {
            int left = 2 * j;
            int right = left + 1 < count ? left + 1 : -1;
            if (right != -1) {
                level.after.push_back(combine(current[left], current[right]));
                level.stops.push_back(stops[right]);
                ++level.combines;
            } else {
                level.after.push_back(current[left]);
                level.stops.push_back(stops[left]);
                ++level.carries;
            }
            level.starts.push_back(starts[left]);
            level.jobs.push_back(Job{left, right, j % processors, j / processors});
        }
        level.rounds = (static_cast<int>(level.jobs.size()) + processors - 1)
                       / processors;
        result.combines += level.combines;
        result.carries += level.carries;
        result.rounds += level.rounds;
        // A level barrier precedes publishing the new source array.
        current = level.after;
        starts = level.starts;
        stops = level.stops;
        result.levels.push_back(level);
    }
    if (!current.empty()) result.value = current[0];
    return result;
}

Result<long long> sum_reduce(const std::vector<long long>& values, int processors) {
    if (processors < 1 || processors > 64)
        throw std::invalid_argument("PROCESSORS");
    if (values.size() > 256)
        throw std::invalid_argument("SIZE");
    for (long long value : values) {
        if (value < -1000000 || value > 1000000)
            throw std::invalid_argument("VALUE");
    }
    return reduce_core(values, 0LL, std::plus<long long>{}, processors);
}

std::string show(long long value) { return std::to_string(value); }
std::string show(const std::string& value) { return value.empty() ? "\"\"" : value; }

template<class T> std::string array_text(const std::vector<T>& values) {
    std::ostringstream out;
    out << '[';
    for (std::size_t i = 0; i < values.size(); ++i) {
        if (i) out << ',';
        out << show(values[i]);
    }
    out << ']';
    return out.str();
}

template<class T> std::string format_result(const Result<T>& result) {
    std::ostringstream out;
    for (std::size_t k = 0; k < result.levels.size(); ++k) {
        const auto& level = result.levels[k];
        out << "level=" << k + 1 << " before=" << array_text(level.before) << '\n';
        for (std::size_t j = 0; j < level.jobs.size(); ++j) {
            const auto& job = level.jobs[j];
            out << "  job=" << j << " worker=" << job.worker << " wave=" << job.wave
                << " sources=" << job.left;
            if (job.right != -1) out << ',' << job.right;
            out << " range=[" << level.starts[j] << ',' << level.stops[j]
                << ") value=" << show(level.after[j]) << '\n';
        }
        out << "  after=" << array_text(level.after) << " rounds=" << level.rounds
            << " combines=" << level.combines << " carries=" << level.carries << '\n';
    }
    out << "result=" << show(result.value) << " levels=" << result.levels.size()
        << " combines=" << result.combines << " carries=" << result.carries
        << " model_rounds=" << result.rounds;
    return out.str();
}

int main() {
    std::vector<long long> values{3, 1, 7, 0, 4};
    int processors = 2;
    std::cout << "input=" << array_text(values) << " processors=" << processors << '\n';
    std::cout << format_result(sum_reduce(values, processors)) << '\n';
    return 0;
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.BinaryOperator;

public class Main {
    static final class Job {
        final int left, right, worker, wave;
        Job(int left, int right, int worker, int wave) {
            this.left = left;
            this.right = right;
            this.worker = worker;
            this.wave = wave;
        }
    }
    static final class Level<T> {
        List<T> before = new ArrayList<>(), after = new ArrayList<>();
        List<Integer> starts = new ArrayList<>(), stops = new ArrayList<>();
        List<Job> jobs = new ArrayList<>();
        int rounds, combines, carries;
    }
    static final class Result<T> {
        T value;
        List<Level<T>> levels = new ArrayList<>();
        int combines, carries, rounds;
        Result(T identity) { value = identity; }
    }

    static <T> Result<T> reduceCore(List<T> values, T identity,
                                     BinaryOperator<T> combine, int processors) {
        if (processors < 1 || processors > 64)
            throw new IllegalArgumentException("PROCESSORS");
        if (values.size() > 256)
            throw new IllegalArgumentException("SIZE");
        List<T> current = new ArrayList<>(values);
        List<Integer> starts = new ArrayList<>(), stops = new ArrayList<>();
        for (int i = 0; i < values.size(); ++i) {
            starts.add(i);
            stops.add(i + 1);
        }
        Result<T> result = new Result<>(identity);
        while (current.size() > 1) {
            Level<T> level = new Level<>();
            level.before = new ArrayList<>(current);
            for (int j = 0; j < (current.size() + 1) / 2; ++j) {
                int left = 2 * j;
                int right = left + 1 < current.size() ? left + 1 : -1;
                if (right != -1) {
                    level.after.add(combine.apply(current.get(left), current.get(right)));
                    level.stops.add(stops.get(right));
                    ++level.combines;
                } else {
                    level.after.add(current.get(left));
                    level.stops.add(stops.get(left));
                    ++level.carries;
                }
                level.starts.add(starts.get(left));
                level.jobs.add(new Job(left, right, j % processors, j / processors));
            }
            level.rounds = (level.jobs.size() + processors - 1) / processors;
            result.combines += level.combines;
            result.carries += level.carries;
            result.rounds += level.rounds;
            // A level barrier precedes publishing the new source array.
            current = level.after;
            starts = level.starts;
            stops = level.stops;
            result.levels.add(level);
        }
        if (!current.isEmpty()) result.value = current.get(0);
        return result;
    }

    static Result<Long> sumReduce(List<Long> values, int processors) {
        if (processors < 1 || processors > 64)
            throw new IllegalArgumentException("PROCESSORS");
        if (values.size() > 256)
            throw new IllegalArgumentException("SIZE");
        for (Long value : values) {
            if (value == null || value < -1000000L || value > 1000000L)
                throw new IllegalArgumentException("VALUE");
        }
        return reduceCore(values, 0L, Long::sum, processors);
    }

    static String show(Object value) {
        return "".equals(value) ? "\"\"" : String.valueOf(value);
    }
    static <T> String arrayText(List<T> values) {
        StringBuilder out = new StringBuilder("[");
        for (int i = 0; i < values.size(); ++i) {
            if (i != 0) out.append(',');
            out.append(show(values.get(i)));
        }
        return out.append(']').toString();
    }
    static <T> String formatResult(Result<T> result) {
        StringBuilder out = new StringBuilder();
        for (int k = 0; k < result.levels.size(); ++k) {
            Level<T> level = result.levels.get(k);
            out.append("level=").append(k + 1).append(" before=")
               .append(arrayText(level.before)).append('\n');
            for (int j = 0; j < level.jobs.size(); ++j) {
                Job job = level.jobs.get(j);
                out.append("  job=").append(j).append(" worker=").append(job.worker)
                   .append(" wave=").append(job.wave).append(" sources=").append(job.left);
                if (job.right != -1) out.append(',').append(job.right);
                out.append(" range=[").append(level.starts.get(j)).append(',')
                   .append(level.stops.get(j)).append(") value=")
                   .append(show(level.after.get(j))).append('\n');
            }
            out.append("  after=").append(arrayText(level.after))
               .append(" rounds=").append(level.rounds).append(" combines=")
               .append(level.combines).append(" carries=").append(level.carries).append('\n');
        }
        return out.append("result=").append(show(result.value)).append(" levels=")
                  .append(result.levels.size()).append(" combines=").append(result.combines)
                  .append(" carries=").append(result.carries).append(" model_rounds=")
                  .append(result.rounds).toString();
    }

    public static void main(String[] args) {
        List<Long> values = Arrays.asList(3L, 1L, 7L, 0L, 4L);
        int processors = 2;
        System.out.println("input=" + arrayText(values) + " processors=" + processors);
        System.out.println(formatResult(sumReduce(values, processors)));
    }
}

Identical expected output (each item is one printed line; range=[start,stop) uses original input indices):

• input=[3,1,7,0,4] processors=2
• level=1 before=[3,1,7,0,4]
• job=0 worker=0 wave=0 sources=0,1 range=[0,2) value=4
• job=1 worker=1 wave=0 sources=2,3 range=[2,4) value=7
• job=2 worker=0 wave=1 sources=4 range=[4,5) value=4
• after=[4,7,4] rounds=2 combines=2 carries=1
• level=2 before=[4,7,4]
• job=0 worker=0 wave=0 sources=0,1 range=[0,4) value=11
• job=1 worker=1 wave=0 sources=2 range=[4,5) value=4
• after=[11,4] rounds=1 combines=1 carries=1
• level=3 before=[11,4]
• job=0 worker=0 wave=0 sources=0,1 range=[0,5) value=15
• after=[15] rounds=1 combines=1 carries=0
• result=15 levels=3 combines=4 carries=2 model_rounds=4

Complexity, Correctness, and Invariants

Assume each combine, copied value, and interval/job record has constant cost and size. This holds for our bounded integer sums. Let $n\ge1$, $k=\lceil\log_2 n\rceil$, and let the current array length after level $r$ be

$$q_r=\left\lceil\frac{n}{2^r}\right\rceil,\qquad q_0=n,\qquad q_k=1.$$

This follows from repeatedly replacing $q$ by $\lceil q/2\rceil$. At level $r\in\{1,\ldots,k\}$, there are $q_r$ jobs: $c_r=\lfloor q_{r-1}/2\rfloor$ combines and $h_r=q_{r-1}\bmod2$ carries. Since $c_r=q_{r-1}-q_r$, the combine counts telescope:

$$C=\sum_{r=1}^{k}c_r=n-1.$$

Define $H=\sum_{r=1}^{k}h_r$ and $J=\sum_{r=1}^{k}q_r$. Then $J=C+H=n-1+H$, where $0\le H\le k$. Carries do not inflate the binary operation count; they do add jobs. For powers of two, $H=0$ and $J=n-1$. For five entries, $q_1,q_2,q_3$ are 3, 2, and 1, so $C=4$, $H=2$, and $J=6$.

Work, span, and time. Reduction work is $\Theta(n)$ for $n\ge2$, including carry jobs. The job DAG has span $D=k=\Theta(\log n)$ because each level costs one unit with enough workers, and some input passes through all levels. A binary operation with fan-in two cannot combine information from more than $2^d$ leaves in depth $d$, so a general reduction needs depth at least $\lceil\log_2 n\rceil$ in this model. Likewise, connecting n inputs with binary combines requires at least $n-1$ combine nodes. This tree achieves both bounds for the reduction itself; it does not erase input setup or communication costs.

For our exact level-by-level worker assignment, the modeled time is

$$R_P=\sum_{r=1}^{k}\left\lceil\frac{q_r}{P}\right\rceil.$$

Thus $R_1=J$. If $P\ge\lceil n/2\rceil$, each level takes one round and $R_P=k$. For $n\ge2$, $R_P\ge\max(J/P,k)$ and $R_P\lt J/P+k$, giving

$$R_P=\Theta\!\left(\frac{n}{P}+\log n\right).$$

These are exact counts and asymptotic bounds for the stated unit-job model. A different ready-job schedule can pipeline subtrees instead of imposing full-level barriers; this formula belongs to the shown schedule. Do not blindly substitute $n-1$ for $J$ in its one-worker baseline when carries are present. For the worked input, $R_1=6$, $R_2=4$, and $R_3=3$. Against the same job schedule, modeled speedup at two workers is $6/4=1.5$; against an optimized four-combine sequential sum, the reduction-phase ratio is $4/4=1$. Neither is a wall-clock measurement.

Best, average, worst. For a fixed n and P, the number of jobs and rounds is identical for every supported input value; all three cases have the same bounds. There is no early exit for zero, all-equal values, or a decisive Boolean result. Empty input returns identity in constant algorithmic work with zero modeled jobs. A singleton similarly returns its value without a level. With API validation and copying, actual host work is $\Theta(n+1)$; its sequential duration is not logarithmic.

Space, including the full trace. Source/destination buffers and interval arrays need $O(n)$ extra space. The retained arrays and job records across all levels also total $O(n)$ because their lengths shrink geometrically: $\sum_{r=0}^{k}q_r\lt2n+k$, and $k=O(n)$ for positive n. Thus this particular complete trace remains linear space and work in fixed-size records, unlike tracing n-length arrays at every level of a scan. Printing index digits can add an $O(\log n)$ factor in bit/character accounting; the table uses a word-RAM model. Omitting history lowers constants while keeping $O(n)$ buffer space; a single-thread sequential fold can use $O(1)$ extra space.

Correctness by intervals. Initially each entry is its own original singleton and is trivially the reduction of that interval. Assume the current intervals are adjacent, disjoint, in increasing order, cover $[0,n)$, and each stored value is the ordered reduction of its interval. A pair merges neighboring intervals $[\ell,m)$ and $[m,r)$; by associativity, their left-then-right combine is the reduction of $[\ell,r)$. A carry preserves its interval and value. Therefore the new intervals again partition the entire input in order, with correct values. Disjoint destinations and stable sources make concurrent jobs independent; the barrier establishes this invariant for the next level. When one interval remains it must be $[0,n)$ and its value is the required reduction. Empty input follows the identity convention separately.

Variants, Pitfalls, and Optimizations

Keep the odd tail. A loop over only $\lfloor q/2\rfloor$ complete pairs loses one entry whenever q is odd. For the worked input it returns 11 instead of 15 because the final 4 disappears. Correct code allocates $\lceil q/2\rceil$ destinations and treats the final unmatched value as a carry. Conversely, combining that tail with itself duplicates data. Padding is another valid design, but it needs the operation's real identity; padding maximum with zero fails for [-5,-2], whose maximum is -2.

Preserve order, not just membership. Stride-halving implementations often combine distant positions. They are fine for commutative sum but may reorder inputs. For four strings, first pairing indices 0 with 2 and 1 with 3 returns "acbd" instead of "abcd". Associativity permits regrouping, not arbitrary permutations. Use adjacent ordered intervals or explicitly require commutativity. Out-of-order worker completion must not change output order: write each result into its predetermined destination slot.

Do not parallelize an invalid operation. Subtraction is not associative: $((10-3)-2)-1=4$, while $(10-3)-(2-1)=6$. A tree changes its meaning. Division and rounding-sensitive user functions have similar issues. Some tasks can be reformulated with associative summaries instead: compute a mean by reducing pairs $(s,c)$ with $(s_1,c_1)\oplus(s_2,c_2)=(s_1+s_2,c_1+c_2)$, then divide once as $s/c$ when $c\gt0$. Do not average averages without weighting; averages 1 from one item and 3 from three items combine to 2.5, not 2.

Floating-point addition needs a numerical policy. Finite-precision addition is not mathematically associative: a fixed tree can produce a different answer from a sequential fold. In binary64 arithmetic, the left fold of [1e16,1,-1e16,1] yields 1, while this adjacent-pair tree yields 0; exact arithmetic gives 2. A fixed tree can improve reproducibility under fixed arithmetic and execution settings, but changing partitioning, precision, compiler transformations, or hardware can change results. Pairwise summation often improves error behavior over a long chain, yet it does not guarantee exactness; use appropriate error analysis, compensated methods, or exact accumulators when required. For C++, signed overflow is undefined; Java long arithmetic wraps. The numeric teaching bounds avoid both overflow outcomes for sums.

Use local chunks before global levels. Production implementations often assign each worker a contiguous block, reduce that block locally, then reduce the ordered block summaries. For $Q=\min(P,n)$ nonempty blocks, local folds take $O(\lceil n/Q\rceil)$ time and the summary tree takes $O(\log Q)$ under ideal workers. Keep block order for noncommutative operators. Very small arrays usually favor a sequential fold because setup and barriers outweigh any parallel benefit.

Match synchronization to memory scope. A GPU block-local barrier only coordinates that block; a reduction spanning multiple blocks needs an appropriate global coordination strategy, such as staged kernels. Warp-level primitives and local memory can reduce overhead, but their participant masks and memory rules must be respected. These details are platform-specific and absent from our simulator. Reduce barrier frequency or reuse alternating buffers only after keeping the source-read/destination-write contract clear.

Distinguish related operations. A scan returns all prefixes; a segmented reduction returns one total per segment; a group-by reduction aggregates by key, requiring grouping or appropriate ownership. A distributed reduce delivers the aggregate to a chosen destination; all-reduce makes the aggregate available to every participant and adds a communication/distribution phase. Network latency, data size, failures, and device topology change the cost model; our local unit-job rounds do not predict these costs.

Account for combine cost. Concatenation is associative and excellent for order tests, but copying variable-length strings is not constant cost. On a balanced tree, repeated copying can cost $O(L\log n)$ characters for total input text length L, even though there are only $n-1$ binary calls. Large histograms, matrices, and sketches likewise need costs proportional to their representation. Use ropes, references, fixed-size summaries, or suitable batching when appropriate; keep the algebra and the cost model separate.

Practice Problems and Real-World Use

Start with a sequential reference answer, then test the structure that makes parallel execution safe. At every finished level, fold each recorded original input interval independently and compare it with its stored subtotal. Verify that intervals join end to start, begin at zero, and end at n. The final answer alone may miss a bug that cancels accidentally on one input.

For numeric tests include empty and singleton inputs, all zeros, all negative values, duplicates, opposite-sign cancellation, odd lengths, and lengths just below/at/above powers of two. Check $C=\max(0,n-1)$, count carry jobs separately, and compare modeled rounds against the level-width formula. Vary P while keeping input and tree fixed; values and intervals must remain unchanged even when workers or waves change. For order tests use distinct string tokens and check concatenation against the original sequence. If a production system permits nondeterministic ordering, test only operations with the additional properties that system requires.

Try these extensions in order: replace sum with maximum using a valid identity; add multiplication with checked bounds; return a fixed-size summary containing count, sum, minimum and maximum; add contiguous local blocks; and finally implement actual workers with disjoint destination writes and a real barrier. Retain the sequential oracle while making the last change. Benchmark sufficiently large inputs, record setup and synchronization costs, and report the sequential baseline, worker count, input sizes, arithmetic policy, and measured speedup. Keep modeled rounds in a separate column from elapsed time.

The problems below connect the same reduction invariant to practical uses. Avoid forcing all-prefix outputs, changing group membership, or communication costs into the single-total local model. A well-chosen summary lets the algebra survive even when the execution environment changes.

Further reading: Carnegie Mellon's reduction specification gives the associative/identity contract and work/span assumptions. NVIDIA's reduction implementation discussion illustrates device-level techniques and synchronization choices; it is a hardware-specific historical implementation discussion. The exact trace, tests, interval proof, and round formula above describe this lesson's own adjacent-pair carry algorithm.