Skip to main content

Parallel work: partition, reduce and measure

This required clinic adds 18–26 focused hours: prerequisite repair and reasoning 4–6; native implementation and failure checks 6–8; measurement 4–6; independent defense and delayed transfer 4–6. Concurrency becomes 98–141 hours, and Semester 05 becomes 468–676. These are author estimates awaiting pilots. Queue-close and CQ1–CQ6 remain required; a throughput experiment does not replace lifecycle correctness.

Entry bridge and overlap​

Bring Semester 04's C buffer bounds, pthread create/join, ownership and locality measurement work, and this semester's scheduling, memory and queue predicates. Before coding, explain why a thread argument pointing into a returned stack frame is invalid, when a joined worker's result may be read, and why four runnable threads need not execute on four cores. Repair only missing prerequisites within the 4–6-hour reasoning allocation; larger repairs add time.

Existing Amdahl examples, cache labs and queue-close exercises are retained. This clinic adds work/span reasoning, a native partitioned reduction and failure-aware measurement. It does not require a GPU, cloud account, new language or full parallel-computing textbook.

Lesson 1: partitioning is a correctness argument​

For n items and p positive workers, assign worker t the half-open interval [floor(n*t/p), floor(n*(t+1)/p)), for t from 0 to p-1. The first boundary is zero, adjacent intervals share exactly their boundary, and the last endpoint is n. Thus every item belongs to exactly one interval, even when n is not divisible by p. If p exceeds n, empty intervals are valid. A loop ending at <= hi instead duplicates a boundary or reads outside the array.

For n=10 and p=3, the intervals are [0,3), [3,6), [6,10). The tempting interval [t*(n/p),(t+1)*(n/p)) omits the final item. Derive the boundaries before running a test. The reference bounds n and p so their products fit size_t on supported POSIX hosts; general libraries must guard intermediate multiplication or use a quotient/remainder construction.

The input is immutable while workers run. Each worker computes a local histogram and publishes it in its own job record. The parent sums results only after successful joins. Each final bin equals the sum of contributions from disjoint intervals; this composes the partition proof with the sequential counting invariant. Summing all bins to n is necessary but insufficient: swapping two bins preserves that total while returning the wrong histogram.

An unsynchronized shared bins[value]++ is a read-modify-write conflict in C. A plausible output does not make its data race defined behavior. Per-worker counters avoid that shared mutation. They do not automatically eliminate false sharing: separate objects can share cache lines. The reference writes local counters back once and makes no claim to measure cache-line contention. A separate controlled experiment would be needed to support that claim.

Exercise: draw n=2,p=5 and n=0,p=3; prove coverage and disjointness. Then change input to all one value and to a skewed distribution. Explain why correctness is unaffected but a shared-lock implementation's contention might change.

Lesson 2: work, span and actual execution differ​

Represent dependencies as a directed acyclic graph. Work W counts all operations; span S counts the longest dependency chain under a specified unit-cost model. Any execution on p processors needs at least W/p time and at least S time in that idealized model. W/S bounds available parallelism; neither lower bound promises a real machine's runtime. Memory traffic, startup, scheduling and synchronization add costs outside a simple operation graph.

For a binary tree sum of n inputs, there are n-1 additions and logarithmic span when independent nodes at each level may run together. For the supplied histogram, counting uses linear work, but worker creation and the final merge are serial. With B bins and p workers, an approximate critical path includes p startup operations, the largest partition scan, and p*B merging operations. Do not claim logarithmic span just because the word “reduction” appears: this implementation merges sequentially.

If W=120 and S=30, four processors have a lower bound of 30 model time units; sixteen still have a bound of 30. A real runtime of 60 does not contradict that bound. Nor does W/S=4 guarantee fourfold speedup against a different optimized sequential algorithm. Work inflation can erase the value of a shorter dependency chain.

Amdahl's law complements this view under a fixed workload and fixed serial fraction. Scaling the input with worker count asks a different question from strong scaling at fixed n. State which question your graph answers. More threads can increase overhead, exceed available CPU quota or saturate memory bandwidth. Observing a plateau suggests hypotheses, not proof of one bottleneck.

Exercise: compare serial versus tree merging of p partial histograms. State work, span, storage and synchronization changes; then explain why building a tree may lose for just 16 bins and a few workers. A drawing and cost model suffice; implementing a second scheduler is optional depth.

Lesson 3: failure and measurement contracts​

A thread may begin immediately after successful creation. Its argument and input must already exist and remain valid until completion. If creation fails after two successful starts, join those two before freeing their data. Do not merge uninitialized results or print a successful partial histogram. The reference injects this failure deterministically; it does not exhaust the machine's resources to provoke it.

A successful join establishes completion before the parent consumes the corresponding result. If an unexpected join error prevents establishing completion, this small executable exits without freeing potentially live worker data. A reusable library needs a stronger ownership and recovery design. Distinguish this bounded executable contract from production lifecycle management.

Measure a defined boundary. The reference timer includes job setup, thread creation, counting, joins and serial merge; it excludes allocation, input generation, startup and printing. Its one-worker version still creates a thread. Compare both that scaling baseline and a direct sequential implementation using the same timer boundary and output contract. Otherwise “speedup” may measure a change of benchmark rather than parallel execution.

Do not require a speedup to pass. Record compiler and flags, OS, CPU topology/quota, n, p, data distribution and background-load limitations. Retain every run. Alternate or randomize configurations, use a warm-up, then at least seven repetitions per configuration. Report median and range; do not turn seven observations into an unsupported universal confidence claim. Correctness checks precede timing. Check integer overflow assumptions and explain why floating-point reductions would require a different equivalence contract.

Native laboratory and learner work​

Download parallel-histogram.zip, read its README and compile with a POSIX C compiler and pthreads. Python is used by the repository verifier to orchestrate native executions, not to simulate threads. No package installation or network is required. A platform without this toolchain must record native execution pending; reading output is not equivalent evidence.

Before inspecting reference implementation, predict counts for n=0,1,17 with p=1,3,32. Implement your own direct sequential and partitioned histogram. Use an independent bin-by-bin oracle for small inputs, then deliberately test omitted remainders, duplicated boundaries, empty intervals and malformed arguments. Inject a creation failure at every index in a four-worker run. Preserve failed attempts and corrected reasoning.

Measure small, medium and large inputs within the memory guard (for example 100, 100000 and 5000000), using 1,2,4 workers and an optional oversubscribed configuration. Compare the direct sequential scan, one-worker threaded path and multiple-worker path. Keep output checking outside the timed region in every implementation. A single-core environment can complete correctness work and report its scaling limitations honestly.

Then change from the uniform generator to all-one-bin and skewed inputs. Write a load-balance hypothesis before timing: equal element counts balance this constant-cost operation, but would not necessarily balance variable-cost per-item transformations. Retain a reproducible script, raw observations, a short explanation and one unresolved hypothesis. No screenshots or invented performance numbers substitute for raw runs.

Independent assessment and calibration​

Score each PC1–PC4 using 0 missing/invalid, 1 assisted/incomplete, 2 independently correct with inspectable evidence, 3 also adapts to a fresh case and defends limits. Every gate requires 2, alongside CQ1–CQ6 and the existing security, exam and checkpoint requirements.

  • PC1: partition and result proof. Coverage, disjointness, empty ranges, per-bin oracle and overflow bounds. Calibration: floor boundaries telescope from 0 to n; checking just the total cannot catch bin swaps. Fresh case: n=11,p=4.
  • PC2: ownership and failure. Native build/run, worker argument lifetime, read-only input, join-before-consumption and injected partial-start cleanup. Calibration: join only successfully created workers; publish no success result after creation failure. A model-only run or a race that “usually works” is incomplete.
  • PC3: cost and measurement. Work/span model, serial-merge limitation, both baselines, retained repetitions and honest timing boundary. Calibration: the reference merge has p*B additions, not logarithmic span; no speedup is required. Explain why an ideal lower bound cannot predict a particular elapsed time.
  • PC4: changed workload and transfer. Skewed-input experiment plus a fresh review of a proposed shared-counter implementation. Calibration: shared non-atomic increment is a data race; adding a lock repairs mutual exclusion but may introduce contention. A noisy plateau alone does not prove bandwidth saturation.

Keep assistance and reviewer status explicit. After 7–14 days repeat one partition case and one failure/measurement explanation without notes; use the existing delayed-review visit where possible, with active work counted in this clinic. Repair only failed dimensions, then use fresh evidence. Independent reviewer agreement and learner duration remain unvalidated.

Selective resources​

Use CMU's Work and Depth explanation to reinforce the two cost measures and CMU parallel algorithm notes for selected work/span analysis. Return to the concrete cost derivation rather than reading an entire course first.

Use pthread_create and pthread_join for native API contracts; inspect your platform's own manual for portability. Existing OSTEP concurrency chapters remain the book backbone. These sources were located on 2026-10-23. No book purchase or full transcription is required. GPU kernels, NUMA tuning and lock-free algorithms are later depth, not covered claims of this clinic.