计算机系统结构7多处理机

1、7.1 引 言7.2 对称式共享存储器体系结构7.3 分布式共享存储器体系结构7.4 互连网络 7.5 同 步7.6 同时多线程7.7 多处理机实例第章 多处理机7.1.1 并行计算机体系结构的分类1. 按照Flynn分类法，可把计算机分成 单指令流单数据流（SISD） 单指令流多数据流（SIMD） 多指令流单数据流（MISD） 多指令流多数据流（MIMD）7.1 引 言第章 多处理机2. MIMD已成为通用多处理机体系结构的选择，原因： (1) (1) MIMDMIMD具有灵活性；具有灵活性； (2) (2) MIMDMIMD可以充分利用商品化微处理器在性能价格可以充分利用商品化微处理器在性

2、能价格 比方面的优势。比方面的优势。3. 根据系统中处理器个数的多少，可把现有的MIMD 机器分为两类 （每一类代表了一种存储器的结构和互连策略）（每一类代表了一种存储器的结构和互连策略） (1) (1) 集中式共享存储器结构 动画动画 这类机器有时被称为这类机器有时被称为 SMPSMP机器（机器（Symmetric shared-memory MultiProcessorSymmetric shared-memory MultiProcessor） UMAUMA机器（机器（Uniform Memory AccessUniform Memory Access）7.1 引 言集中共享存储器计算机

3、(2)(2) 分布式存储器结构 动画动画 每个结点包含：每个结点包含： q 处理器处理器q 存储器存储器q I IO O在许多情况下，分布式存储器结构优于集中式共享存储器结构7.1 引 言分布共享存储器计算机 分布式存储器结构的优点 主要缺点q 处理器之间的通信较为复杂，且各处理器之间的处理器之间的通信较为复杂，且各处理器之间的 访问延迟较大。访问延迟较大。q 需要高带宽的互连。需要高带宽的互连。 簇：超结点q 如果大多数的访问是针对本结点的局部存储器，如果大多数的访问是针对本结点的局部存储器， 则可降低对存储器和互连网络的带宽要求；则可降低对存储器和互连网络的带宽要求；q 局部存储器的访问延

4、迟低。局部存储器的访问延迟低。7.1 引 言7.1.2 通信模型和存储器的结构模型1. 地址空间的组织方案（两种）（两种） (1) 物理上分离的多个存储器作为一个逻辑上共享的 存储空间进行编址。这类机器的结构被称为这类机器的结构被称为q 分布式共享存储器结构分布式共享存储器结构 （DSMDSM: Distributed Shared-Memory): Distributed Shared-Memory)q 可缩放共享存储器结构可缩放共享存储器结构 （SSMSSM: Scalable Shared-Memory): Scalable Shared-Memory)q NUMA NUMA机器机器 （

5、NUMANUMA: Non-Uniform Memory Access): Non-Uniform Memory Access)7.1 引 言 (2) 整个地址空间由多个独立的地址空间构成，它 们在逻辑上也是独立的，远程的处理器不能对 其直接寻址。每一个处理器每一个处理器- -存储器模块实际上是一个单独存储器模块实际上是一个单独的计算机，这种机器也称为的计算机，这种机器也称为多计算机。多计算机。7.1 引 言q 共享地址空间的机器 利用利用LoadLoad和和StoreStore指令中的地址隐含地进行指令中的地址隐含地进行 数据通讯。数据通讯。q 多个地址空间的机器 通过处理器间显式地传递消息

6、完成。通过处理器间显式地传递消息完成。 ( (消息传递机器消息传递机器) ) 2. 两种通信模型7.1 引 言 消息传递机器根据简单的网络协议，通过传递消息 来请求某些服务或传输数据，从而完成通信。 例如：例如：一个处理器要对远程存储器上的数据进行访问一个处理器要对远程存储器上的数据进行访问 或操作：或操作： (1) (1) 发送消息，请求传递数据或对数据进行操作；发送消息，请求传递数据或对数据进行操作； 远程进程调用远程进程调用(RPC(RPC， Remote Process Call)Remote Process Call) (2) (2) 目的处理器接收到消息以后，执行相应的操目的处理器

7、接收到消息以后，执行相应的操 作或代替远程处理器进行访问，并发送一个作或代替远程处理器进行访问，并发送一个 应答消息将结果返回。应答消息将结果返回。7.1 引 言 同步消息传递 请求处理器发送一个请求后一直要等到应答请求处理器发送一个请求后一直要等到应答 结果才继续运行。结果才继续运行。 异步消息传递 发送方不先经请求就直接把数据送往数据接发送方不先经请求就直接把数据送往数据接 受方。受方。3.通信机制的性能指标（3个）(1) 通信带宽 理想状态下的通信带宽受限于处理器、存储理想状态下的通信带宽受限于处理器、存储 器和互连网络的带宽。器和互连网络的带宽。 7.1 引 言(2) 通信延迟 理想状

8、态下通信延迟应尽可能地小。 通信延迟发送开销 + 跨越时间 + 传输延迟 + 接收开销(3) 通讯延迟的隐藏 如何才能较好地将通信和计算或多次通信之 间重叠起来，以实现通讯延迟的隐藏。 通常的原则：只要可能就隐藏延迟。 通信延迟隐藏是一种提高性能的有效途径，但 它对操作系统和编程者来讲增加了额外的负担。7.1 引 言4. 不同通信机制的优点 A. 共享存储器通信的主要优点 (1) 与常用的集中式多处理机使用的通信机制兼容。 (2) 易于编程 与传统的编程模式一致 (3) 当通信数据较小时，通信开销较低，带宽利用 较好。 (4) 通过硬件控制的Cache减少了远程通信的频度， 减少了通信延迟以及

9、对共享数据的访问冲突。 7.1 引 言B. 消息传递通信机制的主要优点 (1) 硬件较简单。 (2) 通信是显式的，从而引起编程者和编译程序的 注意，着重处理开销大的通信。q 在共享存储器上支持消息传递相对简单在共享存储器上支持消息传递相对简单q 在消息传递的硬件上支持共享存储器就困难得多。在消息传递的硬件上支持共享存储器就困难得多。 所有对共享存储器的访问均要求操作系统提供地所有对共享存储器的访问均要求操作系统提供地 址转换和存储保护功能，即将存储器访问转换为消址转换和存储保护功能，即将存储器访问转换为消 息的发送和接收。息的发送和接收。7.1 引 言7.1.3 并行处理面临的挑战 并行处理

10、面临着两个重要的挑战并行处理面临着两个重要的挑战： 。 q 程序中有限的并行性程序中有限的并行性q 相对较高的通信开销相对较高的通信开销理论加速比可加速部分比例可加速部分比例）（11系统加速比系统加速比 = =7.1 引 言 例例7.17.1 如果想用如果想用100100个处理器达到个处理器达到8080的加速比，的加速比，求原计算程序中串行部分所占比例。求原计算程序中串行部分所占比例。 解解 动画演示动画演示2. 第二个挑战：多处理机中远程访问的延迟较大 在现有的机器中，处理器之间的数据通信在现有的机器中，处理器之间的数据通信 大约需要大约需要50501000010000个时钟周期。个时钟周期

11、。 1. 第一个挑战：有限的并行性 使机器要达到好的加速比十分困难7.1 引 言机机 器器通信机制通信机制互连网络互连网络处理机数量处理机数量典型远程存储典型远程存储器访问时间器访问时间SPARC Center共享存储器共享存储器总线总线 20 1sSGI Challenge共享存储器共享存储器总线总线 36 1sCray T3D共享存储器共享存储器3维环网维环网 322048 1sConvex Exemplar共享存储器共享存储器交叉开关环交叉开关环 864 2sKSR-1共享存储器共享存储器多层次环多层次环 32256 2-6sCM-5消息传递消息传递胖树胖树 321024 10sInte

12、l Paragon消息传递消息传递2维网格维网格 322048 10-30sIBM SP-2消息传递消息传递多级开关多级开关 2512 30-100s远程访问一个字的延迟时间远程访问一个字的延迟时间 例例 一台一台3232个处理器的计算机，对远程存储个处理器的计算机，对远程存储器访问时间为器访问时间为2000ns2000ns。除了通信以外，假设计算中的。除了通信以外，假设计算中的访问均命中局部存储器。当发出一个远程请求时，本访问均命中局部存储器。当发出一个远程请求时，本处理器挂起。处理器时钟时间为处理器挂起。处理器时钟时间为10ns10ns，如果指令基本，如果指令基本的的CPICPI为为1.0

13、1.0( (设所有访存均命中设所有访存均命中Cache)Cache)，求在没有远程，求在没有远程访问的状态下与有访问的状态下与有0.5%0.5%的指令需要远程访问的状态下，的指令需要远程访问的状态下，前者比后者快多少前者比后者快多少? ? 解解 有有0.5%0.5%远程访问的机器的实际远程访问的机器的实际CPICPI为为 CPICPI基本基本CPICPI远程访问率远程访问率远程访问开销远程访问开销 1.01.00.5%0.5%远程访问开销远程访问开销 7.1 引 言远程访问开销远程访问时间远程访问开销远程访问时间/ /时钟时间时钟时间 2000ns/10ns2000ns/10ns200200个

14、时钟个时钟 CPICPI1.01.00.5%0.5%2002002.02.0 它为只有局部访问的机器的它为只有局部访问的机器的2.02.01.01.02 2倍，倍， 因此在没有远程访问的状态下的机器速度是有因此在没有远程访问的状态下的机器速度是有0.5%0.5%远程访问的机器速度的远程访问的机器速度的2 2倍。倍。 问题的解决 并行性不足：并行性不足： 采用并行性更好的算法采用并行性更好的算法 远程访问延迟的降低：靠体系结构支持和编程技术远程访问延迟的降低：靠体系结构支持和编程技术 7.1 引 言3. 并行程序的计算通信比率 反映并行程序性能的一个重要的度量 计算与通信的比率计算与通信的比率

15、计算通信比率随着处理数据规模的增大而增 加；随着处理器数目的增加而降低。7.1 引 言7.2 对称式共享存储器体系结构 多个处理器共享一个存储器。 当处理器规模较小时，这种机器十分经济。 支持对共享数据和私有数据的Cache缓存 私有数据供一个单独的处理器使用，而共私有数据供一个单独的处理器使用，而共 享数据供多个处理器使用。享数据供多个处理器使用。 共享数据进入Cache产生了一个新的问题 CacheCache的一致性问题的一致性问题第七章 多处理机 (1) 不一致产生的原因（不一致产生的原因（CacheCache一致性问题）一致性问题） I IO O操作操作 CacheCache中的内容可

16、能与由中的内容可能与由I IO O子系统输入输子系统输入输 出形成的存储器对应部分的内容不同。出形成的存储器对应部分的内容不同。 共享数据共享数据 不同处理器的不同处理器的CacheCache都保存有对应存储器单元都保存有对应存储器单元 的内容。的内容。 例例两个处理器两个处理器的的读写读写 7.2.1 多处理机Cache一致性7.2 对称式共享存储器体系结构(2) 存储器的一致性（非正式定义） 如果对某个数据项的任何读操作均可得到其最如果对某个数据项的任何读操作均可得到其最 新写入的值，则认为这个存储系统是一致的。新写入的值，则认为这个存储系统是一致的。 q What: What: 返回给读

17、操作的是什么值返回给读操作的是什么值q When:When: 什么时候才能将已写入的值返回给读操作什么时候才能将已写入的值返回给读操作 需要满足以下满足条件 处理器处理器P P对对X X进行一次写之后又对进行一次写之后又对X X进行读，进行读， 读和写之间没有其它处理器对读和写之间没有其它处理器对X X进行写，则进行写，则 读的返回值总是写进的值。读的返回值总是写进的值。 存储系统行为的两个不同方面存储系统行为的两个不同方面7.2 对称式共享存储器体系结构 一个处理器对一个处理器对X X进行写之后，另一处理器对进行写之后，另一处理器对X X进行进行 读，读和写之间无其它写，则读读，读和写之间无

18、其它写，则读X X的返回值应为写的返回值应为写 进的值。进的值。 对同一单元的写是顺序化的，即任意两个处理器对同一单元的写是顺序化的，即任意两个处理器 对同一单元的两次写，从所有处理器看来顺序都应对同一单元的两次写，从所有处理器看来顺序都应 是相同的。是相同的。 假设 直到所有的处理器均看到了写的结果，一次写操直到所有的处理器均看到了写的结果，一次写操 作才算完成；允许处理器无序读，但必须以程序规定作才算完成；允许处理器无序读，但必须以程序规定 的顺序进行写。的顺序进行写。 7.2 对称式共享存储器体系结构 在一致的多处理机中，Cache提供两种功能： 共享数据的迁移共享数据的迁移 降低了对远

19、程共享数据的访问延迟。降低了对远程共享数据的访问延迟。 共享数据的复制共享数据的复制 不仅降低了访存的延迟，也减少了访问共不仅降低了访存的延迟，也减少了访问共 享数据所产生的冲突。享数据所产生的冲突。 小规模多处理机不是采用软件而是采用硬件技术实现Cache一致性。7.2.2 实现一致性的基本方案7.2 对称式共享存储器体系结构(1) Cache一致性协议 对多个处理器维护一致性的协议。对多个处理器维护一致性的协议。(2) 关键：跟踪记录共享数据块的状态 (3) 共享数据状态跟踪记录技术 q 目录目录 物理存储器中共享数据块的状态及相关信息物理存储器中共享数据块的状态及相关信息 均被保存在一个

20、称为目录的地方。均被保存在一个称为目录的地方。q 监听（监听（snoopingsnooping） 每个每个CacheCache除了包含物理存储器中块的数据拷除了包含物理存储器中块的数据拷 贝之外，也保存着各个块的共享状态信息。贝之外，也保存着各个块的共享状态信息。7.2 对称式共享存储器体系结构 CacheCache通常连在共享存储器的总线上，各个通常连在共享存储器的总线上，各个CacheCache控制器通过监听总线来判断它们是否有总线上请求的控制器通过监听总线来判断它们是否有总线上请求的数据块。数据块。q 两种更新协议 (1) 写作废协议 在一个处理器写某个数据项之前保证它对该在一个处理器写

21、某个数据项之前保证它对该 数据项有唯一的访问权。数据项有唯一的访问权。 例例 ： 在写回在写回CacheCache的条件下，监听总线中写作废协议的实现。的条件下，监听总线中写作废协议的实现。7.2 对称式共享存储器体系结构(2) (2) 写更新协议写更新协议 当一个处理器写某数据项时，通过广播使其它当一个处理器写某数据项时，通过广播使其它 CacheCache中所有对应的该数据项拷贝进行更新。中所有对应的该数据项拷贝进行更新。例例 在写回在写回CacheCache的条件下，监听总线中写更新协议的实现。的条件下，监听总线中写更新协议的实现。 处理器行为处理器行为总线行为总线行为CPUA CPUA

22、 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 (3) (3) 写更新和写作废协议写更新和写作废协议性能上的差别性能上的差别主要来自：主要来自：q 对同一数据的多个写而中间无读操作的情况，对同一数据的多个写

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

24、拷贝。7.2 对称式共享存储器体系结构 大多数多处理机系统都采用写作废协议7.2 对称式共享存储器体系结构7.2.3 监听协议及其实现 基本实现技术小规模多处理机中实现写作废协议的关键 利用总线进行作废操作：把要作废的地址放到总线把要作废的地址放到总线上（一个放，多个读）上（一个放，多个读） 写顺序化：由总线实现写直达Cache：因为所有写的数据同时被写回主存，则从主存中总可以取到最新的数据值。对于写回Cache，得到数据的最新值会困难一些，因为最新值可能在某个Cache中，也可能在主存中。7.2 对称式共享存储器体系结构q 增加增加CacheCache中块的标志位中块的标志位 状态：状态：

25、无效（invalid） 无副本无副本 共享（shared） 至少一个副本，clean 独占（exclusive） 唯一副本，dirty Cache Cache块的拥有者：块的拥有者：拥有唯一的拥有唯一的CacheCache块副本块副本 的处理器。的处理器。 q 因为每次总线任务均要检查因为每次总线任务均要检查CacheCache的地址位，这的地址位，这 可能与可能与CPUCPU对对CacheCache的访问冲突。可通过下列两种的访问冲突。可通过下列两种 技术之一降低冲突：技术之一降低冲突： 复制标志位复制标志位 采用多级包容采用多级包容CacheCache （许多系统采用）（许多系统采用）7.

26、2 对称式共享存储器体系结构 监听协议举例 为简单起见，对于对共享块的 Write hit 和 Write miss 不加区分，都按 Write miss 处理写作废，写回法7.2 对称式共享存储器体系结构 存储器分布于各结点中，所有的结点通过网络互 连。访问可以是本地的，也可是远程的。 可以不支持Cache一致性：规定共享数据不进入规定共享数据不进入CacheCache， 仅私有数据才能保存在仅私有数据才能保存在CacheCache中。中。 优点： 所需的硬件支持很少所需的硬件支持很少 ( (因为远程访问存取量仅是一个字因为远程访问存取量仅是一个字( (或双字或双字) )而而 不是一个不是一

27、个CacheCache块块) )7.3 分布式共享存储器体系结构第章 多处理机缺点： (1) (1) 实现透明的软件实现透明的软件CacheCache一致性的编译机制能力一致性的编译机制能力 有限。有限。 (2) (2) 没有没有CacheCache一致性，机器就不能利用取出同一一致性，机器就不能利用取出同一 块中的多个字的开销接近于取一个字的开销块中的多个字的开销接近于取一个字的开销 这个优点，这是因为共享数据是以这个优点，这是因为共享数据是以CacheCache块为块为 单位进行管理的。当每次访问要从远程存储单位进行管理的。当每次访问要从远程存储 器取一个字时，不能有效利用共享数据的空器取

28、一个字时，不能有效利用共享数据的空 间局部性。间局部性。 (3) (3) 诸如预取等延迟隐藏技术对于多个字的存取诸如预取等延迟隐藏技术对于多个字的存取 更为有效，比如针对一个更为有效，比如针对一个CacheCache块的预取。块的预取。 7.3 分布式共享存储器体系结构解决Cache一致性问题的关键： 寻找替代监听协议的一致性协议。 目录协议 在每个结点增加目录存储器，用于存放目录在每个结点增加目录存储器，用于存放目录对每个结点增加目录表后的分布式存储器的系统结构对每个结点增加目录表后的分布式存储器的系统结构7.3 分布式共享存储器体系结构u 目录协议必须实现两种基本操作q 处理读失效处理读失

29、效q 处理对共享、干净块的写处理对共享、干净块的写对共享块写失效的处理是这两个操作的简单组合对共享块写失效的处理是这两个操作的简单组合 (2) 目录必须跟踪记录每个存储块的状态 存储块的状态有三种：块的状态有三种：7.3.1 基于目录的Cache一致性及其实现7.3 分布式共享存储器体系结构q 共享共享 在一个或多个处理器上具有这个块的副本，在一个或多个处理器上具有这个块的副本， 且主存中的值是最新值（所有且主存中的值是最新值（所有CacheCache均相同）。均相同）。q 未缓冲未缓冲 所有处理器的所有处理器的CacheCache都没有该块的拷贝。都没有该块的拷贝。q 专有专有 仅有一个处理

30、器上有该块的副本，且已对该块仅有一个处理器上有该块的副本，且已对该块进行了写操作，而主存的拷贝仍是旧的。这个处理器进行了写操作，而主存的拷贝仍是旧的。这个处理器称为该称为该块的块的拥有者。拥有者。 7.3 分布式共享存储器体系结构(3) 由于写作废操作的需要，还必须记录哪些处理器 有该块的拷贝 方法：方法：对每个主存块设置一对每个主存块设置一个个位向量位向量 当该块被共享时，每个位指出与之对应的处当该块被共享时，每个位指出与之对应的处 理器是否有该块的拷贝。理器是否有该块的拷贝。 当该块为专有时，可根据位向量来寻找其拥当该块为专有时，可根据位向量来寻找其拥 有者。有者。7.3 分布式共享存储器

31、体系结构结点之间发送的消息及其作用7.3 分布式共享存储器体系结构目录状态转换图q 对基于目录的Cache一致性的多种改进 有限映射目录 链式结构目录q 基于目录的Cache一致性协议是完全由硬件实现的。 此外，还可以用软硬结合的办法实现。7.3 分布式共享存储器体系结构7.4 互连网络 互连网络是将集中式系统或分布式系统中的结点连 接起来所构成的网络。 在拓扑上，互连网络为输入和输出两组结点之间提 供一组互连或映象。 本节介绍：构造多处理机的互连网络第章 多处理机7.4.1 互连网络的性能参数1. 互连网络的拓扑结构 (1) 静态网络 由点和点直接相连而成，这种连接方式在由点和点直接相连而成

32、，这种连接方式在 程序执行过程中不会改变。程序执行过程中不会改变。 (2) 动态网络 用开关通道实现，可动态地改变结构，用开关通道实现，可动态地改变结构， 使其与用户程序中通信要求匹配。使其与用户程序中通信要求匹配。7.4 互连网络2. 性能参数 (1) 网络规模：结点数 (2) 结点度：与结点相连接的边的数目。 入度：入度：进入结点的通道数进入结点的通道数 出度：出度：从结点出来的通道数从结点出来的通道数 (3) 网络直径 网络中任意两个结点间最短路径长度的最大值。 (4) 等分宽度 在将某一网络切成相等两半的各种切法中， 沿切口的最小通道边数。7.4 互连网络q 对称网络对称网络 从其中的

33、任何一个结点看，拓扑结构都是一样的。从其中的任何一个结点看，拓扑结构都是一样的。(5) 路由 在网络通信中对路径的选择与指定。3. 互连函数 如果把互连网络的N个入端和N个出端各自用 整数0，1，N-1代表，则互连函数表示互连的 出端号和入端号的一一对应关系。 7.4 互连网络4. 几种数据路由功能 (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(x,f(xj j)=x)=x0 0

34、 j+1j+1称为该称为该循环的周期循环的周期。 (2) 置换 指对象的重新排序。对于指对象的重新排序。对于n n个对象来说，个对象来说， 有有n!n!种置换。种置换。 7.4 互连网络 例如例如 置换置换=(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) 均匀混洗 n=8（对象个数）的均匀混洗所对应的

35、映射与其逆过程 对对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)=( xf(x)=( xk-2k-2, ,x,x1 1,x,x0,0,x xk-1k-1) ) （将（将x x循环左移循环左移1 1位）位）7.4 互连网络(4) 超立方体路由功能 例例 一个三维二进制立方体网络 7.4 互连网络q 根据最低位根据最低位C C0 0路由路由 q 根据中间位根据中间位C

36、C1 1路由路由q 根据最高位根据最高位C C2 2路由路由 一个一个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) )。有三种路由功能: 分别根据结点的二进制地址（C2 C1 C0）中的某一位来确定7.4 互连网络 (5) 广播和选播 q 广播广播 一对全体的映射。一对全体的映射。q

37、 选播选播 一个子集到另一子集一个子集到另一子集( (多对多多对多) )的映射。的映射。5. 影响互连网络性能的因素 (1) 功能特性 网络如何支持路由、中断处理、同步、请网络如何支持路由、中断处理、同步、请 求消息组合和一致性。求消息组合和一致性。7.4 互连网络(2) 网络时延 单位消息通过网络传送时最坏情况下的时间延迟。单位消息通过网络传送时最坏情况下的时间延迟。(3) 带宽 通过网络的最大数据传输率，用通过网络的最大数据传输率，用MBMBs s表示。表示。(4) 硬件复杂性 诸如导线、开关、连接器、仲裁和接口逻辑等诸如导线、开关、连接器、仲裁和接口逻辑等 的造价。的造价。(5) 可扩展

38、性 在增加机器资源使性能可扩展的情况下，网络在增加机器资源使性能可扩展的情况下，网络 具备模块化可扩展的能力。具备模块化可扩展的能力。 7.4 互连网络7.4.2 静态连接网络1. 线性阵列 一种一维的线性网络，其中N个结点用N-1个链 路连成一行。 q 内部结点度：内部结点度：2 2q 端结点度：端结点度：1 1q 直径：直径：N-1N-1q 等分宽度等分宽度b=1b=17.4 互连网络2. 环和带弦环 (1) 环 用一条附加链路将线性阵列的两个端点连接起 来而构成的。可以单向工作，也可以双向工作。q 结点度：结点度：2 2q 双向环的直径：双向环的直径：N N2 2q 单向环的直径：单向环

39、的直径：N N7.4 互连网络(2)(2) 带弦环 增加的链路愈多，结点度愈高，网络直径就愈小。 7.4 互连网络全连接网络q 结点度结点度: N-1: N-1q 直径最短，为直径最短，为1 17.4 互连网络3. 循环移数网络 通过在环上每个结点到所有与其距离为2的整 数幂的结点之间都增加一条附加链而构成的。q 结点数结点数: 16: 16q 结点度结点度: 7: 7q 直径直径: 2: 27.4 互连网络 如果如果j-ij-i=2=2 r r，r=0,1,2,r=0,1,2,n-1,n-1，网络规模，网络规模N=2N=2n n，则结点，则结点i i与结点与结点j j连接。这种循环移数网络的

40、结连接。这种循环移数网络的结点度为点度为d=2n-1d=2n-1，直径，直径D=nD=n2 2。 7.4 互连网络4. 树形和星形 (1) 一棵5层31个结点的二叉树 一般说来，一棵k层完全平衡的二叉树有 N=2k-1个结点。 最大结点度是3，直径是2(k-1)。 (2) 星形q 一种一种2 2层树层树q 结点度较高，为结点度较高，为d=N-1d=N-1q 直径较小，是一常数直径较小，是一常数2 27.4 互连网络7.4 互连网络5.5. 胖树形胖树形7.4 互连网络6. 网格形和环网形 (1) 一个33网格形网络 一般说来，N=nk 个结点的k维网络的内 部结点度为2k ，网络直径为k(n-

41、1)。边结 点和角结点的结点度分别为3或2。 (2) 环形网 可看做是直径更短的另一种网格 环形网沿阵列每行和每列都有环形连接 一个nn二元环网q 结点度为结点度为4 4q 直径为直径为2 2* *n/2n/2 7.4 互连网络7.4 互连网络7. 超立方体 一种二元n-立方体结构 一般说来，一个n-立方体由N=2n 个结点组成， 它们分布在n维上，每维有两个结点。 例例8 8个结点的个结点的3-3-立方体立方体 4-4-立方体立方体 一个n-立方体的结点度等于n，也就是网络的 直径。 7.4 互连网络7.4 互连网络8. k元n-立方体网络 环形、网络形、环网形、二元n-立方体(超立方 体)

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

43、7.4 互连网络7.4.3 动态连接网络 1. 动态互连网络的三个主要操作特征 定时 开关 控制2. 2. 根据级间连结方式，动态互连网络分为 (1) 单级网络 也称循环网络 (2) 多级网络 由一级以上的开关元件构成。 这类网络可以把任一输入与任一输出相连。 7.4 互连网络 阻塞网络 如果同时连接多个输入输出对时如果同时连接多个输入输出对时, ,可能会引可能会引 起开关和通信链路使用上的冲突。起开关和通信链路使用上的冲突。 大多数多级网络都是阻塞网络。大多数多级网络都是阻塞网络。 非阻塞网络 如果多级网络通过重新安排连接方式可以如果多级网络通过重新安排连接方式可以 建立所有可能的输入输出之

44、间的连接。建立所有可能的输入输出之间的连接。 7.4 互连网络q 总线仲裁总线仲裁q 中断处理中断处理q 一致性协议一致性协议q 总线事务的处理总线事务的处理3. 几类主要的开关网络 (1) 总线系统 优点：价格较低 带宽较窄 缺点：容易产生故障 总线研制中的重要问题7.4 互连网络 一种总线连接的多处理机系统 (2) 交叉开关网络 单级无阻塞置换网络 每个交叉点是一个可以打开或关闭的开关， 提供源(处理器)和目的(存储器)之间点对点 的连接通路。 交叉点开关网络中n对处理器可以同时传送 数据。 交叉开关网络的带宽和互连特性最好。 一种交叉开关网络 7.4 互连网络7.4 互连网络(3) 多端

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

46、(4) 多级网络 多级网络可用于构造大型多处理机系统。 一种通用多级网络一种通用多级网络 各种多级网络的区别就在于所用开关模各种多级网络的区别就在于所用开关模 块和级间连接模式的不同。块和级间连接模式的不同。7.4 互连网络 由由a ab b开关模块和级间构成的通用多级互连网络结构开关模块和级间构成的通用多级互连网络结构 2 22 2开关四种可能的连接方式开关四种可能的连接方式 OmegaOmega网络网络 7.4 互连网络 一个一个161616 Omega16 Omega网络网络7.5 同 步 通常是使用硬件提供的有关同步指令，通过用户级软件例程建立的。 7.5.1 基本硬件原语 在多处理器

47、同步中，主要功能是一组能自动读出后并进行写存储单元的硬件原语。它们能够自动读修改单元。通常情况下，用户不直接使用基本的硬件原语，原语主要供系统程序员用来编制同步库函数。 第章 多处理机 功能：将一个存储单元的值和一个寄存器的值 进行交换。建立一个锁，锁值为“0”表示开锁， 为“1”表示上锁。 处理器加锁时，将对应于该锁的存储单元的值 交换为某个寄存器的值“1”。如果返回值为“0”， 存储单元的值此时已置换为“1”，防止了别的进 程竞争该锁。 实现同步的关键: 操作的原子性1. 典型操作:原子交换（atomic exchange）7.5 同 步2. 测试并置定（test_and_set） 先测试

48、一个值，如果符合条件则修改其值。先测试一个值，如果符合条件则修改其值。3. 读取并加1（fetch_and_increment） 它返回存储单元的值并自动增加该值。它返回存储单元的值并自动增加该值。4. 使用指令对q LL(load linked LL(load linked或或load locked)load locked)的取指令的取指令q SC(store conditional)SC(store conditional)的特殊存指令的特殊存指令7.5 同 步例例实现对由实现对由R1R1指出的存储单元进行原子交换操作指出的存储单元进行原子交换操作 trytry：mov R3,R4 mov

49、 R3,R4 ；送交换值；送交换值 ll R2,0(R1) ll R2,0(R1) ；load linkedload linked sc R3,0(R1) sc R3,0(R1) ；store conditionalstore conditional beqz R3,try beqz R3,try ；存失败转移；存失败转移 mov R4,R2 mov R4,R2 ；将取的值送往；将取的值送往R4R4 最终最终R4R4和由和由R1R1指向的单元值进行原子交换，在指向的单元值进行原子交换，在llll和和scsc之间如有别的处理器插入并修改了存储单元的值，之间如有别的处理器插入并修改了存储单元的值，

50、scsc将返回将返回“0 0”并存入并存入R3R3中，从而使指令序列再重新循环。中，从而使指令序列再重新循环。7.5 同 步 llsc机制的一个优点：可用来构造别的同步原语 例如：例如：原子的原子的fetch-and-incrementfetch-and-increment try try： ll R2,0(R1) ll R2,0(R1) ；load linkedload linked addi R2,R2, addi R2,R2,1 1 ；增加；增加 sc R2,0(R1) sc R2,0(R1) ；store conditionalstore conditional beqz R2,try

51、 beqz R2,try ；存失败转移；存失败转移 指令对的实现必须跟踪地址 由由llll指令指定一个寄存器，该寄存器存放着一个指令指定一个寄存器，该寄存器存放着一个 单元地址，这个寄存器常称为单元地址，这个寄存器常称为连接寄存器连接寄存器。7.5 同 步7.5.2 用一致性实现锁 采用多处理机的一致性机制来实现旋转锁。 旋转锁 处理器环绕一个锁不停地旋转而请求获得该锁。处理器环绕一个锁不停地旋转而请求获得该锁。1. 无Cache一致性机制 在存储器中保存锁变量，处理器可以不断地通在存储器中保存锁变量，处理器可以不断地通 过一个原子操作请求加锁，比如先交换，再测试返过一个原子操作请求加锁，比如

52、先交换，再测试返 回值从而知道锁的状况。释放锁的时候，处理器可回值从而知道锁的状况。释放锁的时候，处理器可 简单地将锁置为简单地将锁置为“0 0” 。 7.5 同 步 li R2 li R2，1 1lockitlockit： exch R2,0(R1) exch R2,0(R1) ；原子交换；原子交换 bnez R2bnez R2，lockit lockit ；是否已加锁；是否已加锁? ?2. 机器支持Cache一致性 将锁缓冲进入将锁缓冲进入CacheCache，并通过一致性机制使锁值保，并通过一致性机制使锁值保 持一致。持一致。 7.5 同 步 优点q 可使可使“环绕环绕”的进程对本地的进

53、程对本地CacheCache块进行操作；块进行操作；q 可利用锁访问的局部性，即处理器最近使用过可利用锁访问的局部性，即处理器最近使用过 的锁不久又会使用。的锁不久又会使用。 改进旋转锁(获得第一条好处) 使其环绕过程仅对本地Cache中锁的拷贝进行读， 直到它返回“0”确认锁可用，然后再进行加锁交换操 作。使用锁完毕后新竞争又开始进行。7.5 同 步 lockitlockit：lw R2lw R2，0(R1) 0(R1) ；取锁值；取锁值 bnez R2bnez R2，lockit lockit ；锁不可用；锁不可用 li R2li R2，1 1 ；存入锁值；存入锁值 exch R2exch

54、 R2，0(R1) 0(R1) ；交换；交换 bnez R2bnez R2，lockit ;lockit ;如锁不为如锁不为0 0转移转移 上面给出了对于三个处理器竞争锁的操作。一旦上面给出了对于三个处理器竞争锁的操作。一旦处理器存入处理器存入“0 0”释放锁，所有别的释放锁，所有别的CacheCache对应块均被对应块均被作废，必须取新的值来更新它们锁的拷贝。作废，必须取新的值来更新它们锁的拷贝。 一个处理器一个处理器CacheCache会先获得未加锁值并执行交换会先获得未加锁值并执行交换操作，当别的操作，当别的CacheCache失效处理完后，它们会发现已被失效处理完后，它们会发现已被加锁

55、，所以又必须不停地测试环绕。加锁，所以又必须不停地测试环绕。7.5 同 步表表7.5 7.5 三个处理机对锁的使用三个处理机对锁的使用步骤步骤 处理器处理器P0处理器处理器P1处理器处理器P2锁状态锁状态总线总线/目录操作目录操作1占有锁占有锁环绕测试环绕测试lock=0环绕测试环绕测试lock=0Shared无无2将锁置为将锁置为0（收到作废命令）（收到作废命令）(收到作废命令收到作废命令)ExclusiveP0发锁变量作废消息发锁变量作废消息3 Cache失效失效Cache失效失效Shared总线总线/目录处理目录处理P2 Cache失效失效,锁从锁从P0写回写回4 总线总线/目录忙则等目

56、录忙则等待待Lock=0SharedP2 Cache失效处理失效处理5 Lock=0执行交换，导执行交换，导致致 Cache失效失效SharedP1Cache失效处理失效处理6 执行交换，导致执行交换，导致 Cache失效失效 交换完毕，返交换完毕，返回回0置置lock=1Exclusive总线总线/目录处理目录处理P2 Cache失效失效,发作废消息发作废消息7 交换完毕，返回交换完毕，返回1进入关键处理进入关键处理段段Shared总线总线/目录处理目录处理P2 Cache失效，写回失效，写回8 环绕测试环绕测试lock=0 无无7.5 同 步 llsc原语的另一个状态：读写操作明显分开。

57、Ll不产生总线数据传送，这使下面代码与使用经不产生总线数据传送，这使下面代码与使用经 过优化交换的代码具有相同的特点：过优化交换的代码具有相同的特点： lockitlockit： ll R2ll R2，0(R1) 0(R1) ；load-linked bnez R2 bnez R2，lockit lockit ；锁无效；锁无效 li R2,li R2,，1 1 ；加锁值；加锁值 sc R2sc R2，0(R1) 0(R1) ；存；存 beqz R2beqz R2，lockit lockit ；如存失败转移；如存失败转移 第一个分支形成环绕的循环体，第二个分支解决了两第一个分支形成环绕的循环体，

58、第二个分支解决了两个同时请求锁的处理器竞争问题。尽管旋转锁机制简单并个同时请求锁的处理器竞争问题。尽管旋转锁机制简单并且具有强制性，但难以将它扩展到处理器数量很多的情况。且具有强制性，但难以将它扩展到处理器数量很多的情况。7.5 同 步7.5.3 同步性能问题q 简单旋转锁不能很好地适应可伸缩性。大规模机器 中所有的处理器会产生出大量的竞争问题。 例例7.37.3：设总线上有设总线上有1010个处理器同时准备对同一个处理器同时准备对同一变量加锁。假设每个总线事务处理变量加锁。假设每个总线事务处理( (读失效或写失效读失效或写失效) )是是100100个时钟周期，忽略实际的个时钟周期，忽略实际的

59、CacheCache块锁的读写时间块锁的读写时间以及加锁的时间，求以及加锁的时间，求1010个处理器请求加锁所需的总线个处理器请求加锁所需的总线事务数目。设时间为事务数目。设时间为0 0时锁已释放并且所有处理器在时锁已释放并且所有处理器在旋转，求处理这旋转，求处理这1010个请求时间为多长个请求时间为多长? ?假设总线在新假设总线在新的请求到达之前已服务完挂起的所有请求，并且处理的请求到达之前已服务完挂起的所有请求，并且处理器速度相同。器速度相同。7.5 同 步解解 当当i i个处理器竞争锁的时候，他们完成下列操个处理器竞争锁的时候，他们完成下列操作序列，每一个操作产生一个总线事务：作序列，每

60、一个操作产生一个总线事务： 访问该锁的访问该锁的i i个个LLLL指令操作；指令操作； 试图锁住该锁的试图锁住该锁的i i个个SCSC指令操作；指令操作； 1 1个释放锁的存操作指令。个释放锁的存操作指令。因此对因此对n n个处理器，总线事务的总和为：个处理器，总线事务的总和为： n n (2i+1)=n(n+1)+n=n2+2n(2i+1)=n(n+1)+n=n2+2n i=1 i=1对于对于1010个处理器有个处理器有120120个总线事务，需要个总线事务，需要1200012000个时个时钟周期。钟周期。 7.5 同 步 本例中本例中问题的根源问题的根源是锁的竞争、存储器中锁访问是锁的竞争