存储器山
存储器山是一种综合研究存储器层次结构的工具。它反映了存储器层次结构中不同层次的带宽。也反映了具有不同的时间局部性与空间局部性[1]的程序的性能。通过分析存储器山的数据，还可以看出存储器系统的部分硬件参数。
T. Stricker于1997年在其论文[2]中介绍了存储器山的思想，利用它对存储器系统进行全面描述，并在后来的工作中提出了术语“存储器山”[3]。卡耐基梅隆大学教授Randal Bryant的著作《深入理解计算机系统》（Computer Systems: A programmer's Perspective, Randal Bryant, David O'Hallaron）一书第6.6.1节亦提出了存储器山的概念，并进行了详细分析[3]。
理论上，每台计算机都有一个唯一的存储器山[3]。通过运行一段测试程序，可以得到它的存储器山。了解存储器山，对应用程序的优化能起到指导作用。下图展示了一个基于Intel Core 2 Duo 处理器的存储器山。
目录 |
[编辑] 存储器山测试原理
为了说明存储器山的测试程序的原理，首先简要介绍局部性和存储器层次结构这两个重要概念，然后介绍存储器山的定义和测试程序的原理模型。
[编辑] 局部性
通常，一个编写良好的（优化的）程序具有良好的局部性[3][4]，主要表现在两个方面。
时间局部性（Temporal locality）：如果被访问过的存储器地址在较短时间内被再次访问，则程序具有良好的时间局部性。在一定的时间内，重复访问同一个地址的次数越多，时间局部性越好。换句话说，对同一个地址的两次访问间隔时间越短，时间局部性越好。
空间局部性（Spatial locality）：如果程序访问某个存储器地址后，又在较短时间内访问临近的存储器地址，则程序具有良好的空间局部性。两次访问的地址越接近，空间局部性越好。
局部性在程序中普遍存在。好的程序通常具有好的局部性，是一个普适的原理。[3]
[编辑] 存储器层次结构
不同类型的存储设备，其访问速率相差很大。其基本规律为：访问速率越高的设备，单位容量的成本越高，于是越不容易做得很大。计算机系统的设计者需要在控制成本的同时，尽量提高存储器系统的速率。
受益于局部性的概念，计算机的存储器系统通常设计成一个层次结构，CPU内部的寄存器为该层次结构的最高层----它的容量最小，但速率最高。往下依次为各级cache，主存，磁盘等等。该层次结构的运行策略是：尽量让当前被频繁访问的存储区的内容驻留在较高层存储器，作为代价，把不常访问的存储区的内容置换到较低层存储器。同时，尽量让当前被访问的元素附近的元素也驻留在较高层存储器。一个具有良好的局部性的程序，几乎能总是访问高层的存储器，享受到最高的访问速率。
从程序员的角度来看，要尽量编写具有良好的局部性的程序，以适应层次结构，提高程序运行速率。
[编辑] 存储器山测试程序[3]
具有不同的时间局部性和空间局部性的程序，对存储器层次结构的利用效率是不同的。局部性较好，则能得到较快的访问速率。构造一个存储器测试程序，以不同的时间局部性和空间局部性对存储器进行访问，就能得到存储器系统在不同的局部性下的性能（即访问速率）。以控制时间局部性的变量为x轴，控制空间局部性的变量为y轴，存储器访问速率为z轴，就能得到一个三维图形，它看起来像一座有着山峰，山脊和山坡的小山，即存储器山。
通过存储器山，可以直观地看到具有不同的时间局部性和空间局部性的程序对存储器的访问速率的巨大差别。可作为程序员优化程序的参考。
更加有趣的是，通过分析存储器山的数据，还可以看出存储器系统的部分硬件参数。包括L1数据cache（简称为L1-Dcache）、L2-cache和主存（物理介质通常为SDRAM）各自的最高平均速率，L1-Dcache和L2-cache的容量，甚至L1-Dcache的行尺寸。
不过，存储器山并非万能工具。从中无法看出cache的相联度、访问延迟等参数（这些参数可以用其他测试程序间接得出，但无法从存储器山测试程序中得出）。由于连续密集访问，cache预取（Prefetching）也会被阻塞从而无法体现其效果。
存储器山测试程序的核心就是这样一个循环：
Kernel_loop(elems, stride):
for (i = 0; i < elems; i += stride)
result = data[i];
其中，data是一个整形数组（整形元素单位为4字节），result是一个寄存器变量。Kernel_loop所做的事情，就是将data数组的内容依次读取到CPU的寄存器中。参数elems表示data数组的尺寸，即工作集（working set）尺寸。参数stride表示访问时的步长，即相邻两次访问的元素的地址间隔。 用Get_readrate()函数来获取特定参数下Kernel_loop的读速率：
Get_readrate(elems, stride): Kernel_loop(elems, stride); // 为cache预热，避免“冷缺失” time_start = GetTimer(); // 记录测试开始时间 Kernel_loop(elems, stride); // 执行真正的测试 time_end = GetTimer(); // 记录测试结束时间 time_cost = time_end – time_start; // 得到时间开销 readrate = (elems*sizeof(int)/stride) / time_cost; // 换算为读速率
main()函数改变elems和stride参数的大小，记录Kernel_loop在各个参数下的读速率：
main():
for (elems = MINELEMS; elems <= MAXELEMS; elems <<= 1)
for (stride = 1; stride <= MAXSTRIDE; stride++)
Get_ readrate (elems, stride);
以elems为x轴，stride为y轴，readrate为z轴，即可得到一座存储器山。这裡，elems控制时间局部性。因为当stride固定时，elems越小，对同一个地址的两次访问（cache预热时一次，真正测试时一次）间隔的时间越短。而stride控制空间局部性。因为stride越小，相邻两次访问的地址间隔越小。readrate即是不同时空局部性下对存储器的读速率。MINELEMS、MAXELEMS、MAXSTRIDE等常量的具体数值根据测试平台的参数来选择。
[编辑] 简要分析
本条目图片所示存储器山的测试平台为装备intel Core 2 Duo T9300处理器的个人计算机。测试平台基本参数为：
| CPU型号 | 主频 |
|---|---|
| Intel（R）Core(TM)2 Duo CPU T9300 | 2.50GHz |
| cache类型 | 容量 | 数据指令是否共享 | 行尺寸 | 相联度 |
|---|---|---|---|---|
| L1-Dcache | 32Kbyte | 否 | 64byte | 8路组相联 |
| L2-cache | 6144Kbyte | 是 | 64byte | 16路组相联 |
固定步长不变，可以明显看到，当工作集尺寸不大于32Kbytes时，读速率最高。当工作集尺寸介于32Kbytes与8Mbytes之间时，读速率明显降低。当工作集尺寸大于8Mbytes时，读速率最低。这是由于工作集的尺寸决定了由哪一层存储器来提供待读取的数据。小于32KBytes的工作集可以完全存放在L1-Dcache中，介于32Kbytes与8Mbytes之间的工作集不能完全存放在L1-Dcache中，但可以完全存放在L2-cache中（准确地说，6Mbytes以上的工作集就不能完全存放在L2-cache中了，但由于工作集尺寸呈指数增长，图中无法准确反映6Mbytes时的情况）。
当工作集尺寸小于32Kbyte时，读速率有明显的下降。看起来似乎违背了时间局部性的原理----越小的工作集，性能反而越低。事实上这是Kernel_loop()的额外开销造成的----在该区域，工作集越小，步长越大，则Kernel_loop()的循环次数越少，该额外开销占总开销的比例就越大，导致最终换算出来的读速率越小。所以这个区域不能反映L1-Dcache的真实性能。
而当工作集尺寸固定时，不同的步长也会导致不同的读速率。例如，固定工作集尺寸为512Kbytes，由于工作集尺寸大于L1-Dcache容量，此时测试程序Kernel_loop()的读操作会遇到L1-Dcache缺失，需要从L2-cache中读取数据。随着步长从1个字增加到16个字，读速率逐渐下降。步长位于16个字和32个字之间时，读速率不变，保持在一个较低的值（约2100MBps）上。这是由于L1-Dcache的每次缺失，都会从L2-cache中读回一行数据（行尺寸64bytes，即16个字），随后对这一行的其他部分的读取，就都能由L1-Dcache服务，得到较高的读速率。所以，当步长小于16个字的时候，L1-Dcache的服务会提高读速率。当步长大于16个字的时候，每一次读操作都会缺失，所有的数据都需要从L2-cache中读取，读速率就稳定等于L2-cache的读速率了。
[编辑] 另请参考
- 《深入理解计算机系统》官方网站给出的存储器山测试程序源代码。
- 《深入理解计算机系统》官方网站推荐的生成存储器山的程序ECT memperf，该程序由存储器山概念的最早提出者Tom Stricker[2]编写。
- 卡耐基梅隆大学给出的R.E.Bryant的简历，著作列表中第一位便是《深入理解计算机系统》。
- 卡耐基梅隆大学给出的《深入理解计算机系统》电子版目录，目录封面为存储器山，第6.6.1节（The Memory Mountain）为对存储器山的分析。
- Introducing Computer Systems from a Programmer's Perspective，《深入理解计算机系统》的作者对该书的介绍。
- Memory part 2: CPU caches来自lwn.net的文章，作者Ulrich Drepper，深入分析了cache的性能，其中包括对cache带宽的详细分析。
- Memory Hierarchy in Cache-Based Systems，作者Ruud van der Pas, 2002, Sun Microsystems，是关于CPU高速缓存系统很好的入门介绍。
- RightMark Memory Analyzer，功能丰富的存储器测试分析软件。
- Intel Core 2 Duo Test，对Core2处理器的评测。
- 文献1[3]的第6.2节，以及文献2[4]的第7.1节，有关于局部性的更多讨论。
- 文献1[3]的第6章，以及文献2[4]的第7章，有关于存储器层次结构的更多讨论。
- 文献1[3]的6.6.1节，有关于存储器山测试程序的更多讨论。
[编辑] 资料来源
- ^ Peter J. Denning The locality principle, 2005.关于局部性原则的讨论
- ^ 2.0 2.1 T. Stricker, T. Gross, Global address space, non-uniform bandwidth: A memory system performance characterization of parallel systems. In Proceedings of the Third IEEE Symposium on High-Performance Computer Architecture. IEEE.
- ^ 3.0 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 （美）Randal Bryant, David O'Hallaron，著.《深入理解计算机系统》[M].龚奕利，雷迎春，译。北京：中国电力出版社，2004。ISBN 7-5083-2175-8
- ^ 4.0 4.1 4.2 （美）David A.Patterson, John L.Hennessy，著。计算机组成和设计-硬件/软件接口[M].郑纬民 等，译。北京：清华大学出版社，2003。ISBN 7-302-06901-8
