[小学教育]第8章 多处理机.ppt

第8章 多处理机 内容提要 : 本章首先介绍多处理机的基本结构与类型，包括紧耦合多处理机 、松耦合多处理机及多处理机中的Cache一致性问题。然后，讲述并 行多处理机中的关键技术，比如程序并行性分析、并行程序设计语言 的基本概念、多处理机操作系统的基本特征及多处理机调度策略等。 最后以具体示例阐述并行多处理机的发展趋势。重点是紧耦合/松耦 合多处理机的组成及与Cache的一致性、并行程序设计语言的基本概 念、多处理机操作系统的基本特征以及多处理机调度策略等。难点是 多处理机中的Cache一致性和多处理机调度策略。 第8章 多处理机 8.1 多处理机的基本结构与类型 8.2 并行多处理机技术 8.3 并行多处理机的发展趋势 8.1 多处理机的基本结构与类型 8.1.1 紧耦合多处理机 8.1.2 松耦合多处理机 8.1.3 多处理机中的Cache一致性 多处理机是由多台独立的计算机组成，若按照Flynn分类法，这种 结构称为多指令流多数据流，即MIMD型结构。按照处理机的组成与 连接方式，多处理机可分为两种类型，即紧耦合（Tightly coupled ）多处理机和松耦合（Loosely coupled）多处理机。 8.1.1 紧耦合多处理机 紧耦合（Tightly coupled）多处理机是指各处理机通过系统中 的共享主存实现相互之间的数据传送及通信。各处理机有自己的 局部存储器，又共享共用存储器。 其结构如图8.1所示，由p个 处理机、m个存储器模块和d个 I/O通道组成。每个处理机Pi有一个容量不大的本地存储器LMi，配 置高速Cache CMi。各处理机通过互 连网络PPIN实现互连，又通 过互连网络PMIN与共享存储器连接，通 过互连网络PIOIN与外部 I/O通道连接。 图8.1 紧耦合多处理机典型结构 由于通过共享存储器实现数据传送和通信，因此速度快，效率 高。但是处理机的台数往往受到限制，主要有两方面的因素。一是通 过共享存储器通信，故当处理机的数量增大时，访存冲突增多；二是 处理机与主存之间的互连网络的带宽有限，当处理机的数量增大时可 能成为瓶颈。为此，常采用以下措施： 采用多模块交叉存储器结构，以减少访存冲突。 每台处理机有一个小容量的局部存储器，存放核心代码，减 少对共享存储器的访问。 每台处理机配置一个高速Cache，以减少对主存的访问。 在构成多处理机时，各处理机的内部结构可以相同，也可以不 同；结构形式可采取对称型，也可采取非对称型。下面主要介绍同构 对称型和异构非对称型的结构。 1. 同构对称型多处理机 同构对称型多处理机是指系统中各处理机的结构及总线连接方式 相同。 （1）Balance同构对称型多处理机 如图8.2所示，处理机由232个CPU组成，存储器由16个存储体 组成。每个处理机模块由1个80386CPU、浮点运算器Weitek1167及 64KB的Cache组成；每个存储器模块MEM包含8MB存储体及一个存储控 制器，其容量可扩展到40MB。处理机模块、存储器模块直接与系统总线 连接。系统总线通过磁盘控制器与外部磁盘阵列连接，通过SCSI总线与 其它外部设备连接，另外还可通过总线适配器与局域网（Ethernet）或 远程网（x.25）连接。 图8.2 Balance同构对称型多处理机 （2）曙光一号同构对称型多处理机 如图8.3所示，由4个CPU和4个存储体组成。每个处理机由1个 MC88100和两个包含Cache的存储控制器MC88200组成，主存容量为 64MB，可扩展到768MB。通过高速局部总线将4个CPU和存储器模块 连接起来，通过总线适配器和I/O接口与远程网（X.25）、局域网（ Ethernet）以及SCSI接口连接。 图8.3 曙光一号同构对称型多处理机 2. 异构非对称型多处理机 是指系统中各处理机的结构及与总线的连接方式可以不同，存储器 模块的结构也可以不同，其示意如图8.4所示。除了主CPU和主存之外 ，还有多个专用处理机。字符处理机CIOP与外部字符设备连接，数据 处理机BIOP与外部数组设备连接，网络处理机NIOP用于外部联网，图 形处理机GIOP连接外部图形设备，ACOP是向量处理机。 图8.4 异构非对称型多处理机示意图 8.1.2 松耦合多处理机 松耦合（Loosely coupled）多处理机是由一些功能较强、相对独立的 计算机模块组成；每个模块至少包括一个功能较强的CPU、局部存储器和 I/O设备；相互之间以消息的方式进行通信。如图8.5所示，每个计算机模块 有一个容量较大的局部存储器，因此大 部分程序和数据处理是在本地进行 。当不同模块上运行的进程需要通信时，经网络通信接口NI（Network interface）和消息传送系统MTS（Message transfer system）， 图8.5 松耦合多处理机示意图 以消息的方式进行 。其中有的模块本身 就是一台功能很强的 结点计算机。 松耦合多处理机 的连接方式基本上分 为两种类型，即非层 次结构和层次结构。 （1）非层次结构的松耦合多处理机 图8.5所示就是一种非层次结构的松耦合多处理机。各个结点机均通过 网络接口NI与共用消息传送系统MTS连接，从形式上来看，仅有一层。其 中网络接口NI主要由数据通道和仲裁开关组成，一方面控制数据传送，另 一方面负责多个计算机模块同时请求访问消息传送系统时的仲裁工作。 （2）层次结构的松耦合多处理机 图8.6所示，是由50个LSI11小型机构成的C*m多处理机，采用多 层总线结构实现多层次连接。其中Cm是基本计算机模块，内部采用LSI 11总线，通过开关S经总线MAP与其它Cm连接。每条MAP总线最多可连接 14个计算机模块Cm，构成一个计算机模块群。KMAP与外部总线连接器， 采用双总线，以提高系统的可靠性。 图8.6 C*m层次结构多处理机 图8.6所示的C*m是一个三层总线的多处理机，其中模块内部访 存时间为3.5s，模块群间为9.3s，群组间为26s。其最大优点是可 扩展性好，但级数太多时的性能价格比下降。 在松耦合多处理机中，各计算机模块一般配有Cache，存在 Cache一致性问题。 在多处理机中，各处理机之间的互连方式比SIMD计算机高一些 ，主要有总线方式、纵横交叉开关互连方式、多端口存储器互连方 式、多级互连网络方式以及虫孔（Wormhole）寻径方式等。 8.1.3 多处理机中的Cache一致性 多处理机中各处理机都可能有一个局部Cache，这既要考虑各Cache 与共享主存的一致性，还要考虑各Cache之间的一致性。下面首先说明产生 Cache不一致的途径，然后介绍保持Cache一致性的几种措施。 1. 引起Cache不一致的几种途径 多个处理机用Pi表示，各自Cache用Ci表示，引起Cache不一致的主要途径 ： （1）Cache改写不同步引起不一致性 当某一Pi执行Cache写操作，且用全写法改变了共享主存中的相应区域 ，这时若其它Cache不能随之一起改变，将引起不一致性。 （2）进程迁移引起Cache不一致性 当某Pi在执行某进程时对Cache进行了写操作，且采用替换时写回； 若因某种原因使该进程转移到处理机Pi+1上执行时，再读Cache，则读出的 是没有改写的内容，即不一致性。 （3）I/O传输引起Cache不一致性 当某一或多个处理机的Cache有主存某共享区域的副本时，Pi执行I/O 操作时将输入数据写入到共享主存的这一区域中，将引起Cache与主存共 享区域的不一致性；或者Pi改写了Cache，而采取的是替换时写回策略， 这时另一Pi+1执行输出共享存储器区域的操作，输出的则是原来的内容。 2. 保持Cache一致性的三种措施 目前，解决多处理机中Cache一致性的措施有多种，一是采用软件 的办法，二是监听一致性协议法，另一种是目录表法 （1）软件办法 主要是借助于编译程序进行分析，使共享信息只存放在共享主存中 ，而不进入多处理机的局部Cache中。这样，进入Cache中的信息不为其它 处理机所共享。但是影响了Cache的效率。 （2）监听（Snoopy）一致性协议法 是在处理机-Cache上设置一个部件，监听总线操作。当监听到某Pi 有Cache操作或使主存共享区域改变时，按约定协议处理。常用协议有两 种： 写无效协议：当某一Pi改写其Cache中的数据后，使其它处理机中 Cache的相应副本无效。 写更新协议：当某一Pi改写其Cache中的数据后，将改写结果广播 到其余处理机的Cache中，做相应的拷贝。 （3）目录表法 也称为目录表协议，是在某处理机Pi修改Cache和共享主存后，仅把 修改信息发送到与该Cache有相同副本的处理机，故此需要一个目录表， 记录所有Cache块和共享数据块的位置与状态，其内容主要是一些指针， 表明块拷贝的地址和是否进行了写入的状态。根据目录表的构成方式， 可分为集中式和分布式两种。集中式常用于集中共享主存的小型多处理 机的Cache一致性控制。分布式是将目录分布到各个处理机上，每个存储 模块有一个单独的目录存放所有Cache的状态信息。 8.2 并行多处理机技术 8.2.1 程序并行性分析 8.2.2 并行程序设计语言 8.2.3 多处理机操作系统 8.2.4. 多处理机调度策略 8.2.1 程序并行性分析 多处理机的并行性主要表现在程序级或任务级。因此，能否把 顺序程序转换成语义等价且可并行运行的程序，是程序并行性分析 的主要任务。这里，主要涉及程序中的数据相关和并行检测技术。 1. 程序中数据相关性分析 虽然在多处理机上并行运行的程序段是异步执行的，但是由 于它们是由某一顺序程序转换而来的，因此在程序段之间也可能存 在象标量流水线中所说的相关性。这里，主要是数据相关。下面仅 以赋值语句表示程序段P，来说明三种常见的数据相关。 （1）数据相关 设程序段P1和P2如下： P1：A=B+C P2：D=A*C 由于程序段P1中赋值号左边的变量A出现在P2中赋值号右边的 变量集中，因此程序段P2必须在P1中求出A的值以后才能执行。于是 称程序段P2中的数据相关于P1。 （2）数据反相关 设程序段P1和P2如下： P1：A=B*C P2：C=D+E 由于程序段P2中赋值号左边的变量C出现在P1中赋值号右边的 变量集中，因此程序段P1必须读出变量C的值以后P2才能执行。于是 称程序段P1中的数据反相关于P2。 （3）数据输出相关 设程序段P1和P2如下： P1：A=B+C P2：A=D*E 由于程序段P1和P2中赋值号左边是同一变量A，且两个程序段有先后 之分，为了保证语义的正确性，必须保证程序段P1先写入A，然后P2才能写 入。于是称程序段P2的数据输出相关于P1。 2. 程序并行检查 并行性检查主要是检查程序中是否有前述相关，常用方法有伯恩施 坦（Bernstein）准则。 在程序执行过程中，常需使用输入和输出两个变量集。若用Ii表示程 序段Pi所要读取主存的单元（变量）集，Qi表示所要写入主存的单元（变量 ）集，则程序段P1和P2能够并行执行的伯恩施坦准则为： I1Q2=，程序段P1的输入变量集与P2的输出变量集不相交。 I2Q1=，程序段P2的输入变量集与P1的输出变量集不相交。 Q1Q2=，程序段P1的输出变量集与P2的输出变量集不相交。 【例8.1】设有三个程序段P1、P2和P3如下，且变量A、B、C、D、 X和Y均为NN的矩阵，试判断这三个程序段能否并行执行。 P1：X =（A+B）*（A-B） P2：Y =（C-1）*（C+D）-1 P3：Z = X+Y 解：按照伯恩施坦准则，它们的输入、输出变量集分别为： I1=A,B，I2=C,D，I3=X,Y，Q1=X，Q2=Y，Q3=Z 由于I1Q2=，I2Q1=，Q1Q2=，所以程序段P1和P2可以并 行执行； 由于I3Q1，I3Q2，所以程序段P3不能与P1和P2并行执行 ，只能在P1和P2执行之后执行。 8.2.2 并行程序设计语言 通常，并行程序设计可采用显式说明或隐式说明。显式说明是通 过专门的语言结构显式说明其并行性。隐式说明则要由编译程序来判 断，确定程序中哪些部分可以并行执行，并转换成并行程序。 并行程序设计语言的产生有两种方法，一是在现有程序设计语 言的基础上扩展能表示并行进程的语句，即扩展型并行程序设计语言 。比如并行FORTRAN、并行C等。二是根据多处理机的系统结构，全 新设计。下面介绍几种扩展型并行程序设计语言的方法。 1. FORKJION语句及使用 其作用是从一个进程派生出一个可以与之并行执行的新进程， JION表示新进程结束，有以下三种形式： FORK A：在地址A派生一个新进程，当前进程继续执行。 FORK A,J：在地址A派生一个新进程，在地址J使计数器加1， 当前进程继续执行。 FORK A,J,N：在地址A派生一个新进程，在地址J将计数器的 值置成N，当前进程继续执行。 JION语句只有一种形式：JION J。表示在地址J处将计数器的值 减1。当计数值减为0时，将启动地址J+1处的进程。否则，释放执行 JION语句的处理机。所有进程以执行JION J语句而结束，但是若是执行 最后一个JION J语句，则从J+1继续执行进程。 【例8.2】FORKJION语句的使用。 解：使用FORKJION控制三个并行进程的派生与执行过程如图8.7 所示。 在进程0执行语句FORK A,J,3时，在地址A处派生一个新的进程1，并 将地址J处计数器的值置成3，且继续执行自身进程。进程1执行到语句 FORK B时，在地址B处再派生一个进程2，本身进程继续执行。这时，三 个进程（0,1,2）并行执行。而且，每一个进程都会执行到语句：JION J ，并按该语句控制计数器减1等操作。 设三个进程执行到语句JION J的顺序为0,2,1。当进程0执行到语句 JION J时，使J处的计数器减1，即J=2，进程0结束，并释放处理机资源。 此后进程2执行到语句JION J，使J处的计数器减1，即J=1。由于J的值仍不 等于0，该进程结束，并释放处理机资源。当进程1执行到语句JION J时， J处的计数器减1，且J=0。这时，将在J+1处启动进程1，这主要是由于上 述进程1最后执行语句JION J的缘故。 图8.7 进程派生与执行的过程 2.使用块结构语句表示并行性 （1）使用块结构语句表示并行性 块结构语句有cobegincoend和parbeginparend等，使用时 要把所有可并行执行的语句或进程括起来，即显式说明这些语句或进 程并行执行。例如： begin S0； cobegin S1；S2； ；Sn；coend Sn+1； end 首先执行进程S0，然后并行执行进程S1、S2、 、Sn，最后 执行进程Sn+1。在每一组并行执行的进程中，每一个进程仅有一个 入口和一个出口，即符合结构化程序设计的要求。而且，各进程相互 独立，具有不相交性；也就是说，每一个进程所能修改的变量仅属于 自己的专用局部变量；对于共享变量只能读，不能写。 在实际使用中，并行语句或进程还可以嵌套，例如： begin S0； cobegin S1； begin S2； cobegin S3；S4；S5；coend S6； end S7； coend S8； end 并行执行顺序如图8.8所示。 （2）使用并行循环语句parfor表示并行性 图8.8 嵌套并行执行顺序 【例8.3】设A是一个nn的矩阵，B和C是n1的矩阵，计算C=AB，使用语 句parfor表示算法。 解：使用语句parfor派生p个独立进程。且设p能整除n，则有s=n/p。于是， 可设计算法如下： parfor i =1 until p do begin for j=(i-1)s+1 until s*i do begin C(j)=0 for k=1 until n do C(j)=C(j)+A(j,k)*B(k) end end 每一个派生出来的进程根据i的值，计算外层parforend之间的语句。若设 n=12，p=4，则s=3。于是，执行到语句parfor时，将派生出4个独立的进程，分别 对应于i=1，2，3，4。在4个进程中，j的起始值依次为1，4，7，10。结果如下： i=1：计算C(1),C(2),C(3) i=2：计算C(4),C(5),C(6) i=3：计算C(7),C(8),C(9) i=4：计算C(10),C(11),C(12) 8.2.3 多处理机操作系统 在多处理机中必须有相应的操作系统，以支持多处理机的并行 工作。这里仅介绍其主要特点、类型和对多任务的调度策略。 1. 多处理机操作系统的特点与功能 多处理机操作系统除了具备单机操作系统所要求的资源分配与 管理、存储器管理与保护、死锁防止、异常进程与例外事件处理能力 之外，还应具备以下功能： 支持多个任务的并行执行，即对大的任务进行分解，分配， 且能处理各处理机之间的负载均衡等问题； 支持多处理机之间的同步与通信； 提供系统重构能力，支持多处理机降级使用； 支持硬件和软件的并行性开发。 2. 多处理机操作系统分类 目前，多处理机操作系统的设计主要有三种结构，即主从结构 、独立监控结构和浮动监控结构。这样，也就大致分为三种类型。 （1）主从结构 主从结构是指在多处理机中有一台是主机，多台从机。操作系 统只在主机上运行，且对所有处理机及其软硬件资源进行管理和任务 分配。其特点是控制简单，缺点是可靠性差。一旦主机出现故障，整 个系统瘫痪。 （2）独立监控结构 是指整个系统中各台处理机都有自己的管理程序，独立管理自 己的软硬件资源，某台处理机出现故障不会影响整个系统。但是协调 整个系统并行工作，相对复杂一些，主要适合于松耦合多处理机。 （3）浮动监控系统 管理程序可在各台处理机上浮动，即每一台都有可能成为主处 理机。这种系统使用灵活，易于均衡负载，但是结构复杂，主要适合 于对称型紧耦合多处理机。 8.2.4. 多处理机调度策略 1. 多处理机中的任务调度 在多处理机中，调度的任务就是把一个进程分配到某一台处理机上运 行，不同结构的多处理机有着不同的调度策略。 同构型多处理机是将各种资源，包括处理机、主存、I/O通道及设备， 存放在一个公共的资源池中，为所有进程所共有。这样，有利于提高资源 利用率和各处理机均衡负载。 对于异构型多处理机，由于各处理机可能有很大的差异，对其调度主 要是按功能进行，比如控制、数据处理、数据传送等，使各台处理机各司 其职。 通常，衡量多处理机调度性能的主要指标有以下4点： 希望完成所有任务所用的时间最短； 希望完成所有任务所用到的处理机数最少； 希望最小平均流时间，即执行每一个任务所需要的平均时间最少； 希望处理机的利用率最大，或者处理机的空闲时间最小。 为了说明多处理机任务调度过程，常用调度时空图来表述，如图 8.9所示。设有3个处理机P1、P2、P3，执行5个任务T1T5，各个任 务所用的时间分别为7，6.5，5，2，2。完成所有任务所需要的总时 间为19.5；平均流时间为19.5/5=3.9。P1、P2、P3的利用率分别为 0.93，1.00和0.86；空闲时间分别为0.5，0.0和1.0。 图8.9 任务调度时空图 2. 静态确定性调度模型 这种调度算法要求在求解问题之前就知道在整个系统中执行每一个任 务所需要的时间以及各任务之间的关系，根据不同的环境采用不同的算法 ，允许抢占调度。 为了简单起见，这里仅以一组相同的处理机和具有确定性优先关系的 一组任务所组成的调度环境为例，来说明静态确定性调度模型，且允许抢 占调度。 （1）任务优先图 一个任务的集合也可称为任务系统，其调度过程常用优先图来表示， 如图8.10所示，也称为任务调度图。其中的结点表示具有独立操作且与其 它结点有联系的任务；结点之间的有向边表示任务间的优先关系，也称为 偏序。结点的集合表示的就是任务的集合，即T=T1，T2，Tn。在调 度时，遵循一定的原则，概括起来有以下两条： 遵循偏序关系； 任何时候只能给一台处理机分配一个任务。 图8.10 任务优先图 由于任务的大小不一定相同，用的时间也不一定相等，常用权重来 说明。在图8.10中，权重用表示，其值分别是10.5、14、7和3.5。若 在一个任务图中有n个独立的任务，对应结点的权重依次为t1，t2， tn，有p个处理机。那么，最优调度所需的时间为： w=maxmax(t),(ti)/p n i=1 （8.1） 最小调度时间不能小于最大任务的执行时间或处理机的平均执行时间 。 （2）优化调度 优化调度是希望每一个结点的权重相同，即对执行时间长的任务进 行分解，使权值单位化，如图8.10（b）所示，=3.5。然后再将图中 的结点分成若干互不相交的子集，各子集中的结点彼此独立。这样，处 于同一子集或同一级中的结点可同时执行。 设有图8.11（a）所示任务优先图，其最佳子集序列为T1，T2，T3 ，T5，T6，T7，T4，T8，T9，T10，T11。其级别由下向上，T11为 第一级，T9，T10为第二级，依次类推，直至入口结点。若用两台处理 机P1和P2，允许抢占调度，优化调度时空图如图8.11（b）所示。 图8.11 优化抢占调度举例 首先调度T1；T1执行完后，调度T2和T3；T2和T3执行完后再调度T5 、T6和T7，依次类推。由于处理机的数目是2，因此当某一级中的任务 数也是2时，处理机可充分利用，且在最短的时间内完成任务。而在开 始和结束时，由于只有一个任务，因此仅有一个处理机工作，另一个 空闲。在第三级有三个任务T5，T6，T7，因此只能调度两个，即T5和 T6，T7等待。但是当T6执行一半时，T7抢占P2，于是T6挂起；在T5执行 完后，T6继续执行。这样，T5，T6，T7仅在1 .5个时间单元中完成。P1 和P2得到充分利用 3.动态随机性调度模型 动态随机性调度又称为非确定性调度，在运行过程中对资源进 行动态分配，即把等待处理的任务分配给空闲的处理机。常用分配算 法有随机数法和巡回分配法。动态调度可以较充分地利用处理机资源 ，使所有处理机最大限度地发挥作用。但是由于任务的执行时间不能 事先知道，因此要求系统随时监视所有处理机的状态。无疑，系统开 销大，算法复杂。 8.3 并行多处理机的发展趋势 8.3.1 大规模并行处理机 8.3.2 MPP机举例 8.3.3 共享存储器型多处理机 8.3.4 并行向量处理机 8.3.5 机群 并行多处理机除了上述介绍的同构对称型紧耦合多处理机、异 构非对称型紧耦合多处理机以及各种松耦合多处理机之外，发展较 快的还有大规模并行处理机、并行向量处理机以及工作站机群等。 8.3.1 大规模并行处理机 大规模并行处理机MPP（Massively Parallel Processor）是指规模 可伸缩，常拥有百计、千计甚至万计的处理机的系统。在早期多属于 SIMD计算机，以后逐步成为MIMD计算机。 1. MPP主要特点 MPP系统最突出的特点就是进行大型并行处理，即并行处理能力 强，在结构上表现为很强的规模可伸缩性。 其中每一台处理机的功能都很强，相对独立，且有较大容量的存 储器，有利于系统的伸缩性。这在结构上，拟采用分布式存储器系统。 采用分布式存储器系统，每一台处理机不能直接访问非本地 存储器，因此在各处理机之间常采用消息传送方式。故此可在分布式存 储器系统的基础上构建共享虚拟存储器SVM，系统结构灵活，易于编程 ，易于扩展，使软件有较好的可移植性。 2. SVM构成方式 SVM（Shared virtual memory）的构成方式可以用软件来实现， 也可以用硬件来实现。 （1）软件构成 软件构成方式是用程序把分配在各处理机上的存储器连接起来， 统一编址。采用纯软件方式进行管理，若发生缺页，置换页可能来自外 存，也可能来自其它处理机的局部存储器。为保证页的一致性，软件开 销较大。 （2）硬件构成 硬件构成有两种形式，一种是部分Cache形式，另一种是全Cache形 式。部分Cache是将传统的Cache技术应用到松耦合分布式存储器系统 中，即在每一个处理机中设置一个大容量的Cache和有关保证一致性的 部件。 图8.12 全Cache存储器结构 全Cache结构是指所有处 理机的局部存储器本身就是一 个Cache，其集合构成共享存 储器。这样，相当于每一个处 理机都有一个很大的Cache， 消除了传统意义上的局部存储 器与主存储器，这在逻辑上也 就消除了对物理存储器的寻址 。这样既保持了共享主存多处 理机的优点，又具备分布式存 储器多处理机易扩展的长处。 KSR公司推出的MPP处理机 KSR-1/2采取的就是这种存储 器体系结构，如图8.12所示。 3.芯片选择与网络结构 目前，构成MPP机的基础是功能很强的RISC芯片，比如 CRAY-T3D，采用主频150MHz的DEC Alpha芯片，TMC公司的CM- 5采用40MHz的SPARC芯片。互连网络拓扑结构多采用二维、三维 网格、环（Torus）或胖树结构。在整个系统中，与数据处理时间 相比，网络传输所需要的时间小得多。因此，无论采用哪种网络 结构，对系统的影响都不很大。 8.3.2 MPP机举例 1.CM-5系统组成 CM-5的系统组成如图8.13所示，可包含3216384个处理机结点 ， 图8.13 CM-5系统组成 每个结点包括一个 32MHz的SPARC处理器 、32MB的本地存储器 和一个速度为 128MFLOPS的64位向 量处理部件。系统控制 计算机CP使用的是SUN 公司的工作站计算机， 可配置一台到几十台， 每一台可根据需要配置 存储器和磁盘。 整个系统配置有3个互连网络，其中数据网络为各结点提供高速 点对点数据通信；控制网络为处理机结点与控制计算机之间提供互连 ，实现广播、同步、扫描等协同操作，并完成相关的管理功能；诊断 网络用以访问所有的硬件设备，测试系统的完整性，检查并隔离错误 。 处理结点、控制处理机、I/O通道都采用统一网络接口NI与数据网 络和控制网络连接，这样可实现网络与设备的型号无关性。CM-5的峰 值速度可超过1TFLOPS。 图8.14 4元胖树结构 （1）数据网络 CM-5的数据网络是以胖树概念为基础设计的。各处理机结点、控制 处理机、I/O通道都位于胖树的叶结点上，树的内部结点都是开关。其结 构如图8.14所示，用4元胖树来实现。每一个内部开关结点是由n个寻径 器芯片组成，每个寻径器芯片同与4个开关结点中的寻径器芯片连接，并 与2个或4个父开关结点中的寻径器芯片连接，可调节胖树结点间的带宽 。 （2）控制网络 控制网络是一个完全的二叉树结构，处理机结点、控制处理机、 I/O通道位于叶结点上。该控制网络可为每一个分区分配一棵子树，且 整体结构比数据网络的胖树结构简单，具有切换能力，数据包长64位 ，实现的操作有广播、组合与全局操作。整体分工是控制处理机执行 操作代码中的标量部分，处理机结点执行操作代码中的并行数据处理 部件。 （3）诊断网络 诊断网络也是一棵二叉树结构，根结点可以是一个或多个诊断处理 机，每个叶结点是一块插板或在底板上构成的物理系统盒。诊断处理 机通过一个专门诊断接口来对内部所有支持JTAG（Join test action group）标准的CM-5芯片及网络进行测试，从中发现错误，排除故障 或掉电部分。 图8.15 控制处理机组成 （4）控制处理机 如图8.15所示，由RISC微处理器、存储器、带有本地磁盘的I/O子 系统及网络接口NI组成。该网络接口向内连接CM-5的控制网络及数据 网络，向外连接本地以太网。每个控制处理机运行COMST程序，即一 个基于UNIX的操作系统，负责CM-5并行处理资源的管理工作。包括用 户分区的计算资源和I/O资源。 （5）处理机结点 处理机结点是由SPARC微处理器、向量部件、存储器和网络接口NI组 成，如图8.16所示。内部数据总线64位，每个向量部件有一条专用通路与 8MB存储器连接，专用通路72位，附加了8位错误校正码（ECC）。 图8.16 带向量部件的处理机结点 每个向量部件包含一个流水线式的ALU、一个向量指令译码器 和64个64位的寄存器，执行标量处理器发来的向量指令，完成存储 器访问，并生成校正码（ECC）。 标量处理器可把向量指令发送给指定的向量部件，也可发送给一 对或广播给4个向量部件。每个向量部件访问存储器的峰值带宽为 128MBps，所有向量部件访问存储器的总带宽位512MB/s。处理机结 点的峰值速度为128MFLOPS，CM-5的最大配置为214=16384个处理 机结点，总峰值速度为27214=2TFLOPS。 2.Cray -T3E T3E的体系结构如图8.17所示，是Cray公司1995年推出的又一种 MPP机，如今已有三种型号，即T3E、T3E-90、T3E-1200。 图8.17 T3E体系结构 （1）处理机结点 处理机结点由DEC Alpha 21164和一个外部Shell组成。在Shell中包 含有一个本地主存、通信处理器、512个64位E寄存器及读/写控制部件 。其中21164是一个超标量64位RISC微处理器，内部寄存器也是64位 ，每一个时钟周期能发射4条指令。虚拟地址限定为43位，物理地址限 定为40位，为每个结点配置的本地主存可达2GB。整个系统若有2048 个结点处理机，整个系统的全局物理存储器可达4096GB。在Alpha 21164中设有两级片内Cache，L1指令Cache和数据Cache各8KB，L2 Cache是有96KB的3路组相联Cache，统一用于指令和数据的高速缓存 。 片内两级Cache缓存本地存储器中的内容，处理器则使用虚拟地址 访问远程存储器，虚拟地址经由E寄存器被通信处理器转换成物理地址 ，即结点号+结点内存偏移地址。 （2）互连网络 T3E机采用两种网络，主机连接采用双向三维环网，带宽为 480MB/s，且为处理机结点提供预取和非阻塞写能力，对于存储器提供4 字或8字的块传输能力，且实现自适应最短距离的寻径算法，允许消息绕 过拥挤的链路和结点。 所有结点通过一个或者多个GigaRing相连。GigaRing由一对循环 计数的32位环组成，用以连接用户结点和I/O结点。在I/O结点上设有插 槽，可插入以太、FDDI、HiPPI、ATM等网卡，或者插入磁盘、磁带机等 设备的接口卡。这多个GigaRing构成包交换、高带宽的I/O子系统，包的 大小可达256B，峰值带宽为1GB/s。 在T3E中，除了用户结点、I/O结点之外，还有操作系统服务结点 和预备结点。操作系统使用的是Cray 64位UNIX的一个变种UNIDOS/mk ，是一个全分布式操作系统。 3.MPP发展的新技术 除了提高Cache及其一致性管理、通信网与处理器接口性能以及I/O处理 能力之外，人们已经在研究利用多线程（Multithread）技术开发细粒度的并 行性，研究新的并行算法和计算模型，开发并行编译与并行编程环境等。 而且，数字通信网的速率很高（Gbps），使网络中的计算资源联系非常 紧密，因而分布式系统与并行计算机系统之间的界限逐渐模糊起来。通过计 算机网络也可构成大型并行计算机环境。且有利于开发异构型并行处理机环 境，如图8.18所示，有利于系统的容错能力。 图8.18 异构型并行处理机 8.3.3 共享存储器型多处理机 1.共享存储器型多处理机 共享存储器型多处理机SMP（Shared Memory MultiProcessors） ，也称为对称型多处理机，有三种模型，即均匀存储器存取UMA（ Uniform Memory Access）模型、非均匀存储器存取NUMA（ Nonuniform Uniform Memory Access）模型和只用高速缓存的存储器 结构COMA（Cache Only Memory Architecture）。其区别在于存储器 和外部资源如何共享或分布。 图8.19 UMA多处理机模型 （1）UMA模型 UMA结构如图8.19所示，通过互连网络把各处理机及存储器模块 均匀地连接起来。存储器为所有处理机均匀共享，且具有相同的访问时 间。每台处理机有自己的Cache和外围设备，这些设备也可以某种方式 为其它处理机所共享。 图8.20 NUMA多处理机模型 （2）NUMA模型 非均匀存储器存取多处理机的体系结构如图8.20所示，共享存 储分布在各处理机的本地存储器上，处理机访问存储器的时间因与 存储单元所在的位置而有所不同，主要因为网络传送而引起的附加 时间。所有本地存储器的集合构成全局存储空间，可被所有的处理 机访问。 图8.21 COMA多处理机模型 （3）COMA模型 如图8.21所示，是一种只用高速缓冲存储器的多处理机，可以说是 NUMA的特例，它把NUMA中的分布式主存用高速缓存来取代。在每一个 处理机结点上没有存储器的层次结构，而是将全部高速缓存组成全局存 储器空间。对于远程高速缓存的访问，可借助分布高速缓存目录来进行 。图8.21中，P表示处理机，C表示高速缓冲存储器，D表示高速缓存目 录。 2. S2MP体系结构 S2MP（Scalable Shared-Memory MultiProcessing）可称为新一代 的共享存储器并行多处理机，其示意如图8.22（a）所示，有效地解决 了共享主存的并行多处理机的可扩展性。 图中可以看出，每一个结点都由两个部分组成，即微处理器和存 储器。而存储器又由Cache和主存组成。每个结点通过高速网络互连， 使分布式存储器为所有处理器所共享。高速缓存Cache采用基于目录的 Cache一致性协议，即通过维护指向每一个存储块的Cache的指针实现 一致性。 图8.22 S2MP体系结构示意图 目录存储器的每一个记录对应于主存的一个存储块，其“状态”位 表示存储块的状态uncached/shared/dirty；“存在”对应一个结点的 Cache，表示该Cache是否有主存块的副本。另外S2MP系统支持页 迁移算法，可把某处理机经常使用的数据迁移到该结点的本地存储 器上，缩短访存时间，使存储带宽提高。 目前，共享存储器型多处理机已普遍使用，例如采用S2MP体系 结构的SGI Origin2000系列服务器、Stanford DASH以及Cray T3D等 。 3.SGI Origin 2000系列服务器 SGI公司将Cray Research子公司的开关网络技术应用到S2MP结构中 ，推出了Origin 2000系列可扩展服务器。目前主要包括Origin 200、Origin 2000 Deskside、Origin 2000 Rack和Cray Origin 2000等4种机型。其中 Origin 200是入门级服务器，扩展能力较小，最多可扩展为4个处理器； Origin 2000 Deskside桌边服务器支持的处理机数最多为8个；Origin 2000 Rack机柜服务器支持的处理器数最多为16个；Cray Origin 2000具有大规模 扩展能力，最多可达128个。且可扩展Web服务、数据仓库，提供可视化服 务，可用于科学计算、图形图像处理及仿真等领域，可作为大中小企业、 银行、商务中心及政府机关的信息管理服务器。 基于S2MP结构的Origin 2000系统最多可扩展至1024个处理器，具有 高带宽和低延时特性，通过一种多重交叉开关互连技术将分布在每个处理 器结点上的存储器从逻辑上连接成单一寻址空间的共享存储器系统。Cache 一致性的维护采用的是基于目录的协议，因此在每个结点上设有目录存储 器。基本结构与特点： （1）结点板 结点板也就是主板，也是Origin 2000服务器的一个处理器结点，其 组成如图8.23所示。每一个结点板拥有12个R10000处理器，设有本地 存储器，采用二级Cache，并设有用于Cache一致性维护的目录存储器、 用于网络互连的HUB ASIC芯片、1个I/O接口和1个路由器接口。 R1000属于RISC结构，配置1MB/4MB的二级Cache，其中带 1MBCache的R10000处理器的主频为180MHz，带4MBCache的R10000处 理器的主频为195MHz。Origin 2000系统主存分布在各个结点板上，但 是从整体上构成单一的地址空间，为所有处理器所共享。结点板上的 HUB用来连接处理器、主存储器、目录存储器及外部互连网络。 图8.23 Origin 2000结点板 （2）HUB ASIC 结点上的HUB结构如图8.24所示，是一个4端口的交叉开关，有4个 双向端口，每个端口的单向传输速率峰值达800MB/S，因此双工带宽 可达1.6GB/S。 这4个端口分别连接到处理器、主存、XIO I/O和路由 器，通过路由器连接到CrayLink互连网络上。4个端口在内部通过交叉 开关互连，以消息的方式通信。由HUB控制结点内部各子系统间的通 信，控制与其它结点板HUB的通信，并且对内部消息的Request/reply 格式与外部消息Crosstalk或CrayLink Interconnect格式进行转换。其消 息可分为请求（Request）与应答（Reply）两种，对于内部消息由处 理器和I/O设备初始化。 端口中设有两个FIFO队列，一个用于处理请求，一个用于处理应 答。对于Cache一致性协议有单独的逻辑请求和应答路径，可避免死锁 ，其消息（Read或Write）被相应的接口转换成CrayLink Interconnect 请求，送达目标结点的存储器或I/O接口。再依据目录状态，由目标结 点送回应答或者发送新的请求。 图8.24 HUB ASIC结构 （3）I/O子系统 Origin 2000的I/O子系统是由一组高速Crosstalk（XTALK）链路 构成，采用分布式结构，在每一个结点板上有一个I/O端口，可被每一 个处理器访问。每一I/O端口通过结点板上的单端口Crosstalk协议的链 路控制，或者通过在Crosstalk（XBOW）ASIC芯片上的智能交叉开关 互连。Origin 2000 I/O子系统的核心可谓XBOW ASIC芯片，可将单个 Crosstalk I/O端口扩展到8个，其中6个用于输入输出，2个用于与结点 板连接。 与Crossbow连接的设备可以是PCI、VME、SCSI、Ethernet、 ATM、FibreChannel等I/O设备。在Crosstalk协议控制下，通过编程可 进行8位或16位通信。XBOW ASIC有动态交叉开关，通过扩展两结点板 上的Crosstalk端口，可连接成6个16位的I/O端口，传送8位/16位数据 。在一个结点板上至少连接一个Crossbow端口，最多连接两个。 XBOW ASIC芯片通过交叉开关可动态地将每一个端口连接到指定的I/O 设备，比如结点板、图形板、串行I/O设备等。 （4）互连网络子系统 亦称为路由器，通过外部电缆可连接成各 种拓扑结构，把许多点到点的 链路连接起来,形成mesh（网状）网。这些链路和开关允许 多个传输同时 进行，速度很高，每条双向链路峰值带宽可达1.6GB/S；且不需要仲裁，也 不存在竞争。 图8.25 连接8个结点板的Hypercube 这种互连网络在每对Origin 2000结点之间至少提供两条独立的链 路，进行通信。这样，可绕过不能运 行的路由器或断开的链路。每条链路 按照链路层协议运行，进行CRC校 验 ，且可重试失败传输，以提高容错能 力。图8.25所示是连接8个结点板而成 的Hypercube。其中R0和R1、R2和R3、 R4和R6、R5和R7可以同时通信，也不 会中断任何其它结点的运行。 （5）路由器 在互连网络子系统中，通过路由器将结点板上的HUB ASIC连接到 外部CrayLink Interconnect上，由CrayLink Interconnect为结点提供高带 宽、低延时的互连机制。路由器实现一套路由协议，保证在链路出错时 仍能可靠地交换数据，并进行流量控制和优先级管理。路由器的核心是 实现6路无阻塞交叉开关的路由ASIC芯片。其中交叉开关允许6个路由端 口全双工同时操作，每个端口有2条单向数据通路。路由器性能与功能可 概括如下： 选择发送和接收端口高效连接，保存接收到的数据，动态地切 换6个端口的连接； 在CrayLink Interconnect链路层协议的控制下，与其它路由器 和HUB通信； 为了减少延时，消息通过Wormhole方式通过路由器； 缓存CrayLink信息； 所提供的峰值通信带宽达9.36GB/S。 （6）分布式共享存储器地址空间 Origin 2000服务器采用分布式存储器结构，但是具有单一共享存储 器地址空间，通过互连网络可被所有的处理器访问。I/O设备分布在一个 共享地址空间，每台设备在整个系统中可为所有的处理器全局寻址。 存储器系统分为四个层次。最里层是接近于CPU的寄存器，与CPU在同 一芯片中；第二层是Cache，有主Cache和二级Cache两层，主Cache在 R10000芯片中，二级Cache在与处理器紧耦合的板子上；第三层是本地存 储器，与处理器在同一块结点板上，包括主存和目录存储器；第四层是远 程Cache，用于存放指定的存储块。通常，Cache采用SRAM构成。尽管数 据是在本地或远程存储器中存储，但是它们的映像可能在多个结点板上的 Cache中，由HUB ASIC实现Cache一致性协议。 （7）C ache一致性 存储器中的数据可被所有的处理器和Cache所共享。把数据存入Cache 可减少访存时延，但是使Cache的一致性复杂化。这里采用基于目录的 Cache一致性协议来解决，以保证不管哪一个处理器访问该数据单元都能 得到最新数据。 由于存储器整体分布在各个结点板上，目录表也分布在各个结点板上 ，即目录存储器。目录项存放的信息是系统存储块的全局缓存状态和指向每 个对该存储块进行映像的Cache位向量指针。如图8.26所示，通过检查状态 和位向量，存储器可以确定哪些Cache在某次访存操作中需要参与操作，以 保持一致性。 图8.26 基于目录的Cache一致性 存储块有四个状态，Unowned（缓存映像不存在）、Exclusive（ 只有一个 Cache缓存映像）、Shared（有多个Cache缓存映像）、 Poisoned（该存储块所在的页已经迁移到其它结点）。这样，只有那 些存放有被访问存储块的Cache需要通知，参与一致性的相关操作。这 一特点保证了系统不会因为支持Cache一致性而影响带宽的可扩展性， 避免了Snoopy协议占用太多带宽的缺点。 基于目录的Cache一致性协议可采用两种维护