Machine Shape and Hierarchical Blocking: A Mathematics of Arrays Formalization, with an Open Problem in Hierarchical Shape Occupancy

Abstract

Lenore M. Mullin

A companion empirical study found that dense matrix multiplication block sizes calibrated on Apple M1 Pro correspond to two cache-fit formulas that mispredict badly on a different chip’s known cache sizes. This paper formalizes the question that finding raises. We extend the Mathematics of Arrays (MoA) framework’s array-shape derivation operator to a new operator that derives a hierarchical, multi-level blocking and prefetch schedule from a machine’s shape: an ordered sequence of cache-level capacities, bandwidths, and occupancy fractions. This operator recovers the calibrated values on every one of three real machines tested to date as a special case, reducing each machine’s unknowns to a small number of level-specific occupancy fractions. We then state precisely, without claiming to resolve, the paper’s central open problem: whether those fractions are derivable from more primitive properties – co-tenancy, private- cache-level count, associativity, prefetcher behavior – or are fundamentally per-architecture constants. Four falsifiable hypotheses are stated and tested against real hardware, with mixed results. We further state two limits of the framework explicitly: it requires dedicated, non-virtualized hardware access to be well-defined at all, and it extends only partway to a distributed-memory network, where realizing a tile across nodes requires a separate choice of communication algorithm the framework does not itself make. A first, honest attempt at extending the framework toward predicting throughput directly, not just block size, closes the paper: two terms prove derivable from a specification sheet, one requires a single measurement, and one – tested across three machines – does not yet transfer between them.

PDF