《基本概念第二章指令系统及CPU组成第三章存储系统.ppt》由会员分享，可在线阅读，更多相关《基本概念第二章指令系统及CPU组成第三章存储系统.ppt（83页珍藏版）》请在三一办公上搜索。
1、2023/10/11,1,第一章 基本概念第二章 指令系统及CPU组成第三章 存储系统第四章 输入输出系统第五章 标量处理机第六章 向量处理机第七章 互连网络第八章 并行处理机第九章 多处理机,计算机组成与系统结构,2023/10/11,2,两个或两个以上处理机(包括PU和CU)，通过高速互连网络连接起来，在统一的操作系统管理下，实现指令以上级（任务级、作业级）并行。按照Flynn分类法，多处理机系统属于MIMD计算机。9.1 多处理机结构9.2 多处理机性能模型9.3 多处理机的Cache一致性9.4 多处理机实例9.5 多处理机并行算法,第九章 多处理机,2023/10/11,3,9.1
2、多处理机结构,多处理机系统由多个独立的处理机组成，每个处理机都能够独立执行自己的程序。它有多种分类方法：以松散偶合多处理机和紧密偶合多处理机两种类型结构说明多处理机的基本结构和特点。9.1.1 松散偶合多处理机9.1.2 紧密偶合多处理机9.1.3 多处理机系统的特点,2023/10/11,4,多处理机系统有多种分类方法：按照处理机之间的连接程度：紧密偶合和松散偶合多处理机按照是否共享主存储器：共享存储器和分布存储器多处理机按照处理机是否相同：同构型和异构型多处理机按照处理机的个数：大规模并行处理机MPP和对称多处理机SMP按照PE与IOP之间互连方式：对称型：每个IOP能够连接到所有PE上非
3、对称型：每个IOP只与一个PE连接。冗余对称型：一个PE与多个IOP连接。按照存储器的访问方式：均均存储器，UMA模型非均均存储器，NUMA模型只有Cache，COMA模型多向量处理机，机群系统（Cluster）等也称为多处理机系统。,2023/10/11,5,处理机之间的连接频带比较低通过输入输出接口，处理机之间互为外围设备进行连接。例如，IBM公司的机器都可以通过通道到通道的连接器CTC(Channel To Channel)把两个不同计算机系统的IOP连接起来。通过并行口或串行口把多台计算机连接起来。例如，用串行口加一个MODEL拨号上网，也可以直接连接；多台计算机之间的连接需要有多个接
4、口。通过Ethernet网络接口连接多台计算机。速度达10Mb、100Mb、1Gb，Mynet已经达到1.28Gb和2.56Gb。当通信速度要求更高时，可以通过一个通道和仲裁开关CAS(Channel and Arbiter Switch)直接载存储器总线之间建立连接。在CAS中有一个高速的通信缓冲存储器。,9.1.1 松散偶合多处理机,2023/10/11,6,2023/10/11,7,2023/10/11,8,处理机之间共享主存储器，通过高速总线或高速开关连接。每个CPU能够访问任意一个存储器模块通过映象部件MAP把全局逻辑地址变换成局部物理地址通过互连网络寻找合适的路径，并分解访问存储器
5、的冲突多个输入输出处理机IOP也连接在互连网络上，输入输出设备与CPU共享主存储器。处理机个数不能太多，一般几个到十几个。紧密偶合方式要求有很高通信频带。可以采用如下措施：(1)采用高速互连网络(2)增加存储模块个数，一般nm，取12倍之间。(3)每个存储模块再分成多个小模块，并采用流水线方式工作。(4)每个CPU都有自己的局部存储器LM。(5)每个CPU设置一个Cache。,9.1.2 紧密偶合多处理机,2023/10/11,9,2023/10/11,10,2023/10/11,11,1、结构灵活并行处理机：专用，PE数很多(几千个)，固定有限的通信多处理机：通用，几十个，高速灵活的通信2、
6、程序并行性并行处理机的并行性存在于指令内部，识别比较容易。多处理机的并行性存在于指令外部，在多个任务之间，识别难度较大。一个简单的例子：Y=A+B*C*D/E+F。用两个处理机：CPU1：B*C，A+F，A+B*C*D/E+FCPU2：D/E，B*C*D/E，,9.1.3 多处理机系统的特点,2023/10/11,12,3、并行任务派生并行处理机把同种操作集中，由指令直接启动各PE同时工作。多处理机用专门的指令来表示并发关系，一个任务开始执行时能够派生出与它并行执行的另一些任务。如果任务数多于处理机数，多余的任务进入排队器等待。4、进程同步并行处理机仅一个CU，自然是同步的。多处理机执行不同的
7、指令，工作进度不会也不必保持相同。先做完的要停下等待。有数据相关和控制相关也要停下等待。要采取特殊的同步措施来保持程序所要求的正确顺序。5、资源分配和进程调度并行处理机的PE是固定的，用屏蔽改变实际参加操作的PE数目。多处理机执行并发任务，需用处理机的数目不固定，各处理机进出任务的时刻不相同，所需共享资源的品种、数量随时变化。资源分配和进程调度问题，对整个系统的效率有很大的影响。,2023/10/11,13,引起峰值性能下降的原因：(1)由于处理机之间通信而产生的延迟。(2)一台处理机与其它处理机同步所需的开销。(3)当没有足够多任务时，一台或多台处理机处于空闲状态。(4)由于一台或多台处理机
8、执行无用的工作。(5)系统控制和操作调度所需的开销。研究多处理机的目的：单处理机的速度提高很快，为什么还要研究多处理机？提前5年得到速度高10倍的机器。或用1/10的价格获得一台高性能的机器。在某些适合进行并行处理得应用领域，可以达到：提前10年得到速度高100倍的机器。或用1/100的价格获得一台高性能的机器。,9.2 多处理机性能模型,2023/10/11,14,并行性在很大程度上依赖于R/C比值，其中：R代表程序执行时间，C代表通信开销。通常：R/C比值小，并行性低。R/C比值大，并行性高。如果把作业分解成较大的块，就能得到较大的R/C比值，但是所得到的并行性比最大可能的并行性要小得多。
9、R/C比值是衡量任务粒度（Task Granularity）大小的尺度。粗粒度(Coarsegrain)并行：R/C比值比较大，通信开销小。细粒度(Finegrain)并行：R/C比值比较小，通信开销大。细粒度并行需要的处理机多，粗粒度并行需要的处理机少。细粒度并行性的基本原理是把一个程序尽可能地分解成能并行执行的小任务。在极端情况下，一个小任务只完成一个操作。指令级并行。,2023/10/11,15,目标：由M个任务组成的程序，在N台处理机组成的系统上运行，求最短执行时间？为了简单起见，基本模型仅考虑由两台处理机组成的系统。总处理时间Rmax(MK，K)C(MK)K 其中：R：每个任务的执行
10、时间，C：通信开销，K：任务分配参数。直观看：当通信时间比较小时，把M个任务平均分给两台处理机，当通信时间很大时，把M个任务分配给一台处理机。,9.2.1 基本模型,2023/10/11,16,2023/10/11,17,通信时间：C(M-K)K是一个开口向下的二次函数，任务执行时间是两根相交的直线。当通信时间比较大时，总时间的最小值发生的两个端点，当通信时间比较小时，总时间的最小值发生的中点。结论：(1)总时间的最小值只可能出现在中点或两个端点，(2)如果总时间的最小值发生在中点 即M个任务平均分给两台处理机，必须满足：M R R M/2+C M/2 M/2 R/C M/2总时间最短的结论：
11、当R/CM/2时，把所有任务分配给同一台处理机，K0；当R/CM/2时，把任务平均地分配给两台处理机，KM/2。,2023/10/11,18,M个任务分配给N台处理机，求总处理时间的最小值。实际的最小值发生在极端分配情况下，或者将所有的任务集中在一台处理机上，或者将任务平均分配给所有处理机。先讨论平均分配方法：个任务平均分给台处理机（P）：11个任务平均分给台处理机（P）：,9.2.2 N台处理机系统的基本模型,2023/10/11,19,M个任务平均分配给N台处理机的最佳分配方法：有 台处理机，每台分给 个任务；如果M/N0，则：另有1台处理机分得剩下的 个任务；剩下的 台处理机不分配任何任
12、务。例如：101个任务平均分给50台处理机：有33台处理机，每台分给3个任务；另有台处理机分给个任务；剩下的16台处理机不分配任务。,2023/10/11,20,假设Ki个任务分给了第台处理机：第一项求出N台处理机中最大执行时间；第二项计算出Ki与（MKi）任务之间两两通信的开销时间；第二项是关于Ki的二次函数。其中，Ki最多有3个取值：、0当 M 是 N 的倍数时，当R/CM/2时采用平均分配方法，当R/CM/2时采用集中分配方法。,2023/10/11,21,多处理机系统的加速比：一个计算问题在一台处理机上运行时间与在多处理机系统上运行时间的比值称为多处理机系统的加速比当M是N的倍数时，有
13、：如果M和N较小，R/C较大，即分母中的第一项远大于第二项，则加速比与处理机台数N成正比。当处理机台数N很大，加速比，趋近于一个常数。这时如果再增加处理机，性能的提高很小。,2023/10/11,22,每个任务要和其它所有任务通信，而通信的内容相同。把M个任务分配给N台处理机时，当M是N的倍数时，总处理时间RMNCN很明显，这个函数有一个极小值。(RMNCN)N0 解得：因此得到最小的总处理时间：这种模型的加速比为：当M是N的倍数时，该多处理机系统的最大加速比为：,9.2.3 通信开销为线性函数的模型,2023/10/11,23,由于通信与计算可以在两个独立的功能部件中进行，因此，能够采用重叠
14、或流水线方式并行进行。一个理想模型，通信与计算完全重叠。对于两台处理机的系统：当R/CM/2时，执行时间与通信时间的交点就是总处理时间的最小值；当R/CM/2时，采用平均分配方法，在这一点运行时间足够长，完全能够屏蔽通信时间。,9.2.4 通信与计算完全重叠的模型,2023/10/11,24,2023/10/11,25,直线与二次曲线的交点是关键点：R(MK)C(MK)K即：KR/C（其中：1KM/2）总处理时间R（MR/C），两台处理机系统的加速比在1与2之间；当R/CM/2，即把任务平均分配给两台处理机时，加速比最大；当R/C逐渐减为1时，加速比也逐渐减为1，最优分配变得越来越不均衡了。至
15、于N台处理机的系统：当N比较大时，近似为：处理机数目N由下面一个关于R/C和M的函数式 给出。,2023/10/11,26,通信链路随的增加而增加，让每台处理机与别的任何一台处理机都有专门的链路相连。当任务数M是处理机数N的倍数时，尽可能平分任务可以使总处理时间达到最小：把处理机台数作为自变量，这个函数有一个极大值。由于分母大于1，因此总处理时间的极大值出现在2时,当=2时，随着处理机台增加，总处理时间肯定减小。,9.2.5 具有多条通信链的模型,2023/10/11,27,为了验证N台处理机是否比一台处理机效果更佳：相等点在：在相等点参数R/C与N成反比例，N越大，允许的粒度越小；N台处理机
16、的总性能等价于一台处理机。总结上面几个模型，可以得出如下结论：(1)多处理机系统结构所需的额外开销，包括调度，对共享资源的竞争，同步，处理机之间通信等。(2)当处理机台数增加时，额外开销时间也增加。实际上，额外开销的增加可能比处理机数目的线性增加更快。(3)R/C比值越大，越有利于计算过程。如果采用粗粒度，能够获得较大的R/C比值；但是并行程度将大为降低。(4)为了使价格和性能都比较合理，处理机数目存在一个极大值，这个值主要依赖于机器的系统结构、基本技术（尤其是通信技术）和具体的应用问题。,2023/10/11,28,在并行处理机和多处理机系统中，采用局部Cache会引起Cache与共享存储器
17、之间的一致性问题。出现不一致性问题的原因有三个：共享可写的数据进程迁移I/O传输。9.3.1 问题由来9.3.2 监听协议9.3.3 基于目录的协议,9.3 多处理机的Cache一致性,2023/10/11,29,1、写共享数据引起的不一致性使用多个局部Cache时，可能发生Cache不一致性问题：当P1把X的值写为X之后，如果P1采用写通过方式，内存中的内容也变为X，但是P2处理机Cache中的内容还是X。如果P1采用写回策法，内存中的内容还是X，当P2处理机要读X时，读到的是X而不是X。,9.3.1 问题由来,2023/10/11,30,2、进程迁移引起的数据不一致性P1和P2中都有共享数
18、据X的拷贝，P2修改了X，并采用写通过方式，所以内存中的X修改成了X。如果该进程迁移到P1上，P1的Cache中仍然是X。P1中有共享数据X的拷贝，而P2中没有该共享数据，P1进程对X进行了修改，如果该进程迁移到了P2上，P2运行时从内存中读到是X。,2023/10/11,31,3、I/O造成数据不一致性如果P1和P2在各自的局部Cache中都有X的拷贝，当I/O将一个新数据X写入存储器时就导致存储器和Cache的数据不一致。如果两个局部Cache中都有X的拷贝，并采用写回方式，当P1把X修改成X之后；输出部件读X，存储器把X传给输出部件一种解决I/O操作引起数据不一致性的方法是把I/O处理机
19、分别连接到各自的局部Cache上。,2023/10/11,32,有两类解决Cache不一致性问题的协议：在总线互连的多处理机系统中，通常采用监听协议。在其他多处理机系统中，通常采用基于目录协议。1、两种监听协议使用监听协议，有两种方法：方法一：写无效（Write Invalidate）策略，在本地Cache的数据块修改时使远程数据块都无效。方法二：写更新（Write Update）策略，在本地Cache数据块修改时通过总线把新的数据块广播给含该块的所有其他Cache采用写无效或写更新策略与Cache采用写回方式（Write Back）还是写通过方式（Write Through）无关。如果Cac
20、he采用的写通过方式，在使远程数据块无效或更新其他Cache的同时，还要同时修改共享存储器中的内容。,9.3.2 监听协议,2023/10/11,33,由于写更新策略在本地Cache修改时需要通过总线把修改过的数据块广播给所有含该数据块的其他Cache，增加了总线的负担。大部分多处理机系统使用写无效策略。,2023/10/11,34,2、采用写通过方式的Cache数据块有两种状态:有效和无效。有效表示该数据块内容正确，两种状态的转换如下图：采用写通过方式的Cache状态图RL、WL表示本地处理机对Cache的读和写操作，RR、WR表示远程处理机对Cache中相同内容数据的读和写操作。,2023
21、/10/11,35,3、采用写回方式的Cache只读状态表示整个系统中有多个数据块拷贝是正确的，读写状态表示数据块至少被修改过一次，存储器中相应数据块还没有修改，即在整个系统中只有一个数据块拷贝是正确的。对于只读的数据块，本地的和远程的读操作都是安全的，本地的写操作将使状态转移为读写，远程的写操作将使之变为无效。对于读写状态的数据块，本地的读、写操作都是安全的，而远程的读操作将数据块传递给远程处理机的Cache，使两个Cache都转移至只读状态，远程写操作使远程处理机Cache转移至读写状态，而本地Cache转移至无效状态。对于无效状态，本地读操作，使状态转移至只读；本地写操作，使状态转移至读
22、写，同时使其他Cache中相应数据块的状态转移为无效状态；其他操作不会引起从无效状态向其他状态的转移。,2023/10/11,36,RL：本地处理机对Cache的读操作WL：本地处理机对Cache的写操作 RR：远程处理机对Cache中相同内容数据的读操作 WR：远程处理机对Cache中相同内容数据的写操作,2023/10/11,37,4、写一次(Write-Once)协议方法：第一次写Cache采用写通过方式，以后采用写回方式。整个系统中只有一份正确的拷贝。为了区分第一次写，把“读写”状态分为：“保留（Reserved）”和“重写(Dirty)”。共有4种状态(1)有效(Valid,相当于写
23、回方式中的只读)：(2)无效(Invalid)：在Cache中找不到或Cache中的数据块已作废。(3)保留(Reserved)：数据从存储器读入Cache后只被写过一次，Cache和存储器中的拷贝都是正确。(4)重写(Dirty)：Cache中的数据块被写过多次，而且是唯一正确的数据块，此时存储器中的数据块也不是正确的。写一次协议的主要优缺点:优点:减少大量的无效操作，提高了总线效率。缺点:当主存储器的内容无效时,读缺失引起的总线读操作必须禁止访问主存储器，而大多数总线不支持这种操作。IEEE Futurebus+总线支持该操作。,2023/10/11,38,写一次协议的状态图RL：本地处理
24、机对Cache的读操作WL：本地处理机对Cache的写操作 RR：远程处理机对Cache中相同内容数据的读操作 WR：远程处理机对Cache中相同内容数据的写操作,2023/10/11,39,CPU读Cache：有两种可能性。(1)数据块在Cache中存在(包括有效、保留或重写)，CPU直接读取数据。(2)Cache中的数据块处于无效状态。如果存在处于有效、保留或重写状态的相应数据块，则将其调入本地Cache；在相应数据块处于重写状态时，还要同时禁止存储器操作。如果不存在处于有效、保留或重写状态的相应数据块，则直接从存储器中读入(只有存储器中是唯一正确的拷贝)。把读入Cache中的相应数据块置
25、为“有效”状态。,2023/10/11,40,CPU写Cache：也有两种可能。(1)写命中，当Cache处于“有效”状态时，采用写通过方式，把写入Cache的内容同时写入存储器，将Cache的状态转移为“保留”，将其他Cache的相应数据块状态置为“无效”；当Cache处于“保留”或“重写”态时，使用写回方式，Cache的状态转移至“重写”,其他的存有相同内容的Cache处于“无效”态。(2)写不命中，将数据块调入Cache，采用写通过方式,同时写存储器;将本地Cache的状态置为“保留”，同时将其他Cache的状态置为“无效”。,2023/10/11,41,在非总线结构的多处理机系统中，采
26、用基于目录的Cache一致性协议。1、Cache目录结构Cache目录中存放的内容是大量的指针，用以指明块拷贝的地址，每个目录项还有一个重写位，指明是否有一个Cache允许写入数据。根据Cache目录的存放形式，有集中式和分布式两种。根据目录的结构，目录协议分成三类：全映射(Full-Map)目录：存放全局存储器每个块的有关数据。有限(Limited)目录：每个目录项的指针数固定。链式(Chained)目录：把目录分布到所有Cache中。,9.3.3 基于目录的协议,2023/10/11,42,目录的使用规则：当一个CPU对Cache进行写操作时，要根据Cache目录中的内容将所有其他存有相同
27、内容的所有Cache拷贝无效，并置重写位。在CPU对Cache进行读操作时，如果读命中，泽直接读Cache即可。如果重写位为“0”，则从主存或其他Cache中读入该块，并修改目录。,2023/10/11,43,2、全映射目录目录项中有N个处理机位和一个重写位。处理机位表示相应处理机对应的Cache块的状态。只有一个处理机的重写位为“1”，则该处理机可以对该块进行写操作。Cache的每个数据块有两个状态位。一位表示数据块是否有效，另一位表示有效块是否允许写。,2023/10/11,44,从第二种状态(b)转移至第三种状态(c)的过程如下：(1)Cache3发现包含X单元的块是有效的，但是不允许写
28、(2)Cache3向包含X单元的存储器模块发写请求，并暂停P3工作(3)该存储器模块发无效请求至Cache1和Cache2(4)Cache1和Cache2接到无效请求后，将对应块置为无效态，并发回答信号给存储器模块。(5)存储器模块接到Cache1和Cache2的回答信号后，置重写位为“1”，清除指向Cache1和Cache2的指针，发允许写信号到Cache3。(6)Cache3接到允许写信号，更新Cache状态，并激活P3。优点：全映射目录协议的效率比较高。缺点：开销与处理机数目的平方成正比，不具有扩展性。,2023/10/11,45,3、有限目录当处理机数目为N时，限制目录大小为O(N l
29、og2 N)。目录指针需要对N进行二进制编码，每个指针占log2 N位，目录所占的总存储空间与（Nlog2 N）成正比。当Cache1和Cache2中都有X的拷贝时，若P3请求访问X，则必须在在Cache1和Cache2中选择一个使之无效，这种替换过程称为驱逐。有限目录的驱逐需要一种驱逐策略，驱逐策略的好坏对系统的性能具有很大的影响。驱逐策略与Cache替换策略在很多方面是相同的。,2023/10/11,46,2023/10/11,47,4.链式目录通过维护一个目录指针链来跟踪共享数据拷贝。当P1读X时，存储器送X到Cache1,同时写Cache1的一个链结束指针CT，在存储器中也保存一个指向
30、Cache1的指针。当P2读X时，存储器送X给Cache2,同时给Cache2一个指向Cache1的指针,存储器则保存一个指向Cache2的指针。当某一个处理机需要写X时,它必须沿整个目录链发送一个数据无效信息。在收到所有相关处理机的回答信号之后，存储器才给该处理机写允许权。当Cache中的数据块需要替换时，要把该Cache从目录链中删除。有如下解决办法：(1)把Cachei+1的指针指向Cachei-1。在Cachei中存放新数据块。(2)使Cachei及在链中位于其后的所有Cache中的单元X无效。(3)使用双向链。在替换时不再需要遍历整个链。但指针增加了一倍，一致性协议也更加复杂。,20
31、23/10/11,48,优点：不限制共享数据块的拷贝数目，又保持了可扩展性。指针的长度以处理机数目的对数关系增长，Cache的每个数据块的指针数目与处理机数目无关。缺点：链式目录的复杂程度超过了前两种目录。,2023/10/11,49,多处理机系统主要有四大类：(1)多向量处理机系统：如：CRAY YMP-90，NEC SX-3和FUJITSU VP-2000(2)SMP(Symmetry MultiProcessors)对称多处理机 SMP(Shared Memory mulptiProcessors)共享存储多处理机 如：SGI Challenge、Sun SparcCenter 2000
32、(3)MPP(massively parallel processing)大规模并行处理机 如：Intel Paragon，CM-5，Cray T3D(4)Cluster 机群系统（NOW或COM）9.4.1 大规模并行处理机（MPP）9.4.2 对称多处理机（SMP）9.4.3 机群系统（Cluster）,9.4 多处理机实例,2023/10/11,50,科学计算中的重大课题要求提供的性能：(1)Teraflops计算能力(2)Terabyte主存储器(3)Terabyte/s 输入输出频带宽度目前，速度还慢1000倍左右，存储容量和I/O带宽差距更大。科学计算中的重大课题：全球气候预报、基
33、因工程、飞行动力学、海洋环流、流体动力学、超导建模、半导体建模、量子染色动力学、视觉采用的关键技术：VLSI技术、可扩展技术、共享虚拟存储技术虚拟共享存储器(Shared Virtual Memory)也称为：共享分布存储器(Distributed Shared Memory)物理上分布存储器，逻辑上共享存储器。,9.4.1 大规模并行处理机(MPP),2023/10/11,51,虚拟共享存储器的优点：编程容易，系统结构灵活，可扩充性好，有较好的软件移植性。与消息传递方式相比：程序的运行效率高，主要原因：(1)数据块缓存在本地（内存或Cache中），可以多次使用。(2)通信时间分散，提高了并行
34、性。(3)扩大存储空间，减少换页操作。虚拟共享存储器实现途径：(1)硬件实现，利用Cache技术。需要增加专用硬件。(2)操作系统和库实现，通过虚拟存储机制取得共享和一致性。在松耦合的分布存储多处理机上，不需要增加任何硬件。(3)编译实现，自动将共享访问转换成同步和一致原语。大多数系统采用途径(1)和(2)，或这两种途径结合实现。,2023/10/11,52,1、同步MIMD机器SIMD与MIMD的优点结合在一起。CM-5同时支持SIMD与MIMD两种并行计算方式。数据并行可以采用SIMD、多SIMD或同步MIMD模式。32到16384个处理器结点，每个结点有一个SPARC处理机，32MB存储
35、器，64位浮点和整数操作，128Mflops向量处理部件,2023/10/11,53,控制处理机到几十台，根据需要配置存储器和磁盘。输入输出接口与图形设备、海量存储器及高性能网络相连。占地面积为30米30米，峰值速度超过Tflops。三个网络：数据网络、控制网络和诊断网络。数据网络提供点对点通信。控制网络提供广播、同步、扫描和系统管理功能。诊断网络从后台访问所有系统硬件，测试系统完整性，检测和隔离错误。数据网络和控制网络有很好的可扩展性，与处理机类型无关。可以划分成一个或多个分区供用户使用每个分区一台控制处理机，一组处理结点，数据和控制网络的专用部分。允许任何分区中的进程可以访问任何I/O设备
36、。,2023/10/11,54,2、CM-5网络结构数据网络采用胖树型网，数据处理结点、控制处理机和I/O通道都位于胖树的叶子上。利用胖树的层次结构特性，可以划分一棵子树给一个用户。采用4元胖树实现，每个内部开关结点由n个寻径器芯片组成。每个寻径器与4个子芯片和2个或4个父芯片相连。可以分配不同的子树处理不同的作业，子树的大小可以任意。为了把消息从一台处理机传送到另一台处理机，首先沿树将消息向上传送到离两台处理机最近的公共祖先，然后向下传送到目的处理机。每台处理机与数据网络有两条连接通路，每个叶子结点的输入和输出的频宽为40兆字节/秒。当一个消息沿树向上传送时，使用哪条父连接通路则有几种选择。
37、,2023/10/11,55,2023/10/11,56,3、控制处理机控制处理机由CPU、存储器、本地磁盘、网络接口、以太网组成。它相当于一台标准工作站。网络接口通过控制网络和数据网络使处理机与系统的其它部分相连。控制处理机专门执行管理功能，不需要高性能的运算部件。每台控制处理机都能够运行操作系统，负责并行处理资源的管理。一部分控制处理机管理用户区的计算资源，其它管理I/O资源。,2023/10/11,57,4、处理结点SPARC处理器，重叠寄存器窗技术，实现快速的进程切换，使不同时间不同用户分区能够动态地使用处理结点。通过控制网络和数据网络将结点与系统的其它部分相连。向量部件执行由标量处理
38、机发出的向量指令，每个向量部件有一个流水ALU和64个64位的寄存器。每条向量指令可能传送给一个向量部件、或一对向量部件、或同时广播给所有4个向量部件。标量处理机负责地址转换和循环控制，向量处理部件的操作与标量处理部件并行执行。每个结点的峰值速度为128Mflops。16384个处理结点的总峰值速度为：21427221 Mflops=2Tflops网络的系统结构设计，做到与所选择的处理器无关。提供更换处理机提供系统的性能。,2023/10/11,58,2023/10/11,59,2023/10/11,60,1、概述SMP称为共享存储多处理机(Shared Memory mulptiProces
39、sors),也称为对称多处理机（Symmetry MultiProcessors)。有三种模型：(1)UMA多处理机均匀存储器存取模型(Uniform Memory Access)存储器被所有处理机均匀共享处理机对所有存储单元具有相同的存取时间。每台处理机有局部Cache。外围设备可以共享。,9.4.2 对称多处理机（SMP）,2023/10/11,61,(2)NUMA多处理机非均匀存储器存取（Nonuniform Memory Access）模型存储器访问时间随存储单元的位置不同而变化。共享存储器在物理上是分布在所有处理机中的本地存储器。所有局部存储器地址空间的集合就组成了全局地址空间。处理
40、机访问本地存储器比较快，访问属于另一台处理机的远程存储器则比较慢，因为通过互连网络会产生附加的时间延迟。,2023/10/11,62,(3)COMA多处理机只有Cache的存储器结构(Cache-Only Memory Architecture)模型COMA是一种只用Cache的多处理机系统实际上，COMA模型是NUMA模型的一种特例，后者分布存储器换成了Cache。在每个处理机结点上没有主存储器，全部Cache组成了全局虚拟地址空间。远程Cache访问则借助于分布的Cache目录进行。共享存储系统拥有统一的寻址空间，程序员不必参与数据分配和传输。,2023/10/11,63,2、S2MP结构
41、1996年SGI Origin 2000服务器，采用S2MP并行体系结构S2MP实际上是NUMA多处理机系统，采用分布存储器，并通过cache对系统的共享和局部数据都进行缓存，以达到高性能。从用户编程角度看，S2MP是一种共享存储的多处理机系统。S2MP的主要特点：易编程、可扩展(1)编程简单，使用方便。(2)可扩展性好，增加处理器数目不受总线带宽的限制。(3)通信开销小，可以开发程序中的细粒度并行性。S2MP的关键技术：(1)高速无阻塞互连网络，增加系统的通信带宽。(2)分布式存储器，随处理器数目的增加自动增加存储器带宽。(3)引入cache，降低访存时延。(4)所有存储器统一编址，提供单一
42、的地址空间。(5)每个处理器结点上有一个目录存储器，维护cache一致性。,2023/10/11,64,2023/10/11,65,3.SGI Origin2000系列服务器Origin 2000将SMP、MPP、Cluster的优点结合起来SMP易编程，MPP可扩展性，Cluster可用性好。有4种机型：Origin 2000，塔式系统，最多4个处理器。Origin 2000 Deskside，桌边服务器，最多8个处理器。Origin 2000 Rack，机柜服务器，处理器数目最多为16个。Cray Origin 2000，支持128个处理器。Origin 2000是S2MP结构的典型实现，
43、地址空间成指数增长，连续可扩展，最多可以扩展至1024个处理器，具有高带宽和低时延。关键技术：Cray Link多重交叉开关互连技术Cellular IRIX蜂窝式操作系统,2023/10/11,66,Origin 2000系列服务器结构：(1)结点板每个结点板（主板）有一到两个R10000处理器、二级cache、主存储器、录存储器、HUB、I/O接口、互连网络路由器接口。,2023/10/11,67,(2)HUB结构四个双向的端口，每个端口的双工带宽1.6GB/S。四个端口分别连接到处理器、主存储器、XIO和互连网络。四个端口在内部以交叉开关互连。,2023/10/11,68,(3)存储系统
44、有一个统一的共享地址空间，存储系统共分为四个层次：第一层：寄存器堆，访问延迟时间最短；第二层：cache,主cache在CPU芯片上,二级cache在结点板上；第三层：本地存储器，包括主存储器和目录存储器；第四层：远程cache，用于减少访问共享存储器所需的时间。(4)互连网络互连网络是一组开关组成，称为路由器；允许多个传输同时发生；速度极高，每条链路带宽达到1.6GB/S；互连网络不需要仲裁，也不存在竞争；路由器的核心是6路全交叉开关。峰值通信带宽9.6GB/S。,2023/10/11,69,2023/10/11,70,(5)扩展连接方式：可以构成 4、16、32、64、128个处理器的互连
45、拓扑结构。两个结点板通过HUB直接连接得到4个处理器的机器。由于路由器提供了两条连接结点板的链路，由一个路由器和两个结点板构成一个模块，利用路由器的其他4个接口可以扩展到不同的规模。使用其中的2条链路，可以连接16个处理器。使用其中的3条链路，形成一个立方体，可以连接32个处理器。使用4条链路，构成一个4维超立方体，可以连接64个处理器。采用Cray Router，最大配置可以达到128个处理器。图中：P是处理器、N是结点板、H表示HUB、R表示路由器。,2023/10/11,71,2023/10/11,72,2023/10/11,73,1、机群系统的组成机群系统是利用高速网络将一组高性能工作
46、站或高档PC机连接起来，在并行程序设计以及可视化人机交互集成开发环境支持下，统一调度，协调处理，实现高效并行处理的系统。Cluster、NOW、COM从结构和结点间的通信方式来看，属于分布存储系统。机群系统中的主机和网络可以是同构的，也可以是异构的。微处理机技术、网络技术和并行编程环境的发展使得机群系统这一新的并行处理系统形式正成为当前研究的热点。(1)微处理器的性能不断提高。(2)网络技术的进步使松散耦合系统的通信瓶颈逐步得到缓解。(3)并行编程环境使新编并行程序或改写串行程序更为容易。,9.3.4 机群系统（Cluster）,2023/10/11,74,2、机群系统的特点(1)系统开发周期
47、短。(2)用户投资风险小。(3)系统价格低。(4)节约系统资源。UC Berkeley计算机系100多台工作站的使用情况调查表明，一般单机系统的使用率不到10%，而机群系统中的资源利用率可达到80%左右。(5)系统扩展性好。(6)用户编程方便。3、机群系统的关键技术(1)高效的通信系统 在用户空间实现通信协议 精简通信协议 Active Message通信机制,2023/10/11,75,传统通信协议(TCP/IP),10M Ethernet,100M Ethernet,Myrinet,硬件开销,软件开销,通信开销分析,软件开销成为影响通信系统性能的瓶颈,2023/10/11,76,2023/
48、10/11,77,(2)并行程序设计环境PVM(Parallel Virtual Machine)，开始于1989年夏天,美国橡树岭国家实验室(ORNL)；一套并行计算工具软件，支持多用户及多任务运行；支持多种结构的计算机，工作站、并行机以及向量机等；支持C、C+和Fortran语言；自由软件，使用非常广泛；编程模型可以是SPMD或MPMD；具有容错功能，当发现一个结点出故障时，自动将之删除MPI(Message Passing Interface)在1992年11月至1994年元月产生。能用于大多数并行计算机、计算机机群和异构网络环境，支持C和Fortran两种语言,编程模型采用SPMD,2
49、023/10/11,78,Express美国Parasoft公司推出；能在不同的硬件环境上运行；支持C和Fortran两种程序设计语言。Linda美国Yale大学与科学计算协会共同研制；通过函数扩充现并行程序的设计，C-Linda、Fortran-Linda等；,2023/10/11,79,(3)并行程序设计语言在多处理机系统中，必须用并行程序设计语言编写程序。或者把已经用串行语言编写的程序转换成并行语言程序之后，才能在多处理机系统上运行。把传统串行语言程序转换成并行语言程序的过程称为并行编译。有两种方式：全自动并行编译与半自动并行编译：全自动并行编译是方向，但实现起来很困难。半自动并行编译又
50、称为交互式并行编译。程序员通过多次与机器对话，找到串行程序中可以并行执行的部分。并行编译器生成代码的形式有多种：并行高级语言程序 并行中间语言程序 并行目标语言程序,2023/10/11,80,交互式Fortran77并行编译系统,2023/10/11,81,(4)负载平衡技术一个大任务可以分解为多个子任务，把多个子任务分配到各个处理结点上并行执行的技术称为负载平衡技术。对于由异构处理结点构成的并行系统，相同的负载在各个结点上的运行时间可能不同。负载平衡技术的核心就是调度算法，将各个任务均衡地分布到不同的处理结点上并行计算，使各结点的利用率达到最大。负载平衡技术分为静态和动态两大类：静态方法是
