计算机系统结构(第二版)尹朝庆主编-第6章_多处理机.ppt

第6章 多处理机 6.1 多处理机的结构与特点 6.2 多处理机的cache一致性 6.3 多处理机的软件 6.4 多处理机的性能 6.5 mimd并行机结构模型 1 第6章 多处理机 多处理机具有两台以上处理机，每台处理机可以带有 本地cache、本地存储器、甚至i/o设备，它们都能独立 执行各自的程序。多台处理机之间通过总线、纵横交叉 开关、多级互连网络或高速的商品化网络实现互连。多 处理机可以通过共享存储器，也可以通过消息传送系统 来实现处理机间的通信。多台处理机在操作系统的控制 下，实现资源的统一分配与调度。 2 第6章 多处理机 6.1多处理机的结构与特点 6.1.1 多处理机的结构 多处理机在系统结构上可分为两类： 紧耦合多处理机 松耦合多处理机 3 第6章 多处理机 紧耦合多处理机 紧耦合多处理机 是通过共享主存来 实现处理机间的通 信的。各处理机与 主存之间通过一个 互连网络连接。它 的典型结构如图6.1 所示。 4 第6章 多处理机 在紧耦合多处理机系统中，为了减少处理机访问主存的 冲突而采取的措施有： v 多处理机的主存采用多模块交叉存取。模块数越多，发生 访主存冲突的概率将越低，但必须解决好数据在各存储器模 块中的定位和分配。 v 让每台处理机拥有一个小容量的本地存储器，用来存放频 繁使用的核心代码等，以减少对主存的访问。 v 让每台处理机都有一个cache，以减少对主存的访问。但 要解决好cache与主存之间以及各个cache之间的数据一致 性问题。 5 第6章 多处理机 紧耦合多处理机按所用处理机类型是否相同可分为同 构型和异构型两种。而按其对称性又可分为对称式多处理 机和非对称式多处理机。 如果紧耦合多处理机中的每台处理机在访问任意一个 存储器模块或i/o用设备时，都具有同等的能力，那么这个 系统就具有对称性。反之，表示多处理机是非对称的。一 个多处理机要成为对称式多处理机必须满足两个条件：首 先存储器必须是集中共享的，其次系统所用的互连网络也 必须是对称的。 6 第6章 多处理机 具有非对称i/o子系统的多处理机如图6.2所示。 7 第6章 多处理机 采用冗余连接非对称i/o子系统的多处理机如图6.3所示 8 第6章 多处理机 在紧耦合多处理机中，常见的组合是同构对称式多处 理机及异构非对称式多处理机。 1）同构对称式多处理机 sequent公司生产的balance多处理机就是同构对称 式的，它的结构如图6.4所示。 9 第6章 多处理机 10 第6章 多处理机 2）异构非对称式多处理机 异构非对称式多处理机的一般结构如图6.5所示。 11 第6章 多处理机 2. 松耦合多处理机 松耦合多处理机是通过消息传送方式来实现处理机间的相 互通信的。每台处理机是由一个独立性较强的计算机模块组 成，该模块由处理器、较大容量的本地存储器（在运算时所 需的绝大部分的指令和数据均取自本地存储器）、i/o设备以 及网络接口电路组成。各模块之间通过消息传送系统(mts)相 连接。当不同模块上运行的进程间需要通信时，通过网络接 口电路及消息传送系统进行信息交换。由于这种相互间的耦 合程度是很松散的，因此称之为松耦合多处理机。 12 第6章 多处理机 松耦合多处理机可分为层次式和非层次式两种结构。 1）松耦合非层次式多处理机 图6.6所示是一个典型的通过消息传送系统进行互连的 松耦合非层次式多处理机。 13 第6章 多处理机 2）松耦合层次式多处理机 松耦合层次式多处理机采用多级总线实现层次连接。图6.7 所示为卡内基梅隆大学研制的cm* 松耦合层次式多处理机。 14 第6章 多处理机 6.1.2 多处理机的特点 灵活性和通用性强 高层次的并行性等级 并行任务派生 进程同步 资源分配和任务调度 15 第6章 多处理机 6.2 多处理机的cache一致性 cache作为提高系统性能的一种技术手段在计算机系统 中得到普遍的使用。在共享存储器的多处理机中，每台处理 机都有自己的局部cache。这类多处理机在运行一个具有多 个进程的程序时，各处理机可能会使用到共享存储器中的同 一数据块，为维持多处理机的高速运行，这些共享数据块将 被调入各处理机的局部cache中。由于多个处理机是异步地 独立操作，可能使共享存储器中同一数据块的不同cache拷 贝出现不一致，就可能危及系统的正常运行，这就是cache 的一致性问题。 16 第6章 多处理机 6.2.1 出现cache一致性问题的原因 出现cache一致性问题的原因主要有3个： 共享可写的数据 进程迁移 i/o传输 17 第6章 多处理机 1共享可写数据引起的不一致 假设在写操作之前，cache的初始状态如图6.8(a)所示。处 理机p1和p2的局部高速缓冲存储器cache1和cache2中分别有共 享存储器的某个数据x的副本。 18 第6章 多处理机 若采用写直达法，如图6.8(b)所示，当处理机p1改写cache1 中的数据为x时，共享存储器中的相应数据也立即更新为x，这 将导致cache1中的数据与cache2中所缓存的数据不一致。 19 第6章 多处理机 若采用写回法，如图6.8(c)所示，当处理机p1改写cache1 中的数据为x时，cache1的变化不会引起cache2和共享存储器 的变化，这将导致cache1中的数据与共享存储器和cache2中 所缓存的数据不一致。 20 第6章 多处理机 2进程迁移引起的不一致 在多处理机上，有时为了提 高系统的效率而允许进程迁移， 将一个尚未执行完而被挂起的进 程调度到另一个空闲的处理机上 去执行，使系统中各处理机的负 荷保持均衡。但这样做可能会造 成cache一致性问题。 假设在迁移前cache的初始 状态仍如图6.9(a)所示，处理机p1 的cache1中有共享存储器中数据 x的拷贝，而处理机p2的cache2 中没有该数据。 21 第6章 多处理机 若采用写直达法，如图6.9(b) 所示，当某进程从p1迁移到p2后， 处理机p2在执行此进程时需要使用 数据x时，会将x所在块由共享存储 器调入cache2。假设进程运行时 将cache2的数据x改写为x，在共 享存储器中的相应数据也立即更新 为x，这将导致共享存储器和 cache2中的数据与处理机p1中 cache1所缓存的数据的不一致。 22 第6章 多处理机 若采用写回法，如图6.9(c) 所示，当处理机p1修改cache1中 的数据成x时cache1的变化不会 引起共享存储器的变化。当某进 程从p1迁移到p2后，处理机p2在 执行此进程时需要使用数据x时， 会将x所在块由共享存储器调入 cache2。此时调入的数据x并非 是已经修改过的x，这将导致共享 存储器及cache2与处理机p1中 cache1所缓存的数据的不一致。 23 第6章 多处理机 3i/o操作引起的不一致 假设在执行i/o操作之 前，cache的初始状态如 图6.10(a)所示。处理机p1 和p2的局部cache中分别 有共享存储器的某个数据x 的拷贝。 24 第6章 多处理机 若采用写直达法，当i/o 处理机执行输入操作，直接将 共享存储器中的数据x改写成x 时，将导致cache1和cache2 中的数据与共享存储器数据的 不一致，如图6.10(b)所示。 25 第6章 多处理机 若采用写回法，当处理机 p1将cache1中的数据x改写为x 时，由于cache1数据的修改不 会立即引起共享存储器中数据x 的更新，此时若此数据恰好被 i/o处理机输出，就会造成输出 错误，如图6.10(c)所示。 26 第6章 多处理机 解决多处理器维护cache一致性的协议称为cache一致性 协议。实现cache一致性协议的关键是跟踪共享数据块的状态 。目前有两类协议，它们采用了不同的共享数据状态跟踪技术 ，分别适合于不同的系统结构。 （1）监听：每个cache除了包含物理存储器中块的数据 拷贝之外，也保存着各个块的共享状态信息。这是一种基于总 线的一致性协议，各处理机通过监听总线上处理机与存储器之 间的cache操作事件，对各自局部cache中的数据采取保持一 致性的措施。 （2）目录：物理存储器中共享数据块的状态及相关信息 均被保存在一个称为目录的地方。共享数据块的变化通过此数 据块所在的各目录项，将一致性命令发给所有存放该数据块拷 贝的cache。 27 第6章 多处理机 6.2.2 监听一致性协议 在基于总线互连结构的系统中，各处理机的cache都 连接到公共总线。一般都采用监听协议，通过总线监听 机制实现高速缓存和共享存储器之间的数据一致性。监 听协议有两种策略来保持cache一致性： 写无效策略 写更新策略 28 第6章 多处理机 1. 写无效策略 写无效策略是指在某局部 cache数据被修改后，使所有其它 cache中的相应数据拷贝都无效。 假设在写操作之前，cache的 初始状态如图6.11(a)所示。处理机 p1和p2的局部cache中都存有共享 存储器中数据x的拷贝，图中数据x 加虚线框表示数据x所在的数据块。 当处理机p1要进行写操作时， 它必须首先获得对x的唯一访问权， 然后更新数据为x并使cache2中的 相应数据块拷贝失效（标志为i）。 29 第6章 多处理机 若采用写直达法，则共享 存储器中的数据x将会立即更新 为x，如图6.11(b)所示。当处理 机p2访问已修改的数据x时，会 发生cache2失效并从共享存储 器中读取新值x，同时将x所在 数据块调入cache2。 30 第6章 多处理机 若采用写回法，则共享存 储器中数据x所在的数据块也 将被设置为无效，如图6.11(c) 所示。当处理机p2访问已修改 的数据x时，会发生cache2失 效并从处理机p1的cache1读取 新值x，同时将x所在数据块 调入cache2并且更新共享存储 器中的相应数据块。 31 第6章 多处理机 2.写更新策略 写更新策略是指在某局部 cache数据被修改后，通过总线 广播修改后的数据使所有含有相 应数据拷贝的其他cache进行更 新。 假设在写操作之前，cache 的初始状态如图6.12(a)所示。处 理机p1和p2的局部cache中都存 有共享存储器中数据x的拷贝。 32 第6章 多处理机 若采用写直达法，则共享存储器中数据x所在的数据块将会 立即更新，如图6.12(b)所示。若采用写回法，则共享存储器中 数据x所在的数据块将会被设置为无效，如图6.12(c)所示。 33 第6章 多处理机 写更新和写无效策略性能上的差别来自三个方面： 对同一数据的多个写而中间无读操作的情况，写更新策 略需进行多次写广播操作，而在写无效策略下只需一次 置无效操作。 对同一块中多个字进行写操作，写更新策略对每个字的 写均要进行一次广播，而在写无效策略下仅在对该块第 一次写时进行置无效操作即可。写无效是针对cache块 进行操作，而写更新则是针对字（或字节）进行操作。 从一个处理机写到另一个处理机读之间的延迟通常在写 更新模式中较低，因为它写数据时马上更新了相应的其 他cache中的内容（假设读的处理器cache中有此数据 ）。而在写无效策略中，需要读一个新的拷贝。 34 第6章 多处理机 6.2.3 基于目录的协议 在监听协议中，每当cache被修改时，要与所有的 cache进行通信，包括对于可能共享的数据的写操作，这可 能导致总线的流量大大增加。 基于目录的协议的基本思想是：使用cache目录来记录 可以进入cache的每个数据块的访问状态、该块在各个处理 机的共享状态以及是否修改过等信息。把一致性命令只发给 存有相应数据块拷贝的cache，从而支持cache的一致性。 各种目录协议的主要差别是目录存放什么信息以及如何 维护信息。 35 第6章 多处理机 根据目录的结构特点，基于目录的协议可分 为三类： 全映射目录（full-map directory ） 有限目录（limited directory） 链式目录（chained directory） 36 第6章 多处理机 1. 全映射目录协议 全映射目录协议规定共享存储器中的每个数据块 都有一个目录项，每个目录项中有n个处理机位和一个 重写位，其中n为处理机的台数，目录项结构如图6.13 所示。 37 第6章 多处理机 下面以三个处理机的系统为例，说明全映射目录的三种状 态以及全映射目录协议保持cache一致性的原理。 （1）处理机cache中没有包含单元x的数据块副本 全映射目录的第一种状态。此时，包含单元x的数据块bd 目录项中的三个处理机位均为“0”，表示整个系统所有cache中 都没有数据块bd的副本；重写位为未写(c)状态，表示没有一台 处理机允许写入该数据块。 38 第6章 多处理机 （2）处理机从共享存储器读入数据块到cache 当三台处理机都有过读x的请求之后，全映射目录出现第二 种状态。目录项中的三个处理机位被置“1”，表示这些cache中 已有数据块bd的拷贝；重写位仍为未写状态，不允许处理机写 cache块bd。此时，三个cache中bd的cache块状态位均为有 效位1，允许写位0，与cache目录的状态位一致。 39 第6章 多处理机 （3）处理机写cache块 如果处理机p3向cache3发出写x（或bd中其它单元）的请求， 全映射目录将从第二种状态转换到第三种状态，此时的cache全映 射目录呈现第三种状态。目录项中cache1和cache2的处理机位被 置“0”，表示这些cache中数据块bd的拷贝已失效；cache3的处理机 位为“1”，同时重写位为重写状态，表示允许处理机p3写cache块bd ，且cache3中的bd块已被修改为bd。 40 第6章 多处理机 2. 有限目录协议 有限目录协议与全映射目录协议十分相似，都有一位 重写位，但有限目录的目录项中的指针（处理机位）实际上 是数目固定的若干个处理机编号。若共有n台处理机，则每 个处理机指针为log2n位。有i个指针域的目录项最多只能允 许该数据块装入i个cache中，有限目录协议使用in个指 针，可以缓解目录过大的问题。 41 第6章 多处理机 如图6.15所示，假设多处理机系统中共有三台处理机，目 录项中只有两个指针域。当p1和p2的cache中都有单元x所在数 据块bd的拷贝时，该数据块对应的目录项中的两个指针分别指 向处理机p1和p2。 42 第6章 多处理机 3. 链式目录协议 链式目录通过将目录信息分布到多个小规模的本地目录 中来模拟全映射机制。其主要思想是通过维护一个目录指针链 来跟踪共享数据块的拷贝。要想得到某个数据块在所有cache 中的共享情况，必须搜索整个cache目录链。链式目录的优点 在于既不限制共享数据块的拷贝数目，又保持了可扩展性。链 式目录有两种实现方法，单向链和双向链。若采用比较简单的 单向链，则目录项中除一位重写位之外，只需要一个指针域。 43 第6章 多处理机 采用单向链的链式目录如图6.16所示。 44 第6章 多处理机 6.3 多处理机的软件 6.3.1并行算法 算法对于并行性的开发至关重要。算法必须适应具体的计 算机结构。对表达式e1abxcx2dx3 ，顺序算法与并行 算法比较如图6.17所示。将运算过程用树形流程图来表示的方 法。运算的级数 就是树的高度， 用tp代表；p为 所需处理机数目 ；sp为加速比 ，sptl/tp； ep为效率，ep sp/p 45 第6章 多处理机 对树进行变换来降低树高，减少运算级数，即可提高运 算的并行性。树形结构可以用交换律、结合律、分配律来变 换。 先从算术表达式的最直接形式出发，利用交换律把相同 的运算集中在一起；再利用结合律把参加运算的操作数（称 原子）配对，尽可能并行运算，组成树高最小的子树；最后 利用分配律，平衡各分支运算的级数，把这些子树结合起来 ，使总级数减至最少。 46 第6章 多处理机 例如：某表达式e2ab(cdefg)h，需7级运算， 如图6.18(a)所示。利用交换律和结合律改写为e2(ah) b(cg)def ，则需5级运算，如图6.18(b)所示。 47 第6章 多处理机 再利用分配律，将上式改写为e2(ah)(bcbg)bdef 则用3个处理机，仅需4级运算。如图6.18(c)所示。 48 第6章 多处理机 6.3.2 程序并行性分析 除算法以外，任务间能否并行在很大程度还取决于程 序的结构形式。 假设一个程序包含p1、p2、pi、pj、pn等 n个程序段，其书写的顺序反映了该程序正常执行的顺序 。为了便于分析，设pi和pj程序段都是一条语句，pi在pj 之前执行，且只讨论pi和pj之间的直接数据相关关系。 49 第6章 多处理机 程序段之间会出现类似的3种数据相关。 如果pi的左部变量在pj的右部变量集内，且pj要从pi取 得运算结果来作为操作数，则称pj“数据相关”于pi。如 pi a = b + d pj c = a * e pj必须取pi算得的a值作为操作数，相当于流水中发 生的“先写后读”相关。 50 第6章 多处理机 如果pj的左部变量在pi的右部变量集内，且当pi未取用其变 量的值之前，不允许被pj所改变，则称pi“数据反相关”于pj。 如 pi c = a * e pj a = b + d 在a的值未被pi取用之前不能被pj所改变，相当于流水中 发生的“先读后写”相关。 如果pi的左部变量也是pj的左部变量，且pj存入其算得的值 必须在pi存入之后。则称pj“数据输出相关”于pi。如 pi a = b + d pj a = c + e pj存入其算得的a值必须在pi存入其结果a之后，相当于 流水中发生的“写写”相关。 51 第6章 多处理机 对程序并行性的影响表现为下列几种可能的 执行次序。 写读串行次序 读写次序 可并行次序 必并行次序 52 第6章 多处理机 1. 写读串行次序 如果程序必须保持前面的语句先写，后面的语句后读的次 序，则允许上述任意一种数据相关存在。一般情况下，执行的 次序不可并行，也不可颠倒。这是通常遇到的典型串行程序。 但有一种特殊情况，即当pi和pj服从交换律时，虽仍需串行执 行，但允许pi和pj的执行次序交换，这称为可交换串行。如 pi a = 2 * a pj a = 3 * a 为可交换串行，但 pi a = b + 1 pj b = a + 1 就不是可交换串行的。 53 第6章 多处理机 2. 读写次序 如果两个程序段之间只包含第2种数据相关，则只须保持前 面的语句先读，后面的语句后写的次序，便允许它们既可串行 执行，也可并行执行，但不可交换串行。如 pi a = b + d pj b = c + e 二者同时执行，能保证pi先读b，pj后写b的次序。又如 pi a = 3 * c/b pj b = c * 5 pk c = 7 + e 三者同时执行虽属可能，但由于处理时间上pi费时最长， pj次之，pk最短，如果不采取特别的同步措施，就不能保证必 要的先读后写次序。 54 第6章 多处理机 3. 可并行次序 如果两程序段之间不存在任何一种数据相关，即无共 同变量，或共同变量仅为右部变量，而不作为左部变量 出现，则它们可以无条件地并行执行。当然，也可以串 行执行，而且是可交换串行的。如 pi a = b * c pj d = b + e 55 第6章 多处理机 4. 必并行次序 如果两程序段的输入变量互为输出变量，同时具有“ 先写后读”和“先读后写”两种相关，以交换数据为目的， 则二者必须并行执行，既不能顺序串行，也不能交换串 行。如 pi a = b pj b = a 两语句的左右变量互相交换，必须并行执行，且需保 证读写完全同步。 56 第6章 多处理机 综上所述：两个程序段之间若有先写后读的数据相关 ，不能并行，只在特殊情况下可以交换串行；若有先读 后写的数据反相关，可以并行执行，但必须保证其写入 共享主存时的先读后写次序，不能交换串行；若有写 写的数据输出相关，可以并行执行 但同样需保证其写入 的先后次序，不能交换串行；若同时有先写后读和先读 后写两种相关，以交换数据为目的时，则必须并行执行 ，且要求读写完全同步，不许顺序串行和交换串行；若 没有任何相关，或仅有右部源数据相同时，可以并行、 顺序串行和交换串行。 57 第6章 多处理机 6.3.3并行程序设计语言 并行算法需要用并行程序来实现，而编写并 行程序所用的程序语言中需要含有能明确表示并 发进程的成分，这就要使用并行程序设计语言。 并行进程的特点是多个进程在时间上重叠地执行 ，而并行程序设计语言必须便于具体描述这些并 行关系。 58 第6章 多处理机 1.描述程序并行性的语句 包含并行性的程序在多处理机上运行时，需要对并行 任务的派生和汇合进行管理。 并行任务的派生和汇合通常是用软件手段来控制的。 要在程序中反映出并行任务的派生和汇合关系，可以在 程序语言中使用fork 语句来派生并行任务，用join语 句来实现对多个并发任务的汇合。 59 第6章 多处理机 语句格式：fork m，其中m为一个新进程开始的标号。 功能：执行一个 fork m 语句时 l继续在原分配的处理机上执行fork m 语句 的原进程； l派生出标号为m开始的新进程。准备好启动 和继续执行新进程所必需的有关信息。若是共享主存 ，则应该产生存储器指针、映像函数和访问权等信息 。 l将空闲处理机分配给被fork语句派生的新 进程，如果所有处理机都忙，则让新进程排队等待。 60 第6章 多处理机 语句格式：join n ，其中n为已派生出的并发进程个数。 join与fork语句相配合，作为每个并发进程的终端语句。 功能：join语句附有一个计数器，其初始值为0。当执行 join语句时，计数器加1，并与n比较。 l若计数器值等于n，表明此进程是执行中的 第n个并发进程经过join语句，则允许该进程通过 join语句，将计数器清0，在其所在的处理机上继 续执行后续语句。 l若计数器值小于n，表明此进程不是并发进 程中的最后一个，可让现在执行join语句的这个 进程先结束，并把它占用的处理机释放出来，分配 给排队等待的其他任务。若无等待任务，则该处理 机空闲。 61 第6章 多处理机 给定算术表达式 z = e + a * b * c/d + f 经并行编译得到如下程序： s1 g = a * b s2 h = c/d s3 i = g * h s4 j = e + f s5 z = i + j 如果不加并行控制语句，该 程序仍是串行程序，不能发挥多 处理机作用。图6.19(a)示出了 各语句间的数据相关情况。 62 第6章 多处理机 利用fork和join语句实现并行任务派生和汇合，可将程 序改写为： fork s2 s1 g = a * b （进程s1） join 2 goto s3 s2 h = c/d （进程s2） join 2 s3 fork s4 i = g * h （进程s3） join 2 goto s5 s4 j = e + f （进程s4） join 2 s5 z = i + j （进程s5） 63 第6章 多处理机 执行这个程序可用p1和p2两个处理机。假定最初的程序在 p1上运行，按照fork语句和join语句对并行任务的派生和汇 合关系，程序执行过程如图6.19(b)所示。 64 第6章 多处理机 作为forkjoin概念的发展，e.w.dijkstra提出一种新的 块结构语言。它把所有可并行执行的语句或进程s1，s2， sn用并行语句对cobegincoend（或parbeginparend）括起 来，如下程序的执行过程如图所示： begin s0； cobegin s1； s2； sn； coend sn+1； end 65 第6章 多处理机 并行语句也可以嵌套。例如： begin s0； cobegin s1； begin s2； cobegin s3；s4；s5；coend s6； end s7； coend s8； end 其程序的执行过程如图6.21所示。 66 第6章 多处理机 2.并行编译 实现算术表达式的并行处理可以应用并行算法编制并行 程序，还可以依靠并行编译程序。有一些编译算法，可以经 过或不经过逆波兰式，直接从算术表达式产生能并行执行的 目标程序。例如，对下列表达式： z = e + a * b * c/d + f 利用普通串行编译算法，产生三元指令组为 1 *ab 2 *1c 3 /2d 4 +3e 5 +4f 6 =5z 指令之间均相关，需5级运算。 67 第6章 多处理机 如采用并行编译算法可得 1 *ab 2 /2d 3 *12 4 +ef 5 +34 6 =5z 其中，1，2为第1级；3，4为第2级；5，6为第3级。分配 给两个处理机，只需3级运算即可实现。 68 第6章 多处理机 6.3.4 多处理机的操作系统 多处理机操作系统的功能与特点 在多处理机中有多台实际的处理机，它可以真正实现多 个进程的并行执行。 在多处理机中有多个进程并行执行，很可能出现若干个 进程同时要求访问某一共享的资源的情况。 在多处理机中有各处理机共享的全局性存储器，还有每 个处理机自己的局部存储器。 多处理机（尤其是松耦合多处理机）表现出任务、资源 和控制上的分布性。 系统的容错性对多处理机，特别是分布式系统是非常重 要的。 69 第6章 多处理机 2. 多处理机操作系统的类型 主从型，即集中控制方式； 单独管理型，即分布控制方式； 浮动管理型，即对称控制方式。 70 第6章 多处理机 6.4 多处理机的性能 多处理机系统是程序并行的基础，使用多处理机的主 要目的是用多个处理机并发执行多个任务来提高解题速 度。只有当多处理机系统的并行性能为程序并行带来较 高的性能时才能产生效益，否则只会增加程序的运行成 本和复杂性。因此，多处理机的性能除取决于多处理机 系统硬件和软件的性能之外，在很大程度上取决于程序 的并行度。 71 第6章 多处理机 6.4.1 任务粒度与系统性能 颗粒规模或粒度是衡量软件进程所含计算量的尺度。 任务粒度过小，辅助开销大，系统效率低；粒度过大，并 行度低，性能也不会很高。 如果用r表示程序用于有效计算的时间开销，c表示处 理机间的通信等的辅助时间开销，则比值r/c就作为衡量 任务粒度大小的依据。在粗任务粒度并行情况下，r/c比 值较大，计算所需的处理机数量少；在细任务粒度并行情 况下，r/c比值较小，计算所需的处理机数量多。用r/c比 值能直观地反映系统的性能，只有r/c比值较大时，开发 并行性才能得到好处。 72 第6章 多处理机 6.4.2 多处理机性能模型 现在我们通过几种不同的多处理机模型来分析r/c的值 对系统性能的影响。 基本模型 随机模型 通信开销为线性函数的模型 完全重叠通信的模型 具有多条通信链的模型 73 第6章 多处理机 1.基本模型 若某应用程序包含m个任务，在一个由n台处 理机组成的系统上运行。为了简单起见，我们先 讨论在一个仅有两台处理机的系统上运行的情况 ，并假设以下两个条件是成立的。 l每个任务的计算时间开销为r，各 处理机的执行速度相同； l不在同一台处理机上运行的两个 任务之间用于通信的额外时间开销为c ，忽略在同一台处理机上运行的两个任 务之间的通信开销。 74 第6章 多处理机 m个任务在两台处理机上有多种分配方法。如果把全 部任务都分配给一台处理机而另一台空闲，则通信开销最 小，但没有并行性。若把k个任务分配给一台处理机，把 （mk）个任务分配给另一台处理机，则系统运行包含m 个任务的应用程序所需总的处理时间为： trmax(mk，k)c(mk)k (6.1) 式中第一项为程序用于计算的时间，取两台处理机执 行时间中的大者；第二项为通信产生的额外开销时间。k 称为任务分配参数。 75 第6章 多处理机 由(6.1)式可知，总处理时间是k的函数, 第一项是k的 线性函数，第二项是k的二次函数。任务分配应使总处理 时间最小，分析任务分配参数k对处理时间的影响可得： l当k0 时(任务集中分配给一台处理机) ，执行时间最长(为rm)，通信时间最短(为0)， 总的处理时间为t1rm； l当km/2时(任务平均分配给两台处理 机) ，执行时间最短(为rm/2)，通信时间最长( 为cm2/4)，总的处理时间为t2rm/2cm2/4 。 76 第6章 多处理机 使总处理时间最短的k的最 佳值的范围为：0km/2。 当0km/2时，max(mk ，k)mk，总处理时间为 tr(mk)c(mk)k ck2(cmr)krm (6.2) t与k的关系曲线为一开口向 下的抛物线，如图6.22所示。 77 第6章 多处理机 由图6.22可见，当k0和km/2时的总处理时间t较小 ，而谁是使总处理时间最小的最佳k值则与任务粒度有关。 设tt1t2，有 trm(rm/2cm2/4) rm/2cm2/4 (6.3) 对(6.3)式进行讨论，并得该模型的结论： l若t0，得r/cm/2，说明任务粒度较 细。此时t1t2，表示采用集中分配策略(k0) 可使总的处理时间最短，为trm； l若t0，得r/cm/2，说明任务粒度 较粗。此时t1t2，表示采用平均分配策略(k m/2)可使总的处理时间最短，为trm/2 cm2/4。 78 第6章 多处理机 现在，讨论包含m个任务的程序，在一个由n台处理机组 成的系统上运行的情况。仍假设各处理机的速度相同，每个任 务的执行时间均为r，将ki个任务分配给第i台处理机，则n台 处理机执行一个包含m个任务的应用程序所需的总处理时间为 (6.4) 式中第一项为n台处理机中最大的计算时间，第二项为不 同处理机上的任务两两之间通信的额外时间开销的总和。这里 ，假设处理机的计算时间和通信时间不会重叠，而且所有的任 务间的通信是串行执行的。 79 第6章 多处理机 与两台处理机系统的基本模型类似，n台处理机系统的 基本模型也有一个决定采用平均分配还是采用集中分配的 临界值。设m为n的倍数，由(6.4)式可得： l当k0 时(采用集中分配策略)，执行时 间最长(为rm)，通信时间最短(为0)，总的处理 时间为t1rm； l当km/n时(采用平均分配策略，将m 个任务尽可能平均分配给n台处理机) ，执行时 间最短(为rm/n)，通信时间最长(为cm2/2(1 1/n)，总的处理时间为 tnrm/ncm2/2(11/n) 80 第6章 多处理机 注意，这里的所谓平均，是指如果任务数m是处理机数 n的整数倍，则每台处理机分得m/n个任务，否则让大多数 处理机分得个任务，一台处理机分配剩余的不足个任务，余 下的处理机空闲不分配任务。这样可减少不必要的通信开销 。例如，有19个任务和6台处理机。让其中4台处理机各分 得个任务，第5台处理机分得余下的3个任务，而第6台处理 机空闲，免去了通信开销。 81 第6章 多处理机 令tt1tn ，有 (6.5) 对(6.5)式进行讨论，由此得出r/c比值对最佳任务分配的 影响： l若t0，得r/cm/2，细粒度任务对应的 r/c比值很小，t1tn表示采用集中分配策略(k 0)将任务集中分配给一台处理机可使总的处理时 间最短，为trm； l若t0，得r/cm/2，粗粒度任务对应 的r/c比值较大，t1tn表示采用平均分配策略 (km/n)将任务平均分配给所有处理机会使总的 处理时间最短，为 trm/ncm2/2(11/n) 82 第6章 多处理机 2. 随机模型 对于n台处理机系统的随机模型，假设各处理机的速度 不一定相同，各任务的执行时间也可能不同。执行一个包 含m个任务的应用程序所需的总处理时间为 (6.6) 其中，ri表示i台处理机执行一个任务所需的时间，其 它参数的含义与n台处理机系统的基本模型相同。 83 第6章 多处理机 例2.2假设有两台处理机，处理机a的速度是b的两倍 ，参考基本性能模型和随机模型的分析，请问如何分配任务能 达到最优性能? 解：由于a处理机的速度是b处理机的两倍，现给b分配k个任 务，每个任务执行的时间为r，则a分配mk个任务，每个任 务执行的时间为r/2，同时设各对任务之间的通信开销为c。 参考基本性能模型和随机模型的系统总处理时间公式，可 写出两台处理机执行m个任务的总处理时间为 (6.7) 式中第一项为并行执行时间，若要使其最小，必须让两个处理 器的执行时间完全相等，即r/2(mk)rk，可得km/3。 84 第6章 多处理机 分析(6.7)式可得： l当k0时(全部任务集中分配给速度快的a 处理机)，计算时间最长(为rm/2)，通信时间最短( 为0)，总处理时间为t1rm/2； l当km/3时(让两个处理机的执行时间相等) ，计算时间最短(为rm/3)，通信时间为2m2c/9， 总处理时间为t2rm/32m2c/9； l当km/2时(将任务平均分配给两个处理机) ，计算时间并不是最短(为rm/2)，但通信开销却是 最大(m2c/4)，故其总处理时间(rm/2m2c/4) 肯 定大于t2。85 第6章 多处理机 由此可知，使总处理时间t最小的k值最佳取值范围为 0km/3。据此简化(6.7)式得 (6.8) 86 第6章 多处理机 t与k的关系曲线为一开口向下的抛物线，如图6.23所示 。其中，图6.23(a) 表示当k0时t取最小值（图中m/3也可 能大于(2mcr)/(4c)，图中未标出），图6.23(b) 表示当k m/3时t取最小值。 87 第6章 多处理机 具体k取何值能使总处理时间最短仍与任务粒度有关。 设tt1t2，有 (6.9) 分析上式并得以下结论： l若t0，得r/c4m/3，说明任务粒度较 细。此时取k0可使总的处理时间最短，为t rm/2； l若t0，得r/c4m/3，说明任务粒度 较粗。此时取km/3可使总的处理时间最短，为 trm/32m2c/9。 88 第6章 多处理机 3. 通信开销为线性函数的模型 在基本模型中，我们假设每一对在不同处理机上的任 务之间都要通信，因此通信开销随处理机数目的增加以二 次函数增加。实际上一个任务要同另一台处理机上的所有 任务通信，且通信内容相同，只需向这台处理机发送一次 信息就可以了，当信息到达该处理机后，在这台处理机上 各任务之间的信息传递就不必花费通信开销了。 89 第6章 多处理机 在通信开销为线性函数的模型中，就假设通信开销与处理 机的数目n成正比，而不是同分配的任务数成正比。如果把m个 任务分配给n台处理机，并假设m是n的整数倍，各处理机的速 度相同，每个任务的执行时间均为r，则总的处理时间为 trmax(ki)cn (6.10) 式中的第一项与任务的分配有关，第二项与任务的分配无关。 如果把m个任务平均地分配给n台处理机，那么第一项等于 rm/n，使计算时间最短。总处理时间为t(n)rm/ncn。当 n增加时，第二项的增加甚至会超过第一项的减少。所以存在一 个最大的n值，这时的性能最佳，这个n值是r/c的函数。 90 第6章 多处理机 把m个任务平均地分配给n1台处理机，则总处理时间为 t(n1)rm/(n1)c(n1) 对 m个任务多分配一台处理机是希望总处理时间减少，即 t(n1)t(n)，由此可得出进一步提高并行性的条件为： 或 n (6.11) 上式表明，如果分配m个任务给n台处理机并行处理，当 任务的r/c比值已达到临界值n(n1)/m后，总的处理时间不 会随n的增加而减少，反而也会增加。原因是通信开销的增加 超过了提高并行性带来的好处。式(6.11)的第二种形式直接给 出了可使用处理机数量n的上限。 91 第6章 多处理机 该模型的结论是：将任务平均地分配给各台处理机， 且当处理机的数目 时，总的处理时间最短。 在本模型中，通信开销随着n值的增大线性增加，当n 超过临界值时，计算时间的减少将小于通信开销的增加， 这使得系统的整体性能下降。前面的几种模型告诉我们， 在某种情况下，限制并行性反而能获得高性能，也就是说 ，使用的处理机数目并不是越多越好。 92 第6章 多处理机 4. 完全重叠通信的模型 完全重叠通信是指任务间的通信过程可以完全与任务 的计算过程重叠进行以使额外开销趋于零。在n台处理机 系统的完全重叠通信模型中，执行包含m个任务的程序所 需的总处理时间为 93 第6章 多处理机 通信过程与计算过程完全重叠时，计算时间越短，总处 理时间也就越短。当任务平均分配时，即km/n并带入式 (6.12)，得最短计算时间为 (6.13) 通信时间为 (6.14) 对于完全重叠通信模型，计算时间等于通信时间，由式 (6.13)和(6.14)得 (6.15) 94 第6章 多处理机 当n值很大时，1/n可忽略，式(6.15)可简化为 (6.16) 式(6.16)表明，包含m个任务的程序在n台处理机上并行 处理，若任务间的通信过程能与计算过程重叠进行，则只有 当r/c比值等于或大于mn/2，才能将通信的开销完全屏蔽， 从而使总处理时间最短。式(6.16)的第二种形式直接给出了 可使用处理机数量n的上限，并显示处理机数量n的选择与可 提供的任务数m成反比。 95 第6章 多处理机 若n的值不是很大，则式(6.15)中的1/n不能忽略。如对n 2的两台处理机完全重叠通信的理想模型，有 (6.17) 简化上式，得r/cm/2，满足此关系时总处理时间最短 ，为trm/2。 该模型的结论是：将任务平均地分配给各台处理机，当处 理机的数目n较大且等于2r/(cn) 时，计算时间与通信时间完 全重叠，且总的处理时间最短。 96 第6章 多处理机 5. 具有多条通信链的模型 如果每台处理机与其他任何一台处理机之间都有专用的通 信链路，而且链路和处理机都支持双向通信。由于一台处理机 在某一时刻只能与另一台处理机通信，则在一个具有n台处理 机的系统中，通信过程的最大并发度为n。在这种理想情况下 ，总的通信开销可缩短为原来通信过程串行执行时的1/n。 在此具有多条通信链路支持并行通信的模型中，n台处理 机执行m个任务的总处理时间为 97 第6章 多处理机 设m为n的倍数，由式(6.18)可得 l当k0时（采用集中分配策略），执行时间 最长（为rm），通信时间最短（为0）总的处理时 间为t1r