Mechanical Sympathy 系列翻译 (CPU Cache Flushing Fallacy)

 前言：

    由于最近在学习LMAX Disruptor， 它是一个高效的并发框架，里面涉及到许多底层的并发话题，后来在http://mechanical-sympathy.blogspot.com/这个博客上，发现很多很好的文章。于是起心翻译之，一来借翻译加深学习印象，二来推广之。。

 

    Mechanical Sympathy   这个短语非常有意思，直译过来是Mechanical是机械的意思，Sympathy是同情的意思，在这里表示硬件的运作方式，以及与硬件运行方式协同的软件编程。。。

 

下面是文章正文：

CPU 缓存刷新的谬误（CPU Cache Flushing Fallacy）

    即使是有丰富经验的技术人员，我也经常听到谈论某些操作会导致CPU缓存“刷新”。 这似乎可以说是一个对CPU缓存的工作原理，以及CPU缓存子系统和内核如何进行交互很常见的谬误。 在这篇文章中，我将试图解释CPU缓存履行的核心功能，内核如何执行我们的程序，以及它们如何进行交互。 作为一个具体的例子，我将深入介绍最新的intl x86服务器的CPU， 其它CPU使用技术类似。 

 

 

    即是是最现代的系统，也是多处理器共享内存设计。 一个共享的内存系统由一个内存资源组成，可以供2个或更多独立的CPU内核访问。 主内存的延迟往往是很高的，从10到100纳秒不等。 一个3.0GHz的CPU在100ns可以处理多达1200条指令。 每个Sandy Bridge（译者注：Intel推出代号为Sandy Bridge的处理器）内核在每个周期（IPC）可以并行执行多达4个指令。 CPU采用缓存子系统来降低延迟，提高处理指令的能力。 这些缓存有的是容量小，速度快，而且每个内核独立，有的则速度稍慢，容量更大，多内核共享。 这些缓存和寄存器，主内存，构成我们非持久性存储器的层次结构。 

 

    将来，如果你在开发一个重要的算法，需要牢记，一次缓存失效约等于失去执行500 CPU指令机会！ 这还只是一款单插槽系统，一个多插槽系统可能失去机会增加一倍，因为请求的内存可能是在交叉互连的另一个插槽上。 

 

存储器层次结构 ：

  在2012年的Sandy Bridge E级服务器的内存层次结构可以分解为如下： 

1. 寄存器 ：在每个内核独立寄存器空间，包含160个integer和144个float空间。 这些寄存器的访问都在一个周期内，是提供给我们执行内核最快的内存空间。 编译器通常将这些寄存器分配给局部变量和函数参数。 编译器分配知道的寄存器体系的寄存器的子系统 ，然后通过硬件的扩展，可以并行的或者无序的运行指令。 对于给定的处理器，编译器是知道它有的无序和并行执行能力，并且通过调整指令流顺序和分配寄存器来利用这种能力。 当启用超线程（hyperthreading）时，这些寄存器可以在同地协作的超线程（co-located hyperthreads）共享。
2. 内存排序缓冲器（MOB）：MOB是由64个load指令和36个store指令的缓冲区组成。 当缓存子系统无序的执行指令的时候，这些缓冲区用于跟踪这些“飞行中”的操作。 你可以把store缓冲区完全想象为一个队列，它可以搜索store操作是否存在，这个操作已经排队等待L1高速缓存。 当数据异步的在高速缓存子系统中传输，这些缓冲区使我们可以更快的处理数据。 当处理器发出异步读写，然后得到一个无序的结果。 MOB对它们进行区分的store和load的顺序，以符合内存模型 。 指令可以无序的执行再加上我们的store和load也是无序的获取结果从高速缓存子系统。 这些缓冲区可以重建一个符合存储器模型预期的顺序。
3. 1级缓存（Level 1 Cache） ：L1缓存是一个内核独立的缓存，分为独立的32K的数据和32K的指令缓存。 访问时间为3个时钟周期，如果数据已经被内核加载到L1缓存，指令也透明的加载。
4. 2级高速缓存（Level 2 Cache） ：L2缓存页是内核独立的缓存，处于L1和共享的L3高速缓存缓冲区之间。 大小为256K，和作为L1和L3之间的一个高效的队列。 L2既存储数据也存储指令。 L2访问延迟为12个周期。
5. 3级高速缓存（Level 3 Cache） ：L3缓存是同插槽内所有的内核共享的缓存。 L3被分成一个一个的segment，每个segment为2MB， 在插槽里通过环形总线（ring-bus ）链接。 每个内行人也通过该环形总线连接。 地址通过hash到各个segment，提供更大的吞吐量。 根据高速缓存大小,延迟可长达38个周期 。 高速缓存大小根据segment的数量可高达20MB，每额外通过ring一次就会增加一个额外的周期。 L3缓存的数据包含在同一个插座上的每个核心的L1和L2中的所有数据。 这种包容性，空间的价值在于，使得L3缓存可以拦截请求，从而消除了内核私有的L1＆L2高速缓存的负担。
6. 主内存（Main Memory） ：DRAM通道连接到每个插槽，在所有cache失效后，插槽内的访问平均延迟约为65ns。 然而，这是非常不可控的，因为大量排队影响和存储器刷新周期冲突，后续访问中很少能命中同一行的缓存。 为了提高吞吐量，每个插槽上的4个内存通道聚集在一起，并通过独立内存通道的流水线来减低延迟。
7. NUMA：在一个多插槽服务器，我们有非统一内存访问 （non-uniform memory access）。 之所以是不均匀的，是因为所需的存储，也许在远程插槽上，必须通过QPI总线，花费一个额外的40ns访问。 Sandy Bridge通过Westmere和Nehalem为双插槽系统迈进了一大步。 随着Sandy Bridge的的QPI限制已被从6.4GT / s提高到8.0GT / s，并可以合并两通道，从而消除了以前的系统瓶颈。

关联性水平（Associativity Levels）

     Caches 是基于硬件的高效的哈希表。 哈希函数通常是简单的屏蔽一些低序位缓存索引。 哈希表需要一些手段来处理相同的插槽碰撞。 关联性水平是一个插槽或者叫set的hash值可能出现在cache中插槽的数量。 关联性水平确定与存储更多的数据和搜索每个数据的时间和请求之间的权衡。

     对于Sandy Bridge的L1D和L2，L3是8路关联12路相联的。

 

译者注：具体参见 http://en.wikipedia.org/wiki/Cache_memory

 

缓存一致性 （Cache Coherence）

     随着一些内核独立缓存的出现，我们需要一种方法来保持一致的，即是所有内核都可以有一个一致的内存试图。 主内存被认为是高速缓存子系统的“真相源头”。 如果内存从缓存中获取，它是永远不会过时的。当数据存在于缓存和主内存中，缓存的数据是一个主副本。 这种风格的内存管理被称为回写模式（write-back），在数据更新时只写入缓存Cache，只在数据被替换出缓存时，被修改的缓存数据才会被写到后端存储。 基于x86的缓存数据块的大小是64字节，称为缓存行（cache-line）。 其他处理器可以使用不同大小的缓存行。 一个较大的缓存行在增加的带宽是非常昂贵的时候可以有效的减少延迟。 

     

     为了保持缓存一致性，缓存控制器跟踪每个高速缓存行的状态，作为一个有限数量的状态集。intel使用MESIF协议 ，AMD采用一个变种叫MOESI 。 MESIF协议下每个缓存行可以处在以下5种状态： 

1. 被修改 ：表示高速缓存行是脏的，在稍后阶段必须写回内存。 当写回主内存的状态后转换为独占。
2. 独占 ：表示高速缓存行独占，并且和主内存保持一致。 当写入数据后，然后转换为修改状态。 要达到这个状态，需要发送一个请求所有权（RFO）消息，这涉及到一个只读加上一个对所有其他副本失效的广播。
3. 共享 ：表示与主内存保持一致的一个干净的副本。
4. 无效 ：表示未使用的缓存行。
5. 转发 ：表示一个共享状态下的一个特色版本，这是指定的NUMA系统中的其他缓存的缓存。

    从一种状态过渡到另一种之间，在缓存之间一系列的消息被发送，去影响状态的变化。 在英特尔Nehalem和AMD Opteron处理器之前，在插槽之间的缓存一致性信号必须共享内存总线，这极大地限制的可扩展性。 这时候内存控制器之间的通信是在一个单独的总线。 在英特尔的QPI和AMD 的HyperTransport，总线被用于保持插槽间缓存一致性。 

 

     缓冲控制器是存在在每一个L3缓存segment里的一个模块，通过插槽的环形总线（ring-bus ）链接。 每个内核，L3缓存segment，QPI控制器，​​内存控制器和集成图形子系统都是通过这个环形总线连接。环形总线有4个独立的通道：请求时 ， 监听 ， 确认 ，每个周期32个字节的数据。L3的包容性是指任何在缓存L1或L2的数据也保持在了L3缓存中。 这通过监听变化，快速识别内核中修改的行来提供。 L3的segment缓存控制器跟踪记录每一个内核自己对缓存行（cache-line ）的修改版本。

 

    如果一个内核要读一些内存，并没有在一个共享，独占或修改的状态，它必须通过环形总线读取。如果没有在缓存子系统它页必须从主内存读取，或者读取L3，如果是干净的，或者需要监听另一个内核的修改。 在任何情况下读取从缓存子系统将永远不会返回一个陈旧的副本，它是保证是一致的。 

 

并行编程 （Concurrent Programming）

     如果我们的缓存总是一致的，那么为什么我们在编写并发程序时担心的可见性？ 这是因为在我们的内核中，为了追求更高的性能，数据的修改对于其他线程是无序的。 主要有2个原因。 

 

    首先，出于性能方面的考虑，我们的编译器可以生成程序寄存器，在相当长的一段时间内用于存储一个变量，如反复使用的变量在一个循环中。 如果我们需要这些变量在多个内核是可见的，然后更新必须是寄存器分配。 在C语言中通过声明一个变量为“ volatile ” 实现。 要注意的是C / C + + 的volatile还不足以告诉编译器不可重新排序其他指令。 如果需要这个功能，你需要的内存栅栏（ memory fences）/屏障（barriers.）。 

 

    第二个主要的问题是指令重拍，一个线程写一个变量，然后在很短的时间后读取，可能看到的是它在缓存中的老值。在单一的Writer算法（Single Writer Principle）里这是永远不会发生，但对于类似  Dekker 和 Peterson 锁定算法里这将是一个问题。 为了解决这个问题，确保最新值是可见的，线程必须不能加载本地缓存中。 这可以通过一个发出一个fence 指令，防止后续的load指令在另外一个线程执行store指令之间得到执行 。量在Java中申明的volatile 变量，永远不会分配到寄存器，它伴随着一个完整的fence 指令。因为在x86上fence 指令会暂停线程直到store的缓存写回内存， 所以会影响性能。 其它处理器上fence 指令能有更有效的实现，简单地在缓存放置一个标记，标记搜索边界。如Azul Vega这样实现的。 

 

    当尊 Single Writer Principle得到时候，如果你想确保整个Java线程的内存顺序，并避免存储栅栏（store fence），可以使用j.u.c.Atomic(Int|Long|Reference).lazySet()，而不是设置一个volatile变量。 

 

谬论 

     回到作为并发算法的一部分的“刷新缓存”谬论，。 我认为我们可以有把握地说，我们从来没有在我们的用户空间程序里“刷新”CPU缓存。 我相信这个谬论的来源是因为在某些类别的并行算法中需要对缓存刷新，标记或漏一个点，以便在随后load操作中可以观察到的最新值。 为此，我们需要一个内存排序栅栏（memory ordering fence ），而不是缓存刷新。 

 

    这一谬误的另一个可能的来源是L1缓存，或TLB ，可能需要根据地址索引策略在上下文切换时被刷新。 ARM，之前的ARMv6，在TLB中没有使用的地址空间标记，因此上下文切换是要求整个的L1缓存刷新。 许多处理器的L1的指令缓存的刷新出于同样的原因，在许多情况下，这仅仅是因为指令缓存不须保持一致。 底线是，上下文切换是昂贵的，这有点偏离主题。另外的L2缓存污染，上下文切换，也会引起的TLB和/L1缓存刷新。 Intel x86处理器在上下文切换只需要TLB刷新。

 

 

 

 

 

 

 

原文地址：http://mechanical-sympathy.blogspot.com/2013/02/cpu-cache-flushing-fallacy.html

 

 

本站支持 pay for your wishes