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

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