《计算机体系结构(张晨曦)第8章_PPT.ppt》由会员分享，可在线阅读，更多相关《计算机体系结构(张晨曦)第8章_PPT.ppt（104页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 1/104/104第8章 多处理机张晨曦张晨曦 刘依刘依www.GotoS2 2/104/1048.1引言8.2对称式共享存储器系统结构8.3分布式共享存储器系统结构8.4同步8.5同时多线程8.6多处理机实例3 3/104/1048.1 引 言1.单处理机系统结构正在走向尽头？2.多处理机正起着越来越重要的作用。近两年来，我们已经开始进入多处理机将起主要作用的新时期。期望：将来更加普及问题：q如何发挥其潜在计算能力？如何发挥其潜在计算能力？（并行程序）（并行程序）q应用是否具有足够的并行性？应用是否具有足够的并行性？并行计算机应用软件已有了稳定的发展。（尽管缓慢）（尽管缓慢）并行处理已经
2、成为重要和主流的技术。3.本章重点：中小规模的计算机(处理器的个数128)（多处理机设计的主流）4 4/104/1048.1 引 言1.Flynn分类法 SISD、SIMD、MISD、MIMD2.MIMD已成为通用多处理机系统结构的选择，原因：MIMD具有灵活性。MIMD可以充分利用商品化微处理器在性能价格比方面的优势。计算机机群系统（计算机机群系统（clustercluster）是一类广泛被采用是一类广泛被采用的的MIMDMIMD计算机。计算机。8.1.1 并行计算机系统结构的分类 5 5/104/1048.1 引 言1.根据系统中处理器个数的多少，可把现有的MIMD计算机分为两类：（每一类
3、代表了一种存储器的结构和互连策略）（每一类代表了一种存储器的结构和互连策略）集中式共享存储器结构 动画q最多由几十个处理器构成。最多由几十个处理器构成。q通过大容量的通过大容量的CacheCache和总线互连使各处理器共享一个和总线互连使各处理器共享一个单独的物理存储器。单独的物理存储器。这类计算机有时被称为这类计算机有时被称为 qSMPSMP计算机计算机 （Symmetric shared-memory Symmetric shared-memory MultiProcessorMultiProcessor）qUMAUMA计算机计算机（Uniform Memory AccessUniform
4、 Memory Access）6 6/104/1048.1 引 言对称式共享存储器多处理机的基本结构对称式共享存储器多处理机的基本结构7 7/104/1048.1 引 言分布式存储器结构 动画q每个结点包含：每个结点包含：n处理器处理器n存储器存储器nI IO On互连网络接口互连网络接口q在许多情况下，分布式存储器结构在许多情况下，分布式存储器结构优于优于集中式共享存集中式共享存储器结构。储器结构。8 8/104/1048.1 引 言9 9/104/1048.1 引 言q分布式存储器结构的分布式存储器结构的优点优点n如果大多数的访问是针对本结点的局部存储器，则如果大多数的访问是针对本结点的局
5、部存储器，则可降低对存储器和互连网络的带宽要求。可降低对存储器和互连网络的带宽要求。n对局部存储器的访问延迟低。对局部存储器的访问延迟低。q最主要的最主要的缺点缺点n处理器之间的通信较为复杂，且各处理器之间访问处理器之间的通信较为复杂，且各处理器之间访问延迟较大。延迟较大。q簇：簇：超级结点超级结点 n每个结点内包含个数较少（例如每个结点内包含个数较少（例如2 28 8）的处理器；）的处理器；n处理器之间可采用另一种互连技术（例如总线）相处理器之间可采用另一种互连技术（例如总线）相互连接形成簇。互连接形成簇。1010/104/1048.1 引 言1.地址空间的组织方案（两种）共享地址空间 q物
6、理上分离的多个存储器作为一个逻辑上共享的存物理上分离的多个存储器作为一个逻辑上共享的存储空间进行编址。储空间进行编址。q任何一个处理器可以访问该共享空间中的任何一个任何一个处理器可以访问该共享空间中的任何一个单元（如果它具有访问权），而且不同处理器上的单元（如果它具有访问权），而且不同处理器上的同一个物理地址指向的是同一个存储单元。同一个物理地址指向的是同一个存储单元。q这类机器的结构被称为这类机器的结构被称为 分布式共享存储器结构分布式共享存储器结构 （DSMDSM:Distributed Shared-Memory):Distributed Shared-Memory)NUMA NUMA机
7、器机器 （NUMANUMA:Non-Uniform Memory Access):Non-Uniform Memory Access)8.1.2 通信模型和存储器的结构模型 1111/104/1048.1 引 言整个地址空间由多个独立的地址空间构成，它们在逻辑上也是独立的，远程的处理器不能对其直接寻址。q每一个每一个处理器处理器-存储器存储器模块实际上是一台单独的计算机模块实际上是一台单独的计算机q现在的这种机器多以集群的形式存在现在的这种机器多以集群的形式存在2.两种通信机制 共享地址空间的机器 利用利用loadload和和storestore指令中的地址隐含地进行数据通信。指令中的地址隐含
8、地进行数据通信。多个地址空间的机器 通过处理器间显式地传递消息来完成。通过处理器间显式地传递消息来完成。（消息传递多处理机）（消息传递多处理机）1212/104/1048.1 引 言q消息传递计算机通过传递消息来请求某些服务或传输数据，消息传递计算机通过传递消息来请求某些服务或传输数据，从而完成通信。从而完成通信。例如：例如：一个处理器要对远程存储器上的数据进行访问或操作：一个处理器要对远程存储器上的数据进行访问或操作：n发送消息，请求传递数据或对数据进行操作；发送消息，请求传递数据或对数据进行操作；远程进程调用远程进程调用(RPC(RPC，Remote Process Call)Remote
9、 Process Call)n目的处理器接收到消息以后，执行相应的操作或代替目的处理器接收到消息以后，执行相应的操作或代替远程处理器进行访问，并发送一个应答消息将结果返远程处理器进行访问，并发送一个应答消息将结果返回。回。q同步消息传递同步消息传递 请求处理器发送一个请求后一直要等到应答结果才继续运行。请求处理器发送一个请求后一直要等到应答结果才继续运行。1313/104/1048.1 引 言q异步消息传递异步消息传递 发送方不经请求就直接把数据送往数据接收方。发送方不经请求就直接把数据送往数据接收方。3.通信机制的性能指标（3个）通信带宽 理想状态下的通信带宽受限于处理器、存储器和互连网理想
10、状态下的通信带宽受限于处理器、存储器和互连网络的带宽。络的带宽。通信延迟理想状态下通信延迟应尽可能地小。理想状态下通信延迟应尽可能地小。通信延迟发送开销跨越时间传输延迟接收开销通信延迟发送开销跨越时间传输延迟接收开销 q跨越时间跨越时间：数字信号从发送方的线路端传送到接收方：数字信号从发送方的线路端传送到接收方的线路端所经过的时间。的线路端所经过的时间。q传输时间传输时间：全部的消息量除以线路带宽。：全部的消息量除以线路带宽。1414/104/1048.1 引 言通信延迟的隐藏q如何才能较好地将通信和计算或多次通信之间重叠起如何才能较好地将通信和计算或多次通信之间重叠起来，以实现通信延迟的隐藏
11、。来，以实现通信延迟的隐藏。q通常的原则：通常的原则：只要可能就隐藏延迟。只要可能就隐藏延迟。q通信延迟隐藏是一种提高性能的有效途径，但它对操通信延迟隐藏是一种提高性能的有效途径，但它对操作系统和编程者来讲增加了额外的负担。作系统和编程者来讲增加了额外的负担。1.不同通信机制的优点 共享存储器通信的主要优点 q与常用的对称式多处理机使用的通信机制兼容。与常用的对称式多处理机使用的通信机制兼容。q易于编程，同时在简化编译器设计方面也占有优势。易于编程，同时在简化编译器设计方面也占有优势。1515/104/1048.1 引 言q当通信数据量较小时，通信开销较低，带宽利用较好。当通信数据量较小时，通
12、信开销较低，带宽利用较好。q通过硬件控制的通过硬件控制的CacheCache减少了远程通信的频度，减少了减少了远程通信的频度，减少了通信延迟以及对共享数据的访问冲突。通信延迟以及对共享数据的访问冲突。消息传递通信机制的主要优点q硬件较简单。硬件较简单。q通信是显式的，因此更容易搞清楚何时发生通信以及通通信是显式的，因此更容易搞清楚何时发生通信以及通信开销是多少，以便编程者和编译程序设法减少通信开信开销是多少，以便编程者和编译程序设法减少通信开销。销。1616/104/1048.1 引 言可在支持上面任何一种通信机制的硬件模型上建立所需的通信模式平台。q在共享存储器上支持消息传递相对简单。在共享
13、存储器上支持消息传递相对简单。q在消息传递的硬件上支持共享存储器就困难得多。在消息传递的硬件上支持共享存储器就困难得多。所有对共享存储器的访问均要求操作系统提供地址所有对共享存储器的访问均要求操作系统提供地址转换和存储保护功能，即将存储器访问转换为消息转换和存储保护功能，即将存储器访问转换为消息的发送和接收。的发送和接收。1717/104/1048.1 引 言并行处理面临着两个重要的挑战程序中的并行性有限相对较高的通信开销8.1.3 并行处理面临的挑战 系统加速比系统加速比 =1818/104/1048.1 引 言1.第一个挑战有限的并行性使机器要达到好的加速比十分困难。例例8.18.1 假设
14、想用假设想用100100个处理器达到个处理器达到8080的加速比，求原计算程的加速比，求原计算程序中串行部分最多可占多大的比例？序中串行部分最多可占多大的比例？解解 AmdahlAmdahl定律为定律为由上式可得，由上式可得，并行比例并行比例0.99750.9975 1919/104/1048.1 引 言1.第二个挑战：多处理机中远程访问的延迟较大在现有的计算机中，处理器之间的数据通信大约需要1001000个时钟周期。主要取决于：通信机制、互连网络的种类和计算机的规模通信机制、互连网络的种类和计算机的规模 在几种不同的共享存储器并行计算机中远程访问一个字的典型延迟 2020/104/1048.
15、1 引 言计算机类型 通信机制 互连网络 处理机最大数量 典型远程存储器访问时间（ns）Sun Sun StarfireStarfire servers servers SMP SMP 多总线多总线 64 64 500 500 SGI Origin 3000 SGI Origin 3000 NUMA NUMA 胖超立方体胖超立方体 512 512 500 500 Cray T3E Cray T3E NUMA NUMA 3 3维环网维环网 2048 2048 300 300 HP V series HP V series SMP SMP 8 88 8交叉开关交叉开关 32 32 1000 100
16、0 HP HP AlphaServerAlphaServer GS GS SMP SMP 开关总线开关总线 32 32 400 400 2121/104/1048.1 引 言 例例8.28.2 假设有一台假设有一台3232个处理器的多处理机，对远程存储器个处理器的多处理机，对远程存储器访问时间为访问时间为400400 nsns。除了通信以外，假设所有其他访问均命中局除了通信以外，假设所有其他访问均命中局部存储器。当发出一个远程请求时，本处理器挂起。处理器的时部存储器。当发出一个远程请求时，本处理器挂起。处理器的时钟频率为钟频率为1 1 GHzGHz，如果指令基本的如果指令基本的IPCIPC为为
17、2 2（设所有访存均命中（设所有访存均命中CacheCache），），求在没有远程访问的情况下和有求在没有远程访问的情况下和有0.2%0.2%的指令需要远程的指令需要远程访问的情况下，前者比后者快多少访问的情况下，前者比后者快多少?2222/104/1048.1 引 言解解 没有远程访问时，机器的没有远程访问时，机器的CPICPI为为 1/1/基本基本IPC=1/2=0.5IPC=1/2=0.5 有有0.2%0.2%远程访问的机器的实际远程访问的机器的实际CPICPI为为 CPICPI基本基本CPICPI远程访问率远程访问率远程访问开销远程访问开销 0.50.50.2%0.2%远程访问开销远程
18、访问开销 远程访问开销为远程访问开销为 远程访问时间远程访问时间/时钟周期时间时钟周期时间400400 ns/1ns/1 nsns400400个时钟周期个时钟周期 CPICPI0.50.50.2%0.2%4004001.31.3 因此在没有远程访问的情况下的计算机速度是有因此在没有远程访问的情况下的计算机速度是有0.2%0.2%远程远程访问的计算机速度的访问的计算机速度的1.3/0.5=2.61.3/0.5=2.6倍倍。2323/104/1048.1 引 言问题的解决q并行性不足：并行性不足：采用并行性更好的算法采用并行性更好的算法q远程访问延迟的降低：靠系统结构支持和编程技术远程访问延迟的降
19、低：靠系统结构支持和编程技术 3.在并行处理中，影响性能（负载平衡、同步和存储器访问延迟等）的关键因素常依赖于：应用程序的高层特性 如数据的分配，并行算法的结构以及在空间和如数据的分配，并行算法的结构以及在空间和时间上对数据的访问模式等。时间上对数据的访问模式等。依据应用特点可把多机工作负载大致分成两类：q单个程序在多处理机上的并行工作负载单个程序在多处理机上的并行工作负载q多个程序在多处理机上的并行工作负载多个程序在多处理机上的并行工作负载2424/104/1048.1 引 言4.并行程序的计算通信比率反映并行程序性能的一个重要的度量：计算与通信的比率计算与通信的比率计算通信比率随着处理数据
20、规模的增大而增加；随着处理器数目的增加而降低。2525/104/104多个处理器共享一个存储器。当处理机规模较小时，这种计算机十分经济。教材中图教材中图8.18.1是这种计算机的一个简单示意图。是这种计算机的一个简单示意图。支持对共享数据和私有数据的Cache缓存 私有数据供一个单独的处理器使用，而共享数据私有数据供一个单独的处理器使用，而共享数据则是供多个处理器使用。则是供多个处理器使用。共享数据进入Cache产生了一个新的问题 CacheCache的一致性问题的一致性问题8.2 对称式共享存储器系统结构2626/104/1048.2 对称式共享存储器系统结构1.不一致产生的原因（Cache
21、一致性问题）IO操作 CacheCache中的内容可能与由中的内容可能与由I IO O子系统输入子系统输入/输出形输出形成的存储器对应部分的内容不同。成的存储器对应部分的内容不同。共享数据 不同处理器的不同处理器的CacheCache都保存有对应存储器单元的内容。都保存有对应存储器单元的内容。例两个处理器的读写8.2.1 多处理机Cache一致性2727/104/1048.2 对称式共享存储器系统结构由两个处理器（由两个处理器（A A和和B B）读写引起的读写引起的CacheCache一致性问题一致性问题 时间时间 事件事件 CPU A Cache CPU A Cache 内容内容 CPU B
22、 Cache CPU B Cache 内容内容 X单元存储器内容 0 011 CPU A1 CPU A读读X X 1 112 CPU B2 CPU B读读X X 1 11 113 CPU A3 CPU A将将0 0存入存入X X 0 01 102828/104/1048.2 对称式共享存储器系统结构1.存储器的一致性（非正式定义）如果对某个数据项的任何读操作均可得到其最新写入的值，则认为这个存储系统是一致的。存储系统行为的两个不同方面qWhat:What:读操作得到的是什么值读操作得到的是什么值qWhen:When:什么时候才能将已写入的值返回给读操作什么时候才能将已写入的值返回给读操作需要满
23、足以下条件q处理器处理器P P对单元对单元X X进行一次写之后又对单元进行一次写之后又对单元X X进行读，进行读，读和写之间没有其他处理器对单元读和写之间没有其他处理器对单元X X进行写，则进行写，则P P读读到的值总是前面写进去的值。到的值总是前面写进去的值。2929/104/1048.2 对称式共享存储器系统结构q处理器处理器P P对单元对单元X X进行写之后，另一处理器进行写之后，另一处理器Q Q对单元对单元X X进进行读，读和写之间无其他写，则行读，读和写之间无其他写，则Q Q读到的值应为读到的值应为P P写进写进去的值。去的值。q对同一单元的写是顺序化的，即任意两个处理器对同对同一单
24、元的写是顺序化的，即任意两个处理器对同一单元的两次写，从各个处理器的角度看来顺序都是一单元的两次写，从各个处理器的角度看来顺序都是相同的。相同的。(写顺序化写顺序化 )在后面的讨论中，我们假设：q直到所有的处理器均看到了写的结果，这个写操作才直到所有的处理器均看到了写的结果，这个写操作才算完成；算完成；q处理器的任何访存均不能改变写的顺序。就是说，允处理器的任何访存均不能改变写的顺序。就是说，允许处理器对读进行重排序，但必须以程序规定的顺序许处理器对读进行重排序，但必须以程序规定的顺序进行写。进行写。3030/104/1048.2 对称式共享存储器系统结构在一致的多处理机中，Cache提供两种
25、功能：共享数据的迁移 降低了对远程共享数据的访问延迟，也减少了降低了对远程共享数据的访问延迟，也减少了对共享存储器带宽的要求。对共享存储器带宽的要求。共享数据的复制 不仅降低了访存的延迟，也减少了访问共享数据不仅降低了访存的延迟，也减少了访问共享数据所产生的冲突。所产生的冲突。一般情况下，小规模多处理机采用硬件的方法来实现Cache的一致性。8.2.2 实现一致性的基本方案3131/104/1048.2 对称式共享存储器系统结构1.Cache一致性协议 在多个处理器中用来维护一致性的协议。关键：跟踪记录共享数据块的状态 两类协议（采用不同的共享数据状态跟踪技术）q目录法目录法（director
26、ydirectory）物理存储器中共享数据块的状态及相关信息均被物理存储器中共享数据块的状态及相关信息均被保存在一个称为目录的地方。保存在一个称为目录的地方。q监听法监听法（snoopingsnooping）n每个每个CacheCache除了包含物理存储器中块的数据副本除了包含物理存储器中块的数据副本之外，也保存着各个块的共享状态信息。之外，也保存着各个块的共享状态信息。3232/104/1048.2 对称式共享存储器系统结构nCacheCache通常连在共享存储器的总线上，各个通常连在共享存储器的总线上，各个CacheCache控制器通过监听总线来判断它们是否有总线上请控制器通过监听总线来判
27、断它们是否有总线上请求的数据块。求的数据块。2.两种更新协议（维持一致性要求）写作废协议 在处理器对某个数据项进行写入之前，保证它拥在处理器对某个数据项进行写入之前，保证它拥有对该数据项的唯一的访问权。有对该数据项的唯一的访问权。(作废其他副本作废其他副本)3333/104/1048.2 对称式共享存储器系统结构处理器行为处理器行为 总线行为总线行为 CPU ACPU A Cache Cache内容内容 CPU B CPU B CacheCache内容内容 主存单元主存单元X X的内容的内容 0 0CPU A CPU A 读读X X CacheCache失效失效 0 00 0CPU B CPU
28、 B 读读X X CacheCache失效失效 0 00 00 0CPU ACPU A将将1 1写入单元写入单元X X 作废作废X X单元单元 1 10 0CPU B CPU B 读读X X CacheCache失效失效 1 11 11 1例例 在在写回写回CacheCache、监听总线监听总线的情况下，的情况下，写作废协议写作废协议的实现的实现3434/104/1048.2 对称式共享存储器系统结构写更新协议 当一个处理器对某数据项进行写入时，通过广播当一个处理器对某数据项进行写入时，通过广播使其他使其他CacheCache中所有对应于该数据项的副本进行更新。中所有对应于该数据项的副本进行更
29、新。例例 在写回在写回CacheCache、监听总线监听总线的情况下，的情况下，写更新协议的实现。写更新协议的实现。处理器行为处理器行为 总线行为总线行为 CPU A CPU A CacheCache内容内容 CPU B CPU B CacheCache内容内容 主存单元主存单元X X的内容的内容 0 0CPU A CPU A 读读X X CacheCache失效失效 0 00 0CPU B CPU B 读读X X CacheCache失效失效 0 00 00 0CPU ACPU A将将1 1写入单元写入单元X X 对单元对单元X X进进行行写广播写广播 1 11 11 1CPU B CPU
30、B 读读X X 1 11 11 13535/104/1048.2 对称式共享存储器系统结构写更新和写作废协议性能上的差别主要来自：q在对同一个数据进行多次写操作而中间无读操作的情在对同一个数据进行多次写操作而中间无读操作的情况下，写更新协议需进行多次写广播操作，而写作废况下，写更新协议需进行多次写广播操作，而写作废协议只需一次作废操作。协议只需一次作废操作。q在对同一在对同一CacheCache块的多个字进行写操作的情况下，写更块的多个字进行写操作的情况下，写更新协议对于每一个写操作都要进行一次广播，而写作新协议对于每一个写操作都要进行一次广播，而写作废协议仅在对该块的第一次写时进行作废操作即
31、可。废协议仅在对该块的第一次写时进行作废操作即可。写作废是针对写作废是针对CacheCache块进行操作，而写更新则是针块进行操作，而写更新则是针对字（或字节）进行。对字（或字节）进行。q考虑从一个处理器考虑从一个处理器A A进行写操作后到另一个处理器进行写操作后到另一个处理器B B能能读到该写入数据之间的延迟时间。读到该写入数据之间的延迟时间。写更新协议的延迟时间较小。写更新协议的延迟时间较小。3636/104/1048.2 对称式共享存储器系统结构1.小规模多处理机中实现写作废协议的关键利用总线进行作废操作：把要作废的地址放到总线上 （一个放，多个读）（一个放，多个读）写操作的顺序性：由总
32、线实现 （获取总线控制权的顺序性）（获取总线控制权的顺序性）写直达Cache：因为所有写的数据同时被写回主存，所以从主存中总可以取到最新的数据值。对于写回Cache，得到数据的最新值会困难一些，因为最新值可能在某个Cache中，也可能在主存中。8.2.3 监听协议及其实现3737/104/1048.2 对称式共享存储器系统结构1.在写回法Cache条件下的实现技术Cache的标识（tag）用于实现监听。作废一个块只需将其有效位（valid）置为无效。给每个Cache块加一个特殊的状态位。状态：状态：q共享共享（sharedshared）至少一个副本，至少一个副本，cleancleanq专有专有
33、（exclusiveexclusive）唯一副本，唯一副本，dirtydirty Cache块的拥有者：拥有唯一的Cache块副本的处理器。3838/104/1048.2 对称式共享存储器系统结构在每个结点内嵌入一个Cache状态控制器。控制器根据来自处理器或总线的请求，改变所控制器根据来自处理器或总线的请求，改变所选择的数据块的状态。选择的数据块的状态。因为每次总线操作均要检查Cache的地址标识，这可能会影响CPU对Cache的访问。可通过下列两种技术之一来减少影响：q复制标志位复制标志位q采用多级包容采用多级包容CacheCache （许多系统采用）许多系统采用）3939/104/104
34、 存储器分布于各结点中，所有的结点通过网络互连。访问可以是本地的，也可是远程的。可以不支持Cache一致性：规定共享数据不进入Cache，仅私有数据才能保存在Cache中。优点：所需的硬件支持很少所需的硬件支持很少 (因为远程访问存取量仅是一个字因为远程访问存取量仅是一个字(或双字或双字)而不是一而不是一个个CacheCache块块)如何将支持如何将支持CacheCache一致性的共享存储器模式扩展一致性的共享存储器模式扩展到可扩缩的大规模多处理机系统到可扩缩的大规模多处理机系统?8.3 分布式共享存储器系统结构4040/104/1048.3 分布式共享存储器系统结构解决Cache一致性问题的
35、关键：寻找替代监听协议的一致性协议。（采用目录协议）8.3.1 基于目录的Cache一致性1.目录协议目录：一种专用的数据结构，用于记录可以进入Cache的每个数据块的状态、哪些处理器有该块的副本以及是否修改过等信息。分布式目录 4141/104/1048.3 分布式共享存储器系统结构q目录与存储器一起分布到各结点中，从而对于不同目录目录与存储器一起分布到各结点中，从而对于不同目录内容的访问可以在不同的结点进行。内容的访问可以在不同的结点进行。q特点：特点：存储块的共享状态信息可以在唯一的一个固定单元存储块的共享状态信息可以在唯一的一个固定单元中找到。这使一致性协议避免了广播操作。中找到。这使
36、一致性协议避免了广播操作。q对每个结点增加目录表后的分布式存储器多处理机的系对每个结点增加目录表后的分布式存储器多处理机的系统结构。统结构。4242/104/1048.3 分布式共享存储器系统结构4343/104/1048.3 分布式共享存储器系统结构1.目录协议必须完成两种主要的操作：处理读失效处理对共享、干净（clean）块的写 一个共享块的写失效处理可用这两个操作组合而成。2.目录必须跟踪记录每个Cache块的状态存储块的状态有三种：q共享共享 在一个或多个处理器上具有这个块的副本，且存在一个或多个处理器上具有这个块的副本，且存储器中的值是最新的（所有储器中的值是最新的（所有CacheC
37、ache中的副本均相同）。中的副本均相同）。4444/104/1048.3 分布式共享存储器系统结构q未缓冲未缓冲 所有处理器的所有处理器的CacheCache都没有该块的副本。都没有该块的副本。q专有专有 仅有一个处理器上有该块的副本，且已对该块进仅有一个处理器上有该块的副本，且已对该块进行了写操作，而主存中的副本仍是旧的。这个处理器行了写操作，而主存中的副本仍是旧的。这个处理器称为称为该块的拥有者该块的拥有者。4.由于写作废操作的需要，还必须记录哪些处理器有该块的副本。方法：对每个主存块设置一个位向量q当该块被共享时，每个位指出与之对应的处理器是否当该块被共享时，每个位指出与之对应的处理器
38、是否有该块的副本。有该块的副本。q当该块为专有时，可根据位向量来寻找其拥有者。当该块为专有时，可根据位向量来寻找其拥有者。4545/104/1048.3 分布式共享存储器系统结构 假设：对于本地Cache中非“专有”状态Cache块的写入操作总会产生写失效，处理器封锁直到写操作完成。1.一个例子本地结点、宿主结点以及远程结点的关系 q本地结点：本地结点：发出访问请求的结点发出访问请求的结点 q宿主结点：宿主结点：包含所访问的存储单元及其目录项的结点包含所访问的存储单元及其目录项的结点 q远程结点可以和宿主结点是同一个结点，也可以不是远程结点可以和宿主结点是同一个结点，也可以不是同一个结点。同一
39、个结点。CPUCache本地结点APCache远程结点C宿主结点B(Home)副本副本目录目录存储器存储器宿主结点：宿主结点：存放有对应地址的存储器块和目录项的结点存放有对应地址的存储器块和目录项的结点 K4747/104/1048.3 分布式共享存储器系统结构响应访问请求时，要将宿主结点中相应的值返回给请求结点。数据写回在两种情况下发生：qCacheCache中某个块被替换时必须写回到其宿主结点的存中某个块被替换时必须写回到其宿主结点的存储器。储器。q响应宿主结点发出的取数和取数响应宿主结点发出的取数和取数/作废消息时也要写作废消息时也要写回。回。4848/104/1048.3 分布式共享存
40、储器系统结构总结：目录协议的基本点在每个结点中增加了目录存储器用于存放目录。存储器的每一块在目录中有对应的一项。每一个目录项主要由两个字段构成：q状态：状态：描述所对应的存储块的当前状态。描述所对应的存储块的当前状态。q位向量：位向量：每一位对应于一个处理器，用于指出该处每一位对应于一个处理器，用于指出该处理器的理器的CacheCache中是否有该存储块的副本。当处理器对中是否有该存储块的副本。当处理器对某一块进行写操作时，只要根据位向量通知具有相某一块进行写操作时，只要根据位向量通知具有相应副本的处理器进行作废操作。应副本的处理器进行作废操作。位向量中记录的处理器集合称为位向量中记录的处理器
41、集合称为共享集合共享集合。4949/104/1048.3 分布式共享存储器系统结构在基于目录的协议中，目录承担了一致性协议操作的主要功能。发往一个目录的消息会产生两种不同类型的动作：q更新目录状态更新目录状态q发送消息以完成所请求的操作发送消息以完成所请求的操作目录可能接收三种不同的请求：q读失效读失效q写失效写失效q数据写回数据写回8.3.2 目录协议及其实现5050/104/1048.3 分布式共享存储器系统结构1.当一个块处于未缓冲状态时，对该块发出的请求及目录的处理操作为：读失效q将存储器数据送往请求方处理器，且该处理器成为将存储器数据送往请求方处理器，且该处理器成为该块的唯一共享结点
42、，本块的状态变成共享。该块的唯一共享结点，本块的状态变成共享。写失效q将存储器数据送往请求方处理器，该块的状态变成将存储器数据送往请求方处理器，该块的状态变成专有，表示该块仅存在唯一的有效副本。专有，表示该块仅存在唯一的有效副本。q其共享集合仅包含该处理器，指出该处理器是其拥其共享集合仅包含该处理器，指出该处理器是其拥有者。有者。5151/104/1048.3 分布式共享存储器系统结构1.当一个块处于共享状态时，其在存储器中的数据是当前最新的，对该块发出的请求及其处理操作为：读失效q将存储器数据送往请求方处理器，并将其加入共享将存储器数据送往请求方处理器，并将其加入共享集合。集合。写失效q将数
43、据送往请求方处理器，对共享集合中所有的处将数据送往请求方处理器，对共享集合中所有的处理器发送写作废消息。理器发送写作废消息。q将共享集合改为仅含有该处理器，该块的状态变为将共享集合改为仅含有该处理器，该块的状态变为专有。专有。5252/104/1048.3 分布式共享存储器系统结构1.当某块处于专有状态时，该块的最新值保存在共享集合所指出的唯一处理器（拥有者）中。有三种可能的目录请求：读失效q将将“取数据取数据”的消息发往拥有者处理器，使该块的的消息发往拥有者处理器，使该块的状态转变为共享。状态转变为共享。q将数据送回宿主结点写入存储器，进而把该数据送将数据送回宿主结点写入存储器，进而把该数据
44、送回请求方处理器，将请求方处理器加入共享集合。回请求方处理器，将请求方处理器加入共享集合。q此时共享集合中仍保留原拥有者处理器（因为它仍此时共享集合中仍保留原拥有者处理器（因为它仍有一个可读的副本）。有一个可读的副本）。5353/104/1048.3 分布式共享存储器系统结构写失效q该块将有一个新的拥有者。该块将有一个新的拥有者。q给旧的拥有者处理器发送消息，要求它将数据块送给旧的拥有者处理器发送消息，要求它将数据块送回宿主结点写入存储器，然后再从该结点送给请求回宿主结点写入存储器，然后再从该结点送给请求方处理器。方处理器。q把请求处理器加入共享者集合，使之成为新的拥有把请求处理器加入共享者集
45、合，使之成为新的拥有者。该块的状态仍旧是专有。者。该块的状态仍旧是专有。数据写回q当一个块的拥有者处理器要从其当一个块的拥有者处理器要从其CacheCache中把该块替换中把该块替换出去时，必须将该块写回其宿主结点的存储器中，出去时，必须将该块写回其宿主结点的存储器中，从而使存储器中相应的块中存放的数据是最新的从而使存储器中相应的块中存放的数据是最新的（宿主结点实际上成为拥有者），该块的状态变成（宿主结点实际上成为拥有者），该块的状态变成非共享，其共享集合为空。非共享，其共享集合为空。5454/104/1048.3 分布式共享存储器系统结构1.对基于目录的Cache一致性的多种改进有限映射目录
46、链式结构目录2.基于目录的Cache一致性协议是完全由硬件实现的。此外，还可以用软硬结合的办法实现。5555/104/104 同步机制通常是在硬件提供的同步指令的基础上，通过用户级软件例程来建立的。8.4 同 步8.4.1 基本硬件原语 在多处理机中实现同步，所需的主要功能是：p一组能以原子操作的方式读出并修改存储单元的硬件原一组能以原子操作的方式读出并修改存储单元的硬件原语。它们能够自动读修改单元。语。它们能够自动读修改单元。p通常情况下，用户不直接使用基本的硬件原语，原语主通常情况下，用户不直接使用基本的硬件原语，原语主要供系统程序员用来编制同步库函数。要供系统程序员用来编制同步库函数。5
47、656/104/1048.4 同 步1.典型操作：原子交换（atomic exchange）功能：将一个存储单元的值和一个寄存器的值进行交换。建立一个锁，锁值：建立一个锁，锁值：n0 0：表示开表示开（可用）（可用）n1 1：表示表示已上锁（不可用）已上锁（不可用）处理器上锁时，将对应于该锁的存储单元的值与存放在某个寄存器中的1进行交换。如果返回值为0，存储单元的值此时已置换为1，防止了其他进程竞争该锁。实现同步的关键：操作的原子性。5757/104/1048.4 同 步1.测试并置定（test_and_set）先测试一个存储单元的值，如果符合条件则修改其值。2.读取并加1（fetch_and
48、_increment）它返回存储单元的值并自动增加该值。3.使用指令对qLLLL(load linked(load linked或或load locked)load locked)的取指令的取指令qSCSC(store conditional)(store conditional)的特殊存指令的特殊存指令5858/104/1048.4 同 步指令顺序执行：q如果由如果由LLLL指明的存储单元的内容在指明的存储单元的内容在SCSC对其进行写之前对其进行写之前已被其他指令改写过，则第二条指令已被其他指令改写过，则第二条指令SCSC执行失败。执行失败。q如果在两条指令间进行切换也会导致如果在两条指令
49、间进行切换也会导致SCSC执行失败。执行失败。qSCSC将返回一个值来指出该指令操作是否成功：将返回一个值来指出该指令操作是否成功：n“1 1”：成功成功n“0 0”：不成功不成功qLLLL则返回该存储单元初始值。则返回该存储单元初始值。5959/104/1048.4 同 步例：例：实现对由实现对由R1R1指出的存储单元进行原子交换操作。指出的存储单元进行原子交换操作。trytry：ORORR3,R4,R0R3,R4,R0 /R4 /R4中为交换值。把该值送入中为交换值。把该值送入R3R3 LL LLR2,0R2,0（R1R1）/把单元把单元0 0（R1R1）中的值取到中的值取到R2R2 SC
50、SCR3,0R3,0（R1R1）/若若0 0（R1R1）中的值与中的值与R3R3中的值相中的值相 /同，则置同，则置R3R3的值为的值为1 1，否则置为，否则置为0 0 BEQZBEQZR3,tryR3,try/存失败（存失败（R3R3的值为的值为0 0）则转移）则转移 MOVMOVR4,R2R4,R2/将取的值送往将取的值送往R4R4 最终最终R4R4和由和由R1R1指向的单元值进行原子交换，在指向的单元值进行原子交换，在LLLL和和SCSC之间之间如有别的处理器插入并修改了存储单元的值，如有别的处理器插入并修改了存储单元的值，SCSC将返回将返回0 0并存入并存入R3R3中，从而使这段程序