Struct ForcedSplitLevels

Struct Documentation

struct ForcedSplitLevels

Pass levels, global over every batched basis key: every value gets an integer pass such that a value that needs another value’s completed form sits in a later pass than that other value.

Three kinds of dependency edge bump the reader’s pass because it needs the completed operand (the “source”), keyed on the source rather than the axis basis key:

  • the source is LoopCarried on some axis (any basis key): its full array exists only after its own loop closes, so every direct reader is bumped;

  • the source is a Reduction on some instance (an AccumulateSum

    escape) and the reader is produced inside that same instance (its production site is at or below the reduction’s depth, in the same nest): such a reader would otherwise see the current batch’s partial sum rather than the completed reduction (pinned by the “a reduction source read inside its own loop by a later pass gets two

    pass blocks” test). A reader produced outside the reduced instance reads the completed sum from the escape’s residency scope as always and needs no bump.

    inside(reader_vid, source_vid) decides this per (reader, source) pair – the caller’s lambda captures the loop chain (fusion_slot, depth_of_instance, production_depth, type_cluster) needed to resolve the source’s reduced instance(s) and the reader’s production site exactly as the escape placement does;

  • the source is LoopLocal on an instance some occurrence reads assembled (OccurrenceRole::Assembled, a AccumulateScatter escape) and the reader at such an occurrence is produced inside that instance, decided by inside_assembled the same way. A reader above the instance, at root, or in another nest reads the scattered form after the block closes and needs no bump (pinned by the “assembled reader produced inside the nest above the instance” test);

A fourth kind of bumping edge keeps every pass orderable. The schedule realizes a nest as a chain of blocks, one block per pass at root, and orders the steps of each block level by their dependencies: inside a block, its builds and the one block nested in it; at root, the root builds and every nest’s pass blocks. A block stands for everything produced in it, so the steps of one level can need each other in a cycle although no value does: a build that reads what the inner block completes, with a reader of its own inside that block; two nests’ blocks, each reading a completed value of the other. pass_step_cycle_edges finds such cycles among the steps of one pass (site_of says which step a value belongs to at each level) and the levels are recomputed with the readers it names bumped past their operands, until no cycle is left.

Forward sweep (operands before consumers): level(v) = max over direct operands o of (bump(o, v) ? pass(o) + 1 : level(o)), 0 with no operands; a bumping-edge source’s pass is its level (it is pinned, see below); a value that is the source of no bumping edge has its level as its base. Reverse sweep (consumers before operands): a non-pinned value with at least one consumer is lifted to max(base, min over its direct consumers’ passes), so a value whose readers all sit later is built with them; a value with readers in several passes keeps its base (and is materialized by the builder’s materialization rule when a later same-nest reader needs it).

Every dependency edge points to an equal or earlier pass. With only LoopCarried bumps present (no Reduction-source bump fires) the passes reduce to a two-set partition: carried sources and everything else.

Public Functions

inline int pass(std::size_t vid) const

Public Members

std::unordered_set<std::size_t> carried

LoopCarried (any basis key) ids.

std::unordered_set<std::size_t> pinned

sources of a bumping edge of any kind: the reverse lift skips every id in this set.

std::unordered_map<std::size_t, int> pass_of

value id -> pass, for every value ordered_schedule_dep_graph reached (has a legality cell and takes part in the dependency graph); absent for a value with no legality cell, which pass() below reports as pass 0 rather than throwing.

int max_pass = 0