A recursive decomposition of an affine Tile.

A Tiling defines the structural children of a tile. Each structural child is labelled by its relationship to the parent: an Anchor child contains the parent root, while a Sibling child introduces a distinct communication root.

A lawful Tiling satisfies:

Inclusion

Every structural child is contained in its parent.

  tileRanks child `isSubsetOf` tileRanks parent
  

Structural cover

For a non-terminal parent, the structural children partition the parent ranks: their ranks are pairwise disjoint and their union is the parent.

Progress

Every structural child is strictly smaller than its parent.

  length (tileRanks child) < length (tileRanks parent)
  

Anchor preservation

An anchor child preserves the parent root.

  case relation node of
    Anchor _ -> root (tile node) == root parent
    _        -> True
  

Sibling movement

A sibling child has a distinct root from its parent.

  case relation node of
    Sibling _ -> root (tile node) /= root parent
    _         -> True
  

Partition by fixing one coordinate at a time.

BlockPartitioning finds the first non-singleton dimension. It creates one anchor child at index 0 and one sibling child for each remaining index in that dimension.

Rectangular tiling with bounded communication fan-out.

BoundedFanout computes the full local rectangular frontier of a tile. The frontier contains, for each active dimension, the ranks whose first coordinate away from the root occurs in that dimension. The remaining root point is emitted as a terminal anchor.

The requested cap is respected when it is geometrically feasible:

minimumFanout tile <= fanout
  ==> length (children (BoundedFanout fanout) tile) <= fanout

Unconditionally:

length (children (BoundedFanout fanout) tile)
  <= effectiveFanout tile fanout

The tiler preserves affine rectangular children; it does not introduce jagged regions. A non-positive requested fan-out produces no children.

Minimum communication fan-out required by rectangular geometry.

This is the number of active dimensions in the tile. With affine rectangular children and a corner root, each active dimension contributes one necessary frontier region away from the root.

Fan-out actually available to BoundedFanout.

The requested cap is honored when geometry permits it. If the cap is below the rectangular minimum, the geometric minimum is used instead.

Partition by bisecting one dimension at a time.

Bisection finds the first non-singleton dimension. It keeps the lower floor(n / 2) half as the anchor and creates one sibling from the remaining upper half.

The affine dimension and starting index selected by a tiling step.

A Split records where a child tile came from inside its parent.

Relationship between a TileNode and its parent.

Relations distinguish geometry-only anchor steps from communication steps. The tree layer contracts anchor edges; sibling edges become communication edges.

A tile labelled with its relationship to a parent tile.

TileNode is the node type used by decomposition and hop trees. The relation field records how the node arises from its parent; the root node of a tree uses Root.