计算机系统结构课件：第五章 并行处理技术

1、二、 并行处理技术的发展,三、 阵列处理机原理,四、 互连网络,五、 多处理机,一、并行处理技术的 概述,第五章 并行处理机和多处理机,一.并行性概念 在数值计算，数据处理，信息处理或人工智能求解过程中，可能存在某些能同时进行运算或操作的部分。 在同一时刻或同一时间间隔内完成多个性质相同或不同的任务。,同时性（simultaneity）:指两个或多个事件在同一时 刻发生在多个资源中。 并发性（concurrency）:指两个或多个事件在同一时 间间隔内发生在多个资源中。,并行处理技术涉及： 并行结构、并行软件、并行算法等多个方面。,一、并行处理技术概述,第五章 并行处理机和多处理机,1从计算机

2、系统处理数据的并行性来看，并行性等级从低到 高可分： 位串字串-通常指传统的串行单处理机。 位并字串-通常指传统的并行单处理机。 字并位串-同时对多个字的同一位（称位片）进行处理 ，开始进入并行处理领域。 全并行-同时对多个字的全部或部分位组进行处理。,2从计算机信息加工步骤和阶段看，并行性等级可分为： 存储器操作并行-并行存储器系统和以相联存储器为核心构成的相联处理机。,二. 并行的等级和分类,处理器操作步骤并行-可以是一条指令的取指、分析、执行等操作步骤，也可以是具体运算，如流水计算机。,第五章 并行处理机和多处理机,并行性的开发还可以按程序大小划分不同粒度的开发方式。 并行粒度（gran

3、ularity）或颗粒规模（grain size）- 衡量软件进程所含计算量的尺度。测量方法是数一下颗粒（程序段）中的指令数目。一般用细、中、粗来描述，决定并行处理的基本程序段。,3. 程序划分和粒度,并行性粒度：每次并行处理的规模大小。用字母G表示 G=TW/TC TW：所有处理器进行计算的时间总和； TC：所有处理器进行通信的时间总和。（设系统共有P个处理器） 当TC较大时，通信量大，则G较小处理粒度较细。反之对于粗粒度的并行，通信量较小。,处理器操作并行-为支持向量、数组运算，可以通过重复设置处理单元进行，如并行处理机,指令、任务、作业并行-较高级并行，属于MIMD计算机。,第五章 并行

4、处理机和多处理机,时延（TC ）机器各子系统间通信开销的时间量度。如：存贮时延是处理机访问存贮器所需时间；同步时延是两台处理机互相同步所需的时间。,通信时延问题：计算机中不同的时延是由机器内部系统结构，实现技术和通信方式决定。系统结构和实现技术将会影响子系统间容许时延的选择。可以用平衡粒度和时延的办法来求得较好的计算机系统性能。,处理机间通信引起的时延：除数据通路中的信号延迟外，还受到通信方式的影响。一般情况下n个处理任务互相通信时，它们之间需有n（n-1）/2 条通信链路。由此看出复杂性是以平方关系增长，这将限制大型计算机系统中允许使用的处理机数量。,第五章 并行处理机和多处理机,现代计算机

5、程序运行并行性级别,五种程序执行级别体现了不同的算法粒度规模以及通信和控制要求的变化。级别越低，软件进程的粒度越细。一般情况，程序可在这些级别的组合状态下运行。,第五章 并行处理机和多处理机,（1）指令级：并行性发生在指令内部微操作之间或指令之间。取决于程序的具体情况。可借助于优化编译器开发细粒度并行性，它能自动检测并行性并将源代码换成运行时系统能识别的并行形式。,（2）循环级：相当于迭代循环操作，典型循环包含的指令大约几百条，循环级并行性是并行机或向量计算机上运行的最优程序结构，并行处理主要由编译器在循环级中进行开发。,（3）子任务级：属于中粒度。子程序是在单处理机或多处理机的多道程序设计这

6、一级进行的。这一级并行性由算法设计者或程序员开发而非用编译器开发。,（4）任务级：这是与任务、过程、程序段、协同程序级相对应的中粒度或粗粒度规模。典型粒度包含的指令几千条，检测本级的并行性比细粒度级困难得多，需要更多地涉及过程间的相关性分析。需编译器支持。,（5）作业（程序）级：对于少量几台高性能处理机构成的超级计算机开发这种粗粒度并行性切实可行。,第五章 并行处理机和多处理机,小结： 细粒度并行性常在指令级或循环级上借助于并行化或向量化编译器来进行开发的。 任务或作业步骤（过程级）中粒度并行性开发需要程序员和编译器的共同作用。 开发程序作业级的粗粒度并行性主要取决于高效的操作系统和所用算法的

7、效率。 共享变量通信常用于支持中、细粒度计算。消息传递型多计算机用于中粒度和粗粒度的计算。通常情况下，粒度越细，并行性潜力越大，通信和调度的开销也越大。细粒度能提供较高的并行度，但与粗粒度计算相比，其通信开销也较大。大规模并行性通常是在细粒度级上开发。如：SIMD或MIMD计算机上开发的数据并行性。,第五章 并行处理机和多处理机,提高计算机系统的并行性的技术途径： 时间重叠（Time Interleaving）：在并行性概念中引入时间因素。让多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度。,资源重复（Resource Replication）：并

8、行性概念中引入空间因素。通过重复设置的硬件资源来提高系统可靠性或性能。例如，通过使用两台或多台完全相同的计算机完成同样的任务来提高可靠性。,资源共享（Resource Sharing）：利用软件的方法让多个用户按一定时间顺序轮流地使用同一套资源，以提高其利用率，这样相应地提高整个系统的性能。例如多道程序分时系统.,二、 并行处理技术发展,第五章 并行处理机和多处理机,并行处理技术发展,第五章 并行处理机和多处理机,并行处理中需研究的课题： （1）在处理机数目很多的情况下，要把任何一个问题分成足够多的并行过程（即任务分配）非常困难，并且也不是所有问题都能做到这一点。 （2）现有的并行算法绝大多数

9、是由串行算法发展而来的，因此很难摆脱传统串行的思维和处理方式方法的约束。 （3）现有算法语言对并行性限制很大。现行的SIMD和MIMD系统结构仍然没有摆脱传统的以指令流为主导的Von Neumann模式。因指令相关和地址空间相关等矛盾的出现，使并行效率受到严重的限制。 （4）在并行处理过程中，各处理机间的通信开销有可能使并行处理技术得不偿失。 （5）并行处理技术的主要困难是软件，软件的关键在于如何高效地进行存储管理和机间通信，尤其是并行编译程序发展，对发挥硬件特性改善系统性能影响更大。,第五章 并行处理机和多处理机,一、阵列处理机的基本构成 基本思路：阵列处理机是通过重复设置大量相同的处理单元

10、PE，将它们按一定的方式互连，在统一的控制部件CU（Control Unit）控制下，对各自分配来的不同数据并行地完成同一条指令所规定的操作。它依靠操作一级的并行处理来提高系统的速度。,阵列处理机的控制部件中进行的是单指令流，因此与高性能单处理机一样，指令基本上是串行执行，最多加上使用指令重叠或流水线的方式工作。 指令重叠是将指令分成两类，把只适合串行处理的控制和标量类指令留给控制部件自己执行，而把适合于并行处理的向量类指令播送到所有处理单元，控制让处于活跃的那些处理单元去并行执行。因此这是一种标量控制类指令和向量类指令的重叠执行。,三、 阵列处理机的原理,第五章 并行处理机和多处理机,二 、

11、阵列处理机分类,阵列处理机根据存贮器采用的组成方式不同分成两种基本构成。 （1）分布存贮的阵列处理机 各个处理单元设有局部存贮器存放分布式数据，只能被本处理单元直接访问。此种局部存贮器称为处理单元存贮器（Processing Element Memory）PEM。在控制部件CU内设有一个用来存放程序的主存贮器CUM。整个系统在CU统一控制下运行系统程序的用户程序。执行主存中的用户程序指令播送给各个PE，控制PE并行地执行。,特点：处理器阵列一般是通过CU接到一台管理处理机SC上，SC一般是一种通用计算机，用于管理整个系统的全部资源，完成系统维护、输入输出、用户程序的汇编及向量化编译、作业调度、

12、存贮分配、设备管理、文件管理等操作系统的功能。,第五章 并行处理机和多处理机,分布存贮器阵列处理机结构,第五章 并行处理机和多处理机,ILLIAC-IV 结构 （分布存贮器并行处理机结构）,处理单元阵列 由64个结构完全相同的处理单元PEi 构成，每个处理单元PEi字长64位，PEMi为隶属于PEi的局部存储器，每个存储器有2K字，全部PEi由CU统一管理，PEi都有一根方式位线，用来向CU传送每个PEi的方式寄存器D中的方式位，使CU能了解各PEi的状态是否活动，作为控制它们工作的依据。,第五章 并行处理机和多处理机,ILLIAC-IV的处理单元原理图,第五章 并行处理机和多处理机,第五章

13、并行处理机和多处理机,ILLIAC-IV的处理单元互连图,将PU63传送到PU10，最快可经PU63PU7PU8PU9PU10。,第五章 并行处理机和多处理机,控制器的功能有以下五个方面： 对指令流进行控制和译码，包括执行一整套标量操作指令； 向各处理单元发出执行数组操作指令所需的控制信号； 产生和向所有处理单元广播的公共的地址部分； 产生和向所有处理单元广播的公共数据； 接收和处理由各PE（计算出错时）、系统I/O操作以及B6700所生产的陷阱中断信号。,阵列控制器 除了对阵列的处理单元实行控制以外，还能利用本身的内部资源执行一整套指令，用以完成标量操作，在时间上与各PE的数组操作重叠起来。

14、,第五章 并行处理机和多处理机,I/O系统 由磁盘文件系统DFS、I/O分系统和B6700组成， 完成输入输出及其他管理功能。,ILLIAC-IV系统的操作系统，连同编译程序、汇编程序、输入输出服务子程序等都驻留在宿主机B6700中，处理单元阵列就像是宿主机的一台专门作向量处理的后端机。或者说宿主机是处理单元阵列的一台输入输出处理机。,第五章 并行处理机和多处理机,（2）集中式共享存贮的阵列处理机 特点：每个PE没有局部存储器，存储模块以集中形式为所有PE共享，互连网络ICN受CU控制。,具有共享存贮器阵列处理机结构,KN,互连网络ICN的作用不同,第五章 并行处理机和多处理机,BSP的五级数

15、据流水线构图 （集中式共享存贮器）,（1）并行处理机 （2）控制处理器 （3）文件存储器 （4）对准网络 （5）BSP的五级 数据流水线,示例：Burroughs公司与依里诺大学联合研制的科学处理机BSP（Burroughs Scientific Processor）,第五章 并行处理机和多处理机,作用： （1）由17个存储器模块并行读出16个操作数； （2）经对准网络NW1将16个操作数重新排列成16个处理单元所需要的次 序； （3）将排列好的16个操作送到并行处理单元完成操作； （4）所得的16个结果经过对准网络NW2重新排列成17个存储器模块所需要的次序； （5）写入存储器；,第五章 并

16、行处理机和多处理机,共同特点：可以通过各种途径把它们转化成为对数组或向量的处理，利用多个处理单元对向量或数组所包含的各个分量同时进行运算，从而易于获得很高的处理速度。,三阵列处理机的特点,并行处理机有如下特点： （1）利用资源重复（空间因素）而非时间重叠。 （2）利用同时性而非并发性。 （3）提高运算速度主要是靠增大处理单元个数，比起向量流水线处理机主要依靠缩短时钟周期来说，速度提高的潜力要大得多。 （4）使用简单而又规整的互连网络来确定多个处理单元之间的连接模式。 （5）并行处理机（阵列机）研究必须与并行算法研究密切结合，使之适应性更强，应用面更广。,第五章 并行处理机和多处理机,概念：一种

17、由开关元件，按照一定的拓扑结构和控制方式构成的，用来实 现计算机系统内部的多个功能部件或者是多个处理机之间的相互连接。,MIMD 计算机,SIMD 计算机,四、 互连网络,第五章 并行处理机和多处理机,第五章 并行处理机和多处理机,互连网络的特性,网络规模：网络中结点数。 结点度：与结点相连接的边（即链路或通道）数，用d表示。结点度是入度、出度之和。,距离： 两结点之间相连的最少边数。 网络直径：它是网络中任意两个结点之间距离的最大值。 等分宽度：某一网络被切成相等的两半时，沿切口的最小边数（通道），用b表示。 结点间的线长：两个结点间线的长度。 对称性：从任何结点看拓扑结构都是一样。对称网络

18、较易实现，编程也较容易。,第五章 并行处理机和多处理机,机器A 机器B 连接两台计算机的简单网络,一台机器发送消息给另一台机器时，发送方的步骤如下： （1） 应用程序把要发送的数据拷贝到操作系统的缓冲区。 （2） 操作系统根据要发送的数据计算出检查和，并把它加在消息中，同时启动超时计数器。 （3） 操作系统把缓冲区中的数据送到网络接口硬件并通知硬件开始发送消息。,第五章 并行处理机和多处理机,消息包的接收步骤： （1） 系统把数据从网络接口硬件数据拷贝到操作系统缓冲区。 （2） 系统根据接收到的数据计算出检查和。 （3） 如果数据通过检查，系统把接收到的数据拷贝到用户地址空间并启动应用程序继续

19、执行。,第五章 并行处理机和多处理机,发送方 开销（5） 传输时间（2） 发送方 “飞行”时间（3） 传输时间 接收方开销（6） 接收方 传输时延（4） 总时延,互连网络的传输性能参数,传输时延=“飞行”时间+传输时间 一个消息的总时延 = 发送方开销 + “飞行”时间 + 消息长度/频宽（1） +接收方开销,第五章 并行处理机和多处理机,概念：表示互连网络的出端号和入端号的一一对应关系。,作用： 对于所有的0iN-1，同时存在入端j连至出端f（j）的对应关系。 当互连函数用来实现处理机之间数据变换时，互连函数也反映了网络输入数组与输出数组间对应的排列关系或者置换关系。,互连函数有三种表示法：

20、 输入输出对应表示法 循环表示法 函数表示法,（一） 互联函数,第五章 并行处理机和多处理机,1、输入输出对应表示法 0变换为f(0),1变换为f(1),N-1变换成f(N-1)。 f是互连函数。,2、 循环表示法 f（X0）= X1，f（X1）= X2，f（Xj）= Xj+1， f（Xk-1）= X0，其中Xi为结点编号，这里k为循环长度。,第五章 并行处理机和多处理机,3、 函数表示法 如x：bn-1bn-2bib0，互连函数对应地表示为f（bn-1bn-2bib0）。 例如交换置换： E（ bn-1bn-2bib0 ）= bn-1bn-2bib0 它表示实现二进制地址编号中第0位位值不同

21、的输入端和输出端之间连接。,第五章 并行处理机和多处理机,几种基本的互连函数,用N表示节点数目，当用二进制表示这些节点号时，将用n 位二进制数表示，其中 n=log2N。,1、 恒等置换 相同编号的输入端与输出端一一对应互连所实现的置换即为恒等置换，其表达式为： I（Xn-1Xn-2X1X0）= Xn-1Xn-2X1X0 其中等式左边括号内的Xn-1Xn-2X1X0和等式右边的Xn-1Xn-2X1X0均为网络输入端和输出端的二进制地址编号。,第五章 并行处理机和多处理机,2、 交换置换 交换置换是实现二进制地址编号中第0位位值不同的输入端和输出端之间的连接。其表达式为： E（ Xn-1Xn-2

22、X1X0 ）= Xn-1Xn-2X1X0,第五章 并行处理机和多处理机,第五章 并行处理机和多处理机,第五章 并行处理机和多处理机,4、 均匀洗牌置换 将输入端分成数目相等的两半，前一半和后一半按序一个隔一个地从头至尾依次与输出端相连，其函数关系可表示为：,第五章 并行处理机和多处理机,第五章 并行处理机和多处理机,5.蝶式置换（Butterfly） 被定义为： （Xn-1Xn-2X1X0）= X0Xn-2X1 Xn-1,子蝶式（subbutterfly）(k) 置换： (K)(Xn-1Xn-2 Xk+1XkXk-1X1X0） = Xn-1Xn-2 Xk+1X0Xk-1X1Xk 超蝶式置换(k

23、) : (k) (Xn-1Xn-2 Xn-kXn-k-1X1X0） = X n-k-1Xn-2Xn-kXn-1Xn-k-2 X1 X0,第五章 并行处理机和多处理机,(a)=置换 （b）(1)=(1)置换 （c） (1)=(1)置换 N=8的蝶式置换,第五章 并行处理机和多处理机,6、移数置换 将输入端数组循环移动一定的位置向输出端传输。其函数表达式无需用二进制编号来写，可表达如下： a(X)=(X+k) mod N, 0X N k为常数，指移动的位置值。,第五章 并行处理机和多处理机,7、 加减2i（PM2I）置换 加减2i 置换实际上是一种移数置换包含2n个互连函数，其表达式为 PM2+i

24、（j）=j+2 i （mod N） PM2-i（j）=j-2 i （mod N） 式中，0jN-1，0in-1，n=log2N,第五章 并行处理机和多处理机,（二） 互联网结构,第五章 并行处理机和多处理机,三个单级互连网（以N=8为例）,立方体网,立方体单级网循环表示为： Cube0：（0 1）（2 3）（4 5）（6 7） Cube1：（0 2）（1 3）（4 6）（5 7） Cube2：（0 4）（1 5）（2 6）（3 7）,第五章 并行处理机和多处理机,第五章 并行处理机和多处理机,PM2I单级互联网,PM2I单级网结点间的互连函数关系为加减2i 置换, 对于N=8，PM2I单级网共

25、有2*3=6个互连函数，循环表示为： PM2+0：（0 1 2 3 4 5 6 7） PM2-0：（7 6 5 4 3 2 1 0） PM2+1：（0 2 4 6）（1 3 5 7） PM2-1：（6 4 2 0）（7 5 3 1） PM22：（0 4）（1 5）（2 6）（3 7）,第五章 并行处理机和多处理机,PM2+1 0 1 2 3 4 5 6 7,PM22 0 1 2 3 4 5 6 7,PM2I互连网连接图,第五章 并行处理机和多处理机,混洗交换单级互联网络,全混洗（Perfect shuffle）、交换（Exchange）,全混洗交换单级网,第五章 并行处理机和多处理机,基本的循

26、环互连网和多级互连网,循环互连网：将同一套单级互连网循环使用，组成循环互连网络.,传送 寄存器,多路开关,第五章 并行处理机和多处理机,多级互连网：将多套单级互连网串联使用，组成多级互连网。,优点: 缩短了通过时间而提高了速度; 可以利用各种单级互连网络进行不同的组合，产生具有各种特性和连接模式的多级互连网络，灵活性较好。,缺点: 增加了设备和成本。,第五章 并行处理机和多处理机,最基本的多级互连网络：多级立方体互连网络，多级混洗交换网络和PM2I网络。 实现各种多级网络的区别：所用开关模块、控制方式和拓扑结构（级间连接模式）三个因素不同。,直连 交换,上播 下播,22交叉开关连接模式,开关模

27、块,i j,i j,i j,i j,i j,i j,i j,i j,第五章 并行处理机和多处理机,控制方式：是对各个开关模块进行控制的方式。,拓扑结构：指各级之间出端和入端相互连接的规则或连接模式。,级控制-每一级的所有开关只用一个控制信号控制，同时只能处于同一种状态； 单元控制-每一个开关都有自己单独的控制信号控制，可各自处于不同的状态； 部分级控制-第i级的所有开关分别用i+1个信号控制，0in-1，n为级数。,第五章 并行处理机和多处理机,多级立方体网,特点：第i级（0in-1）控制信号为“1”时，处于交换状态，实现的是cube i 互连函数，当该信号为“0”时，相应单元处于直连状态代码

28、不变，它们都采用两个功能（直接、交换）的交换单元。常用的多级立方体网有STARAN网，间接二进制n方体网等。,交换网络：级控 移数网络：部分级控,第五章 并行处理机和多处理机,三级STARAN交换网络实现的入出端连接,第五章 并行处理机和多处理机,多级混洗交换网络,又称omega网络，由n级相同的网络组成，每一级都包含一个全混拓扑和随后一列2n-1个四功能交换单元，（直连、交换、上播、下播），采用单元控制方式。,第五章 并行处理机和多处理机,多级PM2I互连网又称为数据交换网; 其中N=8，n=log2N=3各级中的处理单元按PM2I互连函数关系连接起来。 第0级、第一级、第二级完成的都是PM

29、2I。 网络中提供了冗余通路，提高了可靠性。,多级PM2I互连网,STARAN网络和omega网络都是为了进行存储器与处理器之间的数据交换，间接二进制n方体网络是为了连接成微处理器阵列。,第五章 并行处理机和多处理机,互连网络的设计特性,计算机中，衡量互连网络性能好坏的主要因素是它的连接度、延时性、带宽、可靠性和成本。,连接度：指一个结点与其他结点的连接程度。如果一个结点直接连接的其他结点数越多，连接度就越高，表明连接性越好。 延时性：指从一个结点传送信息到任何另一个结点所需的时间。通常可用结点间最大距离加以表示。,第五章 并行处理机和多处理机,1、 通信工作方式 通信工作方式可分为同步和异步

30、两种。 2、 控制策略 控制策略分为集中和分散两种。 3、 交换方式 交换方式分为线路交换和分组交换两种。 4、 网络拓扑 网络拓扑分为静态和动态两种。这里的拓扑是指互连网络中的各个结点间连接关系，通常用图来描述。,互连网络设计的四个特征,第五章 并行处理机和多处理机,网络拓扑结构,静态网络常用来实现集中式系统的多系统之间或分布式系统的多个计算机结点间固定连接。它一旦构成后就固定不变。,1 静态互连网络,第五章 并行处理机和多处理机,第五章 并行处理机和多处理机,各种互连网主要性能比较,第五章 并行处理机和多处理机,2 动态互连网,根据程序要求实现所有的通信模式； 通常紧耦合多处理机系统的互连

31、网络采用动态拓扑结构； 不用固定连接，而是沿着连接通路使用开关与仲裁器以提供动态连接特性，实现所要求的通讯模式； 按照价格和性能增加的顺序，动态连接网络分为总线系统，多端口存储器，交叉开关和多处理机的多级网络等。,第五章 并行处理机和多处理机,1、多处理机概念 一种系统构造方式; 多个处理机共享主存或输入输出的子系统; 统一操作系统控制或受各自独立操作系统; 实现作业，任务级甚至指令级间并行。,五、 多处理机,第五章 并行处理机和多处理机,（一） 多处理机硬件结构,2 、 多处理机特点,具有更大的灵活性和更强的通用性。 主要开发高层次作业及任务级（粗粒性）并行性。 并行任务的派生需要用显式的专

32、用语句或指令加以表示。 并发执行的进程间的同步需要采取特殊措施，以保证程序 原来的正确语义。 对资源分配和任务分配要进行良好的调度。 MIMD系统在执行条件语句时比SIMD系统有较高的效率。 MIMD的异步特性使得它在执行一串完成时间可变的指令时，比SIMD有更快的速率。,第五章 并行处理机和多处理机,（a）共享存储型,3、两种多处理机结构,第五章 并行处理机和多处理机,（1）共享存储型（紧耦合系统） 特点： 1）多处理机系统中，多个处理器、高速缓存（cache）一般利用公 共总线实现互连。 2）通过共享主存实现处理机间的相互通信，相互间的联系比较紧密。 3）所有处理机共享I/O设备或通过通道

33、和外设相连，整个系统有统一的操作系统管理，提供处理机及程序之间的作业、任务、文件、数据各个级别上的相互联系。,按系统所用的处理机结构类型是否相同及操作功能是否对称，可分为： 同构对称型多机系统 异构非对称型多机系统。,第五章 并行处理机和多处理机,UMA多处理机模型,三种模型 （按存取方式） 1）均匀存储器存取(Uniform-Memory-Access）UMA 2）非均匀存储器存取（Nonuniform-Memory-Access）NUMA 3）高速缓存存储结构（Cache-Only-Memory Architecture） COMA模型,第五章 并行处理机和多处理机,（a） NUMA共享本

34、地存储器（如BBN Butterfly）,多处理机系统的两种NUMA模型,第五章 并行处理机和多处理机,第五章 并行处理机和多处理机,多处理机的COMA模型,第五章 并行处理机和多处理机,（2）分布存储型（松散耦合的多处理机系统 ）,层次式和非层次式两种,第五章 并行处理机和多处理机,Cmn层次式多机系统,第五章 并行处理机和多处理机,总线结构：把所有功能模块（或部件、或计算机）连接到一条公共通信通路上，又称为分时或公共总线。,机间互连形式,第五章 并行处理机和多处理机,采用总线结构的多处理机系统,优点： （1）系统硬件成本最低且最简单，每个处理机的物理 接口、寻址、判优和分时逻辑线路与单处理

35、机系统相同。 （2）通过增、删功能模块可方便地改变系统硬件配置。,缺点： （1）全部存贮访问都要经过总线，所以全系统的速度 受到总线工作周期的限制，带宽窄，可连接的处理机数少。 （2）系统以增加模块方式进行扩充会降低整个系统的 吞吐率； （3）这种互联方式其可靠性差，系统效率较低。,第五章 并行处理机和多处理机,常用的仲裁算法,静态优先级算法：为每个连到总线上的处理机（或计算机模块）分配一个唯一的固定优先级。 优点：算法简单，易实现。 缺点：优先级低的处理机将很少有机会使用总线。,平等算法：以轮转方式将总线按固定大小的时间片依次供各处理机使用，常用于同步总线。 优点：算法较简单且能保证各处理机

36、有均等机会使用总线。 缺点：平均等待时间较长。,第五章 并行处理机和多处理机,动态优先级算法：根据总线使用情况和相应规则，能动态地改变连接到总线上的多处理机的优先级。 优点：兼顾了前两种算法的优点，即有较短的平均等待时间,并可使系统中的各处理机有均等机会使用总线。 缺点：控制逻辑较为复杂。,先来先服务算法：不是按优先级选择主控器。 优点：具有最好的均等性，该算法是性能最好的仲裁算法。 缺点：实现困难。该算法的作用只提供一种标准以衡量其他算法好坏。,第五章 并行处理机和多处理机,交叉开关网络 包含一组纵横开关阵列，把纵向的处理机P及I/O通道与横向的存储器模块M连接起来，使每个处理器都有有它单独

37、可用的通路与存储器模块相连，这样可以加大频带宽度，每个交叉点都有开关、多路控制转换及仲裁部件。,第五章 并行处理机和多处理机,特点： （1） 互连系统最复杂，潜在的总通信速率最高； （2） 控制和切换逻辑在开关内部，所以功能模块最简单且最便宜； （3） 任何功能模块要装配到系统中都需要使用一个基本开关矩阵，所以面向多处理机才会能使性能价格比趋于合理。 （4） 系统扩充会提高整个系统性能，而且不必重写操作系统，有最高的系统潜在效率。 （5） 从理论上讲，系统扩充只受开关矩阵大小限制，而开关矩阵的设计和控制可采用模块化方式予以扩展。 （6） 开关内部采用与/或的冗余方法提高了开关的可靠性，因此，也

38、就提高了系统的可靠性。,对于分布存储的松散耦合方式的大规模并行多处理机系统可采用纵横交叉开关实现互连。,第五章 并行处理机和多处理机,多端口存储器互连方式 每个存贮器模块有多个存取端口，将分布在交叉开关矩阵中的控制，转换和优先级仲裁逻辑分别移到相应存贮器模块的接口中，构成多端口存贮器的结构。,四端口存储器形式的结构,第五章 并行处理机和多处理机,优点： （1） 比较简单。 （2） 传送速率可以较高。 （3） 增加安全性，防止无权使用的用户访问，还可以保护存放在存贮器 中的重要程序不被其它处理机修改破坏。 缺点：比总线结构复杂，在存贮器系统中要增加很多硬件。,第五章 并行处理机和多处理机,多级互

39、连网 MIMD和SIMD计算机都使用多级网络。每一级都用了多个ab开关，相邻各级开关之间都有固定的级间连接。为了在输入和输出之间建立所需的连接，可用动态设置开关的状态来实现。,各种多级网络的区别就在于所用开关模块、控制方式和级间连接（ISC）模式的不同。最简单的开关模块是22开关。前面介绍的有立方体多级网，多级混洗交换网等。这些交叉开关在处理机时比较复杂，可采用改进的方法，即把多个较小规模交叉开关“串联”和“并联”，组成多级交叉开关网络。,第五章 并行处理机和多处理机,单处理机：cache一致性问题只存在于cache与主存之间，即使有I/O通道共享cache亦可通过全写法或回写法较好地加以解决； 多处理机：由于每一个处理机都有一个cache，因此在写操作时，必须保证各cache之间的数据一致性。,导致多处理机系统中cache内容不一致的因素有三个： （1）可写数据的共享。 （2）输入输出活动。 （3）进程迁移。,（二） 多处理机cache一致性,第五章 并行处理机和多处理机,解决多处理机CACHE一致性的方法,监视cache协议法（snoopy cache protoco