第 7 章 并行处理技术

第7章并行处理技术2/2/20231本章学习内容并行处理技术的基本概念SIMD并行计算机基础知识计算机互连网络及互连算法多处理机2/2/202327.1并行处理技术的基本概念(简述)并行性在同一时刻或是同一时间间隔内完成两种或两种以上性质相同或不相同的工作。并行性包括并发性和同时性。并行性的粒度Tw：所有处理器的计算时间的总和。Tc：所有处理器的通信时间的总和2/2/20233并行性的等级2/2/20234（1）指令级：并行性发生在指令内部微操作之间或指令之间。取决于程序的具体情况。可借助于优化编译器开发细粒度并行性，它能自动检测并行性并将源代码换成运行时系统能识别的并行形式。（2）循环级：相当于迭代循环操作，典型循环包含的指令大约几百条，循环级并行性是并行机或向量计算机上运行的最优程序结构，并行处理主要由编译器在循环级中进行开发。2/2/20235（3）子任务级：属于中粒度。子程序是在单处理机或多处理机的多道程序设计这一级进行的。这一级并行性由算法设计者或程序员开发而非用编译器开发。（4）任务级：这是与任务、过程、程序段、协同程序级相对应的中粒度或粗粒度规模。典型粒度包含的指令几千条，检测本级的并行性比细粒度级困难得多，需要更多地涉及过程间的相关性分析。需编译器支持。（5）作业（程序）级：对于少量几台高性能处理机构成的超级计算机开发这种粗粒度并行性切实可行。2/2/20236并行性的开发策略时间重叠资源重复资源共享并行性的开发方式粗粒度开发方式：主要采用软件手段开发并行性。细粒度开发方式：主要采用硬件手段开发并行性。粒度与Flynn的关系粗粒度-MIMD方式（G↗）细粒度-SIMD方式（G↘）2/2/202377.2阵列处理机（SIMD并行计算机）并行计算机的定义并行计算机就是由多个处理单元PE(以下也称为处理器，或简称为CPU)组成的计算机系统，这些处理单元相互通信和协作能快速、高效的求解大型复杂问题。

下图给出了从标量到向量和并行计算机的演变。2/2/202382/2/20239阵列机以SIMD方式工作、采用资源重复技术实现数据处理时的高度并行的阵列处理机。阵列机主要用于处理向量和阵列型数据。它在同一个控制部件管理下，有多个处理单元。所有处理单元均收到从控制部件广播来的同一条指令，但操作对象是不同的数据。H.J.Siegel提出了SIMD计算机的操作模型。2/2/2023107.2.1阵列机的基本结构1.阵列机的结构阵列机通常由一个控制器（CU）、N个处理器单元（PE）、M个存储器模块（M）以及一个互连网络部件（IN）所组成。互连网络（IN）有时也称为对准网络或排列网络。2/2/202311H.J.Siegel提出的并行处理机模型

2/2/2023122.阵列机的工作方式阵列机工作时，由控制器CU控制将指令广播给系统中的各个PE，所有活跃的PE将以同步方式执行相同的指令（单指令流）。PE从相应的存储模块中取得自己所需的数据对象（多数据流）进行处理。互连网络IN用来使各个PE之间或是PE和M之间实现方便的通信连接。2/2/2023133.阵列机的两种基本结构⑴分布式存储器阵列机2/2/202314①N个相同的处理单元PE由处理器Pi和局部存储器Mi组成。各个Pi主要将从自己的局部存储器Mi中获取数据进行操作。各个PE通过IN实现相互间必要的数据交换，因此IN是单向的。②CU具有自己的存储器，用于存放系统程序、用户程序以及各个PE所需的共享数据。CU的主要功能是对指令译码和判别指令应在何处执行。对于标量或控制类指令，CU利用本身的运算部件直接执行；若是向量指令，它就将指令广播到各个PE去执行。分布式存储器阵列机的特点2/2/202315③各个PE同步执行来自CU的操作命令。但是并不一定每个操作非得所有PE都参加，CU将对PE实行屏蔽控制，只有那些未被屏蔽的活跃PE才可参加操作。CU控制互连网络IN，使各个PE之间通过IN实现相互之间必要的数据交换。当相互需要交换数据的两个PE不直接相连时，就需要经过它们之间的中间PE来完成连接。2/2/202316⑵共享存储器的阵列机2/2/202317①每个PE没有自己的局部存储器。存储器模块以集中形式为所有PE（通过IN）共享。②互连网络受CU控制，用来构成PE和M之间的数据交换通路。要求互连网络具有同时连接PE到M和M到PE的双向性。③系统中的一个PE可以与任何另一个PE实现数据交换（只要有任何一个存储模块同时与这两个PE相连接）。当两个需交换数据的PE之间没有共享的存储模块时，可能需要经过多次的传送之后，方可实现交换。④互连网络比较复杂。共享存储器阵列机的特点2/2/202318SIMD计算机的操作模型可用五元组表示：C＝<N，C，I，M，R>式中：

(1)N为机器的处理单元(PE)数。

例如，IlliacIV有64个PE。而连接机(ConnectionMachine)CM-2采用65536个PE。

(2)C为由控制部件(CU)直接执行的指令集，包括标量和程序流控制指令。

阵列机特征的形式化表示2/2/202319(3)I为由CU广播至所有PE进行并行执行的指令集，它包括算术运算、逻辑运算、数据寻径、屏蔽以及其它由每个活动的PE对它的数据所执行的局部操作。(4)M为屏蔽方案集，其中每种屏蔽将PE集划分为允许操作和禁止操作两种子集。

(5)R是数据寻径功能集，说明互连网络中PE间通信所需要的各种设置模式。

F=(C,R)描述了互连网络及参数这种描述模型为评价不同的阵列机结构提供了比较基础。2/2/202320计算机的操作特性描述如MasParMP-1计算机：(1)PE数N＝1024至16384。PE数目与机器配置有关。

(2)CU执行标量指令，将译码后的向量指令广播到PE阵列，并控制PE间的通信。

(3)每个PE都是基于寄存器的加载/存储RISC处理机，能执行不同数据量的整数运算和标准浮点运算。PE从CU接受指令。

(4)屏蔽方案设在每个PE中，并由CU连续监控，它能在运行时动态地使每个PE处于置位或复位状态。

(5)MP-1有一个X-Net网格网络和一个全局多级交叉开关寻径器，以实现CU-PE之间、X-Net的8个近邻之间和全局寻径器的通信。2/2/2023212/2/2023227.2.2阵列机的主要特点(1)阵列机采用资源重复的策略，利用并行性中的同时性提高处理速度。(2)阵列机中通常都采用简单、规整的互连网络实现处理单元PE间的连接操作。(3)阵列机的研究必须与并行算法研究密切结合。(4)增加PE可提高阵列机的性能，因此阵列机具有较好的可扩展性。(5)由于处理单元PE都是相同的，因此可将阵列机看成是一个同构型并行机。但实际的阵列机系统是由控制器、PE、前端机三部分构成的一个异构型多处理机系统。2/2/2023237.2.3阵列机的并行算法以矩阵加为例

在阵列处理机上解决矩阵加法问题是最简单的一维情形。假定两个8×8的矩阵A和B相加，则只需把A和B居于相似位置的一对分量存放在同一PEM内，且令A的分量在全部64个PEM中存放的单元地址均为a,B的分量单元地址码均为a+1，而C＝A＋B的结果分量均放在地址码为a+2的单元内，如图所示。于是，只需用下列3条IlliacIV的汇编指令就可一次实现矩阵相加。

2/2/2023242/2/202325LDAALPHA

；全部(a)由PEM送PE的累加器RGA

ADRN

ALPHA＋1；全部(a+1)与(RGA)进行浮点规舍加，结果送PGA

STAALPHA＋2；全部(RGA)由PE送PEM的a+2单元。

由于全部64个处理单元并行操作，故速度可提高为顺序处理的64倍。2/2/2023267.2.4典型SIMD计算机举例一、Illiac-IVSIMD阵列机

它是由Burroughs公司和Illinois大学1965年开始制、并于1972年完成的。Illiac-IV是SIMD阵列处理机的典型代表,其结构框图如下图所示，共有64个PE，统一由CU控制。B6500作为前端机进行系统管理。每个PE有自己的局存PEM，容量为2K字，字长64位，同时每个PE拥有4个64位的寄存器，分别用作累加器、操作数寄存器、数据路由寄存器和通用寄存器。此外，尚有1个16位变址器和1个8位的方式寄存器，用于存放PE的屏蔽信息。

2/2/2023272/2/202328下图示出了Illiac-IV带环绕的2维网孔互连网络，这是一种4近邻的互连网络，从一个PE发送数据到另一个PE，在最坏情况下，须要经过步（n为PE数）。这种互连拓朴形式很适合于求解偏微分方程和矩阵运算之类的问题。当64个PE并行工作时，系统峰值速度可达每秒2亿次运算，它主要应用于气象预报和核工程研究等领域。2/2/202329IlliacIV处理阵列的连接由８８＝64个PU组成。每个PU由处理部件PE和它的局部存储器PEM组成。每一个PUi只和它的东、西、南、北四个近邻： PUi+1mod64、PUi-1mod64、PUi+8mod64、PUi-8mod64直接连接。南北方向同一列PU连成一个环， 东西方向构成一个闭合螺线。闭合螺线网络直径为7步， 环形网格的直径为8步。2/2/2023302/2/202331阵列控制器CU阵列控制器CU实际上是一台小型计算机。

对阵列处理单元实行控制和完成标量操作。 标量操作与各PE的数组操作可以重叠执行。控制器的功能有以下五个方面： (1)对指令进行译码，并执行标量指令； (2)向各PE发出执行数组操作指令的控制信号； (3)产生并向所有处理单元广播公共的地址； (4)产生并向所有处理单元广播公共的数据； (5)接收和处理PE、I/O操作以及B6700产生的陷阱中断信号。2/2/202332二、国产曙光系列并行机系统介绍我国的高性能计算机的发展起步并不晚：早在20世纪60年代后期到70年代，我国就自行研制了大型计算机（MainframeComputer），其典型代表机器有150、905、718和DJS260等，它们采用单/双CPU，其峰值速度约为1MOPS（MillionOperationsPerSecond），即俗称的百万次机器；20世纪70年代后期到80年代，我国研制了向量机和多处理机，其典型代表机器有757、银河1号和2号等，它们采用1~4个CPU，其峰值速度达10~100MOPS，即俗称的亿次机器。2/2/20233320世纪80年代后期到现在，我国研制了对称多处理机（SMP）、大规模并行机（MPP）和工作站群（COW），其典型代表机器有曙光1号、曙光-1000/1000A、YH-3和曙光-2000等，它们采用4~128个CPU，其峰值速度达1Gflops~几十Gflops，即俗称百亿次机器，我国1999年正式推出了千亿次高性能计算机。

以下简介我国的大规模并行处理系统：曙光-1000

2/2/202334技术特点

曙光-1000是一台分布存储的大规模并行处理MPP（MassivelyParallelProcessing）系统，它突破了MPP中一些技术关键，采用20世纪90年代大量先进技术，其峰值速度达25亿次，可广泛应用于科学工程计算、气象预报、石油勘探、地震数据处理和银行等商务处理中。其技术特点是：

①良好的可扩放性，包括硬件和软件两个方面；2/2/202335②大量的节点、强大的计算能力和大容量存储器；③自行设计的稳定可靠的虫蚀通信芯片；④使用带流控的消息传递协议；⑤优良的优化并行编译器；

⑥先进的并行编程环境、并行查错工具、自动并行化工具和包括PVM、MPI、Express、NX等的编程工具。

2/2/202336主要技术指标

曙光-1000整体性能达到20世纪90年代初期世界先进水平，其主要技术指标是：

①使用6×6的二维网孔连接、共36个节点，其中计算节点32个，服务节点2个和I/O节点2个；②峰值速度单精度达2.56Gflops，双精度1.92Gflops，实际速度为1.58Gflops；③存储容量为每个节点32MB，共1GB；④硬盘容量可超过5GB；⑤二维网孔连接、虫蚀选路，总通信容量为4.8GB/s；

2/2/202337⑥计算节点和通信网络间带宽为2.8GB/s；⑦支持并行C、C++和Fortran，提供并行优化重构工具Port和自动并行化工具Autopar、动态监视和分析工具ParaVision以及单计算节点上源代码与目标代码的优化工具；⑧基于Unix的分布式并行操作系统；⑨提供并行程序查错环境NDB；⑩提供并行程序设计和运行环境PVM、MPI、Express、NX和P4等。

2/2/202338硬件系统

曙光-1000是一台分布存储、消息传递的MPP系统，如下图所示，在6×6二维网孔的每个格点上有一个虫蚀路由芯片WRC（WormholeRoutingChip）和一个计算节点（或服务节点或I/O节点），系统监视器（Monitor）负责系统初始化和硬件故障诊断，用户工作平台可以是工作站SUNSparc-Ⅱ(或其它工作站)也可以是终端（它们都称为前端机），它们通过10Mb/s的以太网连向服务节点。

2/2/2023392/2/202340（1）二维网孔和WRC：二维网孔是一种扩展的互连网络。格点上的计算节点（或服务节点或I/O节点）都连向WRC。节点编号（物理地址）由X方向编号和Y方向编号两部分组成，节点间相对地址包含在消息中。一个WRC有10条输入/输出通道，每个通道包含8条数据线，一条指明消息结束的尾信号线、一条发送请求线REQ和一条应答ACK。当一条消息自源发往目的时，它只穿过途中的WRC，并不进入与WRC相连的节点处理器。消息选路采用X-Y选路算法。

2/2/202341（2）计算节点：它是一块插入板，其核心是一个i860xr芯片，其主频为40MHz

，字长64位，单精度浮点运算速度为80Mflops，双精度为60Mflops，标量计算速度为40MIPS；它有带奇偶校验的32MBDRAM、8KBEPROM和2KBNVRAM；节点与网孔的接口模块包含16KBFIFO，网孔与各节点间的通信带宽为33MB/s，消息具有CRC校验，RS-232接口直接连向监视器上的多用户卡，以便监视器能诊断所有的节点处理器。在所有的计算节点上运行OS与用户程序。

2/2/202342（3）服务节点：服务节点用于管理系统资源，它是一台50MHz的具有EISA总线的486PC机。EISA总线与网孔之间有一接口模块EMI，在EMI卡上有DMA机制；在数据通路FIFO-网孔-FIFO上使用CRC校验；EMI卡和网孔之间的通信速度是16MB/s。如果较多的用户和图形显示设备，则可使用2个服务节点，两者可使用共享系统资源表的方法协同工作。

2/2/202343（4）I/O节点：和服务节点一样，I/O节点也是一台带有EISA总线、具有EMI插卡的486PC机。一个I/O节点使用插在EISA总线上的SCSI卡可接入4GB硬盘。系统可提供一个或两个I/O节点，当用户要求大的I/O吞吐率时可使用更多的I/O节点，但计算节点则须相应减少。I/O节点和网孔之间的数据传输速度为16MB/s。每个I/O节点上运行并行文件系统，执行并行文件操作。

2/2/202344（5）系统控制台：也就是监视器，它运行SCOUNIX，其中有一块多用户卡，连向32个RS-232串行口。控制台与计算节点可执行点到点通信，也可向所有计算节点同时播送消息。其主要功能是初始化系统、监视计算节点上操作系统和用户程序的运行、动态地查看节点处理器资源组态表和诊断失效的计算节点。

2/2/202345（6）前端机：曙光-1000用户工作平台是SUNSparc-Ⅱ或SGI图形工作站或终端，所有这些设备均经由LAN（如以太网）连向系统服务节点。LAN遵从TCP/IP协议，其速率为10Mb/s。事实上，网孔系统可视为前端系统的计算服务器，在前端机上用户程序被编辑、编译（使用C和Fortran77i860交叉编译器）、链接和查错，当编译成功后，应用程序的目标代码通过以太网传到服务节点；然后由服务节点发往计算节点；最终的计算结果由前端机显示输出。

2/2/202346系统软件

（1）操作系统：曙光-1000的操作系统是基于Unix的分布操作系统。在计算节点上运行微核操作系统，支持虚拟存储管理、自陷处理、作业管理和消息传递；在服务节点上运行基于Mach2.6操作系统，支持多线程，其主要功能是系统管理，特别是节点处理器的分配与去分配；在I/O节点上运行并行文件服务器PFS。服务节点和I/O节点与计算节点具有相同的消息传递接口。系统执行带有流控的消息传递协议。

2/2/202347（2）并行优化编译和工具：节点程序编译优化包括源码级优化和目标码级优化，前者使用循环（Loop）交换、循环合并和循环分离的办法开拓并行性；后者采用充分利用流水线、双指令模式和双操作指令（由i860所提供的）和浮点加载指令以向量化循环的方式开拓并行性。Autopar是自行开发的自动并行化工具，它能识别并行循环、执行数据划分和产生并行的Fortran源代码。Paravision是曙光-1000并行系统的可视化工具，它能够移植到其它MPP系统上，用户使用它能观察程序动态运行过程，包括消息传递条件、负载平衡情况和是否出现死锁等。

2/2/202348（3）并行编程环境和并行查错工具：为了便利用户编程和运行并行程序，曙光-1000移植了4种成熟的界面环境，即NX、Express、PVM和MPI。其中NX原是Paragon系统上的用户并行编程界面，而Express、PVM和MPI均是世界上广泛使用的并行编程和运行环境。并行程序查错器包括源代码查错程序NDB和汇编代码查错程序ADB，它们的主要功能是显示、设置和取消指令断点、读/写存储器、逐步或连续运行程序或发送和接收现行进程状态。它们能够查错运行在多个节点上的程序。

2/2/202349与某些著名MPP系统的性能比较一览表

下表列出了曙光-1000与某些著名MPP系统的性能比较，性能指标是利用求解标准线性方程组测得的，其中R（max）是机器能够达到的最高速度，系统N（max）是速度达到R（max）时线性方程组的阶，N（1/2）是速度达到1/2R（max）时线性方程组的阶。

2/2/2023502/2/202351超级并行计算机系统：曙光-2000

曙光天潮系列“曙光-2000”是基于分布存储和消息传递体系结构的通用可扩放并行计算机系统，其节点数为4~128个，节点CPU采用先进的PowerPC604e微处理器，通过高速以太网和虫蚀路由器芯片组成的二维孔互连。每个节点上运行完整的IBMAIX操作系统，系统与IBMRS/6000二进制兼容。可广泛应用于科技计算和商业计算的多种领域中。

2/2/202352设计准则

为了将曙光-2000设计成一种通用、灵活的可扩放并行机系统，设计者们在广泛分析和深入理解当前硬件、软件技术发展趋势，不同应用领域的需求和用户环境要求的基础上，遵循了一系列设计准则：①一个高性能的可扩放并行系统必须采用标准的微处理器、软件构件（Component）和操作系统，只应在标准技术无法满足可扩放并行系统某些特殊要求（如通信延迟）时，才采用定制的硬件和软件；2/2/202353②采用最新的技术，保证性能价格比的领先优势。为此必须尽可能少地依赖于技术供应商，低层的体系结构必须足够灵活，在OS级上对各节点采用松散耦合方式；

③对低延迟的高带宽的要求使得在今后几年内可扩放并行计算机系统仍然依赖于定制的内部网络和通信子系统；④系统的编程和执行环境应与标准的、开放的、分布式Unix环境一致；⑤系统应当有选择地在下列领域提供高性能服务：通信系统、高性能文件系统、并行库、并行数据库、高速I/O，以利于高效地进行超级计算、并行查询和高性能事务处理；

2/2/202354⑥消除造成系统崩溃的单一故障点和从失效中快速恢复，可获得系统高可用性。为此必须有足够的硬件和软件备份（Replication），同时提供支持可用性的基础软件（故障检测、诊断、系统重配置和恢复等）；⑦对于单一系统映像进行有选择地支持，只进行重要资源（如文件、目录服务）和命令的全局化以及提供对系统管理的单点控制。

2/2/202355体系结构

曙光-2000体系结构

如图所示。曙光-2000系统可由4~128个处理节点组成。每个节点包括可靠的高效的RISC微处理器Power-PC，运行完整的IBMAIX操作系统。诸节点由高速以太网和二维网孔互连；通信网卡通过PCI总线与节点相连，外围子系统通过I/O接口与节点相连；系统管理员通过控制台管理系统；用户工作站或终端通过外部以太网访问节点。曙光-2000系统的节点可分为计算节点和I/O与登录服务节点：前者用于执行用户提交的任务；后者用于支持用户作业在计算节点上运行。

2/2/2023562/2/202357（1）节点处理器：PowerPC微处理器采用超标量技术（即每个周期同时执行多条指令）和很多复杂结构技术来获得高性能。它拥有6个处理单元（浮点单元FPU、转移处理单元BPU、存/取单元LSU、2个单周期整数单元SCIU和多周期整数单元MCIU），可同时执行4条指令，300MHz主频的处理器可达到每秒6亿次浮点运算。每个处理器的一级高速缓存容量为32KB数据/32KB指令，二级高速缓存容量为1MB；内存容量为128~52MB；内置硬盘容量为4.3GB；I/O总线速率为133MB/s。

2/2/202358（2）通信子系统：曙光-2000采用二维网孔互连，使用“虫蚀”选路，从而具有可扩放性、低延迟、高带宽、低处理器开销和可靠灵活之特性。在二维网孔中，点与点之间采用基于消息包的固定路由、无缓冲的传输机制，点与点之间的通信带宽保持常数，不依赖于拓朴中两节点的物理位置。WRC芯片有10个通道，如图所示，每个通道16位数据宽度，50MHz频率，数据带宽100MB/s。芯片内部有X、Y两个路选择控制器和4级16位数据缓冲器。曙光-2000节点通过一块PCI网络接口板与底板相连，其中PMI-16接口板由PCI的DMA引擎控制数据传输，PMI-960接口板由一个Intel960协处理器负责DMA传输和协议控制。接口板和节点内存之间采用DMA方式传输，减少了消息传递中处理器的开销。

2/2/2023592/2/202360软件系统

曙光-2000软件逻辑结构如下图所示。其中，每个节点均由一个完整的AIX4.2以上操作系统管理，它提供了大量的多用户通信和系统管理技术、编译器等，符合主要的工业标准；在低层它提供了用于消息传递的基本通信库BCL、PVM和MPI；在高层提供集成并行程序设计环境IPPE、并行可视化工具ParaVT、并行调试器DCDB、KISS（KeepItSimpleandScalable）、基于Web的用户界面、自动并行化工具AutoPAR、可扩放文件系统COSMOS、批作业管理JOSS、资源管理RMS和曙光服务器聚集软件DSC；此外，曙光-2000系统还提供了一系列广泛的IBMRS/6000兼容的开放软件工具来支持管理和操作，包括IBM的C和Fortran编译器、数学和工程库ESSL、数据库DB2等。

2/2/2023612/2/202362（1）并行环境：它由BCI、IPPE、ParaVT和DCDB组成，用户可用来开发、调试和修改并行Fortran和C程序，并且可启动、监视和控制程序的运行。其中，BCL支持Fortran和C显式消息传递模型，提供大量的函数集和子程序以支持进程间点到点通信和用户非阻塞通信，并支持多用户方式用户空间通信；IPPE提供启动、监视、控制并行应用的用户环境，主要功能包括编译、链接并行代码和通信库，并行任务分区、并行作业加载和监视作业的运行，傻瓜界面KISS提供基于Web的查询和使用界面；ParaVT提供并行应用的性能监视和跟踪可视化，前者在程序运行时实时地显示系统的活动状态；后者用户可设置跟踪点以观察并行进程间的通信情况、识别死锁、负载变化和性能瓶颈等；DCDB是一个源代码级的调试器，支持图形化使用界面，是在Unix串行调试器dbx或gdb基础上附加了一些专用的并行程序调试功能。

2/2/202363（2）可扩放文件系统：COSMOS可有效解决超级计算应用对单个文件的可扩展高带宽的要求，并能提高网络文件系统吞吐量的可扩放性。它支持对条带化（Stripe）方式分布存储的文件的并行访问；它允许一个并行程序的多个进程对同一文件进行访问；可支持异步的I/O和规模大于2GB的文件；COSMOS支持标准Unix文件系统调用，用户通过UNIXioctl操作可获得其它的功能。由于每个计算节点上运行一个ClientDaemon、每个COSMOS服务节点上运行一个StorageDaemon（或有选择地运行ManagerDaemon），所以这些服务进程相互通信形成一个可扩放服务器来满足用户请求。

2/2/202364（3）可用性服务：曙光-2000所提供的可用性服务包括系统管理软件中的系统监控和NCIC-HA高可用软件包。目前曙光-2000系统可用性服务的主要功能包括心跳服务、资源组服务、通知服务和恢复协调服务。其中心跳服务就是监视系统的状态是否正常，包括侦测和交换心跳信息；资源组服务就是定义节点和应用程序、系统资源（如IP）属于一个故障切换资源组，通常该组包括那些相关的应用服务员；通知服务就是在组的结构和节点状态发生了变化时通知组内成员；恢复服务提供了当组内结构和节点状态发生变化时，当前组中备份节点恢复进程的启动机制，即故障切换（Takeover）。这些服务是由运行在节点上的HA守护进程（Daemon）所实现的。

2/2/202365（4）全局服务：对于曙光-2000来说，一个全面的单一系统映像并不是迫切需要的，它只是对特殊资源（包括磁盘、文件和通信网络等）提供单一系统映像。在曙光-2000中，通过网络文件系统NFS来提供对文件的全局访问，全局网络访问是通过网络路由机制和TCP/IP及UDP/IP对互连网络的支持来进行的。在此方式下，可使曙光-2000上的应用以单一的IP地址对外提供服务；曙光-2000还打算使用虚拟共享磁盘VSD提供对磁盘的全局访问，使用VSD，运行在任何节点上的应用程序可以透明地访问任一其它节点上的磁盘，就像该磁盘是连接在自身节点上的一样；2/2/202366另一个全局服务是系统存储库SDR，它提供曙光-2000系统中各节点和控制工作站上的数据存储和检索，这包括各个节点和互连网络的配置的全局信息以及系统中资源和作业的信息，这些重要的系统数据不仅要储存在实现这些系统功能的服务节点上，而且也应被保存在这些节点以外的全局储存库SDR上。当重要的系统服务发生故障时，故障节点可以通过查询SDR来重新恢复正常工作，在此期间，对服务的请求只是被延迟，但不会引起其它的故障发生。

2/2/202367（5）系统管理：访问曙光-2000系统管理和监控软件是建立在大量的AIX工作站环境中已有的系统管理工具和命令的界面上的，它使得在多节点上可以运行传统的系统管理命令，这些命令的功能包括系统安装、重启/关机、系统操作、用户管理、安全管理、作业记帐、硬件监控、打印和邮件服务等；曙光-2000的单点控制在系统控制台上进行，它是一台独立的天演系列工作站，与系统中每一机柜相连，用户可从网络的任何一个地方登录到控制台；系统管理软件使用基于SNMP协议的客户/服务方式来从控制台启动系统管理命令，基于JAVA的图形化界面用于确定在哪一个节点上进行操作、修改和收集节点应答；硬件监控软件使得系统员可以监控曙光-2000系统的硬件状态。

2/2/202368（6）作业管理：用户可以使用批处理或交互方式使用曙光-2000：在批处理方式中，作业是通过网络作业调度程序提交的；在交互方式中，用户使用Unixrlogin/telnet命令登录到曙光-2000系统上，通过相应的网络地址就可直接访问某个特定的节点。曙光-2000的资源管理器的主控服务运行在控制台上，它将相应的节点分配给并行作业，当并行作业被提交时，用户通过函数或命令向资源管理器申请作业所需的节点，如果有相应数量的可用节点，资源管理器就返回一个可用节点表，这些节点就构成了该并行作业的节点分区；当节点分区确定后，分区管理进程就在分区内的每个节点上加载一份作业的可执行代码，并通知该节点上的守护进程启动代码的执行；当作业完成后，分区管理进程负责清除和终止工作，并交回分区内所有节点。

2/2/2023697.3计算机互连网络1.地位与作用随着各个领域对高性能计算的要求越来越高，多处理机和多计算机系统的规模越来越大，处理机之间或处理单元和存储模块之间的通信要求和难度也越来越突出。所以互连网络已成为并行处理系统的核心组成部分，它对整个计算机系统的性能价格比有着决定性的影响。互连网络在多处理机系统中位置和作用如图所示。2/2/2023702/2/2023712.互连网络互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接。下图是具有本地存储器、私有高速缓存、共享存储器和共享外围设备的多处理机系统互连结构。每台处理机Pi与自己的本地存储器(LM)和私有高速缓存(Ci)相连，多处理机－存储器互连网络IPMN与共享存储器模块(SM)相连。处理机通过处理机－I/O网络PION访问共享的I/O和外围设备。处理机之间通过处理机间通信网络IPCN进行通信。2/2/2023722/2/202373其中：IPMN（处理机－存储器网络）PION（处理机－I/O网络）IPCN（处理机之间通信网络）P（处理机）C（高速缓冲存储器）SM（共享存储器）LM（本地存储器）2/2/2023743.互连网络信息的交互发送方的步骤如下：(1)用户程序把要发送的数据拷贝到系统缓冲区。(2)缓冲区中的数据打包并发送到网络接口部件。(3)网络接口硬件开始发送消息。数据包的接收步骤如下：(1)把数据包从网络接口部件拷贝到系统缓冲区。(2)检查收到的数据包，如果正确，发回答信号。(3)把接收到的数据拷贝到用户地址空间。发送方接收到回答信号后释放系统缓冲区2/2/2023754.互连网络的主要时延(1)频带宽度(Bandwidth)：传输信息的最大速率(2)传输时间(Transmissiontime)：等于消息长度除以频宽。(3)飞行时间(Timeofflight)：第一位信息到达接收方所花费的时间。(4)传输时延(Transportlatency)：等于飞行时间与传输时间之和。(5)发送方开销(Senderoverhead)：处理器把消息放到互连网络的时间。(6)接收方开销(Receiveroverhead)：处理器把消息从网络取出来的时间。2/2/202376一个消息的总时延可以用下面公式表示：

总时延＝发送方开销＋飞行时间＋消息长度/频宽＋接收方开销2/2/202377例1：假设一个网络的频宽为10Mb/S，发送方开销为230us，接收方开销分别为270us。如果两台机器相距100米，现在要发送一个1000字节的消息给另一台机器，试计算总时延。如果两台机器相距1000公里，那么总时延为多大？（设光的速度为299792.5km/s，信号在导体中传递速度大约是光速的50％。）2/2/202378解：相距100米时总时延为：相距1000公里时的总时延为：2/2/2023795.互连网络的种类静态互连网络：连接通路是固定的，一般不能实现任意结点到结点之间的互连。循环互连网络：通过多次重复使用同一个单级互连网络以实现任意结点到结点之间的互连。多级互连网络：将多套相同的单级互连网络连接起来，实现任意结点到结点之间的互连。全排列互连网络：能够同时实现任意结点到结点之间的互连。全交叉开关网络：能够同时实现任意结点到结点之间的互连，还能够实现广播和多播。2/2/2023807.3.1互连网络的设计准则及互连函数若把处理单元PE或存储模块M看成结点，则互连网络实际为输入和输出两组结点之间提供了数据通路或映像。对于N个输入和M个输出来讲，由于不允许有多对一的映像（因为会造成访问冲突），由输入到输出映象共有NM种，如果限定为一对一映像，则只有N!种映像。NMICN2/2/2023811.互连网络的性能参数⑴网络规模网络中的结点数。用于表示网络中所能连接的部件的多少。⑵连接度（结点度）网络中与结点相连接的边的数目。用于表示结点所需要的I/O端口数。入度：进入结点的通道数。出度：从结点出来的通道数。结点度＝入度＋出度。结点度也反映了一个结点与其他结点的连接程度。2/2/202382⑶连接数网络中所有结点之间连接的数量，即通路（边数）的总和。⑷距离网络中两结点之间相连的最少边数。⑸网络直径网络中任意两结点之间距离的最大值。网络直径反映了从一个结点传送信息到任何另一个结点所需的时间，即网络的延时性。另外，带宽、可靠性和成本也是反映网络性能的重要指标。2/2/202383⑴通信工作方式（定时方式）①同步方式用统一的时钟同步各PE的并行操作以及控制器向处理单元广播命令的操作。SIMD并行机都采用同步方式。同步方式的控制比较简单。②异步方式不用统一时钟同步操作，各个处理单元根据需要相互建立动态连接。异步方式的控制比较复杂。2.互连网络设计时应考虑的因素2/2/202384⑵控制策略①集中式控制由一个统一控制器对各个互连开关状态加以控制。一般的SIMD并行机都采用集中控制。②分散式控制由各个互连开关自身实行管理。2/2/202385⑶交换方式①线路交换在整个交换过程中，在源和目标结点之间建立固定的物理通路。线路交换适用于成批数据传送。②分组交换把要传送的一个信息分成多个分组，分别送入互连网络。这些分组可通过不同的路由到达目标结点。分组交换适合于短数据报文的传送。SIMD并行机一般采用线路交换，因为处理单元间的联接比较紧密。MIMD多机系统多采用分组交换方式。2/2/202386⑷网络拓扑拓扑：互连网络中的各个结点间连接关系，通常用图来描述。①静态拓扑在各结点间有专用的连接通路，且在运行中不能改变。静态拓扑一维的有线性阵列结构，二维的有环形、星形、树形、网格形等，三维的有立方体等，三维以上的有超立方体等。2/2/2023872/2/202388②动态拓扑各结点之间的连接通路中设置有源开关，可根据需要利用控制信号对连接通路加以重新组合。动态拓扑主要有单级循环网络和各种多级互连网络等。2/2/202389每种互连网络可用一组互连函数来定义，互连函数反映了不同互连网络的连接特性。若将互连网络的N个输入端和N个输出端分别用整数0，1，…，N－1表示，则互连函数表示互相连接的输出端号与输入端号的一一对应关系。或者说，存在互连函数f，输入i与输出f(i)相连，0≤i≤N－1。当用互连网络实现PE与PE之间的数据变换时，互连函数也反映了输入数组与输出数组间对应的置换或排列关系，因此互连函数也称为置换函数或排列函数。3.互连函数2/2/202390互连函数的表示方法⑴输入输出对应表示法例：2/2/202391⑵函数表示法用x表示输入端变量，f(x)表示互连函数。通常把N个输入端x用N位二进制形式表示为：互连函数对应表示为例：设所以即，127号输入与254号输出关联。2/2/2023924.拓扑结构图例（1）线形和环形2/2/2023932/2/2023942/2/202395（2）树形和星形2/2/2023962/2/202397（3）网格形和环网形

2/2/2023982/2/202399（4）超立方体和带环立方体2/2/20231002/2/20231012/2/20231022/2/2023103（5）k元n--立方体（k=4,n=3）2/2/2023104按照惯例，低维k元n-立方体称为环网，而高维二元n-立方体则称为超立方体。用网络折叠的方法可避免环网中长的端绕连接，如图所示。2/2/2023105静态网络特性一览表下表汇总了静态互连网络的重要特性。大多数网络的结点度都小于4，这是比较理想的。全连接网络和星形网络的结点度都太高。超立方体的结点度随log2N值增大而增大，当N值很大时其结点度也太高。

网络直径的变化范围很大。但随着硬件寻径技术不断革新(虫蚀寻径)，直径已不是一个严重问题，因为任意两结点间的通信延迟在高度流水线操作下几乎是固定不变的。链路数会影响网络价格，等分宽度将影响网络的带宽。

2/2/20231062/2/20231077.3.2单级互连网络具有N个输入分配器和N个输出选择器的开关网络。通常只实现有限的几种基本连接。2/2/2023108在单级互连网络中，IS和OS分别为一对多和多选一的多路分配和多路选择器。所有的IS和OS根据互连函数在控制器控制下，在处理单元之间建立起所需要的连接通路。全交叉开关网络是单级互连网络中的例外。在全交叉互连网络中，任何一个结点都有与其他结点的直接通路，所以只需经过一步就可使源结点中的数据传送到网络中任一目标结点。全交叉互连网络具有最好的连接性。2/2/2023109全交叉开关网络2/2/2023110下图示出了Digital公司的千兆开关/FDDI中所设计的交叉开关。该交叉开关是为Alpha工作站和服务器的多个FDDI环之间计算机群互连而设计的。使用FDDI全双工技术（FFDT），能够连接多至22个FDDI端口，每路速度为100Mbps。

2/2/20231112/2/2023112由于使用切通选路技术，时延可减少到20微秒。使用2或4端口线卡可构造22端口的交叉开关。总之，千兆开关/FDDI能提供高达3.6Gbps的带宽（是以太网的360倍），它已用在Digital的TruCluster中。千兆开关/FDDI是一种通用的网络产品，可用于任意以FDDI环连接的系统中，它是基于交叉开关设计的实现节点间通信的一个很好例子。2/2/2023113常用的单级互连网络1．交换互连网络（Exchange）在网络规模为N的互连网络中，交换互连网络的互连函数为：E(x)k＝(bn－1…bk…b0)其中：0≤k≤n－1，n＝log2N即把输入端x的二进制编码的第k位变反就可得到对应的输出排列。也写成2/2/2023114交换互连网络共有n＝log2N种互连函数。在单级交换互连网络中，从一个结点到任何另一个结点所需的最短距离(即网络直径)为n。当N＝8，n＝log28＝3时，交换互连网络就是常用的立方体互连网络。立方体中的每一个顶点代表一个处理单元。8个PE的坐标地址可用3位二进制代码表示。它的三个互连函数为：2/2/2023115

(a)E0方体置换(b)E1方体置换(c)E2方体置换

2/2/2023116立方体互连网络2/2/20231172.混洗互连网络（Shuffle）⑴全混洗Shuffle(bn－1bn－2…b1b0)

＝(bn－2…b0bn－1)即将输入端x的二进制编码循环左移一次就可得到输出端的二进制编码。也写成2/2/2023118子混洗(subshuffle)S(k),最低k位循环左移一位

超混洗(supershuffle)S(k),最高k位循环左移一位

显然成立：逆混洗函数：2/2/2023119例：N＝8时的混洗互连2/2/2023120Σ是x的一次全混洗，若再进行一次混洗，则得到新的函数：即每全混洗一次，输出端的二进制编码就是输入端x的二进制编码循环左移一次得到的编码。当全混洗次数为n时，全部N个输入对应的输出又恢复到最初的排列次序。全混洗互连网络的特点是编号为全“0”和全“1”的输入端PE无法与网络中的其他PE相连。2/2/20231213.蝶式互连网络（Butterfly）Butterfly(bn－1bn－2…b1b0)

＝(b0bn－2…

b1bn－1)即将输入端x的二进制编码的最高位与最低位互相交换位置就可得到输出端的二进制编码。也写成2/2/2023122

子蝶式(subbutterfly)B(k)

最低k位的高低位互换

超蝶式(superbutterfly)B(k)

最高k位的高低位互换 显然成立：2/2/20231234.反位序互连网络(BitReversalpermutation)

即将输入x的二进制编码的位序颠倒就可得到输出端的二进制编码。子反位序函数，最低k位的位序反过来;超反位序函数，最高k位的位序反过来.对于N=8,n＝3的情况，正好有：R＝B，R(2)＝B(2)，R(2)＝B(2)。2/2/20231242/2/20231255.移数互连网络(shiftpurmutation)α(x)＝(x＋1)mod2n0≤x≤N移数互连函数相当于把N个输入端的二进制编码同时移动一个位置。即把x的n位二进制编码的末位上加上“1”再取模2n，就是输出端的二进制编码。例：N＝8＝23时的移数互连α(x)。0000010100111001011101110000010100111001011101112/2/2023126移数互连函数用x的十进制编码更容易表示。一般地，如果需要把N个输入端同时移动m个位置传到输出端，则移数互连函数可写为：α(x)＝(x＋m)modN

0≤x≤N例：N＝8，m＝2的移数互连01234567012345672/2/20231276.PM2I互连网络PM2I互连网络是“加减2i”单级网络的简称，又称循环移数网。它的互连函数为移数互连网络的特例：PM2±i（j）＝（j±2i）modN式中：0≤i≤n－1，0≤j≤N－1，n＝log2N，N是网络中的结点数。这种互连网络中共有2n个互连函数。2/2/2023128例：N＝8时，PM2＋0，PM2＋1和PM2＋2互连网络2/2/202312901234567PM2＋001234567PM2＋101234567PM2±22/2/2023130只需将PM2＋0和PM2＋1中相应的箭头反向即可实现PM2－0和PM2－1的连接，且PM2＋2＝PM2－2在通用情况下：PM2＋(n－1)＝PM2－(n－1)在N相同的情况下，PM2I网络比立方体网络具有更好的连接性。例如，在PM2I网络处理单元0可直接与处理单元1，2，4，6，7相连，而立方体网络中0只能与1，2，4相连。2/2/20231317.混洗交换互连网络混洗交换互连网络由全混洗Shuffle(x)和交换网络Exchange0(x)复合而成。也写成2/2/20231327例：N＝8时的混洗交换互连网络01234560000010100111001011101110000010100111001011101112/2/2023133N＝8时的混洗交换互连网络可以看作由Cube0交换函数和全混洗函数复合得到。其中最远的全“0”和全“1”两个PE间的连接需要n次交换和n－1次混洗才能实现，所以的最大距离为2n－1。2/2/2023134三种基本单级网络的比较互连函数个数网络最大距离（网络直径）PM2I2n－1交换nn混洗交换22n－12/2/2023135互连函数举例假设16个处理机的编号分别为0、1、…、15，采用单级互连网络。互连函数分别为：(1)Cube3(2)PM2+3(3)PM2-0(4)Shuffle(5)Butterfly(6)Reversal第12号处理机分别与哪一个处理机相连？2/2/2023136解：16个处理器，需4位二进制表示，故：(12)10=(1100)2

(1)Cube3，1100最高位取反得0100，

4号处理机

(2)PM2+3，

(12+8)MOD16=4，

4号处理机

(3)PM2-0，

12–1=11，

11号处理机

(4)Shuffle，

1100循环左移1位得到1001,

9号处理机

(5)Butterfly，1100的最高最低位交换0101,5号处理机

(6)Reversal，

1100的位序反过来为0011,

3号处理机2/2/20231377.3.3多级互连网络单级互连网络通常只能实现有限几种基本连接，不能实现任意处理单元之间连接。为实现任意处理器间的互连，可采用的方法有：①利用时间重复性，将同一套单级互连网络循环使用。特点：节省器材，但由于输入、输出控制部分较为复杂，因此工作速度较慢，一般不采用。②采用空间重复性，将多套单级互连网络串接使用。特点：缩短了通过时间，提高了速度，可将多种单级互连网络进行灵活组合以适应多种算法的需要，但增加了成本。2/2/2023138ISC1，ISC2，……，ISCn构成的通用多级互连网络结构2/2/20231391.决定多级互连网络特性的主要因素(1)交换开关交换开关是组成互连网络的基本单元。一个a×b开关模块中有a个输入和b个输出。在理论上a和b不一定要相等，但实际上常选择使

a＝b＝2k，k≥1。如：常用的开关模块的大小：2×2，4×4，8×8在交换开关的作用下，每一个输入可与一个或多个输出相连，但在输出端必须避免发生冲突。即输入与输出允许一对一或一对多的映射，但不允许多对一的映射。2/2/2023140只允许一对一映射的开关称为交叉开关。例：2×2交换开关的功能：直通、交换、上播、下播。四功能开关：具有直通、交换、上播、下播功能。二功能开关（交叉开关）：具有直通、交换功能。2/2/20231412/2/2023142(2)拓扑结构用于表示网络间各级输入端与输出端相互连接的规则或连接模式。将各种单级互连网络进行不同组合，可构成各种具有不同连接特性的多级互连网络。(3)控制方式控制方式是指对各交换开关进行控制的方式①级控同一级的所有交换开关都受同一控制信号控制，对一个n级网络就需要n个控制信号。2/2/2023143②单元控制每一个交换开关都有一个单独的控制信号，各自处于不同的状态。单元控制的控制电路较为复杂，但灵活性较高。③部分级控对不同的级采用不同数量的控制信号。例如，第0级采用1个控制信号，第1级采用2个控制信号，而第2级采用3个控制信号等，即用i＋1个控制信号控制第i级，0≤i≤n－1，n为级数。为了方便，规定用写在交换单元中的文字代表控制信号。若不同框中是同一文字，则表示它们所用的控制信号相同。2/2/20231442.常用的多级互连网络下面讨论的多级互连网络均为具有N个输入端、N个输出端，且级数等于n＝log2N的条件下的基本多级互连网络。⑴多级立方体网络由n个Cubei网络串连构成，其中0≤i≤n－1。因为在单级立方体网络中，网络的最大距离为n。所以重复n次使用单级互连网络，就可以实现任意两个结点的连接。在多级立方体网络中将n个单级立方体网络串连，让每一级实现一种互连函数E(x)kk＝0，1，…，n－1，就可以实现任意两个结点的连接。2/2/2023145多级立方体网络通常采用二功能交换开关构成，根据控制方式的不同分为STARAN网络和间接二进制n方体网络等。STARAN网络采用级控制和部分级控制。间接二进制n方体网络采用单元控制方式。2/2/2023146例：将具有Cube0，Cube1和Cube2三种互连函数的三个单级立方体网串接起来构成多级立方体STARAN网络。2/2/2023147①对0～2级采用级控方式，“1”控制开关为交换方式，“0”控制开关为直通方式。当级控信号为“101”时，输出与输入的对应关系为：0—5，1—4，2—7，3—6，4—1，5—0，6—3，7—2。采用不同的级控信号，可实现不同的交换功能。2/2/2023148②对各级开关采用部分级控方式。例如，0级级控信号为“0”，1级级控信号为“1”，2级中I、J级控信号为“1”，K、L级控信号为“0”时，输出与输入的对应关系为：0—2，1—3，2—4，3—5，4—6，5—7，6—0，7—1。实现了移2（mod8）功能2/2/2023149(2)多级混洗交换网络多级混洗交换网络又称OMEGA网络，由n级相同的网络组成，每一级都包含一个全混洗拓扑和随后一列N/2个四功能交换单元，采用单元控制方式。n级混洗交换网络的互连函数可以表示成：PSE(n)＝(σ(n)ε(0))n四功能交换单元根据控制信号可分别完成恒等、交换、上播和下播功能。2/2/2023150三级混洗交换网络2/2/2023151在OMEGA网络中，各级的编号顺序与多级立方体网络正好相反。当采用级控方式时，OMEGA网络成为STARAN网络的逆网络。当采用单元控制方式时，OMEGA网络成为间接二进制N方体网络的逆网络。OMEGA网络与多级立方体网络之间的差别：①前者的数据流向与后者的数据流向正好相反。②前者采用四功能交换开关，而后者采用二功能交换单元。由于OMEGA网络采用四功能交换开关，因此允许同时实现一个入端到多个出端的连接，具有更多的灵活性。2/2/2023152例：将输入端2连接到所有输出端的控制信号为：C、I、J、K、L采用上播，E、F采用下播。2/2/2023153例：实现置换（0，7，6，4，2）（1，3）（5）的控制信号为：2/2/2023154分析：实现置换（06473）（15）（2）的控制信号怎么安排？阻塞出现：A、D、G、I、L==〉阻塞网络2/2/20231552/2/2023156

一般说来，一个n输入的Ω网络需要log2n级2×2开关，每级要用n/2个开关模块，网络共需(nlog2n)/2个开关。每个开关模块采用单元控制方式。

不同的开关状态组合可实现各种置换、广播或从输入到输出的其它连接。2/2/2023157(3)多级PM2I互连网络多级PM2I互连网络又称为数据交换网络。各级中的处理单元按PM2I互连函数进行连接。该网络由log2N+1列开关单元和log2N级互连网络构成。例：N＝8，n＝log28＝3，各级处理单元按PM2I互连函数连接起来，其中：第0级：完成PM2I±0。第1级：完成PM2I±1。第2级：完成PM2I±2。第i级的每个输入端j都有三根连接线分别连到输出端j、(j＋2i)modN和(j－2i)modN。2/2/20231582/2/2023159在第2级中，因为(x＋22)mod8＝(x－22)mod8，为到同一处理单元提供了冗余通路，有利于提高可靠性。进一步，因为单级PM2I网络的网络直径为，但组成多级PM2I互连网络时用了n级，所以在网络中提供了冗余通路，有利于提高可靠性。2/2/2023160(4)基准网络基准网络可如下图(a)所示递归生成。

第1级为一个N×N模块，第2级为两个(N/2)×(N/2)子模块，以C0和C1表示。以上构成方法可递归用于子模块，直至得到2×2的N/2子模块为止。各小框和最终的子模块构件是2×2开关，每个有两个合法连接状态：两个输入和两个输出间的直送和交叉连接。16×16基准网络如下图(b)所示。

2/2/2023161（a）递归构成

2/2/2023162（b）16×16基准网络

2/2/20231637.3.4消息寻径方式(略)消息传递机制的研究在互连网络的研究中占有非常重要的地位。

一.消息格式1.消息、包和片等术语消息（Message）：是在多计算机系统的处理接点之间传递包含数据和同步消息的信息包。它是一种逻辑单位，可由任意数量的包构成。包（Packet）：包的长度随协议不同而不同，它是信息传送的最小单位，64-512位。片（Flit）：片的长度固定，一般为8位。2/2/20231642.格式

消息寻径中的信息单位如图所示。消息是结点间通信的逻辑单位，它常常由任意数目的长度固定的包组成，因此它的长度是可变的。

2/2/20231652/2/2023166

包是包含寻径目的地址的基本单位。由于不同的包可能异步地到达目的结点，因此每个包需要一个序号，以便把传递的消息重新装配起来。

可以进一步把包分成一些固定长度的数据片。寻径信息(目的地址)和序号形成头片，其余的片是数据片。

在采用存储转发寻径方式的多计算机系统中，包是信息传送的最小单位。在采用虫蚀寻径网络的多计算机中，包可以进一步分成片。片的长度往往受网络大小的影响。256个结点的网络需要片长为8位。2/2/2023167包的长度取决于寻径方式和网络的实现方法。典型的包的长度为64～512位。序号可能占用1～2个片，取决于消息的长度。包和片的大小还与通道频宽、寻径器设计以及网络流量密度等有关。

二.四种寻径方式

消息寻径方式可以分为两大类：线路交换和包交换。其中包交换又包括：存储转发寻径、虚拟直通寻径和虫蚀寻径等。2/2/2023168(1)线路交换(circuitswitch)：在线路交换这种寻径方式下，在传递一个消息之前，先建立一条从源结点到目的结点的物理通路，然后再传递消息，如图所示。

其传输时延用公式表示为T＝(Lt/B)×D+L/B，Lt为建立路径所需的小信息包的长度，L为信息包的长度，D为经过的结点数，B为带宽(以下同)。

在并行计算机中的频繁的小信息包通信的这种方式下，由于在传递一个消息之前，需要频繁地建立从源结点到目的结点的物理通路，开销将会很大，这种寻径方式与以下的几种包交换(packetswitch)的寻径方式相比这是一个很大的缺点。包交换的寻径方式以其较高的传输带宽和较低的平均传输时延，更适合于具有动态和突发特性的MPP数据传送。2/2/20231692/2/2023170

(2)存储转发寻径(storeandforward)：在存储转发网络中包是信息流的基本单位。每个结点有一个包缓冲区。包从源结点经过一系列中间结点到达目的结点。

当一个包到达一个中间结点时，它首先被存入缓冲区。当所要求的输出通道和接收结点的包缓冲区可使用时，然后再将它传送给下一个结点。如图7.26(b)所示。

存储转发网络的时延与源和目的地之间的距离(段数)成正比。第一代多计算机系统采用这种寻径方式。其时延用公式表示为T＝(L/B)×D+L/B=(D+1)×L/B。2/2/20231712/2/2023172(3)虚拟直通(virtualcutthrough)：目前有一些多计算机系统采用的是虚拟直通的寻径方式。虚拟直通的寻径方式的思想是，为了减少时延，没有必要等到整个消息全部缓冲后再作路由选择，只要接收到用作寻径的消息头部即可判断。

其通信时延用公式表示为T=(Lh/B)×D+L/B=(Lh×D+L)/B，Lh是消息的寻径头部的长度。一般来说，L>>Lh×D，所以公式可以近似为T＝L/B，可以看到此时通信时延与结点数无关，这相对于存储转发的寻径方式来说是一个非常大的改进。2/2/2023173

然而，当出现寻径阻塞时，虚拟直通方式只有将整个消息全部存储在寻径结点中，直到寻径通道不阻塞时才能将消息发出，这就需要每个寻径结点都有足够的缓冲区来存储可能出现的最大的信息包，在这一点上，虚拟直通方式与存储转发的寻径方式是一样的，同样不利于VLSI的实现。因此，虚拟直通方式在最坏的情况下与存储转发方式的通信时延是一样的。由此出现了下面将要讨论的新的寻径方式虫蚀寻径方式，它改进了以上提到的缺点。2/2/2023174(4)虫蚀寻径(wormhole)：新型的多计算机系统很多采用的是虫蚀寻径方式，把包进一步分成更小的片。与结点相连的硬件寻径器中有片缓冲区。消息从源结点传送到目的结点要经过一系列寻径器，如图所示。该寻径由Dally于1986年提出。

同一个包中所有的片象不可分离的同伴一样以流水方式顺序地传送。包可以看作是一列火车，由火车(头片)和被牵引的车厢(数据片)组成。

只有头片知道包将发往何处。所有的数据片必须跟着头片。不同的包可以交替地传送，但不同包的片不能交叉，否则它们可能被送到错误的目的地。2/2/20231752/2/2023176

用头片直接开辟一条以输入链路到输出链路的路径的方法来进行操作。每个消息中的片以流水方式在网络中向前“蠕动”。每个片相当于虫的一个节，“蠕动”是以节为单位顺序地向前爬行。

当消息的头片到达一个结点A的寻径器后，寻径器根据头片的寻径消息立即做出路由选择：

如果所选择的通道空闲且所选择的结点B的片缓冲区可用，那么这个头片就不必等待，直接通过结点A传向下一个结点B。随后的其它数据片跟着相应地向前“蠕动”一步。当消息的尾片向前“蠕动”一步之后，它刚才所占有的结点就被放弃了。2/2/2023177

为了实现上述的一个包内相继片的异步流水操作，采用如图所示的握手协议。(a)沿着路径，相邻寻径器之间有一根一位的就绪/请求(R/A)线。当接收寻径器(D)就绪时，就可以接收一片，即片缓冲区可用了，R/A线的电平变低。(b)当发送的寻径器(S)就绪时，R/A线的电平变高并通过通道传送片I。当D正在接收片时，R/A线保持高电平。(c)当片i从D的缓冲区移走后(即传送到下一个结点)，重复上述操作过程以便传送片i+1，直到整个包都被接收。2/2/20231782/2/2023179虫蚀寻径的通信时延用公式表示为：

T=Tf×D+L/B=(Lf/B)×D＋L/B=(Lf×D＋L)/B

其中，Lf是片的长度，Tf是片经过一个结点所需时间。

一般来说，L>>Lf×D，所以公式可以近似为：T＝L/B，可以看到此时通信时延也与结点数无关。

(5)虫蚀寻径的优点：

(a)每个结点的缓冲区较小，易于VLSI实现。2/2/2023180

(b)较低的网络传输时延。所有的片以流水方式向前传输，采用了时间并行性。而存储转发方式的消息包整个地从一个结点“跳”到另一个结点，通道的使用是串行的，所以它的传输时延基本上正比于消息在网络中传输的距离。虫蚀寻径方式的网络传输时延正比于消息包的长度，传输距离对它的影响很小。

(c)通道共享性好，利用率高，对通道的预约和释放是结合在一起的一个完整的过程，有一段新的通道后将立即放弃用过的一段旧通道。

(d)易于实现选播和广播通信方式。允许寻径器复制消息包的片并把它们从其多个输出通道输出。2/2/20231817.4多处理机多处理机结构由若干台独立的计算机组成，每台计算机能够独立执行自己的程序，属于MIMD系统。多处理机系统的目的是开发粗粒度的并行性，即作业或任务级的并行性。在多处理机系统中存在有多个指令控制流，每个指令控制流分别独立地对共享主存中数据进行加工或是对自己私有局部存储器中的数据对象进行加工。处理器之间按某种形式互连，实现程序之间的数据交换和同步。多处理机系统中处理器之间通过适当的通信，可以协同求解