第四章 多处理器和线程级并行

第四章多处理器和线程级并行

4.1

简介4.2对称式共享存储器系统结构4.3对称式共享存储器多处理器的性能4.4分布式共享存储器和基于目录的一致性4.1简介并行系统结构的分类

1966年，Michael.J.Flynn提出根据多处理器中限制要求最多的单元中的指令所调用的数据流和指令流的并行度，把所有的计算机归为四类：

1、单指令流，单数据流（SISD）：单处理器

2、单指令流，多数据流（SIMD）：同一条指令被多个使用不同数据流的多处理器执行。SIMD计算机通过将相同的操作以并行的方式应用于数据的各个项来实现数据级的并行。每个处理器有自己的数据存储器（因此是多种数据），但系统中有唯一的指令存储器和控制处理器，用来获取和分配指令。3、多指令流，单数据流（MISD）：至今还没有这种类型的商用机器。4、多指令流，多数据流（

MIMD）：每个处理器取自己的指令并对自己的数据进行操作。MIMD计算机实现线程级并行，因为多个线程是按并行操作。一般来说，这种线程级并行比数据级并行更加灵活，因此用途更为广泛。从20世纪90年代开始，单芯片日益增长的容量允许设计者将多个处理器设计在一块单独的晶片上。这种方法一开始称为片内多处理器或单芯片多处理器，现在称为多核，这个名字来自于在单独一个晶片上设计多个处理器内核的方法。在这样的设计中，多个内核共享一些资源，比如二级或三级Cache、存储器和I/O总线。

对于MIMD，每个处理器执行自己的指令流。在许多情况下，每个处理器运行不同的进程。进程是可以独立运行的一段代码，进程的状态包含了处理器运行这个程序的所有必要信息。在一个多道程序环境中，各个处理器可能执行相互独立的任务，因此，每个进程与在其他处理器上执行的进程不相关。让多个处理器执行同一个程序并且共享程序的代码和地址空间也是十分有效的。用这种方式共享代码和地址空间的多个进程，通常称之为线程。现在，线程经常用来指运行在不同处理器上的多个执行过程，即便它们并没有共享同一地址空间。例如，多线程的系统结构实际上允许不同地址空间上的多个进程同时执行，而且也允许共享地址空间上的多个线程同时运行。根据存储器组织方式将现有的MIMD机器分为两类：第一种类型为集中式共享存储器系统结构。由于只有单一存储器，它对每个处理器而言都是对等的，并且每个处理器的访问时间相同，这种多处理器系统也称为对成（共享存储器）多处理器系统（SMPs），这种系统结构也称为均匀存储器访问（UMA），这是因为所有的处理器访问存储器都有相同的时延，即使存储器是按多组方式组织的。

集中式共享存储器系统结构有三个特点：1、处理器数量不大——从而所有处理器可共享一个集中式存储器，处理器和存储器通过总线互连。2、采用大容量Cache——可使采用单一总线和单一存储器满足数目不多处理器对存储器的要求。3、每一处理器访问存储器的时间是相等的。集中式共享存储器的基本结构分布式存储器多处理器特点：存储器分布于各节点中，所有节点通过网络互连。访问可以是本地的，也可是远程的；可以不支持cache一致性协议，规定共享数据不进入cache，仅私有数据才保存在cache中。分布式存储器多处理器的基本结构图第二种类型的多处理器的存储器在物理上是分布的

将存储器分布在各个节点上有两个主要的好处:

第一，如果大部分访问是在节点内的本地存储器中进行的，这样做是增大存储器比较经济的方法。第二，缩短了本地存储器访问的时延。在处理器变得越来越快并要求存储器带宽更高以及存储器时延更低的情况下，这两个优点使得这种方法在构建较少处理器的系统时颇具吸引力。分布式存储器系统结构的主要缺点是由于处理器不再共享单一集中存储器，处理器间的数据通信在某种程度上变得更加复杂，且时延也更大。通信和存储器系统结构模型如前所述，大规模多处理器系统结构使用与各个处理器分布在一起的多个存储器。根据处理器间传递数据所用的方法，有两种不同的系统结构。第一种方法通过共享的地址空间进行通信。物理上分开的存储器能够作为逻辑上共享的地址空间进行寻址，就是说只要有正确的访问权限，任何一个处理器都能够通过引用地址的方式访问任意节点上的存储器。这类机器称为分布式共享存储器（DSN）系统。所谓共享存储器指的是共享寻址空间，就是说，两个处理器中相同的物理地址指向存储器中的同一位置。共享存储器并不是说有一个单一的、集中式的存储器。与对称式共享存储器多处理器——也称UMA（均匀存储器访问）相比，DSN多处理器由于访问时间取决于数据字在存储中的位置，因而也称为NUMA（非均匀存储器访问）。

另外一种地址空间由多个私有的地址空间组成，这些私有地址空间在逻辑上是分散的，并且不能被远程处理器寻址。在这种机器中，两个不同处理器中相同的物理地址分别指向两个不同存储器中的不同位置。每个处理器-存储器模块本质上是一台独立的计算机。最初，这种计算机由不同的处理节点和专用的互连网络组成。目前，这种类型的大多数设计实际上就是集群。

每一种地址空间组织方式都有相应的通信机制。对于共享地址空间的机器，可以利用地址空间通过load和store操作隐式地传递数据；所谓的共享存储器就是由此得名的。对于有多个寻址空间的多处理器系统，数据通信通过显式地在处理器间传送消息来完成。因此，这类机器经常称为消息传递多处理器系统，集群就是使用消息传递的一类系统。并行处理遇到的挑战

多处理器的应用非常广泛，不论是运行相互之间没有通信的独立任务，还是必须通过线程通信才能完成的并行程序，都可以应用多处理器。然而，有两个障碍使得并行处理的应用遇到了挑战。这两个障碍都可以用Amdahl定律解释。障碍的难易程度是由应用和系统结构共同决定的。第一个障碍是程序可获得的并行度是有限的。第二个障碍来自于通信相对较高的开销。只能获得有限的并行度使得并行处理器很难得到较高的性价比，正如下面的例子所示。

例题：假设要用100个处理器获得80倍的加速比。那么原来的计算中串行部分该占多大比例呢？解答：Amdahl定律是

加速比=

为简单起见，在本例中假设程序仅有两种执行模式：一种是使用所有处理器的并行模式，也就是改进模式，另一种是仅利用一个处理器的串行模式。在这种简化下，改进部分的加速比就简化为处理器个数，而改进模式所占的比例就是在并行模式中花费的时间。代入上面的公式

1改进部分所占比例改进部分的加速比+（1-改进部分所占比例）

对等式简化得到

0.8*并行部分所占比例+80*（1-并行部分所占比例）=1

80-79.2*并行部分所占比例=1

并行部分所占比例=

并行部分所占比例=0.9975

因此要用100个处理器得到80的加速比，原程序只能有0.25%的部分是串行的。当然，要得到线性加速比（即用n个处理器得到加速比为n)，整个程序必须没有串行部分，全部是并行的。实际上，程序并不只是在完全并行或串行的模式下运行，通常并行模式中并没有使用全部的处理器，而仅仅使用了一部分处理器。第二个主要挑战与并行处理器中远程访问的时延较长有关。现有共享存储多处理器中，处理器间的数据通信少则花费50个时钟周期（多核），多则超过1000个时钟周期（大规模多处理器），时间的长短由通信机制、互连网络的类型和多处理器的规模决定。长通信时延的影响非常之大，让我们来看一个简单的例子。

1并行部分所占比例100+（1-并行部分所占比例）80-179.280=例题：假设有一个应用程序在一台32个处理器系统上运行，该处理器访问一个远程存储器需要200ns。对于这个应用，假设除了涉及通信的存储器访问外，所有的访问都命中本地存储系统（这样假设有点乐观）。执行远程访问时处理器会阻塞，处理器的时钟频率为2GHz。如果基本CPI（假设所有的访问命中Cache）是0.5，那么多处理器在没有远程访问时比只有0.2%的指令涉及远程访问时能快多少？解答：首先计算CPI，有0.2%远程访问的多处理器的CPI是

CPI=基本CPI+远程请求率*远程请求开销

=0.5+0.2%*远程请求开销远程请求开销是

远程请求开销周期时间=200ns0.5ns=400周期

然后我们可以计算CPI:CPI=0.5+0.8=1.3

全部为本地调用的多处理器将会快1.5/0.3=2.6倍。

问题的解决并行性不足：采用并行性更好的算法远程访问延迟的降低：靠体系结构支持和编程技术

4.2对称式共享存储器系统结构

对称式共享存储器系统支持共享和私有数据的缓存。私有数据被单个处理器使用，而共享数据则被多个处理器使用，基本上是通过读写共享数据完成处理器间的通信。把一个私有数据缓存之后，对该数据的访问就可以在Cache中进行，这样就减少了平均访问时间和对存储器带宽的需求。因为没有其他处理器使用这些数据，程序的行为与单存储器系统相同。当共享数据装载到Cache中时，会在多个Cache中形成副本。这样做除了会减少访问时延和降低对存储器带宽的要求外，还能减少多个处理器同时读取共享数据时的竞争现象。然而，把共享数据放入Cache又出现了一个新的问题：Cache一致性。

什么是多处理器的Cache一致性

缓存共享数据带来了一个新的问题，这是因为两个不同的处理器所保存的存储器视图是通过各自的Cache得到的，如果没有其他的防范措施，则会导致两个处理器分别得到两个不同的值。下图说明了这个问题，并解释了为什么两个不同的处理器对存储器相同位置进行操作会得到不同的数值，这个问题常常称为Cache一致性问题。时间事件处理器A的Cache内容处理器B的Cache内容存储器位置X的内容011A读X112B读X1113A向X写入0010Cache一致性问题

如果一个存储器系统满足如下条件，那么认为该存储器系统是一致的：

1、处理器P对地址X的写操作后面紧跟着处理器P对X的读操作，而且在这次读操作和写操作之间没有其他处理器对X进行写操作，这时读操作总是返回P写入的数值。

2、在其他处理器对X的写操作后，处理器P对X执行读操作，这两个操作之间有足够的间隔而且没有其他处理器对X进行写操作，这时，读操作返回的是写入的数值。3、在同一个地址的写操作是串行执行的；也就是说，任何两个处理器对同一个地址的两个写操作在所有处理器看来都有相同的顺序。例如，如果向同一个地址中先写入数值1和数值2，处理器决不会从该地址中先读出2再读出1。

第一个性质是为了保证程序的顺序——即使在单处理器中也要保证这个性质。第二个性质定义了什么意味着有一个一致性的视图；如果一个处理器对某个数据项执行读操作时，总是读入旧的数值，我们就认为这个存储器是非一致的。

将写操作串行化，这样对同一个地址的写操作在所有处理器看来就具有形同的顺序，这个性质成为写串行化。存储器连贯性模型定义了写入的数值必须在什么时候才能被读操作读出的问题。假设：直到所有的处理器均看到了写的结果，一次写操作才算完成；允许处理器无序读，但必须以程序规定的顺序进行写。实施一致性的基本方案

在一致的多处理机中，Cache提供两种功能：

（1）共享数据的迁移降低了对远程共享数据的访问延迟。

（2）共享数据的复制不仅降低了访存的延迟，也减少了访问共享数据所产生的冲突。小规模多处理机不是采用软件而是采用硬件技术实现Cache一致性。

实现cache一致性协议的关键是跟踪每一个共享数据块的状态。有两种协议分别使用不同的技术跟踪共享状态：

1、基本目录的协议－－物理存储器内数据块的共享状态只保留在一个称为目录的地方。

2、监听协议－－包含有物理存储器数据块的备份的cache也含有该数据块的共享状态的备份，即不集中保存状态。Cache通常连在一条共享存储器总线上，所有cache控制器监控或监听总线以确定它是否含有总线上请求的数据块的一个备份。两种监听协议（1）写无效协议在处理器写数据项之前保证该处理器能独占地访问数据项。因为它在执行写操作时要使其他副本无效。而且这种协议是到目前为止在监听和目录方案中最常用的协议。独占访问确保写操作执行后不存在其他可读或可写的数据项副本：Cache中该数据项的所有其他副本都是无效的。

处理器活动总线活动处理器A的cache活动处理器B的cache内容存储器X位置cache的内容0处理器A读XCache缺失于X00处理器B读XCache缺失于X000处理器A向X写1对X无效10处理器B读XCache缺失于X111监听总线方式的写无效协议实例（2）写更新或写广播协议写入数据项时更新该数据项所有的副本。因为写更新协议必须将所有的写操作广播给共享cache，所以需要更大的带宽。由于这个原因，所有近期的多处理器都选择执行写无效协议。

(3)写更新和写无效协议性能上的差别主要来自：

对同一数据的多个写而中间无读操作的情况，写更新协议需进行多次写广播操作，而在写无效协议下只需一次作废操作。对同一块中多个字进行写，写更新协议对每个字的写均要进行一次广播，而在写无效协议下仅在对本块第一次写时进行作废操作。从一个处理器写到另一个处理器读之间的延迟通常在写更新式中较低。而在写无效协议中，需要读一个新的拷贝。基本实现技术在小规模多处理器系统中实现写无效协议的关键是使用总线或其他广播媒介来完成无效操作。要实现无效操作，处理器只要取得总线控制权然后在总线上广播无效数据的地址即可。所有的处理器都要不断地监听总线来监测地址。处理器要检查各自的cache中是否有总线上广播的地址。如果有，则cache中相应的数据要置位无效。

除了要使执行写操作的Cache数据块的副本无效外，还需要在Cache缺失时对数据项进行定位。

写直达Cache：查找数据项的最新值非常容易，因为所有写的数据同时被写回存储器中，则从存储器中总可以取到最新的数据值。对于写回Cache：得到数据的最新值会困难一些，因为最新值可能在某个Cache中，也可能在存储器中。写回式Cache能够使用同样的监听方案来处理Cache缺失和写操作：所有处理器都要监听总线上的每个地址。如果一个处理器发现它留有被请求的Cache块的一个脏副本，它会对读操作做出响应，提供这个Cache块，并中断对存储器的访问。额外的复杂性来自于从处理器Cache中重新找回Cache块，如果处理器是在彼此独立的芯片上，那么这个时间通常要比从共享存储器中找回Cache块的时间长。因为写回式Cache对存储器带宽的要求较低，而且支持更多更快的处理器。

可以利用Cache中已有的标识位来实现监听过程。其中数据块的有效位使得实现无效操作更加容易。无论是由无效操作还是由其它的事件导致的读操作失败，都可以通过监听总线来直接解决。对于写操作，需要知道其他Cache中是否存有该数据块的副本。这是因为如果没有其他副本，则在写回式Cache中就不用将写操作放在总线上。不发送写操作能够节省时间和带宽。

要跟踪一个Cache数据块是否能被共享，需要为每一个数据块再增加一个状态位，就像有效位和脏数据位一样。增加标志该数据块是否被共享的状态位之后，执行写操作时就可以据此来判定是否需要发送无效操作。党对共享的数据块执行写操作时，Cache会在总线上发送一个无效操作并且把该数据块标记为私有。之后，处理器就不会再发送该数据块的无效操作了。拥有Cache唯一一个副本的处理器通常称为该Cache块的所有者。

当发送无效操作时，所有者的Cache块从共享状态变为非共享（或独占）状态。如果稍后其它处理器请求这个Cache块，那么它会再次变成共享状态。因为Cache对总线的监听同样可以观测到缺失的现象，所以它能够发现其他处理器请求独占Cache的情况，并且会把状态设置成共享。因为每次总线任务均要检查Cache的地址位，这可能与CPU对Cache的访问冲突。可通过下列两种技术之一降低冲突：

(1)复制标识

(2)在多级Cache中是将监听请求转给二级Cache监听协议范例

MESI属于写无效协议，它根据所有的读、写、命中、不命中和在总线上监听的事件来跟踪Cache数据块的状态。数据Cache中所有数据块有以下几种状态之一：

（1）无效状态：这是Cache复位后的初始状态，或该Cache块由于与另一个Cache共享而发生了此Cache块拷贝在另一个Cache的写命令中，导致本地Cache块变为无效状态。

（2）共享状态：该Cache块有效，但一个或多个远程Cache中或主存储器中的Cache块也可能是有效的。

（3)独占状态：该Cache有效，而其它Cache中的相应数据块皆为无效。此外，主存储器中的相应数据块尚未被修改。

（4）已修改状态：该Cache块已由本地处理器完成命中的写操作。

在处理器活动的激励下进行的状态转换

对称式共享存储器多处理器和监听协议的局限性

随着多处理器中处理器数目的增加，或是处理器对存储器要求的增加，系统的任何集中式资源都会变成“瓶颈”。在最简单的基于总线的多处理器的例子中，总线必须同时支持一致性通信和由于Cache导致的存储器通信。同样，如果只有一个存储器部件，它就必须处理所有的处理器请求。随着处理器在过去几年的飞速发展，单独一条总线或单独一个物理存储器所能支持的处理器数量正在下降。为了增加处理器和存储器之间的通信带宽，设计者使用多种总线以及各种互连网络，像交叉开关或小型点对点网络。在这样的设计中，存储器系统可以被配置成多个物理组，以便在保持均匀存储器访问时间的情况下增加有效存储器带宽。一级或多级Cache一级或多级Cache处理器处理器处理器处理器一级或多级Cache一级或多级Cache互联网络I/O系统存储器存储器存储器存储器使用互联网络而不是总线得多处理器，拥有均匀的存储器访问4.3对称式共享存储器多处理器的性能在一个使用监听一致性协议的多处理器中，几个不同的现象决定系统性能。特别是Cache的总体性能由单处理器的Cache缺失。改变处理器个数、Cache大小、块大小都会以不同的方式影响这两种缺失率，导致系统整体性能受这两个因素的共同影响。由处理器间通信引起的缺失通常称为一致性缺失。它可以分为两种。第一种是所谓的真共享缺失，由Cache一致性机制下的数据通信产生。在基于无效的协议中，处理器对共享Cache的第一次写操作引发无效事件，从而获得该块的独占权。除此之外，另一个处理器试图从这个Cache块读一个已修改的字时，会产生一个缺失并且传送一个结果。因为这两种缺失都直接由处理器间共享数据引起，所以都被归为真共享缺失。第二种影响即假共享，是由于使用基于无效的一致性算法引起的。这种算法利用了数据块的有效位，而这个有效位每个数据块只有一个。对数据块中的某些字执行写操作而导致该数据块被置位无效后（随后对该块的调用会导致缺失），再对该块中的某些字执行写操作时，就会发生假共享现象。如果在写操作中将其他处理器中的数据副本置为无效之后，这些处理器再次使用已经写入的数据，那么该调用是一个真共享调

用并会导致缺失，而缺失与块大小或字的位置无关。然而，如果写入的字和读取的字不相同，那么无效并不会引发传输新数值的操作，而只是导致多余的Cache缺失，这就是假共享缺失。在假共享缺失中，共享的是数据块，但是并没有共享单个的字，如果数据块大小是个字，则不会发生这种缺失。下面的例题解释了各种共享方式。例题：假设字x1和x2处于同一块Cache中，这个Cache块在Cachep1和p2中均为共享状态。P1和p2两个Cache在这之前已经读入了x1和x2。假设有如下事件序列，请区别每个缺失究竟是真共享Cache，还是假共享Cache，或是命中。如果数据块大小是一个字，任何能够发生的缺失就都是正共享缺失了。时序p1p21写x12读x23写x14写x25读x2

解答：按事件顺序给出：

1、是真共享缺失。因为p2已经读取了x1,需要将p2上的x1设置为无效。

2、是假共享缺失。因为x2是由于p1对x1执行写操作而置成无效的，但p2中并没有使用x1。

3、是假共享缺失。因为数据块是由于在p2中读x2而被标记为共享的，但p2中并没有读取x1。包含x1的Cache块在p2读后被标记为共享状态，而写缺失需要获得块的独占访问权，在某些协议中，可以通过更新请求解决这个问题，即只产生一个总线无效，但是并不传输该Cache块。

4、是假共享缺失。理由与3相同。

5、是真共享缺失。因为要读取的值刚被p2写过。

4.4分布式共享存储器和基于目录的一致性

存储器分布于各结点中，所有的结点通过网络互连。访问可以是本地的，也可是远程的。可以不支持Cache一致性：规定共享数据不进入Cache，仅私有数据才能保存在Cache中。优点：所需的硬件支持很少(因为远程访问存取量仅是一个字(或双字)而不是一个Cache块)

缺点：(1)实现透明的软件Cache一致性的编译机制能力有限。(2)没有Cache一致性，机器就不能利用取出同一块中的多个字的开销接近于取一个字的开销这个优点，这是因为共享数据是以Cache块为单位进行管理的。当每次访问要从远程存储器取一个字时，不能有效利用共享数据的空间局部性。(3)诸如预取等延迟隐藏技术对于多个字的存取更为有效，比如针对一个Cache块的预取。解决Cache一致性问题的关键：寻找替代监听协议的一致性协议。目录协议：在每个结点增加目录存储器，用于存放目录。处理器+cache处理器+cache处理器+cache存储器目录存储器目录I/O处理器+cache存储器处理器+cacheI/O目录存储器I/O目录存储器I/O目录处理器+cache存储器存储器I/OI/O目录目录目录处理器+cacheI/O存储器处理器+cacheI/O互连网络在分布式存储器多处理器中，每个节点上用目录来实现的Cache的一致性基于目录的Cache一致性协议目录协议必须实现两种基本操作：处理读缺失和处理共享未修改Cache块的写操作（处理共享数据块的写缺失由这两个操作简单组合而成）。为了实现这些操作，目录必须跟踪每个Cache块的状态。在一个简单的协议中，可能出现的状态如下：

共享在一个或多个处理器上拥有Cache

的数据块，并且存储器中的数值也是最新值（与所有的Cache中一样）。未缓存没有任何一个处理器含有数据块的副本。修改只有一个处理器上拥有该Cache块的副本并且已对该块进行过写操作，因此存储器中的副本是无效的。这个处理器称为该块的所有者。

除了跟踪Cache中每个块的状态外，还必须跟踪拥有共享数据块副本的处理器，因为执行写操作后这些处理器中的副本要设置成无效状态。实现这一功能的最简单方法是为每个存储器保留一个位向量。当块处于共享状态时，向量的每一位表示所对应的处理器是否拥