3.4 案例分析：稠密矩阵转置
在下面的实例分析中，假定矩阵按列存储。计算一个稠密矩阵的转置（A = BT），根据循环的组织顺序，矩阵A或者B会有一个矩阵的访存是非连续的。矩阵转置最不幸的实现方式如下：
矩阵A的写入操作是非连续的（见图3-7）。由于写分配操作的影响，非连续写比非连续读的代价要大得多。从这个最坏的代码出发，我们尝试获得期望性能。由于矩阵转置不执行任何算术操作，因此我们使用有效带宽（即应用程序达到的GB/s）来表示性能。
图3-7 vanilla矩阵转置中的cache行遍历（非连续写入操作，按列存储）。如果矩阵第一维的大小是cache行的整数倍，则矩阵的每一列都是cache行对齐的
C表示cache大小，Lc表示cache行大小（单位为DP字）。根据矩阵大小的不同，共有三个主要的性能优化法则：
- 当两个矩阵可以一次性加载到CPU cache中时（2N2＜～C），我们期望的有效访存带宽同cache的访存速度是同一数量级的。空间局部性的重要性只体现在多个不同的cache层次上。这种情况下，优化空间有限。
- 当矩阵太大而不能一次性加载到cache中，但仍然有
A的非连续写操作对性能的影响微乎其微，这是因为在一次完整的行遍历中，所有导致写未命中数据的写入操作都开启一个cache行进行写分配。这些cache行在接下来的Lc-1行中有很大可能依然位于cache中，减轻了非连续写的影响（空间局部性）。在这种情况下，有效访存带宽应该和处理器可达到的最大访存带宽位于同一数量级。
- 当N继续增大，使得NLc＞～C时，每次对A的写入操作都会导致cache未命中和随后的写分配操作。在这种情况下，当进行内存写入时，只有一个cache行的数据被真正用到，所有的空间局部性都会丧失，因此导致预测性能的大幅下跌。
图3-8的vanilla 部分说明了上述假设基本上是正确的。然而，即使工作集全部加载到cache中，非连续写操作看起来也是非常低效的。这可能是因为所选择架构（英特尔Xeon/Nocona）的L1 cache是完全写入（write-through）类型；例如，不管L1 cache命中与否，L2 cache在写入操作时总是更新。因此，两级cache间的写分配操作浪费了大部分内部可用带宽。
在上述的第二个性能优化法则中，当写入操作的N个cache行占用的cache大小和L2 cache大小具有可比性时，性能会大致恒定在一个水平上：有效带宽大约是1.8 GB/s，同理论最大带宽5.3 GB/s（由两个性能为333MTransfer/s的内存通道获得）相比并不理想。绝大多数商业架构的理论峰值带宽通过使用编译器生成的代码不可能达到，但是50%的性能还是经常可以达到的。因此，肯定有一个因素能够显著降低可用带宽。这个因素就是快表（Translation Lookaside Buffer，TLB），物理地址和逻辑地址转换表。TLB可以看作是额外的一级cache，其cache行大小为物理内存页面大小（页面大小通常为4KB，也有16KB的，在有的系统上甚至可以配置）。在本节使用的架构上，它只需容纳64个元素，对应于256KB内存（物理页面大小为4KB）。这个值小于L2 cache大小，所以TLB的影响在cache内部也可以观察到。更为严重的是，当N大于512时，也即一个矩阵行大小超过了物理页面的大小，非连续访存的每一个单独访存操作都会导致TLB未命中。即使页表位于L2 cache中，这也会明显降低有效带宽。这是因为每一次TLB未命中都会导致至少57个处理器时钟周期的访存延迟（在这个给定的CPU上）。在频率为3.2 GHz，总线传输速率为666MW/s的核上，这相当于传输超过64字节cache行的数据。
当N＞～8192时，性能最终达到了预期的低水平。本节所使用处理器的理论内存带宽为5.3GB/s，实际仅达到了大约200MB/s。在有效长度为128个字节（每次未命中时，两个长度为64字节的cache行被一起读取，但分别提取）的cache行中，只有一个元素被用来执行非连续写操作。在cache内部，每一次循环迭代都需要读取或者写入3个字，但最坏的情况是需要读取或者写入33个字。因此我们期望一个1 : 11的性能比，同观察到的值大略相等。
我们必须再次强调基于硬件特征的性能预测并不是在任何情况下都能够发挥作用[M41, M44]，特别是在商业系统中，其芯片组、内存芯片和中断基本上不可控。有时对发生的独特性能行为的原因只有一个定性的了解，但这足以获得下一步的逻辑优化步骤。
稠密矩阵转置最重要的一个优化方法是交换嵌套循环的顺序，即将i移入内层循环。虽然这样会导致矩阵B的非连续读，但是却消除了矩阵A的非连续写，从而节省了大约一半（准确地说是5/11）的内存带宽（对于较大的N）。实际的性能收益（见图3-8 “flipped”部分）虽然明显，但还是没有达到这个性能预期。一个可能的原因是缺乏一个对于非连续写的更高效的内存接口。
图3-8显示的性能图在某些点看起来非常不稳定。粗略看来，并不确定是否是某些N值导致了明显的性能降低（同它的邻值比较）。然而，通过仔细分析（图3-9的“vanilla”部分）可以看出当数组维度是2的指数倍时，对性能是非常不利的（基准测试程序对于每个新的N都会分配合适大小的矩阵）。像在1.3.2节描述的那样，由于关联性的不足，当连续迭代命中相同的cache行时，非连续访存会导致性能“颠簸”。图3-7非常清楚地说明了当矩阵的第一维大小是2的指数倍时，转置操作是非常容易发生性能“颠簸”的。对于大小为C并且直接映射的cache，每隔C/N次迭代就会命中相同的cache行。对于大小为Lc的cache行，有效的cache大小为：
由于关联性的限制，这是实际可用的cache大小。对于一个m路组关联的cache，其有效大小也仅仅是乘以m。考虑一个真实的例子：C = 217 (1 MB)，Lc = 16，m = 8，N = 1024，Ceff = 211 DPW（DP word，DP字），即16 KB，则NLc >>Ceff，其性能应该和N值很大时相似。
然而，一个简单的代码变换就可以消除性能“颠簸”的影响：假定矩阵的大小为1024*1024，将第一维的大小增加p（称为padding），得到（1024+p，1024）的矩阵A，从而导致完全不同的cache使用模式。如果Cm/N＞Lc/p（见图3-10），则Lc/p次迭代后，访问地址属于另外一组m个cache行，并且没有关联性冲突。当将第一维的大小增加1时，图3-9显示了显著的效果。通常来讲，应该使用所有的方法使数组的第一维大小不是2的指数倍。不同的维度添加不同大小的padding从而获得最优性能是非常有效的。所以有时可应用一个经验法则：尽量将数组的维度修正为16的奇数倍。
应用矩阵转置算法的更进一步优化方法将在下面的章节中详细讨论。