第10章多处理机

张晨曦编著华中科技大学计算机学院2013年5月10.1引言10.2对称式共享存储器体系结构10.3分布式共享存储器体系结构10.4同步10.5同时多线程10.6多处理机实例第10章多处理机10.1.1并行计算机体系结构的分类1.按照Flynn分类法，可把计算机分成单指令流单数据流(SISD)单指令流多数据流(SIMD)多指令流单数据流(MISD)多指令流多数据流(MIMD)10.1引言第十章多处理机2.MIMD已成为通用多处理机体系结构的选择，原因：(1)MIMD具有灵活性；(2)MIMD可以充分利用商品化微处理器在性能价格比方面的优势。3.根据系统中处理器个数的多少，可把现有的MIMD 机器分为两类

(每一类代表了一种存储器的结构和互连策略)(1)集中式共享存储器结构这类机器有时被称为SMP机器(Symmetricshared-memoryMultiProcessor)UMA机器(UniformMemoryAccess)10.1引言集中(对称)共享存储器计算机(2)分布式存储器结构每个结点包含：处理器存储器I／O在许多情况下，分布式存储器结构优于集中式共享存储器结构10.1引言分布式存储器计算机分布式存储器结构的优点主要缺点10.1引言如果大多数的访问是针对本结点的局部存储器，则可降低对存储器和互连网络的带宽要求；局部存储器的访问延迟低。处理器之间的通信较为复杂，且各处理器之间的

访问延迟较大。需要高带宽的互连。簇：超结点10.1.2通信模型和存储器的结构模型1.地址空间的组织方案(两种)(1)物理上分离的多个存储器作为一个逻辑上共享的存储空间进行编址。这类机器的结构被称为:10.1引言分布式共享存储器结构(DSM:DistributedShared-Memory)可缩放共享存储器结构(SSM:ScalableShared-Memory)NUMA机器

(NUMA:Non-UniformMemoryAccess)(2)整个地址空间由多个独立的地址空间构成，它们在逻辑上也是独立的，远程的处理器不能对其直接寻址。每一个处理器-存储器模块实际上是一个单独的计算机，这种机器也称为多(地址空间)计算机。10.1引言共享地址空间的机器利用Load和Store指令中的地址隐含地进行数据通讯。多个地址空间的机器通过处理器间显式地传递消息完成。消息传递机器2.两种通信模型10.1引言消息传递机器根据简单的网络协议，通过传递消息来请求某些服务或传输数据，从而完成通信。例如：一个处理器要对远程存储器上的数据进行访问或操作：

(1)发送消息，请求传递数据或对数据进行操作；远程进程调用(RPC，RemoteProcessCall)(2)目的处理器接收到消息以后，执行相应的操作或代替远程处理器进行访问，并发送一个应答消息将结果返回。10.1引言同步消息传递

请求处理器发送一个请求后一直要等到应答结果才继续运行。异步消息传递

发送方不先经请求就直接把数据送往数据接受方。3.通信机制的性能指标(3个)(1)通信带宽

理想状态下的通信带宽受限于处理器、存储器和互连网络的带宽。

10.1引言(2)通信延迟理想状态下通信延迟应尽可能地小。

通信延迟＝发送开销+跨越时间+传输延迟+接收开销(3)通讯延迟的隐藏如何才能较好地将通信和计算或多次通信之间重叠起来，以实现通讯延迟的隐藏。通常的原则：只要可能就隐藏延迟。通信延迟隐藏是一种提高性能的有效途径，但它对操作系统和编程者来讲增加了额外的负担。10.1引言4.不同通信机制的优点

A.共享存储器通信(Load/Store)的主要优点(1)与常用的集中式多处理机使用的通信机制兼容。(2)易于编程——与传统的编程模式一致(3)当通信数据较小时，通信开销较低，带宽利用较好。(4)通过硬件控制的Cache减少了远程通信的频度，减少了通信延迟以及对共享数据的访问冲突。10.1引言B.消息传递通信机制的主要优点(1)硬件较简单。(2)通信是显式的，从而引起编程者和编译程序的注意，着重处理开销大的通信(本地Load/Store,远程MSG)。在共享存储器上支持消息传递相对简单在消息传递的硬件上支持共享存储器就困难得多。所有对共享存储器的访问均要求操作系统提供地址转换和存储保护功能，即将存储器访问转换为消息的发送和接收。10.1引言10.1.3并行处理面临的挑战并行处理面临着两个重要的挑战：程序中有限的并行性相对较高的通信开销系统加速比=10.1引言例10.1如果想用100个处理器达到80的加速比，求原计算程序中串行部分所占比例。解2.第二个挑战：多处理机中远程访问的延迟较大

在现有的机器中，处理器之间的数据通信大约需要50～10000个时钟周期。

1.第一个挑战：有限的并行性

使机器要达到好的加速比十分困难10.1引言机器通信机制互连网络处理机数量典型远程存储器访问时间SPARCCenter共享存储器总线≤201μsSGIChallenge共享存储器总线≤361μsCrayT3D共享存储器3维环网32－20481μsConvexExemplar共享存储器交叉开关＋环8－642μsKSR-1共享存储器多层次环32－2562-6μsCM-5消息传递胖树32－102410μsIntelParagon消息传递2维网格32－204810-30μsIBMSP-2消息传递多级开关2－51230-100μs远程访问一个字的延迟时间例一台32个处理器的计算机，对远程存储器访问时间为2000ns。除了通信以外，假设计算中的访问均命中局部存储器。当发出一个远程请求时，本处理器挂起。处理器时钟时间为10ns，如果指令基本的CPI为1.0(设所有访存均命中Cache)，求在没有远程访问的状态下与有0.5%的指令需要远程访问的状态下，前者比后者快多少?

解有0.5%远程访问的机器的实际CPI为CPI＝基本CPI＋远程访问率×远程访问开销＝1.0＋0.5%×远程访问开销

10.1引言远程访问开销＝远程访问时间/时钟时间＝2000ns/10ns＝200个时钟∴CPI＝1.0＋0.5%×200＝2.0它为只有局部访问的机器的2.0／1.0＝2倍，因此在没有远程访问的状态下的机器速度是有0.5%远程访问的机器速度的2倍。

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

10.1引言3.并行程序的计算／通信比率(类似于单机访存频度)反映并行程序性能的一个重要的度量计算与通信的比率计算／通信比率随着处理数据规模的增大而增加；随着处理器数目的增加而降低。10.1引言10.2对称(集中)式共享存储器体系结构多个处理器共享一个存储器。当处理器规模较小时，这种机器十分经济。支持对共享数据和私有数据的Cache缓存.私有数据供一个单独的处理器使用，而共享数据供多个处理器使用。共享数据进入Cache产生了一个新的问题Cache的一致性问题第十章多处理机(1)不一致产生的原因（Cache一致性问题）I／O操作Cache中的内容可能与由I／O子系统输入输出形成的存储器对应部分的内容不同。共享数据不同处理器的Cache都保存有对应存储器单元的内容。

例两个处理器的读写10.2.1多处理机Cache一致性10.2对称式共享存储器体系结构(2)存储器的一致性（非正式定义）

如果对某个数据项的任何读操作均可得到其最新写入的值，则认为这个存储系统是一致的。

What:返回给读操作的是什么值When:什么时候才能将已写入的值返回给读操作需要满足以下满足条件①处理器P对X进行一次写之后又对X进行读，读和写之间没有其它处理器对X进行写，则读的返回值总是写进的值。

存储系统行为的两个不同方面10.2对称式共享存储器体系结构②一个处理器对X进行写之后，另一处理器对X进行读，读和写之间无其它写，则读X的返回值应为写进的值。③对同一单元的写是顺序化的，即任意两个处理器对同一单元的两次写，从所有处理器看来顺序都应是相同的。假设直到所有的处理器均看到了写的结果，一次写操作才算完成；允许处理器无序读，但必须以程序规定的顺序进行写。

10.2对称式共享存储器体系结构在一致的多处理机中，Cache提供两种功能：共享数据的迁移(拷贝到本地Cache)

降低了对远程共享数据的访问延迟。共享数据的复制(多个机器都需要的数据拷贝到各自的Cache)

不仅降低了访存的延迟，也减少了访问共享数据所产生的冲突。

小规模多处理机不是采用软件而是采用硬件技术实现Cache一致性。10.2.2实现一致性的基本方案10.2对称式共享存储器体系结构(1)Cache一致性协议对多个处理器维护一致性的协议。(2)关键：跟踪记录共享数据块的状态(3)共享数据状态跟踪记录技术目录(directory)物理存储器中共享数据块的状态及相关信息均被保存在一个称为目录的地方。监听(snooping)每个Cache除了包含物理存储器中块的数据拷贝之外，也保存着各个块的共享状态信息。10.2对称式共享存储器体系结构Cache通常连在共享存储器的总线上，各个Cache控制器通过监听总线来判断它们是否有总线上请求的数据块。两种更新协议(1)写作废协议在一个处理器写某个数据项之前保证它对该数据项有唯一的访问权。无论是在监听还是目录模式下，唯一的访问权保证了在进行写后不存在其它的可读或者可写的拷贝存在，即别的拷贝都作废了。

例：在写回Cache的条件下，监听总线中写作废协议的实现。10.2对称式共享存储器体系结构在写回cache的条件下，监听总线中写作废协议的实现处理器行为总线行为CPUACache内容CPUBCache内容主存X单元内容0CPUA读XCache失效00CPUB读XCache失效000CPUA将X单元写1作废X单元11CPUB读XCache失效111(2)写更新协议当一个处理器写某数据项时，通过广播使其它Cache中所有对应的该数据项拷贝进行更新。例在写回Cache的条件下，监听总线中写更新协议的实现。

处理器行为总线行为CPUACache内容CPUBCache内容主存X单元内容0CPUA读XCache失效00CPUB读XCache失效000CPUA将X单元写1广播写X单元111CPUB读X111(3)写更新和写作废协议性能上的差别主要来自：对同一数据的多个写而中间无读操作的情况，写更新协议需进行多次写广播操作，而在写作废协议下只需一次作废操作。对同一块中多个字进行写，写更新协议对每个字的写均要进行一次广播，而在写作废协议下仅在对本块第一次写时进行作废操作。从一个处理器写到另一个处理器读之间的延迟通常在写更新模式中较低。而在写作废协议中，需要读一个新的拷贝。10.2对称式共享存储器体系结构大多数多处理机系统都采用写作废协议10.2.3监听协议及其实现基本实现技术10.2对称式共享存储器体系结构小规模多处理机中实现写作废协议的关键利用总线进行作废操作：把要作废的地址放到总线上（一个放，多个读）。其它处理器一直监听总线。写顺序化：对于写直达Cache，因为所有写的数据同时被写回主存，则从主存中总可以取到最新的数据值。对于写回Cache，得到数据的最新值会困难一些，因为最新值可能在某个Cache中，也可能在主存中。写缺失时，除了作废其它处理器相应的cache块，还要从存储器取出该数据据块。增加Cache中块的标志位，用于实现监听过程

状态：

有效位（valid）——无副本(为了作废方便)共享（shared）——至少一个副本，clean独占（exclusive）——唯一副本，dirty。写操作使共享变成独占。如果没有别的写，永远是独占；反之变共享。便于决定是否广播？

Cache块的拥有者：拥有唯一的Cache块副本的处理器。

因为每次总线任务均要检查Cache的地址位，这可能与CPU对Cache的访问冲突。可通过下列两种技术之一降低冲突：复制标志位采用多级包容Cache（许多系统采用）10.2对称式共享存储器体系结构监听协议举例为简单起见，对于对共享块的Writehit和Writemiss不加区分，都按Writemiss处理写作废，写回法10.2对称式共享存储器体系结构

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

(1)实现透明的软件Cache一致性的编译机制能力有限。(2)没有Cache一致性，机器就不能利用取出同一块中的多个字的开销接近于取一个字的开销这个优点，这是因为共享数据是以Cache块为单位进行管理的。当每次访问要从远程存储器取一个字时，不能有效利用共享数据的空间局部性。(3)诸如预取等延迟隐藏技术对于多个字的存取(coalesced)更为有效，比如针对一个Cache块的预取。10.3分布式共享存储器体系结构解决Cache一致性问题的关键：寻找替代监听协议的一致性协议。目录协议在每个结点增加目录存储器，用于存放目录对每个结点增加目录表后的分布式存储器的系统结构10.3分布式共享存储器体系结构(1)目录协议必须实现两种基本操作处理读失效处理对共享、干净块的写对共享块写失效的处理是这两个操作的简单组合

(2)目录必须跟踪记录每个存储块的状态存储块的状态有三种：10.3.1基于目录的Cache一致性及其实现10.3分布式共享存储器体系结构共享

在一个或多个处理器上具有这个块的副本，且主存中的值是最新值（所有Cache均相同）。未缓冲所有处理器的Cache都没有该块的拷贝。专有仅有一个处理器上有该块的副本，且已对该块进行了写操作，而主存的拷贝仍是旧的。这个处理器称为该块的拥有者。

10.3分布式共享存储器体系结构(3)由于写作废操作的需要，还必须记录哪些处理器有该块的拷贝方法：对每个主存块设置一个位向量当该块被共享时，每个位指出与之对应的处理器是否有该块的拷贝。当该块为专有时，可根据位向量来寻找其拥有者。10.3分布式共享存储器体系结构结点之间发送的消息及其作用10.3分布式共享存储器体系结构目录状态转换图对基于目录的Cache一致性的多种改进有限映射目录链式结构目录基于目录的Cache一致性协议是完全由硬件实现的。

此外，还可以用软硬结合的办法实现。10.3分布式共享存储器体系结构10.4同步

通常是使用硬件提供的有关同步指令，通过用户级软件例程建立的。10.4.1基本硬件原语在多处理器同步中，主要功能是一组能自动读出后并进行写存储单元的硬件原语。它们能够自动读／修改单元。通常情况下，用户不直接使用基本的硬件原语，原语主要供系统程序员用来编制同步库函数。

第十章多处理机功能：将一个存储单元的值和一个寄存器的值进行交换。建立一个锁，锁值为“0”表示开锁，

为“1”表示上锁。处理器加锁时，将对应于该锁的存储单元的值

交换为某个寄存器的值“1”。如果返回值为“0”，

存储单元的值此时已置换为“1”，防止了别的进

程竞争该锁。

实现同步的关键:操作的原子性1.典型操作:原子交换（atomicexchange）10.4同步2.测试并置定（test_and_set）先测试一个值，如果符合条件则修改其值。3.读取并加1（fetch_and_increment）它返回存储单元的值并自动增加该值。4.使用指令对

LL(loadlinked或loadlocked)的取指令

SC(storeconditional)的特殊存指令10.4同步例实现对由R1指出的存储单元进行原子交换操作try：movR3,R4；送交换值llR2,0(R1)；loadlinkedscR3,0(R1)；storeconditionalbeqzR3,try；存失败转移movR4,R2；将取的值送往R4最终R4和由R1指向的单元值进行原子交换，在ll和sc之间如有别的处理器插入并修改了存储单元的值，sc将返回“0”并存入R3中，从而使指令序列再重新循环。10.4同步

ll／sc机制的一个优点：可用来构造别的同步原语

例如：原子的fetch-and-incrementtry：

llR2,0(R1)；loadlinked

addiR2,R2,＃1；增加

scR2,0(R1)；storeconditional

beqzR2,try；存失败转移指令对的实现必须跟踪地址

由ll指令指定一个寄存器，该寄存器存放着一个

单元地址，这个寄存器常称为连接寄存器。10.4同步10.4.2用一致性实现锁采用多处理机的一致性机制来实现旋转锁。旋转锁

处理器环绕一个锁不停地旋转而请求获得该锁。1.无Cache一致性机制在存储器中保存锁变量，处理器可以不断地通过一个原子操作请求加锁，比如先交换，再测试返回值从而知道锁的状况。释放锁的时候，处理器可简单地将锁置为“0”。10.4同步liR2，＃1lockit：exchR2,0(R1)；原子交换bnezR2，lockit；是否已加锁?2.机器支持Cache一致性将锁缓冲进入Cache，并通过一致性机制使锁值保

持一致。

10.4同步

优点可使“环绕”的进程对本地Cache块进行操作；可利用锁访问的局部性，即处理器最近使用过的锁不久又会使用。改进旋转锁(获得第一条好处)

使其环绕过程仅对本地Cache中锁的拷贝进行读，直到它返回“0”确认锁可用，然后再进行加锁交换操作。使用锁完毕后新竞争又开始进行。10.4同步

lockit：lwR2，0(R1)；取锁值bnezR2，lockit；锁不可用liR2，＃1；存入锁值exchR2，0(R1)；交换bnezR2，lockit;如锁不为0转移上面给出了对于三个处理器竞争锁的操作。一旦处理器存入“0”释放锁，所有别的Cache对应块均被作废，必须取新的值来更新它们锁的拷贝。一个处理器Cache会先获得未加锁值并执行交换操作，当别的Cache失效处理完后，它们会发现已被加锁，所以又必须不停地测试环绕。10.4同步表10.5三个处理机对锁的使用步骤处理器P0处理器P1处理器P2锁状态总线/目录操作1占有锁环绕测试lock=0环绕测试lock=0Shared无2将锁置为0（收到作废命令）(收到作废命令)ExclusiveP0发锁变量作废消息3

Cache失效Cache失效Shared总线/目录处理P2Cache失效,锁从P0写回4

总线/目录忙则等待Lock=0SharedP2Cache失效处理5

Lock=0执行交换，导致Cache失效SharedP1Cache失效处理6

执行交换，导致Cache失效

交换完毕，返回0置lock=1Exclusive总线/目录处理P2Cache失效,发作废消息7

交换完毕，返回1进入关键处理段Shared总线/目录处理P2Cache失效，写回8

环绕测试lock=0

无10.4同步

ll／sc原语的另一个状态：读写操作明显分开。

Ll不产生总线数据传送，这使下面代码与使用经过优化交换的代码具有相同的特点：

lockit：

llR2，0(R1)；load-linked

bnezR2，lockit

；锁无效

liR2,，＃1；加锁值

scR2，0(R1)；存

beqzR2，lockit

；如存失败转移

第一个分支形成环绕的循环体，第二个分支解决了两个同时请求锁的处理器竞争问题。尽管旋转锁机制简单并且具有强制性，但难以将它扩展到处理器数量很多的情况。10.4同步10.4.3同步性能问题简单旋转锁不能很好地适应可伸缩性。大规模机器中所有的处理器会产生出大量的竞争问题。例10.3：设总线上有10个处理器同时准备对同一变量加锁。假设每个总线事务处理(读失效或写失效)是100个时钟周期，忽略实际的Cache块锁的读写时间以及加锁的时间，求10个处理器请求加锁所需的总线事务数目。设时间为0时锁已释放并且所有处理器在旋转，求处理这10个请求时间为多长?假设总线在新的请求到达之前已服务完挂起的所有请求，并且处理器速度相同。10.4同步解当i个处理器竞争锁的时候，他们完成下列操作序列，每一个操作产生一个总线事务：访问该锁的i个LL指令操作；试图锁住该锁的i个SC指令操作；1个释放锁的存操作指令。因此对n个处理器，总线事务的总和为：n∑(2i+1)=n(n+1)+n=n2+2ni=1对于10个处理器有120个总线事务，需要12000个时钟周期。10.4同步本例中问题的根源是锁的竞争、存储器中锁访问的串行性以及总线访问的延迟。旋转锁的主要优点:对于总线或网络开销较低10.4同步并行循环的程序中另一个常用的同步操作:栅栏栅栏强制所有到达的进程进行等待，直到全部的进程到达栅栏，然后释放全部的进程，从而形成同步。

栅栏的典型实现用两个旋转锁

(1)用来记录到达栅栏的进程数

(2)用来封锁进程直至最后一个进程到达栅栏栅栏的实现要不停地探测指定的变量，直到它满足规定的条件。

一种典型的实现，其中lock和unlock提供基本的旋转锁，total是要到达栅栏的进程总数。10.4同步Lock(counterlock)；

／*确保更新的原子性*／if(count=0)release=0；／*第一个进程则重置release*／count=count+1；／*到达进程记数*／unlock(counterlock)；／*释放锁*／if(count==total){／*进程全部到达*／count=0；／*重置计数器*／release=1；／*释放进程*／｝else{／*还有进程未到达*／spin(release=1)；／*等待别的进程到达*／｝10.4同步

对counterlock加锁保证增量操作的原子性，变量count记录着已到达栅栏的进程数，变量release用来封锁进程直到最后一个进程到达栅栏。

实际情况中会出现的问题可能反复使用一个栅栏，栅栏释放的进程运行一段后又会再次返回栅栏，这样有可能出现某个进程永远离不开栅栏的状况(它停在旋转操作上)。10.4同步例如：OS调度进程，可能一个进程速度较快，当它第二次到达栅栏时，第一次的进程还挂在栅栏中未能离开。这样所有的进程在这个栅栏的第二次使用中都处于无限等待状态，因为进程的数目永达不到total。10.4同步一种解决方法当进程离开栅栏时进行计数，在上次栅栏使用中的所有进程离开之前不允许任何进程重用并初始化本栅栏。另一种解决办法sense_reversing栅栏，每个进程均使用一个私有变量local_sense，初始化为1。10.4同步Local_sense=!Local_sense；／*local-sense取反*／lock(counterlock)；／*确保增加的原子性*／count++；／*记算到达进程数*／unlock(counterlock)；／*解锁*／if(count==total){／*进程全部到达*／count=0；／*重置计数器*／release=local_sense；／*释放进程*／｝else{／*还有进程未到达*／spin(release=local_sense)；／*等待信号*／｝10.4同步例10.4假设总线上10个处理器同时执行一个栅栏，设每个总线事务需100个时钟周期，忽略Cache块中锁的读、写实际花费的时间，以及栅栏实现中非同步操作的时间，计算10个处理器全部到达栅栏，被释放及离开栅栏所需的总线事务数。设总线完全公平，整个过程需多长时间?答：下表给出一个处理器通过栅栏发出的事件序列，设第一个获得总线的进程并未拥有锁。10.5同步表10.6第i个处理器通过栅栏产生的事件序列

事件数量对应源代码说明LLiLock(counterlock)；所有处理器抢锁SCiLock(counterlock)；所有处理器抢锁LD1count=count+1；一个成功LLi-1Lock(counterlock)；不成功的处理器再次抢锁SD1count=count+1；获得专有访问产生的失效SD1unlock(counterlock)；获得锁产生的失效LD2spin(release=local_sense)；读释放：初次和最后写产生的失效10.4同步当竞争不激烈且同步操作较少时，我们主要关心的是一个同步原语操作的延迟。基本的旋转锁操作可在两个总线周期内完成：一个读锁，一个写锁。我们可用多种方法改进形成在一个单周期内完成操作。同步操作最严重的问题：进程的串行性当出现竞争时，就会出现串行性问题。它极大地增加了同步操作的时间。

总线的使用是这个问题关键所在。在基于目录的Cache一致性机器中，串行性问题也同样严重。10.4同步10.4.4大规模机器的同步所希望的同步机制：在无竞争的条件下延迟较小在竞争激烈时串行性小1.软件实现旋转锁

(1)旋转锁实现的主要问题当多个进程检测并竞争锁时引起的延迟

(2)一种解决办法:当加锁失败时就人为地推延这些进程的等待时间。

(3)具有指数延迟的旋转锁代码10.4同步

liR3，1；R3＝初始延迟值；lockit：llR2，0(R1)；loadlinkedbnezR2，lockit；无效addiR2，R2，1；取到加锁值scR2，0(R1)；storeconditionalbnezR2，gotit；存成功转移sllR3，R3，1；将延迟时间增至2倍pauseR3；延迟R3中时间值jlockitgotit：使用加锁保护的数据

当sc失败时，进程推延R3个时间单位。10.4同步先讨论采用数组进行的软件实现。为此我们给出一种更好的栅栏实现代码。前面栅栏机制实现中，所有的进程必须读取

release标志，形成冲突。通过组合树来减小冲突组合树是多个请求在局部结合起来形成树的一种分级结构。降低冲突的原因：将大冲突化解成为并行的多个小冲突。

锁实现的另一种技术是排队锁10.4同步组合树采用预定义的n叉树结构用变量k表示扇入数目，实际中k=4效果较好。当k个进程都到达树的某个结点时，则发信号进入树的上一层。当全部进程到达的信号汇集在根结点时，释放所有的进程。采用sense_reversing技术来给出下面的基于组合树的栅栏代码。10.4同步structnode｛

／*组合树中一个结点*／intcounterlock；intcount

；intparent；｝；structnodetree［0..p-1］；

／*树中各结点*／intlocal_sense；intrelease；barrier(intmynode)｛lock(tree[mynode].counterlock)；／*保护计数器*／count++；／*计数的累加*／unlock(tree[mynode].conterlock)；／*解锁*／if(tree[mynode].count==k)｛／*本结点全部到达*／if(tree[mynode].parent)>=0｛barrier(tree[mynode］.parent)；

｝else｛release=local_sense；｝tree[mynode].count＝0；｝

／*为下次重用初始化*／else｛spin(release=local_sense)；｝；｝；local_sense=!local_sense；barrier(mynode)；10.4同步2.硬件原语支持

介绍两种硬件同步原语：(1)排队锁可以排队记录等待的进程，当锁释放时送出一个已确定的等待进程。

第一个针对锁第二个针对栅栏和要求进行计数或提供明确索引的某些用户级操作10.4同步硬件实现

在基于目录的机器上，通过硬件向量等方式来进行排队和同步控制。在基于总线的机器中要将锁从一个进程显式地传给另一个进程，软件实现会更好一些。在第一次取锁变量失效时，失效被送入同步控制器。同步控制器可集成在存储控制器中(基于总线的系统)或集成在目录控制器中。排队锁的工作过程10.4同步如果锁空闲，将其交给该处理器；如果锁忙，控制器产生一个结点请求记录，并将锁忙的标志返回给处理器，然后该处理器不停地进行检测。当该锁被释放时，控制器从等待的进程排队中选出一个使用锁，这可以通过更新所选进程Cache中的锁变量来完成。10.4同步例10.5如果在排队锁的使用中，失效时进行锁更新，求10个处理器完成lock和unlock所需的时间和总线事务数。假设条件与前面例子相同。解对n个处理器，每个处理器都初始加锁产生1个总线事务，其中1个成功获得锁并在使用后释放锁，第1个处理器将有n+1个总线事务。每一个后续的处理器需要2个总线事务：1个获得锁，另1个释放锁。因此总线事务的总数为(n+1)+2(n-1)=3n-1。注意这里的总线事务总数随处理器数量成线性增长，而不是前面旋转锁那样成二次方增长。对10个处理器，共需要29个总线事务或2900个时钟周期。10.4同步首先，需要识别出对锁进行初次访问的进程，从而对其进行排队操作。第二，等待进程队列可通过多种机制实现，在基于目录的机器中，队列为共享集合，需用类似目录向量的硬件来实现排队锁的操作。最后，必须有硬件来回收锁，因为请求加锁的进程可能被切换时切出，并且有可能在同一处理器上不再被调度切入。

排队锁功能实现中有一些要考虑的关键问题10.4同步

为减少栅栏记数时所需的时间，从而减小瓶颈的串行度，引进一种原语Fetch_and_increment，它可以原子地取值并增量。使用fetch_and_increment可以很好地改进栅栏的实现。例7.6：写出fetch_and_increment栅栏的代码。条件与前面假设相同，并设一次fetch_and_increment操作也需100个时钟周期。计算10个处理器通过栅栏的时间，及所需的总线周期数。(2)栅栏实现10.4同步解下面的程序段给出栅栏的代码。对n个处理器，这种实现需要进行n次fetch_and_increment操作，访问count变量的n次cache失效和释放时的n次Cache失效，这样总共需要3n个总线事务。对10个处理器，总共需要30个总线事务或3000个时钟周期。这里如同排队锁那样，时间与处理器个数成线性增长。

当然，实现组合树栅栏时也可采用fetch_and_increment来降低树中每个结点的串行竞争。10.4同步

local_sense=!local_sense；

／*local_sense变反*／fetch-and-increment(count)；／*原子性更新*／if(count==total){／*进程全部到达*／count=0；／*初始化计数器*／release=local_sense；

／*释放进程*／｝else{／*还有进程未到达*／spin(releaze=local_sense)；／*等待信号*／}10.4同步多线程使多个线程以重叠的方式共享单个处理器的功能单元。10.5同时多线程为实现共享，处理器必须保存各个线程的独立状态。硬件必须能够较快地完成线程间的切换。线程的切 换应该比进程的切换要高效的多，进程的切换一般 需要成百上千个处理器时钟周期。第十章多处理机第一种方法：细粒度多线程技术它在每条指令间都能进行线程的切换，从而导致多个线程的交替执行。

主要优点：能够隐藏由任何或长或短的阻塞带来的吞吐率的损失主要缺点：减慢了每个独立线程的执行目前有两种主要的多线程实现方法10.5同时多线程第二种方法：粗粒度多线程技术粗粒度多线程之间的切换只在发生代价较高、时间较长的阻塞出现时。缺点：不能有效地减少吞吐率的损失。原因：由粗粒度多线程的流水线建立时间的开销造成的。由于实现粗粒度多线程的CPU只执行单个线程的指令，因此当发生阻塞时，流水线必须排空或暂停。阻塞后切换的新的线程在指令执行产生结果之前必须先填满整个流水线。10.5同时多线程10.5.1将线程级并行转换为指令级并行

同时多线程技术是一种在多流出、动态调度处理器上开发线程级并行和指令级并行的改进的多线程技术。1.产生的主要原因

现代多流出处理器通常含有多个并行的功能单元，而单个线程不能有效地利用这些功能单元。通过寄存器重命名和动态调度机制，来自各个独立线程的多条指令可以同时流出，而不考虑他们之间的相互依赖关系；其相互依赖关系将通过动态调度机制得以解决。10.5同时多线程2.一个超标量处理器在以下几种配置时其性能的差别支持多线程技术的超标量处理器由于缺乏足够的指令级并行而限制了流出槽的利用率。支持粗粒度多线程的超标量处理器通过线程的切换部分隐藏了长时间阻塞带来的开销。由于只有当发生阻塞时才进行线程切换，新线程还需要流水线建立时间，所以会产生一些完全空闲的时钟周期。10.5同时多线程支持细粒度多线程的超标量处理器线程的交替执行消除了完全空闲的流出槽。由于在每个时钟周期内只流出一个线程的指令，指令级并行的限制仍然导致一个时钟周期内存在不少的空闲流出槽。支持同时多线程的超标量处理器通过在一个时钟周期内调度多个线程使用流出槽，从而同时实现线程级并行和指令级并行。理想情况下，流出槽的使用率只受限于多个线程对资源的需求和可用资源间的不平衡。10.5同时多线程图7.16:超标量处理器中的4种不同的流出槽使用方法开发的基础:使用动态调度技术的处理器已经具有了开发线程级并行所需的硬件设置。动态调度超标量处理器有大量的虚拟寄存器组，可以用来保存每个独立线程的寄存器状态。由于寄存器重命名机制提供了唯一的寄存器标识符，多个线程的指令可以在数据路径上混合执行，而不会导致各线程间源操作数和目的操作数的混乱。多线程技术可以通过在一个乱序执行的处理器上为每个线程设置重命名表、保留各自的PC值、提供多个线程的指令结果提交的能力来实现。10.5同时多线程10.5.2同时多线程处理器的设计同时多线程只有在细粒度的实现方式下才有意义并发多个同优先级的线程必然拉长单个线程的执 行时间

通过指定一个优先线程来减小这种影响，从而在整体性能提高的同时对单个指定的线程性能只产生较小的影响。10.5同时多线程多个线程的混合执行将不可避免地影响单个线程的执行时间

为提高单个线程的性能，应该为指定的优先线程尽可能多地向前取指，并且在分支预测失效和预取缓冲失效的情况下清空取指单元。但是这样限制了其他线程可用来调度的指令条数，从而减少了吞吐率。所有的多线程处理器都必须在这里寻求一种折衷方案。10.5同时多线程只要一有可能，处理器就运行指定的优先线程。从取指阶段开始就优先处理优先线程

只要优先线程的指令预取缓冲区未满，就为它优先取指。只有当优先线程的缓冲区填满以后才为其他线程预取指令。当有两个优先线程时，需要并发预取两个指令流，这给取指部件和指令cache的设置都增添了复杂度。

10.5同时多线程设计同时多线程处理器时面临的其他主要问题指令流出单元也要优先考虑指定的优先线程，只有当优先线程阻塞不能流出的时候才考虑其他线程。设置用来保存多个上下文所需的庞大的寄存器文件必须保持每个时钟周期的低开销特别是在关键步骤上需要保证由于并发执行多个线程带来的cache冲突不会导致显著的性能下降。10.5同时多线程通过研究这些问题还可以了解到在大多情况下多线程所导致的额外性能开销是很小的，简单的线程切换选择算法就足够；目前的超标量处理器的效率是比较低的，还有很大的改进余地，同时多线程是获得吞吐率改进的最有前途的方法之一。10.5同时多线程10.5.3同时多线程的性能图7.17表示在超标量处理器上增添8个线程的同 时多线程能力时获得的性能提高图7.18表示SMT与基本的超标量处理器在主要内 部指标利用率和命中率上的对比

10.5同时多线程两个特点超标量处理器本身功能十分强大，它具有很大的一级cache、