Global dependencies and barriers

A result can depend on the whole dataset without requiring the whole image in one buffer. The important question is what information must cross block boundaries. A histogram can be reduced to a fixed number of bins; connected components can require an equivalence relation growing with the segmentation; a globally ordered watershed can require a different execution shape entirely.

Three dependency shapes

A local filter needs bounded source pixels and is expressed by ordinary reach. A complete-axis operation needs all positions along selected axes and can use AxisReach::All, while remaining cut into strips in transverse directions. A global reduction needs every declared partial contribution before any consumer uses the combined state, even when its local pixel read is tiny.

The last case is a synchronization dependency, not a large pixel halo. Treating the two as the same would make every block read the whole image merely to wait for the other blocks’ histogram contributions.

flowchart TB
  A["Image block A"] --> HA["Histogram fragment A"]
  B["Image block B"] --> HB["Histogram fragment B"]
  C["Image block C"] --> HC["Histogram fragment C"]
  HA --> R["Barrier: reduce complete histogram"]
  HB --> R
  HC --> R
  R --> T["Shared threshold"]
  T --> AA["Apply to block A"]
  T --> AB["Apply to block B"]
  T --> AC["Apply to block C"]
Figure 1: The reduction waits for complete partials. Pixel reads for the later application can remain block-local.

A concrete histogram pipeline

In the first phase, each block reads its owned pixels and emits a histogram fragment. A fixed bin count makes each contribution small and mergeable. The consumer declares the producing stream through FragmentInput; the producer uses FragmentOutput and Coverage to say which blocks must contribute.

An empty or all-invalid block still needs the declared empty contribution when the coverage contract requires one. Missing data and an empty histogram have different meanings. Treating an unwritten fragment as an empty one could produce a plausible threshold from an incomplete dataset.

The consumer implements FragmentOp::barrier and FragmentOp::reduce. The barrier is recorded in PhaseDecomposition and TaskGraph. The executor waits until every earlier phase has completed, invokes the reduction once, and makes its bytes available through BlockView::reduced before applying the consumer to any block.

For a histogram threshold, those bytes can hold the chosen scalar threshold and any calibration needed to interpret it. Each subsequent block then reads only its own pixels and compares them to that common value. The application work remains parallel after the phase-start gate opens.

Why a phase flag is better than all-to-all edges

Ordinary producer/consumer edges remain region intersections, so source coverage checks still operate on the actual pixel read. A barrier adds a phase-level ordering fact instead of one edge from every earlier block to every consumer block. At large block counts, the all-to-all representation would grow quadratically even though the synchronization requirement is just one fact about the phase.

A scheduler must explicitly honor the barrier flag. Merely following the local source edges is insufficient: a histogram consumer’s core can be covered before faraway histogram producers finish. A phase-major priority is also insufficient, because preference among ready tasks is not a synchronization contract.

Declaring a reduction without its required barrier is rejected. Declaring an unnecessary barrier can remain correct but prevent otherwise legal pipelining; only the algorithm author can state whether the global dependency is real.

Determinism and encodings

PhaseView gives the reduction access to the complete declared fragment set. A stable traversal order is useful, but it is not a substitute for an honest accumulation rule. Floating-point addition can change with grouping even when the same observations are present. Integer counts and appropriately designed fixed-point sums can provide stronger decomposition-independent guarantees.

SeamFold distinguishes fragment consumers that promise order independence from those that require a particular order. The execution path checks relevant order contracts rather than inferring associativity from the fact that a method is called a reduction. A mean also needs both a sum and a count; averaging block means without weighting gives the wrong result for unequal edge blocks.

Shared bytes are a format boundary. Give a reduced-state encoding a version, validate lengths and field meaning, and distinguish invalid input from a valid empty result. The consumer should not silently reinterpret bytes written by a different operation or an earlier encoding version.

A barrier does not bound the reduction

Histogram bins can remain constant-sized as image volume grows. A map with one entry per connected component cannot, and a seam-equivalence structure can grow with boundary complexity. A globally solved graph can be much larger still. Estimate the cardinality and use bounded fragments, streaming or external-memory algorithms where needed. Moving an allocation into a once-per-phase reduction removes repetition; it does not make the allocation small.

Distributed execution retains the same visibility requirement. Workers must see committed fragments from every completed producer before loading a hoisted reduction or applying a barrier consumer. The reduced state must be available through the supported storage/runtime contract, rather than assumed to live in a coordinator’s process memory. See parallel execution for the distinction between task ownership and shared storage.