储器层次结|「计算机组成原理」：高速缓存存储器( 七 ) 存储器|cpu|索引|局部性|缓存

文章插图
假设每个块中能保存4个元素，则可以分析每个变量的命中率
说明我们可以对循环重排列，来提高空间局部性，增加命中率。
3.2 使用分块来提高时间局部性
分块的主要思想是将一个程序中的数据结构组织成大的片（Chunk），使得能够将一个片加载到L1高速缓存中，并在这个偏重进行读写。

文章插图

文章插图
如上图所示是一个普通的矩阵乘法函数，这里将二维数组想象成一个连续的字节数组，通过显示计算偏移量进行计算。这里假设每个块中可保存8个元素，并且高速缓存容量远小于矩阵的行列数。
每一次迭代就计算一个C的元素值，我们分析每一次迭代的不命中次数
对于矩阵a，一次会保存行的8个元素到块中，则一行元素一共会有n/8次不命中。对于矩阵b，因为是列优先读取的，所以无法利用高速缓存中保存的块，所以一行元素会有n次不命中。则一共会有9n/8次不命中，对于C中的n*n个元素，一共会有 [公式] 次不命中。

文章插图
如上图所示是使用分块技术实现的矩阵乘法，将矩阵乘法分解为若干个BxB小矩阵的乘法，每次能将一个BxB的小矩阵加载到缓存中。
每一次迭代就计算C中一个BxB大小的块，我们分析每一次迭代的不命中次数

文章插图
每个块有 B^{2} /8B2??/8 次不命中次数，而每一行每一列有n/B个块，所以计算一次C中的一个块会有次不命中，则一共会有 nB/4 times {(n/B)}^{2} = n^{3}/(4B) ，我们就能调整B的大小来减小不命中率。
分块降低不命中率是因为加载一个块后，就反复使用该块，提高了空间局部性。
分块技术的介绍：http://csapp.cs.cmu.edu/2e/waside/waside-blocking.pdf
【储器层次结|「计算机组成原理」：高速缓存存储器】建议：

将注意力集中在内循环中，因为大部分的计算和内存访问都集中在这里
按照数据对象存储在内存中的顺序，以步长为1来读数据，使得空间局部性最大。比如步长为2的命中率就比步长为1的命中率降低一半。
一旦从存储器读入一个数据对象时，就尽可能使用它，使得时间局部性最大。特别是局部变量，编译器会将其保存在寄存器中。

文章插图