【文档说明】计算机系统结构第6章多处理器和线程级并行课件.pptx，共(87)页，470.933 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-76834.html

以下为本文档部分文字说明：

计算机系统结构第6章多处理器和线程级并行课件第6章-多处理器和线程级并行第6章-多处理器和线程级并行多指令流单数据流（MISD）－至今没有这种商用机器多指令流多数据流（MIMD）－每个处理器取用自己的数据进行操作。MIMD已成为通用多处理机体系结构

的选择，原因：(1)MIMD(2)MIMD可以充分利用商品化微处理器在性能价格比方面的优势。计算机机群系统（cluster）是一类广泛被采用的MIMD计算机。根据多处理机系统中处理器个数的多少，可把现有的MIMD机器分为两类：(1)集中式共享存储器结构最多由几十个处理器构成。

通过大容量的Cache和总线互连使各处理器共享一个单独的物理存储器。这类机器有时被称为UMA(uniformmemoryaccess,均匀存储器访问)机器。第6章-多处理器和线程级并行第6章-多处理器和线程级并行CPU0CPU1CPU2CPU3存

储器I/O对称式共享存储器多处理机的基本结构由于单个主存储器对每个处理器都是对称关系，且每个处理器访问主存储器的时间相同，这种多处理器系统也称为对称多处理器系统。第6章-多处理器和线程级并行第6章-多处理器和线程级并行(2)分布式存储器结构

多处理器存储器在物理上分布•处理器•存储器•I／O•互连网络接口在许多情况下，分布式存储器结构优于采用集中式共享存储器结构。分布式存储器结构需要高带宽的互连。分布式存储器结构的优点(1)如果大多数的访问是针对本结点的局部存储器，

则可降低对存储器和互连网络的带宽要求；(2)对局部存储器的访问延迟低。第6章-多处理器和线程级并行第6章-多处理器和线程级并行分布式存储器多处理器的基本结构由多个独立节点构成互连网络I/o存储器I/o存储器I/o存储器I/o

存储器CPU0CPU1CPU2CPU3存储器I/o存储器I/o存储器I/o存储器I/oCPU4CPU5CPU6CPU7第6章-多处理器和线程级并行6.1.2通信模型和存储器的结构模型主要缺点:处理器不再共享单一集中存储器，处理器之间的通信较为复杂

，且各处理器之间访问延迟较大。6.1.2通信模型和存储器的结构模型1.两种地址空间的组织方案共享地址空间(1)物理上分离的多个存储器可作为一个逻辑上共享的存储空间进行编址。(2)任何一个处理器可以访问该共享空间中的任何一个单元（如果它具有访问权），而且不同处理器上的同一个物理地址指向

的是同一个存储单元。这类机器的结构被称为分布式共享存储器DSM(DistributedShared-Memory)或可缩放共享存储器体系结构。DSM机器被称为NUMA(non-uniformmemoryaccess,即均匀存储器访问)机器。第6章-多

处理器和线程级并行6.1.2通信模型和存储器的结构模型(2)整个地址空间由多个独立的地址空间构成，它们在逻辑上也是分散的，远程的处理器不能对其直接寻址。每一个处理器-存储器模块实际上是一个单独的计算机，这种机器也称为多计算机。每一个处理器-存储器模块实际上是

一台单独的计算机,这些并行的处理器称为多机系统；多机系统能游独立的计算机通过网络连接实现，称之为集群。第6章-多处理器和线程级并行6.1.2通信模型和存储器的结构模型2.两种通信模型共享地址空间的机器利用Load和Store指令中的地址隐含地进行数

据通信多个地址空间的机器通过处理器间显式地传递消息完成(消息传递多处理机)消息传递机器根据简单的网络协议，通过传递消息来请求某些服务或传输数据，从而完成通信。例如：一个处理器要对远程存储器上的数据进行访问或操作发送消息，请求传递数据或对数据

进行操作；远程进程调用(RPC，remoteprocesscall)目的处理器接收到消息以后，执行相应的操作或代替远程处理器进行访问，并发送一个应答消息将结果返回。第6章-多处理器和线程级并行6.1.2通信模型和存储器的结构模型同步消息传递请求处理器发

送一个请求后一直要等到应答结果才继续运行。异步消息传递发送方不先经请求就直接把数据送往数据接收方。通信机制的性能指标三个关键的性能指标：通信带宽理想状态下的通信带宽受限于处理器、存储器和互连网络的带宽，不受通信机制的限制。通

信延迟理想状态下通信延迟应尽可能地小。通信延迟＝发送者开销＋飞行时间＋传输延迟＋接收者开销飞行时间(Timeofflight)：数字信号从发送方的线路端传送到接收方的线路端所经过的时间，是固定的。传输时间：全部的消息量除以线路带宽,取决于互连网络。发送和

接收开销:主要由通信机制及其实现方法决定。第6章-多处理器和线程级并行6.1.2通信模型和存储器的结构模型通信延迟的隐藏通信机制通过将通信过程与计算过程或其他通信过程重叠的方法来隐藏延迟。如何才能较好地将通信和计算或多次通信之间重叠起来，以实现通信延迟的隐藏。通常的原则是：只要可能就隐

藏延迟。通信延迟隐藏是一种提高性能的有效途径，但它对操作系统和编程者来讲增加了额外的负担。4.不同通信机制的优点共享存储器通信的主要优点与常用的集中式多处理机使用的通信机制兼容。当处理器通信方式复杂或

程序执行动态变化时易于编程，同时当通信数据较小时，通信开销较低，带宽利用较好。通过硬件控制的Cache减少了远程通信的频度，减少了通信延迟以及对共享数据的访问冲突。第6章-多处理器和线程级并行6.1.2

通信模型和存储器的结构模型通信是显式的，从而引起编程者和编译程序的注意，着重处理开销大的通信。可在支持上面任何一种通信机制的硬件模型上建立所需的通信模式平台。在共享存储器上支持消息传递相对简单；

在消息传递的硬件上支持共享存储器就困难得多。所有对共享存储器的访问均要求操作系统提供地址转换和存储保护功能，即将存储器访问转换为消息的发送和接收。第6章-多处理器和线程级并行6.1.3并行处理面临的挑战并行处理面临

着两个重要的挑战：程序中有限的并行性相对较高的通信开销（可通过Amdahl定律解释）系统加速比=理论加速比可加速部分比例可加速部分比例）（11可获得的并行度有限使得并行机很难获得较高的加速比第6章-多处理器和线程级并行6.1.3并行处理面临的挑战1

.第一个挑战有限的并行性使机器要达到好的加速比十分困难。例6.1假设想用100个处理器达到80的加速比，求原计算程序中串行部分最多可占多大的比例？解Amdahl定律为－可加速部分比例）＋（理论加速比可加速部分比例加速比＝11－并行比例）＋（并行比例＝110018

0由上式可得，并行比例＝0.9975第6章-多处理器和线程级并行6.1.3并行处理面临的挑战2.第二个挑战：多处理机中远程访问的延迟较大现有的机器中，处理器之间的数据通信大约需要50～10000个时钟周期。主要取决于：通信机制、互连网络的种类和计算机的规模问

题的解决并行性不足：在软件中采用更好的并行算法远程访问延迟的降低：靠系统结构支持和编程技术比如，在硬件上缓存共享数据，或在软件上重新构造以便增加本地访问、使用预取或多线程来减少延迟的影响。第6章-多处理器和线程级并行6.1.3并行处理面临的挑战（2

）远程访问一个字的延迟时间机器通信机制互连网络处理机数量典型远程存储器访问时间SPARCCenter共享存储器总线≤201μsSGIChallenge共享存储器总线≤361μsCrayT3D共享存储器3维环网32－20481μsCo

nvexExemplar共享存储器交叉开关＋环8－642μsKSR-1共享存储器多层次环32－2562-6μsCM-5消息传递胖树32－102410μsIntelParagon消息传递2维网格32－204810-30μsIBMSP-2消息传递多

级开关2－51230-100μs第6章-多处理器和线程级并行6.1.3并行处理面临的挑战（3）例6.2一台32个处理器的计算机，对远程存储器访问时间为400ns。除了通信以外，假设计算中的访问均命中局部存储器。当发出一个远程请求时，本处理器挂

起。处理器时钟时间为1GHz，如果指令基本的IPC为2(设所有访存均命中Cache)，求在没有远程访问的状态下与有0.2%的指令需要远程访问的状态下，前者比后者快多少?解:解没有远程访问时，机器的CPI为1/基本IPC=1/2=0.5有0.2%远程访问的机

器的实际CPI为CPI＝基本CPI＋远程访问率×远程访问开销＝0.5＋0.2%×远程访问开销远程访问开销为远程访问时间/时钟周期时间＝400ns/1ns＝400个时钟周期∴CPI＝0.5＋0.2%×400＝1.3因此在

没有远程访问的情况下的计算机速度是有0.2%远程访问的计算机速度的1.3/0.5=2.6倍。第6章-多处理器和线程级并行6.1.3并行处理面临的挑战3.在并行处理中，影响性能（负载平衡、同步和存储器访问延迟等）的关键因素常依赖于：应用程序的高层特

性如数据的分配，并行算法的结构以及在空间和时间上对数据的访问模式等。依据应用特点可把多机工作负载大致分成两类：单个程序在多处理机上的并行工作负载多个程序在多处理机上的并行工作负载4.并行程序的计算／通信比率反映并行程序性能的一个重要的

度量：计算与通信的比率计算／通信比率随着处理数据规模的增大而增加；随着处理器数目的增加而降低。第6章-多处理器和线程级并行6.2对称式共享存储器系统结构多个处理器共享一个存储器。当处理机规模较小时，这种计算机十分经济。支持对共享数据和私有数据的Cache缓存私有数据供一个单独的处理器

使用，而共享数据则是供多个处理器使用。共享数据进入Cache产生了一个新的问题：Cache的一致性问题第6章-多处理器和线程级并行6.2对称式共享存储器系统结构6.2.1多处理机Cache一致性1.不一致产生的原因（Cache一致性问题）I／O操作Cache中的内容可能与

由I／O子系统输入/输出形成的存储器对应部分的内容不同。共享数据不同处理器的Cache都保存有对应存储器单元的内容。第6章-多处理器和线程级并行6.2对称式共享存储器系统结构（2）时间事件CPUACache

内容CPUBCache内容X单元存储器内容011CPUA读X112CPUB读X1113CPUA将0存入X010由两个处理器（A和B）对存储器位置(X)读写引起的Cache一致性问题第6章-多处理器和线程级并行6.2对称式共享存储器系统结构（3）2.存储器的一致性（非正式定义）如果对某个

数据项的任何读操作均可得到其最新写入的值，则认为这个存储系统是一致的。存储系统行为的两个不同方面:What:读操作得到的是什么值When:什么时候才能将已写入的值返回给读操作需要满足以下条件:处理器P对单元X进行一次写之后又对单元X进行读，读和写之间没有其他处理器对单元

X进行写，则P读到的值总是前面写进去的值。第6章-多处理器和线程级并行6.2对称式共享存储器系统结构（4）处理器P对单元X进行写之后，另一处理器Q对单元X进行读，读和写之间无其他写，则Q读到的值应为P写进去的值。对同一单元的写是顺序化的，即任意两个处理

器对同一单元的两次写，从各个处理器的角度看来顺序都是相同的。(写顺序化)在后面的讨论中，假设：直到所有的处理器均看到了写的结果，这个写操作才算完成；处理器的任何访存均不能改变写的顺序。就是说，允许处理器对读进行重排序，但必须以程序规定的顺序进行写。第6章-多处理器和线程级并行6.2对称

式共享存储器系统结构（5）6.2.2增强一致性的基本方案在一致的多处理机中，Cache提供两种功能：共享数据的迁移降低了对远程共享数据的访问延迟，也减少了对共享存储器带宽的要求。共享数据的复制不仅降低了访存的延迟，也减少

了访问共享数据所产生的冲突。一般情况下，小规模多处理机采用硬件的方法来实现Cache的一致性。第6章-多处理器和线程级并行6.2对称式共享存储器系统结构（6）1.Cache一致性协议在多个处理器中用来维护一致性的协议

。关键：跟踪记录共享数据块的状态两类协议（采用不同的共享数据状态跟踪技术）目录法（directory）物理存储器中共享数据块的状态及相关信息均被保存在一个称为目录的地方。监听法（snooping）每个Cache除了包含物理存储器中块的数据副本之外，也保存

着各个块的共享状态信息。Cache通常连在共享存储器的总线上，各个Cache控制器通过监听总线来判断它们是否有总线上请求的数据块。第6章-多处理器和线程级并行6.2对称式共享存储器系统结构（7）2.两种更新协议（维持一致性要求）

写作废协议在处理器对某个数据项进行写入之前，保证它拥有对该数据项的唯一的访问权。(作废其他副本)处理器行为总线行为CPUACache内容CPUBCache内容主存单元X的内容0CPUA读XCache失效00CPUB读XCache失效00

0CPUA将1写入单元X作废X单元10CPUB读XCache失效111在写回Cache、监听总线的写无效协议示例第6章-多处理器和线程级并行6.2对称式共享存储器系统结构（8）写更新协议当一个处理器对某数据项进行写入时，通过广播使其他Cache中所有对应于该数据项的副本进行更新。处理器行为总线

行为CPUACache内容CPUBCache内容主存单元X的内容0CPUA读XCache失效00CPUB读XCache失效000CPUA将1写入单元X对单元X进行写广播111CPUB读X111在写回Cache、监听总线的情况下，写更新协

议的实现的例子第6章-多处理器和线程级并行6.2对称式共享存储器系统结构（9）写更新和写作废协议性能上的差别主要来自：在对同一个数据进行多次写操作而中间无读操作的情况下，写更新协议需进行多次写广播操

作，而写作废协议只需一次作废操作。在对同一Cache块的多个字进行写操作的情况下，写更新协议对于每一个写操作都要进行一次广播，而写作废协议仅在对该块的第一次写时进行作废操作即可。写作废是针对Cache块进行操作，而写更新

则是针对字（或字节）进行。考虑从一个处理器A进行写操作后到另一个处理器B能读到该写入数据之间的延迟时间。写更新协议的延迟时间较小。第6章-多处理器和线程级并行6.2对称式共享存储器系统结构（10）2.在写回法Ca

che条件下的实现技术Cache的标识（tag）用于实现监听。作废一个块只需将其有效位（valid）置为无效。给每个Cache块加一个特殊的状态位。状态：共享（shared）——至少一个副本，clean专有（excl

usive）——唯一副本，dirtyCache块的拥有者：拥有唯一的Cache块副本的处理器。在每个结点内嵌入一个Cache状态控制器。控制器根据来自处理器或总线的请求，改变所选择的数据块的状态。因为每次总线操作均要检查Cache的地址标识，这可能

会影响CPU对Cache的访问。可通过下列两种技术之一来减少影响：复制标志位采用多级包容Cache（许多系统采用）第6章-多处理器和线程级并行6.3分布式共享存储器系统结构存储器分布于各结点中，所有的结点通过网络互连。访问可以是本地的，也可是远程的。可以不

支持Cache一致性：规定共享数据不进入Cache，仅私有数据才能保存在Cache中。优点：所需的硬件支持很少(因为远程访问存取量仅是一个字(或双字)而不是一个Cache块)如何将支持Cache一致性的共享存储器模式扩展到可

扩缩的大规模多处理机系统?解决Cache一致性问题的关键：寻找替代监听协议的一致性协议。（采用目录协议）第6章-多处理器和线程级并行6.3分布式共享存储器系统结构（2）6.3.1基于目录的Cache一致性1.目录协议目录：一种专用的数据结构，用于记录可以进入Cache的每个数据块的状态

、哪些处理器有该块的副本以及是否修改过等信息。分布式目录目录与存储器一起分布到各结点中，从而对于不同目录内容的访问可以在不同的结点进行。特点：存储块的共享状态信息可以在唯一的一个固定单元中找到。这使一致性协议避免了广播操作。第6章-多处理器和线程级并行6.3分布式共享存储器系统

结构(3)对每个结点增加目录表后的分布式存储器多处理机的系统结构第6章-多处理器和线程级并行6.3分布式共享存储器系统结构(4)2.目录协议必须完成两种主要的操作：处理读失效处理对共享、干净（clean）块的写一个共享块的写失效处理可用这两个操作组合而成。3.目录必

须跟踪记录每个Cache块的状态存储块的状态有三种：共享在一个或多个处理器上具有这个块的副本，且存储器中的值是最新的（所有Cache中的副本均相同）。未缓冲所有处理器的Cache都没有该块的副本。专有仅有一个处理器上有该块的副本，且已对该块进行了写操作，而主存中的副本仍是旧的。这个处理器称

为该块的拥有者。第6章-多处理器和线程级并行6.3分布式共享存储器系统结构(5)4.由于写作废操作的需要，还必须记录哪些处理器有该块的副本。方法：对每个主存块设置一个位向量当该块被共享时，每个位指出与之对应的处理器是否有该块的副本。当该块为专有

时，可根据位向量来寻找其拥有者。假设：对于本地Cache中非“专有”状态Cache块的写入操作总会产生写失效，处理器封锁直到写操作完成。5.一个例子本地结点、宿主结点以及远程结点的关系本地结点：发出访问请求的结点宿主结点：包含所访问的

存储单元及其目录项的结点远程结点可以和宿主结点是同一个结点，也可以不是同一个结点。第6章-多处理器和线程级并行6.3分布式共享存储器系统结构(6)CPUCache本地结点APCache远程结点C宿主结点B(Home)副本目录存储

器K宿主结点：存放有对应地址的存储器块和目录项的结点第6章-多处理器和线程级并行6.3分布式共享存储器系统结构(7)响应访问请求时，要将宿主结点中相应的值返回给请求结点。数据写回在两种情况下发生：Cache中某个块被替换时必须写回到其宿主结点的存储器。响应宿主结点发出的取数和取数/作

废消息时也要写回。总结：目录协议的基本点在每个结点中增加了目录存储器用于存放目录。存储器的每一块在目录中有对应的一项。每一个目录项主要由两个字段构成：状态：描述所对应的存储块的当前状态。第6章-多处理器和线程级并行6.3分布式共享存储器系统结构(8)位向量：每一位对应于一个处

理器，用于指出该处理器的Cache中是否有该存储块的副本。当处理器对某一块进行写操作时，只要根据位向量通知具有相应副本的处理器进行作废操作。位向量中记录的处理器集合称为共享集合。6.3.2目录协议及其实现在基于目录的协议中，目录承担了一

致性协议操作的主要功能。发往一个目录的消息会产生两种不同类型的动作：更新目录状态发送消息以完成所请求的操作目录可能接收三种不同的请求：读失效写失效数据写回第6章-多处理器和线程级并行6.3分布式共享存储器系统结构(9)1.当一个块处于未缓冲状态时，

对该块发出的请求及目录的处理操作为：读失效将存储器数据送往请求方处理器，且该处理器成为该块的唯一共享结点，本块的状态变成共享。写失效将存储器数据送往请求方处理器，该块的状态变成专有，表示该块仅存在唯一的有效

副本。其共享集合仅包含该处理器，指出该处理器是其拥有者。第6章-多处理器和线程级并行6.3分布式共享存储器系统结构(10)2.当一个块处于共享状态时，其在存储器中的数据是当前最新的，对该块发出的请求及其处理操作为：读失效将存储器数据送往请

求方处理器，并将其加入共享集合。写失效将数据送往请求方处理器，对共享集合中所有的处理器发送写作废消息。将共享集合改为仅含有该处理器，该块的状态变为专有。第6章-多处理器和线程级并行6.3分布式共享存储器系统结构(11)3.当某块处于专有状态时

，该块的最新值保存在共享集合所指出的唯一处理器（拥有者）中。有三种可能的目录请求：读失效将“取数据”的消息发往拥有者处理器，使该块的状态转变为共享。将数据送回宿主结点写入存储器，进而把该数据送回请求方处理器，将请求方处理器加入共享集合。此时共享集合中仍保留原拥有者处理

器（因为它仍有一个可读的副本）。第6章-多处理器和线程级并行6.3分布式共享存储器系统结构(12)写失效该块将有一个新的拥有者。给旧的拥有者处理器发送消息，要求它将数据块送回宿主结点写入存储器，然后再从该结点送给请

求方处理器。把请求处理器加入共享者集合，使之成为新的拥有者。该块的状态仍旧是专有。数据写回当一个块的拥有者处理器要从其Cache中把该块替换出去时，必须将该块写回其宿主结点的存储器中，从而使存储器中相应的块中存

放的数据是最新的（宿主结点实际上成为拥有者），该块的状态变成非共享，其共享集合为空。第6章-多处理器和线程级并行6.3分布式共享存储器系统结构(13)4.对基于目录的Cache一致性的多种改进有限映射目录链式结构目录5.基于目录的Cache一致性协议是完全由硬件实现的。此外，还

可以用软硬结合的办法实现。第6章-多处理器和线程级并行6.4同步同步机制通常是在硬件提供的同步指令的基础上，通过用户级软件例程来建立的。6.4.1基本硬件原语在多处理机中实现同步，所需的主要功能是：一组能以原子操作的方式读出并修改存储单元的硬件

原语。它们能够自动读／修改单元。通常情况下，用户不直接使用基本的硬件原语，原语主要供系统程序员用来编制同步库函数。第6章-多处理器和线程级并行6.4同步（1）1.典型操作：原子交换（atomicexchan

ge）功能：将一个存储单元的值和一个寄存器的值进行交换。建立一个锁，锁值：0：表示开（可用）1：表示已上锁（不可用）处理器上锁时，将对应于该锁的存储单元的值与存放在某个寄存器中的1进行交换。如果返回值为0，存储单元的值此时已置换为1，防止了其他进程竞争该锁。实现同步的

关键：操作的原子性。2.测试并置定（test_and_set）先测试一个存储单元的值，如果符合条件则修改其值。3.读取并加1（fetch_and_increment）它返回存储单元的值并自动增加该值。第6章-

多处理器和线程级并行6.4同步（2）4.使用指令对LL(loadlinked或loadlocked)的取指令SC(storeconditional)的特殊存指令指令顺序执行：如果由LL指明的存储单元的内容在SC对其进行写之前已被其他指令改写过，则第二条指令SC执行失败。如果在两条

指令间进行切换也会导致SC执行失败。SC将返回一个值来指出该指令操作是否成功：“1”：成功“0”：不成功LL则返回该存储单元初始值。第6章-多处理器和线程级并行6.4同步（3）例：实现对由R1指出的存储单元

进行原子交换操作。try：ORR3,R4,R0//R4中为交换值。把该值送入R3LLR2,0（R1）//把单元0（R1）中的值取到R2SCR3,0（R1）//若0（R1）中的值与R3中的值相//同，则置R3的值为1，否则置为0BEQZR3,try//存失败（R

3的值为0）则转移MOVR4,R2//将取的值送往R4最终R4和由R1指向的单元值进行原子交换，在LL和SC之间如有别的处理器插入并修改了存储单元的值，SC将返回0并存入R3中，从而使这段程序再次执行。第6章-多处理器和线程级并行6.4同步（4）LL/SC机制的一个优点：用来构造

别的同步原语例如：构造原子操作fetch_and_increment：try：LLR2,0（R1）DADDIUR2,R2,#1SCR2,0（R1）BEQZR2,try指令对的实现必须跟踪地址由LL指令指定一个寄存器，该寄存器存

放着一个单元地址，这个寄存器常称为连接寄存器。第6章-多处理器和线程级并行6.4同步（5）6.4.2用一致性实现锁采用多处理机的一致性机制来实现旋转锁。旋转锁处理器环绕一个锁不停地旋转而请求获得该锁。它适合于这样的场合：锁

被占用的时间很少，在获得锁后加锁过程延迟很小。1.无Cache一致性机制在存储器中保存锁变量，处理器可以不断地通过一个原子操作请求使用权。比如：利用原子交换操作，并通过测试返回值而知道锁的使用情况。释放锁的时候，处理

器只需简单地将锁置为0。第6章-多处理器和线程级并行6.4同步（6）例如，用原子交换操作对旋转锁进行加锁，R1中存放的是该旋转锁的地址。DADDIUR2,R0,#1lockit：EXCHR2,0（R1）BNEZR2,locki

t支持Cache一致性将锁调入Cache，并通过一致性机制使锁值保持一致。优点：可使“环绕”的进程只对本地Cache中的锁（副本）进行操作，而不用在每次请求占用锁时都进行一次全局的存储器访问。可利用访问锁时所具有的局部性，即处理器最近使用过的锁不久又会使用。（减少为获

得锁而花费的时间）第6章-多处理器和线程级并行6.4同步（7）改进旋转锁（获得第一条好处）只对本地Cache中锁的副本进行读取和检测，直到发现该锁已经被释放。然后，该程序立即进行交换操作，去跟在其他处理器上的进程争用该锁变量。修改后

的旋转锁程序：lockit：LDR2,0（R1）BNEZR2,lockitDADDIUR2,R0,#1EXCHR2,0（R1）BNEZR2,lockit3个处理器利用原子交换争用旋转锁所进行的操作。第6章-多处理器和线程级并行6.4同步（8）步骤处理器P0处理器P1处理器

P2锁的状态总线/目录操作1占有锁环绕测试是否lock=0环绕测试是否lock=0共享无2将锁置为0（收到作废命令）（收到作废命令）专有(P0)P0发出对锁变量的作废消息3Cache失效Cache失效共享总线/目录收到P2Cache失效；锁从P0写回4（因总线/目录忙而等待）lock=0共享P2

Cache失效被处理5Lock=0执行交换，导致Cache失效共享P1Cache失效被处理6执行交换，导致Cache失效交换完毕：返回0并置lock=1专有(P2)总线/目录收到P2Cache失效；发作废消息7交换完毕：返回1进入关键程序

段专有(P0)总线/目录处理P1Cache失效；写回8环绕测试是否lock=0无3个处理器利用原子交换争用旋转锁所进行的操作第6章-多处理器和线程级并行6.4同步（9）LL／SC原语的另一个优点：读写操作明显分开LL不产生总线数据传送，这使下面代

码与使用经过优化交换的代码具有相同的特点：lockit：LLR2,0（R1）BNEZR2,lockitDADDIUR2,R0,#1SCR2,0（R1）BEQZR2,lockit第一个分支形成环绕的循环体，第二个分支解决了

两个处理器同时看到锁可用的情况下的争用问题。尽管旋转锁机制简单并且具有吸引力，但难以将它应用于处理器数量很多的情况。第6章-多处理器和线程级并行6.4同步（10）6.4.3同步性能问题简单旋转锁不能很好地适应可扩缩性。大规模多处理机中，若所

有的处理器都同时争用同一个锁，则会导致大量的争用和通信开销。例6.3假设某条总线上有10个处理器同时准备对同一变量加锁。如果每个总线事务处理（读失效或写失效）的时间是100个时钟周期，而且忽略对已调入Cache中的锁进行读写的时间以及占用该锁的时间。（1）假设该锁在时间为0时被释放，并

且所有处理器都在旋转等待该锁。问：所有10个处理器都获得该锁所需的总线事务数目是多少？（2）假设总线是非常公平的，在处理新请求之前，要先全部处理好已有的请求。并且各处理器的速度相同。问：处理10个请求大概需要多少时间

？第6章-多处理器和线程级并行6.4同步（11）解:当i个处理器争用锁的时候，它们都各自完成以下操作序列，每一个操作产生一个总线事务：访问该锁的i个LL指令操作试图占用该锁（并上锁）的i个SC指令操作1

个释放锁的存操作指令因此对于i个处理器来说，一个处理器获得该锁所要进行的总线事务的个数为2i+1。由此可知，对n个处理器，总的总线事务个数为：对于10个处理器来说，其总线事务数为120个，需要12000个时钟周期。n1i2n2nn)1n(n)1i2(第6章-多处理器和线程级并行6.

4同步（12）本例中问题的根源：锁的争用、对锁进行访问的串行性以及总线访问的延迟。旋转锁的主要优点：总线开销或网络开销比较低，而且当一个锁被同一个处理器重用时具有很好的性能。1.如何用旋转锁来实现一个常用的高级同步原语：栅栏栅栏强制所有到达该栅栏的进程进行等待，直

到全部的进程到达栅栏，然后释放全部的进程，从而形成同步。栅栏的典型实现用两个旋转锁：用来保护一个计数器，它记录已到达该栅栏的进程数；用来封锁进程直至最后一个进程到达该栅栏。第6章-多处理器和线程级并行6.4同步（13）一种典型的实现其

中：lock和unlock提供基本的旋转锁变量count记录已到达栅栏的进程数total规定了要到达栅栏的进程总数第6章-多处理器和线程级并行6.4同步（14）lock（counterlock）；//if（count==0）releas

e=0；//第一个进程则重置releasecount=count+1；//到达进程数加1unlock（counterlock）；//if（count==total）{//count=0；//release=1；//｝else{//spi

n（release=1）；//｝实现一个简单栅栏的代码第6章-多处理器和线程级并行6.4同步（15）对counterlock加锁保证增量操作的原子性。release用来封锁进程直到最后一个进程到达栅栏。spin（release=1）使进程等待直到全部的

进程到达栅栏。实际情况中会出现的问题可能反复使用一个栅栏，栅栏释放的进程运行一段后又会再次返回栅栏，这样有可能出现某个进程永远离不开栅栏的状况(它停在旋转操作上)。一种解决方法当进程离开栅栏时进行计数（和到达时一

样），在上次栅栏使用中的所有进程离开之前，不允许任何进程重用并初始化本栅栏。但这会明显增加栅栏的延迟和竞争。第6章-多处理器和线程级并行6.4同步（16）另一种解决办法采用sense_reversing栅栏，每个进程均

使用一个私有变量local_sense，该变量初始化为1。sense_reversing栅栏的代码。优缺点：使用安全，但性能比较差。对于10个处理器来说，当同时进行栅栏操作时，如果忽略对Cache的访问时间以及其他非同步操作

所需的时间，则其总线事务数为204个，如果每个总线事物需要100个时钟周期，则总共需要20400个时钟周期。第6章-多处理器和线程级并行6.4同步（16）local_sense=!local_sense；//local-s

enselock（counterlock）；//count++；//到达进程数加1unlock（counterlock）；//if（count==total）{//count=0；//release=local_sense；//｝els

e{//spin（release==local_sense）；//｝判断－反转栅栏的代码第6章-多处理器和线程级并行6.4同步（17）2.当竞争不激烈且同步操作较少时，我们主要关心的是一个同步原语操作的延迟。即单个进程要花多长时间才完成一个同步操

作。基本的旋转锁操作可在两个总线周期内完成：一个读锁一个写锁我们可用多种方法改进，使它在单个周期内完成操作。3.同步操作最严重的问题：进程进行同步操作的顺序化。它极大地增加了同步操作的时间。第6章-多处理器和线程级并行6.5多线程:在

单个处理器中开发线程级并行线程级并行性（ThreadLevelParallelism，TLP）线程是指具有自己的程序和数据的进程。它可以是一个并行执行程序的一部分，也可以是一个独立的程序。每个线程包含自己执行所需要的状态

，包括指令、数据、程序计数器、寄存器状态等。多线程使多个线程以重叠的方式共享单个处理器的功能单元。硬件必须对较快地完成线程间的切换提供支持。线程的切换应该比进程的切换高效得多。进程的切换一般需要成百上千个处理器时钟周期。第6章-多处理器和线程级并行6.5多线程:在单个处

理器中开发线程级并行实现多线程有两种主要的方法：细粒度（fine-grained）多线程技术在每条指令之间都能进行线程的切换，从而导致多个线程的交替执行。通常以时间片轮转的方法实现这样的交替执行，在轮转的过程中跳过当时处于停顿的线程

。CPU必须在每个时钟周期都能进行线程的切换。主要优点：既能够隐藏由长时间停顿引起的吞吐率的损失，又能够隐藏由短时间停顿带来的损失。主要缺点：减慢了每个独立线程的执行第6章-多处理器和线程级并行6.5多线程:在单个处理器中开发线程级并行粗粒度（coarse-grained）

多线程技术线程之间的切换只发生在时间较长的停顿出现时。例如：第二级Cache失效。减少了切换次数，也不太会降低单个线程的执行速度。缺点：减少吞吐率损失的能力有限，特别是对于较短的停顿来说更是如此。原因：由粗粒度多线程的流水线建立时间的开销造成的。由于实现粗

粒度多线程的CPU只执行单个线程的指令，因此当发生停顿时，流水线必须排空或暂停。停顿后切换的新的线程在第一条指令执行完之前必须先填满整个流水线。第6章-多处理器和线程级并行6.5多线程:在单个处理器中开发线程级并行6.5.1将线程级并行转换为指令级并行并发多线程技术

SimultaneousMultiThreading，SMT一种在多流出、动态调度的处理器上同时开发线程级并行和指令级并行的技术。1.提出SMT的主要原因现代多流出处理器通常含有多个并行的功能单元，而单个线程不能有效地利用这些功能单元。通过寄存器

重命名和动态调度机制，来自各个独立线程的多条指令可以同时流出，而不用考虑它们之间的相互依赖关系，其相互依赖关系将通过动态调度机制得以解决。第6章-多处理器和线程级并行6.5多线程:在单个处理器中开发线程级并行2.一个超标量处理器在4种情况下的资源使用情况：不支持多线程技术的超标量处

理器由于缺乏足够的指令级并行而限制了流出槽的利用率。支持粗粒度多线程的超标量处理器通过线程的切换部分隐藏了长时间停顿带来的开销，提高了硬件资源的利用率。只有发生停顿时才进行线程切换，而且新线程还有个启动期，所以仍然

可能有一些完全空闲的时钟周期。第6章-多处理器和线程级并行6.5多线程:在单个处理器中开发线程级并行超标量处理器中使用流出槽的4种方法第6章-多处理器和线程级并行6.5多线程:在单个处理器中开发线程级并行支持细

粒度多线程的超标量处理器线程的交替执行消除了完全空闲的时钟周期。由于在每个时钟周期内只能流出一个线程的指令，ILP的限制导致了一些时钟周期中依然存在不少空闲流出槽。支持同时多线程的超标量处理器在

同一个时钟周期中可以让多个线程使用流出槽。理想情况下，流出槽的利用率只受限于多个线程对资源的需求和可用资源间的不平衡。第6章-多处理器和线程级并行6.5多线程:在单个处理器中开发线程级并行3.开发的基础:动态调度的处理器已经具备了开发线程级并行所需的许多硬件设置。动态调度超标量处理器

有一组虚拟寄存器，可以用作各独立线程的寄存器组。由于寄存器重命名机制给各寄存器提供了唯一的标识，多个线程的指令可以在数据路径上混合执行，而不会导致各线程之间源操作数和目的操作数的混乱。多线程可以在一个乱序执行的处理器

的基础上实现，只要为每个线程设置重命名表、分别设置各自的程序计数器并为多个线程提供指令确认的能力。第6章-多处理器和线程级并行6.5多线程:在单个处理器中开发线程级并行6.5.2同时多线程处理器的设计1.同

时多线程只有在细粒度的实现方式下才有意义2.细粒度调度方式会对单个线程的性能产生不利的影响可以通过指定优先线程来减小这种影响，既能保持多线程在性能上的优势，又对单个线程的性能影响比较少。3.多个线程的混合执行不可避免地会影响单个线程的执行速度为提高单个线程的性能，应该为指定的优先线程

尽可能多地向前取指（或许在分支指令的两条路径上都要向前取指）。在分支预测失效和预取缓冲失效的情况下需要清空取指单元。但是这样限制了其他线程可用来调度的指令条数，从而减少了吞吐率。所有的多线程处理器都必须在这里寻求一种折中方

案。第6章-多处理器和线程级并行6.5多线程:在单个处理器中开发线程级并行只要一有可能，处理器就运行指定的优先线程。从取指阶段开始就优先处理优先线程：只要优先线程的指令预取缓冲区未满，就为它们优先取指。只有当优先线程的缓冲区填满以后才为其

他线程预取指令。当有两个优先线程时，意味着需要并发预取两条指令流，这给取指部件和指令Cache都增添了复杂度。指令流出单元也要优先考虑指定的优先线程，只有当优先线程停顿不能流出的时候才考虑其他线程。第6章-多处理器和线程级并行6.

5多线程:在单个处理器中开发线程级并行4.设计同时多线程处理器时面临的其他主要问题：需要设置更大的寄存器组，用来保存多个线程的现场。不能影响时钟周期，特别是在关键路径上。如指令流出和指令完成：指令流出时，有更多的候选指令需要考虑。指令完成时，选择提交哪些指令可能会比较

困难。需要保证由于并发执行多个线程带来的Cache冲突和TLB冲突不会导致明显的性能下降。5.需要重视的两个实际情况：在许多情况下，多线程所导致的潜在额外性能开销是很小的，简单的线程切换选择算法就足够好了。目前的超标量处理器的效率是比较低的，还有很大的改进余地，即使增加一些开销也是值

得的。第6章-多处理器和线程级并行6.5多线程:在单个处理器中开发线程级并行SMT与基本的超标量处理器在几个主要指标上的对比第6章-多处理器和线程级并行6.5多线程:在单个处理器中开发线程级并行两个特点超标量处理器本

身功能十分强大，它具有很大的一级Cache、二级Cache以及大量的功能单元。仅仅采用指令级并行，不可能利用全部的硬件性能，因此超标量处理器的设计者不可能不考虑使用诸如同时多线程这样的技术来开发线程级并行。同时多线程的能力也很强大，可以支持8个线程，并为两个线程同步取指。将超标量和同时多线程结合

起来，在指令级并行基础上进一步开发线程级并行，可以获得显著的性能提高。第6章-多处理器和线程级并行6.6多处理机实例1.Origin2000是一个分布共享存储器结构的大规模并行多处理机系统，采用超结点的模块结构，可以从1个处理器扩展到128个处理器。2.Origin2000采用超标量MIPSR

10000处理器，运行UNIX的64位IRIX操作系统。3.Origin是基于NUMA系统结构第6章-多处理器和线程级并行6.6多处理机实例第6章-多处理器和线程级并行6.6多处理机实例每个结点可安装1个或2个MIPSR10000微处理

器、第二级高速缓存（L2Cache）、主存储器、目录存储器及Hub等，Hub用于连接微处理器、存储器、I／O和路由器等。Origin存储器系统每个结点的主存储器容量:4GB结点的Hub内含4个接口和交叉开关存储器最大传输率为780MbpsI／O和路由器接口最大传输率:

2×780Mbs(1.56Gbps)Origin的路由器有6个端口，用于连接结点或其他路由器。Origin的路由器和互连网络是ASIC芯片，通过芯片内部的交叉开关选择数据传送路径。第6章-多处理器和线程级并行6.6多处理机实例4.两个结点互连的情况Origin系统可由1～128个处理器组成

。第6章-多处理器和线程级并行6.6多处理机实例5.由8结点构成的16处理器系统为了减少数据在路由器之间的传送延迟，加快传送速度，可将处于对角位置的路由器进行连接。第6章-多处理器和线程级并行6.6多处理机实例

6.128处理器系统128处理器构成的Origin2000系统由4个立方体组成，在立方体之间传送数据多经过了一级路由器。在结点内部实现的是SMP（对称多处理器）结构，由于只有两个处理器，所以不存在SMP结构的总线瓶颈问题。在结点之间实现的是大规模并行处理结构，但又解决了共

享存储器问题。因此在Origin系统中，无论是访问存储器的时间还是结点间传送数据的带宽都很理想。第6章-多处理器和线程级并行6.6多处理机实例第6章-多处理器和线程级并行6.6多处理机实例7.Origin系统中CPU访问存储器的延迟时间假设：CPU的主频为195

MHzCache不命中最小延迟时间：CPU访问本结点存储器的时间最大延迟时间：CPU访问距离最远的存储器的时间第6章-多处理器和线程级并行6.6多处理机实例Origin系统中CPU访问存储器的延迟时间系统CPU数最小延迟

时间最大延迟时间平均延迟时间2318ns343ns343ns4318ns554ns441ns8318ns759ns623ns16318ns759ns691ns32318ns836ns764ns64318ns1067ns851ns128318ns1169ns959ns第6章-多处理器和线程

级并行6.6多处理机实例8.Origin系统的带宽每个Hub连到路由器和互连网络的最大频宽为1.56Gbps（全双工，2×780Mbps）系统处理器数带宽（无快速传送连线）带宽（无快速传送连线）81.56Gbps3.12Gbps163.12Gbps6.

24Gbps326.24Gbps12.5Gbps6412.5Gbps--12825Gbps--第6章-多处理器和线程级并行6.6多处理机实例9.Origin系统的存储器层次结构可分为：寄存器、L1Cache、L2Cache和主存储器寄存器和L1Cache在R10000微处理

器中寄存器的存取时间最短L1Cache又分成指令Cache和数据Cache两部分（避免取指令和存/取数据发生冲突）L2Cache安装在结点卡中，统一存放指令和数据，由SRAM组成。主存储器地址是统一编址的，每个处理器通过互连网络可访问系统中任一存储单元。第6章-多处理器和线程级并行6

.6多处理机实例10.实现Cache的一致性基于目录协议与写作废协议每个结点中，有一个存储器和一个目录存储器。每块对应于一个目录项，每个目录项包含其对应存储器块的状态信息和系统中各Cache共享该存储块情况的位向量

，根据位向量可以知道哪些Cache中有其副本。第6章-多处理器和线程级并行(END)