计算机系统机构-ppt-第9章课件

《计算机系统机构-ppt-第9章课件》由会员分享，可在线阅读，更多相关《计算机系统机构-ppt-第9章课件（93页珍藏版）》请在金锄头文库上搜索。

1、1,计算机系统结构,第一章 基本概念 第二章 指令系统 第三章 存储系统 第四章 输入输出系统 第五章 标量处理机 第六章 向量处理机 第七章 互连网络 第八章 并行处理机 第九章 多处理机,2,第九章 多处理机,多处理机系统 两个或两个以上处理机(包括PE和CU)， 通过高速互连网络连接起来， 在统一的操作系统管理下， 实现指令以上级(任务级、作业级)并行 按照Flynn分类法，多处理机系统属于MIMD计算机 多处理机系统由多个独立的处理机组成 每个处理机都能够独立执行自己的程序,3,9.1 多处理机结构,流水线机器： 流水线机器通过几级流水的同时操作来获得高性能 连续计算机器： 连续计算的

2、机器由多台处理机组成，每台处理机执行相同的程序 前几章讨论了如何加快单指令流执行速度的方法 尽管只有一个程序在执行,前面讨论过的技术可以进一步开发单条指令流内部的指令并行性 本章讨论多处理机-由若干立的处理机组成的系统 器件本身的物理条件限制了任何单处理机的速度最高不能超过某个上界值 欲达到超过这个上界值的速度就必须采用其它的方法 本章通过研究多处理机系统来实现这个目的 本章的中心议题是多处理机的结构和性能 介绍如何把多台处理机组成高并行度的系统 深入分析这类系统的瓶颈和改进性能的方法,4,9.1.1a 松散偶合多处理机,处理机之间的连接频带比较低 通过输入输出接口连接,处理机间互为外围设备进

3、行连接 如IBM公司的机器，都可以通过通道到通道的连接器CTC把两个不同计算机系统的IOP连接起来 通过并口或串口把多台计算机连接起来 如用串行口加一个MODEL拨号上网 也可以直接连接 多台计算机之间的连接需要有多个接口 通过Ethernet网络接口连接多台计算机 速度达10Mb、100Mb、1Gb Mynet已经达到1.28Gb和2.56Gb 当通信速度要求更高时，可通过一个通道和仲裁开关CAS(Channel and Arbiter Switch)直接在存储器总线之间建立连接 在CAS中有一个高速的通信缓冲存储器,5,通过多输入输出输出口连接的多处理机,6,通过消息传送系统连接的松散耦合

4、多处理机,7,9.1.1b 紧密偶合多处理机,处理机之间共享主存储器，通过高速总线或高速开关连接 主存储器有多个独立的存储模块 每个CPU能够访问任意一个存储器模块 通过映象部件MAP把全局逻辑地址变换成局部物理地址 通过互连网络寻找合适的路径，并分解访问存储器的冲突 多个输入输出处理机IOP也连接在互连网络上，I/O设备与CPU共享主存储器 处理机个数不能太多，几个到十几个 紧密偶合方式要求有很高通信频带。 可以采用如下措施 (1) 采用高速互连网络 (2) 增加存储器模块个数，一般nm，取12倍之间 (3) 每个存储器模块再分成多个小模块，并采用流水线方式工作 (4) 每个CPU都有自己的

5、局部存储器LM (5) 每个CPU设置一个Cache,8,紧密耦合多处理机模型,9,带二维共享存储器、局部Cache及存储器的多处理机,10,多处理机在结构原理上区别于并行处理机的主要特点,(1)多处理机有多个控制器 有多个指令部件，对各个PE实现单独的控制，而又相互协调配合。 (2)多处理机的外围设备要能够被多个PE分别调用， 通过互连网络转接 并行处理机的外围设备统一访问主存储器进行程序和数组的有规则的传送。,11,多处理机在结构原理上区别于并行处理机的主要特点,(3)并行处理机由于主要完成数组向量运算，它的PE和MM之间的数据交往是比较有规则的，存储器访问的地址变换功能要求不高，因而互连

6、网络的作用主要放在数据对准上，可以做得比较简单 多处理机由于互连网络必须满足各个PE随机地访问主存储器的要求 连接模式、频带和路径选择等问题都要复杂得多 存储映射部件对每一个PE也是必需的 多处理机系统中存储器的数据和存储空间都要被多个处理机共享 不能允许每一个PE在运行自己的程序段时直接产生物理地址 要利用存储映射部件来满足存储器动态分配和处理机共享数据块的需要,12,9.1.2 多处理机系统的特点,1、结构灵活 并行处理机：专用，PE数很多(几千个)，固定有限的通信 多处理机：通用，几十个，高速灵活的通信 2、程序并行性 并行处理机的并行性存在于指令内部，识别比较容易 多处理机的并行性存在

7、于指令外部，在多个任务之间，识别难度较大 一个简单的例子 Y = A+B*C*D/E+F 用两个处理机 CPU1 CPU2 B*C D/E A+F B*C*D/E A+B*C*D/E+F,13,9.1.2 多处理机系统的特点,3、并行任务派生 并行处理机把同种操作集中在一起，由指令直接启动各PE同时工作 多处理机用专门的指令来表示并发关系，一个任务开始执行时能够派生出与它并行执行的另一些任务 如果任务数多于处理机数，多余的任务进入排队器等待 4、进程同步 并行处理机仅一个CU，自然是同步的 多处理机执行不同的指令，工作进度不会也不必保持相同, 先做完的要停下来等待 有数据相关和控制相关也要停下

8、来等待 要采取特殊的同步措施来保持程序所要求的正确顺序,14,9.1.2 多处理机系统的特点,5、资源分配和进程调度 并行处理机的PE是固定的，采用屏蔽手段改变实际参加操作的PE数目 多处理机执行并发任务，需用处理机的数目不固定，各个处理机进入或退出任务的时刻不相同，所需共享资源的品种、数量又随时变化 提出资源分配和进程调度问题，它对整个系统的效率有很大的影响,15,9.2 多处理机性能模型,引起峰值性能下降的原因是 (1)因处理机间通信而产生的延迟 (2)一台处理机与其它处理机同步所需的开销 (3)没有足够多任务时，一台或多台处理机处于空闲状态 (4)由于一台或多台处理机执行无用的工作 (5

9、)系统控制和操作调度所需开销 研究多处理机的目的 提前5年得到速度高10倍的机器-跨越设计、生产工艺的台阶 或用1/10的价格获得一台高性能的机器-低成本的组合 设计得好，某些适合进行并行处理得应用领域，可达到 提前10年得到速度高100倍的机器 或用1/100的价格获得一台高性能的机器,16,R/C比值,并行性在很大程度上依赖于R/C比值 其中：R代表程序执行时间，C代表通信开销 通常：R/C比值小，并行性低。R/C比值大，并行性高 如果把作业分解成较大的块，就能得到较大的R/C值，但是所得到的并行性比最大可能的并行性要小得多 R/C比值是衡量任务粒度(Granularity)大小的尺度 在

10、粗粒度(Coarsegrain)并行情况下，R/C比值比较大，通信开销小 在细粒度(Finegrain)并行情况下，R/C比值比较小，通信开销大 细粒度并行性需要的处理机多，粗粒度并行性需要的处理机少 细粒度并行性的基本原理是把一个程序尽可能地分解成能并行执行的小任务。 在极端情况下，一个小任务只完成一个操作,17,9.2.1 基本模型,假设有一个包含M个任务的应用程序，希望在一个由N台处理机组成的系统上以最快的速度执行这个程序 先考虑一个仅有两台处理机的系统，然后再逐步增加处理机数目 为了模拟性能，需要用公式表示出执行时间和额外开销 先承认下面两个假设是成立的，以获得初步结论，然后放宽假设，

11、观察性能如何变化 (1)每个任务的执行时间为R个单位时间 (2)当两个任务不在同一台处理机上时，其通信所需的额外开销为C个单位时间。当两个任务在同一台处理机上时，通信所需的额外开销为0,18,一个应用程序在两台处理机系统上运行有多种分配方法 可以把全部任务都分配给一台处理机而另一台空闲 这种分配方法的通信开销最小，但没有利用并行性 也可以按各种不同比例将任务分配给两台处理机 那么总处理时间是执行时间和额外开销时间之和 CPU1 CPU2 M 0 M-1 1 M-2 2 . 0 M,19,用C表示用于通信的时间，其实它还包括系统所有其它额外开销 某些情况下，系统的额外开销的操作可与计算过程重叠进

12、行 如处理机在执行指令的同时能通过I/O接口进行通信 并不是所有的额外开销都可以被屏蔽掉 如处理机在访问共享数据或通信通路时可能会发生竞争，处理机在等待同步信号期间处于空闲状态等 假设一部分额外开销的操作会增加总处理时间,20,用下列等式表示一个程序的总处理时间 总处理时间=Rmax(M-K，K)+C(M-K)K (9.1) M个任务的应用程序，在由N台处理机组成的系统执行 C表示用于通信的时间 每个任务的执行时间为R个单位 总处理时间是两个时间的和 一个是执行时间 另一个是用于通信和其它额外开销的时间 对两台处理机系统，执行时间取两台处理机较大的一个 K个任务分配给一台处理机，剩下的(M-K

13、)个任务分配给另一台处理机时，执行时间取R(M-K)和RK中较大的一个 K为任务分配参数 第二项表示额外开销时间与通信次数成正比例关系 通信次数与任务分配方法有关 从式(9.1)可知，第一项是K的线性函数，第二项是K的二次函数,21,从式(9.1)可知总处理时间是K的函数，其最小值是多少呢？也就是说，任务如何分配才能获得最小的总处理时间 用图解法来求最小处理时间 R/C代入式(9.1)，令C=1,22,图9.2 两种不同R/C比值的并行执行时间,对于该模型的结论是 当R/CM/2时，把所有任务分配给同一台处理机能使总处理时间最小 当R/CM/2时，把任务平均地分配给两台处理机能使总处理时间最小

14、 使任务分配参数K=0或K=M/2 当M为奇数时，应使K尽可能接近M/2,23,9.2.2 N台处理机系统的基本模型,M个任务分配给N台处理机，求总处理时间的最小值 实际的最小值发生在极端分配情况下，或者将所有的任务集中在一台处理机上，或者将任务平均分配给所有处理机 先讨论平均分配方法 4个任务平均分给3台处理机(P),24,11个任务平均分给5台处理机(P),每个P最大任务数3 完全均分，每个P为2个任务，多出的一个分给其中任一个 不超出最大任务数3，往前推，若干个3，一个2，其余为0 最大任务数尽量小-R 尽量往前推，不足最大任务数的余数分给一个P-C,25,M个任务平均分配给N台处理机的

15、最佳分配方法,最大任务数每台分 个任务 分得最大任务数的有 台处理机 如果M/N 0 则另有1台处理机分得剩下的 个任务 剩下的 台处理机不分配任何任务 处理机任务数有3个取值： 、 、0 如101个任务平均分给50台处理机 每台分给 =3个任务,有 = 33台处理机 另有1台处理机分给 101 mod 3 =2个任务 剩下的 50-33-1=16 台处理机不分配任务,26,假设Ki个任务分给了第i台处理机 第一项求出N台处理机中最大执行时间 第二项计算出Ki与(M-Ki)任务之间两两通信的开销时间,第二项是关于Ki的二次函数 其中，Ki最多有3个取值： 、 、0 当M是N的倍数时，有： 当R

16、/CM/2时采用平均分配方法 当R/CM/2时采用集中分配方法,27,多处理机系统的加速比,一个计算问题在一台处理机上运行时间与在多处理机系统上运行时间的比值称为多处理机系统的加速比 当M 是N 的倍数时，有 如果M 和N 较小，R /C 较大，即分母中的第一项远大于第二项，则加速比与处理机台数N 成正比 当处理机台数N很大，加速比 即加速比趋近于一个常数 这时再增加处理机，性能的提高很小，与所增加的成本相比是不值得的,28,9.2.3 随机模型,略,29,9.2.4 通信开销为线性的模型,略,30,9.2.5 完全重叠通信的理想模型,略,31,9.2.6 具有多条通信链的模型,略,32,几个模型的总结,(1)多处理机系统结构所需的额外开销，包括调度，对共享资源的竞争，同步，处理机之间通信等 串行机和向量机(或别的