摘要: 循环镶嵌（loop tiling）,或称循环分块 (loop blocking)，是人们熟知的一种程序转换技术。针对带有矩阵运算的多层循环，循环镶嵌可以用来提高数据的局部化程度，从而提高高速缓存器的命中率。在关联度 (associativity) 较低的高速缓存器上，数组在存储空间的分布直接影响到数组元素与缓存线的对应，从而影响到哪些数组元素会在同一缓存线上产生冲突。为了提高各个循环嵌块执行中对高速缓存的访问命中率，许多文献提出了通过调整嵌块尺寸来消除数组元素冲突的办法。其中的很大一部分努力侧重在数组的自我冲突，也就是同一数组的不同元素之间的相互冲突。 本文指出，调整嵌块尺寸并不是消除数组分布冲突的最佳办法。其原因在于，使分布冲突达到最小的嵌块尺寸往往使得缓存容量的使用效率降低，其结果是造成另一类缓存错失的上升。这一类缓存错失是出于缓存容量的限制。所以，仅仅通过选择嵌块尺寸，通常无法使数组冲突和容量限制带来的两种不同错失同时达到最小。本文从另一个方向来解决这个问题。本文首先对嵌块尺寸选择与缓存容量之间的关系作分析。对一类重要的矩阵运算问题，我们找出使得容量限制导致的缓存错失达到最小的嵌块尺寸。数组冲突的最小化，则通过存储空间中对数组作空白衬垫（array padding）来得以实现。空白衬垫量的计算是在前面确定了嵌块尺寸的基础上作出的。本文给出一个确定衬垫量的定理，并由此得出一个对任意数组维数都通用的衬垫算法。