11.2 多核处理器的访存结构
通用多核处理器采用共享存储结构，其设计存在如下关键问题：
1）片上Cache如何组织？与单核处理器类似，多核处理器需要在片上设置大容量的Cache来缓解芯片计算能力与访存性能之间日益扩大的差距。片上Cache如何组织？Cache结构采用私有还是共享，集中式还是分布式？这些是需要设计者考虑的问题。
2）多个处理器核发出的访存指令次序如何约定？各处理器核并行执行线程（或者进程）发出读/写（load/store）访存指令，这些访问指令的执行次序如何约定，使得应用程序员可以利用这些约定来推理程序的执行结果？存储一致性模型就是用来解决这方面问题的。
3）如何维护Cache数据一致性？一个数据可能同时在多个处理器核的私有Cache中和内存中存在备份，如何保证数据一致性？Cache一致性协议将解决Cache一致性问题。
11.2.1 通用多核处理器的片上Cache结构
片上Cache结构是通用多核处理器设计的重要内容。片上Cache的种类主要有：私有Cache、片上共享Cache、片间共享Cache。图11.1a是私有Cache结构示意图，图11.1b是片上共享Cache结构示意图（由于一级Cache的访问速度对性能影响大，通用多核处理器的一级Cache几乎都是私有的）。私有Cache结构具有较快的访问速度，但是具有较高的失效率。共享Cache结构的访问速度稍慢，但具有失效率低的优点。多处理器芯片间共享Cache结构的访问速度慢，且失效率高，因此并不常用。
图11.1 Cache结构图
目前，主流多核处理器的典型Cache结构是：片内共享最后一级Cache（Last Level Cache，简称LLC），片间共享内存。表11.1列出了典型商用多核处理器的Cache结构参数。处理器核的一级Cache和二级Cache私有，三级Cache（LLC）共享。有些处理器甚至有片外的四级Cache，例如Intel i7处理器。
表11.1 商用多核处理器主要参数示例
在共享LLC结构中，主要有UCA（Uniform Cache Access）和NUCA（Non-Uniform Cache Access）两种。图11.2为共享LLC结构示意图（假设二级Cache为LLC）。
图11.2 共享LLC结构示意图
UCA是一种集中式共享结构，多个处理器核通过总线或者交叉开关连接LLC，所有处理器核对LLC的访问延迟相同。这种集中式的共享LLC，很容易随着处理器核数目的增加成为瓶颈。另外，UCA结构由于使用总线或者交叉开关互连，可扩展性受限。因此，通常在处理器核数较少的多核处理器中采用UCA结构，例如四核龙芯3号处理器。
NUCA是一种分布式共享结构，每个处理器核拥有本地的LLC，并通过片上互连访问其他处理器核的LLC。在NUCA结构中，处理器核可以访问所有的LLC，但是不同位置的LLC具有不同的访问延迟。当工作集较小时，处理器核的本地Cache足够容纳工作集，处理器核只使用本地Cache；当工作集较大时，本地Cache中放不下的数据可以放到远地Cache中。NUCA结构需要高效Cache查找和替换算法，使得在使用远地Cache时不影响性能。NUCA结构中通常采用可扩展的片上互连（如Mesh片上网络等），采用基于目录的Cache一致性协议，具有良好的可扩展性，可以有效支持较多数目的处理器核。因此，在具有较多核数的多核/众核处理器中通常采用NUCA结构，如SPARC M7和龙芯3C5000等。
11.2.2 存储一致性模型
本节简要介绍常见的存储一致性模型。存储一致性模型最初是针对共享存储的多处理器设计提出来的，同样也可以适用于多核处理器设计。本节在介绍存储一致性模型时，处理器（处理机）和处理器核在概念上是可以互用的。
下面举一个存储一致性问题的例子。如图11.3所示，寄存器R1为进程P2的内部寄存器，R2和R3为进程P3的内部寄存器，初始值均为0；变量a、b为P1、P2和P3的共享变量，初始值均为0。
图11.3 共享存储程序片段
在图11.3所示的程序片段中，如果仅要求P1、P2及P3根据指令在程序中出现的次序来执行指令，那么这个程序的访存事件可能按如下次序发生：
1）P1发出存数操作L11；
2）L11到达P2，但由于网络堵塞等原因，L11未到达P3；
3）P2发出取数操作L21取回a的新值；
4）P2发出存数操作L22，且其所存的b新值到达P3；
5）P3发出取数操作L31取回b的新值；
6）P3发出取数操作L32，但由于L11未到达P3，故L32取回a的旧值；
7）L11到达P3。
这是一个程序员难以接受的执行结果。因为从程序员的观点来看，如果L21和L31分别取回a和b的新值，则说明存数操作L11和L22都已完成，L32必然取回a的新值。在此例中，即使每个处理器都根据指令在程序中出现的次序来执行指令，仍然会导致错误的结果。从这个例子可以看出，在共享存储系统中，需要对多处理器的访存操作的次序做出限制，才能保证程序执行的正确。
存储一致性模型是多处理器系统设计者与应用程序员之间的一种约定，它给出了正确编写程序的标准，使得程序员无须考虑具体访存次序就能编写正确程序，而系统设计者则可以根据这个约定来优化设计提高性能。系统设计者通过对各处理器的访存操作完成次序加以必要的约束来满足存储一致性模型的要求。
文献中常见的存储一致性模型包括：顺序一致性模型、处理器一致性模型、弱一致性模型、释放一致性模型等。这些存储一致性模型对访存事件次序的限制不同，因而对程序员的要求以及所能得到的性能也不一样。存储一致性模型对访存事件次序施加的限制越弱，越有利于提高性能，但编程越难。下面介绍具体的存储一致性模型。
1）顺序一致性（Sequential Consistency，简称SC）模型。这种模型是程序员最乐于接受的存储一致性模型，最符合程序员的直觉。对于满足顺序一致性的多处理机中的任一执行，总可以找到同一程序在单机多进程环境下的一个执行与之对应，使得二者结果相等。
为了放松对访存事件次序的限制，人们提出了一系列弱存储一致性模型。这些弱存储一致性模型的基本思想是：在顺序一致性模型中，虽然为了保证正确执行而对访存事件次序施加了严格的限制，但在大多数不会引起访存冲突的情况下，这些限制是多余的，极大地限制了系统优化空间进而影响了系统性能。因此可以让程序员承担部分执行正确性的责任，即在程序中指出需要维护一致性的访存操作，系统只保证在用户指出的需要保持一致性的地方维护数据一致性，而对用户未加说明的部分，可以不考虑处理器之间的数据相关。
2）处理器一致性（Processor Consistency，简称PC）模型。这种模型比顺序一致性模型弱，故对于某些在顺序一致条件下能正确执行的程序，在处理器一致条件下执行时可能会导致错误结果。处理器一致性模型对访存事件发生次序施加的限制是：在任一取数操作load被允许执行之前，所有在同一处理器中先于这一load的取数操作都已完成；在任一存数操作store被允许执行之前，所有在同一处理器中先于这一store的访存操作（包括load和store）都已完成。上述条件允许store之后的load越过store而执行，在实现上很有意义：在Cache命中的load指令写回之后但没有提交之前，如果收到其他处理器对load所访问Cache行的无效请求，load指令可以不用取消，较大地简化了流水线的设计。多核龙芯3号处理器设计中就采用了处理器一致性。
3）弱一致性（Weak Consistency，简称WC）模型。这种模型的主要思想是把同步操作和普通访存操作区分开来，程序员必须用硬件可识别的同步操作把对可写共享单元的访问保护起来，以保证多个处理器对可写共享单元的访问是互斥的。弱一致性模型对访存事件发生次序做如下限制：同步操作的执行满足顺序一致性条件；在任一普通访存操作被允许执行之前，所有在同一处理器中先于这一访存操作的同步操作都已完成；在任一同步操作被允许执行之前，所有在同一处理器中先于这一同步操作的普通访存操作都已完成。上述条件允许在同步操作之间的普通访存操作执行时不用考虑进程之间的相关。虽然弱一致性模型增加了程序员的负担，但它能有效地提高性能。值得指出的是，即使是在顺序一致的共享存储并行程序中，同步操作也是难以避免的，否则程序的行为难以确定。因此，在弱一致性模型的程序中，专门为数据一致性而增加的同步操作不多。
4）释放一致性（Release Consistency，简称RC）模型。这种模型是对弱一致性模型的改进，它把同步操作进一步分成获取操作acquire和释放操作release。acquire用于获取对某些共享存储单元的独占性访问权，而release则用于释放这种访问权。释放一致性模型对访存事件发生次序做如下限制：同步操作的执行满足顺序一致性条件；在任一普通访存操作被允许执行之前，所有在同一处理器中先于这一访存操作的acquire操作都已完成；在任一release操作被允许执行之前，所有在同一处理器中先于这一release的普通访存操作都已完成。
11.2.3 Cache一致性协议
在共享存储的多核处理器中，存在Cache一致性问题，即如何使同一数据块在不同Cache以及主存中的多个备份保持数据一致的问题。具体来说，一个数据块可能在主存和Cache之中保存多份，而不同的处理器核有可能同时读取或者修改这个数据，导致不同的处理器核观察到的数据的值是不同的。Cache一致性协议（Cache Coherence Protocol）是指在共享存储的多处理器或者多核处理器系统中，一种用来保持多个Cache之间以及Cache与主存之间数据一致的机制。人们已经提出了若干Cache一致性协议来解决这个问题。
1.Cache一致性协议的分类
Cache一致性协议的具体作用就是把某个处理器核新写的值传播给其他处理器核以确保所有处理器核看到一致的共享存储内容。从如何传播新值的角度看，Cache一致性协议可分为写无效（Write-Invalidate）（也可称为写使无效）协议与写更新（Write-Update）协议；从新值将会传播给谁的角度看，它可以分为侦听协议与目录协议。Cache一致性协议决定系统为维护一致性所做的具体动作，因而直接影响系统性能。
1）写无效协议与写更新协议。在写无效协议中，当根据一致性要求要把一个处理器核对某一单元所写的值传播给其他处理器核时，就使其他处理器核中该单元的备份无效；其他处理器核随后要用到该单元时，再获得该单元的新值。在写更新协议中，当根据一致性要求要把一个处理器核对某一单元所写的值传播给其他处理器核时，就把该单元的新值传播给所有拥有该单元备份的处理器核，对相应的备份进行更新。
写无效协议的优点是：一旦某处理器核使某一变量在所有其他Cache中的备份无效后，它就取得了对此变量的独占权，随后它可以随意地更新此变量而不必告知其他处理器核，直到其他处理器核请求访问此变量而导致独占权被剥夺。其缺点是：当某变量在一处理器核中的备份变无效后，此处理器核再读此变量时会引起Cache不命中，在一个共享块被多个处理器核频繁访问的情况下会引起所谓的“乒乓”效应，即处理器核之间频繁地互相剥夺对一个共享块的访问权而导致性能严重下降。写更新协议的优点是：一旦某Cache缓存了某一变量，它就一直持有此变量的最新备份，除非此变量被替换掉。其缺点是：写数的处理器核每次都得把所写的值传播给其他处理器核，即使其他处理器核不再使用所写的共享块。写无效协议适用于顺序共享（Sequential Sharing）的程序，即在较长时间内只有一个处理器核访问一个变量；而写更新协议适用于紧密共享（Tight Sharing）的程序，即多个处理器核在一段时间内频繁地访问同一变量。
2）侦听协议与目录协议。侦听协议的基本思想是，当处理器核对共享变量的访问不在Cache命中或可能引起数据不一致时，它就把这一事件广播到所有处理器核。系统中所有处理器核的Cache都侦听广播，当拥有广播中涉及的共享变量的Cache侦听到广播后，就采取相应的维持一致性的行动（如，使本Cache的备份无效、向总线提供数据等）。侦听协议实现较简单，每个处理器核Cache只需要维护状态信息就可以了。侦听协议适合于通过总线互连的多核处理器，因为总线是一种方便而快捷的广播媒介。在写使无效侦听协议中，当一个Cache侦听到其他处理器核欲写某一单元且自己持有此单元的备份时，就使这一备份无效以保持数据一致性；在写更新侦听协议中，当一个Cache侦听到自己持有备份的某一共享单元的内容被其他处理器核所更新时，就根据侦听到的内容更新此备份的值。
由于侦听协议需要广播，因此只适用于共享总线结构。总线是一种独占式资源，且总线延迟随所连接的处理器核数目的增加而增加，存在可伸缩性差的问题。在采用片上网络互连的多核处理器中通常使用基于目录的Cache一致性协议。目录协议的主要思想是，为每一存储行维持一目录项，该目录项记录所有当前持有此行备份的处理器核号以及此行是否已被改写等信息。当一个处理器核欲往某一存储行写数且可能引起数据不一致时，它就根据目录的内容只向持有此行的备份的那些处理器核发出写使无效/写更新信号，从而避免了广播。典型的目录组织方式为位向量目录。位向量目录中的每一目录项有一个n位的向量，其中n是系统中处理器核的个数。位向量中第i位为“1”表示此存储行在第i个处理器核中有备份。每一目录项还有一改写位，当改写位为“1”时表示某处理器核独占并已改写此行。位向量目录的缺点是，所需的目录存储器容量随处理器核数n以及共享存储容量m的增加以O（mn）的速度增加，有较大存储开销。
2.Cache状态
Cache一致性协议的实现方式为：在Cache中每一个Cache行设置一致性状态来记录该Cache行的读写状态，确保Cache行不会被多个处理器核同时修改。Cache行的一致性状态的实现有多种具体形式，如最简单的三状态ESI，较为常见的MESI及其变种MOESI等。
ESI是指Cache行的三种一致性状态：E（Exclusive，独占），S（Shared，共享），I（Invalid，无效）。Invalid状态表示当前Cache行是无效的，对其进行任何读写操作都会引发缓存缺失（Cache Miss）。Shared状态表明当前Cache行可能被多个处理器核共享，只能读取，不能写入，对其写入也会引发缓存缺失。Exclusive状态表明对应Cache行被当前处理器核独占，该处理器核可以任意读写这个Cache行，而其他处理器核如果想读写这个Cache行需要请求占有这个Cache行的处理器核释放该Cache行。图11.4给出了三个状态之间的转换关系。
图11.4 三状态Cache一致性协议状态转换图
MESI在ESI的基础上增加了M（Modified，修改）状态。其中Shared状态和Invalid状态和ESI的完全一样，而Exclusive状态表示当前Cache块虽然被当前处理器核独占，但是还没有被修改，与内存中的数据保持一致，如果处理器核想将其替换出去，并不需要将该Cache行写回内存。Modified状态表示当前Cache行被当前处理器核独占并且已经被修改过了，如果处理器核想替换该Cache行，需要将该Cache行写回内存。与ESI协议相比，增加一个Modified状态的优点是减少了Cache到内存的数据传输次数，Cache只需要将Modified状态的Cache行写回内存。
下面通过一个写无效的位向量目录协议例子简单说明Cache一致性协议的工作原理。通常，一个Cache一致性协议应包括以下三方面的内容：Cache行状态、存储行状态以及为保持Cache一致性的状态转化规则。
该协议采用ESI实现，Cache的每一行都有三种状态：无效状态（INV）、共享状态（SHD）以及独占状态（EXC）。在存储器中，每一行都有一相应的目录项。每一目录项有一n位的向量，其中n是系统中处理器核的个数。位向量中第i位为“1”表示此存储行在第i个处理器核Pi中有备份。此外，每一目录项有一改写位，当改写位为“1”时，表示某处理器核独占并已改写此行，相应的存储行处于DIRTY状态；否则相应的存储行处于CLEAN状态。
当处理器核Pi发出一取数操作“LOAD x”时，根据x在Cache和存储器中的不同状态采取如下不同的操作：若x在Pi的Cache中处于共享或独占状态，则取数操作“LOAD x”在Cache命中。若x在Pi的Cache中处于无效状态，那么这个处理器核向存储器发出一个读数请求read（x）。存储器在收到这个read（x）后查找与单元x相对应的目录项，如果目录项的内容显示出x所在的存储行处于CLEAN状态（改写位为“0”），即x在存储器的内容是有效的，那么存储器向发出请求的处理器核Pi发出读数应答rdack（x）提供x所在行的一个有效备份，并把目录项中位向量的第i位置为“1”；如果目录项的内容显示出x所在的存储行已被某个处理器核Pk改写（改写位为“1”），那么存储器向Pk发出一个写回请求wtbk（x），Pk在收到wtbk（x）后，把x在Cache的备份从独占状态（EXC）改为共享状态（SHD），并向存储器发出写回应答wback（x）提供x所在行的一个有效备份，存储器收到来自Pk的wback（x）后向发出请求的处理器核Pi发出读数应答rdack（x）提供x所在行的一个有效备份，把目录项中的改写位置为“0”并把位向量的第i位置为“1”。如果x不在Pi的Cache中，那么Pi先从Cache中替换掉一行再向存储器发出一个读数请求read（x）。
当处理器核Pi发出一存数操作“STORE x”时，根据x在Cache和存储器中的不同状态采取如下不同的操作：若x在Pi的Cache中处于独占状态，则存数操作“STORE x”在Cache命中。若x在Pi的Cache中处于共享状态，那么这个处理器核向存储器发出一个写数请求write（x），存储器在收到这个write（x）后查找与单元x相对应的目录项，如果目录项的内容显示出x所在的存储行处于CLEAN状态（改写位为“0”），并没有被其他处理器核所共享（位向量中所有位都为“0”），那么存储器向发出请求的处理器核Pi发出写数应答wtack（x）表示允许Pi独占x所在行，把目录项中的改写位置为“1”并把位向量的第i位置为“1”；如果目录项的内容显示出x所在的存储行处于CLEAN状态（改写位为“0”），并且在其他处理器核中有共享备份（位向量中有些位为“1”），那么存储器根据位向量的内容向所有持有x的共享备份的处理器核发出一个使无效信号invld（x），持有x的有效备份的处理器核在收到invld（x）后把x在Cache的备份从共享状态（SHD）改为无效状态（INV），并向存储器发出使无效应答invack（x），存储器收到所有invack（x）后向发出请求的处理器核Pi发出写数应答wtack（x），把目录项中的改写位置为“1”并把位向量的第i位置为“1”，其他位清“0”。若x在Pi的Cache中处于无效状态，那么这个处理器核向存储器发出一个写数请求write（x），存储器在收到这个write（x）后查找与单元x相对应的目录项，如果目录项的内容显示出x所在的存储行处于CLEAN状态（改写位为“0”），并没有被其他处理器核所共享（位向量中所有位都为“0”），那么存储器向发出请求的处理器核Pi发出写数应答wtack（x）提供x所在行的一个有效备份，把目录项中的改写位置为“1”，并把位向量的第i位置为“1”；如果目录项的内容显示出x所在的存储行处于CLEAN状态（改写位为“0”），并且在其他处理器核中有共享备份（位向量中有些位为“1”），那么存储器根据位向量的内容向所有持有x的共享备份的处理器核发出一个使无效信号invld（x），持有x的有效备份的处理器核在收到invld（x）后，把x在Cache的备份从共享状态（SHD）改为无效状态（INV），并向存储器发出使无效应答invack（x），存储器收到所有invack（x）后向发出请求的处理器核Pi发出写数应答wtack（x）提供x所在行的一个有效备份，把目录项中的改写位置为“1”并把位向量的第i位置为“1”，其他位清“0”；如果目录项的内容显示出x所在的存储行已被某个处理器核Pk改写（改写位为“1”，位向量第k位为“1”），那么存储器向Pk发出一个使无效并写回请求invwb（x），Pk在收到invwb（x）后把x在Cache的备份从独占状态（EXC）改为无效状态（INV），并向存储器发出使无效并写回应答invwback（x）提供x所在行的有效备份，存储器收到来自Pk的invwback（x）后向发出请求的处理器核Pi发出写数应答wtack（x）提供x所在行的一个有效备份，把目录项中的改写位置为“1”，并把位向量的第i位置为“1”，其他位清“0”。如果x不在Pi的Cache中，那么Pi先从Cache中替换掉一行再向存储器发出一个写数请求write（x）。
如果某处理器核要替换一Cache行且被替换行处在EXC状态，那么这个处理器核需要向存储器发出一个替换请求rep（x）把被替换掉的行写回存储器。
假设单元x初始时在存储器中处于CLEAN状态（改写位为“0”），并被处理器核Pj和Pk所共享（在Pj和Pk的Cache中处于SHD状态），如图11.5a所示。接着x被多个处理器核按如下次序访问：处理器核Pi发出存数操作“STORE x”，处理器核Pk发出存数操作“STORE x”，处理器核Pi发出取数操作“LOAD x”，处理器Pj发出取数操作“LOAD x”。图11.5b～f显示出上述访问序列引起的一系列消息传递，以及x在Cache及在存储器中的状态的转化过程。
图11.5 基于目录的写无效Cache一致性协议