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