Tile coverage, remainders, and legal interchange

For a positive tile size T, write an index as a tile base qT plus an intra-tile remainder r. Full tiles use all T positions, while the final tile may have fewer valid iterations. A loop upper bound such as min(base+T, N) preserves the original one-dimensional domain when N is nonnegative. Multi-dimensional tiling applies that reasoning to each dimension and must keep guards consistent with actual memory operations, not merely suppress an invalid final store.

Padding is another strategy, but its semantics need an identity or neutral value appropriate to the operation. Zero padding that is harmless for one sum can change a maximum, division, normalization, or masked reduction. Allocating padded storage can make an access in bounds without making the padded arithmetic mathematically correct. State both the physical allocation and logical validity domain. Include shapes smaller than one tile and dimensions equal to zero if the source operation permits them.

A larger tile can reduce repeated data movement but requires more live inputs, outputs, accumulators, or staging buffers. The useful size depends on cache or shared-memory budgets, vector shape, occupancy, and the access pattern. Count all simultaneously live tiles and double buffers rather than only one input. A tile that exceeds a resource limit may fail compilation or spill, and a tile that nominally fits can still lose because of conflicts, scheduling, or excess boundary work.

Interchanging tile or point loops changes execution order. Check the original dependence relations under that schedule, including aliasing and effectful operations. A matrix-product reduction also has numerical-order requirements: reassociation may be permitted only by an explicit floating-point contract. Do not infer legality from a faster benchmark or exact-real algebra. An elementwise independent loop has different freedoms from a recurrence or reduction, even when all share the same rectangular bounds.

Validate dimensions just below, equal to, and just above tile multiples, as well as small and non-square shapes. Count coverage or use a reference that exposes missing and duplicate outputs. Exercise slices and layout variants so a contiguous default does not conceal incorrect indexing. After correctness, measure total work, transferred bytes, and resource usage on representative dimensions; a large padded square benchmark can hide poor tail efficiency that dominates real small batches.

The cache lab illustrates abstract reuse only. Reset and set both C=4, s=4, predict twelve hits in its initial sixteen requests, then Step. Reset and re-set C=3, s=4, predicting no hits for the four-address cycle. The empty-start fully associative LRU trace caps at 4096 requests and has no tile domain, loop order, or boundary guards. Use it to discuss a working set that fits versus one that does not, while keeping the actual tiling-coverage proof separate.