计算机体系结构-东北大学乔百友chap

《计算机体系结构-东北大学乔百友chap》由会员分享，可在线阅读，更多相关《计算机体系结构-东北大学乔百友chap（195页珍藏版）》请在金锄头文库上搜索。

1、第七章 多处理机7.1 引言7.2 多处理机的存储器体系结构7.3 互连网络 7.4 同步与通信7.5 并行化技术 1第七章 多处理机 7.1 引 言单处理机单处理机的发展正在走向尽头？的发展正在走向尽头？并行计算机并行计算机在未来将会发挥更大的作用。在未来将会发挥更大的作用。1.1.获得超过单处理器的性能，最直接的方法就是把获得超过单处理器的性能，最直接的方法就是把2.2. 多个处理器连在一起；多个处理器连在一起；2. 2. 自自19851985年以来，体系结构的改进使性能迅速提高，年以来，体系结构的改进使性能迅速提高， 这种改进的速度能否持续下去还不清楚，但通过这种改进的速度能否持续下去还

2、不清楚，但通过 复杂度和硅技术的提高而得到的性能的提高正在复杂度和硅技术的提高而得到的性能的提高正在 减小；减小；3. 3. 并行计算机应用软件已有缓慢但稳定的发展。并行计算机应用软件已有缓慢但稳定的发展。 2第七章 多处理机本章重点本章重点: : 中小规模的机器中小规模的机器( (处理器的个数处理器的个数100) 100) （多处理机设计的主流）（多处理机设计的主流）7.1.1 并行计算机体系结构的分类1. 1. 按照按照FlynnFlynn分类法，可把计算机分成分类法，可把计算机分成 单指令流单数据流单指令流单数据流（SISDSISD） 单指令流多数据流（单指令流多数据流（SIMDSIMD

3、） 多指令流单数据流（多指令流单数据流（MISDMISD） 多指令流多数据流（多指令流多数据流（MIMDMIMD）3第七章 多处理机2. 2. MIMDMIMD已成为通用多处理机体系结构的选择，原因已成为通用多处理机体系结构的选择，原因： (1)(1) MIMDMIMD具有灵活性。具有灵活性。 (2)(2) MIMDMIMD可以充分利用商品化微处理器在性能价格可以充分利用商品化微处理器在性能价格 比方面的优势。比方面的优势。3. 3. 根据多处理机系统中处理器个数的多少，可把现根据多处理机系统中处理器个数的多少，可把现 有的有的MIMDMIMD机器分为两类机器分为两类（每一类代表了一种存储器的

4、结构和互连策略）（每一类代表了一种存储器的结构和互连策略） (1)(1) 集中式共享存储器结构集中式共享存储器结构 这类机器有时被称为这类机器有时被称为UMA(uniform memory UMA(uniform memory access) access)机器。机器。4第七章 多处理机5第七章 多处理机(2)(2) 分布式存储器结构分布式存储器结构 每个结点包含：每个结点包含： 在许多情况下，分布式存储器结构优于采用在许多情况下，分布式存储器结构优于采用 集中式共享存储器结构。集中式共享存储器结构。 分布式存储器结构需要高带宽的互连。分布式存储器结构需要高带宽的互连。 处理器处理器 存储器存

5、储器 I IO O6第七章 多处理机7第七章 多处理机 分布式存储器结构的分布式存储器结构的优点优点(1)如果大多数的访问是针对本结点的局部存储器，如果大多数的访问是针对本结点的局部存储器，则可降低对存储器和互连网络的带宽要求；则可降低对存储器和互连网络的带宽要求；(2)对局部存储器的访问延迟低。对局部存储器的访问延迟低。 主要主要缺点缺点处理器之间的通信较为复杂，且各处理器之间处理器之间的通信较为复杂，且各处理器之间访问延迟较大。访问延迟较大。 簇簇：超结点：超结点8第七章 多处理机7.1.2 通信模型和存储器的结构模型1. 1. 两种地址空间的组织方案两种地址空间的组织方案 (1)(1)

6、物理上分离的多个存储器可作为一个逻辑上共物理上分离的多个存储器可作为一个逻辑上共 享的存储空间进行编址。享的存储空间进行编址。 这类机器的结构被称为这类机器的结构被称为分布式共享存储器分布式共享存储器( (DSMDSM) ) 或或可缩放共享存储器可缩放共享存储器体系结构。体系结构。 DSMDSM机器被称为机器被称为NUMA(non-uniform memory access)NUMA(non-uniform memory access)机器。机器。 (2)(2) 整个地址空间由多个独立的地址空间构成，它整个地址空间由多个独立的地址空间构成，它 们在逻辑上也是独立的，远程的处理器不能对们在逻辑上

7、也是独立的，远程的处理器不能对 其直接寻址。其直接寻址。9第七章 多处理机每一个处理器每一个处理器- -存储器模块实际上是一个单独的存储器模块实际上是一个单独的计算机，这种机器也称为计算机，这种机器也称为多计算机多计算机。2. 2. 两种通信模型两种通信模型 这种机器常称为这种机器常称为消息传递机器消息传递机器。 共享地址空间的机器共享地址空间的机器 利用利用LoadLoad和和StoreStore指令中的地址隐含地进行指令中的地址隐含地进行 数据通讯。数据通讯。多个地址空间的机器多个地址空间的机器通过处理器间显式地传递消息完成。通过处理器间显式地传递消息完成。 10第七章 多处理机 消息传递

8、机器根据简单的网络协议，通过传递消消息传递机器根据简单的网络协议，通过传递消 息来请求某些服务或传输数据，从而完成通信。息来请求某些服务或传输数据，从而完成通信。例如例如 一个处理器要对远程存储器上的数据进行访问一个处理器要对远程存储器上的数据进行访问 或操作或操作 (1) (1) 发送消息，请求传递数据或对数据进行操作；发送消息，请求传递数据或对数据进行操作； 远程进程调用远程进程调用( (RPCRPC， remote process call) remote process call) (2) (2) 目的处理器接收到消息以后，执行相应的操目的处理器接收到消息以后，执行相应的操 作或代替远

9、程处理器进行访问，并发送一个作或代替远程处理器进行访问，并发送一个 应答消息将结果返回。应答消息将结果返回。11第七章 多处理机 同步消息传递同步消息传递 请求处理器发送一个请求后一直要等到应答请求处理器发送一个请求后一直要等到应答 结果才继续运行。结果才继续运行。 异步消息传递异步消息传递 发送方不先经请求就直接把数据送往数据接发送方不先经请求就直接把数据送往数据接 受方。受方。7.1.3 通信机制的性能 三个关键的性能指标：三个关键的性能指标： 1. 1. 通信带宽通信带宽 理想状态下的通信带宽受限于处理器、存储理想状态下的通信带宽受限于处理器、存储 器和互连网络的带宽。器和互连网络的带宽

10、。 12第七章 多处理机2. 2. 通信延迟通信延迟 理想状态下通信延迟应尽可能地小。理想状态下通信延迟应尽可能地小。 通信延迟发送开销跨越时间传输延迟通信延迟发送开销跨越时间传输延迟 接收开销接收开销3. 3. 通讯延迟的隐藏通讯延迟的隐藏 如何才能较好地将通信和计算或多次通信之如何才能较好地将通信和计算或多次通信之 间重叠起来，以实现通讯延迟的隐藏。间重叠起来，以实现通讯延迟的隐藏。 通常的原则是：通常的原则是：只要可能就隐藏延迟。只要可能就隐藏延迟。 通信延迟隐藏是一种提高性能的有效途径，但通信延迟隐藏是一种提高性能的有效途径，但 它对操作系统和编程者来讲增加了额外的负担。它对操作系统和

11、编程者来讲增加了额外的负担。13第七章 多处理机7.1.4 不同通信机制的优点 1.1.共享存储器通信的主要共享存储器通信的主要优点优点 (1)(1) 与常用的集中式多处理机使用的通信机制兼容。与常用的集中式多处理机使用的通信机制兼容。 (2)(2) 当处理器通信方式复杂或程序执行动态变化时当处理器通信方式复杂或程序执行动态变化时 易于编程，同时在简化编译器设计方面也占有易于编程，同时在简化编译器设计方面也占有 优势。优势。 (3)(3) 当通信数据较小时，通信开销较低，带宽利用当通信数据较小时，通信开销较低，带宽利用 较好。较好。 (4)(4) 通过硬件控制的通过硬件控制的CacheCach

12、e减少了远程通信的频度，减少了远程通信的频度， 减少了通信延迟以及对共享数据的访问冲突。减少了通信延迟以及对共享数据的访问冲突。 14第七章 多处理机2. 2. 消息传递通信机制的主要消息传递通信机制的主要优点优点 (1)(1) 硬件较简单。硬件较简单。 (2)(2) 通信是显式的，从而引起编程者和编译程序通信是显式的，从而引起编程者和编译程序 的注意，着重处理开销大的通信。的注意，着重处理开销大的通信。 在共享存储器上支持消息传递相对简单，但在消在共享存储器上支持消息传递相对简单，但在消 息传递的硬件上支持共享存储器就困难得多。息传递的硬件上支持共享存储器就困难得多。 所有对共享存储器的访问

13、均要求操作系统提供地所有对共享存储器的访问均要求操作系统提供地 址转换和存储保护功能，即将存储器访问转换为消址转换和存储保护功能，即将存储器访问转换为消 息的发送和接收。息的发送和接收。15第七章 多处理机7.1.5 并行处理面临的挑战 并行处理面临着两个重要的挑战：并行处理面临着两个重要的挑战： （可通过（可通过AmdahlAmdahl定律解释定律解释）1. 1. 有有限限的的并并行行性性使使机机器器要要达达到到好好的的加加速速比比十十分分困困难难。 程序中有限的并行性程序中有限的并行性 相对较高的通信开销相对较高的通信开销16第七章 多处理机 例例7.17.1 如如果果想想用用100100

14、个个处处理理器器达达到到8080的的加加速速比比，求原计算程序中串行部分所占比例。求原计算程序中串行部分所占比例。 解解 AmdahlAmdahl定律为定律为加速比加速比得出：得出：并行比例并行比例0.99750.9975 可以看出要用可以看出要用100100个处理器达到个处理器达到8080的加速比，串行的加速比，串行计算的部分只能占计算的部分只能占0.25%0.25%。1可可加速部分比例加速部分比例理论加速比理论加速比（1可加速部分比例）可加速部分比例）801并行比例并行比例100（1并行比例）并行比例）17第七章 多处理机2.2.面临的第二个挑战主要是指多处理机中远程访面临的第二个挑战主要

15、是指多处理机中远程访3.3. 问的较大延迟。问的较大延迟。 在现有的机器中，处理器之间的数据通信在现有的机器中，处理器之间的数据通信 大约需要大约需要50501000010000个时钟周期。个时钟周期。18第七章 多处理机机机器器通信机制通信机制互连网络互连网络处理机数量处理机数量典典型型远远程程存存储储器访问时间器访问时间SPARCCenter共享存储器共享存储器总线总线201sSGIChallenge共享存储器共享存储器总线总线361sCrayT3D共享存储器共享存储器3维环网维环网3220481sConvexExemplar共享存储器共享存储器交叉开关环交叉开关环8642sKSR-1共享

16、存储器共享存储器多层次环多层次环322562-6sCM-5消息传递消息传递胖树胖树32102410sIntelParagon消息传递消息传递2维网格维网格32204810-30sIBMSP-2消息传递消息传递多级开关多级开关251230-100s远程访问一个字的延迟时间远程访问一个字的延迟时间19第七章 多处理机 例例7.27.2 一台一台3232个处理器的计算机，对远程存储个处理器的计算机，对远程存储器访问时间为器访问时间为20002000nsns。除了通信以外，假设计算中的除了通信以外，假设计算中的访问均命中局部存储器。当发出一个远程请求时，本访问均命中局部存储器。当发出一个远程请求时，本

17、处理器挂起。处理器时钟时间为处理器挂起。处理器时钟时间为1010nsns，如果指令基本如果指令基本的的CPICPI为为1.01.0( (设所有访存均命中设所有访存均命中CacheCache) )，求在没有远程求在没有远程访问的状态下与有访问的状态下与有0.5%0.5%的指令需要远程访问的状态下，的指令需要远程访问的状态下，前者比后者快多少前者比后者快多少? ? 解解 有有0.5%0.5%远程访问的机器的实际远程访问的机器的实际CPICPI为为 CPICPI基本基本CPICPI远程访问率远程访问率远程访问开销远程访问开销 1.01.00.5%0.5%远程访问开销远程访问开销 20第七章 多处理机

18、远程访问开销远程访问时间远程访问开销远程访问时间/ /时钟时间时钟时间 20002000ns/10nsns/10ns200200个时钟个时钟 CPICPI1.01.00.5%0.5%2002002.02.0 它为只有局部访问的机器的它为只有局部访问的机器的2.02.01.01.02 2倍倍， 因此在没有远程访问的状态下的机器速度是有因此在没有远程访问的状态下的机器速度是有0.5%0.5%远程访问的机器速度的远程访问的机器速度的2 2倍倍。 问题的解决问题的解决 并行性不足并行性不足： 通过采用并行性更好的算法来解决通过采用并行性更好的算法来解决 远程访问延迟的降低远程访问延迟的降低： 靠体系结

19、构支持和编程技术靠体系结构支持和编程技术 21第七章 多处理机7.1.6 并行程序的计算通信比率 反映并行程序性能的一个重要的度量反映并行程序性能的一个重要的度量 计算与通信的比率计算与通信的比率 计算通信比率随着处理数据规模的增大而增计算通信比率随着处理数据规模的增大而增 加；随着处理器数目的增加而降低。加；随着处理器数目的增加而降低。22第七章 多处理机7.2 多处理机的存储器体系结构 多个处理器共享一个存储器。多个处理器共享一个存储器。 当处理器规模较小时，这种机器十分经济。当处理器规模较小时，这种机器十分经济。 支持对共享数据和私有数据的支持对共享数据和私有数据的CacheCache缓

20、存。缓存。 私有数据供一个单独的处理器使用，而共私有数据供一个单独的处理器使用，而共 享数据供多个处理器使用。享数据供多个处理器使用。 共享数据进入共享数据进入CacheCache产生了一个新的问题产生了一个新的问题 CacheCache的一致性问题的一致性问题7.2.1 集中式共享存储器体系结构23第七章 多处理机1. 1. 多处理机的一致性多处理机的一致性(1)(1) 不一致产生的原因（不一致产生的原因（CacheCache一致性问题一致性问题） I IO O操作操作 CacheCache中的内容可能与由中的内容可能与由I IO O子系统输入输子系统输入输出形成的存储器对应部分的内容不同。

21、出形成的存储器对应部分的内容不同。 共享数据共享数据 不同处理器的不同处理器的CacheCache都保存有对应存储器单元都保存有对应存储器单元的内容。的内容。 24第七章 多处理机例两个处理器例两个处理器CacheCache对应同一存储器单元产生出不同的值对应同一存储器单元产生出不同的值 假设：初始条件下各个假设：初始条件下各个CacheCache无无X X值，值，X X单元值为单元值为1 1； 写直达方式的写直达方式的CacheCache。时间时间事件事件CPUACache内容内容CPUBCache内容内容X单元存储器内容单元存储器内容011CPUA读读X112CPUB读读X113CPUA将

22、将0存入存入X01025第七章 多处理机(2)(2) 存储器是一致的（非正式地定义）存储器是一致的（非正式地定义） 如果对某个数据项的任何读操作均可得到其最如果对某个数据项的任何读操作均可得到其最 新写入的值，则认为这个新写入的值，则认为这个存储系统是一致的。存储系统是一致的。 存储系统行为的两个不同方面存储系统行为的两个不同方面 返回给读操作的是什么值返回给读操作的是什么值 什么时候才能将已写入的值返回给读操作什么时候才能将已写入的值返回给读操作 满足条件满足条件 处理器处理器P P对对X X进行一次写之后又对进行一次写之后又对X X进行读，进行读， 读和写之间没有其它处理器对读和写之间没有

23、其它处理器对X X进行写，则进行写，则 读的返回值总是写进的值。读的返回值总是写进的值。 26第七章 多处理机 一个处理器对一个处理器对X X进行写之后，另一处理器对进行写之后，另一处理器对X X进行进行 读，读和写之间无其它写，则读读，读和写之间无其它写，则读X X的返回值应为写的返回值应为写 进的值。进的值。 对同一单元的写是顺序化的，即任意两个处理器对同一单元的写是顺序化的，即任意两个处理器 对同一单元的两次写，从所有处理器看来顺序都应对同一单元的两次写，从所有处理器看来顺序都应 是相同的。是相同的。 假设假设 直到所有的处理器均看到了写的结果，一次写操直到所有的处理器均看到了写的结果，

24、一次写操 作才算完成；允许处理器无序读，但必须以程序规定作才算完成；允许处理器无序读，但必须以程序规定 的顺序进行写。的顺序进行写。 27第七章 多处理机2. 2. 实现一致性的基本方案实现一致性的基本方案 在一致的多处理机中，在一致的多处理机中，CacheCache提供两种功能。提供两种功能。 共享数据的迁移共享数据的迁移 降低了对远程共享数据的访问延迟。降低了对远程共享数据的访问延迟。 共享数据的复制共享数据的复制 不仅降低了访存的延迟，也减少了访问共不仅降低了访存的延迟，也减少了访问共 享数据所产生的冲突。享数据所产生的冲突。 小规模多处理机不是采用软件而是采用硬件技术小规模多处理机不是

25、采用软件而是采用硬件技术实现实现CacheCache一致性。一致性。28第七章 多处理机(1)(1) CacheCache一致性协议一致性协议 对多个处理器维护一致性的协议对多个处理器维护一致性的协议(2)(2) 关键关键：跟踪共享数据块的状态：跟踪共享数据块的状态 (3)(3) 共享数据状态跟踪技术共享数据状态跟踪技术 目录目录 物理存储器中共享数据块的状态及相关信息物理存储器中共享数据块的状态及相关信息 均被保存在一个称为目录的地方。均被保存在一个称为目录的地方。 监听监听 每个每个CacheCache除了包含物理存储器中块的数据拷除了包含物理存储器中块的数据拷 贝之外，也保存着各个块的共

26、享状态信息。贝之外，也保存着各个块的共享状态信息。29第七章 多处理机 CacheCache通常连在共享存储器的总线上，各个通常连在共享存储器的总线上，各个CacheCache控制器通过监听总线来判断它们是否有总线上请求的控制器通过监听总线来判断它们是否有总线上请求的数据块。数据块。30第七章 多处理机3. 3. 两种协议两种协议 (1) (1) 写作废协议写作废协议 在一个处理器写某个数据项之前保证它对该数据项在一个处理器写某个数据项之前保证它对该数据项 有唯一的访问权。有唯一的访问权。例例 在写回在写回CacheCache的条件下，监听总线中写作废协议的实现的条件下，监听总线中写作废协议的

27、实现。 处理器行为处理器行为总线行为总线行为CPU A Cache内内容容CPU B Cache内内容容主存主存X单元内容单元内容0CPUA读读XCache失效失效00CPUB读读XCache失效失效000CPUA将将X单元写单元写1作废作废X单元单元10CPUB读读XCache失效失效11131第七章 多处理机(2) (2) 写更新协议写更新协议 当一个处理器写某数据项时，通过广播使其它当一个处理器写某数据项时，通过广播使其它 CacheCache中所有对应的该数据项拷贝进行更新。中所有对应的该数据项拷贝进行更新。例例 在写回在写回CacheCache的条件下，监听总线中写更新协议的实现。的

28、条件下，监听总线中写更新协议的实现。 处理器行为处理器行为总线行为总线行为CPUA CPUA CacheCache内容内容CPUB CPUB CacheCache内容内容主主存存X X单单元元内容内容 0 0 CPU A CPU A 读读X XCachCach失效失效 0 0 0 0 CPU B CPU B 读读X XCachCach失效失效 0 0 0 0 0 0CPUACPUA将将 X X单单元写元写1 1广广 播播 写写 X X单元单元 1 1 1 1 1 1 CPU B CPU B 读读X X 1 1 1 1 1 1 32第七章 多处理机(3)(3) 写更新和写作废协议写更新和写作废协

29、议性能上的差别性能上的差别 对同一数据的多个写而中间无读操作的情况，对同一数据的多个写而中间无读操作的情况， 写更新协议需进行多次写广播操作，而在写写更新协议需进行多次写广播操作，而在写 作废协议下只需一次作废操作。作废协议下只需一次作废操作。 对同一块中多个字进行写，写更新协议对每对同一块中多个字进行写，写更新协议对每 个字的写均要进行一次广播，而在写作废协个字的写均要进行一次广播，而在写作废协 议下仅在对本块第一次写时进行作废操作。议下仅在对本块第一次写时进行作废操作。 从一个处理器写到另一个处理器读之间的延从一个处理器写到另一个处理器读之间的延 迟通常在写更新模式中较低。而在写作废协议迟

30、通常在写更新模式中较低。而在写作废协议 中，需要读一个新的拷贝。中，需要读一个新的拷贝。33第七章 多处理机 在基于总线的多处理机中，写作废协议成为绝大在基于总线的多处理机中，写作废协议成为绝大多数系统设计的选择。多数系统设计的选择。4. 4. 监听协议的基本实现技术监听协议的基本实现技术 (1)(1) 小规模多处理机中实现写作废协议的关键小规模多处理机中实现写作废协议的关键 利用总线进行作废操作利用总线进行作废操作 每个块的有效位使作废机制的实现较为容易。每个块的有效位使作废机制的实现较为容易。 (2)(2) 写直达写直达CacheCache，因为所有写的数据同时被写回因为所有写的数据同时被

31、写回 主存，则从主存中总可以取到最新的数据值。主存，则从主存中总可以取到最新的数据值。 (3)(3) 对于对于写回写回CacheCache，得到数据的最新值会困难一得到数据的最新值会困难一 些，因为最新值可能在某个些，因为最新值可能在某个CacheCache中，也可能中，也可能 在主存中。在主存中。34第七章 多处理机(4)(4) 在写回在写回CacheCache条件下的实现技术条件下的实现技术 用用CacheCache中块的中块的标志位标志位实现监听过程。实现监听过程。 给每个给每个CacheCache块加一个块加一个特殊的状态位特殊的状态位说明它是否说明它是否 为共享。为共享。 Cache

32、Cache块的拥有者块的拥有者：拥有唯一的：拥有唯一的CacheCache块拷贝的处理器。块拷贝的处理器。 因为每次总线任务均要检查因为每次总线任务均要检查CacheCache的地址位，这的地址位，这 可能与可能与CPUCPU对对CacheCache的访问冲突。可通过下列两种的访问冲突。可通过下列两种 技术之技术之 一降低冲突：一降低冲突： 复制标志位或采用多级包含复制标志位或采用多级包含CacheCache。 35第七章 多处理机7.2.2 分布式共享存储器体系结构 存储器分布于各结点中，所有的结点通过网络互存储器分布于各结点中，所有的结点通过网络互 连。访问可以是本地的，也可是远程的。连。

33、访问可以是本地的，也可是远程的。 不支持不支持CacheCache一致性一致性：规定共享数据不进入：规定共享数据不进入CacheCache， 仅私有数据才能保存在仅私有数据才能保存在CacheCache中。中。 优点优点： 所需的硬件支持很少所需的硬件支持很少 ( (因为远程访问存取量仅是一个字因为远程访问存取量仅是一个字( (或双字或双字) )而而 不是一个不是一个CacheCache块块) )36第七章 多处理机缺点：缺点： (1)(1) 实现透明的软件实现透明的软件CacheCache一致性的编译机制能力一致性的编译机制能力 有限。有限。 (2)(2) 没有没有CacheCache一致性

34、，机器就不能利用取出同一一致性，机器就不能利用取出同一 块中的多个字的开销接近于取一个字的开销块中的多个字的开销接近于取一个字的开销 这个优点，这是因为共享数据是以这个优点，这是因为共享数据是以CacheCache块为块为 单位进行管理的。当每次访问要从远程存储单位进行管理的。当每次访问要从远程存储 器取一个字时，不能有效利用共享数据的空器取一个字时，不能有效利用共享数据的空 间局部性。间局部性。 (3)(3) 诸如预取等延迟隐藏技术对于多个字的存取诸如预取等延迟隐藏技术对于多个字的存取 更为有效，比如针对一个更为有效，比如针对一个CacheCache块的预取。块的预取。 37第七章 多处理机

35、1.Cache一致性协议的开销分析（1）采用写无效协议无效后，当其它处理机再读该副本时，出现Readmiss，要有开销（2）采用写更新协议需要更新所有Cache和memory中的副本，所以开销大，有些处理机对更新后的数据可能不会使用。基于目录的Cache一致性协议38第七章 多处理机2.基于目录的一致性协议的基本思想当处理机台数增加时，一般不用总线结构，而采用多级互联网络。多级互连网络实现广播功能代价很大。为什么需要广播功能为什么需要广播功能？把一致性命令，如Write-inv，Read-inv等命令要发送给所有的Cache。能不能只发送给存放该副本的能不能只发送给存放该副本的Cache?基于

36、目录的协议的基本思想39第七章 多处理机3.目录的结构（1）目录里放什么有关Cache副本驻留在哪里的信息：所有共享数据块的所有Cache副本的地址表。（2）每个目录项（每个数据结构）包含若干个指向这个块（每个数据块有个目录项）的Cache副本地址的指针以及一个重写位（用来说明是否有一个Cache允许把有关的数据写入）。（3）基于目录的Cache一致性协议是依靠一个目录来记录系统之中哪些处理机的Cache中有指定存储块的副本。当一台处理机希望写某个共享块时，通过目录向有该块的副本的那些处理机“点对点”的发无效信号，使所有其它的副本无效。40第七章 多处理机4.目录的方式（1）集中目录方式（中心

37、目录）1976年Tang提出。用一个中心目录存放所有Cache目录的副本，它能提供为保证一致性所需要的所有信息。缺点：容量非常大，必须采用联想方法来检查，冲突多，检索时间长。41第七章 多处理机（2）分布式目录1978年Censier和Feautrier提出。每个存储模块维护各自的目录，目录中记录着每个存储块的当前信息。当前信息指明哪些Cache有该存储块的副本。如下面的图：4243第七章 多处理机5.三种目录全映射（fullmap）目录存放与全局存储器中每个块有关的数据。系统中的每个Cache可以同时存储任何数据块的副本，即每个目录项包含N个指针（N是处理机数目）。有限（limited）目录

38、每个目录项有固定数目的指针（小于N）。链式（chained）目录将目录分布到各个Cache（其余同全映射目录）。44第七章 多处理机全映射目录1.目录项结构目录项中有N个处理机位（对应N台处理机）和一个重写位，如下图所示：目录项：重写位（1位）处理机位（N位）处理机位表示相应处理机的Cacheblock的状态（存在或不存在）。有一个也只有一个处理机位为“1”，那么该处理机可以对该块进行写操作。45第七章 多处理机Cache的每个块有两个状态位：有效位有效块是否允许写有效1位Cache的状态位应该和目录项的状态一致。1位允许写目录项：重写位（1位）处理机位（N位）Cache状态位：46第七章 多

39、处理机2.目录的三种情况我们来看三台处理机（三个Cache）的例子。（1）C1，C2，C3都没有单元X的副本SharedMemoryx:c000dataC1P1C2P2C3P347第七章 多处理机（2）C1，C2，C3同时请求X单元的副本，这时目录项中的三个指针（处理机位）被置一，表示这些Cache中已有数据副本。目录项的重写位被置为未写（c）状态，表示无一处理机允许写入该数据块。SharedMemoryx:c111datax:P1x:P2x:P3C1C2C348第七章 多处理机（3）C3请求对该块的写允许权时出现第（3）种情形，重写被置成D状态，且有一个指针指向C3的数据块。SharedMe

40、moryx:D001dataP1P2x:P3C1C2C3data49第七章 多处理机3.第二种情况第三种情况的过程P3向C3发出写请求时：（1）C3检测出包含单元X的块是有效的，但Cache中的块允许位状态表示不允许处理机对该块进行写操作。（2）C3向包含单元X的存储器模块发出写请求，并暂停P3工作。（3）该存储器模块发出一个无效请求给C1和C2（根据目录项的内容发几个无效信号）50第七章 多处理机（4）C1和C2收到无效请求后，把相应位置1，表示含单元X的块已无效，并发送一个回答信号给请求的存储器模块。（5）存储器模块收到回答信号后，将重写位置1，清除指向C1、C2的指针，发出允许信号给C3

41、。（6）C3收到写允许信号后，修改Cache的状态并激活处理机P3。51第七章 多处理机4.目录所占空间假设存储器大小和处理机台数N成正比，即台数增加时，存储器的模块数也增加，所以数据块的个数也和N成正比。另外目录项的大小也和处理机台数N成正比，所以目录的总所占空间和N2成正比。即：目录项数*项大小=O(N2)太大不便于扩展。52第七章 多处理机有限目录有限目录的每个目录项只用一定数量的指针，而不管系统的大小如何。这减少了Cache目录对存储空间的要求，因而当存储器数据块共享比较少时更加经济。但如果有大量的处理机Cache共享相同的数据，那么它有可能降低Cache/主存的更新速度。53第七章

42、多处理机有限目录协议的状态与全映射目录协议十分相似，但目录项中的指针(处理机位)实际上是处理机的地址编码，若共有N台处理机，则目录项中指针部分为log2N位，每个目录项中指针的个数远远小于处理机的台数N。正因为如此，当多于允许数目的Cache同时要求某一个数据块的拷贝的时候，就必须进行指针的替换。这种指针替换过程称为驱逐(eviction)。由于多处理机系统中的处理机具有局部性（即在任何给定的时间间隔内，只有一小部分的处理机访问某个给定的存储器数据），所以有限目录足以应付这个小的处理机组了。54第七章 多处理机如图7.19所示，假设多处理机系统中共有3台处理机，目录项中只有2个指针，存储单元x

43、所在的数据块对应的目录项中2个指针分别指向处理机P1和P2，即在P1和P2的Cache中都有单元x所在的数据块的拷贝。当P3请求访问单元x时，需将单元x在共享存储器中的数据块调入Cache3，同时采用某种替换算法修改目录项中的指针部分。在图7.19中假设替换的是指向处理机P2的指针。在这里，任一时刻最多只能有2台处理机的Cache共享一个数据块。由于和存储器中数据块有关的目录项大小同log2N成正比，所以目录所花费的存储器容量就同存储器大小O(N)和目录项大小O(log2N)的乘积O(Nlog2N)成正比。55第七章 多处理机图7.19有限目录的驱逐56第七章 多处理机链式目录用目录指针链来跟

44、踪共享数据副本。 两种方法，单链法与双链法。数据块共享副本的数目并无限制。所占的空间及可扩展性同有限目录。它的工作原理如下过程所示。57第七章 多处理机（1）P1要读单元X，则memory发送一份副本给C1，同时送给C1一个链结束指针（CT：ChainTermination），存储器也保存指向C1的指针。SharedMemoryx:cdataP1P2P3C1C2C3x:CTdata58第七章 多处理机（2）当P2要读单元X时，存储器送一份副本给C2，同时送给C2一个指向C1的指针，存储器保存指向C2的指针。SharedMemoryx:cdataP1P2P3C1C2C3x:CTdatax:dat

45、a59第七章 多处理机（3）重复以上步骤，所有Cache都得到单元X的副本。（4）如果P3要对单元X进行写操作，它必须沿着链发送一个数据无效信息。为了保证顺序一致性，在有链结束指针的处理机回答无效信号之前，存储器模块不给P3写允许权。无效命令从一个Cache到一个Cache顺序进行，不象snoopy协议那样同时发送给所有Cache。60第七章 多处理机（5）替换。假设C1到CN都有单元X的副本，还假设单元X和单元Y都映射到同一个高速缓存块（直接映射法）。如果处理机Pi要读单元Y，它首先必须把X所在的块从Cache中去掉，这可以采用两种方法：1）沿着链发一个消息使Ci+1的指针指向Ci-1，这样

46、使Ci从链中去掉（这时Ci中存放Y了）。2）使Ci+1到CN中的单元X无效（这时Ci中存放Y了）。61第七章 多处理机目录占用的存储容量：指针的尺寸以处理机数目的对数关系增长（这和有限目录相同）log2N，每个Cache块的指针数目与处理机个数无关。62三种Cache一致性策略6.4.1采用Write-Through策略的Cache数据块的两种状态：有效和无效（指本地处理机相应数据块的状态，并非整个Cache的状态。)一致性的四种操作：Rr和Wr：其它处理机对该数据块（指在其它处理机Cache中的数据块）的读写Rl和Wl：是本地处理机对该数据块的读写状态转移图如下：63有效有效RrWlRlRl

47、,WlWrRr,Wr64Cache的数据块为无效时：其它处理机的任何操作都不会影响本地Cache的这种无效状态；只有在本地处理机读或者写了数据块中的某个数据，即对Cache执行了Read或Write命令时，该数据块的状态才会成为“有效”。65Cache的数据块为“有效”时：本地处理机的读、写操作，不会影响该状态；其它处理机对存有相同内容的数据块读，不会影响该状态；其它处理机对存有相同内容的数据块执行了写操作，该数据块状态变成无效。666.4.2采用Write-Back策略的Cache1.数据块的三种状态RO(只读）状态：表示整个系统中不止一个副本正确（例如一个在Cache中，一个在memory

48、中）。读-写状态：表示整个系统中，只有这个副本是正确的，其它都“过时”（即无效），这说明这个Cache的数据块至少被写过一次，但memory中的内容还没有被修改。无效状态：“过时”数据。672.一致性的四种操作：Rr和Wr：其它处理机对该数据块（指在其它处理机Cache中的数据块）的读写Rl和Wl：是本地处理机对该数据块的读写状态转移图如下：683.处于RO状态本地读，远程读不会改变状态本地写，使ROR-W（这时只有一个数据块正确）远程写，使RO无效有效ROWlWrRl,RrW-R694.处于读-写状态有效RORrWrRl,WlW-R70本地读、写不会改变状态远程读：这时只有这个Cache的数

49、据块是正确的，所以要有“写回”动作（即把内容写回Memory），另外还需要把正确的数据传递给远程读的处理机相应的Cache。两个Cache的状态RO远程写：把本地处理机的数据块传递给远程处理机，远程处理机对数据块进行写操作，远程处理机对应的Cache状态变为RO，而本地的Cache变为无效状态。715.处于无效状态有效ROWlRr,WrW-RRl72本地读：无效RO本地写：无效WR（同时使其它拥有相同内容的数据块的Cache中相应的数据块的状态变成无效）远程写、远程读：不影响状态的改变73采用Write-Once策略的Cache1.Write-Through和Write-Back的缺点Writ

50、e-Through策略的弱点是每次都要修改memory，所以总线流量增大；Write-Back策略的弱点是Cache写了一次后，Memory中的内容不一致。742.Write-Once的基本思想把Write-Through和Write-Back两者的优点结合在一起：减少总线流量。Cache的第一次写采用Write-Through策略（有一个以上的副本正确）；Cache而后的写采用Write-Back策略（只有一份副本正确）。为了区分是否是第一次写，把“读-写”状态分成两个状态：Reserved和Drity。753.数据块的四种状态有效状态（Valid）：相当于Write-Back里的“只读”，

51、从共享存储器中读入的并与存储器副本一致的Cache数据块。无效状态（Invalid）：在Cache中找不到或Cache中的数据块内容与共享存储器中的内容不一致的Cache数据块。76保留状态（Reserved）：数据从共享存储器读入Cache只被写过一次。Cache中的副本与共享存储器中的副本是一致的，并且它是正确的副本。重写状态（Dirty）：Cache中的数据块不止一次被写过，此时共享存储器中的数据块也不是正确的数据块，唯一正确的数据块在Cache中。774.如果处于“有效”状态有效保留WrRl,Rr无效Wl重写78（1）本地读Rl，不影响状态。（2）本地写Wl（第一次写），采用Write

52、-Through策略，这时要发无效命令给其它Cache中相应的副本，并修改memory。有效保留（3）远程写Wr（不管是第几次写），远程CPU会发无效命令：有效无效（4）远程读Rr：不影响状态。795.如果处于“保留”状态有效保留WrRl无效Rr重写Wl80（1）本地读Rl，不影响状态。（2）远程读Rr：这时Cache中只有处于保留状态的数据块是正确的，所以把该数据块送到远程CPU的Cache中（远程Cache中该数据块变为有效），本数据块状态已变为有效。（3）本地写Wl：第二次及以后的写，采取Write-Back策略，不修改Memory，状态由Reserved变为Dirty（这时只有一个副本

53、有效），发无效命令给其它Cache的对应的副本，使Memory中的副本也无效。（4）远程写Wr：远程CPU会发无效命令，使状态由Reserved变为Invalid。816.如果处于“重写”状态有效保留WrRr无效Rl，Wl重写82（1）本地读Rl：不影响状态。（2）本地写Wl：不影响状态。（3）远程读Rr：这时只有这个Cache的数据块是正确的，所以把该数据块发送给远程的Cache，远程Cache的数据块和本Cache中的数据块都变得有效。（4）远程写Wr：远程CPU写后，发无效命令使状态由重写无效。837.如果处于“无效”状态有效保留RlWr,Rr无效Wl重写84（1）本地读Rl：这时产生R

54、ead-Miss，设法找到有效的数据块调入Cache：如果系统存在处于有效，保留或重写状态的相应数据块，则将其调入本地Cache如果系统中不存在处于有效、保留或重写状态的相应数据块，则说明共享存储器中的数据块是正确的，直接从共享存储器读入即可。读入后相应数据块进入“有效”状态。85（2）远程读Rr：状态不变（3）本地写Wl：一定是Write-Miss，系统首先把正确的内容调入Cache，然后写Cache，因为是第一次写，所以Write-Through策略，同时写memory，将本地Cache状态置为“保留”，同时将系统中其它相应的数据块置为“无效”（4）远程写Wr：状态不变86第七章 多处理机

55、7.3 互连网络 互连网络互连网络是将集中式系统或分布式系统中的结点连是将集中式系统或分布式系统中的结点连 接起来所构成的网络，接起来所构成的网络，连接和控制方式不同，连接效果不同。 结点（node）:处理单元（PE、处理机）、存储器 在拓扑上，互连网络为输入和输出两组结点之间提在拓扑上，互连网络为输入和输出两组结点之间提 供一组互连或映象。供一组互连或映象。7.3.1 互连网络的性能参数1.1.互连网络的结构特征互连网络的结构特征(1) (1) 拓扑结构拓扑结构 静态网络静态网络 结点之间的连接路径是固定的，这种连接方式在程序执行过程这种连接方式在程序执行过程中不会改变。中不会改变。 动态网

56、络网络使用开关元件，结点之间的路径可重配置87第七章 多处理机互连网络的结构特征互连网络的结构特征(2)(2)通信方式通信方式同步：同步地建立通信路径同步：同步地建立通信路径异步：动态地提出连接请求以建立通信路径异步：动态地提出连接请求以建立通信路径混合型：同步混合型：同步+ + 异步异步(3)(3)控制策略：控制策略：控制网络中开关元件的状态以实现路径选择控制网络中开关元件的状态以实现路径选择 集中、分散集中、分散(4)(4)交换方式交换方式 线路交换：在发送和接收之间建立一条物理线路线路交换：在发送和接收之间建立一条物理线路 分组交换：数据打包，多条路径传送分组交换：数据打包，多条路径传送

57、88第七章 多处理机2. 2. 性能参数性能参数 (1)(1) 网络规模网络规模：结点数：结点数 (2)(2) 结点度结点度：与结点相连接的边的数目。：与结点相连接的边的数目。 入度入度：进入结点的通道数：进入结点的通道数 出度出度：从结点出来的通道数：从结点出来的通道数 (3)(3) 网络直径网络直径 网络中任意两个结点间最短路径长度的最大值。网络中任意两个结点间最短路径长度的最大值。 (4)(4) 等分宽度等分宽度 在将某一网络切成相等两半的各种切法中，在将某一网络切成相等两半的各种切法中， 沿切口的最小通道边数。沿切口的最小通道边数。89第七章 多处理机 对称网络对称网络 从其中的任何一

58、个结点看，拓扑结构都是从其中的任何一个结点看，拓扑结构都是 一样的网络。一样的网络。(5)(5) 路由路由 在网络通信中对路径的选择与指定。在网络通信中对路径的选择与指定。3. 3. 互连网络表示互连网络表示 互连网络的连接特征一般用互连函数表示。 如果把互连网络的如果把互连网络的N N个个入端和入端和N N个个出端各自用出端各自用 整数整数0 0，1 1，N-1N-1代表，则互连函数表示互连的代表，则互连函数表示互连的 出端号和入端号的一一对应关系。出端号和入端号的一一对应关系。 一个互连网络的连接特征可对应多个互连函数。 90第七章 多处理机5.5. 几种数据路由功能几种数据路由功能 (1

59、)(1) 循环循环 若把互连函数若把互连函数f(x)f(x)表示为：表示为： ( (x x0 0,x,x1 1,x,x2 2, , ,x xj j) ) 则代表对应关系为：则代表对应关系为： f(xf(x0 0)=x)=x1 1,f(x,f(x1 1)=x)=x2 2, ,f(,f(x xj j)=x)=x0 0 j+1j+1称为该称为该循环的周期。循环的周期。 (2)(2) 置换置换 指对象的重新排序。对于指对象的重新排序。对于n n个个对象来说，对象来说， 有有n!n!种置换。种置换。 4.设计思路设计思路根据应用需要（互连网络属性），选择合理的特征方式，考虑互连网根据应用需要（互连网络属

60、性），选择合理的特征方式，考虑互连网络的性能因素，综合加以合理组合。络的性能因素，综合加以合理组合。目标：低成本、高灵活性、高连接度、低延时、适合目标：低成本、高灵活性、高连接度、低延时、适合VLSI。91第七章 多处理机 例如例如 置换置换=(a,b,c)(d,e)=(a,b,c)(d,e)表示了置换映射：表示了置换映射： f(a)=b,f(b)=c,f(c)=a,f(d)=ef(a)=b,f(b)=c,f(c)=a,f(d)=e和和f(e)=df(e)=d。 这里循环这里循环( (a,b,c)a,b,c)周期为周期为3 3，循环，循环( (d,e)d,e)周期为周期为2 2。(3)(3)

61、均匀混洗均匀混洗 n=8n=8（对象个数）的均匀混洗所对应的映射与其逆过程对象个数）的均匀混洗所对应的映射与其逆过程 9293第七章 多处理机对对n=2n=2k k个对象均匀混洗，可用个对象均匀混洗，可用k k位二进制数位二进制数 x=(xx=(xk-1k-1, ,x,x1 1,x,x0 0) )来表示定义域中的每个对象。来表示定义域中的每个对象。均匀混洗将均匀混洗将x x映射到映射到f(x)f(x)，得到得到f(x)=(xk-2,x1,x0,xk-1) 。这是将这是将x x循环左移循环左移1 1位位得到。得到。 (4)(4) 超立方体路由功能超立方体路由功能 例例 一个三维二进制立方体网络一

62、个三维二进制立方体网络 有三种路由功能有三种路由功能: : 分别根据结点的分别根据结点的 二进制地址二进制地址（C C2 2 C C1 1 C C0 0）中的某一位来确定。中的某一位来确定。9495第七章 多处理机 一个一个n n维维超立方体共有超立方体共有n n种种路由功能，分别由路由功能，分别由n n位位地地址中的每一位求反位值来确定。将址中的每一位求反位值来确定。将x=(xx=(xk-1k-1,x,x1 1,x,x0 0) )映映射到射到f(x)f(x)，得到得到f(x)=( xf(x)=( xk-1k-1, , , , x xk k,x,x1 1,x,x0 0) )。( (5)5) 广

63、播和选播广播和选播 广播广播 一对全体的映射一对全体的映射 选播选播 一个子集到另一子集一个子集到另一子集( (多对多多对多) )的映射。的映射。5. 5. 影响互连网络性能的因素影响互连网络性能的因素 (1) (1) 功能特性功能特性 网络如何支持路由、中断处理、同步、请网络如何支持路由、中断处理、同步、请 求消息组合和一致性。求消息组合和一致性。96第七章 多处理机(2)(2) 网络时延网络时延 单位消息通过网络传送时最坏情况下的时间延迟。单位消息通过网络传送时最坏情况下的时间延迟。(3)(3) 带宽带宽 通过网络的最大数据传输率，用通过网络的最大数据传输率，用MBMBs s表示。表示。(

64、4)(4) 硬件复杂性硬件复杂性 诸如导线、开关、连接器、仲裁和接口逻辑等诸如导线、开关、连接器、仲裁和接口逻辑等 的造价。的造价。(5)(5) 可扩展性可扩展性 在增加机器资源使性能可扩展的情况下，网络在增加机器资源使性能可扩展的情况下，网络 具备模块化可扩展的能力。具备模块化可扩展的能力。 977.3.2 静态连接网络1. 1. 线性阵列线性阵列 一种一维的线性网络，其中一种一维的线性网络，其中N N个结点用个结点用N-1N-1个链个链 路连成一行。路连成一行。 内部结点度：内部结点度：2 2 端结点度：端结点度：1 1 直径：直径：N-1N-1 等分宽度等分宽度b=1b=1982.2.

65、环环和和带弦环带弦环 (1)(1) 环环 用一条附加链路将线性阵列的两个端点连接起用一条附加链路将线性阵列的两个端点连接起 来而构成的。可以单向工作，也可以双向工作。来而构成的。可以单向工作，也可以双向工作。 结点度：结点度：2 2 双向环的直径：双向环的直径：N N2 2 单向环的直径：单向环的直径：N N99第七章 多处理机(2) (2) 带弦环带弦环 增加的链路愈多，结点度愈高，网络直径就愈小。增加的链路愈多，结点度愈高，网络直径就愈小。 全连接网络全连接网络结点度结点度: : 1 1直径最短，直径最短，为为1 1。100101102第七章 多处理机3.3. 循环移数网络循环移数网络(

66、(PM2I) 通过在环上每个结点到所有与其通过在环上每个结点到所有与其距离为距离为2 2的整的整 数幂数幂的结点之间都增加一条附加链而构成的。的结点之间都增加一条附加链而构成的。 结点数结点数: : 1616 结点度结点度: : 7 7 直径直径: : 2 2 如果如果j-ij-i=2=2 r r，r=0,1,2,n-1r=0,1,2,n-1，网络规模网络规模N=2N=2n n，则结点则结点i i与结点与结点j j连接。这种循环移数网络的结连接。这种循环移数网络的结点度为点度为d=2n-1d=2n-1，直径直径D=nD=n2 2。 共有2n个互连函数，对N个结点的网络为103第七章 多处理机4

67、.4. 树形树形和和星形星形 (1)(1) 一棵一棵5 5层层3131个结点的个结点的二叉树二叉树 一般说来，一棵一般说来，一棵k k层层完全平衡的二叉树有完全平衡的二叉树有 N=2N=2k-1k-1个结点。个结点。 最大结点度是最大结点度是3 3，直径是，直径是2(2(k-1)k-1)。 (2)(2) 星形星形 一种一种2 2层树层树。 结点度较高，为结点度较高，为d=N-1d=N-1。 直径较小，是一常数直径较小，是一常数2 2。5.5. 胖树形胖树形104105第七章 多处理机6.6. 网格形网格形和和环网形环网形 (1)(1) 一个一个3 33 3网格形网络网格形网络 一般说来，一般说

68、来，N=N=n nk k 个结点的个结点的k k维维网络的内网络的内 部结点度为部结点度为2 2k k ，网络直径为网络直径为k(n-1)k(n-1)。边结边结 点和角结点的结点度分别为点和角结点的结点度分别为3 3或或2 2。 (2)(2) 环形网环形网 可看做是直径更短的另一种网格。可看做是直径更短的另一种网格。 环形网沿阵列每行和每列都有环形连接。环形网沿阵列每行和每列都有环形连接。 一个一个n nn n二元环网二元环网 结点度为结点度为4 4 直径为直径为2*2*n/2n/2 106107第七章 多处理机7.7. 超立方体超立方体 一种一种二元二元n-n-立方体立方体结构。结构。 一般

69、说来，一个一般说来，一个n-n-立方体立方体由由N=2N=2n n 个结点组成，个结点组成， 它们分布在它们分布在n n维维上，每维有上，每维有两个两个结点。结点。 例例8 8个结点的个结点的3-3-立方体立方体 4-4-立方体立方体 一个一个n-n-立方体立方体的结点度等于的结点度等于n n，也就是网络的也就是网络的 直径。直径。 108109第七章 多处理机8.8. k k元元n-n-立方体网络立方体网络 环形、网络形、环网形、二元环形、网络形、环网形、二元n-n-立方体立方体( (超立方超立方 体体) )等网络都是等网络都是k k元元n-n-立方体网络立方体网络系统的拓扑同构体。系统的拓

70、扑同构体。 参数参数n n: : 立方体的维数立方体的维数 k k: : 基数或者说是沿每个方向的结点数基数或者说是沿每个方向的结点数( (多重性多重性) )。 N=N=k kn n, (n=, (n=loglogk kN N) ) K K元元n-n-立方体立方体的结点可用基数为的结点可用基数为k k的的n n位地址位地址 A=aA=a0 0a a1 1a a2 2a an n来表示，其中来表示，其中a ai i代表第代表第i i维结点的位置。维结点的位置。 按照惯例，低维按照惯例，低维k k元元n-n-立方体称为环网，而高维二立方体称为环网，而高维二 元元n-n-立方体则称为立方体则称为超立

71、方体超立方体。 110例例一种一种4 4元元3-3-立方体网络立方体网络111第七章 多处理机7.3.3 动态连接网络 1. 1. 动态互连网络的三个主要操作特征动态互连网络的三个主要操作特征 定时定时 开关开关 控制控制2. 2. 根据级间连结方式，动态互连网络分为根据级间连结方式，动态互连网络分为 (1)(1) 单级网络单级网络 也称循环网络也称循环网络 (2)(2) 多级网络多级网络 由一级以上的开关元件构成。由一级以上的开关元件构成。 这类网络可以把任一输入与任一输出相连。这类网络可以把任一输入与任一输出相连。 112第七章 多处理机 阻塞网络阻塞网络 如果同时连接多个输入输出对时如果

72、同时连接多个输入输出对时, ,可能会引可能会引 起开关和通信链路使用上的冲突。起开关和通信链路使用上的冲突。 大多数多级网络都是阻塞网络。大多数多级网络都是阻塞网络。 非阻塞网络非阻塞网络 如果多级网络通过重新安排连接方式可以如果多级网络通过重新安排连接方式可以 建立所有可能的输入输出之间的连接。建立所有可能的输入输出之间的连接。 113第七章 多处理机 缺点：缺点：容易产生故障容易产生故障 总线研制中的重要问题总线研制中的重要问题 总线仲裁总线仲裁 中断处理中断处理 一致性协议一致性协议 总线事务的处理总线事务的处理3. 3. 几类主要的开关网络几类主要的开关网络 (1)(1) 总线系统总线

73、系统 优点：优点： 价格较低价格较低 带宽较窄带宽较窄 114 一种总线连接的多处理机系统一种总线连接的多处理机系统115第七章 多处理机(2)(2) 交叉开关网络交叉开关网络 单级无阻塞置换网络单级无阻塞置换网络 每个交叉点是一个可以打开或关闭的一元每个交叉点是一个可以打开或关闭的一元 开关，提供源开关，提供源( (处理器处理器) )和目的和目的( (存储器存储器) )之间之间 点对点的连接通路。点对点的连接通路。 交叉点开关网络中交叉点开关网络中n n对对处理器可以同时传送处理器可以同时传送 数据。数据。 交叉开关网络的带宽和互连特性最好。交叉开关网络的带宽和互连特性最好。 116 一种交

74、叉开关网络一种交叉开关网络 P1P2P16M1M1M16117第七章 多处理机(3)(3) 多端口存储器多端口存储器 主要思想主要思想 将所有交叉点仲裁逻辑和跟每个存储器模将所有交叉点仲裁逻辑和跟每个存储器模 块有关的开关功能移到存储器控制器中。块有关的开关功能移到存储器控制器中。 多端口存储器结构是一个折衷方案，它介于低多端口存储器结构是一个折衷方案，它介于低 成本低性能的总线系统和高成本高带宽的交叉成本低性能的总线系统和高成本高带宽的交叉 开关系统之间。开关系统之间。 缺点缺点十分昂贵十分昂贵不能扩展不能扩展当系统配置很大时，需大量的互连电缆和连接器当系统配置很大时，需大量的互连电缆和连接

75、器。118 用于多处理机系统的多端口存储器结构用于多处理机系统的多端口存储器结构119第七章 多处理机(4)(4) 多级网络多级网络 多级网络可用于构造大型多处理机系统。多级网络可用于构造大型多处理机系统。 一种通用多级网络一种通用多级网络 各种多级网络的区别就在于所用开关模各种多级网络的区别就在于所用开关模 块和级间连接模式的不同。块和级间连接模式的不同。120第七章 多处理机 由由abab开关模块和级间构成的通用多级互连网络结构开关模块和级间构成的通用多级互连网络结构 121第七章 多处理机OmegaOmega网网 2222开关四种可能的连接方式开关四种可能的连接方式 122第七章 多处理

76、机 一个一个161616 16 OmegaOmega网络网络123第七章 多处理机 路路由算法举例由算法举例 置换置换1 1=(0,7,6,4,2)(1,3)(5)=(0,7,6,4,2)(1,3)(5)124第七章 多处理机 置换置换2 2=(0,6,4,7,3)(1,5)(2)=(0,6,4,7,3)(1,5)(2)125(3)多级立方体网络多级立方体网络由n级相同的网络组成，每一级都包含一个Cubei拓扑和随后一列2n-1个二功能交换单元。8个处理单元的多级立方体互连网络的拓扑结构如图5.28所示。126图5.28N=8的立方体多级互连网络127常见的多级立方体网络有STARAN网络和间

77、接二进制n方体网络。两者的相同点是当第i级（0in-1）交换单元处于交换状态时，实现的是Cubei互连函数，且都采用二功能交换单元；不同之处在于各级交换开关采用的控制方式，STARAN采用级控制（称交换网络）或部分级控制（称移数网络）；而间接二进制n方体网络采用单元控制。128当STARAN网络用作交换网络时，采用级控制，每级的所有2n-1个二功能交换开关用同一个控制信号控制。当第i级的级控制信号为0时，这一级的所有二功能交换开关都完成直连功能，当第i级的级控制信号为1时，这一级的所有二功能交换开关都完成Cubei交换函数的功能。当处理单元个数N=8时，STARAN交换网络共设计为3级(log

78、2N=3)，共需要3个级控制信号，级控制信号的组合及所实现的功能如表5.2所示。129表5.2STARAN交换网络(N=8)级控制信号的组合及所实现的功能级控制信号（K2K1K0）000001010011100101110111入端号012345670123456710325476230167453210765445670123547610326745230176543210130执行的交换函数功能恒等4组2元4组2元+2组4元2组4元2组4元+1组8元4组2元+2组4元+1组8元4组2元+1组8元1组8元iCube0Cube1Cube0+Cube1Cube2Cube0+Cube2Cube1+

79、Cube2Cube0+Cube1+Cube2131从表5.2可以看出，当级控制信号为K2K1K0=001时，由于第0级的级控制信号K0=1，其它级控制信号都为0，所以所有处理单元执行的交换函数的功能是Cube0。 同 样 的 道 理 ， 当 级 控 制 信 号 为K2K1K0=011时，所有处理单元执行的交换函数的功能是Cube0+Cube1。132当级控制信号K2K1K0=011时的各级交换开关状态如图5.29所示。由图5.29中各处理单元的连接同样可以看出，当级控制信号为K2K1K0=011时，所有处理单元执行的交换函数的功能是Cube0+Cube1，即二进制编码为P2P1P0的处理单元连

80、往二进制编码为P2P1P0的处理单元。在图 5.29中 给 出 了 当 级 控 制 信 号 为K2K1K0=011时，0号处理单元到3号处理单元的路由选择过程。133图5.29当级控制信号K2K1K0=011时的各级交换开关状态图134在 表 5.2中 ， 当 级 控 制 信 号 为K2K1K0=101时，所有处理单元执行的交换函数的功能是4组2元+2组4元+1组8元，意思是对于入端的8个处理单元与出端的8个处理单元的连接在排列上表现为先将8个处理单元的排列分成4组，每组2元交换，然后再将当前的排列分成2组，每组4元交换，最后再将当前新的排列分成1组，每组8元交换，如下所示：135入端排列：0

81、1234567分成4组：|01|23|45|67|每组2元交换：|10|32|54|76|分成2组：|1032|5476|每组4元交换：|2301|6745|分成1组：|23016745|每组8元交换：54761032136当STARAN网络用作移数网络时，采用部分级控制，第i级的2n-1个二功能交换开关分成i+1组，每组用一个控制信号控制。对于n级STARAN移数网络来说，从第0级到第n-1级所需的控制信号个数分别为1，2，3，n个。当处理单元个数N=8时，共需要6个控制信号，每一级控制信号的分组和控制结果如表5.3所示。STARAN移数网络的置换函数可以表示为：(x)=(x+2m)mod2

82、pp和m为整数，且0mpn。137例如，表5.3中功能部分的第1列，当控制信号A=B=C=D=0，F=H=0，E=G=1，K=L=0，J=0，I=1时，完成的功能是移1模8，即m=0，p=3。意思是对于入端的8个处理单元与出端的8个处理单元的连接在排列上表现为先将8个处理单元的排列分成1组，然后再将当前的处理单元排列循环移动1位。138表5.3三级移数网络能实现的入出端连接及移数函数功能部分级控制信号2级K，LJI0010111110000000000001级F，HE，G011100011100000级A，B，C，D0001010139入端号01234567123456702345670145

83、67012312305674230167451032547601234567相当于实现的移数功能移1mod8移2mod8移4mod8移1mod4移2mod4移1mod2不移全等140再如，表5.3中功能部分的第5列，当控制信号A=B=C=D=0，F=H=1，E=G=1，K=L=0，J=0，I=0时，完成的功能是移2模4，即m=1，p=2。意思是对于入端的8个处理单元与出端的8个处理单元的连接在排列上表现为先将8个处理单元的排列分成2组，然后再将当前的处理单元排列循环移动2位。141第七章 多处理机7.4 同步与通信7.4.1 同步机制 1. 1. 基本的硬件原语基本的硬件原语 自动读出并修改存

84、储单元。自动读出并修改存储单元。 (1)(1) 原子交换原子交换 将一个存储单元的值和一个寄存器的值进将一个存储单元的值和一个寄存器的值进 行交换。行交换。 将一个存储单元定义为锁，该锁的值为将一个存储单元定义为锁，该锁的值为“0 0” 表示锁是开的，为表示锁是开的，为“1 1”表示已上锁。表示已上锁。 实现同步的关键实现同步的关键: : 操作的原子性操作的原子性142第七章 多处理机(2)(2) 测试并置定测试并置定（test_and_settest_and_set） 先测试一个值，如果符合条件则修改其值。先测试一个值，如果符合条件则修改其值。(3)(3) 读取并加读取并加1 1（fetch

85、_and_incrementfetch_and_increment） 它返回存储单元的值并自动增加该值。它返回存储单元的值并自动增加该值。(4)(4) 使用指令对使用指令对 LL(load linkedLL(load linked或或load locked)load locked)的取指令的取指令 SC(store conditional)SC(store conditional)的特殊存指令的特殊存指令143第七章 多处理机例例实现对由实现对由R1R1指出的存储单元进行原子交换操作指出的存储单元进行原子交换操作 trytry：mov mov R3,R4R3,R4 ；送交换值送交换值 ll l

86、l R2,0(R1)R2,0(R1) ；load linkedload linked sc R3,0(R1)sc R3,0(R1) ；store conditionalstore conditional beqzbeqz R3,try R3,try ；存失败转移存失败转移 mov mov R4,R2R4,R2 ；将取的值送往将取的值送往R4R4 144第七章 多处理机 LL/SCLL/SC机制的一个机制的一个优点优点: : 可用来构造别的同步原语。可用来构造别的同步原语。例如例如 原子的原子的fetch_and_incrementfetch_and_increment trytry： ll l

87、l R2,0(R1)R2,0(R1) ；load linkedload linked addiaddi R2,R2, R2,R2,1 1 ；增加增加 sc R2,0(R1) sc R2,0(R1) ；store conditionalstore conditional beqzbeqz R2,try R2,try ；存失败转移存失败转移145第七章 多处理机2. 2. 使用一致性实现锁使用一致性实现锁 采用多处理机的一致性机制来实现旋转锁。采用多处理机的一致性机制来实现旋转锁。 旋转锁旋转锁 处理器环绕一个锁不停地旋转而请求获得该锁。处理器环绕一个锁不停地旋转而请求获得该锁。 (1)(1) 无

88、无CacheCache一致性机制一致性机制 实现方法实现方法 在存储器中保存锁变量，处理器可以不断地通在存储器中保存锁变量，处理器可以不断地通 过一个原子操作请求加锁，比如先交换，再测试返过一个原子操作请求加锁，比如先交换，再测试返 回值从而知道锁的状况。释放锁的时候，处理器可回值从而知道锁的状况。释放锁的时候，处理器可 简单地将锁置为简单地将锁置为“0” 0” 。 146第七章 多处理机 一个旋转锁的代码段一个旋转锁的代码段 （R1R1中的地址对应为用来进行原子交换的锁）中的地址对应为用来进行原子交换的锁） li li R2R2，1 1 lockitlockit： exch exch R2,

89、0(R1)R2,0(R1) ；原子交换原子交换 bnez bnez R2R2，lockit lockit ；是否已加锁是否已加锁? ? (2)(2) 机器支持机器支持CacheCache一致性一致性将锁缓冲进入将锁缓冲进入CacheCache，并通过一致性机制使锁值保持一致。并通过一致性机制使锁值保持一致。 lockitlockit：lw lw R2R2，0(R1)0(R1) ；取锁值取锁值 bnez bnez R2R2，lockitlockit ；锁不可用锁不可用 li li R2R2，1 1 ；存入锁值存入锁值 exch exch R2R2，0(R1)0(R1) ；交换交换 bnez bn

90、ez R2R2，lockitlockit ；如果锁不为如果锁不为0 0转移转移 147第七章 多处理机(3) (3) 旋转锁是怎样使用旋转锁是怎样使用CacheCache一致性机制的？一致性机制的？三个处理器竞争锁的操作三个处理器竞争锁的操作 步骤步骤处理器处理器P0处理器处理器P1处理器处理器P2锁状态锁状态总线总线/目录操作目录操作1占有锁占有锁环绕测试环绕测试lock=0环绕测试环绕测试lock=0Shared无无2将将锁锁置置为为0（收到作废命令）（收到作废命令）(收收到到作作废废命命令令)ExclusiveP0发锁变量作废消息发锁变量作废消息3Cache失效失效Cache失效失效Sh

91、ared总总线线/目目录录处处理理P2Cache失效失效,锁从锁从P0写回写回4总总线线/目目录录忙忙则则等等待待Lock=0SharedP2Cache失效处理失效处理5Lock=0执执行行交交换换，导导致致Cache失效失效SharedP1Cache失效处理失效处理6执行交换，导致执行交换，导致Cache失效失效交交换换完完毕毕，返返回回0置置lock=1Exclusive总总线线/目目录录处处理理P2Cache失效失效,发作废消息发作废消息7交换完毕，返回交换完毕，返回1进进入入关关键键处处理理段段Shared总总线线/目目录录处处理理P2Cache失效，写回失效，写回8环绕测试环绕测试l

92、ock=0无无148第七章 多处理机(4)(4) 下面代码与使用经过优化交换的代码具有相同的特点下面代码与使用经过优化交换的代码具有相同的特点 ( (R1R1中保存锁的地址中保存锁的地址) )lockit：llR2，0(R1)；load-linkedbnezR2，lockit；锁无效锁无效liR2,，1；加锁值加锁值scR2，0(R1)；存存beqzR2，lockit；如果存失败则转移如果存失败则转移3. 3. 同步的性能同步的性能 竞争问题竞争问题149第七章 多处理机 例例7.37.3 设总线上有设总线上有2020个处理器同时准备对同一个处理器同时准备对同一变量加锁。假设每个总线事务处理变

93、量加锁。假设每个总线事务处理( (读失效或写失效读失效或写失效) )是是5050个时钟周期，忽略实际的个时钟周期，忽略实际的CacheCache块锁的读写时间块锁的读写时间以及加锁的时间，求以及加锁的时间，求2020个处理器请求加锁所需的总个处理器请求加锁所需的总线事务数目。设时间为线事务数目。设时间为0 0时锁已释放并且所有处理器时锁已释放并且所有处理器在旋转，求处理这在旋转，求处理这2020个请求时间为多长个请求时间为多长? ?假设总线在假设总线在新的请求到达之前已服务完挂起的所有请求，并且新的请求到达之前已服务完挂起的所有请求，并且处理器速度相同。处理器速度相同。 答答 表给出了从一次释

94、放锁到下一次释放锁之间表给出了从一次释放锁到下一次释放锁之间150第七章 多处理机发生的事件。当然，每次获得锁后竞争的处理器数发生的事件。当然，每次获得锁后竞争的处理器数目也会减目也会减1 1，从而使平均开销降为，从而使平均开销降为15251525个周期。个周期。2020个个处理器总通过锁的时间会超过处理器总通过锁的时间会超过3000030000多个周期。整体多个周期。整体上看处理器平均有一半时间处于闲置状态，只是简上看处理器平均有一半时间处于闲置状态，只是简单地在请求获得锁，所用的总线事务数超过了单地在请求获得锁，所用的总线事务数超过了400400（基于第三、第三和第四项：（基于第三、第三和

95、第四项：(40+1)/2 20=410(40+1)/2 20=410）。）。151第七章 多处理机事件事件 时间时间所有等待的处理器取锁产生的读失效所有等待的处理器取锁产生的读失效(2050)1000释放锁的处理器导致的写失效及作废释放锁的处理器导致的写失效及作废50所有等待的处理器的读失效所有等待的处理器的读失效(2050)1000所有等待的处理器写失效，一个成功获得锁所有等待的处理器写失效，一个成功获得锁(50)，并作废其余的锁拷贝并作废其余的锁拷贝(1950)1000一个处理器获得和释放锁的总时间一个处理器获得和释放锁的总时间3050个时钟周期个时钟周期2020个处理器竞争同一锁时，从请

96、求到释放的时间个处理器竞争同一锁时，从请求到释放的时间假设每个总线事务处理时间为假设每个总线事务处理时间为5050个时钟周期。个时钟周期。 152第七章 多处理机4.4. 栅栏栅栏同步同步 栅栏强制所有到达该栅栏的进程进行等待，栅栏强制所有到达该栅栏的进程进行等待， 直到全部的进程到达栅栏，然后释放全部的进程，直到全部的进程到达栅栏，然后释放全部的进程， 从而形成同步。从而形成同步。 (1)(1) 栅栏的典型实现栅栏的典型实现 用两个用两个旋转锁旋转锁 一个用来记录到达栅栏的进程数一个用来记录到达栅栏的进程数 一个用来封锁进程直至最后一个进程到达栅栏一个用来封锁进程直至最后一个进程到达栅栏15

97、3第七章 多处理机Lock(counterlock)；*确保更新的原子性确保更新的原子性*if(count=0)release=0；*第一个进程则重置第一个进程则重置release*count=count+1；*到达进程记数到达进程记数*unlock(counterlock)；*释放锁释放锁*if(count=total)*进程全部到达进程全部到达*count=0；*重置计数器重置计数器*release=1；*释放进程释放进程*else*还有进程未到达还有进程未到达*spin(release=1)；*等待别的进程到达等待别的进程到达* 其中其中locklock和和unlockunlock提供基

98、本的旋转锁，提供基本的旋转锁，totaltotal规定了要规定了要到达栅栏的进程总数。到达栅栏的进程总数。154第七章 多处理机(2)(2) 问题问题 通常反复使用一个栅栏，栅栏释放的进程运行一通常反复使用一个栅栏，栅栏释放的进程运行一 段后又会再次返回该栅栏，这样有可能出现某个进程段后又会再次返回该栅栏，这样有可能出现某个进程永远离不开栅栏的状况永远离不开栅栏的状况( (它停在旋转操作上它停在旋转操作上) )。 解决方法解决方法 当进程离开栅栏时进行计数当进程离开栅栏时进行计数( (和入口一样和入口一样) )，在上，在上次栅栏使用中的所有进程离开之前不允许任何进程重次栅栏使用中的所有进程离开

99、之前不允许任何进程重 用并初始化本栅栏。用并初始化本栅栏。 sense_reversingsense_reversing栅栏，每个进程均使用一个私栅栏，每个进程均使用一个私有变量有变量local_senselocal_sense，该变量初始化为该变量初始化为1 1。 155第七章 多处理机local_sense=!local_sense；*local-sense取反取反*lock(counterlock)；*确保更新的原子性确保更新的原子性*count+；*记算到达进程数记算到达进程数*unlock(counterlock)；*解锁解锁*if(count=total)*进程全部到达进程全部到达

100、*count=0；*重置计数器重置计数器*release=local_sense；*释放进程释放进程*else*还有进程未到达还有进程未到达*spin(release=local_sense)；*等待信号等待信号*156第七章 多处理机 例例7.47.4 假设总线上假设总线上2020个处理器同时执行一个栅个处理器同时执行一个栅栏，设每个总线事务需栏，设每个总线事务需5050个时钟周期，忽略个时钟周期，忽略CacheCache块块中锁的读、写实际花费的时间以及栅栏实现中非同中锁的读、写实际花费的时间以及栅栏实现中非同步操作的时间，计算步操作的时间，计算2020个处理器全部到达栅栏，被个处理器全部

101、到达栅栏，被释放及离开栅栏所需的总线事务数。设总线完全公释放及离开栅栏所需的总线事务数。设总线完全公平，整个过程需多长时间平，整个过程需多长时间? ? 答答 表给出一个处理器通过栅栏产生的事件序表给出一个处理器通过栅栏产生的事件序列，设第一个获得总线的进程还没有获得锁。列，设第一个获得总线的进程还没有获得锁。 157第七章 多处理机事件事件每个处理器时间每个处理器时间20个处理器时间个处理器时间每个处理器获得锁、增量、每个处理器获得锁、增量、152530500释放锁的时间释放锁的时间执行释放的时间执行释放的时间5050每个处理器获得释放标志每个处理器获得释放标志501000的时间的时间总和总和

102、162531550 一个处理器通过栅栏产生的事件序列一个处理器通过栅栏产生的事件序列 栅栏操作比前面讲的栅栏操作比前面讲的2020个处理器加锁解锁操作所需时个处理器加锁解锁操作所需时 间稍长，所需总的总线事务数约为间稍长，所需总的总线事务数约为440440。 158第七章 多处理机7.4.2 大规模机器的同步 希望的同步机制：希望的同步机制：1. 1. 软件实现软件实现 旋转锁旋转锁 主要问题主要问题 当多个进程检测并竞争锁时引起的延迟。当多个进程检测并竞争锁时引起的延迟。 解决办法解决办法 (1)(1) 当加锁失败时就人为地推延这些进程的等待时间。当加锁失败时就人为地推延这些进程的等待时间。

103、 在无竞争的条件下延迟较小在无竞争的条件下延迟较小 在竞争激烈时串行性小在竞争激烈时串行性小159第七章 多处理机 具有指数延迟的旋转锁代码具有指数延迟的旋转锁代码liR3，1；R3初始延迟值；初始延迟值；lockit：llR2，0(R1)；loadlinkedbnezR2，lockit；无效无效addiR2，R2，1；取到加锁值取到加锁值scR2，0(R1)；storeconditionalbnezR2，gotit；存成功转移存成功转移sllR3，R3，1；将延迟时间增至将延迟时间增至2倍倍；（左移；（左移1位）位）pauseR3；延迟延迟R3中时间值中时间值jlockitgotit：使用加

104、锁保护的数据使用加锁保护的数据160第七章 多处理机(2)(2) 排队锁排队锁 采用数组进行软件实现。采用数组进行软件实现。 通过通过组合树组合树来减少冲突。来减少冲突。 组合树组合树降低冲突的原因是将大冲突化解成为并降低冲突的原因是将大冲突化解成为并 行的多个小冲突。行的多个小冲突。 组合树组合树采用预定义的采用预定义的n n叉树结构。叉树结构。 采用采用sense_reversingsense_reversing技术，基于组合树的栅栏技术，基于组合树的栅栏 代码。代码。 变量变量k k表示扇入数目表示扇入数目 161第七章 多处理机structnode*组合树中一个结点组合树中一个结点*i

105、ntcounterlock；*本结点锁本结点锁*intcount；*计数本结点计数本结点*intparent；*树中父结点树中父结点0.p-1，根结点父结点号根结点父结点号-1*；structnodetree0.p-1；*树中各结点树中各结点*intlocal_sense；*每个处理器的私有变量每个处理器的私有变量*intrelease；*全局释放标志全局释放标志*栅栏实现函数栅栏实现函数*barrier(intmynode)lock(treemynode.counterlock)；*保护计数器保护计数器*count+；*计数的累加计数的累加*unlock(treemynode.conterl

106、ock)；*解锁解锁*if(treemynode.count=k)*本结点进程全部到达本结点进程全部到达*162第七章 多处理机if(treemynode.parent)=0barrier(treemynode.parent)；elserelease=local_sense；treemynode.count0；*为下次重用初始化为下次重用初始化*elsespin(release=local_sense)；*等待等待*；*加入栅栏的进程执行代码加入栅栏的进程执行代码*local_sense=!local_sense；barrier(mynode)；163第七章 多处理机2. 2. 硬件原语支持硬

107、件原语支持 两种硬件同步原语两种硬件同步原语 针对锁针对锁 针对栅栏和要求进行计数或提供明确索引的针对栅栏和要求进行计数或提供明确索引的 某些用户级操作某些用户级操作 排队锁排队锁 排队记录等待的进程，当锁释放时送出一排队记录等待的进程，当锁释放时送出一 个已确定的等待进程。个已确定的等待进程。 (1)(1) 工作过程工作过程164第七章 多处理机 在第一次取锁变量失效时，失效被送入同步控制器。在第一次取锁变量失效时，失效被送入同步控制器。 如果锁空闲，将其交给该处理器；如果锁空闲，将其交给该处理器； 如果锁忙，控制器产生一个结点请求记录如果锁忙，控制器产生一个结点请求记录( (比如可以比如可

108、以 是向量中某一位是向量中某一位) )，并将锁忙的标志返回给处理器，并将锁忙的标志返回给处理器， 然后该处理器进入旋转等待。然后该处理器进入旋转等待。 当该锁被释放时，控制器从等待的进程排队中选出一当该锁被释放时，控制器从等待的进程排队中选出一 个使用该锁。个使用该锁。 165第七章 多处理机 例例7.57.5 如果在排队锁的使用中，失效时进行锁更如果在排队锁的使用中，失效时进行锁更新，求新，求2020个处理器完成个处理器完成locklock和和unlockunlock所需的时间和总所需的时间和总线事务数。假设条件与前面例子相同。线事务数。假设条件与前面例子相同。 答答 每个处理器初始加锁及随

109、后释放锁各产生每个处理器初始加锁及随后释放锁各产生1 1次次失效，所以总共需失效，所以总共需4040个总线周期。个总线周期。2020个初始失效需个初始失效需10001000个时钟周期，接着是每次需要个时钟周期，接着是每次需要5050个周期的个周期的2020次释次释放，总和为放，总和为20502050个周期。与通常的基于个周期。与通常的基于CacheCache一致性一致性的旋转锁相比，性能大大提高。的旋转锁相比，性能大大提高。 166第七章 多处理机(2)(2) 关键问题关键问题 需要识别出对锁进行初次访问的进程，从而需要识别出对锁进行初次访问的进程，从而 对其进行排队操作；对其进行排队操作；

110、等待进程队列可通过多种机制实现；等待进程队列可通过多种机制实现； 有硬件来回收锁。有硬件来回收锁。(3) (3) Fetch_and_incrementFetch_and_increment原语原语 原子地取值并增量，返回的值可以为增量原子地取值并增量，返回的值可以为增量 后的值，也可以为取出的值。后的值，也可以为取出的值。 167第七章 多处理机 例例7.6 7.6 写出采用写出采用fetch_and_incrementfetch_and_increment栅栏的代码。栅栏的代码。条件与前面假设相同，并设一次条件与前面假设相同，并设一次fetch_and_incrementfetch_and

111、_increment操作也需操作也需5050个时钟周期。计算个时钟周期。计算2020个处理器通过栅栏的个处理器通过栅栏的时间，及所需的总线周期数。时间，及所需的总线周期数。 答答 下面的程序段给出栅栏的代码，这种实现需要下面的程序段给出栅栏的代码，这种实现需要进行进行2020次次fetch_and_incrementfetch_and_increment操作，释放时有操作，释放时有2020次次CacheCache失效，总共需时间失效，总共需时间20002000个时钟周期，个时钟周期，4040个总线事个总线事务操作。与前面实现的栅栏机制相比，前面所需时间务操作。与前面实现的栅栏机制相比，前面所需

112、时间长达长达1515倍，总线操作多达倍，总线操作多达1010倍。当然，实现组合树栅倍。当然，实现组合树栅栏时也可采用栏时也可采用fetch_and_incrementfetch_and_increment来降低树中每个结来降低树中每个结点的串行竞争。点的串行竞争。168第七章 多处理机local_sense=!local_sense；*local_sense变反变反*fetch_and_increment(count)；*原子性更新原子性更新*if(count=total)*进程全部到达进程全部到达*count=0；*初始化计数器初始化计数器*release=local_sense；*释放进程

113、释放进程*else*还有进程未到达还有进程未到达*spin(releaze=local_sense)；*等待信号等待信号*169第七章 多处理机7.5 并行化技术 7.5.1 并行化的基本策略 并行程序设计模型是专门为并行程序设计模型是专门为多处理机多处理机、多计算机多计算机或或向量向量SIMDSIMD计算机而设计的。计算机而设计的。 并行性的五种模型并行性的五种模型: : 1. 1. 共享变量模型共享变量模型 (1)(1) 多处理机程序设计的基础多处理机程序设计的基础 利用共享变量来实现进程间的通信。利用共享变量来实现进程间的通信。 这需要使用共享存储器以及访问同一组共享这需要使用共享存储器

114、以及访问同一组共享 变量的多个进程间的同步特性。变量的多个进程间的同步特性。 170第七章 多处理机(2)(2) 遇到的主要问题遇到的主要问题 临界区的保护性访问临界区的保护性访问 存储器的一致性存储器的一致性 存储操作的可分性存储操作的可分性 快速同步快速同步 共享的数据结构共享的数据结构 快速数据迁移技术快速数据迁移技术2. 2. 消息传递模型消息传递模型 驻留在不同处理机结点上的两个进程可以通过驻留在不同处理机结点上的两个进程可以通过 网络传递消息来相互通信。网络传递消息来相互通信。 消息可以是指令、数据、同步信号或中断信号等。消息可以是指令、数据、同步信号或中断信号等。 171第七章

115、多处理机(1)(1) 同步消息传递同步消息传递 在时间和空间上必须对发送进程和接收进程在时间和空间上必须对发送进程和接收进程 实现同步。实现同步。(2)(2) 异步消息传递异步消息传递 通道中常用缓冲区。通道中常用缓冲区。 倘若缓冲区足够大或网络通信量不饱和，则消倘若缓冲区足够大或网络通信量不饱和，则消 息传递就不会阻塞。息传递就不会阻塞。 不管接收者是否准备好，都允许发送者发送消不管接收者是否准备好，都允许发送者发送消 息而不被阻塞。息而不被阻塞。 关键问题关键问题 如何把程序代码和数据分布或复制到所有如何把程序代码和数据分布或复制到所有 处理结点上。处理结点上。 172第七章 多处理机3.

116、 3. 数据并行模型数据并行模型 数据并行程序要求使用预先分布好的数据集。数据并行程序要求使用预先分布好的数据集。 数据并行程序设计强调的是局部计算和数据路数据并行程序设计强调的是局部计算和数据路 由操作。由操作。 数据并行性取决于粒度大小以及所采用的操作数据并行性取决于粒度大小以及所采用的操作 方式。方式。 数据并行通常研究数据并行通常研究 有几千个并发数据操作的高度并行性问题。有几千个并发数据操作的高度并行性问题。4. 4. 面向对象模型面向对象模型 对象对象 把数据和操作封装在一个计算单元中的程序实体。把数据和操作封装在一个计算单元中的程序实体。173第七章 多处理机 对象是动态建立和控

117、制的。对象是动态建立和控制的。 处理是通过在对象间发送和接收消息来完成的。处理是通过在对象间发送和接收消息来完成的。5. 5. 函数和逻辑模型函数和逻辑模型 (1)(1) 函数程序设计模型函数程序设计模型 强调程序的函数性，程序在执行后不应强调程序的函数性，程序在执行后不应 该产生副作用。该产生副作用。 (2)(2) 逻辑程序设计模型逻辑程序设计模型 以谓词逻辑为基础，适用于涉及大型数据以谓词逻辑为基础，适用于涉及大型数据 库的知识处理。库的知识处理。 174第七章 多处理机7.5.2 并行语言与编译器 1. 1. 并行性的语言特征并行性的语言特征 并行程序设计的语言特性：并行程序设计的语言特

118、性： (1)(1) 优化特性优化特性 (2)(2) 可用性可用性 包括：包括： 扩展性扩展性 兼容性兼容性 可移植性可移植性175第七章 多处理机(3)(3) 同步通信特性同步通信特性 主要包括：主要包括： 共享变量共享变量( (锁锁) )的支持的支持 消息传递的发送接收消息传递的发送接收 远程过程调用远程过程调用 栅栏同步机制和邮栅栏同步机制和邮箱箱(4)(4) 并行性控制并行性控制 包括以各种形式确定并行性的控制结构。包括以各种形式确定并行性的控制结构。 主要处理：主要处理：176第七章 多处理机各种粒度的并行性各种粒度的并行性显式并行性与隐式并行性显式并行性与隐式并行性整个程序中的全局并

119、行性整个程序中的全局并行性迭代中的循环并行性迭代中的循环并行性任务分割并行性任务分割并行性共享任务队列共享任务队列共享抽象数据类型共享抽象数据类型(5)(5) 数据并行性数据并行性 说明访问数据以及把数据分布在多处理计算机说明访问数据以及把数据分布在多处理计算机 上的方法。上的方法。 177第七章 多处理机主要包括：主要包括： 无需用户干预的运行时数据自动分布；无需用户干预的运行时数据自动分布； 为用户提供一种能指定通信模式或说明数据和为用户提供一种能指定通信模式或说明数据和 进程映射到硬件上的方法；进程映射到硬件上的方法； 编译器将虚处理机动态或静态地映射到物理处编译器将虚处理机动态或静态地

120、映射到物理处 理机上的虚拟处理机支持；理机上的虚拟处理机支持； 共享数据可被直接访问而不用管程控制；共享数据可被直接访问而不用管程控制； SPMD(single program multiple data)SPMD(single program multiple data)程序设程序设 计支持。计支持。 178第七章 多处理机 (6)(6) 进程管理特性进程管理特性 用来支持并行进程的高效创建、多线程用来支持并行进程的高效创建、多线程 处理和多任务处理的实现、程序划分和复制处理和多任务处理的实现、程序划分和复制 以及运行以及运行 时的动态负载平衡。时的动态负载平衡。 2. 2. 并行语言结构并

121、行语言结构 (1)(1) Fortran 90Fortran 90数组表示符数组表示符 多维数组是用一个带下标三元组序列的多维数组是用一个带下标三元组序列的 数组名来表示的，每维一个三元组，不同维数组名来表示的，每维一个三元组，不同维 的三元组用逗号隔开。的三元组用逗号隔开。179第七章 多处理机例如例如 e e1 1 :e :e2 2 :e :e3 3 e e1 1 :e :e2 2 e e1 1 :* :e :* :e3 3 e e1 1 :* :* e e1 1 * * 每个每个e ei i一定是能产生一个标量整数值的算术表达式。一定是能产生一个标量整数值的算术表达式。 180第七章 多

122、处理机(2)(2) 并行流控制并行流控制 ( (DoallDoall, ,EndallEndall) )语句对语句对 说明并行活动说明并行活动 ( (DoacrossDoacross, ,EndacrossEndacross) )语句语句 说明循环体间相关并行性。说明循环体间相关并行性。 例如：例如： DoacrossDoacross I=2,N I=2,N Do J=2,N Do J=2,N S1:A(I,J)=(A(I(J-1)+A(I,J+1) S1:A(I,J)=(A(I(J-1)+A(I,J+1)2 2 EnddoEnddo Endacross Endacross181第七章 多处理

123、机 ( (CobeginCobegin, ,CoendCoend) )语句对语句对 CobeginCobegin P P1 1 P P2 2 . . . . . . CoendCoend182第七章 多处理机 ForkFork和和JoinJoin命令命令 在进程在进程P P的执行过程中，可以使用的执行过程中，可以使用Fork QFork Q命令命令 来产生一个新的进程来产生一个新的进程Q Q： Process P Process QProcess P Process Q . . . . . . . . . . . . Fork Q Fork Q . . . . . . . . . . . .

124、Join Q End Join Q End183第七章 多处理机3. 3. 并行优化编译器并行优化编译器 由三个主要部分组成：由三个主要部分组成： 流分析流分析 优化优化 代码生成代码生成 (1)(1) 流分析流分析 为确定源代码中的数据和控制一致性，将为确定源代码中的数据和控制一致性，将 程序流的模式分析出来。程序流的模式分析出来。184185第七章 多处理机(2)(2) 程序优化程序优化 目的目的：尽可能多地挖掘硬件的潜能。：尽可能多地挖掘硬件的潜能。 最终目标最终目标: : 使代码执行速度达到最高。使代码执行速度达到最高。 要求要求 代码的长度最短代码的长度最短 存储器的访问次数最少存储

125、器的访问次数最少 程序并行性得到较好的开发程序并行性得到较好的开发 优化技术包括：优化技术包括： 用流水线硬件完成向量化用流水线硬件完成向量化 同时用多台处理机实现并行化同时用多台处理机实现并行化186第七章 多处理机(3)(3) 并行代码生成并行代码生成 涉及从一种描述到另一种称之为中间形式描涉及从一种描述到另一种称之为中间形式描 述的转换。述的转换。 代码生成与所用的指令调度策略是紧密联系代码生成与所用的指令调度策略是紧密联系 在一起的。在一起的。 187第七章 多处理机1. 1. 基于目录的基于目录的CacheCache一致性一致性 (1)(1) 目录协议必须完成两个主要的操作。目录协议

126、必须完成两个主要的操作。 处理读失效处理读失效 处理对共享、干净块的写处理对共享、干净块的写( (对一个共享块的对一个共享块的 写失效处理是这两个操作的简单结合写失效处理是这两个操作的简单结合) ) (2)(2) 目录必须跟踪每个目录必须跟踪每个CacheCache块的状态。块的状态。 CacheCache块状态有三种：块状态有三种：188第七章 多处理机共享共享 在一个或多个处理器上具有这个块的拷贝，在一个或多个处理器上具有这个块的拷贝，且主存中的值是最新值且主存中的值是最新值( (所有所有CacheCache均相同均相同) )。未缓冲未缓冲 所有处理器的所有处理器的CacheCache都没

127、有此块的拷贝。都没有此块的拷贝。专有专有 仅有一个处理器上有此块的拷贝，且已对此仅有一个处理器上有此块的拷贝，且已对此块进行了写操作，而主存的拷贝仍是旧的。块进行了写操作，而主存的拷贝仍是旧的。这这个处个处理器称为此块的理器称为此块的拥有者拥有者。 189第七章 多处理机(3)(3) 由于写作废操作的需要，还必须记录共享此块的由于写作废操作的需要，还必须记录共享此块的 处理器信息。处理器信息。 方法：对每个主存块设置一个方法：对每个主存块设置一个位向量位向量。 当此块被共享时，每个位指出与之对应的处当此块被共享时，每个位指出与之对应的处 理器是否有此块的拷贝。理器是否有此块的拷贝。 当此块为专

128、有时，可根据位向量来寻找此块当此块为专有时，可根据位向量来寻找此块 的拥有者。的拥有者。(4)(4) 宿主结点宿主结点 存放有存储器块和对应地址目录项的结点。存放有存储器块和对应地址目录项的结点。 190第七章 多处理机(5)(5) 目录协议的目录协议的基本点基本点 在每个结点增加了目录存储器用于存放目录；在每个结点增加了目录存储器用于存放目录； 存储器的每一块在目录中对应有一项；存储器的每一块在目录中对应有一项； 每一个目录项主要有每一个目录项主要有状态状态和和位向量位向量两种成分。两种成分。状态状态描述该目录所对应存储块的当前情况；描述该目录所对应存储块的当前情况；位向量位向量共有共有N

129、N位位，其每一位对应于一个处理器的局，其每一位对应于一个处理器的局部部CacheCache，用于指出该用于指出该CacheCache中有无该存储块的拷贝。中有无该存储块的拷贝。2. 2. 目录协议的基本实现技术目录协议的基本实现技术在基于目录的协议中，目录承担了一致性协议操在基于目录的协议中，目录承担了一致性协议操作的主要功能。作的主要功能。 191第七章 多处理机(1)(1) 发往一个目录的消息会产生两种不同类型的动作发往一个目录的消息会产生两种不同类型的动作 更新目录状态更新目录状态 发送消息满足请求服务发送消息满足请求服务(2)(2) 目录项可能接收到三种不同的请求目录项可能接收到三种不

130、同的请求 读失效读失效 写失效写失效 数据写回数据写回 (3)(3) 在各个状态下所接收到的请求和相应的操作在各个状态下所接收到的请求和相应的操作 当一个块处于当一个块处于未缓冲状态未缓冲状态时，对此块发出的时，对此块发出的 请求及处理操作为请求及处理操作为 192第七章 多处理机 读失效读失效 将存储器数据送往请求方处理器，且本处理器将存储器数据送往请求方处理器，且本处理器 成为此块的唯一共享结点，本块的状态转换为共享。成为此块的唯一共享结点，本块的状态转换为共享。 写失效写失效 将存储器数据送往请求方处理器，此块成为专有。将存储器数据送往请求方处理器，此块成为专有。 当一个块是当一个块是共

131、享状态共享状态时，存储器中的数据是其当前时，存储器中的数据是其当前 最新值，对此块发出的请求及处理操作为最新值，对此块发出的请求及处理操作为 读失效读失效 将存储器数据送往请求方处理器，并将其加入共将存储器数据送往请求方处理器，并将其加入共 享集合。享集合。193第七章 多处理机 写失效写失效 将数据送往请求方处理器，对共享集合中所有的将数据送往请求方处理器，对共享集合中所有的处理器发送写作废消息，且将共享集合置为仅含有此处理器发送写作废消息，且将共享集合置为仅含有此处理器，本块的状态变为专有。处理器，本块的状态变为专有。 当当某某块块处处于于专专有有状状态态时时，本本块块的的最最新新值值保保

132、存存在在共共 享享集集合合指指出出的的拥拥有有者者处处理理器器中中，从从而而有有三三种种可可能能 的目录请求。的目录请求。 读失效读失效 将将“取数据取数据”的消息发往拥有者处理器，使该块的消息发往拥有者处理器，使该块的状态转变为共享，并将数据送回目录结点写入存储的状态转变为共享，并将数据送回目录结点写入存储器，进而把该数据返送请求方处理器，将请求方处理器，进而把该数据返送请求方处理器，将请求方处理器加入共享集合。器加入共享集合。194第七章 多处理机 写失效写失效 本块将有一个新的拥有者。本块将有一个新的拥有者。 数据写回数据写回 拥有者处理器的拥有者处理器的CacheCache要替换此块时必须将其要替换此块时必须将其 写回，从而使存储器中有最新拷贝写回，从而使存储器中有最新拷贝( (宿主结点实际宿主结点实际 上成为拥有者上成为拥有者) )，此块成为非共享，共享集合为空。，此块成为非共享，共享集合为空。3. 3. 对基于目录的对基于目录的CacheCache一致性的多种改进一致性的多种改进 有限映射目录有限映射目录 链式结构目录链式结构目录4. 4. 基于目录的基于目录的CacheCache一致性协议是完全由硬件实现的。一致性协议是完全由硬件实现的。 此外，还可以用软硬结合的办法实现。此外，还可以用软硬结合的办法实现。195