Title: Latency Based Tiling Show Chinese title

Title: 基于延迟的分块

Abstract: Latency Based Tiling provides a systems based approach to deriving approximate tiling solution that maximizes locality while maintaining a fast compile time. The method uses triangular loops to characterize miss ratio scaling of a machine avoiding prefetcher distortion. Miss ratio scaling captures the relationship between data access latency and working set size with sharp increases in latency indicating the data footprint exceeds capacity from a cache level. Through these noticeable increases in latency we can determine an approximate location for L1, L2, and L3 memory sizes. These sizes are expected to be under approximations of a systems true memory sizes which is in line with our expectations given the shared nature of cache in a multi process system as described in defensive loop tiling. Unlike auto tuning, which can be effective but prohibitively slow, Latency Based Tiling achieves negligible compile time overhead. The implementation in Rust enables a hardware agnostic approach which combined with a cache timing based techniques, yields a portable, memory safe system running wherever Rust is supported. The tiling strategy is applied to a subset of the polyhedral model, where loop nestings are tiled based on both the derived memory hierarchy and the observed data footprint per iteration. Show Chinese abstract

Abstract: 基于延迟的分块提供了一种系统化的方法，以推导出近似分块解，该解在保持快速编译时间的同时最大化局部性。 该方法使用三角形循环来描述机器的缺失比率缩放，避免预取器失真。 缺失比率缩放捕捉数据访问延迟与工作集大小之间的关系，延迟的急剧增加表明数据足迹超过了缓存级别的容量。 通过这些明显的延迟增加，我们可以确定L1、L2和L3内存大小的近似位置。 这些大小预计会低于系统真实内存大小的近似值，这与我们的预期一致，考虑到多进程系统中缓存的共享性质，如防御性循环分块中所述。 与自动调优不同，自动调优可能有效但代价高昂，基于延迟的分块实现了可忽略的编译时间开销。 Rust中的实现使一种与硬件无关的方法成为可能，结合基于缓存时间的技术，产生一个可在Rust支持的任何地方运行的可移植、内存安全的系统。 分块策略应用于多面体模型的一个子集，其中循环嵌套基于推导出的内存层次结构和每迭代观察到的数据足迹进行分块。