《体系结构课件chapter73章节》由会员分享，可在线阅读，更多相关《体系结构课件chapter73章节（31页珍藏版）》请在金锄头文库上搜索。
1、1,7.3 多处理机的并行和性能,并行算法 程序并行性分析 并行语言与并行编译 多处理性能,2,1并行算法,并行算法的定义和分类 多处理机并行算法的研究思路,3,并行算法的定义,算法规定了求解某一特定问题时的有穷的运算处理步骤 并行算法是指可同时执行的多个进程的集合，各进程可相互作用、协调和并发操作,4,并行算法的分类,按运算基本对象 数值型（基于代数运算） 非数值型（基于关系运算） 按并行进程间的操作顺序不同 同步型 异步型 独立型 按计算任务的大小 细粒度 中粒度 粗粒度,5,多处理机并行算法的研究思路,将大的程序分解成可由足够多的并行处理的过程（进程、任务、程序段）,6,举例1,E1=a
2、+bx+cx2+dx3 利用Horner法：E1=a+x(b+x(c+x(d) 需3个乘加循环，6级运算 适合于单处理机 用树形流程图,7,举例1（续）,E1=a+bx+cx2+dx3 用3台处理机，需4级运算 级数（高度）Tp=4 处理机数P=3 加速比Sp=顺序运算级数/高度=6/4=3/2 效率Ep=Sp/P=1/2,8,说明,降低树高，增加并行性 用交换律、结合律、分配律来变换 先利用交换律把相同的运算集中起来，再用结合律把参加运算的操作数配对，尽可能并行运算，最后再把子树结合起来。,9,举例2,E2=a+b(c+def+g)+h 需7级运算,10,举例2（续）,利用交换律和结合律 E
3、2=(a+h)+b(c+g)+def) 需5级运算 P=2 Tp=5 Sp=7/5 Ep= Sp/p=0.7,11,举例2（续）,利用分配律降低树高。 E2=(a+h)+(bc+bg)+bdef 需4级运算 P=3 Tp=4 Sp=7/4 Ep=7/12,12,说明,表达式运算并行性的识别，除依靠算法 可以依靠编译程序 可以经过或不经过逆波兰后缀表达式产生并行指令,13,2. 程序的并行性分析,假定一个程序包含P1,P2,Pi,Pj,Pn等n个程序段，设Pi和Pj程序段都是一条语句，Pi在Pj之前执行。 数据相关 数据反相关 数据输出相关,14,数据相关,如果Pi的左部变量在Pj的右部变量集内
4、，且Pj必须取出Pi运算的结果来作为操作数，称Pj”数据相关”于Pi，例： Pi: A=B+D Pj: C=A*E 相当于流水中的“先写后读”相关。顺序执行的正确结果是： Pi A新=B原+D原 Pj C新=A新*E原=(B原+D原)* E原,15,数据相关（续）,Pi，Pj不能并行。 特殊，当Pi和Pj服从交换律时 Pi A=2*A Pj A=3*A 虽不能并行，但能交换串行。 得：6*A,16,数据反相关,如果Pj的左部变量在Pi的右部变量集内，且当Pi未取用其变量的值之前，是不允许被Pj所改变，称Pi”数据反相关”于Pj，例： Pi: C=A+E Pj: A=B+D 相当于流水中的“先读
5、后写”相关。顺序执行的正确结果是： Pi C新=A原+E原 Pj A新=B原+ D原 不能交换串行。,17,数据输出相关,如果Pi的左部变量也是Pj的左部变量，且Pj存入其算得的值必须在P存入之后，则称Pj”数据输出相关”于Pi，例： Pi: A=B+D Pj: A=C+E,18,总结,两个程序段之间如有先写后读的数据相关，不能并行，只在特殊情况下可以交换串行； 如有先读后写的数据反相关，可以并行执行，但必须保证其写入共享主存时的先读后写次序，不能交换串行； 如有写-写的数据输出相关，可以并行执行，但同样需保证其写入的先后次序，不能交换串行； 如同时有先写后读和先读后写两种相关，以交换数据为目
6、的时，则必须读写完全同步，不许顺序串行和交换串行； 如没有任何相关，或仅有源数据相同时，可以并行、顺序串行和交换串行。,19,3.并行语言和并行编译,是在普通顺序型程序设计语言基础上加以扩充，增加能明确表示并行进程的成分。 并行程序设计语言要求能使程序员灵活方便地在其程序中表示出各类并行性，同时应有高的效率，能在各种并行/向量计算机系统中有效地实现。 并行进程的特点：进程在时间上重叠执行。 派生：FORK; 汇合：JOIN 在不同的机器上有不同的表现形式。,20,多处理机与并行处理机的区别,并行处理机的每一条指令要求8个处理单元完全同步地对j=0,1,7的不同数组进行运算。在多处理机中，不需要
7、也不会完全同步。-操作级与任务级 多处理机中可用处理机数目对程序编写没有影响。,21,4.多处理机性能,引起峰值性能下降的原因是： 因处理机间通信而产生的延迟 一台处理机与其它处理机同步所需的开销 当没有足够多任务时，一台或多台处理机处于空闲状态 由于一台或多台处理机执行无用的工作 系统控制和操作调度所需开销,22,多处理机性能（续）,研究多处理机的目的： 提前5年得到速度高10倍的机器。 或用1/10的价格获得一台高性能的机器。 如果设计得好，在某些适合进行并行处理得应用领域，可以达到：提前10年得到速度高100倍的机器 或用1/100的价格获得一台高性能的机器。 并行性在很大程度上依赖于E
8、/C比值，其中： E代表程序执行时间 C代表通信开销。,23,多处理机性能（续）,通常：E/C比值小，并行性低。E/C比值大，并行性高 如果把作业分解成较大的块，就能得到较大的E/C值，但是所得到的并行性比最大可能的并行性要小得多。 E/C比值是衡量任务粒度(Granularity)大小的尺度 在粗粒度（Coarsegrain）并行情况下，E/C比值比较大，通信开销小,24,多处理机性能（续）,在细粒度（Finegrain）并行情况下，E/C比值比较小，通信开销大 细粒度并行性需要的处理机多，粗粒度并行性需要的处理机少。 细粒度并行性的基本原理是把一个程序尽可能地分解成能并行执行的小任务。在极
9、端情况下，一个小任务只完成一个操作。,25,7-4 多处理机的操作系统,多处理机操作系统的难度与特点 多处理机操作系统的类型 多处理机操作系统的的发展,26,多处理机操作系统的难度,处理机的分配和进程调度 进程间的同步 进程间的通信 存储系统的管理 文件系统的管理 系统重组,27,多处理机操作系统的特点,程序执行的并行性 分布性 机间通信与同步性 系统容错性,28,多处理机操作系统的类型,主从型(Master-slave Configuration) 管理程序只在主处理机上运行。 硬件结构、管理、控制简单，对主处理机要求高。 用于工作负荷固定、从处理机能力明显低的紧耦合、异构型、非对称多处理机
10、系统。 实现简单，经济，方便,29,多处理机操作系统的类型（续）,各自独立型（Separate Supervisor） 每个处理机有独立的管理程序在运行。 管理程序可再入，可靠性高，系统表格少，系统效率高；实现复杂、访存冲突解决和负载平衡较困难。 效率高； 实现复杂， 适合于松耦合多处理机,30,多处理机操作系统的类型（续）,浮动型(Floating Supervisor) 管理程序在多个处理机间浮动。 管理程序可再入，实现复杂，负载平衡较好。 折衷方式； 灵活性； 适合于紧耦合型，同构型；,31,小结,多处理机的定义及与并行处理机的区别 多处理机在硬件结构的分类； 多处理机的五种机间互连形式； 解决多Cache一致性的方法及特点； 多处理机的并行算法；,
