矩阵转置缓存分块算法：小块尺寸为何实现更高加速比？

核心原因：缓存容量、局部性与冲突的权衡 #

你观察到的“小block size反而加速比更高”的现象，本质是更大的block size并未带来预期的缓存效率提升，反而触发了缓存置换、局部性下降等问题，具体拆解如下：

• 缓存容量超限导致频繁置换
  更大的block size确实能一次性载入更多数据，但如果单个分块的src和dst子矩阵总大小超过了CPU缓存（比如L1）的可用容量，会导致缓存不断把旧数据置换出去以容纳新数据，反而增加内存访问次数。比如L1缓存通常只有32KB~64KB，当n较大时，过大的blocksize会让分块数据远超缓存容量，每次分块处理都要反复从内存读写，效率骤降。

• dst访问的空间局部性随blocksize增大而恶化
  看你的代码：dst[k + l*n] = src[l + k*n]，其中dst的访问逻辑是按列写入（l固定时，k遍历块内行索引，对应dst第l行的k列，内存地址跨度为n）。当blocksize过大时，这些列访问的元素会分散到更多缓存行中，每访问一个元素都可能触发缓存miss；而较小的blocksize能让这些列元素尽可能集中在少数缓存行内，大幅提升缓存命中率。

• 缓存行对齐与冲突问题
  CPU缓存是以缓存行为单位加载数据的（通常64字节）。如果blocksize的大小超过了单缓存行能容纳的元素数（比如int类型时，一行可存16个元素），dst的列访问会频繁跨缓存行，进一步增加miss率。小blocksize更易匹配缓存行的粒度，减少跨缓存行的访问。

• src与dst的缓存资源竞争
  过大的blocksize会让src和dst的分块数据同时占用大量缓存空间，导致一方的数据被挤出缓存，后续访问又需要重新从内存加载。小blocksize能让两者的分块数据同时驻留在缓存中，避免频繁的置换开销。

你的代码针对性分析 #

你的内层循环顺序是先遍历k再遍历l：

• src[l + k*n]是行连续访问，空间局部性极佳，几乎不会触发缓存miss；
• 但dst[k + l*n]是列跳跃访问，这是缓存低效的核心点。blocksize越小，这种跳跃访问的范围越窄，越容易被缓存覆盖，从而降低miss率。

结论 #

循环分块的blocksize并非越大越好，需要根据CPU缓存容量、缓存行大小以及矩阵规模来调整，找到能让分块数据完全驻留缓存、同时最小化跨缓存行访问的平衡点。

内容的提问来源于stack exchange，提问作者Edward