系统结构第九章.ppt

《系统结构第九章.ppt》由会员分享，可在线阅读，更多相关《系统结构第九章.ppt（82页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第九章第九章 并行处理技术并行处理技术第一节第一节 概述概述一、并行性基本概念一、并行性基本概念1.并行性并行性 在计算、处理等过程中可同时进行的现象。在计算、处理等过程中可同时进行的现象。包括同时性和并发性。包括同时性和并发性。分类：分类：计算并行性计算并行性与算法设计、算法表示密切相关与算法设计、算法表示密切相关 搜索并行性搜索并行性改变存储结构实现并行检索改变存储结构实现并行检索 逻辑并行性逻辑并行性对问题空间或状态空间进行搜索时对问题空间或状态空间进行搜索时存在的各种并行性，如存在的各种并行性，如ANDAND并行性和并行性和OROR并行性并行性1 (1)(1)并行性粒度并行性粒度 G小

2、则粒度细，通信量大。小则粒度细，通信量大。(2)并行性等级划分并行性等级划分 作业级、任务级、子程序级作业级、任务级、子程序级-MIMDMIMD 循环级、语句或指令级循环级、语句或指令级 -SIMDSIMD 粗粗粒度通常采用粒度通常采用MIMD，细粒度则采用细粒度则采用SIMD。2.2.并行处理并行处理 是是一种相对串行处理的信息处理方式，侧一种相对串行处理的信息处理方式，侧重并发性。重并发性。2二、开发策略二、开发策略1.1.方法方法 资源重复：资源重复：侧重空间方面，开发并行性的侧重空间方面，开发并行性的 同时性；同时性；时间重叠：时间重叠：侧重时间方面，在处理时间上侧重时间方面，在处理时

3、间上 相互重叠；相互重叠；资源共享：资源共享：侧重软件手段，开发并行性的并发性。侧重软件手段，开发并行性的并发性。2.2.实现实现 粗粒度：粗粒度：MIMDMIMD方式，侧重软件手段。方式，侧重软件手段。细粒度：细粒度：SIMDSIMD方式，侧重硬件手段辅以软件技术。方式，侧重硬件手段辅以软件技术。31.1.组成组成 通常由通常由1 1个控制器个控制器(CU)CU)，多个处理器多个处理器(PE)PE)，m m个存储模块个存储模块(M)M)及及1 1个互连网络个互连网络(IN)IN)组成。组成。一、基本结构一、基本结构第二节第二节 并行处理机工作原理并行处理机工作原理 根据存储模块组成方式可有分

4、布式和集中式两种。根据存储模块组成方式可有分布式和集中式两种。IN分布式集中式P0M0Pn-1Mn-1PE0PEn-1CUINCUM0M1Mm-1PE0PE1PEn-1返回下页42.2.分布式结构分布式结构存储模块由每个存储模块由每个PEPE自带。自带。3.3.集中式结构集中式结构各个各个PEPE共享共享m m个存储模块。个存储模块。特点：特点：ININ：是单向的，是单向的，PEPEPEPE。工作流程：工作流程：特点：特点：ININ：是双向的，是双向的，PEMPEM。工作流程：工作流程：比较：比较：分布式每个分布式每个PEPE有局部存储器，集中式共享存储器。有局部存储器，集中式共享存储器。IN

5、IN的作用不同：分布式的作用不同：分布式PEPEPEPE，集中式集中式PEMPEM。转上页5二、主要特点二、主要特点1.1.利用资源重复方法，开发并行性中的同时性利用资源重复方法，开发并行性中的同时性 所有所有PE操作相同，数据不同；操作相同，数据不同；与流水线的方法不同点；与流水线的方法不同点；（时间重叠）（时间重叠）侧重向量处理方面；侧重向量处理方面；发展潜力无穷。发展潜力无穷。2.2.通过通过ININ进行进行PEPE间、间、PEPE与与M M间连接，数据带宽较大间连接，数据带宽较大 IN影响并行算法的实现方法；影响并行算法的实现方法；IN的研究成为并行处理的重点问题之一。的研究成为并行处

6、理的重点问题之一。3.3.并行算法与并行处理机结构密切相关并行算法与并行处理机结构密切相关 不同结构对应的不同结构对应的并行算法的实现方法不同；并行算法的实现方法不同；并行算法的研究是并行处理的又一个重点问题。并行算法的研究是并行处理的又一个重点问题。6三、阵列处理机的常用并行算法三、阵列处理机的常用并行算法1.1.有限差分问题有限差分问题 应用：应用：网格覆盖场；图像平滑化算法。网格覆盖场；图像平滑化算法。结构：结构：IN采用闭合螺旋线阵列。采用闭合螺旋线阵列。P189图图 原理：原理：实现：实现：每个每个PE存储和计算一组结点，多次迭代，直存储和计算一组结点，多次迭代，直到误差小于规定。到

7、误差小于规定。效率：效率：接近接近N倍（要扣除通讯开销）。倍（要扣除通讯开销）。结点最大间距结点最大间距n-1，。72.2.矩阵加矩阵加 原理：原理：把矩阵中不同位置的分量放到不同把矩阵中不同位置的分量放到不同的的PE中运算，提高并行性。中运算，提高并行性。实现：实现：对对C=A+B，A、B、C同一地址分量同一地址分量放在同一放在同一PE不同地址，用三条指令完成：不同地址，用三条指令完成：LOAD、ADD、STOREC(0,0)A(0,0)B(0,0)+1+2C(0,1)A(0,1)B(0,1)C(7,7)A(7,7)B(7,7)8 注意点：注意点：如何把数据合理分配到如何把数据合理分配到PE

8、PEi i。（存储单元分配算法）存储单元分配算法）当只有当只有8 8个个PEPE处理时，处理时，对对 每个每个PEPE存某列数据，其他数据通过播送得到。存某列数据，其他数据通过播送得到。如何分配任务给某个如何分配任务给某个PEPEi i；（同一地址同一地址+屏蔽向量）屏蔽向量）93.3.累加求和累加求和 算法：算法：折叠算法。折叠算法。实现：实现：k=0;k=0;while(2k T TMIMDMIMD。53二、多处理机需解决问题二、多处理机需解决问题 模块互连，并行性开发，任务分解，同模块互连，并行性开发，任务分解，同步，调度。步，调度。54三、多处理机结构三、多处理机结构1.1.紧耦合系统

9、紧耦合系统(TCS)TCS)特点：特点：通过共享主存实现机间通讯。通过共享主存实现机间通讯。PPINPpPIOIND1PMpPMINM1I/O 通道PM-局存CM-高速缓存P-处理器D-外部设备P1PM1CM1CMPDDMM 互连网络：互连网络：实现实现PEPEMPEPEM、PEI/OPEI/O通道、通道、PEPE中断信号间的连接。中断信号间的连接。55 系统属性：系统属性：同构同构/异构异构-PEPE类型相同类型相同/不同；不同；对称对称/非对称非对称每个每个PEPE与与部分部分/全部的全部的I/OI/O通道连接。通道连接。常见结构：常见结构：同构对称式同构对称式和和异构非对称式异构非对称式

10、多机系统。多机系统。限制：限制：PEPE数量不能很多。数量不能很多。为什么？为什么？主存带宽、主存带宽、ININ带宽、同步开销限制了带宽、同步开销限制了PEPE的数量。的数量。访存冲突解决方案：访存冲突解决方案：采取多体交叉访问方式，增加采取多体交叉访问方式，增加PEMPEM数量；数量；每个每个PEPE自带小容量局部存储器，存放核心代码、自带小容量局部存储器，存放核心代码、OSOS表格等，减少表格等，减少PEPE访存次数；访存次数；每个每个PEPE自带一个自带一个CacheCache，减少减少PEPE访存次数。访存次数。562.2.松耦合系统松耦合系统(LCS)LCS)消息传送系统 MTSPM

11、I/ONI模块1NI-结点机接口 计算机模块(结点机)PMI/ONI模块N 特点：特点：通过消息传送系统实现机间通讯；通过消息传送系统实现机间通讯；每个模块是一个独立的处理机，整个系统可每个模块是一个独立的处理机，整个系统可看成是一个分布系统。看成是一个分布系统。互连网络：互连网络：MTSMTS有总线、环形、多级网络等种类；有总线、环形、多级网络等种类；结构：结构：有层次和非层次两种结构。有层次和非层次两种结构。57 与计算机网络区别：与计算机网络区别：单一的系统物理地址空间；单一的系统物理地址空间；每个每个PEPE的存储器均可被其它的存储器均可被其它PEPE访问，通过访问，通过CASCAS实

12、现。实现。层次结构访存实现：层次结构访存实现：CmCm内部局部开关内部局部开关slocalslocal功能：功能：确定确定PEPE地址的访问地址的访问路线。路线。10X.PSW415Slocal映象表16位PE地址661212存储器18LSI总线局部全局slocalPEMap总线58 开关控制器开关控制器K KMapMap功能：功能：传送地址访问请求传送地址访问请求及结果。及结果。LincKbusPmapMap总线返回队列服务队列端口0送队列端口1送队列运行队列输出队列Intercluster总线0Intercluster总线1构成：构成：三个处理器三个处理器和一个共享存储器。和一个共享存储器

13、。KbusKbus：总线管理总线管理器，仲裁对器，仲裁对MapMap的请的请求。求。LincLinc：管理管理K KMapMap间间的通讯。的通讯。PmapPmap：映象处理器，响应映象处理器，响应KbusKbus及及LincLinc的请求。的请求。59 PmapPmap设计可有设计可有8 8个并发请求，对等待返个并发请求，对等待返回的请求，则切换到另一任务请求，以达到回的请求，则切换到另一任务请求，以达到最佳性能。最佳性能。工作流程：工作流程：分模块组内访存和模块组分模块组内访存和模块组间访存两种。间访存两种。603.3.多处理机中多处理机中CacheCache的一致性的一致性 软件方法软件

14、方法：（回避方法）（回避方法）共享信息只存放在主存，借助于编译程序完成；共享信息只存放在主存，借助于编译程序完成；判断数据何时可放在判断数据何时可放在CacheCache中。中。总线监听机制总线监听机制：（只适合于总线结构）（只适合于总线结构）每个每个PEPE的的CacheCache设置一个监听部件，一旦在设置一个监听部件，一旦在CacheCache中的单元的听到写操作，作相应处理（修改或作废）。中的单元的听到写操作，作相应处理（修改或作废）。目录表法目录表法：（非总线结构）（非总线结构）主存设置目录表数据块地址，指示器、标志位主存设置目录表数据块地址，指示器、标志位，某，某PEPE写写Cac

15、heCache时，通知指示器中的时，通知指示器中的PEPE处理。处理。61四、机间互连形式四、机间互连形式1.1.总线形式总线形式 （时间分配）（时间分配）最常见最常见 PEPE、PEMPEM、I/OI/O通道均连在总线上，采用分时或多路通道均连在总线上，采用分时或多路转换技术实现数据传递，是最简单的连接方式。转换技术实现数据传递，是最简单的连接方式。总线仲裁算法：总线仲裁算法：静态优先级算法、平等算法、动态静态优先级算法、平等算法、动态优先级算法、先来先服务算法等。优先级算法、先来先服务算法等。对外设一般采用优先级算法；对对外设一般采用优先级算法；对PEPE采用均等算法。采用均等算法。实现方

16、法：实现方法：集中式：由总线控制器控制；集中式：由总线控制器控制；分布式：中机构分散到各分布式：中机构分散到各PEPE中。中。提高总线效率方法：提高总线效率方法：改善传输介质和增加总线数量。改善传输介质和增加总线数量。总线互连方式不适宜连接过多的处理机。总线互连方式不适宜连接过多的处理机。622.2.交叉开关形式交叉开关形式 （空间分配）（空间分配）是总线形式的极端，总线数是总线形式的极端，总线数=PEPE数数+PEMPEM数数+I/OI/O通道数，是一种全相联形式，控制、仲通道数，是一种全相联形式，控制、仲裁、转换机构均在开关中。裁、转换机构均在开关中。改进：改进：用一系列较小开关串联或并联

17、，形用一系列较小开关串联或并联，形成多级交叉开关，减少其复杂性。成多级交叉开关，减少其复杂性。交叉开关方式不适宜连接过多的处理机。交叉开关方式不适宜连接过多的处理机。3.3.多端口存储器形式多端口存储器形式 将控制、仲裁、转换机构移到存储器中。将控制、仲裁、转换机构移到存储器中。每个端口与一个每个端口与一个PEPE或或I/OI/O通道相连。通道相连。多端口存储器形式不适宜连接过多的处理机。多端口存储器形式不适宜连接过多的处理机。634.4.多级互连网络形式多级互连网络形式 是介于总线是介于总线(N)N)与交叉开关与交叉开关(N N2 2)中间的一种中间的一种(NlogNlog2 2N)N)。对

18、互连网络对互连网络I I与与O O数不一致时，可采用榕树形网络。数不一致时，可采用榕树形网络。多级互连网络适宜于多级互连网络适宜于PEPE数较多的系统。数较多的系统。abab交叉开关交叉开关 a a入入b b出，输入基于出，输入基于a a编码，输出基于编码，输出基于b b编码。编码。入端入端出端受阻后，重新申请，性能受建立时间出端受阻后，重新申请，性能受建立时间限制；设置缓冲器性能有所改善，适合于包交换网络。限制；设置缓冲器性能有所改善，适合于包交换网络。a an nb bn n互连网络互连网络 交叉开关为交叉开关为abab开关，由开关，由n n级构成。级构成。比较：比较：交叉开关时结点数为交

19、叉开关时结点数为a an nb bn n，多级互连网络时多级互连网络时结点数为结点数为abnabn2 2，明显降低了复杂性。明显降低了复杂性。645.5.开关枢纽形式开关枢纽形式 将互连结构设置在将互连结构设置在PEPE或其接口内部，组成或其接口内部，组成分布结构分布结构(松耦合松耦合)。开关枢纽：开关枢纽：由仲裁单元和开关单元组成，端由仲裁单元和开关单元组成，端口数不能多。口数不能多。结构：结构：由开关枢纽组成各种结构，如树形结构。由开关枢纽组成各种结构，如树形结构。开关枢纽网络适宜于开关枢纽网络适宜于PEPE数较多的系统。数较多的系统。656.6.虫孔互连和寻径技术虫孔互连和寻径技术 原理

20、：原理：采用流水技术解决互连网络传输延迟问题。采用流水技术解决互连网络传输延迟问题。传输延迟原因：传输延迟原因：存储存储-转发结构使传输延迟与结点间距成正比。转发结构使传输延迟与结点间距成正比。延时分析：延时分析：存储存储-转发：转发：T=(L/W)(D+1)T=(L/W)(D+1)；TTWH=+DLWN1N2N3N4TWHL/WDFWF66 虫孔寻径虫孔寻径：LFLF时时T TWHWH与结点间距与结点间距D D无关。无关。控制原理：控制原理：存储存储-转发转发：软件控制；软件控制；虫孔寻径虫孔寻径：硬件控制，采用握手式的异硬件控制，采用握手式的异步流水方式，形成虚拟通道，使一个物理通步流水方

21、式，形成虚拟通道，使一个物理通道为多个虚拟通道所共享。道为多个虚拟通道所共享。拓扑结构：拓扑结构：存储存储-转发转发：寻求最短结点间距的互连网络；寻求最短结点间距的互连网络；虫孔寻径虫孔寻径：传统的二维或三维结构，不采用多维传统的二维或三维结构，不采用多维结构。结构。67第七节第七节 多处理机中并行性开发多处理机中并行性开发一、并行性开发一、并行性开发1.1.相关类型相关类型 数据相关数据相关RAWRAW相关，相关，数据反相关数据反相关WARWAR相关，相关，数据输出相关数据输出相关WAWWAW相关，相关，控制相关控制相关条件语句。条件语句。2.2.并行性检测并行性检测 -伯恩斯坦准则伯恩斯坦

22、准则 I Ii i读单元集，读单元集，O Oi i写单元集，写单元集，P P1 1、P P2 2可并行条件：可并行条件：I I1 1OO2 2=，并且并且I I2 2OO1 1=，并且并且O O1 1OO2 2=。683.3.数据相关避免数据相关避免 主要解决反相关和输出相关，由编译程序自动完成。主要解决反相关和输出相关，由编译程序自动完成。重命名方法：重命名方法：S S：A=B+CA=B+C T T：D=A+ED=A+E U U：A=A+DA=A+D V V：IF X0 THEN G=F+AIF X0 THEN G=F+AUU：AA=A+DAA=A+DVV：IF X0 THEN G=F+AA

23、IF X0 THEN G=F+AA 标量扩充方法：标量扩充方法：for i=1 to n dofor i=1 to n do if A(i)0 then X=B(i);if A(i)0 then X=B(i);else X=C(i);else X=C(i);D(i)=X+1;D(i)=X+1;for i=1 to n dofor i=1 to n do b(i)=A(i)0;b(i)=A(i)nFORK A2,A6循环体SJOIN A1A2A3A4A5A674例：例：C(n1)=A(nn)B(n1)C(n1)=A(nn)B(n1)parforparfor i=1,p i=1,p for j=(

24、i-1)*s+1,s*i for j=(i-1)*s+1,s*i /*s=n/p*/*s=n/p*/c(j)=0 c(j)=0 for k=1,n for k=1,n c(j)=c(j)+A(j,k)*B(j)c(j)=c(j)+A(j,k)*B(j)P P1 1:1s;P:1s;P2 2:s+12s;P:s+12s;Pp p:n-sn:n-sn 并行程序设计语言必须处理好因共享变量导致的进并行程序设计语言必须处理好因共享变量导致的进程间通讯与同步问题。程间通讯与同步问题。75三、并行算法三、并行算法 分为同步并行算法、异步并行算法、宏流水线算法。分为同步并行算法、异步并行算法、宏流水线算法。

25、1.1.同步并行算法同步并行算法 进程某些段要等待其它进程以保持同步的并行算法。进程某些段要等待其它进程以保持同步的并行算法。同步并行算法只适用于进程速度波动较小的情况。同步并行算法只适用于进程速度波动较小的情况。2.2.异步并行算法异步并行算法 进程间的通信通过全局变量或共享数据进行的，不进程间的通信通过全局变量或共享数据进行的，不需要等待任何输入触发。需要等待任何输入触发。有简单异步迭代算法和自适应算法两种。有简单异步迭代算法和自适应算法两种。异步并行算法通过进程交替进行，提高处理速度。异步并行算法通过进程交替进行，提高处理速度。3.3.宏流水并行算法宏流水并行算法 计算可分为几部分的输出

26、是另一部分输入的算法。计算可分为几部分的输出是另一部分输入的算法。76第八节第八节 多处理机操作系统多处理机操作系统一、操作系统类型一、操作系统类型1.1.主从型主从型 管理程序只在主处理机上运行。管理程序只在主处理机上运行。硬件结构、管理、控制简单，对主处理机要求高。硬件结构、管理、控制简单，对主处理机要求高。适用于工作负荷固定、从处理机能力明显低的紧耦适用于工作负荷固定、从处理机能力明显低的紧耦合、异构型、非对称多处理机系统。合、异构型、非对称多处理机系统。772.2.各自独立型各自独立型 每个处理机有独立的管理程序在运行。每个处理机有独立的管理程序在运行。管理程序可再入，可靠性高，系统表

27、格管理程序可再入，可靠性高，系统表格少，系统效率高；实现复杂、访存冲突解少，系统效率高；实现复杂、访存冲突解决和负载平衡较困难。决和负载平衡较困难。适用于松耦合的多处理机系统。适用于松耦合的多处理机系统。3.3.浮动型浮动型 管理程序在多个处理机间浮动。管理程序在多个处理机间浮动。管理程序可再入，实现复杂，负载平衡较好。管理程序可再入，实现复杂，负载平衡较好。适用于紧耦合的对称多处理机系统。适用于紧耦合的对称多处理机系统。78二、多处理机调度策略二、多处理机调度策略1.1.资源分配资源分配 同构型：按资源分类，每类资源均有资源池；同构型：按资源分类，每类资源均有资源池；异构型：按功能专用化及功

28、能分布原则调度。异构型：按功能专用化及功能分布原则调度。2.2.进程控制进程控制 按运行、等待、挂起、就绪四种状态进行调度。按运行、等待、挂起、就绪四种状态进行调度。3.3.多处理机调度多处理机调度 算法：算法：静态、动态。静态、动态。指标：指标：最少完成时间、最少最少完成时间、最少PEPE数、最小平均流时间、数、最小平均流时间、PEPE最大利用率及最小空闲时间。最大利用率及最小空闲时间。79三、进程通讯三、进程通讯 分共享变量（同步与互斥）和消息传递两分共享变量（同步与互斥）和消息传递两种方法。种方法。四、系统死锁四、系统死锁1.1.造成死锁的条件造成死锁的条件 进程独占某些资源；进程独占某

29、些资源；死循环。死循环。2.2.死锁的处理死锁的处理 使用协议，不进入死锁；允许进入，提供解除方法。使用协议，不进入死锁；允许进入，提供解除方法。进程进一步申请资源被拒绝，且不释放已占资源；进程进一步申请资源被拒绝，且不释放已占资源；803.3.死锁的预防死锁的预防 被挂起的进程强迫其释放已占用资源；被挂起的进程强迫其释放已占用资源；进程必须一次性提出资源申请，未满足要求前，不进程必须一次性提出资源申请，未满足要求前，不占用任何资源；占用任何资源；4.4.死锁的避免死锁的避免 利用已有的资源使用信息来控制资源的分配，不致利用已有的资源使用信息来控制资源的分配，不致进入危险区。进入危险区。BankerBanker算法和有向图环路问题算法和有向图环路问题 资源种类按一定次序排序，进程按此次序申请资源；资源种类按一定次序排序，进程按此次序申请资源；将所有资源信息构成资源使用表，有申请时由操作将所有资源信息构成资源使用表，有申请时由操作系统核算，是否会造成死锁。系统核算，是否会造成死锁。815.5.死锁的检测死锁的检测 定期检查，方法与思索避免方法类似。定期检查，方法与思索避免方法类似。6.6.死锁的解除死锁的解除 选择一个牺牲者，或重新某一进程。选择一个牺牲者，或重新某一进程。82