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的指令译码、执行。像指令操作那样，阵列机的存储器有双重变址机构，除了逻辑控制器的公共变址外，还有每个PE自己的单独变址。这样既节省了公共数据和指令所占的存储空间，又增加各PE对存储器数据分配的灵活性。阵列机结构(cont.)一般，每个PE都配有状态寄存器，它标志了目前本PE处于活动状态还是处于屏蔽状态；运算结果是否有错；矩阵边缘处于何种连接等等各种状态信息。

高性能计算机分三大类PVP向量型超级计算机，如国防科技大学研制的银河I（1亿次/秒）、银河II（10亿次/秒）。MPP大规模并行处理超级计算机，如国防科技大学研制的银河III（130亿次/秒）、中国科学院计算机技术研究所研制的曙光1000（25亿次/秒）、中国江南计算机技术研究所研制的神威I（3840亿次/秒）。Cluster集群计算机，中国科学院计算机技术研究所研制的曙光2000-II（1100亿次/秒）、

曙光3000（4030亿次/秒）、清华大学研制的THNPSC-1（320亿次/秒）、,上海大学研制的自强2000（4500亿次/秒）。大规模并行处理机(MPP)1979年，美国NASA-Goddard中心与Goodyear宇航公司合作研制一台用于处理遥感卫星图片的大规模SIMD阵列机获得成功。由于这台机器用了128*128=16384个可并行工作的微处理机，因此被定名为大规模并行处理机MPP（MassivelyParallelProcessor）。MPP可对变长的操作数按位片进行算术运算。MPP有一个微程序控制器，能够十分灵活地定义向量、标量和I/O操作的指令系统，整个MPP系统均用微处理器芯片和SRAM芯片组成。

大规模并行处理机(cont.)阵列部件ARU（ARrayUnit）由128*128个PE构成一个二维阵列，以SIMD方式工作。每个PE有一个1027位SRAM，有奇偶校验功能每个PE是位片式微处理机，与四周近邻相连。程序员可在平面、水平圆柱、垂直圆柱、开螺线、闭螺线等五种阵列拓扑中任选一种，增加了阵列机结构的灵活性。

大规模并行处理机(cont.)在阵列中增加了4列冗余PE，使阵列的物理结构为132列*128行。阵列硬件出现故障时可旁路掉故障列方法，使阵列逻辑结构仍为128*128。每个PE内有一个串行加法器及用一个移位寄存器实现位串式加法。PE阵列的时钟周期为100ns。阵列控制器ACU是微程序控制器，对PE阵列处理进行管理，完成标量运算以及控制数据在PE阵列上移位。

大规模并行处理机(cont.)程序和数据管理部件PDMU（ProgramandDataManagementUnit）是一台后端小型计算机，其作用是管理阵列中的数据流，将程序装入控制器，进行系统的测试和诊断并提供程序开发手段等。MPP系统运行方式有两种，独立方式由用户在终端予以操作控制；在线方式由外接计算机予以控制。MPP与外接计算机之间的数据传输速率为6MB/s，按高速数据方式运行时，数据通过128位外部接口传输，其速率可达320MB/s。

多处理机的基本结构

常用的松散耦合和紧密耦合这两种形式

松散耦合多处理机结构：互联常用通道或通信线路来实现，它们连接的频带较低。紧密耦合多处理机结构：通常是高速总线或高速开关实现机间互联，以共享存储器。

多处理机的基本结构通道连接的多处理机结构：

每台计算机是独立的，它们之间通过通道适配器连接。在进行通信时，发送的计算机可以把接受的计算机认为是自己的一个I/O设备，从而能完成两个主存储器之间的数据传送。

多处理机的基本结构(cont.)信息传输系统连接的多处理机结构：计算机模块通过一个信息传输系统连接起来。信息传输系统是耦合程度较低的，常用简单的分时总线及环形、星形等拓扑结构的系统。每个计算机模块可以是独立的计算机，它有处理单元、存储器、I/O部件。而模块与信息传输系统则通过通道仲裁开关相连。通道仲裁开关的作用除使要通信的计算机模块与被通信的计算机模块在信息传输系统里连接起来外，还起到多个模块同时申请信息传输系统时，决定本模块是提出申请还是延缓提出申请，故称有仲裁作用。

多处理机的基本结构(cont.)紧密耦合多处理机结构是真正的MPP：多个处理器通过互联网络（它是由高速开关来组成的）共享集中的主存储器（它由若干个存储模块组成）和多个输入输出设备。当某个处理机要访问主存储器，只需通过它的存储映象部件（MAP），就可以把全局的逻辑地址变换成局部的物理地址（即某一存储模块内的物理地址）。互联网络不仅要提供高速的传输通路，而且具有选择有效路径、仲裁访问冲突等功能。对于输入输出设备的访问也与访问存储器一样，只是它们的界面通过输入输出处理机（IOP）来进行。

多处理机的互联网络

多处理机的主要特点是各台处理机共享一组存储器和I/O设备。这种共享功能是通过两个互联网络实现的：一个是处理机和存储器模块之间的互联网络；另一个是处理机和I/O子系统（I/O接口和I/O设备）之间的互联网络。互联网络可以采用不同的物理形式，一般可有四种基本结构。

1.总线结构

多处理机结构最简单互联系统是把所有功能模块（或部件）连接到一条公共通信通路上，如图5-16所示。公共通信通路也称为时分或公共总线。这种总线结构的特点是简单、容易实现，也容易扩展（重构）。总线是一个无源部件，通信完全由发送和接收的总线接口控制。由于总线是共享资源，所以必须有总线请求和仲裁的机构，以避免发生总线冲突。

1.总线结构(cont.)总线仲裁方法有静态的或动态的优先级方法、先进先出（FIFO）队列方法、串行优先链方法和总线控制器（或仲裁器）方法。当一个处理机要占用总线时，首先需测试总线状态是否“忙”（busy），若是忙，则等待，等到空闲时（即不“忙”），发出总线请求信号，经仲裁后，等到总线响应信号，才可以占用总线，与目的部件进行通信。在一个处理机占用总线进行通信过程中，哪怕比其优先级高的处理机需占用总线，也不能终止（中断）原来已在进行中的通信过程。

1.总线结构(cont.)单总线结构简易而可靠。但总线接口线路出现任何一个故障会造成系统瘫痪。

为了提高总线通信效率，设置在同一时间可进行多条总线通信，但增加了系统的复杂性。影响总线性能的因素有：总线上主控设备（即能掌握、占用总线的部件）数量、总线仲裁算法、控制集中程度、数据宽度、数据传输同步和错误检测等。

1.总线结构(cont.)总线仲裁算法：静态优先级算法：给每一个设备一个唯一的优先级。

固定时间片算法：把带宽分成固定长度的时间片，按循环方式顺序分配给每个设备。

动态优先级算法

：优先级予以动态调整，使每个设备均有机会占用总线。“近期最少使用LRU”算法和旋转菊花链RDC算法。

先来先服务算法

：按照接受到的请求先后顺序予以处理。

总线形式

（时间分配）

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

当不断增加总线数目，使每个存储器模块有它自己单独可用的通路形成的互联网络称为无阻塞交叉开关。它的特点是开关和功能部件的接口非常简单，而且支持所有存储器模块同时通信。每个交叉点不仅能切换并行传播，而且必须能解决在同一存储器周期内访问同一个存储器模块的多个请求之间的冲突。通常用预设的优先级来处理冲突。交叉开关形式

（空间分配）是总线形式的极端，总线数=PE数+PEM数+I/O通道数，是一种全相联形式，控制、仲裁、转换机构均在开关中。

改进：用一系列较小开关串联或并联，形成多级交叉开关，减少其复杂性。交叉开关方式不适宜连接过多的处理机。3.多端口存储器

如果把分布在交叉开关矩阵网络上的控制、转接、优先级仲裁等逻辑功能转移到存储器模块的接口上，就形成了多端口存储器系统，如图5-25所示。这种系统既适合单处理机，也适合于多处理机。

将控制、仲裁、转换机构移到存储器中。每个端口与一个PE或I/O通道相连。多端口存储器形式不适宜连接过多的处理机。3.多端口存储器(cont.)对于访问存储器的冲突，常用的解决方法是每个存储器端口分配一个永久优先级，而各个主控模块相对于某个存储器模块有一个优先级别序列。例如对于M0而言，其能接收主控模块的访问优先次序为P0、P1、I/O0、I/O1；对于M1而言，则为P0、P1、I/O1、I/O0；对于M3而言，则为P1、P0、I/O1、I/O0；对于M3而言，则为P1、P0、I/O1、I/O0。

4.多级互连网络形式是介于总线(N)与交叉开关(N2)中间的一种(Nlog2N)。多级互连网络适宜于PE数较多的系统。a×b交叉开关a入b出，输入基于a编码，输出基于b编码。入端→出端受阻后，重新申请，性能受建立时间限制；设置缓冲器性能有所改善，适合于包交换网络。an×bn互连网络交叉开关为a×b开关，由n级构成。

比较：交叉开关时结点数为an×bn，多级互连网络时结点数为a×b×n2，明显降低了复杂性。多处理机系统结构并行处理机属SIMD结构，较适合向量处理；一、多处理机与并行处理机区别多处理机属MIMD结构，可进行更高层次的并行处理。1.结构与通用性

SIMD：单指令流系统，并行操作相同，一个CU，控制、数据通讯简单，通用性较差；

MIMD：多指令流系统，并行操作不同，多个CU，控制、数据通讯复杂，通用性较强。2.程序并行性

SIMD：操作级并行（数据并行），

识别：隐式识别和向量指令，

支持：编译程序和硬件；

MIMD：任务级并行（数据、功能并行），

识别：显式指令、编译程序、OS和硬件等，

支持：专用指令，OS对任务的分派和调度。3.任务派生

SIMD：向量指令表示及控制，隐式并行、效率低；

MIMD：专用指令表示及控制，显式并行、效率高。三、多处理机结构1.紧耦合系统(TCS)

特点：通过共享主存实现机间通讯。PPINPIOIND1PMpPMINM1······I/O通道···PM--局存CM--高速缓存P--处理器D--外部设备···PM1DDMM

互连网络：实现PE←→PEM、PE←→I/O通道、PE←→中断信号间的连接。2.松耦合系统(LCS)消息传送系统MTSPMI/ONI模块1NI--结点机接口·

·

·计算机模块(结点机)PMI/ONI模块N

特点：通过消息传送系统实现机间通讯；每个模块是一个独立的处理机，整个系统可看成是一个分布系统。

互连网络：MTS有总线、环形、多级网络等种类；

结构：有层次和非层次两种结构。多处理机系统的存储器结构

在多处理机系统中，为了减少访存冲突，主存采用并行存储器结构。多个存储模块可采用低位交叉编址技术，也可采用高位交叉编址技术。能为某处理机进程放置大多数页面的存储器模块称为该处理机宿主存储器，图5-31所示。如果该处理器的现行进程全部活动页面在宿主存储器内，而且该存储器不包含其他处理机的页面，则处理机不会遇到存储冲突。

多处理机系统的存储器结构(cont.)多处理机系统中常采用二维存储器结构，如图5-32所示。有n个同样容量的存储模块，排成l列（体），每一列有m个模块组成。各列之间按高位交叉编址，而列内各模块为按低位交叉编址，每列有一个列控制器连到互联网络。

多处理机系统的cache结构

当每个处理机都有自己专用的cache时，对应主存中某一个单元的数据，在各个cache中可能会出现相应的多个副本，当对其中某一个副本进行一次修改操作，就会产生cache中数据不一致性。无论cache采用“写回法”或“写直接法”，都不能解决多个cache不一致问题。

静态一致性校验

只让该进程的独用信息（指令和操作数据）和共享的只读信息进入本处理机的cache，而对于共享的可写（即可修改）的信息不准进入cache，只可留在主存中。这种方法增加了互联网络和主存的竞争，因此，性能较差。减少竞争的方法是增加一个共享cache--sc（sharedcache），共享信息均在sc内，而取指令和独用数据则通过独用cache--pc（privatecache），其结构如图5-33所示。

动态一致性校验

基本思想是在若干个cache中使同一个信息（指令、数据）始终保持动态一致。一种方法是广播法：即当每个处理机每次写cache时，不仅写入自己的cache和共享的主存中，而且还把信息送到所有cache，如果其他cache有与自己cache相同的目标行，则也进行改写。

动态一致性校验(cont.)另一种时目录法。在快速ram中构建一个目录表，如图5-34所示。它有两个部分：存在表（presenttable）是二维的，其中每一项P（i,c）表示第i块是在第c个cache中，修改表（modifiedtable）是一维的，其中每项M（i）表示第i块是否被修改过。在每个cache中还有一个本地标志（可