缓存优化

处理器缓存内部分为一级缓存和二级缓存，以及在多核处理器中常见的三级缓存，其中一级缓存又分为指令缓存和数据缓存两部分。这种结构缓和了处理器与主存之间速度不匹配的矛盾，使存储速度、存储容量与处理器功耗之间的关系相对平衡。

以矩阵乘代码为例具体说明缓存分块技术的使用方法。这段代码中两个内部循环读取了数组z的全部N*N个元素，以及数组y的某一行中的N个元素，所产生的N个结果被写入数组x的某一行。下图为i=1时，原始循环中三个数组的访问情况，其中黑色表示最近被访问过，灰色表示早些时候被访问过，而白色表示尚未被访问。

代码：

对原始循环中的i，j层循环分别进行分块， 将原始的大矩阵分割为了若干个小矩阵，嵌套循环每次对一个小矩阵内的数据进行计算得出一个部分结果，下图说明了分块后三个数组的访问情况。

为进一步说明分析结果，针对上文中的矩阵乘示例使用x86架构平台进行测试。当固定分块大小为50时，随着矩阵规模的不断增大，分块后的矩阵乘程序相对于未分块程序的性能提升越来越明显，如下图所示。

当固定矩阵规模为1024时，此时三个矩阵并不能全部保存在缓存中。随着分块大小的逐渐提高，分块前后运行时间对比如图所示。

造成上述现象的部分原因为高速缓存不同的映射策略以及替换策略，地址映射就是主存地址与高速缓存地址的对应方式，常见的缓存地址映射策略包括直接相联、组相联和全相联。

1.       全相联高速缓存的映射策略为内存中的每个数据块均能够被映射到缓存中的任意一个缓存行，但其请求数据时需要将其地址的标记位与所有缓存行标记位进行对比，花费代价较大。

2.       直接相联的映射方式是内存中的每一个数据块都只能存放在缓存中的一个特定的缓存行，但每个主存块只有一个固定位置可存放，容易产生冲突，使缓存效率下降。

3.       组相联映射实际上是直接映射和全相联映射的折中方案，映射方法是将主存和缓存都分组，组间采用直接映射，组内采用全相联映射。尽量避免了全相连和直接相连的缺点，适度兼顾二者的优点，缓存命中率较高，因而得到普遍采用。

结合上文中矩阵乘的例子，可以将数组按照读取效率从高到低分为三类：

一类数组

这类数组是最好的情况，其矩阵行的长度是缓存行大小的整数倍。当程序访问一个缓存行行大小的数据时，一类数组的这些数据会在一个缓存行中，缓存命中率高。

二类数组

第二类数组其矩阵行的长度不是缓存行的整数倍。这种情况下，程序运行时访存数据很有可能需要跨越两个缓存行，与一类数组相比缓存命中率会变低。

三类数组

第三类数组其矩阵行是整个缓存大小的整数倍。这种情况下，数组的每一列数据均映射到同一缓存行组，当进行数组转置时缓存的利用率非常低，会多次发生缓存不命中的情况，严重影响程序执行效率。

在矩阵乘计算或者其它类似程序中，这三类数组的计算效率差异很大。所以优化人员应结合缓存映射方式，尽可能避免三类数组或者二类数组的出现。例如在计算时对对矩阵的行列进行扩充，使其变为一类数组，从而获得性能的提升。以矩阵乘代码为例，对其进行不同规模下运行时间的测试，结果如下。

代码为：

在此例子中，若将数据由251列扩展到256列，扩充的部分使用0进行补齐，这样矩阵行的长度就是缓存行的整数倍，即从二类数组变成了一类数组，可以增加缓存命中率。

在进行行列扩充优化后，实际的有效数据量依然为251*251，但优化后矩阵乘耗时为100ms，加速比达到了1.6倍左右。

代码为：