1.3 存储层次
数据以不同的方式存储在计算机系统中。前面章节提到，CPU有一组可以不延时访问的寄存器。另外，有一个或几个容量小但存取速度快的cache，用以保存最近被访问过的数据项副本。主存要慢得多，但是容量比cache大很多。最后，数据能够存放在磁盘上，在需要的时候再复制到主存中。这是一个复杂的层次结构，为了搞清楚它的性能瓶颈，理解数据在不同层次之间的传递原则是至关重要的。下面我们将集中描述从CPU到主存的各个层次（见图1-3）。
1.3.1 高速缓存
高速缓存是低容量、高速度的存储器，通常集成在CPU内部。只要认识到主存的数据传输速度远低于CPU的运算速度，就能很容易理解为什么高速缓存是必不可少的。当每核的峰值性能达到GFlop/s时，存储器带宽即数据从存储器到CPU的传输速率，还停留在GB/s，完全不能使运算单元保持繁忙（更加详细的分析见第3章）。更加糟糕的是，为了将一个数据项（一个或两个DP字）从主存传送到CPU，需要一个等待时间，称为延迟。延迟通常定义为传输一个0字节消息需要的时间。主存的延迟通常是几百个CPU周期，由存储器芯片、芯片组和处理器等不同成分组成。尽管摩尔定律保证了芯片复杂性和性能的稳定增长，但是存储器性能的增长速度仍然在一个很低的水平上。CPU和主存之间的延迟和带宽有越来越大的差距[R34，R37]。
在很多情况下，高速缓存能够缓解主存带来的影响。通常至少有两级cache（见图1-3）分别称为L1和L2。L1通常分成两个部分：指令cache（I-cache，L1I）和数据cache（L1D）。而在L2上，存储数据和存储指令通常都是相同的。一般来说，cache离CPU寄存器越近，它的带宽越大，延迟越低，管理开销就越小。当CPU发出读请求（加载）时，传输一个数据项到寄存器中，L1 cache逻辑检查该数据项是否已经存放在其中。如果在，则称为cache命中，且请求能够被立即响应。然而在cache不命中的情况下，数据需要从外层cache中取出，最糟的情况下需要从主存中获得。如果所有的cache都被占用，则需要由硬件实现的算法来进行数据替换，用新的数据替换cache中原来的数据。而在cache不命中对于写操作更加复杂，后文将介绍。因为代码中往往有很多循环，所以相比于数据cache，指令cache的重要性要稍低，指令cache的不命中率与数据高速缓存相比也要低很多。
cache只有在应用程序的数据使用具有局部性引用时才会对性能产生积极影响。更加具体地说，数据项被加载到cache中后，在没来得及被换出前被再次使用，这也称为时间局部性。现在我们运用一个简单的模型来估计高速缓存带来的性能增益。使用一个参数τ表示速度上cache比主存快的倍数（这涉及带宽和延时；存在更精确的模型，但是计算效果是一样的）。令β等于cache的重用率，即最近被访问过的数据被再次访问的次数。主存访问时间（同样这里包括延时和带宽）记为Tm。在cache中，数据访问时间减少至Tc = Tm/τ。对于一些确定的β，平均访问时间达到Tav = βTc+(1-β)Tm，于是我们计算性能增益为：
如图1-9所示，仅当cache的重用率接近1时，它才能获得一个显著的性能优势。
不幸的是，支持时间局部性是不够的。许多应用程序为流模式：大量数据被加载到CPU、修改然后写回，而没有被及时复用。对于一个仅支持时间局部性的cache，复用率β等于0。由于cache中的旧数据项被新的取代，产生很大延迟，因此每一次新的数据加载都有很大开销。为了减少延时开销，在cache中加入了一个叫cache行（cache line）的特殊组织结构。在cache和主存之间的数据传输，都在cache行级别上进行（这个规则可能有一些例外，可参考下面介绍的非时效性存储的内容）。cache行的优势在于，cache不命中的延时开销只发生在数据项第一次不命中的时候。cache行作为整体从主存中取出，相邻数据项能够以一个更低的延时从cache中取出，提升了cache 的命中率γ，不要与重用率β混淆。因此，如果应用程序具有一些空间局部性，即连续访问相邻数据项的概率越高，那么延时能够显著减少。cache行的缺点是不支持不稳定的数据访问模式。那样会导致每次数据加载都会产生不命中和随之而来的延时，而且由于传输了整个cache行会导致主存总线上传输很多从未被使用过的数据，则应用程序的有效带宽将非常低。然而从总体上来看cache行的优势还是很受欢迎的，大部分处理器制造商都使用这一机制。
假设一个基于DP浮点型的流式应用程序在CPU上执行，cache行的长度为Lc = 16字，空间局部性的命中率γ为一个看似很大的值上：γ= (16-1)/16 = 0.94。它的性能仍然依赖于主存的带宽和延迟，即代码受制于内存。为了使应用程序能够真正受制于cache，而不再受主存带宽和延时的影响，γ必须足够大，从而使得处理cache中数据的时间远远大于重新重加载数据的时间，这种情况的发生取决于执行操作的细节。
现在，我们可以定性分析基于cache体系结构上三维向量算法性能，如图1-4中所示。在很小的循环长度下，处理器流水线太长以至于效率不高。随着N的增加，这种制约变得微不足道，而当4个数组都能在最内层cache 命中时，性能达到一个饱和值，这个值由一级（L1）cache带宽和处理器发出存取指令的能力决定。继续增加N的大小将导致性能急剧下降，因为最内层cache的容量不足以容纳所有数据。二级（L2）cache总有更长延迟但带宽只是接近于一级cache，因此延迟比预期更大。然而，来自L2的数据流还带来一个缺点：此时的L1不得不向寄存器提供数据，同时又持续地重载并数据写回到L2，这限制了L1cache的带宽利用率。由于cache向其他存储层次传送数据的能力高度依赖体系结构，除了最内层cache和主存外，整体性能很难被估计。随着N的增加，不同层次cache的性能分别下降，直到最后，甚至最外层的cache容量都显得过小，以致所有的数据不得不与主存交换。而带宽瓶颈的位置也与cache的容量直接相关。一些基本参数，例如cache、主存带宽和应用程序数据需求等，对循环的性能有着不同影响，3.1节将具体讲述怎样预测这些参数带来的性能影响。
写数据比读数据更加复杂。在当前的cache中，如果即将被写回的数据已经存储在cache中，则发生写命中。写cache有多种策略，但是通常最外层的cache采用写回策略：先修改cache行，当数据要被从cache中换出时，整个数据再被写回主存。然而，当写不命中时，在数据被修改之前，由于cache和主存的一致性，需要先将数据从主存写入cache中，这就是所谓的写分配，这将导致从CPU到主存的写数据流会使用总线两次：一次是从主存导入数据到cache行，另一次是修改后写回（由于写分配，traid基准测试代码的数据转移需求增加了25%）。因此，流式应用程序不总是受益于写回策略，其可能导致更多写分配的发生。所以要尽可能避免写分配的发生，某些体系结构提供了这种功能，并且一般有两种不同的策略：
- 非时效性存储。有一些特殊的存储指令不必通过所有的cache层次而将数据直接写进内存中。写数据流不会“污染”cache，但是这会导致缺乏时间局部性。为了避免大量的延时，通常需要有一个小的写缓冲区，临时存储着由许多非时效性存储的数据[C 104]。
- cache行标零。一些特殊的指令能把cache行标零，代表发生过改变。这些数据在替换出去的时候要写到内存。与非时效性存储比较，cache行标零方法能够为写数据流用完cache空间。另一方面，在高速缓存受限的条件下，存储操作不必减速。但是必须注意，即使只有一部分数据改变，整个cache行在替换的时候都要写到内存。
这两种方法都能被编译器使用，程序员也可以通过指令来指示编译器如何做，在简单情况下，编译器在代码优化阶段会自动使用这些指令。但是要留意，使用非时效性存储会让受限于cache的代码变慢，但是会让受限于存储的代码则变得更有效。
需要注意的是，之所以需要写分配，是因为cache和内存交换的基本单元是cache行。还有一种普遍的误解认为写分配只需要保持多处理器核的cache一致就可以了（还需要与内存一致）。
1.3.2 高速缓存映射
之前我们默认假设了cache行与存储单元之间的映射没有任何约束，这种设计也叫全相联（fully associative）。不幸的是，这种方式设计的cache很难做得很快或者很大，因为全相联的cache有很大的簿记开销：每一个cache行，在CPU的地址空间中必须存储其地址，而且每一次存取操作都要检查所有的地址。此外，如果cache满了，cache的替换策略由硬件实现。最近最小使用策略（Least Recently Used, LRU）会保证“最久”的项被替换，而像最近不使用算法（Not Recently Used，NRU）或者随机替换策略则不能够保证。
直接映射策略则是最直接、最简单的方法。直接将大小为cache容量的内存块映射到cache（如图1-10），相距cache大小整数倍的存储单元会被映射到cache中相同的行，只要去除最高有效位，就能很快地得到某内存地址的cache行。而且cache的替换不需要任何算法，不需要硬件支持也没有时间周期的开销。
直接映射cache的一个缺点是很可能产生颠簸，即某些cache行被快速地导入和替换。当应用程序中使用的很多数据映射在cache的同一行时就会发生种现象。用一个简单的例子说明，例如还是双精度的跨步三维向量算法，只要改变一下内循环，如下所示：
用cache的容量（双精度字为单位）作为跨步，连续的循环迭代会取相同cache行数据，即使每一次导入都填满cache行，也会导致一次cache失效。原则上cache中有大量的空间未被利用，这种情况叫做冲突缺失。如果跨步为cache行的长度，即使N很小，cache的利用率也为100%。而跨步为cache容量时，无论N多小，cache重利用率几乎为0。
为了降低替换开销同时减少冲突失效和cache颠簸，可以使用组相联。将cache分为m组相同大小的直接相连cache，即叫做m路组相联。m的数量是一个存储单元可以被映射到的不同cache行的个数（图1-11是一个2路组相联的例子）。在每一次存取中，硬件很少干涉数据应该存储到哪一路cache或者在未命中的情况下哪一路的cache行应该替换。
为了在低延迟和防止颠簸中寻求平衡，系统程序员必须考虑cache层次。最内层的cache(L1)相比于外层cache较少使用组相联。典型组相联的组数在2～48之间。但cache的有效容量还比较小，例如在应用程序中，根据数据流的数目和它们的跨度、相互位移会产生时间、空间局部性，但能有效利用这些局部性的cache部分非常小。
1.3.3 预取
即使引进了cache行以利用空间局部性，可以使cache更有效，但是在第一次不命中时还是会有大量延迟。图1-12是求向量范数内核的例子。
代码中只有一条数据加载流。假设cache行的长度为4，则在三次加载中能在cache中命中，然后就会发生一次cache不命中，这种长延迟会导致内存总线长时间空闲。
增大cache行的长度会减少上述类似的延迟，但是会造成访问模式不稳定而减慢应用程序的执行速度。为了平衡，主流的cache行长度为64～128字节（8～16个双精度浮点数）。到目前为止还会存在较大的类似延迟，所以内存带宽、内存总线利用率较低。假设一个商用系统存储延迟为50ns，带宽为10GB/s，传输一个128字节的cache行需要13ns，则80%的总线带宽没有被使用，此时延迟已经是一个比带宽更重要的问题。
有很多方法可以减少延迟，预取是其中之一。预取是指在应用程序使用数据之前就已经把它们导入cache。通过软流水，编译器会在程序中打乱一些指令，从而让硬件有时间异步地把数据提前导入cache（如图1-13）。这里假设现代系统架构一定程度上能支持异步传输。还有一种方案可以达到预取一样的效果，一些处理器有一个硬件预取器，能够根据数据访问模式提前读取应用程序数据，保持持续的数据流，并提供与预取指令相同的服务。无论处于哪个阶段，必须强调的是预取使用的资源必须由设计进行限制。存储子系统必须能支持一定数量的预取指令（例如正在响应的预取请求），容忍存储流水线的阻塞和不可避免的延迟。我们可以估计为了隐藏所有延迟而预取需要的指令数量，假设T?是延迟，B是带宽，则传输Lc（以字节为单位）需要的时间：
每次cache行传输的时候都需要一次预取操作，处理器需要预取的指令数量是在时间T内能传输的cache行的数量，设为P（见图1-13），则处理器必须：
例如cache行长度为128字节(16个双精度浮点数)，B = 10GB/s，T???=?50ns，则可以得到P≈5。如果没达到这种预取要求，延迟不会完全隐藏，存储带宽也不能完全被利用。另一方面，如果应用程序使用很多高速缓存块数据（这些数据在传输时不能被隐藏）的浮点型操作，执行时间比数据传输的时间明显要长，将不会受到带宽的限制，对存储子系统的压力也不大（3.1节中会介绍合适的高性能模型）。这种情况下，不需要太多指令预取。
严重依赖存储带宽的应用程序可能会给预取机制带来较大压力。可以用一个共享存储总线的协处理器来提供预取功能，减轻带宽的压力（详细请参考1.4节的多核设计）。通常，如果程序具有流模式访存，那么一个好的编程模型应该提供一种更长的持续数据流方法。
最后，有些要注意的地方。图1-12和图1-13强调了指令预取对隐藏延迟的作用，但是带宽的性能限制也不能忽视。即使单个cache行的传输时间主要是传输延迟，预取也不能提高主存带宽。