系统结构第九章.ppt

1、1,第九章 并行处理技术 第一节 概述,一、并行性基本概念,1.并行性,在计算、处理等过程中可同时进行的现象。 包括同时性和并发性。,分类： 计算并行性与算法设计、算法表示密切相关 搜索并行性改变存储结构实现并行检索 逻辑并行性对问题空间或状态空间进行搜索时存在的各种并行性，如AND并行性和OR并行性,2,(1)并行性粒度,G小则粒度细，通信量大。,(2)并行性等级划分,作业级、任务级、子程序级-MIMD 循环级、语句或指令级 -SIMD,粗粒度通常采用MIMD，细粒度则采用SIMD。,2.并行处理,是一种相对串行处理的信息处理方式，侧重并发性。,3,二、开发策略,1.方法,资源重复：侧重空间

2、方面，开发并行性的 同时性；,时间重叠：侧重时间方面，在处理时间上 相互重叠；,资源共享：侧重软件手段，开发并行性的并发性。,2.实现,粗粒度：MIMD方式，侧重软件手段。,细粒度：SIMD方式，侧重硬件手段辅以软件技术。,4,1.组成,通常由1个控制器(CU)，多个处理器(PE)，m个存储模块(M)及1个互连网络(IN)组成。,一、基本结构,第二节 并行处理机工作原理,根据存储模块组成方式可有分布式和集中式两种。,返回下页,5,2.分布式结构,存储模块由每个PE自带。,3.集中式结构,各个PE共享m个存储模块。,特点：,IN：是单向的，PEPE。,工作流程：,特点：,IN：是双向的，PEM。

3、,工作流程：,比较：,分布式每个PE有局部存储器，集中式共享存储器。,IN的作用不同：分布式PEPE，集中式PEM。,转上页,6,二、主要特点,1.利用资源重复方法，开发并行性中的同时性,所有PE操作相同，数据不同；,与流水线的方法不同点；（时间重叠）,侧重向量处理方面；,发展潜力无穷。,2.通过IN进行PE间、PE与M间连接，数据带宽较大,IN影响并行算法的实现方法；,IN的研究成为并行处理的重点问题之一。,3.并行算法与并行处理机结构密切相关,不同结构对应的并行算法的实现方法不同；,并行算法的研究是并行处理的又一个重点问题。,7,三、阵列处理机的常用并行算法,1.有限差分问题,应用：网格覆

4、盖场；图像平滑化算法。,结构：IN采用闭合螺旋线阵列。P189图,原理：,实现：每个PE存储和计算一组结点，多次迭代，直到误差小于规定。,效率：接近N倍（要扣除通讯开销）。,结点最大间距n-1， 。,8,2.矩阵加,原理：把矩阵中不同位置的分量放到不同的PE中运算，提高并行性。,实现：对C=A+B，A、B、C同一地址分量放在同一PE不同地址，用三条指令完成：LOAD、ADD、STORE,9,注意点：,如何把数据合理分配到PEi。 （存储单元分配算法）,每个PE存某列数据，其他数据通过播送得到。,如何分配任务给某个PEi； （同一地址+屏蔽向量）,10,3.累加求和,算法：折叠算法。,实现：,k

5、=0; while (2k TMIMD。,54,二、多处理机需解决问题,模块互连，并行性开发，任务分解，同 步，调度。,55,三、多处理机结构,1.紧耦合系统(TCS),特点：通过共享主存实现机间通讯。,互连网络：实现PEPEM、PEI/O通道、 PE中断信号间的连接。,56,系统属性：,同构/异构-PE类型相同/不同；,对称/非对称每个PE与部分/全部的I/O通道连接。,常见结构：同构对称式和异构非对称式多机系统。,限制：PE数量不能很多。为什么？,主存带宽、IN带宽、同步开销限制了PE的数量。,访存冲突解决方案：,采取多体交叉访问方式，增加PEM数量；,每个PE自带小容量局部存储器，存放核

6、心代码、OS表格等，减少PE访存次数；,每个PE自带一个Cache，减少PE访存次数。,57,2.松耦合系统(LCS),特点：通过消息传送系统实现机间通讯；,每个模块是一个独立的处理机，整个系统可看成是一个分布系统。,互连网络：MTS有总线、环形、多级网络等种类；,结构：有层次和非层次两种结构。,58,与计算机网络区别：,单一的系统物理地址空间；,每个PE的存储器均可被其它PE访问，通过CAS实现。,层次结构访存实现：,Cm内部局部开关slocal功能：确定PE地址的访问路线。,59,开关控制器KMap功能：传送地址访问请求 及结果。,构成：三个处理器和一个共享存储器。,Kbus：总线管理器，

7、仲裁对Map的请求。,Linc：管理KMap间的通讯。,Pmap：映象处理器，响应Kbus及Linc的请求。,60,Pmap设计可有8个并发请求，对等待返 回的请求，则切换到另一任务请求，以达到 最佳性能。,工作流程：分模块组内访存和模块组 间访存两种。,61,3.多处理机中Cache的一致性,软件方法： （回避方法）,共享信息只存放在主存，借助于编译程序完成；,判断数据何时可放在Cache中。,总线监听机制： （只适合于总线结构）,每个PE的Cache设置一个监听部件，一旦在Cache中的单元的听到写操作，作相应处理（修改或作废）。,目录表法： （非总线结构）,主存设置目录表数据块地址，指示

8、器、标志位，某PE写Cache时，通知指示器中的PE处理。,62,四、机间互连形式,1.总线形式 （时间分配） 最常见,PE、PEM、I/O通道均连在总线上，采用分时或多路转换技术实现数据传递，是最简单的连接方式。,总线仲裁算法：静态优先级算法、平等算法、动态优先级算法、先来先服务算法等。,对外设一般采用优先级算法；对PE采用均等算法。,实现方法：,集中式：由总线控制器控制；,分布式：中机构分散到各PE中。,提高总线效率方法：,改善传输介质和增加总线数量。,总线互连方式不适宜连接过多的处理机。,63,2.交叉开关形式 （空间分配）,是总线形式的极端，总线数=PE数+PEM数 +I/O通道数，是

9、一种全相联形式，控制、仲 裁、转换机构均在开关中。,改进：用一系列较小开关串联或并联，形 成多级交叉开关，减少其复杂性。,交叉开关方式不适宜连接过多的处理机。,3.多端口存储器形式,将控制、仲裁、转换机构移到存储器中。,每个端口与一个PE或I/O通道相连。,多端口存储器形式不适宜连接过多的处理机。,64,4.多级互连网络形式,是介于总线(N)与交叉开关(N2) 中间的一种(Nlog2N)。,对互连网络I与O数不一致时，可采用榕树形网络。,多级互连网络适宜于PE数较多的系统。,ab交叉开关,a入b出，输入基于a编码，输出基于b编码。,入端出端受阻后，重新申请，性能受建立时间限制；设置缓冲器性能有

10、所改善，适合于包交换网络。,anbn互连网络,交叉开关为ab开关，由n级构成。,比较：交叉开关时结点数为anbn，多级互连网络时结点数为abn2，明显降低了复杂性。,65,5.开关枢纽形式,将互连结构设置在PE或其接口内部，组成分布结构(松耦合)。,开关枢纽：由仲裁单元和开关单元组成，端口数不能多。,结构：由开关枢纽组成各种结构，如树形结构。,开关枢纽网络适宜于PE数较多的系统。,66,6.虫孔互连和寻径技术,原理：采用流水技术解决互连网络传输延迟问题。,传输延迟原因：,存储-转发结构使传输延迟与结点间距成正比。,延时分析：,存储-转发：T=(L/W)(D+1)；,67,虫孔寻径：LF时TWH

11、与结点间距D无关。,控制原理：,存储-转发：软件控制；,虫孔寻径：硬件控制，采用握手式的异 步流水方式，形成虚拟通道，使一个物理通 道为多个虚拟通道所共享。,拓扑结构：,存储-转发：寻求最短结点间距的互连网络；,虫孔寻径：传统的二维或三维结构，不采用多维结构。,68,第七节 多处理机中并行性开发,一、并行性开发,1.相关类型,数据相关RAW相关，数据反相关WAR相关， 数据输出相关WAW相关，控制相关条件语句。,2.并行性检测 -伯恩斯坦准则,Ii读单元集，Oi写单元集， P1、P2可并行条件：,I1O2=，并且I2O1=，并且O1O2=。,69,3.数据相关避免,主要解决反相关和输出相关，由

12、编译程序自动完成。,重命名方法：,S：A=B+C T：D=A+E U：A=A+D V：IF X0 THEN G=F+A,U：AA=A+D V：IF X0 THEN G=F+AA,标量扩充方法：,for i=1 to n do if A(i)0 then X=B(i); else X=C(i); D(i)=X+1;,for i=1 to n do b(i)=A(i)0; X(i)=B(i) when b(i); X(i)=C(i) when not b(i); D(i)=X(i)+1;,存在数据相关、反相关、输出相关、控制相关。,消除了数据反相关、输出相关。,消除反相关、输出相关,70,fora

13、ll和pipeling变换：改善循环体中相关,将循环体中语句重排序(无环路和有环路语句)，,forall：不同PE执行不同次循环； pipeling：不同PE执行各次循环中同一语句块。,71,二、并行程序设计语言,1.开发方式,语言形成方式：扩充语言功能、重新设计并行语言,对语言的要求：灵活性、效率,程序设计方式：显式、隐式,2.扩展语言中三种并行结构,FORK-JOIN：不同机器有不同形式，效果相同,FORK A： 派生一个进程，当前进程继续，,FORK A,J： FORK A功能外，地址J计数器+1，,FORK A,J,N：FORK A功能外，地址J计数器值为N；,JOIN J： 地址J处

14、计数器减1，当计数器值为零时，启动J+1处进程，否则，结束该进程，释放PE。,72,例：3个PE并行处理88矩阵乘法。,DO 10 J=0，6 10 FORK 20，60 /*派生处理第06列进程*/ J=7 /*当前进程处理第7列*/ 20 DO 40 I=0，7 /*处理07行*/ C(I,J)=0 DO 30 K=0,7 /*处理C(I,J)*/ 30 C(I,J)=C(I,J)+A(I,K)*B(K,J) 40 CONTINUE JOIN 60 60 ,73,块结构语言：,把可并行执行的进程用cobegin-coend括起来处理,最后一条语句执行完成后，方可执行后续语句。,该语句可嵌套

15、；可使用共享变量，但不允许修改。,74,parfor语句：,parfor语句原语：,75,例：C(n1)=A(nn)B(n1),parfor i=1, p for j=(i-1)*s+1, s*i /*s=n/p*/ c(j)=0 for k=1, n c(j)=c(j)+A(j,k)*B(j) ,P1:1s;P2:s+12s;Pp:n-sn,并行程序设计语言必须处理好因共享变量导致的进程间通讯与同步问题。,76,三、并行算法,分为同步并行算法、异步并行算法、宏流水线算法。,1.同步并行算法,进程某些段要等待其它进程以保持同步的并行算法。,同步并行算法只适用于进程速度波动较小的情况。,2.异步

16、并行算法,进程间的通信通过全局变量或共享数据进行的，不需要等待任何输入触发。,有简单异步迭代算法和自适应算法两种。,异步并行算法通过进程交替进行，提高处理速度。,3.宏流水并行算法,计算可分为几部分的输出是另一部分输入的算法。,77,第八节 多处理机操作系统,一、操作系统类型,1.主从型,管理程序只在主处理机上运行。,硬件结构、管理、控制简单，对主处理机要求高。,适用于工作负荷固定、从处理机能力明显低的紧耦合、异构型、非对称多处理机系统。,78,2.各自独立型,每个处理机有独立的管理程序在运行。,管理程序可再入，可靠性高，系统表格 少，系统效率高；实现复杂、访存冲突解 决和负载平衡较困难。,适

17、用于松耦合的多处理机系统。,3.浮动型,管理程序在多个处理机间浮动。,管理程序可再入，实现复杂，负载平衡较好。,适用于紧耦合的对称多处理机系统。,79,二、多处理机调度策略,1.资源分配,同构型：按资源分类，每类资源均有资源池；,异构型：按功能专用化及功能分布原则调度。,2.进程控制,按运行、等待、挂起、就绪四种状态进行调度。,3.多处理机调度,算法：静态、动态。,指标：最少完成时间、最少PE数、最小平均流时间、PE最大利用率及最小空闲时间。,80,三、进程通讯,分共享变量（同步与互斥）和消息传递两 种方法。,四、系统死锁,1.造成死锁的条件,进程独占某些资源；,死循环。,2.死锁的处理,使用协议，