计算机体系结构（金星）第七章 多处理机

1、第七章第七章 多处理机多处理机一、多处理机的特点一、多处理机的特点1 1、多处理机的定义、多处理机的定义具有两台以上的处理机，在操作系统控制下通过具有两台以上的处理机，在操作系统控制下通过共享的主存或输入输出子系统或高速通讯网络进共享的主存或输入输出子系统或高速通讯网络进行通讯。实现指令以上级（任务级、作业级）并行通讯。实现指令以上级（任务级、作业级）并行。行。按照按照FlynnFlynn分类法，多处理机系统属于分类法，多处理机系统属于MIMDMIMD计算计算机。机。多处理机系统由多个独立的处理机组成，每个处多处理机系统由多个独立的处理机组成，每个处理机都能够独立执行自己的程序。理机都能够独立

2、执行自己的程序。互连网络互连网络处理机处理机1处理机处理机2处理机处理机N存储器存储器存储器存储器存储器存储器I/OI/O具有通过互连网络共享存储器和具有通过互连网络共享存储器和I/O的多处理机系统的多处理机系统处理机处理机1存储器存储器I/O处理机处理机2存储器存储器I/O处理机处理机N存储器存储器I/O互连网互连网每个处理机都拥有自己的存储器和每个处理机都拥有自己的存储器和I/O的多处理机系统的多处理机系统2、多处理机与并行处理机的区别、多处理机与并行处理机的区别结构灵活性结构灵活性： MIMDMIMD通用，通用，SIMDSIMD专用；专用； 程序并行性程序并行性： MIMDMIMD是作业

3、级并行，是作业级并行，并行性存在并行性存在于指令外部，于指令外部， SIMDSIMD则是操作级并行，则是操作级并行，并行性存并行性存在于指令内部在于指令内部。 并行任务派生并行任务派生： MIMDMIMD需要由专用语句显式指明需要由专用语句显式指明是否派生并行任务，而是否派生并行任务，而SIMDSIMD则不需要专门指令则不需要专门指令 进程同步进程同步：MIMDMIMD各进程的同步需要采取特殊措各进程的同步需要采取特殊措施来保证，施来保证， SIMDSIMD则由于受同一控制器控制，自则由于受同一控制器控制，自然是同步的。然是同步的。 资源分配和调度资源分配和调度： MIMDMIMD任务调度要采

4、用软件手任务调度要采用软件手段，段， SIMDSIMD只需用屏蔽来控制实际参加并行操作只需用屏蔽来控制实际参加并行操作的处理单元数目。的处理单元数目。 二、多处理机的硬件结构二、多处理机的硬件结构1、多处理机的两种形式、多处理机的两种形式(1)紧耦合紧耦合(2)松耦合松耦合(1)紧耦合紧耦合 紧耦合是通过共享主存实现处理机间的互相紧耦合是通过共享主存实现处理机间的互相通信，处理机间的相互联系比较紧密。通信，处理机间的相互联系比较紧密。 两种结构：带专用两种结构：带专用cache，不带专用，不带专用cache 适用场合：细粒度并行计算，同构形适用场合：细粒度并行计算，同构形(同类型同类型处理机处

5、理机)(2)松耦合松耦合 不同处理机间通过不同处理机间通过通道互连通道互连或或消息传递消息传递方式方式相互通信，有较大的局部存储器，减少访主相互通信，有较大的局部存储器，减少访主存冲突。存冲突。 适用场合：粗粒度并行计算，任务间信息流适用场合：粗粒度并行计算，任务间信息流量小量小2、多处理机机间互连、多处理机机间互连 多处理机系统中，机间互连主要采用以多处理机系统中，机间互连主要采用以下几种方式。下几种方式。互连形式互连形式特点特点存在问题存在问题适用场合适用场合总线形式总线形式 总线连接，采用分时多总线连接，采用分时多路转换技术，结构简单，路转换技术，结构简单，造价低，可扩充造价低，可扩充失

6、效敏感，效失效敏感，效率低，总线冲率低，总线冲突突机数少机数少环形互连环形互连 处理机间点点相连成环处理机间点点相连成环形，令牌传递形，令牌传递每个接口处有每个接口处有传输延迟传输延迟高带宽，高带宽，光纤通信光纤通信交叉开关交叉开关 开关阵列连接，是总线开关阵列连接，是总线分配机制分配机制开关阵列复杂，开关阵列复杂，成本高成本高机数少机数少多端口存多端口存储器储器开关阵列连接，采用多开关阵列连接，采用多端口存储器，每个端口端口存储器，每个端口 负责一个处理机或通道负责一个处理机或通道的访问的访问存储器端口复存储器端口复杂，不易改变杂，不易改变机数少机数少开关枢纽开关枢纽结构结构在处理机内部或端

7、口内在处理机内部或端口内部设置开关，与其它处部设置开关，与其它处理机构成分布式结构理机构成分布式结构开关复杂，接开关复杂，接口复杂口复杂机数多机数多三、程序并行性三、程序并行性 多处理机并行性存在于指令内部，也存多处理机并行性存在于指令内部，也存在于指令外部在于指令外部 并行性开发途径：并行性开发途径：低层次并行：向量化低层次并行：向量化高层次并行：算法、编译、语言、操作系统高层次并行：算法、编译、语言、操作系统1并行算法研究并行算法研究 以算术表达式为例，把表达式看成是多个程序段以算术表达式为例，把表达式看成是多个程序段相互作用的结果，而表达式中每一项都可看成是相互作用的结果，而表达式中每一

8、项都可看成是一个程序段的运行结果一个程序段的运行结果 研究研究思路思路：对描述运算过程的树形结构进行变换：对描述运算过程的树形结构进行变换 研究研究目标目标：减少运算级数，即降低树高：减少运算级数，即降低树高 研究研究手段手段：用交换率、结合率、分配率进行变换：用交换率、结合率、分配率进行变换 研究研究方法方法： 用交换率把相同的运算结合在一起用交换率把相同的运算结合在一起 用结合率、分配率把操作数配对，尽可能并行用结合率、分配率把操作数配对，尽可能并行 结合各子树结合各子树用树形流程图描述运算过程用树形流程图描述运算过程参数：参数： 处理机的数目：处理机的数目：P 运算的级数：运算的级数：T

9、p 加速比：加速比：Sp=T1/ Tp 效率：效率：Ep=Sp/P串行运算串行运算用霍纳法得：用霍纳法得：E=a+x(b+x(c+x(d) 需要需要3个乘加循环，个乘加循环，6级运算级运算 适合于单处理机适合于单处理机例例1：E1=a+bx+cx2+dx3并行运算并行运算 E=a+bx+cx2+dx3 用用3台处理机，需要台处理机，需要4级运算级运算 处理机的数目：处理机的数目：P=3 运算的级数：运算的级数：Tp=4 加速比：加速比：Sp=T1/ Tp=6/4=1.5 效率：效率：Ep=Sp/P=1.5/3=0.5例例2 2 ：E2=a+b(c+def+g)+hE2=a+b(c+def+g)

10、+h 串行运算需要串行运算需要7级级利用交换律和结合律利用交换律和结合律 E2=(a+h)+b(c+g)+def) 需要需要5级运算级运算 P=2 Tp=5 Sp=7/5 Ep=0.7*利用分配律降低树高利用分配律降低树高 E2= (bc+bg) +(a+h) +bdef 需要需要4级运算级运算 P=3 Tp=4 Sp=7/4 Ep=7/12b2程序并行性分析程序并行性分析 若程序段间有数据相关若程序段间有数据相关(写后读写后读)，不能并行，不能并行，只在特殊情况下可以交换串行，只在特殊情况下可以交换串行Pi A=B+DPj C=A*EPi A=2*APj A= 3*A任务间能否并行，除了算法

11、外，很大程序任务间能否并行，除了算法外，很大程序上还取决于程序的结构。程序中的各类数据相上还取决于程序的结构。程序中的各类数据相关是限制程序并行的重要因素。关是限制程序并行的重要因素。 若程序段间有数据反相关若程序段间有数据反相关( (读后写读后写) )，可，可以并行执行，但必须保证其写入共享主以并行执行，但必须保证其写入共享主存时的先读后写次序，不能交换串行存时的先读后写次序，不能交换串行Pi C=A+EPj A=B+D 若有数据输出相关若有数据输出相关( (写后写写后写) )，可以并行，可以并行执行，但同样需要保证写入共享主存的执行，但同样需要保证写入共享主存的先后次序，不能交换串行先后次

12、序，不能交换串行Pi A=B+DPj A=C+E 若同时有数据相关与数据反相关，以交若同时有数据相关与数据反相关，以交换数据为目的时，必须并行执行换数据为目的时，必须并行执行Pi A=BPj B=A 若没有任何相关或仅有源数据相关时，若没有任何相关或仅有源数据相关时，可以顺序串行，交换串行和并行执行可以顺序串行，交换串行和并行执行Pi A=B+CPj D=B*E3并行程序设计语言并行程序设计语言 并行算法要用并行程序来实现，使用并行程序设计并行算法要用并行程序来实现，使用并行程序设计语言加强并行性的识别，并明确表示并发进程。语言加强并行性的识别，并明确表示并发进程。 并行任务的派生：一个任务执

13、行的同时，可派生出并行任务的派生：一个任务执行的同时，可派生出并行执行的其它任务并行执行的其它任务 并行任务的汇合：并行执行的程序完成后，汇合在并行任务的汇合：并行执行的程序完成后，汇合在一起，执行后续工作一起，执行后续工作 M.E.Conway形式形式 FORK m:派生并行任务，派生并行任务，m为新进程开始标号为新进程开始标号 JOIN n:并发任务汇合，并发任务汇合，n为已派生出的并发进程个为已派生出的并发进程个数数 工作过程：工作过程： FORK m 语句功能语句功能 准备好新进程启动和执行的必需信息准备好新进程启动和执行的必需信息 将空闲的处理机分配给派生的新进程，若无空将空闲的处理

14、机分配给派生的新进程，若无空闲处理机，则排队等待闲处理机，则排队等待 继续在原处理机上执行继续在原处理机上执行FORK m语句的原进程语句的原进程 JOIN有一个计数器，初值为有一个计数器，初值为0 每执行一次每执行一次JOIN n，计数器加，计数器加1，并与，并与进行比较进行比较 计数器值计数器值=n? 相等，完成汇合，通过相等，完成汇合，通过JOIN， 计数器清计数器清0，执行后续语句，执行后续语句 不等，还有进程未结束，已结束进程释不等，还有进程未结束，已结束进程释放处理机。放处理机。例：例：Z=E+A*B*C/D+F 经并行编译后得到如下程序经并行编译后得到如下程序 S1 G=A*B

15、S2 H=C/D S3 I=G*H S4 J=E+F S5 Z=I+J FORK 2010 G=A*B (S1) JOIN 2 GOTO 3020 H=C/D (S2) JOIN 230 FORK 40 I=G*H (S3) JOIN 240 J=E+F (S4) JOIN 250 Z=I+J (S5)四、多处理机的性能四、多处理机的性能系统性能系统性能：完成任务的总运行时间，其中各处理机：完成任务的总运行时间，其中各处理机的执行时间与通讯时间的执行时间与通讯时间并行度并行度：处理机数：处理机数N任务粒度任务粒度：按并行性对任务分割的大小，用有效计：按并行性对任务分割的大小，用有效计算的执行间

16、算的执行间E与辅助开销时间与辅助开销时间C的比值来表示。的比值来表示。任务粒度任务粒度过小，即细粒度过小，即细粒度(Finegrain)，并行度并行度高，高，执行时间少，但辅助开销时间大，系统效率低执行时间少，但辅助开销时间大，系统效率低任务粒度任务粒度过大，即粗粒度过大，即粗粒度(Coarsegrain)，并行度低并行度低，辅助开销时间小，但执行时间长，性能也不会高，辅助开销时间小，但执行时间长，性能也不会高多处理机性能模型多处理机性能模型 对一个应用程序：对一个应用程序： T：应用程序中任务的个数：应用程序中任务的个数 R：程序总的运行时间：程序总的运行时间 N：处理机数：处理机数 E：每

17、个任务执行时间：每个任务执行时间 C：不同处理机通讯开销时间：不同处理机通讯开销时间1 1、N=2N=2且通讯不能重叠且通讯不能重叠I个任务给一台处理机，个任务给一台处理机，T-I个任务给另一台处理机个任务给另一台处理机R=E*Max(T-I ，I)+C(T-I)I考虑两种特殊的分配方案：集中分配与平均分配考虑两种特殊的分配方案：集中分配与平均分配集中分配：集中分配：R1=E*T平均分配：平均分配：R2=ET/2+CT2/4令令R1-R2=0，可得，可得E/C=T/2E/C T/2时，时，R1 T/2时，时，R1R2结论：结论：当当E/CT/2时，平均分配使总处理时间最小。时，平均分配使总处理

18、时间最小。2 2、N N台处理机系统的基本模型台处理机系统的基本模型 将将IK个任务分配给第个任务分配给第K台处理机。推广前面台处理机。推广前面的式子：的式子：)(2)max()(2)max(1221NKKKNKKKKITCIEITICIER 集中分配：集中分配：R=T*E 平均分配平均分配 简单起见，设简单起见，设T是是N的整数倍的整数倍NCTCTNETR2222 分析任务均分给分析任务均分给N台处理机和任务集中在台处理机和任务集中在一台处理机的总处理时间差，有：一台处理机的总处理时间差，有： 令其令其=0得，得， E/C=T/2 结论：结论： 如果如果E/CT/2，任务平均分配。，任务平均

19、分配。 如果如果E/CT(N-1)/2，加速比可接近于，加速比可接近于N 当任务数当任务数T及处理机数及处理机数N均较少，均较少， E/C较大时，较大时，并行系统的加速比是随处理机机数并行系统的加速比是随处理机机数N的增加而接近的增加而接近线性提高的线性提高的当机数当机数N增大到较大后，接近于增大到较大后，接近于2 E/(CT)，只与，只与E/C及任务数及任务数T有关，而与机数有关，而与机数N基本无关基本无关控制较少的额外开销控制较少的额外开销C，以及合理选择任务粒度，以及合理选择任务粒度E/CT/2，有利于并行效率的提高。，有利于并行效率的提高。 常见是：一个任务与其它任务通信且通信内容常见

20、是：一个任务与其它任务通信且通信内容相同时，只需向每台处理机通信一次即可：相同时，只需向每台处理机通信一次即可： 随着处理机数随着处理机数N增大，第增大，第1项减少，第项减少，第2项增大，项增大，存在一个最大的存在一个最大的N使系统性能最佳。使系统性能最佳。CNIERKmax* 当机数由当机数由N台增加到台增加到N+1台时，总运行时间台时，总运行时间的减少量为：的减少量为： 令其令其=0，有，有 临界值临界值CNNETCNNET) 1()111(CETN 3、额外开销与计算工作重叠、额外开销与计算工作重叠 假定额外工作被计算工作完全覆盖，则总假定额外工作被计算工作完全覆盖，则总运行时间为：运行

21、时间为： 对双处理机，下图对双处理机，下图 )(2),max(*max1NKKKKITICIER 当当E/C=T/2时，虚直线与实曲线没有交点或仅在时，虚直线与实曲线没有交点或仅在I=T/2处由一个交点，执行时间完全覆盖了额外开处由一个交点，执行时间完全覆盖了额外开销。销。 当当E/CT/2时，虚直线与实曲线有两个交点。交时，虚直线与实曲线有两个交点。交点的纵坐标为最短运行时间，横坐标为此时任务点的纵坐标为最短运行时间，横坐标为此时任务分配数分配数I的最佳取值的最佳取值4、机间通信可以多路同时进行、机间通信可以多路同时进行 上述各处理机并行，其执行时间相互重叠，而上述各处理机并行，其执行时间相互重叠，而通讯时间串行的情况，相当于采用单总线或共通讯时间串行的情况，相当于采用单总线或共享同一信道的互连结构享同一信道的互连结构 假设每台处理机均有通信链路与其它处理机通假设每台处理机均有通信链路与其它处理机通信，则通信任务就可以与任务本身的执行重叠信，则通信任务就可以与任务本身的执行重叠进