CA第五章—多处理机系统

多处理机系统上海大学计算机系统结构课程组多处理机系统的定义P.H.Enslow对多处理机作了下列定义：*包含两个或两个以上功能大致相同的处理器；*所有处理器共享一个公共内存；*所有处理器共享I/O通道、控制器和外围设备；*整个系统由统一的操作系统控制，在处理器和程序之间实现作业、任务、程序段、数组和数组元素等各级的全面并行。多处理机的优点•很高的性能价格比：单处理机的性能价格比随其规模的增大而下降•很高的可靠性：冗余度大、可维护性、可用性•很高的处理速度：多个处理器并行运算•很好的模块性：大量重复设置，结构灵活性、可扩充性、可重构性特性要求--进程恢复能力•多处理机系统使用的处理机结构应能反映进程和处理机是两个不同的实体。如果某处理机发生故障，另一台处理机应能检索到被中断的进程状态，使被中断的进程能继续运行。没有这个功能，系统的可靠性大大下降。大多数处理机把当前正在运行进程状态保存在内部寄存器中，如何使其他处理器在必要时能访问到进程状态，是恢复进程的关键之一。在不太损失速度的前提下，把通用寄存器与处理机本身分开是可能的，在系统内设置所有处理机共享的寄存器堆可以实现上述功能。特性要求--有效的现场切换•现场切换操作是把当前进程状态保存起来，然后通过恢复新进程的状态切换到被选中的准备好运行的进程。•切换操作可以在指令系统中设置一条专门指令来完成。该指令执行的结果是将当前进程状态或现场内容保存起来，然后到主存储器的缓冲区取另一个进程状态，该缓冲区称为交换包。特性要求--大的物理地址空间和虚拟地址空间•多处理机系统内的处理机必须能支持大的物理地址空间（即直接寻址空间要大），这是因为进程需要访问大量数据。例如，Pentium地址线32根，直接寻址空间可达4GB，能满足需求。有了大的物理地址空间，还需要大的虚拟地址空间，把虚拟地址空间分段，便于模块共享以及地址界限的检查。特性要求--高效率的同步原语•处理机设计时必须能提供作为同步原语基础的某种不可再分的操作。这些同步原语需要有互斥机构支持。当两个以上的进程并发地运行或相互交换数据时，需要互斥。•互斥机构包含某种形式的读—修改—写存储周期和排队。信号灯（semaphore）是互斥机构的一种。每个信号灯有其队列，队列中的项是被挂起来的进程。信号灯操作是不可分操作，利用读—修改—写存储周期，测试和修改信号灯。队列操作也应是不可分的。特性要求--处理机之间有高效率的通信机构•通信机构可用硬件实现。它有助于实现处理机之间的同步。在非对称多处理机系统中，不同的处理机之间经常需要交换服务请求，硬件通信机构作用更加明显。在处理机发生故障时，通过该机构发信号给其他正在运行的处理机，并启动诊断过程或纠错过程。•在紧密耦合的多处理机系统内有共享存储器，采用软件方法实现多处理机之间的通信是可能的。每个处理机必须周期地检查位于共享存储器内的“信箱”（缓冲区），检查是否有信息给它。特性要求--指令系统•处理机的指令系统应能支持实现具有过程级并发功能的高级语言，为有效的处理数据结构提供充分条件。•指令系统内应有过程连接、循环结构、参数处理、多维下标计算和地址界限检查等指令。•还需包括产生和结束程序内部并行执行通路的指令。•设置特权指令。Flynn分类法MichealFlynn(1972)提出指令流、数据流和多倍性概念，把不同的计算机分为四大类（下图）：•SISD（Single-InstructionSingle-Data,单处理机结构）•SIMD（Single-InstructionMulti-Data,带分布存储器）•MISD（Multi-InstructionSingle-Data,搏动式阵列）•MIMD（Multi-InstructionMulti-Data,带共享存储器）并行处理机•在单机系统里主要是采用时间重叠技术。把一件工作按功能分割为若干相互联系的部分，把每一部分指定给专门的部件完成，然后按时间重叠原则把各部分执行过程在时间上重叠起来，使所有部件依次分工完成一组同样的工作。•并行处理机主要是通过资源重复技术来实现并行处理的。它属于单指令流多数据流（SIMD）计算机一类。1.组成通常由1个控制器(CU)，多个处理器(PE)，m个存储模块(M)及1个互连网络(ICN)组成。一、基本结构并行处理机工作原理根据存储模块组成方式可有分布式和集中式两种。ICN分布存集中式P0M0Pn-1Mn-1PE0PEn-1CUICNCUM0M1Mm-1······PE0PE1PEn-1···基本结构的共同特点并行处理机的两种基本结构的共同特点：•重复设置许多个同样的处理单元PE（ProcessElement）；•由ICN(InterConnectionNetwork)按照一定的方式相互连接；•在统一的控制部件CU（ControlUnit）作用下；•各PE对分配来的数据并行地完成同一条指令所规定的操作。并行处理的特点•资源重复。它机利用众多的处理单元对向量所包含的各个分量同时进行运算，获得很高处理速度。•连接模式。它的处理单元间是通过ICN来通信的。不同的连接模式确定了它的不同结构。•专用性。它直接与一定的算法相联系，其效率取决于在多大程度上把计算问题归结为向量数组处理。•复合性。整个系统是由三部分复合起来的一个多机系统，即多个处理单元组成阵列并行地处理向量；功能极强的控制部件实际上是一台标量处理机；系统的管理功能则由高性能单处理机担负。2.分布式结构存储模块由每个PE自带。3.集中式结构各个PE共享m个存储模块。特点：ICN：是单向的，PE→PE。工作流程：特点：ICN：是双向的，PE←→M。工作流程：比较：分布式每个PE有局部存储器，集中式共享存储器。ICN的作用不同：分布式PE→PE，集中式PE←→M。互连网络基本概念并行计算机互连网络基本功能互连网络ICN主要完成结点与结点间的连接，连接和控制方式不同，连接效果不同。并行处理机互联网络ICN是实现并行处理机中各处理单元之间或处理单元与存储器之间的信息交换。互联网络的不同拓扑结构直接决定了并行处理机的结构。结构特征(1)通信方式同步、异步(3)交换方式线路交换、分组交换(4)拓扑结构(2)控制策略集中、分散设计思路根据应用需要（互连网络属性），选择合理的特征方式，考虑互连网络的性能因素，综合加以合理组合。目标：低成本、高灵活性、高连接度、低延时、适合VLSI。互连网络表示入端的编码：x=（bn-1…b0)n=log2N互连函数为基于bn-1…b0的排列、组合、移位、取反等操作的结果。出端的编码：f(x)=(bn-1…b0)或其他形式。互连网络的连接特征一般用互连函数表示。一个互连网络的连接特征可对应多个互连函数。1.立方体单级网络（交换互连网络）单级互连网络只能实现有限的几种连接。单级互连网络出端编码与连接的入端结点的编码有一位相反。zyx010011110111000001101100互连函数：Cube0=(b2b1b0)；Cube1=(b2b1b0)；Cube2=(b2b1b0)。互连特性：交换功能--互连函数可逆；互连函数个数=log28=3；最大连接度=log28=3；结点最大间距=log28=3。出端编码与连接的入端结点的编码有一位相反。互连函数：Cube0=(b2b1b0)（0，1）（2，3）（4，5）（6，7）Cube1=(b2b1b0)（0，2）（1，3）（4，6）（5，7）Cube2=(b2b1b0)（0，4）（1，5）（2，6）（3，7）注意：立方体坐标编号不能标错。000001000001010011010011100101100101110111110111000001000001010011010011100101100101110111110111000001000001010011010011100101100101110111110111Cube0Cube1Cube2连接图：扩展成超立方体：有n=log2N个互连函数；Cubei=(bn-1…bi…b0)；最大连接度=log2N；结点最大间距=log2N。应用：几种互连函数反复调用，任意结点间可连接。2.PM2I单级网络（循环移数网络）出端编码与连接的入端结点编码相差2i。互连函数：PM2I+i(j)=(j+2i)modN；n=log2N,0≤i≤n-1,PM2I-i(j)=(j-2i)modN；0≤j≤N-1共有2n个互连函数(2n-1种不同)。连接图：±0：顺环圆周连接；±1：顺环内接n/2边形连接；01234567±2：顺环内接n/4边形连接；±(n-1)：顺环内直径连接。设n=8，则各互联循环为PM2+0：（01234567）PM2-0：（76543210）PM2+1：（0246）（1357）PM2-1：（6420）（7531）PM2±2：（04）（15）（26）（37）互连特性：最大连接度2n-1；结点最大间距n/2=log2N/2≤log2N/2；互连函数个数2n。应用：几种互连函数混合，任意结点间可连接。实例：闭合螺旋结构为PM2I+0及PM2I±n/2互连函数。3.混洗交换单级网络全混洗（二混洗）：000000001001010010011011100100101101110110111111三混洗：000000010010001101000101011001111000100110101011000000010010001101000101011001111000100110101011全混洗互连函数：Shuffle(bn-1bn-2…b1b0)=(bn-2…b1b0bn-1)；全“0”或全“1”结点无法与其他结点连接，必须辅以交换互连函数，方可实现任意结点间连接。最简单的交换互连函数为Cube0，因此混洗交换网络由全混洗和交换网络组合而成。交换互连函数：Exchange(bn-1bn-2…b1b0)=(bn-1bn-2…b1b0)；混洗交换互连函数：Exchange[Shuffle(bn-1bn-2…b1b0)]=(bn-2…b1b0bn-1)；连接图：012345674.总结任一单级互连网络均可表示成N入N出的过程。(1)单级互连网络特性任一单级互连网络可实现部分结点(一对或几对)间的连接，不能实现任意多对结点间的同时连接。单级互连网络含义：某些连接方法或拓扑结构。(2)单级互连网络应用利用单级互连网络的特性作为实际IN的拓扑结构；通过交换开关作为IN的可变因素；通过交换开关多次控制实现IN的结点间任意互连。阵列机结构•阵列机系统是并行处理机最常见的结构形式，它是由大量的处理机按一定规则的几何形式构成阵列形式。•最早阵列机是ILLIACⅣ，它是由4个处理机阵列构成，每个阵列里由64个处理单元和1个控制部件组成。阵列机结构(cont.)•ILLIACⅣ阵列机结构（如图5-9所示）。•64个PE按矩形排列成8×8方阵，PE只与自己四边相邻的PE相连。任意二个不相邻PE的通信可以通过选择最短路径的算法，由软件来实现。•每个PE包括处理机外，还有自身的附属存储器PEM和存储器逻辑部件MLU。同时还有包含I/O在内的特殊总线结构互联。•像这种阵列机结构又称闭合螺线结构，也是阵列机系统结构中最常见的一种结构形式。阵列机结构(cont.)•阵列机的处理属于SIMD形式（单指令流多数据流），它最适合作向量数组运算。每个处理单元相当于一个向量数组元素的运算，包括定点和浮点的多种运算操作。对于是阵列机处理单元个数的倍数的向量数组运算尤为合适。如PE=64，则16，32，64，128，256，512···阵列向量数组就很方便地使阵列机发挥最佳效能。阵列机结构(cont.)•阵列机中PE之间的互联通信是由互联寄存器来实现的。当PE执行互联指令时，由本PE的互联寄存器与相邻PE互联寄存器进行信息交换。阵列机结构(cont.)•阵列机的操作分公共操作和本地操作。公共操作是指阵列机中的所有PE同时执行的操作，它一般由逻辑控制器来调度。本地操作是每个PE自己的操作，它由PE的指