第五章 多处理机系统.ppt
《第五章 多处理机系统.ppt》由会员分享,可在线阅读,更多相关《第五章 多处理机系统.ppt(113页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、多处理机系统多处理机系统12/20/20221多处理机系统的定义 P.H.Enslow对多处理机作了下列定义:*包含两个或两个以上功能大致相同的处理器;*所有处理器共享一个公共内存;*所有处理器共享I/O通道、控制器和外围设备;*整个系统由统一的操作系统控制,在处理器和程序之间实现作业、任务、程序段、数组和数组元素等各级的全面并行。12/20/20222 多处理机的优点 很高的性能价格比:单处理机的性能价格比随其规模的增大而下降 很高的可靠性:冗余度大、可维护性、可用性 很高的处理速度:多个处理器并行运算 很好的模块性:大量重复设置,结构灵活性、可扩充性、可重构性 12/20/20223特性要
2、求-进程恢复能力 多处理机系统使用的处理机结构应能反映进程和处理机是两个不同的实体。如果某处理机发生故障,另一台处理机应能检索到被中断的进程状态,使被中断的进程能继续运行。没有这个功能,系统的可靠性大大下降。大多数处理机把当前正在运行进程状态保存在内部寄存器中,如何使其他处理器在必要时能访问到进程状态,是恢复进程的关键之一。在不太损失速度的前提下,把通用寄存器与处理机本身分开是可能的,在系统内设置所有处理机共享的寄存器堆可以实现上述功能。12/20/20224特性要求-有效的现场切换 现场切换操作是把当前进程状态保存起来,然后通过恢复新进程的状态切换到被选中的准备好运行的进程。切换操作可以在指
3、令系统中设置一条专门指令来完成。该指令执行的结果是将当前进程状态或现场内容保存起来,然后到主存储器的缓冲区取另一个进程状态,该缓冲区称为交换包。12/20/20225特性要求-大的物理地址空间和虚拟地址空间 多处理机系统内的处理机必须能支持大的物理地址空间(即直接寻址空间要大),这是因为进程需要访问大量数据。例如,Pentium地址线32根,直接寻址空间可达4GB,能满足需求。有了大的物理地址空间,还需要大的虚拟地址空间,把虚拟地址空间分段,便于模块共享以及地址界限的检查。12/20/20226特性要求-高效率的同步原语 处理机设计时必须能提供作为同步原语基础的某种不可再分的操作。这些同步原语
4、需要有互斥机构支持。当两个以上的进程并发地运行或相互交换数据时,需要互斥。互斥机构包含某种形式的读修改写存储周期和排队。信号灯(semaphore)是互斥机构的一种。每个信号灯有其队列,队列中的项是被挂起来的进程。信号灯操作是不可分操作,利用读修改写存储周期,测试和修改信号灯。队列操作也应是不可分的。12/20/20227特性要求-处理机之间有高效率的通信机构 通信机构可用硬件实现。它有助于实现处理机之间的同步。在非对称多处理机系统中,不同的处理机之间经常需要交换服务请求,硬件通信机构作用更加明显。在处理机发生故障时,通过该机构发信号给其他正在运行的处理机,并启动诊断过程或纠错过程。在紧密耦合
5、的多处理机系统内有共享存储器,采用软件方法实现多处理机之间的通信是可能的。每个处理机必须周期地检查位于共享存储器内的“信箱”(缓冲区),检查是否有信息给它。12/20/20228特性要求-指令系统 处理机的指令系统应能支持实现具有过程级并发功能的高级语言,为有效的处理数据结构提供充分条件。指令系统内应有过程连接、循环结构、参数处理、多维下标计算和地址界限检查等指令。还需包括产生和结束程序内部并行执行通路的指令。设置特权指令。12/20/20229Flynn分类法Micheal Flynn(1972)提出指令流、数据流和多倍性概念,把不同的计算机分为四大类(下图):SISD(Single-Ins
6、truction Single-Data,单处理机结构)SIMD(Single-Instruction Multi-Data,带分布存储器)MISD(Multi-Instruction Single-Data,搏动式阵列)MIMD(Multi-Instruction Multi-Data,带共享存储器)12/20/20221012/20/202211 (1)(1)并行性粒度并行性粒度 G小则粒度细,通信量大。小则粒度细,通信量大。(2)并行性等级划分并行性等级划分 作业级、任务级、子程序级作业级、任务级、子程序级-MIMD-MIMD 循环级、语句或指令级循环级、语句或指令级 -SIMD-SIM
7、D 粗粗粒度通常采用粒度通常采用MIMD,细粒度则采用,细粒度则采用SIMD。2.2.并行处理并行处理 是一种相对串行处理的信息处理方式,侧是一种相对串行处理的信息处理方式,侧重并发性。重并发性。12/20/202212并行处理机 在单机系统里主要是采用时间重叠技术。把一件工作按功能分割为若干相互联系的部分,把每一部分指定给专门的部件完成,然后按时间重叠原则把各部分执行过程在时间上重叠起来,使所有部件依次分工完成一组同样的工作。并行处理机主要是通过资源重复技术来实现并行处理的。它属于单指令流多数据流(SIMD)计算机一类。12/20/2022131.1.组成组成 通常由通常由1 1个控制器个控
8、制器(CU)(CU),多个处理器,多个处理器(PE)(PE),m m个存储模块个存储模块(M)(M)及及1 1个互连网络个互连网络(ICN)(ICN)组成。组成。一、基本结构一、基本结构并行处理机工作原理并行处理机工作原理 根据存储模块组成方式可有分布式和集中式两种。根据存储模块组成方式可有分布式和集中式两种。ICN分布存集中式P0M0Pn-1Mn-1PE0PEn-1CUICNCUM0M1Mm-1PE0PE1PEn-112/20/202214基本结构的共同特点并行处理机的两种基本结构的共同特点:重复设置许多个同样的处理单元PE(Process Element);由ICN(Inter Conne
9、ction Network)按照一定的方式相互连接;在统一的控制部件CU(Control Unit)作用下;各PE对分配来的数据并行地完成同一条指令所规定的操作。12/20/202215并行处理的特点 资源重复。它机利用众多的处理单元对向量所包含的各个分量同时进行运算,获得很高处理速度。连接模式。它的处理单元间是通过ICN来通信的。不同的连接模式确定了它的不同结构。专用性。它直接与一定的算法相联系,其效率取决于在多大程度上把计算问题归结为向量数组处理。复合性。整个系统是由三部分复合起来的一个多机系统,即多个处理单元组成阵列并行地处理向量;功能极强的控制部件实际上是一台标量处理机;系统的管理功能
10、则由高性能单处理机担负。12/20/2022162.2.分布式结构分布式结构存储模块由每个存储模块由每个PEPE自带。自带。3.3.集中式结构集中式结构各个各个PEPE共享共享m m个存储模块。个存储模块。特点:特点:ICNICN:是单向的,:是单向的,PEPEPEPE。工作流程:工作流程:特点:特点:ICNICN:是双向的,:是双向的,PEMPEM。工作流程:工作流程:比较:比较:分布式每个分布式每个PEPE有局部存储器,集中式共享存储器。有局部存储器,集中式共享存储器。ICNICN的作用不同:分布式的作用不同:分布式PEPEPEPE,集中式,集中式PEMPEM。12/20/202217三、
11、阵列处理机的常用并行算法三、阵列处理机的常用并行算法1.1.有限差分问题有限差分问题 应用:应用:网格覆盖场;图像平滑化算法。网格覆盖场;图像平滑化算法。结构:结构:IN采用闭合螺旋线阵列。采用闭合螺旋线阵列。P189图图 原理:原理:实现:实现:每个每个PE存储和计算一组结点,多次迭代,直存储和计算一组结点,多次迭代,直到误差小于规定。到误差小于规定。效率:效率:接近接近N倍(要扣除通讯开销)。倍(要扣除通讯开销)。结点最大间距结点最大间距n-1,。12/20/202218互连网络基本概念互连网络基本概念并行计算机互连网络并行计算机互连网络基本功能基本功能 互连网络互连网络ICNICN主要完
12、成结点与结点间的连接,主要完成结点与结点间的连接,连接和控制方式不同,连接效果不同。连接和控制方式不同,连接效果不同。并行处理机互联网络并行处理机互联网络ICNICN是实现并行处理机是实现并行处理机中各处理单元之间或处理单元与存储器之间的中各处理单元之间或处理单元与存储器之间的信息交换。互联网络的不同拓扑结构直接决定信息交换。互联网络的不同拓扑结构直接决定了并行处理机的结构。了并行处理机的结构。12/20/202219结构特征结构特征 (1)(1)通信方式通信方式 同步同步、异步、异步 (3)(3)交换方式交换方式 线路交换线路交换、分组交换、分组交换 (4)(4)拓扑结构拓扑结构 (2)(2
13、)控制策略控制策略 集中集中、分散、分散12/20/202220设计思路设计思路 根据应用需要(互连网络属性),选择合根据应用需要(互连网络属性),选择合理的特征方式,考虑互连网络的性能因素,理的特征方式,考虑互连网络的性能因素,综合加以合理组合。综合加以合理组合。目标:目标:低成本、高灵活性、高连接度、低延时、适低成本、高灵活性、高连接度、低延时、适合合VLSIVLSI。互连网络表示互连网络表示 入端的编码:入端的编码:x=x=(b bn-1n-1bb0 0)n=log)n=log2 2N N 互连函数为基于互连函数为基于b bn-1n-1bb0 0的排列、组合、移位、取反的排列、组合、移位
14、、取反等操作的结果。等操作的结果。出端的编码:出端的编码:f(xf(x)=(b)=(bn-1n-1bb0 0)或其他形式。或其他形式。互连网络的连接特征一般用互连网络的连接特征一般用互连函数互连函数表示。表示。一个互连网络的连接特征可对应多个互连函数。一个互连网络的连接特征可对应多个互连函数。12/20/2022211.1.立方体单级网络立方体单级网络(交换互连网络)(交换互连网络)单级互连网络只能实现有限的几种连接。单级互连网络只能实现有限的几种连接。单级互连网络单级互连网络 出端编码与连接的入端结点的出端编码与连接的入端结点的编码有一位相反。编码有一位相反。zyx0100111101110
15、00001101100 互连函数:互连函数:CubeCube0 0=(b=(b2 2b b1 1b b0 0);CubeCube1 1=(b=(b2 2b b1 1b b0 0);CubeCube2 2=(b=(b2 2b b1 1b b0 0)。互连特性:互连特性:交换功能交换功能-互连函数可逆;互连函数可逆;互连函数个数互连函数个数=log=log2 28=38=3;最大连接度最大连接度=log=log2 28=38=3;结点最大间距结点最大间距=log=log2 28=38=3。12/20/202222 出端编码与连接的入端结点的编码有一位相反。出端编码与连接的入端结点的编码有一位相反。
16、互连函数:互连函数:CubeCube0 0=(b=(b2 2b b1 1b b0 0)(0 0,1 1)()(2 2,3 3)()(4 4,5 5)()(6 6,7 7)CubeCube1 1=(b=(b2 2b b1 1b b0 0)(0 0,2 2)()(1 1,3 3)()(4 4,6 6)()(5 5,7 7)CubeCube2 2=(b=(b2 2b b1 1b b0 0)(0 0,4 4)()(1 1,5 5)()(2 2,6 6)()(3 3,7 7)注意:立方体坐标编号不能标错。12/20/20222300000100000101001101001110010110010111
17、0111110111000001000001010011010011100101100101110111110111000001000001010011010011100101100101110111110111Cube0Cube1Cube2 连接图:连接图:扩展成超立方体:扩展成超立方体:有有n=logn=log2 2N N个互连函数;个互连函数;CubeCubei i=(b=(bn-1n-1bbi ibb0 0);最大连接度最大连接度=log=log2 2N N;结点最大间距结点最大间距=log=log2 2N N。应用:应用:几种互连函数反复调用,任意结点间可连接。几种互连函数反复调用,
18、任意结点间可连接。12/20/2022242.PM2I2.PM2I单级网络单级网络(循环移数网络)(循环移数网络)出端编码与连接的入端结点编码相差出端编码与连接的入端结点编码相差2 2i i。互连函数:互连函数:PM2IPM2I+i+i(j)=(j+2(j)=(j+2i i)mod N)mod N;n=logn=log2 2N,0in-1,N,0in-1,PM2IPM2I-i-i(j)=(j-2(j)=(j-2i i)mod N)mod N;0jN-10jN-1 共有共有2n2n个互连函数个互连函数(2n-1(2n-1种不同种不同)。连接图:连接图:00:顺环圆周连接;:顺环圆周连接;11:顺
19、环内接:顺环内接n/2n/2边形连接;边形连接;01234567 22:顺环内接:顺环内接n/4n/4边形连接;边形连接;(n-1)(n-1):顺环内直径连接。:顺环内直径连接。12/20/202225设n=8,则各互联循环为PM2+0:(01234567)PM2-0:(76543210)PM2+1:(0246)(1357)PM2-1:(6420)(7531)PM22:(04)(15)(26)(37)12/20/202226 互连特性:互连特性:2n2n个互连函数只有一种函数可逆,其余个互连函数只有一种函数可逆,其余均不可逆;均不可逆;最大连接度最大连接度2n-12n-1;结点最大间距结点最大
20、间距 n/2=logn/2=log2 2N/2 logN/2 log2 2N/2N/2;互连函数个数互连函数个数2n2n。应用:应用:几种互连函数混合,任意结点间可连接。几种互连函数混合,任意结点间可连接。实例:实例:闭合螺旋结构为闭合螺旋结构为PM2IPM2I+0+0及及PM2IPM2In/2n/2互连函数。互连函数。12/20/2022273.3.混洗交换单级网络混洗交换单级网络 全混洗(二混洗):全混洗(二混洗):000000001001010010011011100100101101110110111111三混洗:三混洗:00000001001000110100010101100111
21、1000100110101011000000010010001101000101011001111000100110101011 全混洗互连函数:全混洗互连函数:Shuffle(bShuffle(bn-1n-1b bn-2n-2bb1 1b b0 0)=(b)=(bn-2n-2bb1 1b b0 0b bn-1n-1);全全“0”0”或全或全“1”1”结点无法与其他结点连接,必结点无法与其他结点连接,必须辅以交换互连函数,方可实现任意结点间连接。须辅以交换互连函数,方可实现任意结点间连接。12/20/202228 最简单的交换互连函数为最简单的交换互连函数为CubeCube0 0,因此混洗,因
22、此混洗交换网络由全混洗和交换网络组合而成。交换网络由全混洗和交换网络组合而成。交换互连函数:交换互连函数:Exchange(bExchange(bn-1n-1b bn-2n-2bb1 1b b0 0)=(b)=(bn-1n-1b bn-2n-2bb1 1b b0 0);混洗交换互连函数:混洗交换互连函数:ExchangeShuffle(bExchangeShuffle(bn-1n-1b bn-2n-2bb1 1b b0 0)=(b =(bn-2n-2bb1 1b b0 0b bn-1n-1);连接图:连接图:0123456712/20/2022294.4.总结总结 任一单级互连网络均可表示成任
23、一单级互连网络均可表示成N N入入 N N出出的过程。的过程。(1)(1)单级互连网络特性单级互连网络特性 任一单级互连网络可实现部分结点任一单级互连网络可实现部分结点(一对或几对一对或几对)间的连接,不能实现间的连接,不能实现任意多对任意多对结点间的结点间的同时连接同时连接。单级互连网络含义:单级互连网络含义:某些连接方法或拓扑结构。某些连接方法或拓扑结构。(2)(2)单级互连网络应用单级互连网络应用 利用单级互连网络的特性作为实际利用单级互连网络的特性作为实际ININ的拓扑结构;的拓扑结构;通过交换开关作为通过交换开关作为ININ的可变因素;的可变因素;通过交换开关多次控制实现通过交换开关
24、多次控制实现ININ的结点间任意互连。的结点间任意互连。12/20/202230 阵列机结构阵列机结构 阵列机系统是并行处理机最常见的结构形式,它是由大量的处理机按一定规则的几何形式构成阵列形式。最早阵列机是ILLIAC,它是由4个处理机阵列构成,每个阵列里由64个处理单元和1个控制部件组成。12/20/202231阵列机结构阵列机结构(cont.)ILLIAC 阵列机结构(如图5-9所示)。64个PE按矩形排列成88方阵,PE只与自己四边相邻的PE相连。任意二个不相邻PE的通信可以通过选择最短路径的算法,由软件来实现。每个PE包括处理机外,还有自身的附属存储器PEM和存储器逻辑部件MLU。同
25、时还有包含I/O在内的特殊总线结构互联。像这种阵列机结构又称闭合螺线结构,也是阵列机系统结构中最常见的一种结构形式。12/20/202232阵列机结构阵列机结构(cont.)阵列机的处理属于SIMD形式(单指令流多数据流),它最适合作向量数组运算。每个处理单元相当于一个向量数组元素的运算,包括定点和浮点的多种运算操作。对于是阵列机处理单元个数的倍数的向量数组运算尤为合适。如PE=64,则16,32,64,128,256,512阵列向量数组就很方便地使阵列机发挥最佳效能。12/20/202233阵列机结构阵列机结构(cont.)阵列机中PE之间的互联通信是由互联寄存器来实现的。当PE执行互联指令
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五章 多处理机系统 第五 处理机 系统
限制150内