【文档说明】计算机体系结构第七章-多处理机课件.ppt，共(52)页，924.012 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-77480.html

以下为本文档部分文字说明：

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

成，每个处理机都能够独立执行自己的程序。互连网络处理机1处理机2处理机N存储器存储器存储器I/OI/O具有通过互连网络共享存储器和I/O的多处理机系统处理机1存储器I/O处理机2存储器I/O处理机N存储器I/O互连网每个处理机都拥有自己的存储器和I/O的多处理机系统2、多处理机与

并行处理机的区别结构灵活性：MIMD通用，SIMD专用；程序并行性：MIMD是作业级并行，并行性存在于指令外部，SIMD则是操作级并行，并行性存在于指令内部。并行任务派生：MIMD需要由专用语句显式指明是否派生并行任

务，而SIMD则不需要专门指令进程同步：MIMD各进程的同步需要采取特殊措施来保证，SIMD则由于受同一控制器控制，自然是同步的。资源分配和调度：MIMD任务调度要采用软件手段，SIMD只需用屏蔽来控制实际参加并行操作的处理单元数目。二、多处理机的硬件结构1、多处理机的两种形式(

1)紧耦合(2)松耦合(1)紧耦合紧耦合是通过共享主存实现处理机间的互相通信，处理机间的相互联系比较紧密。两种结构：带专用cache，不带专用cache适用场合：细粒度并行计算，同构形(同类型处理机)(2)松耦合不同处理机间通过通道互连或

消息传递方式相互通信，有较大的局部存储器，减少访主存冲突。适用场合：粗粒度并行计算，任务间信息流量小2、多处理机机间互连多处理机系统中，机间互连主要采用以下几种方式。互连形式特点存在问题适用场合总线形式总

线连接，采用分时多路转换技术，结构简单，造价低，可扩充失效敏感，效率低，总线冲突机数少环形互连处理机间点点相连成环形，令牌传递每个接口处有传输延迟高带宽，光纤通信交叉开关开关阵列连接，是总线分配机制开关阵列复杂，成本高机数少多端口存储器开关阵列连接，采用多端口存储器，每个端口负责一个处理机或

通道的访问存储器端口复杂，不易改变机数少开关枢纽结构在处理机内部或端口内部设置开关，与其它处理机构成分布式结构开关复杂，接口复杂机数多三、程序并行性多处理机并行性存在于指令内部，也存在于指令外部并行性开发途径：低层次并行：向量化高层次并行：算法、编译、语言、操作系统

1并行算法研究以算术表达式为例，把表达式看成是多个程序段相互作用的结果，而表达式中每一项都可看成是一个程序段的运行结果研究思路：对描述运算过程的树形结构进行变换研究目标：减少运算级数，即降低树高研究手段：用交换率、结合率、分配率进行变换研究方法：用交换率把相

同的运算结合在一起用结合率、分配率把操作数配对，尽可能并行结合各子树用树形流程图描述运算过程参数：处理机的数目：P运算的级数：Tp加速比：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效率：E

p=Sp/P=1.5/3=0.5例2：E2=a+b(c+def+g)+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程序并行性分析若程序段间有数据相关(写后读)，不能并行，只在特殊情况下可以交换串行PiA=B+DPjC=A*EP

iA=2*APjA=3*A任务间能否并行，除了算法外，很大程序上还取决于程序的结构。程序中的各类数据相关是限制程序并行的重要因素。若程序段间有数据反相关(读后写)，可以并行执行，但必须保证其写入共享主存时的先读后写次序，不能交换串行PiC=A+E

PjA=B+D若有数据输出相关(写后写)，可以并行执行，但同样需要保证写入共享主存的先后次序，不能交换串行PiA=B+DPjA=C+E若同时有数据相关与数据反相关，以交换数据为目的时，必须并行执行PiA=BPjB=A若没有任何相关或仅有源数据相关时，可以顺序

串行，交换串行和并行执行PiA=B+CPjD=B*E3并行程序设计语言并行算法要用并行程序来实现，使用并行程序设计语言加强并行性的识别，并明确表示并发进程。并行任务的派生：一个任务执行的同时，可派生出并行执行的其它任务并行任务的汇合：

并行执行的程序完成后，汇合在一起，执行后续工作M.E.Conway形式FORKm:派生并行任务，m为新进程开始标号JOINn:并发任务汇合，n为已派生出的并发进程个数工作过程：FORKm语句功能准备好新进程启动和执

行的必需信息将空闲的处理机分配给派生的新进程，若无空闲处理机，则排队等待继续在原处理机上执行FORKm语句的原进程JOIN有一个计数器，初值为0每执行一次JOINn，计数器加1，并与进行比较计数器值=n?相等，完成汇合，通过JOIN，计数器清0，执行后续语句不

等，还有进程未结束，已结束进程释放处理机。例：Z=E+A*B*C/D+F经并行编译后得到如下程序S1G=A*BS2H=C/DS3I=G*HS4J=E+FS5Z=I+JFORK2010G=A*B(S1)JO

IN2GOTO3020H=C/D(S2)JOIN230FORK40I=G*H(S3)JOIN240J=E+F(S4)JOIN250Z=I+J(S5)四、多处理机的性能系统性能：完成任务的总运行时间，其中各处理机的执行时间与通讯时间并行度：处理机数N任

务粒度：按并行性对任务分割的大小，用有效计算的执行间E与辅助开销时间C的比值来表示。任务粒度过小，即细粒度(Finegrain)，并行度高，执行时间少，但辅助开销时间大，系统效率低任务粒度过大，即粗粒度(

Coarsegrain)，并行度低，辅助开销时间小，但执行时间长，性能也不会高多处理机性能模型对一个应用程序：T：应用程序中任务的个数R：程序总的运行时间N：处理机数E：每个任务执行时间C：不同处理机通讯开销时间1、N=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<R2E/C>T/2

时，R1>R2结论：当E/C<T/2时，集中分配任使总处理时间最小；当E/C>T/2时，平均分配使总处理时间最小。2、N台处理机系统的基本模型将IK个任务分配给第K台处理机。推广前面的式子：)(2)max()(2)max(122

1NKKKNKKKKITCIEITICIER集中分配：R=T*E平均分配简单起见，设T是N的整数倍NCTCTNETR2222分析任务均分给N台处理机和任务集中在一台处理机的总处理时间差，有

：令其=0得，E/C=T/2结论：如果E/C>T/2，任务平均分配。如果E/C<T/2，任务集中分配。ETNCTCTNET2222总处理时间差并行系统的加速比是一个计算问题在一台处理机上的运行时间与在并行系统上的运行时间的比值，可近似如下：

21222）（）（NTCECENNCTCTNETETSpE/C>>T(N-1)/2，加速比可接近于N当任务数T及处理机数N均较少，E/C较大时，并行系统的加速比是随处理机机数N的增加而接近线性提高的当机数N增大到较大后，接近于2E/(CT)，只与E/C及任务数T有关，而与机数

N基本无关控制较少的额外开销C，以及合理选择任务粒度E/C>T/2，有利于并行效率的提高。常见是：一个任务与其它任务通信且通信内容相同时，只需向每台处理机通信一次即可：随着处理机数N增大，第1项减少，第2项增

大，存在一个最大的N使系统性能最佳。CNIERK}max{*当机数由N台增加到N+1台时，总运行时间的减少量为：令其>=0，有临界值CNNETCNNET)1()111(CETN3、额外开销与计算工作重叠假定额外工作被计算

工作完全覆盖，则总运行时间为：对双处理机，下图})(2),max(*max{1NKKKKITICIER当E/C>=T/2时，虚直线与实曲线没有交点或仅在I=T/2处由一个交点，执行时间完全覆盖了额外开销。当

E/C<T/2时，虚直线与实曲线有两个交点。交点的纵坐标为最短运行时间，横坐标为此时任务分配数I的最佳取值4、机间通信可以多路同时进行上述各处理机并行，其执行时间相互重叠，而通讯时间串行的情况，相当

于采用单总线或共享同一信道的互连结构假设每台处理机均有通信链路与其它处理机通信，则通信任务就可以与任务本身的执行重叠进行任何时刻，由于一台处理机只能与另一台处理机通信，即使链路数为N2，至多也只有N台处理机在并发通信

若采用平均分配策略：)(2)max()(2)max(1221NKKKNKKKKITNCIEITINCIER)11(22NNCTNETR五、多处理机操作系统主从型(Master-slaveSupervisor)各自独立型(Sep

arateSupervisor)浮动型(FloatingSupervisor)主从型管理程序只在主处理机运行硬件结构管理控制简单，对主处理机要求高适用于工作负荷固定，从处理机能力明显低的紧耦合、

异构型、非对称多处理机系统实现简单，经济方便，但不够灵活。各自独立型每个处理机有独立的管理程序在运行管理程序可再入，可靠性高，系统表格少，系统效率高，实现复杂，访存冲突解决和负载较困难适合于松耦合多处理机浮动型管理程序在多个处理机间浮动

管理程序可再入，实现复杂，负载平衡较好折衷方式灵活性适合于紧耦合型，同构型