Search papers, labs, and topics across Lattice.
This paper extends the Mathematics of Arrays (MoA) framework by introducing a new operator that derives hierarchical blocking and prefetch schedules based on a machine's shape, specifically addressing the discrepancies in cache size predictions across different architectures. The authors empirically validate their approach against three real machines, demonstrating that their method can recover calibrated block sizes while reducing unknowns to a limited set of occupancy fractions. Additionally, they articulate an open problem regarding the derivability of these occupancy fractions from fundamental architectural properties, providing a foundation for future research in this area.
The new hierarchical blocking operator reveals that cache occupancy fractions may be more architecture-specific constants than previously thought, challenging existing assumptions in performance prediction.
A companion empirical study found that dense matrix multiplication block sizes calibrated on Apple M1 Pro correspond to two cache-t formulas that mispredict badly on a dierent chip's known cache sizes. This paper formalizes the question that nding 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-specic 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 falsiable 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-dened 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 rst, honest attempt at extending the framework toward predicting throughput directly, not just block size, closes the paper: two terms prove derivable from a specication sheet, one requires a single measurement, and one tested across three machines does not yet transfer between them.
