资源简介

(共109张PPT)
第11章 多处理机与机群系统
11.1 多处理机系统特点与分类
11.2 多处理机软件和典型的多处理机系统
11.3 机群系统
关联
习题
11.1 多处理机系统特点与分类
　　多处理机具有两台以上处理机，每台处理机可以带有本地Cache、本地存储器、甚至I/O设备，它们都能独立执行各自的程序。多台处理机之间通过总线、纵横交叉开关、多级互连网络或高速的商品化网络实现互连。多处理机可以通过共享存储器，也可以通过消息传送系统来实现处理机间的通信。多台处理机在操作系统的控制下，实现资源的统一分配与调度。具有多任务处理，协同求解，提高速度的特点，并利用冗余，提高可靠性、适应性、可用性。为了不同的目的，使用不同的技术途径，可以发展出同构型、异构型、分布型等形式各异的多处理机系统。
11.1.1 基本结构
　　多处理机是指两个或两个以上处理机(包括PU和CU)，通过高速互连网络连接起来，在统一的操作系统管理下，实现指令以上级(任务级、作业级)并行。按照Flynn分类法，多处理机系统属于MIMD计算机，多处理机系统由多个独立的处理机组成，每个处理机都能够独立执行自己的程序。
　　多处理机有两种基本的结构：共享存储器结构和分布式存储器结构。这两种结构的多处理机都是通过底层的互连网络实现数据的交换和同步的，如图11-1所示。
图 11-1 多处理机系统的两种基本结构
　　分布式存储器结构每台处理机都有自己的存储器和I/O设备，处理机之间通过点对点的信息交换实现通信。整个存储器被分成多个模块，每个模块与一个处理机紧密结合，因此这种结构的存储模块也被称为本地存储器。当处理机访问本地存储器时，不需要通过互连网络就可以直接进行，但是，系统内的任意一个处理机仍然可以通过互连网络访问系统中的任何一个存储器模块。
11.1.2 多处理机系统特点
　　多处理机属于多指令流多数据流(MIMD)计算机，它和单指令流多数据流(SIMD)计算机的并行处理机相比，有很大的差别。它们的差别归根结底来源于并行性级别的不同：多处理机要实现任务一级的并行，不能再像SIMD计算机那样只能对多数据流执行同一指令操作。因此，在结构上，它的多个处理机要用多个指令部件分别控制，并且要有复杂的互连网络实现机间通信；在算法上，不限于数组向量处理，要挖掘和实现更多通用算法中隐含的并行性；在系统管理上，要更多依靠软件手段有效地解决资源管理，特别是处理机管理以及进程调度等问题。下面概括说明多处理机系统的特点。
　　1．结构灵活性
　　多处理机能适应更为多样的算法，具备更为灵活多变的系统结构以实现各种复杂的机间互连模式，同时还要解决共享资源的冲突问题。
　　2．程序并行性
　　在多处理机中，不限于解决数组向量处理问题，并行性存在于指令外部，即表现在多个任务之间，再加上系统通用性的要求，就使程序并行性的识别难度较大。因此，它必须利用多种途径，如算法、程序语言、编译、操作系统，以至指令、硬件等，尽量挖掘各种潜在的并行性，而且主要的责任不能放在程序员肩上。
　　3．并行任务派生
　　多处理机是处于多指令流操作方式，一个程序当中就存在多个并发的程序段，需要专门的指令来表示它们的并发关系以控制它们的并发执行，以便一个任务开始被执行时就能派生出可与它并行执行的另一些任务，这个过程称为并行任务派生。
　　4．进程同步
　　多处理机所实现的是指令、任务、程序级的并行。一般地说，在同一时刻，不同的处理机执行着不同的指令。这就要求多处理机采取特殊的同步措施，才能使并发进程之间保持程序所要求的正确顺序。 　　
　　5．资源分配和进程调度
　　多处理机执行并发任务，需用处理机的数目没有固定要求，各个处理机进入或退出任务的时刻互不相同，所需共享资源的品种、数量又随时变化。由于上述情况十分复杂，于是，就提出了一个资源分配和进程调度问题，这个问题解决的好坏对效率有很大的直接影响。
11.1.3 多处理机系统的Cache一致性问题
　　Cache作为提高系统性能的一种技术手段在计算机系统中得到普遍的使用。在共享存储器的多处理机中，每台处理机都有自己的局部Cache。这类多处理机在运行一个具有多个进程的程序时，各处理机可能会使用到共享存储器中的同一数据块，为维持多处理机的高速运行，这些共享数据块将被调入各处理机的局部Cache中。由于多个处理机是异步地独立操作，可能使共享存储器中同一数据块的不同Cache拷贝出现不一致，就可能危及系统的正常运行，这就是Cache的一致性问题 。
　　1．产生Cache一致性问题的原因
　　出现Cache一致性问题的原因主要有三个：共享可写的数据、进程迁移、I/O传输。
　　1) 共享可写数据引起的不一致
　　假设在写操作之前，Cache的初始状态如图11-2(a)所示。处理机P1和P2的局部高速缓冲存储器Cache1和Cache2中分别有共享存储器的某个数据x的副本。
图11-2 共享可写数据引起的Cache不一致性
　　若采用写直达法，如图11-2(b)所示，当处理机P1改写Cache1中的数据为x' 时，共享存储器中的相应数据也立即更新为x' ，这将导致Cache1中的数据与Cache2中所缓存的数据不一致。 若采用写回法，如图11-2(c)所示，当处理机P1改写Cache1中的数据为x' 时，Cache1的变化不会引起Cache2和共享存储器的变化，这将导致Cache1中的数据与共享存储器和Cache2中所缓存的数据不一致。
　　2) 进程迁移引起的不一致
　　在多处理机上，有时为了提高系统的效率而允许进程迁移，将一个尚未执行完而被挂起的进程调度到另一个空闲的处理机上去执行，使系统中各处理机的负荷保持均衡。但这样做可能会造成Cache一致性问题。
　　假设在迁移前Cache的初始状态仍如图11-3(a)所示，处理机P1的Cache1中有共享存储器中数据x的拷贝，而处理机P2的Cache2中没有该数据。
图11-3 进程迁移引起的Cache不一致性
　　若采用写直达法，如图11-3(b)所示，当某进程从P1迁移到P2后，处理机P2在执行此进程时需要使用数据x时，会将x所在块由共享存储器调入Cache2。假设进程运行时将Cache2的数据x改写为x' ，在共享存储器中的相应数据也立即更新为x' ，这将导致共享存储器和Cache2中的数据与处理机P1中Cache1所缓存的数据的不一致。
　　若采用写回法，如图11-3(c)所示，当处理机P1修改Cache1中的数据成x' 时Cache1的变化不会引起共享存储器的变化。当某进程从P1迁移到P2后，处理机P2在执行此进程时需要使用数据x时，会将x所在块由共享存储器调入Cache2。此时调入的数据x并非是已经修改过的x' ，这将导致共享存储器及Cache2与处理机P1中Cache1所缓存的数据的不一致。
　　3) I/O操作引起的不一致
　假设在执行I/O操作之前，Cache的初始状态如图11-4(a)所示。处理机P1和P2的局部Cache中分别有共享存储器的某个数据x的拷贝。
　　若采用写直达法，当I/O处理机执行输入操作，直接将共享存储器中的数据x改写成x' 时，会导致Cache1和Cache2中的数据与共享存储器数据的不一致，如图11-4(b)所示。若采用写回法，当处理机P1将Cache1中的数据x改写为x' 时，由于Cache1数据的修改不会立即引起共享存储器中数据x的更新，此时若此数据恰好被I/O处理机输出，就会造成输出错误，如图11-4(c)所示。
图11-4 I/O操作引起的Cache不一致性
　　2．解决Cache一致性问题的方法
　　解决多处理器维护Cache一致性的协议称为Cache一致性协议。实现Cache一致性协议的关键是跟踪共享数据块的状态。目前有两类Cache一致性协议，它们采用了不同的共享数据状态跟踪技术，分别适合于不同的系统结构。
1) 监听协议
　　每个Cache除了包含物理存储器中块的数据拷贝之外，也保存着各个块的共享状态信息。这是一种基于总线的一致性协议，各处理机通过监听总线上处理机与存储器之间的Cache操作事件，对各自局部Cache中的数据采取保持一致性的措施。监听协议有写无效策略和写更新策略两种策略来保持Cache一致性。
　　2) 目录协议
　　物理存储器中共享数据块的状态及相关信息均被保存在一个称为目录的地方。共享数据块的变化通过此数据块所在的各目录项，将一致性命令发给所有存放该数据块拷贝的Cache。基于目录的协议的基本思想是：使用Cache目录来记录可以进入Cache的每个数据块的访问状态、该块在各个处理机的共享状态以及是否修改过等信息。把一致性命令只发给存有相应数据块拷贝的Cache，从而支持Cache的一致性。各种目录协议的主要差别是目录存放什么信息以及如何维护信息。根据目录的结构特点，基于目录的协议可分为三类：全映射目录(full-map directory)、有限目录(limited directory)、链式目录(chained directory)。
　　另外，还有一种方法是以软件为基础解决Cache一致性的问题。
11.2 多处理机软件和典型的多处理机系统
11.2.1 并行算法
　　算法对于并行性的开发至关重要，算法必须适应具体的计算机结构。对表达式E1=a+bx+cx2+dx3，顺序算法与并行算法的比较如图11-5所示。如果将运算过程用树形流程图来表示的话，则运算的级数就是树的高度，用Tp代表；P为所需处理机数目；Sp为加速比，Sp=Tl/Tp；Ep为效率，Ep=Sp/P。
图11-5 顺序算法与并行算法比较图
　　对树进行变换来降低树高，减少运算级数，即可提高运算的并行性。树形结构可以用交换律、结合律、分配律来变换。先从算术表达式的最直接形式出发，利用交换律把相同的运算集中在一起；再利用结合律把参加运算的操作数(称原子)配对，尽可能并行运算，组成树高最小的子树；最后利用分配律，平衡各分支运算的级数，把这些子树结合起来，使总级数减至最少。
11.2.2 程序并行性分析
　　除算法以外，任务间能否并行在很大程度上还取决于程序的结构形式。
　　假设一个程序包含P1、P2、…、Pi、…、Pj、…、Pn等n个程序段，其书写的顺序反映了该程序正常执行的顺序。为了便于分析，设Pi和Pj程序段都是一条语句，Pi在Pj之前执行，且只讨论Pi和Pj之间的直接数据相关关系。
　　1) 数据相关
　　如果Pi的左部变量在Pj的右部变量集内，且Pj要从Pi取得运算结果来作为操作数，则称Pj“数据相关”于Pi。如
Pi A = B + D
Pj C = A * E
　　Pj必须取Pi算得的A值作为操作数，相当于流水中发生的“先写后读”相关。
　　2) 数据反相关
　　如果Pj的左部变量在Pi的右部变量集内，且当Pi未取用其变量的值之前，不允许被Pj所改变，则称Pi“数据反相关”于Pj。如
Pi C = A * E
Pj A = B + D
　　在A的值未被Pi取用之前不能被Pj所改变，相当于流水中发生的“先读后写”相关。
　　3) 数据输出相关
　　如果Pi的左部变量也是Pj的左部变量，且Pj存入其算得的值必须在Pi存入之后，则称Pj“数据输出相关”于Pi。如
Pi A = B + D
Pj A = C + E
　　Pj存入其算得的A值必须在Pi存入其结果A之后，相当于流水中发生的“写－写”相关。
　　对程序并行性的影响表现为下列几种可能的执行次序：写－读串行次序、读－写次序、可并行次序、必并行次序。
　　综上所述，两个程序段之间若有先写后读的数据相关，不能并行，只在特殊情况下可以交换串行；若有先读后写的数据反相关，可以并行执行，但必须保证其写入共享主存时的先读后写次序，不能交换串行；若有写－写的数据输出相关，可以并行执行，但同样需保证其写入的先后次序，不能交换串行；若同时有先写后读和先读后写两种相关，以交换数据为目的时，则必须并行执行，且要求读写完全同步，不许顺序串行和交换串行；若没有任何相关，或仅有右部源数据相同时，可以并行、顺序串行和交换串行。
11.2.3 并行程序设计语言
　　并行算法需要用并行程序来实现，而编写并行程序所用的程序语言中需要含有能明确表示并发进程的成分，这就要使用并行程序设计语言。并行进程的特点是多个进程在时间上重叠地执行，而并行程序设计语言必须便于具体描述这些并行关系。
　　1．描述程序并行性的语句
　　包含并行性的程序在多处理机上运行时，需要对并行任务的派生和汇合进行管理。
　　并行任务的派生和汇合通常是用软件手段来控制的。要在程序中反映出并行任务的派生和汇合关系，可以在程序语言中使用FORK 语句来派生并行任务，用JOIN语句来实现对多个并发任务的汇合，读者如感兴趣，请参考相关资料。
　　2．并行编译
　　实现算术表达式的并行处理可以应用并行算法编制并行程序，还可以依靠并行编译程序。有一些编译算法，可以经过或不经过逆波兰式，直接从算术表达式产生能并行执行的目标程序。例如，对下列表达式：
Z = E+A*B*C/D+F
利用普通串行编译算法，产生三元指令组为：
　　　1 *AB
2 *1C
3 /2D
4 +3E
5 +4F
6 =5Z
　　指令之间均相关，需5级运算。如采用并行编译算法可得
　　　　　 1 *AB
2 /2D
3 *12
4 +EF
5 +34
6 =5Z
其中，1，2为第1级；3，4为第2级；5，6为第3级。分配给两个处理机，只需3级运算即可实现。
11.2.4 MPP和SMP
　　多处理机系统主要有四大类。第一类是多向量处理系统，以CRAY YMP-90、NEC SX-3和FUJITSU VP-2000等为代表；第二类是基于共享存储的多处理机系统，如SGI Challenge 和Sun SparcCenter 2000；第三类是基于分布存储的大规模并行处理系统(MPP)，比如Intel Paragon、CM-5、Cray T3D等；第四类是机群系统。
　　1．MPP大规模并行性并行处理
　　大规模并行性并行处理(Massively Parallel Processing，MPP)系统的定义随着时间推移在不断地变化。按照当前的标准，具有几百或几千台处理机的任何机器就是大规模并行处理系统。显然，随着计算机技术的快速发展，对并行度的要求会愈来愈高。
　　MPP系统最重要的特点是进行大规模并行处理。MPP主要用于半导体建模、飞行动力学、气候模型、流体湍流、污染分析、人类染色体组、海洋环流、量子染色动力学等需要大量数值处理的领域。
　　我们以1983年美国的128×128=16 384个微处理器(MPU)所组成的并行处理机为例进行说明。此系统总结构如图11-6所示。其主要部分有128×128个处理机的阵列、驿站存储器(Staging Memory)、阵列控制部件、宿主机。其中处理机的阵列由2048个处理机芯片组成，每个芯片上有8个处理机，组成2×4的子阵列， 每个处理机附有一个1024位的RAM，16 384个处理机可以并行工作。
图11-6 MPP的系统结构图
　　MPP阵列的另一改进是在物理布局中增加了4列冗余的处理机（物理布局总数为132列）。当有处理机发生故障时，可以动态地进行重新组合，把存在故障的处理机旁路掉，因而极大地提高了系统的可靠性。 在阵列的上下各有一排128位的开关，分别用来输入输出数据。MPP的时钟频率为10 MHz，每个时钟周期可以并行传送128位数据， 使最大传送速率可达到1.28×109 bit/s，即160 MB/s。
　　驿站存储器容量为64 MB，主要用来作为处理机阵列的输入/输出缓冲器，它以320 MB/s的速度从外部设备接收数据，并能对数据进行压缩或重新安排格式的处理，使这些数据能更有效地在处理机阵列中进行处理。
　　阵列的控制部件实际上是一台专用计算机，执行MPP汇编语言，除了控制数据的输入/输出通路外，还要执行存储在它的程序存储器中的应用程序，其功能包括进行循环的控制、子程序的调用及进行标量运算。MPP系统用一台VAX 11/780机作宿主机，整个系统在VAX 11/780机总的管理下工作。PE是位片式的处理机，它的算术运算用串行加法器按位串行进行，可处理任意长度的操作数。
　　MPP的指令系统可分为三个子集：顺序指令、并行指令和接口指令。与大多数SIMD计算机一样，MPP还有一组接口指令，它们使数据在顺序部件和并行部件之间移动。MPP系统软件设计的基本准则是：用户像使用单机那样使用MPP，但其性能却是单机系统的若干倍
　　2．SMP共享存储型多处理机
　　SMP称为共享存储型多处理机(Shared Memory Multiprocessors)，也称为对称型多处理机(Symmetry Multiprocessors)。
　　共享存储系统拥有统一寻址空间，程序员不必参与数据分配和传输。早期的并行处理系统几乎都是基于总线的共享存储系统，它们的发展得益于两方面的原因：一个是微处理器令人难以置信的性能价格比，另一个是在基于微处理器的并行处理系统中广泛使用的Cache技术。
　　这些因素使得将多个处理器放到同一条总线上，共享单一存储器成为可能，并通过Cache将所有处理器访问存储器所需的存储带宽降低到可以接受的水平。 Cache一致性是通过监听协议实现的。这种实现方式虽然简单，但是阻碍了系统的扩展能力。
　　SMP有三种模型，下面将分别作简单的介绍。
　　1) UMA多处理机
　　均匀存储器存取模型(Uniform Memory Access，UMA)是指存储器被所有处理机均匀共享，所有处理机对所有存储单元具有相同的存取时间，每台处理机有局部Cache，同时外围设备可以共享，如图11-7所示。
图11-7 UMA多处理机系统结构图
　　2) NUMA多处理机
　　非均匀存储器存取(Non-Uniform Memory Access，NUMA)模型是指存储器访问时间随存储单元的位置不同而变化。共享存储器在物理上是分布在所有处理机中的本地存储器，所有局部存储器地址空间的集合就组成了全局地址空间。
　　处理机访问本地存储器比较快，访问属于另一台处理机的远程存储器则比较慢，因为通过互连网络会产生附加的时间延迟，如图11-8所示。
图11-8 NUMA多处理机系统结构图
　　3) COMA多处理机
　　COMA只有Cache的存储器结构(Cache-Only Memory Architecture)模型是一种只用Cache的多处理机系统。实际上，COMA模型是NUMA模型的一种特例，只是后者分布存储器换成了Cache，同时在每个处理机结点上没有主存储器，全部Cache组成了全局虚拟地址空间。特点表现在远程Cache访问通过分布Cache目录进行，共享存储系统拥有统一的寻址空间，程序员不必参与数据分配和传输等。如图11-9所示。
图11-9 COMA多处理机系统结构图
　　MPP和SMP的区别如下所述：SMP(Symmetric Multi Processing)，对称多处理系统内有许多紧耦合多处理器，在这样的系统中，所有的CPU共享全部资源，如总线、内存和I/O系统等，操作系统或管理数据库的复本只有一个，这种系统有一个最大的特点就是共享所有资源。MPP(Massively Parallel Processing，大规模并行处理系统)，这样的系统是由许多松耦合的处理单元组成的。要注意的是，这里指的是处理单元而不是处理器。每个单元内的 CPU都有自己私有的资源，如总线，内存，硬盘等。在每个单元内都有操作系统和管理数据库的实例复本。这种结构最大的特点在于不共享资源。
　　既然有两种结构，那它们各有什么特点呢？采用什么结构比较合适呢？通常情况下，MPP系统因为要在不同处理单元之间传送信息（请注意上图），所以它的效率要比SMP要差一点，但是这也不是绝对的，因为MPP系统不共享资源，因此对它而言，资源比SMP要多，当需要处理的事务达到一定规模时，MPP的效率要比SMP好。这就是看通信时间占用计算时间的比例而定，如果通信时间比较多，那MPP系统就不占优势了，相反，如果通信时间比较少，那MPP系统可以充分发挥资源的优势，达到高效率。当前使用的OTLP程序中，用户访问一个中心数据库，如果采用SMP系统结构，它的效率要比采用MPP结构要快得多。
　　而MPP系统在决策支持和数据挖掘方面显示了优势，可以这样说，如果操作相互之间没有什么关系，处理单元之间需要进行的通信比较少，那采用MPP系统就要好，相反就不合适了。
　　对于SMP来说，制约它速度的一个关键因素就是那个共享的总线，因此对于DSS程序来说，只能选择MPP，而不能选择 SMP，当大型程序的处理要求大于共享总线时，总线就没有能力进行处理了，这时SMP系统就不行了。当然了，两个结构互有优缺点，如果能够将两种结合起来取长补短，当然最好了。
11.2.5 CM-5系统
　　Connection Machine系列的CM-5是Thinking Machines公司为实现3T性能目标(1 TFlops的计算速度、1 TB主存储器和1 TB/s输入/输出系统频带)而推出的MPP系统。
　　1．CM-5的系统结构
　　CM-5机器包含32～16 384个处理器结点。每个结点有一台32 MHz的SPARC处理机，32兆字节的存储器和可以执行64位浮点和整数操作，速度为128 Mflops的向量处理部件。系统采用若干台SUN公司的工作站计算机作为控制处理机。控制处理机的数目根据配置的不同而可从1台到几十台变化。每个控制处理机根据需要配有存储器和磁盘。系统的输入和输出通过高频宽的I/O接口与图形设备、海量辅助存储器以及高性能网络相连。与控制处理机相连的以太网提供低速I/O功能。配置在最大时的占地面积为30 m×30 m，峰值速度可望超过1 Tflops。
　　如图11-10所示，CM-5系统有三个网络：数据网络、控制网络和诊断网络。数据网络和控制网络通过网络接口与处理结点、控制处理机和I/O通道相连。数据网络用于提供处理结点之间高性能点对点的数据通信。控制网络用于提供协同操作，包括广播、同步、扫描和系统管理功能。诊断网络允许从“后门”访问所有的系统硬件以便测试系统完整性，检测和隔离错误。
图11-10 CM-5计算机的系统结构
　　CM-5系统结构是一种通用结构，它对大型复杂问题的数据并行处理，进而获得比较理想的结果。数据并行可用SIMD模式、多SIMD模式或者同步的MIMD模式实现。
　　2．CM-5的网络结构
　　CM-5的网络结构包括数据网络、控制网络和诊断网络。
　　1) 数据网络
　　数据网络是以Leiserson提出的胖树概念为基础设计的。胖树很像一棵真正的树，叶子越多，它将变得越粗。处理结点，控制处理机和I/O通道都位于胖树的叶子上。树的内部结点都是开关。与一般的二进制树不同，从叶子到根，胖树的通道能力也随着增加。
　　2) 控制网络
　　该系统结构是一棵完全二叉树。所有的系统部件都在叶子上。可以给每个用户分区分配一棵网络子树。处理结点位于子树的叶子处，控制处理机位于分区另外的叶子上。控制处理机执行代码中的标量部分，而处理结点执行数据并行部分。
　　3) 诊断网络
　　允许一组盒子按“超立方体编址”模式进行编址。一个专用的诊断接口用来对系统内部支持JTAG(Join Test Action Group)标准的所有CM-5芯片以及所有的网络进行总体测试。它可以扫描访问支持JTAG标准的所有芯片以及可编程访问特定的非JTAG芯片。网络本身是完全可测试和可诊断的。它能够发现和排除机器的故障或掉电部件。
　　3．控制处理机和处理结点
　　控制处理机如图11-11所示，基本的控制处理机由RISC微处理器(CPU)、存储器子系统、带本地磁盘和以太网连接的I/O以及CM-5网络接口组成。它相当于一个流行的标准工作站类计算机系统。网络接口通过控制网络和数据网络将处理机与系统的其它部分相连。
　　图11-12给出了处理结点的基本结构。它是一台有存储器子系统的基于SPARC的微处理机。存储器子系统由存储器控制器和8 MB、16 MB或32 MB的DRAM存储器组成。内部总线宽度为64位。
图11-11 CM-5控制处理机
图11-12 CM-5处理结点基本结构图
11.2.6 SGI Origin 2000系列服务器
　　到20世纪80年代中期，对可扩展的多处理器系统的需求不断增长。基于总线的、Cache一致性、共享单一存储器的机器显然是不可扩展的。1996年，随着SGI Origin 2000系列服务器的推出，一种称为S2MP的并行计算机体系结构受到了人们广泛的注意。S2MP全称为可扩展共享存储多处理(Scalable Shared-memory MultiProcessing)技术。S2MP系统将大量高性能微处理器连接起来，共享一个统一的地址空间，较好地解决了其他并行处理系统无法解决的问题。S2MP是一种共享存储的体系结构，如图11-13所示。
图11-13 S2MP系统的体系结构
　　和大规模的消息传递系统相比，它支持简单的编程模型，系统使用方便，是对SMP系统在支持更高扩展能力方面的发展。共享存储系统降低了通信的额外开销，因此系统也可以运行细粒度的应用。S2MP着眼于扩展性能的研究，和传统的基于总线的共享存储并行处理系统相比，它不存在系统中可以连接的处理器数目的总线带宽的限制。
　　S2MP作为大规模多处理系统，主要问题仍然是解决系统的可扩展和易编程能力。S2MP系统采用分布式存储器技术，引入Cache，降低了访存时延。
　　S2MP系统实际上是一种NUMA结构，每个结点由处理器和存储器两部分组成，存储器靠近处理器，而不是集中在某个地方，处理器可以访问本地存储器获取数据，NUMA结构可以降低平均访存时延，并且随处理器数目的增加自动增加存储器带宽，也就是说，存储带宽是可扩展的。由于在某个结点上访问本地存储器可以和其他结点板上的访存并行进行，系统的总带宽可以随着系统的规模而扩充。
　　SGI公司将Cray Research子公司的开关网络技术应用到S2MP系统中，将SMP、MPP及工作站机群系统的优点结合起来，推出Origin 2000系列可扩展服务器产品。Origin 2000系列服务器结构主要涉及到结点板、扩展连接方式、I/O子系统、互连网络子系统、分布共享存储地址空间和系统时延。请读者自行参考相关信息。
11.3 机 群 系 统
　　机群系统是指利用高速网络将一组计算机结点按某种结构连接起来，并在并行程序设计以及可视化人机交互集成开发环境支持下，统一调度、协调处理，实现高效并行处理的计算机系统。本节介绍机群系统的结构特点、关键技术及其提高通信系统的性能，并给出几种典型的机群系统。
11.3.1 机群系统的结构特点
　　从结构和结点间的通信方式来看，机群系统属于分布存储系统，主要利用消息传递方式实现各主机之间的通信，由建立在一般操作系统之上的并行编程环境完成系统的资源管理及相互协作，同时也屏蔽了工作站及网络的异构性，对程序员和用户来说，机群系统是一个整体的并行系统。机群系统中的主机和网络可以是同构的，也可以是异构的。目前已实现和正在研究中的机群系统大多采用现有商用工作站和通用LAN网络，这样既可以缩短开发周期又可以利用最新的微处理器技术；大多数机群系统的并行编程环境也是建立在一般的UNIX操作系统之上，尽量利用商用系统的研究成果，减少系统的开发与维护费用。
　　机群系统之所以能够从技术可能发展到实际应用主要是它与传统的并行处理系统相比有以下几个明显的特点：
　　1．开发周期短
由于机群系统大多采用商用工作站和通用LAN网络，使结点主机及系统管理相对容易，可靠性高。开发的重点在通信和并行编程环境上，既不用重新研制计算结点，又不用重新设计操作系统和编译系统，这就节省了大量的研制时间。
　　2．用户投资风险小
　　用户在购置传统巨型机或MPP系统时很不放心，担心使用效率不高，系统性能发挥不好，从而浪费大量资金。而机群系统不仅是一个并行处理系统，它的每个结点同时也是一台独立的工作站，即使整个系统对某些应用问题并行效率不高，它的结点仍然可以作为单个工作站使用。
　　3．价格低
　　由于生产批量小，传统巨型机或MPP 的价格都比较昂贵，往往要几百万到上千万美元。工作站或高档PC机由于它们是批量生产出来的，因而售价较底。由近十台或几十台工作站组成的机群系统可以满足相当多数应用的要求，而价格却比较低。
　　4．节约系统资源
　　由于机群系统的结构比较灵活，可以将不同体系结构，不同性能的工作站连在一起，这样就可以充分利用现有设备。单从使用效率上看，机群系统的资源利用率也比单机系统要高得多。UC Berkeley计算机系100多台工作站的使用情况调查表明，一般单机系统的使用率不到10%，而机群系统中的资源利用率可达到80%左右。另一方面，即使用户设备更新，原有的一些性能较低或型号较旧的机器在机群系统中仍可发挥作用。
　　5．扩展性好
　　从规模上说，机群系统大多使用通用网络，系统扩展容易；从性能上说，对大多数中、粗粒度的并行应用都有较高的效率。清华大学计算机系研制的可扩展机群系统上测试的结果表明8台工作站的加速比可以达到5.83～7.9，并行处理的效率为72.88%～99%。
　　6．用户编程方便
　　机群系统中，程序的并行化只是在原有的C、C++ 或Fortran串行程序中插入相应的通信原语。用户使用的仍然是熟悉的编程环境，不用适应新的环境，这样就可以继承原有软件财富，对串行程序做并不很多的修改。
11.3.2 机群系统的关键技术　
　　对于并行处理系统，人们希望要有较高的结点运算速度，系统的加速比性能接近线性增长，并行应用程序的开发要高效、方便。目前，机群系统大多采用商用高性能工作站或高档PC，结点的运算速度问题不是很突出，因而主要的研究方面是在提高系统的并行效率、使系统的使用更为方便上，包括建立高效的通信系统，有效地管理全局资源和提供友好的并行应用程序开发环境等。
　　1．高效的通信系统
　　机群系统一般使用通用局域网连接，目前常用的局域网技术大体可以分成两类，一类是共享介质网络，最常见是10 Mb/s或100 Mb/s的Ethernet；另一类是开关网络，比如155 Mb/s/622 Mb/s的ATM、640 Mb/s/1.28 Gb/s的Myrinet和100 Mb/s的交换式Ethernet。对于共享介质网络，由于其聚合网络频带与单独链路频带是一样的，其性能会随网络负载的增加而下降，特别是对于某些负载比较集中的应用程序，这种影响会更明显，但是售价便宜，组成系统也相对容易，是组成中低档机群系统的一种较好的选择。
　　而开关网络则相反，其聚合网络频带比单独的链路频率带要高得多，理论上讲是N倍；除开关的交换延迟影响外，性能不会随网络负载的增加而降底很多，开关网络的另一个优点是其可扩展性较好，由于Wormhole、Cut-through等交换技术的发展，交换延迟已经很低，与发送/接收端的开销相比要小得多。比如，Myrinet开关的一次交换延迟小于1 ms，一个中等规模的机群系统(16～32台)的点-点的往返延迟仅有几十微秒。但是交换开关及相应接口卡的售价要高得多，组成机群系统的价格相对也比较高，对系统的普及有一定影响。
　　在不考虑网络负载的情况下，一般使用点-点的应用程序可见带宽和往返延迟来衡量通信系统的性能。应用程序可见带宽说明了网络的长消息包的传输性能，虽然由于网络技术的飞速发展，网络的物理链路越来越快，但是应用程序的可见带宽比起链路速度来要小得多，主要原因有网卡接口的硬件限制，协议处理开销和操作系统开销。例如，Myrinet的物理链路是双向的640 Mb/s，而在TCP/IP协议上点-点的应用程序可见带宽只有38 Mb/s。往返延迟是1字节或0字节数据消息包的往返传输时间，它说明了网络短消息包的传输性能。新的网络技术大幅度地提高了传输速度，但往返延迟没有太大变化。
　　2．并行程序设计环境
　　随着MPP和机群系统等分布存储结构并行系统的发展，开发出了PVM、MPI、Express、P4等基于Message Passing方式的并行程序设计环境，它为并行程序的设计和运行提供一个整体系统和各种辅助工具。功能包括提供统一的虚拟机、定义和描述通信原语、管理系统资源、提供可移植的用户编程接口和多种编程语言的支持。开发并行应用程序要比串行程序困难得多，它要涉及多个处理器之间的数据交换与同步，要解决数据划分、任务分配、程序调试和性能评测等问题，需要相应支持工具，比如并行调试器、性能评测工具、并行化辅助工具，它们对程序的开发效率与运行效率都有重要作用。目前，提供工具较完善的系统有FAUST、Express、TOPSYS和VIDE。
　　目前研制的机群系统大多支持PVM和MPI，除了能适应广泛的硬件平台和编程方便等特点之外，它们都是免费软件，可以方便地进行再开发，有利于系统的推广与应用。正是由于它们都是免费软件，所以在支持语言、容错及工具等方面都不完善，许多研究机构和大学正在做这方面的研究。
　　3．多种并行语言的支持
　　并行程序设计语言是并行系统应用的基础，已有的机群系统大多支持Fortran、C和C++,实现的方法主要是使用原有顺序编译器链接并行函数库，比如PVM、MPI，或者加入预编译，比如Multi-thread C、MPC++等。目前机群系统并行程序设计语言的研究主要在三个方面：① 扩展原有顺序语言，提供广泛的并行语言支持，例如，清华大学可扩展机群系统的ADA，MPC++。② 提供全新的并行语言，比如Occam。③ 研究自动化并行编译方法，直接将顺序程序编译成并行代码，目前比较成功的有UIUC 的Polaris、Stanford的 SUIF和复旦大学的AFT。
　　4．全局资源的管理与利用
　　有效地管理系统中的所有资源是机群系统的一个重要方面，常用的并行编程环境PVM、MPI等对这方面的支持都比较弱，仅提供统一的虚拟机。主要原因是，结点的操作系统是单机系统，不提供全局服务支持，同时也缺少有效的全局共享方法。UC Berkeley的NOW项目中提出，在一般操作系统(UNIX、Linux、Windows NT等)之上建立一个全局UNIX: GLUnix来解决机群系统中的所有资源管理，包括组调度、资源分配和并行文件系统。一般认为其中并行文件系统对提高系统的性能潜力最大，即所谓Terabytes >> Teraflops，就是说目前限制并行程序性能的因素主要来自I/O瓶颈，提高I/O性能的方法较之提高CPU速度更能增强并行系统的性能。
　　由于网络技术的发展，通信延迟越来越小，网络访问比本地磁盘访问要快得多。在155 Mb/s的ATM 网络上，读取其他结点的内存100 MB的时间是读取本地磁盘的五分之一。现在的工作站和高档PC 机都配有相当多的内存(32～64 MB)，整个机群系统的全部内存是一个很大的资源，利用其他结点的空闲内存作为本地结点的虚拟内存和文件缓存，可以节省相当多的访盘时间。据UC Berkeley的实验统计，对需要经常访盘的应用程序，使用这种方式可以比使用本地磁盘快5～10倍。
　　除了这几个主要方面的研究之外，还有许多特定应用方面的研究，比如，广播、多播等全局操作的高效实现、DSM并行模型的支持、并行I/O的研究等。
　　5．机群负载平衡技术
　　在并行处理系统中，一个大的任务往往由多个子任务组成，这些子任务被分配到各个处理结点上并行执行，并称之为负载。由于由各结点处理机结构不同，处理能力不同，使得各种子任务在其上运行时间和资源占有率不同。当整个系统任务较多时，各结点上的负载可能产生不均衡现象，就会影响整个系统的利用率。这就是负载不平衡问题，这个问题解决好坏直接影响到系统性能，因此它就成为并行处理中的一个重要问题。
　　为了充分利用高度并行的系统资源，提高整个系统的吞吐率，就需要负载平衡技术的支持，负载平衡技术的核心就是调度算法，即将各个任务比较均衡地分布到不同的处理结点并行计算，从而使各结点的利用率达到最大。
　　在机群系统上，负载平衡要解决的问题主要表现为系统资源使用不均和多用户系统资源分配问题。
　　11.3.3 提高通信系统的性能
　　通信子系统是并行计算机系统的重要组成部分，它完成系统中各结点之间数据传递的功能，其性能的好坏直接影响到并行计算的加速比和效率。这是因为并行计算时间是由各结点计算时间和结点间数据通信时间两部分组成，如果通信时间所占的比例过大，则必然使得并行计算的加速比下降，整个系统的效率也不会高。
　　并行机群系统是基于高性能工作站或高档微机和局域网(LAN)而发展起来的新系统，它是一个由若干微机或工作站通过普通LAN互联而成的松耦合计算机系统，这与大规模并行计算机(MPP)有较大差别，MPP则通常是采用专用网络以紧耦合方式进行结点间的互联。与MPP相比，机群系统具有可扩展性好、性能/价格比高的特点，但网络带宽通常较低，如使用广泛的传统以太网的带宽只有10 Mb/s，即使是新出现的一些高速网络的带宽也只不过上百Mb/s，另外，局域网LAN所使用的通信协议通常是TCP/IP协议，这种协议处理开销比较大，影响了网络硬件特性的发挥；
　　而MPP的内部网络带宽通常都在数百Mb/s以上，而且是采用专用的通信协议，如Paragon XP/S的网络带宽可达到1.4 Gb/s，其通信协议是NX通信库。可见，机群系统中性能过低的通信系统会影响到整个并行计算效率的提高，因此要大力发展并行机群系统，一个关键的问题是对其通信技术进行深入的研究，以期大幅度地提高网络通信系统的性能。
　　1．影响通信系统性能的因素
　　机群系统下的通信子系统的性能是整个系统的薄弱环节，在介绍提高通信系统性能的方法措施之前，先从网络硬件、通信软件两方面分析影响通信系统性能的主要因素。
　　1) 网络带宽低
　　机群系统使用的网络是普通的局域网，而局域网的带宽通常都比较低，如传统以太网的带宽只有10 Mb/s。局域网的带宽之所以低，主要是局域网是为长距离的数据通信而设计的，由于通信距离较长，限制了通信速度的提高，因为信号的频率越高，它能够传输的距离也越短。另外一个原因是出于价格上的考虑。为了降低网络系统布线所需的成本，大多数LAN是共享一根信号总线进行数据传输，因此这也在很大程度上影响了网络系统的性能，特别是在网络负载较重时，由于各结点都要抢占信号总线，很容易造成通信阻塞，使得实际通信带宽比其最大带宽要小得多。　
　　2) 传统TCP/IP协议的多层次结构带来了很大的处理开销
　　TCP/IP协议是面向低速率、高差错和大数据包传输而设计的，它是一个多层次的软件结构，按自底向上的顺序划分，可分为四层：网络接口层、网络层(IP)、传输层(TCP)和应用层。由于协议层次多，在进行数据传输时，数据需要经过多次拷贝才能从应用层传递到网络接口或从网络接口传送到应用层，而多次的拷贝带来了很大的网络延迟时间。另外，在多层协议的实现中，各层还重复实现了很多相同的功能，比如从IP层到传输层都要进行差错控制、从网络接口层到应用层都要进行协议的处理机调度、从IP层到应用层都要进行流量控制、从IP层到应用层都要进行数据包组装和定序的缓冲。
　　这些冗余的功能虽然可确保数据的无差错传送，但却限制了数据及时提交给应用程序处理。可见，多层次的协议结构是造成通信瓶颈的主要原因之一，合并某些层次，删除冗余的处理，设计一种轻型通信协议，是提高通信性能的重要方法。
　　3) 协议复杂的缓冲管理增加了网络延迟
　　网络协议处理包括很多功能，如流量控制、差错控制、出错重发机制、拥塞控制等，而这些功能的实现都与缓冲管理密切相关。缓冲管理的作用是完成数据的分组和组装，缓冲区可看成一种网络资源，这种资源是有限的，对它的管理很重要。不过通常的缓冲管理机制都比较复杂，缓冲管理带来的网络延迟也很大，因此如何简化协议复杂的缓冲管理也是通信技术研究的主要内容。
　　4) 操作系统额外开销不可忽视
　　操作系统提供的系统调用和原语是网络协议实现的底层软件支持。在网络协议实现中涉及到上下文切换、调入/调出页面、启动I/O设备、中断响应等操作系统处理，有时这些开销可能比协议本身的处理开销还大。因此，要提高通信系统的性能，降低网络延迟，应当尽量减少网络协议对主机操作系统的服务请求，最大限度地使通信与计算重叠。
　　2．提高通信系统性能的方法措施
　　1) 采用新型高速网络提高网络带宽
　　为了提高机群系统的网络带宽，必须采用新型的高速网络来取代10 Mb/s以太网。由于多媒体应用、实时网络系统、大规模并行计算等应用对高速网络的需求，推动了网络技术的飞速发展，目前出现了多种新型的高速网络，如快速以太网、ATM、Myrinet。这些新型网络的传输速度是传统以太网的十倍或更高。由于高速网络的运用，使得影响通信系统性能的瓶颈已从过去的网络硬件转移到网络通信软件上，因为虽然高速网络降低了网络的传输延迟，但并没有减少通信协议的处理开销。由于通信协议处理开销过大，在很大程度上阻碍了高速网实际性能的提高。
　　2) 新的通信协议降低了通信延迟
　　为了获得高带宽、低延迟的网络通信，必须对传统的通信协议作较大的修改，以克服传统协议的弊病，使高速网络的优越性能得以充分展现。主要方案有在用户空间实现通信协议、精简通信协议和利用Active Message通信机制。
为了减少操作系统的额外开销，一个重要的方法是在用户空间实现一个用户态的协议层，使得此协议层能够旁路操作系统的影响，直接对网络硬件设备进行操作，这样就可减少数据拷贝次数，提高通信效率；把协议实现放在用户空间的另一优点是可以减少操作系统调用的时间开销，而且通信协议能够与用户的实际应用密切结合，可减少协议不必要的冗余，同时也不有损它的灵活性。
　　不过，把通信协议放在用户空间实现，必须解决好两个问题：一个是多进程复用网络的问题；另一个是在没用核心参与的情况下，如何管理有限网络资源的问题。只有这样，用户态通信协议才能得以有效地实现。
　　前面的分析说明，通信的开销很大程度上是由于协议层次多、数据拷贝频繁引起的，另外，通用的网络接口和协议为满足各种用户的需求，增加了很多与数据传输无关的服务，这些服务也带来了额外的开销。
　　而在并行机群系统中，有些功能是不必要的，完全可以进行精简，以降低通信开销。所谓精简，它包括两部分内容：一部分是功能的精简，就是删除不必要和冗余的功能；第二部分是协议层次的精简，合并各层的功能，使得通信协议变为一层，以达到减少数据拷贝次数的目的。
　　比如，在操作系统Solaris 2.4中，通信协议由网络驱动程序、数据链路层、IP层、TCP层和Socket接口组成，由于数据链路层DLPI已经提供了不保证数据包无差错传送的基本数据通信功能，因此可以在它的基础上实现一个保证数据可靠传送的模块以取代复杂的TCP/IP协议层和Socket接口。这样，新的通信协议不论从结构上看，还是从功能上分析，都比原有的协议要简单得多。
　　通信协议的用户态实现以及协议的精简这两种方法都是针对传统通信协议在实现方法上所做的改进，而Active Message则是一种全新的通信机制，能够更为有效地提高通信系统的性能。
　　11.3.4 几种典型系统
　　目前国内外许多科研机构都在对机群系统下的通信技术进行深入的研究，如UCB
(University of California, Berkeley)提出的NOW计划，Cornell大学研制的U-Net系统，清华大学提出的精简通信协议RCP等，如表11-1所示列举了在机群系统中实现的几种典型的通信子系统。
表11-1 典型通信机群子系统
　　这些系统从实现技术上看，可以分成两类：一类是采用精简通信协议的方法；另一类是使用Active Message通信机制。对比这两类系统的性能可知，采用Active Message通信机制实现的系统性能比用精简通信协议实现的系统要好一些。
关 联
习 题
　　11.1 解释下列概念。
机群系统 共享存储多处理机 监听协议 基于目录的协议 Cache一致性
MPP SMP S2MP UMA NUMA COMA
　　11.2 试比较多处理机系统与并行处理机系统在结构、工作方式及其应用范围方面的
异同点。
　　11.3 共享存储器的多处理机系统有哪几种结构形式？画出它们的结构框图，并说明每种结构的主要特点。
　　11.4 多处理机系统为什么会出现Cache不一致的问题？两种解决不一致问题的方法各用在什么场合？
　　11.5 简要说明监听协议如何保证Cache的一致性。
　　11.6 比较集中共享与分布式存储器系统在结构上的特点，并说明它们各自的优缺点及适用场合。
　　11.7 简述MPP和SMP之间的区别。
　　11.8 什么是机群系统？发展机群系统的关键技术是什么？
　　11.9 提高机群系统的通信性能的途径有哪些？为什么要精简通信协议？
　　11.10 以Origin 2000为例来说明为什么分布式共享存储器系统有很好的可扩展性？

展开更多......

收起↑