《第五章多处理机系统课件.ppt》由会员分享，可在线阅读，更多相关《第五章多处理机系统课件.ppt（113页珍藏版）》请在三一办公上搜索。
1、22.12.2022,1,多处理机系统,22.12.2022,2,多处理机系统的定义,P.H.Enslow对多处理机作了下列定义： * 包含两个或两个以上功能大致相同的处理器； * 所有处理器共享一个公共内存； * 所有处理器共享I/O通道、控制器和外围设备； * 整个系统由统一的操作系统控制，在处理器和程序之间实现作业、任务、程序段、数组和数组元素等各级的全面并行。,22.12.2022,3,多处理机的优点,很高的性能价格比 ： 单处理机的性能价格比随其规模的增大而下降 很高的可靠性 ：冗余度大、可维护性、可用性 很高的处理速度：多个处理器并行运算 很好的模块性：大量重复设置，结构灵活性、可
2、扩充性、可重构性,22.12.2022,4,特性要求-进程恢复能力,多处理机系统使用的处理机结构应能反映进程和处理机是两个不同的实体。如果某处理机发生故障，另一台处理机应能检索到被中断的进程状态，使被中断的进程能继续运行。没有这个功能，系统的可靠性大大下降。大多数处理机把当前正在运行进程状态保存在内部寄存器中，如何使其他处理器在必要时能访问到进程状态，是恢复进程的关键之一。在不太损失速度的前提下，把通用寄存器与处理机本身分开是可能的，在系统内设置所有处理机共享的寄存器堆可以实现上述功能。,22.12.2022,5,特性要求-有效的现场切换,现场切换操作是把当前进程状态保存起来，然后通过恢复新进
3、程的状态切换到被选中的准备好运行的进程。切换操作可以在指令系统中设置一条专门指令来完成。该指令执行的结果是将当前进程状态或现场内容保存起来，然后到主存储器的缓冲区取另一个进程状态，该缓冲区称为交换包。,22.12.2022,6,特性要求-大的物理地址空间和虚拟地址空间,多处理机系统内的处理机必须能支持大的物理地址空间（即直接寻址空间要大），这是因为进程需要访问大量数据。例如，Pentium地址线32根，直接寻址空间可达4GB，能满足需求。有了大的物理地址空间，还需要大的虚拟地址空间，把虚拟地址空间分段，便于模块共享以及地址界限的检查。,22.12.2022,7,特性要求-高效率的同步原语,处理
4、机设计时必须能提供作为同步原语基础的某种不可再分的操作。这些同步原语需要有互斥机构支持。当两个以上的进程并发地运行或相互交换数据时，需要互斥。互斥机构包含某种形式的读修改写存储周期和排队。信号灯（semaphore）是互斥机构的一种。每个信号灯有其队列，队列中的项是被挂起来的进程。信号灯操作是不可分操作，利用读修改写存储周期，测试和修改信号灯。队列操作也应是不可分的。,22.12.2022,8,特性要求-处理机之间有高效率的通信机构,通信机构可用硬件实现。它有助于实现处理机之间的同步。在非对称多处理机系统中，不同的处理机之间经常需要交换服务请求，硬件通信机构作用更加明显。在处理机发生故障时，通
5、过该机构发信号给其他正在运行的处理机，并启动诊断过程或纠错过程。在紧密耦合的多处理机系统内有共享存储器，采用软件方法实现多处理机之间的通信是可能的。每个处理机必须周期地检查位于共享存储器内的“信箱”（缓冲区），检查是否有信息给它。,22.12.2022,9,特性要求-指令系统,处理机的指令系统应能支持实现具有过程级并发功能的高级语言，为有效的处理数据结构提供充分条件。指令系统内应有过程连接、循环结构、参数处理、多维下标计算和地址界限检查等指令。还需包括产生和结束程序内部并行执行通路的指令。设置特权指令。,22.12.2022,10,Flynn分类法,Micheal Flynn(1972)提出指
6、令流、数据流和多倍性概念，把不同的计算机分为四大类（下图）：SISD（Single-Instruction Single-Data,单处理机结构）SIMD（Single-Instruction Multi-Data,带分布存储器）MISD（Multi-Instruction Single-Data,搏动式阵列）MIMD（Multi-Instruction Multi-Data,带共享存储器）,22.12.2022,11,22.12.2022,12,(1)并行性粒度,G小则粒度细，通信量大。,(2)并行性等级划分,作业级、任务级、子程序级-MIMD 循环级、语句或指令级 -SIMD,粗粒度通常采
7、用MIMD，细粒度则采用SIMD。,2.并行处理,是一种相对串行处理的信息处理方式，侧重并发性。,22.12.2022,13,并行处理机,在单机系统里主要是采用时间重叠技术。把一件工作按功能分割为若干相互联系的部分，把每一部分指定给专门的部件完成，然后按时间重叠原则把各部分执行过程在时间上重叠起来，使所有部件依次分工完成一组同样的工作。 并行处理机主要是通过资源重复技术来实现并行处理的。它属于单指令流多数据流（SIMD）计算机一类。,22.12.2022,14,1.组成,通常由1个控制器(CU)，多个处理器(PE)，m个存储模块(M)及1个互连网络(ICN)组成。,一、基本结构,并行处理机工作
8、原理,根据存储模块组成方式可有分布式和集中式两种。,22.12.2022,15,基本结构的共同特点,并行处理机的两种基本结构的共同特点：重复设置许多个同样的处理单元PE（Process Element）；由ICN(Inter Connection Network)按照一定的方式相互连接；在统一的控制部件CU（Control Unit）作用下；各PE对分配来的数据并行地完成同一条指令所规定的操作。,22.12.2022,16,并行处理的特点,资源重复。它机利用众多的处理单元对向量所包含的各个分量同时进行运算，获得很高处理速度。 连接模式。它的处理单元间是通过ICN来通信的。不同的连接模式确定了它
9、的不同结构。 专用性。它直接与一定的算法相联系，其效率取决于在多大程度上把计算问题归结为向量数组处理。 复合性。整个系统是由三部分复合起来的一个多机系统，即多个处理单元组成阵列并行地处理向量；功能极强的控制部件实际上是一台标量处理机；系统的管理功能则由高性能单处理机担负。,22.12.2022,17,2.分布式结构,存储模块由每个PE自带。,3.集中式结构,各个PE共享m个存储模块。,特点：,ICN：是单向的，PEPE。,工作流程：,特点：,ICN：是双向的，PEM。,工作流程：,比较：,分布式每个PE有局部存储器，集中式共享存储器。,ICN的作用不同：分布式PEPE，集中式PEM。,22.1
10、2.2022,18,三、阵列处理机的常用并行算法,1.有限差分问题,应用：网格覆盖场；图像平滑化算法。,结构：IN采用闭合螺旋线阵列。P189图,原理：,实现：每个PE存储和计算一组结点，多次迭代，直到误差小于规定。,效率：接近N倍（要扣除通讯开销）。,结点最大间距n-1， 。,22.12.2022,19,互连网络基本概念,并行计算机互连网络,基本功能,互连网络ICN主要完成结点与结点间的连接，连接和控制方式不同，连接效果不同。 并行处理机互联网络ICN是实现并行处理机中各处理单元之间或处理单元与存储器之间的信息交换。互联网络的不同拓扑结构直接决定了并行处理机的结构。,22.12.2022,2
11、0,结构特征,(1)通信方式 同步、异步,(3)交换方式 线路交换、分组交换,(4)拓扑结构,(2)控制策略 集中、分散,22.12.2022,21,设计思路,根据应用需要（互连网络属性），选择合理的特征方式，考虑互连网络的性能因素，综合加以合理组合。,目标：低成本、高灵活性、高连接度、低延时、适合VLSI。,互连网络表示,入端的编码：x=（bn-1b0) n=log2N,互连函数为基于bn-1b0的排列、组合、移位、取反等操作的结果。,互连网络的连接特征一般用互连函数表示。,一个互连网络的连接特征可对应多个互连函数。,22.12.2022,22,1.立方体单级网络（交换互连网络）,单级互连网
12、络只能实现有限的几种连接。,单级互连网络,出端编码与连接的入端结点的编码有一位相反。,互连函数：,互连特性：,交换功能-互连函数可逆；,互连函数个数=log28=3；,最大连接度=log28=3；,结点最大间距=log28=3。,22.12.2022,23,出端编码与连接的入端结点的编码有一位相反。,互连函数：,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）,注意：立方体坐标编号不能标错。,22.12.2022,24,连接图：,
13、扩展成超立方体：,有n=log2N个互连函数；,最大连接度=log2N；,结点最大间距=log2N。,应用：几种互连函数反复调用，任意结点间可连接。,22.12.2022,25,2.PM2I单级网络（循环移数网络）,出端编码与连接的入端结点编码相差2i。,互连函数：,PM2I+i(j)=(j+2i) mod N； n=log2N,0in-1,PM2I-i(j)=(j-2i) mod N； 0jN-1,共有2n个互连函数(2n-1种不同)。,连接图：,0：顺环圆周连接；,1：顺环内接n/2边形连接；,2：顺环内接n/4边形连接；,(n-1)：顺环内直径连接。,22.12.2022,26,设n=8
14、，则各互联循环为PM2+0：（01234567）PM2-0：（76543210）PM2+1：（0246）（1357）PM2-1：（6420）（7531） PM22：（04）（15）（26）（37）,22.12.2022,27,互连特性：,2n个互连函数只有一种函数可逆，其余均不可逆；,最大连接度2n-1；,互连函数个数2n。,应用：几种互连函数混合，任意结点间可连接。,实例：闭合螺旋结构为PM2I+0及PM2In/2互连函数。,22.12.2022,28,3.混洗交换单级网络,全混洗（二混洗）：,三混洗：,全混洗互连函数：,Shuffle(bn-1bn-2b1b0)=(bn-2b1b0bn-1
15、)；,全“0”或全“1”结点无法与其他结点连接，必须辅以交换互连函数，方可实现任意结点间连接。,22.12.2022,29,最简单的交换互连函数为Cube0，因此混洗交换网络由全混洗和交换网络组合而成。,交换互连函数：,混洗交换互连函数：,连接图：,22.12.2022,30,4.总结,(1)单级互连网络特性,任一单级互连网络可实现部分结点(一对或几对)间的连接，不能实现任意多对结点间的同时连接。,单级互连网络含义：某些连接方法或拓扑结构。,(2)单级互连网络应用,利用单级互连网络的特性作为实际IN的拓扑结构；,通过交换开关作为IN的可变因素；,通过交换开关多次控制实现IN的结点间任意互连。,
16、22.12.2022,31,阵列机结构,阵列机系统是并行处理机最常见的结构形式，它是由大量的处理机按一定规则的几何形式构成阵列形式。最早阵列机是ILLIAC ，它是由4个处理机阵列构成，每个阵列里由64个处理单元和1个控制部件组成。,22.12.2022,32,阵列机结构(cont.),ILLIAC 阵列机结构（如图5-9所示）。64个PE按矩形排列成88方阵，PE只与自己四边相邻的PE相连。任意二个不相邻PE的通信可以通过选择最短路径的算法，由软件来实现。每个PE包括处理机外，还有自身的附属存储器PEM和存储器逻辑部件MLU。同时还有包含I/O在内的特殊总线结构互联。像这种阵列机结构又称闭合
17、螺线结构，也是阵列机系统结构中最常见的一种结构形式。,22.12.2022,33,阵列机结构(cont.),阵列机的处理属于SIMD形式（单指令流多数据流），它最适合作向量数组运算。每个处理单元相当于一个向量数组元素的运算，包括定点和浮点的多种运算操作。对于是阵列机处理单元个数的倍数的向量数组运算尤为合适。如PE=64，则16，32，64，128，256，512阵列向量数组就很方便地使阵列机发挥最佳效能。,22.12.2022,34,阵列机结构(cont.),阵列机中PE之间的互联通信是由互联寄存器来实现的。当PE执行互联指令时，由本PE的互联寄存器与相邻PE互联寄存器进行信息交换。,22.1
18、2.2022,35,阵列机结构(cont.),阵列机的操作分公共操作和本地操作。公共操作是指阵列机中的所有PE同时执行的操作，它一般由逻辑控制器来调度。本地操作是每个PE自己的操作，它由PE的指令译码、执行。像指令操作那样，阵列机的存储器有双重变址机构，除了逻辑控制器的公共变址外，还有每个PE自己的单独变址。这样既节省了公共数据和指令所占的存储空间，又增加各PE对存储器数据分配的灵活性。,22.12.2022,36,阵列机结构(cont.),一般，每个PE都配有状态寄存器，它标志了目前本PE处于活动状态还是处于屏蔽状态；运算结果是否有错；矩阵边缘处于何种连接等等各种状态信息。,22.12.20
19、22,37,阵列机算法,举例矩阵问题：矩阵运算是最适合阵列机运行的。如A、B两个矩阵相加，只要把A和B居于相应位置的一对分量存放在同一个处理单元存储器内。当阵列机执行加法公共操作时，每个处理单元都将处于本结点的Ai和Bi两个矩阵元素进行加法运算，其和即为矩阵和的对应元素。,22.12.2022,38,阵列机算法(cont.),累加和问题 ：书上有详细的举例，请自学。,22.12.2022,39,高性能计算机分三大类,PVP向量型超级计算机，如国防科技大学研制的银河I（1亿次/秒）、银河II（10亿次/秒）。MPP大规模并行处理超级计算机，如国防科技大学研制的银河III（130亿次/秒）、中国科
20、学院计算机技术研究所研制的曙光1000（25亿次/秒）、中国江南计算机技术研究所研制的神威I（3840亿次/秒）。Cluster集群计算机，中国科学院计算机技术研究所研制的曙光2000-II（1100亿次/秒）、 曙光3000（4030亿次/秒）、清华大学研制的THNPSC-1（320亿次/秒）、,上海大学研制的自强2000（4500亿次/秒）。,22.12.2022,40,大规模并行处理机(MPP),1979年，美国NASA-Goddard中心与Goodyear宇航公司合作研制一台用于处理遥感卫星图片的大规模SIMD阵列机获得成功。由于这台机器用了128*128=16384个可并行工作的微处
21、理机，因此被定名为大规模并行处理机MPP（Massively Parallel Processor）。MPP可对变长的操作数按位片进行算术运算。MPP有一个微程序控制器，能够十分灵活地定义向量、标量和I/O操作的指令系统，整个MPP系统均用微处理器芯片和SRAM芯片组成。,22.12.2022,41,大规模并行处理机(cont.),阵列部件ARU（ARray Unit）由128*128个PE构成一个二维阵列，以SIMD方式工作。每个PE有一个1027位SRAM，有奇偶校验功能每个PE是位片式微处理机，与四周近邻相连。程序员可在平面、水平圆柱、垂直圆柱、开螺线、闭螺线等五种阵列拓扑中任选一种，增
22、加了阵列机结构的灵活性。,22.12.2022,42,大规模并行处理机(cont.),在阵列中增加了4列冗余PE，使阵列的物理结构为132列*128行。阵列硬件出现故障时可旁路掉故障列方法，使阵列逻辑结构仍为128*128。每个PE内有一个串行加法器及用一个移位寄存器实现位串式加法。PE阵列的时钟周期为100ns。阵列控制器ACU是微程序控制器，对PE阵列处理进行管理，完成标量运算以及控制数据在PE阵列上移位。,22.12.2022,43,大规模并行处理机(cont.),程序和数据管理部件PDMU（Program and Data Management Unit）是一台后端小型计算机，其作用是
23、管理阵列中的数据流，将程序装入控制器，进行系统的测试和诊断并提供程序开发手段等。MPP系统运行方式有两种，独立方式由用户在终端予以操作控制；在线方式由外接计算机予以控制。MPP与外接计算机之间的数据传输速率为6MB/s，按高速数据方式运行时，数据通过128位外部接口传输，其速率可达320MB/s。,22.12.2022,44,多处理机的基本结构,常用的松散耦合和紧密耦合这两种形式 松散耦合多处理机结构：互联常用通道或通信线路来实现，它们连接的频带较低。紧密耦合多处理机结构：通常是高速总线或高速开关实现机间互联，以共享存储器。,22.12.2022,45,多处理机的基本结构,通道连接的多处理机结
24、构： 每台计算机是独立的，它们之间通过通道适配器连接。在进行通信时，发送的计算机可以把接受的计算机认为是自己的一个I/O设备，从而能完成两个主存储器之间的数据传送。,22.12.2022,46,多处理机的基本结构(cont.),信息传输系统连接的多处理机结构：计算机模块通过一个信息传输系统连接起来。信息传输系统是耦合程度较低的，常用简单的分时总线及环形、星形等拓扑结构的系统。每个计算机模块可以是独立的计算机，它有处理单元、存储器、I/O部件。而模块与信息传输系统则通过通道仲裁开关相连。通道仲裁开关的作用除使要通信的计算机模块与被通信的计算机模块在信息传输系统里连接起来外，还起到多个模块同时申请
25、信息传输系统时，决定本模块是提出申请还是延缓提出申请，故称有仲裁作用。,22.12.2022,47,多处理机的基本结构(cont.),紧密耦合多处理机结构是真正的MPP：多个处理器通过互联网络（它是由高速开关来组成的）共享集中的主存储器（它由若干个存储模块组成）和多个输入输出设备。当某个处理机要访问主存储器，只需通过它的存储映象部件（MAP），就可以把全局的逻辑地址变换成局部的物理地址（即某一存储模块内的物理地址）。互联网络不仅要提供高速的传输通路，而且具有选择有效路径、仲裁访问冲突等功能。对于输入输出设备的访问也与访问存储器一样，只是它们的界面通过输入输出处理机（IOP）来进行。,22.12
26、.2022,48,多处理机的互联网络,多处理机的主要特点是各台处理机共享一组存储器和I/O设备。这种共享功能是通过两个互联网络实现的：一个是处理机和存储器模块之间的互联网络；另一个是处理机和I/O子系统（I/O接口和I/O设备）之间的互联网络。互联网络可以采用不同的物理形式，一般可有四种基本结构。,22.12.2022,49,1.总线结构,多处理机结构最简单互联系统是把所有功能模块（或部件）连接到一条公共通信通路上，如图5-16所示。公共通信通路也称为时分或公共总线。这种总线结构的特点是简单、容易实现，也容易扩展（重构）。总线是一个无源部件，通信完全由发送和接收的总线接口控制。由于总线是共享资
27、源，所以必须有总线请求和仲裁的机构，以避免发生总线冲突。,22.12.2022,50,1.总线结构(cont.),总线仲裁方法有静态的或动态的优先级方法、先进先出（FIFO）队列方法、串行优先链方法和总线控制器（或仲裁器）方法。当一个处理机要占用总线时，首先需测试总线状态是否“忙”（busy），若是忙，则等待，等到空闲时（即不“忙”），发出总线请求信号，经仲裁后，等到总线响应信号，才可以占用总线，与目的部件进行通信。在一个处理机占用总线进行通信过程中，哪怕比其优先级高的处理机需占用总线，也不能终止（中断）原来已在进行中的通信过程。,22.12.2022,51,1.总线结构(cont.),单总线
28、结构简易而可靠。但总线接口线路出现任何一个故障会造成系统瘫痪。 为了提高总线通信效率，设置在同一时间可进行多条总线通信，但增加了系统的复杂性。影响总线性能的因素有：总线上主控设备（即能掌握、占用总线的部件）数量、总线仲裁算法、控制集中程度、数据宽度、数据传输同步和错误检测等。,22.12.2022,52,1.总线结构(cont.),总线仲裁算法：静态优先级算法：给每一个设备一个唯一的优先级。 固定时间片算法：把带宽分成固定长度的时间片，按循环方式顺序分配给每个设备。 动态优先级算法 ：优先级予以动态调整，使每个设备均有机会占用总线。“近期最少使用LRU”算法和旋转菊花链RDC算法。 先来先服务
29、算法 ：按照接受到的请求先后顺序予以处理。,22.12.2022,53,2.交叉开关,当不断增加总线数目，使每个存储器模块有它自己单独可用的通路形成的互联网络称为无阻塞交叉开关。它的特点是开关和功能部件的接口非常简单，而且支持所有存储器模块同时通信。每个交叉点不仅能切换并行传播，而且必须能解决在同一存储器周期内访问同一个存储器模块的多个请求之间的冲突。通常用预设的优先级来处理冲突。,22.12.2022,54,3.多端口存储器,如果把分布在交叉开关矩阵网络上的控制、转接、优先级仲裁等逻辑功能转移到存储器模块的接口上，就形成了多端口存储器系统，如图5-25所示。这种系统既适合单处理机，也适合于多
30、处理机。,22.12.2022,55,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。,22.12.2022,56,4.多处理机的多级网络,由于开关过于复杂，对于大规模交叉开关用多个小规模交叉开关“串联”和“并联”，组成多级交叉开关网络，以取代单级的大规模交
31、叉开关。,22.12.2022,57,多级互连网络,目标：完成某结点与其它任一结点的连接；,同时完成多对结点的连接。,方法：从时间性和空间性方面开发。,1.循环互连网络（时间性）,组成：DTRin、DTRout、MUX、IN。,结构： 一个单级ICN+MUX。,特点： 节省了设备， 增加了时间， 每个MUX可单独控制。,22.12.2022,58,2.多级互连网络（空间性）,组成：DTRin、DTRout、交换开关、拓扑结构(ICN)。,交换开关：具有传送或播送功能。,拓扑结构：不同级开关间连接方式(单级ICN的连接功能)。,控制方式：级控制、部分级控制、单元控制。,DTRin、DTRout：
32、PE或M，可为同一类型。,22.12.2022,59,分类：根据拓扑结构进行分类,多级立方体网络 多级混洗交换网络 多级PM2I网络,22.12.2022,60,3.多级立方体网络,有STARAN(级控制和部分级控制)和间接二进制n立方体(单元控制)两种网络。,以STARAN网络为例介绍。,返回35页,返回下页,交换开关：二功能（直通和交换）,拓扑结构：第i级为Cubei；,为什么只有三级？,22.12.2022,61,(3)带宽问题,STARAN可同时多对结点连接，尚不能同时任意组合。,(4)例题,例1：编号0F的PE间，要实现下列通信配对：(7,D),(6,C),(5,F),(4,E),(
33、3,9),(2,8),(1,B),(0,A)。画出互连网络结构图，写出控制方式级各开关状态。,答：因需实现双向交换功能，选择STARAN的交换网络(级控制方式）可满足要求。,因共有16个结点，编码需要4位，所以开关共4级。,网络结构图如下页：,返回下页,22.12.2022,62,转上页,拓扑结构：不同级完成地址不同位取反功能。,注意：有交换开关的拓扑结构的实现。,22.12.2022,63,4.多级混洗交换网络（网络）,交换开关：四功能（允许实现一对多的连接）,拓扑结构：不同级相同，均为全混洗结构；,控制方式：级控制、部分级控制、单元控制；,连接图：第n-1级靠近入端；,返回下页,22.12
34、.2022,64,并行存储器无冲突访问,一、访问需求,并行存取向量中各分量信息；,可按行、列、对角线等方法存取(步长不一致)。,二、存在问题,存储器带宽限制存储器带宽达不到向量带宽；,访存方式(步长)不同，产生访存冲突。,三、解决方法,1.采用多体交叉存储器-增加MEM带宽,2.对向量分组操作-解决MEM带宽小于向量带宽问题,22.12.2022,65,多处理机系统结构,并行处理机属SIMD结构，较适合向量处理；,一、多处理机与并行处理机区别,多处理机属MIMD结构，可进行更高层次的并行处理。,1.结构与通用性,SIMD：单指令流系统，并行操作相同，一个CU，控制、数据通讯简单，通用性较差；,
35、MIMD：多指令流系统，并行操作不同，多个CU，控制、数据通讯复杂，通用性较强。,22.12.2022,66,2.程序并行性,SIMD：操作级并行（数据并行）， 识别：隐式识别和向量指令， 支持：编译程序和硬件；,MIMD：任务级并行（数据、功能并行）， 识别：显式指令、编译程序、OS和硬件等， 支持：专用指令，OS对任务的分派和调度。,3.任务派生,SIMD：向量指令表示及控制，隐式并行、效率低；,MIMD：专用指令表示及控制，显式并行、效率高。,22.12.2022,67,三、多处理机结构,1.紧耦合系统(TCS),特点：通过共享主存实现机间通讯。,互连网络：实现PEPEM、PEI/O通道
36、、 PE中断信号间的连接。,22.12.2022,68,2.松耦合系统(LCS),特点：通过消息传送系统实现机间通讯；,每个模块是一个独立的处理机，整个系统可看成是一个分布系统。,互连网络：MTS有总线、环形、多级网络等种类；,结构：有层次和非层次两种结构。,22.12.2022,69,多处理机系统的存储器结构,在多处理机系统中，为了减少访存冲突，主存采用并行存储器结构。多个存储模块可采用低位交叉编址技术，也可采用高位交叉编址技术。能为某处理机进程放置大多数页面的存储器模块称为该处理机宿主存储器，图5-31所示。如果该处理器的现行进程全部活动页面在宿主存储器内，而且该存储器不包含其他处理机的页
37、面，则处理机不会遇到存储冲突。,22.12.2022,70,多处理机系统的存储器结构(cont.),多处理机系统中常采用二维存储器结构，如图5-32所示。有n个同样容量的存储模块，排成l列（体），每一列有m个模块组成。各列之间按高位交叉编址，而列内各模块为按低位交叉编址，每列有一个列控制器连到互联网络。,22.12.2022,71,多处理机系统的cache结构,当每个处理机都有自己专用的cache时，对应主存中某一个单元的数据，在各个cache中可能会出现相应的多个副本，当对其中某一个副本进行一次修改操作，就会产生cache中数据不一致性。无论cache采用“写回法”或“写直接法”，都不能解决
38、多个cache不一致问题。,22.12.2022,72,静态一致性校验,只让该进程的独用信息（指令和操作数据）和共享的只读信息进入本处理机的cache，而对于共享的可写（即可修改）的信息不准进入cache，只可留在主存中。这种方法增加了互联网络和主存的竞争，因此，性能较差。减少竞争的方法是增加一个共享cache-sc（shared cache），共享信息均在sc内，而取指令和独用数据则通过独用cache-pc（private cache），其结构如图5-33所示。,22.12.2022,73,动态一致性校验,基本思想是在若干个cache中使同一个信息（指令、数据）始终保持动态一致。一种方法是广
39、播法：即当每个处理机每次写cache时，不仅写入自己的cache和共享的主存中，而且还把信息送到所有cache，如果其他cache有与自己cache相同的目标行，则也进行改写。,22.12.2022,74,动态一致性校验(cont.),另一种时目录法。在快速ram中构建一个目录表，如图5-34所示。它有两个部分：存在表（present table）是二维的，其中每一项P（i,c）表示第i块是在第c个cache中，修改表（modified table）是一维的，其中每项M（i）表示第i块是否被修改过。在每个cache中还有一个本地标志（可在地址变换表中设立）L（k,c），表示第c个cache中块
40、k的状态。,22.12.2022,75,多处理机系统的特点,1.结构灵活性相比并行处理机的专用性，多处理机系统是要把能并行处理的任务、数组，以及标量都进行并行处理，有较强的通用性。因此多处理机系统要能适应更多样化的算法，具有更灵活的结构，以实现各种复杂的机间互联模式。,22.12.2022,76,多处理机系统的特点(cont.),2.程序并行性在多处理机中，并行性存在于指令外部，即表现在多任务之间。为充分发挥系统通用性的优点，便要利用多种途径：算法、程序语言、编译、操作系统以至指令、硬件等，尽量挖掘各种潜在的并行性。,22.12.2022,77,多处理机系统的特点(cont.),3.并行任务派
41、生多处理机是多指令流操作方式，一个程序当中就存在多个并发的程序段，需要专门的指令来表示它们的并发关系以及控制它们的并发执行，使一个任务正在执行时就能派生可与它并行执行的另一些任务。,22.12.2022,78,多处理机系统的特点(cont.),4.进程同步在多处理机系统里，同一时刻，不同的处理机执行不同的指令。由于执行时间互不相等，它们的工作进度不会也不必保持相同。因此当并发程序之间有数据交往或控制依赖时，就要采取特殊的同步措施，使它们包含的指令相互间仍保持程序要求的正确顺序。,22.12.2022,79,多处理机系统的特点(cont.),5.资源分配和任务调度多处理机执行并发任务，需要处理机
42、的数目没有固定要求，各个处理机进入或退出任务以及所需资源变化的情况都要复杂的多，因此资源分配和任务调度的好坏将直接影响整个系统的效率。,22.12.2022,80,算术表达式的并行算法,并行性的开发在算法。顺序处理机习惯采用循环及迭代算法，往往不适合用于多处理机。而采用直解法，有时能揭示更多的并行性。例如下列多项式 E1=a+bx+cx2+dx3 利用Horner法则，可得到 E1= a+xb+xc+x(d),22.12.2022,81,算术表达式的并行算法(cont.),这是顺序处理的典型算法，共需三个乘一加循环，六级运算，见图5-37（b）所示。它对于多处理并不合适，而采用前一式算法更加有
43、效，只需四级运算即可，见图5-37（a）所示。图中P为所需处理机数目；Tp为运算级数；Sp为加速度，Sp=T1/Tp；EP=Sp/P。可见，Sp1，即运算的加速总是伴随着效率的降低。,22.12.2022,82,算术表达式的并行算法(cont.),从算术表达式最直接的形式出发，利用交换律把相同运算集中在一起，再利用结合律把参加运算的操作数（称原子）配对，尽可能并行运算，最后利用分配律，平衡各分支运算的级数，使总级数减至最少。例如某多项式 E2=a+b(c+def+g)+h需要7级运算。利用交换律和结合律改写为 E2=(a+h)+b(c+g)+def则需5级运算。再利用分配律，将上式改写为 E2
44、=(a+h)+(bc+bg)+ddef则仅需4级运算。如图5-38所示。,22.12.2022,83,机间互连形式,1.总线形式 （时间分配） 最常见,PE、PEM、I/O通道均连在总线上，采用分时或多路转换技术实现数据传递，是最简单的连接方式。,总线仲裁算法：静态优先级算法、平等算法、动态优先级算法、先来先服务算法等。,对外设一般采用优先级算法；对PE采用均等算法。,实现方法：,集中式：由总线控制器控制；,分布式：中机构分散到各PE中。,提高总线效率方法：,改善传输介质和增加总线数量。,总线互连方式不适宜连接过多的处理机。,22.12.2022,84,2.交叉开关形式 （空间分配）,是总线形
45、式的极端，总线数=PE数+PEM数+I/O通道数，是一种全相联形式，控制、仲裁、转换机构均在开关中。,改进：用一系列较小开关串联或并联，形成多级交叉开关，减少其复杂性。,交叉开关方式不适宜连接过多的处理机。,3.多端口存储器形式,将控制、仲裁、转换机构移到存储器中。,每个端口与一个PE或I/O通道相连。,多端口存储器形式不适宜连接过多的处理机。,22.12.2022,85,4.多级互连网络形式,是介于总线(N)与交叉开关(N2) 中间的一种(Nlog2N)。,对互连网络I与O数不一致时，可采用榕树形网络。,多级互连网络适宜于PE数较多的系统。,ab交叉开关,a入b出，输入基于a编码，输出基于b
46、编码。,入端出端受阻后，重新申请，性能受建立时间限制；设置缓冲器性能有所改善，适合于包交换网络。,anbn互连网络,交叉开关为ab开关，由n级构成。,比较：交叉开关时结点数为anbn，多级互连网络时结点数为abn2，明显降低了复杂性。,22.12.2022,86,程序并行性的分析,并行性的关键在算法。研究并行算法及程序设计，一直是多处理机系统的一个重要研究课题。 其中相关问题是十分重要和难以解决的问题之一。,22.12.2022,87,数据相关举例,假设有一个程序包含P1、P2、P3、. Pi、. pj、.、Pn等多个程序段，取最简单的形式：Pi和Pj都是一条语句，Pi在Pj之前执行，且只讨论
47、Pi和Pj的直接相关关系。一般而言，Pi和Pj之间存在三种可能的数据相关情况。,22.12.2022,88,数据相关举例（cont.）,（1）如果Pi的左部变量也在Pj的右部变量集内，且Pj要从Pi取出算出的值，称“Pj数据相关”于Pi。如 P1 A=B+C P2 C=A*E P2必须取P1算得的A值作为操作数。,22.12.2022,89,数据相关举例（cont.）,（2）如果Pj的左部变量也在Pi的左部变量集内,则称“Pi数据反相关”于Pj。如 P1 C=A*E P2 A=B+D 在P1未取用A值之前，A的值不能被P2所改变。,22.12.2022,90,数据相关举例（cont.）,（3）
48、如果Pi的左部变量也在Pj的左部变量，则称“Pj数据数相关”于Pi。如 P1 A=B+D P2 A=A+C P2存入它自己算得的值必须在P1存入之后。,22.12.2022,91,3.数据相关避免,主要解决反相关和输出相关，由编译程序自动完成。,重命名方法：,S：A=B+C T：D=A+E U：A=A+D V：IF X0 THEN G=F+A,U：AA=A+DV：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(
49、i)=B(i) when b(i); X(i)=C(i) when not b(i); D(i)=X(i)+1;,存在数据相关、反相关、输出相关、控制相关。,消除了数据反相关、输出相关。,消除反相关、输出相关,22.12.2022,92,二、并行程序设计语言,1.开发方式,语言形成方式：扩充语言功能、重新设计并行语言,对语言的要求：灵活性、效率,程序设计方式：显式、隐式,2.扩展语言中三种并行结构,FORK-JOIN：不同机器有不同形式，效果相同,FORK A： 派生一个进程，当前进程继续，,FORK A,J： FORK A功能外，地址J计数器+1，,FORK A,J,N：FORK A功能外，
50、地址J计数器值为N；,JOIN J： 地址J处计数器减1，当计数器值为零时，启动J+1处进程，否则，结束该进程，释放PE。,22.12.2022,93,描述程序并行性的指令,并行程序的执行是一个不断地进行并行性任务的派生和汇合的过程。派生是在一个任务执行的同时，派生出可与它并行的一个或多个任务，分配给不同的处理机完成。这些任务可以是互不相同的，执行时间也不一样，要等它们全部完成以后在汇合起来，进入后继任务。后继任务可以是单任务，也可以是新的并行任务。若是并行任务，则又开始派生和汇合过程。依次类推，直至整个程序结束。,22.12.2022,94,派生指令FORK,指令格式:FORK A功 能 ：
