【教学课件】第六章-并行处理技术

第六章并行处理技术北京航空航天大学计算机学院2005年5月2021/8/171第六章并行处理技术北京航空航天大学计算机学院2021/什么是并行处理为什么要开发并行处理技术并行机的分类及基本结构并行处理的基本问题和技术主要内容2021/8/172什么是并行处理主要内容2021/8/172多个处理单元(acollectionofcomputingelements)协作、通信（cooperate&communicate）快速求解大型问题（tosolvelargeproblemsfast）并行体系结构：用通信体系结构(CommunicationArchitecture)对传统的体系结构进行扩展。并行处理的基本问题2021/8/173多个处理单元(acollectionofcomputi处理器之间协同的基础是什么？互连与通信编程人员使用何种方式编程？编程模型如何保证并行程序的正确性？存储一致性并行处理的基本问题2021/8/174并行处理的基本问题2021/8/1741、互连与通信的问题互连网络的定义及特性静态网络动态网络多处理器通信问题并行处理的基本问题2021/8/1751、互连与通信的问题并行处理的基本问题2021/8/175

并行计算机往往采用多个处理节点。其根本思想就是将要完成的任务尽量分布到各个处理节点并发执行，在最理想的情况下并行计算机的性能是所有节点计算性能的简单相加。但是由于节点间存在着通信延时和各个节点间的同步关系，使得系统的整体性能通常达不到理想情况。比如在某些MPP上其持续速度只是峰值速度的3%～10%。同时，并行计算也逐步向着松耦合（looselyCoupled）和复杂化的方向发展。大量的SMP集群(CLUMPs)的出现，使得并行计算机内部节点与节点间的通信瓶颈愈发明显。因此，解决并行计算机的通信问题也就成为了一个研究的热点。互连与通信的问题2021/8/176并行计算机往往采用多个处理节点。其根互连与通信的问题互连网络的定义及特性定义：由开关元件按一定拓扑结构和控制方式构成的网络，以实现计算机系统内部多个处理机或多个功能部件间的相互连接。互连网络对并行处理机的性能影响很大，是系统构成的主要部分。互连网络有三大要素，即互连拓扑（包括连接通路）、开关元件和控制方式。由于这三大要素的工作方式和所处的地位不同，才出现了各种各样的互联网络。2021/8/177互连与通信的问题互连网络的定义及特性2021/8/177操作方式：同步通信（SynchronousCommunication)：收发双方必须在时间上同步。这类似于电话网中需要呼叫方和被呼叫方同步。异步通信(AsynchronousCommunication)：收发双方不需要同步。这类似于发送和接收mail。互连与通信的问题2021/8/178操作方式：互连与通信的问题2021/8/178控制策略：集中控制(Centralizedcontrol)：互连网络中的各级互连开关由一组信号统一控制。其优点是控制简单，实现容易，但网络的灵活性相对较差。分布控制(Distributedcontrol)：互连网络中的各级互连开关由多个或多组信号分别控制，各（组）开关可处于不同状态。其优点是网络的灵活性强，但控制相对复杂，实现相对困难。互连与通信的问题2021/8/179控制策略：互连与通信的问题2021/8/179

电路交换(Circuitswitching)：采用与电话网类似的方式，在数据传输期间，从发送节点到接收节点的整个连接通路必须保持。

优点：信息的传输延迟小，对一次接续而言，传输时延固定不变。信息的编码方案和信息格式由双方协调，不受网络限制。缺点：电路资源被通信双方独占，电路利用率低。交换方式：

分组交换(Packetswitching)：采用存储转发方式，把数据分解成许多比较短的、规格化的片段，进行交换和传输。优点：为用户提供了灵活的通信环境（不同速率、不同代码、不同通信协议机制等）。实现线路动态统计复用，通信线路利用率高，可以在一条物理线路上同时提供多条信息通路。可靠性高，经济性好。缺点：由于网络附加的传输信息较多，对长报文通信的传输效率比较低。技术实现复杂。互连与通信的问题2021/8/1710电路交换(Circuitswitching)：采用与网络拓扑结构：

静态网络(Staticnetwork)静态网络的特点与指标典型的静态网络 动态网络(Dynamicnetwork)互连函数多级互联网络互连与通信的问题2021/8/1711网络拓扑结构：互连与通信的问题2021/8/1711A.静态网络的特点

静态网络由点—点直接相连而成，这种连结方式在程序执行过程中不会改变。

如果用图来表示，结点代表开关，边代表通信链路，则：结点间的链路无源，不能重构；开关元件与处理机相连；不直接相连结点间的通信需通过中间结点中转。静态网络的特点与指标2021/8/1712A.静态网络的特点静态网络的特点与指标2021/8/1712B.静态网络的指标结点度：与结点相连接的边（链路或通道）数，表示节点所需要的I/O端口数，模块化要求结点度保持恒定。根据通道到结点的方向，结点度可以进一步表示为：

结点度=入度+出度 其中入度是进入结点的通道数，出度是从结点出来的通道数。距离：与两个结点之间相连的最少边数。网络直径：网络中任意两个结点间距离的最大值。静态网络的特点与指标2021/8/1713B.静态网络的指标静态网络的特点与指标2021/8/1713网络规模：网络中结点数，表示该网络功能连结部件的多少。等分宽度：某一网络被切成相等的两半时，沿切口的最小边数称为该网络的等分宽度。结点间的线长：两个结点间的线的长度。对称性：从任何结点看，拓扑结构都一样，这种网络实现和编程都很容易。结点是否同构。通道是否有缓冲。静态网络的特点与指标2021/8/1714网络规模：网络中结点数，表示该网络功能连结部件的多少。静态网 1).线性阵列对N个结点的线性阵列，有N-1条链路，直径为N-1（任意两点之间距离的最大值），度为2，不对称，等分宽度为1。N很大时，通信效率很低。典型的静态网络2021/8/1715 1).线性阵列对N个结点的线性阵列，有N-1条链路，直径

2).环对N个结点的环，考虑相邻结点数据传送方向：

单向环：链路数为N，直径N-1，度为2，对称，等分宽度为2。

双向环：链路数为N，直径N/2，度为2，对称，等分宽度为2。比如KSR-1（1990）。典型的静态网络2021/8/1716 2).环对N个结点的环，考虑相邻结点数据传送方向：典型的3).带弦环对上图中12个结点的带弦双向环，结点度为3：链路数为18，直径4（比如红色结点），度为3，不对称，等分宽度为2。度为3的带弦环度为4的带弦环

结点度为4：链路数为24，直径3（比如红色结点），度为4，对称，等分宽度为8。典型的静态网络2021/8/17173).带弦环对上图中12个结点的带弦双向环，度为3的带弦环度4).链接（全互联）

链接是带弦环的一种特殊情形。链接中的每个结点和其他结点之间都有单一的直接链路。如下图中8个结点的链接：

有28条链路，直径为1，度为7，对称，等分宽度为16。 典型的静态网络2021/8/17184).链接（全互联） 有28条链路，直径为1，度为7，对称，

5).树形

4层的二叉树

一棵K层完全二叉树应有N=2K-1个结点，对大结点度为3，直径为2（K-1）（即右边任意一个叶子结点到左边任意一个叶子结点）。不对称，等分度为1。 由于结点度为常数，所以树是一种可扩展的系统结构。K=4典型的静态网络2021/8/1719 5).树形 4层的二叉树 一棵K层完全二叉树应有N=

树形的扩展：

带环树二叉胖树

这两种结构都可以缓解根结点的瓶颈问题。典型的静态网络2021/8/1720 树形的扩展： 带环树二叉胖树 这两种结构都可以缓

6).星形

星形实际上是一种二层树（如右图）。有N个结点的星形网络，有N-1条链路，直径为2，最大结点度为N-1，非对称。 典型的静态网络2021/8/1721 6).星形 星形实际上是一种二层树（如右图）。有N

有N个结点的rr网（其中 )，有2r(r-1)

=2N-2r条链路，直径为2（r-1)，结点度为4，非对称，等分宽度为r。

7).网

r-1条边R个节点典型的静态网络2021/8/1722 有N个结点的rr网（其中 )，有2r(r-1)=

有N个结点的rr网（其中 )，有2N条链路，直径为r-1，结点度为4。

网的变形：

Illiac网

典型的静态网络2021/8/1723 有N个结点的rr网（其中 )，有2N条链路，直径为r

有N个结点的rr网（其中 )，有2N

条链路，直径为2r/2，结点度为4，对称。

网的变形：

环形网（2D—Torus）

典型的静态网络2021/8/1724 有N个结点的rr网（其中 )，有2N条链路，

网的变形：搏动式阵列（SystolicArray）

典型的静态网络2021/8/1725 网的变形：搏动式阵列（SystolicArray）

8).超立方体0-立方体1-立方体2-立方体3-立方体4-立方体典型的静态网络2021/8/1726 8).超立方体0-立方体1-立方体2-立方体3-立方体4

一个n-立方体由N=2n个结点构成，它们分布在n维上，每维有两个结点。直径为n，结点度为n，对称。由于结点度随维数线性增加，所以超立方体不是一种可扩展结构。

例子：

Intel的iPSC/1、iPSC/2、nCUBE典型的静态网络2021/8/1727 一个n-立方体由N=2n个结点构成，它们分布在n维上，

9).带环立方体

一个带环n-立方体由N=2n个结点环构成，每个结点环是一个有n个结点的环，所以结点总数为n2n个。直径通常为2n，结点度为3，对称。带环3-立方体典型的静态网络2021/8/1728 9).带环立方体 一个带环n-立方体由N=2n个结点

特点：

网络的开关元件有源，链路可通过设置这些开关的状态来重构。 只有在网络边界上的开关元件才能与处理机相连。动态网络2021/8/1729 特点：动态网络2021/8/1729

互连函数是一级动态互联网络的一种抽象描述，是从输入到输出的一个映射。

排列：N个数的每一种有确定次序的放置方法叫做一个N排列。

置换：把一个N排列变成另一个N排列的变换叫做N阶置换。 在有N个输入端和N个输出端的网络中，输入端和输出端的连接关系可以用置换来表示（输入端与输出端一一对应）。互联函数2021/8/1730互连函数是一级动态互联网络的一种抽象描述，是从输入到输出1).恒等函数其中，Xn-1Xn-2

Xk

X0是PE的地址（通常为二进制）。n为3时的恒等函数的连接情形如下：000001010011100101110111000001010011100101110111互联函数2021/8/17311).恒等函数其中，Xn-1Xn-2XkX2).方体函数（cube0，cube1，…，cuben-1)方体函数是由n个互连函数组成，其中0kn。比如，n为3时，3-立方体各结点地址如下：YZX010011110000111001100101互联函数2021/8/17322).方体函数（cube0，cube1，…，cuben-1000001001000010011011010100101101100110111111110Cube0:01234567YZX010011110000111001100101互联函数2021/8/1733000001001000010011011010100101Cube1:00001000101101000001100110010111011110010111011101234567YZX010011110000111001100101互联函数2021/8/1734Cube1:000010001011010000011001Cube2:01234567000100001101100000010011101110111001010011110111YZX0100111100001110011001012021/8/1735Cube2:0123456700010000110110000000003).洗牌函数：

均匀洗牌（Shuffle-Exchange)11111101234567001010010100011110100001101011110101201012)(XXXXXXSh=互联函数2021/8.洗牌函数：均匀洗牌（Shuffle-E子洗牌即最低k位循环左移一位。000000001010010001011011110111111100100110101101012345671020121)(XXXXXXSh=互联函数2021/8/1737子洗牌即最低k位循环左移一位。000000001010010超洗牌即最高k-1位循环左移一位。0210123)(XXXXXXSh=00000000100101010001010001110101110111011111111001234567互联函数2021/8/1738超洗牌即最高k-1位循环左移一位。0210123)(XXXX000000逆洗牌函数11111101234567001100010001011101100010101110110011互联函数2021/8/1739000000逆洗牌函数1111110123456700110000000010010101101111111012345674).蝶式001100100001110011011110互联函数2021/8/17400000000100101011011111110123455).PM2I函数（加减2i）

共有2n个互连函数，对N个结点的网络为例1：

N=8（8个结点），则n=log28=3，所以：i=0，1，2；j=0，1，…，7。 6个PM2I函数如下：互联函数2021/8/17415).PM2I函数（加减2i）例1：互联函数2021/8/PM2+0: (01234567）01234567PM2-0: (76543210）01234567互联函数2021/8/1742PM2+0: (0123456PM2+1: (0246）（1357）01234567PM2-1: (6420）（7531）01234567互联函数2021/8/1743PM2+1: (0246）（135PM2

2: (04）（15）（26）（37）01234567互联函数2021/8/1744PM22: (04）（15）（26）（3 A.多级网络的三要素

（1）开关单元：a个输入a个输出的开关单元记做aa的开关单元，其中，a是2的整数倍。常见的有2

2、44、88等。 根据开关单元功能的多少，2

2又可以分为两功能和四功能开关。如下图所示：多级互连网络2021/8/1745 A.多级网络的三要素多级互连网络2021/8/17450101直送0101交叉0101上播0101下播多级互连网络2021/8/17460101直送0101交叉0101上播0101下播多级互连网络

（2）级间互连模式（InterStageConnection）： 均匀洗牌、蝶式、多路洗牌（比如四路洗牌即是把牌平均分成4份，然后4堆分别进行均匀洗牌）、纵横开关（CrossSwitch)及立方体连结等。 （3）控制方式

级控制：每级只有一个控制信号

单元控制：每个开关一个控制信号

部分级控制：几个开关合用一个控制信号多级互连网络2021/8/1747 （2）级间互连模式（InterStageConnecti

B.Ω网0123456701234567第0级第1级第2级201012)(XXXXXXSh=2021/8/1748 B.Ω网0123456701234567第0级第1级第2

Ω网的特点：

开关单元：22四功能开关

ISC：洗牌变换

控制方式：采用单元控制方式。当目的地址编码从高位开始的第i位（从0开始）为0时，第i级的22开关的输入端与上输出端连接，否则输入端与下输出端连接。 例子：

UIUC的Cedar IBM的RP3 NYU的Ultracomputer多级互连网络2021/8/1749 Ω网的特点：多级互连网络2021/8/17490123456701234567第0级第1级第2级

无阻塞的实现置换

π1=（07642）（13）（5）多级互连网络2021/8/17500123456701234567第0级第1级第2级 无阻塞的0123456701234567第0级第1级第2级

置换π2=（06473）（15）（2）

在开关F、G、H、I和J上发生阻塞FGHJI多级互连网络2021/8/17510123456701234567第0级第1级第2级 置换π

Ω网的特点(2)：

并不是所有的置换在Ω网中一次通过便可以实现。 Ω网是阻塞网络：出现冲突时，可以采用几次通过的方法来解决冲突。多级互连网络2021/8/1752 Ω网的特点(2)：多级互连网络2021/8/17520123456701234567第0级第1级第2级

Ω网的广播功能：

0018个输出端多级互连网络2021/8/17530123456701234567第0级第1级第2级 Ω网的广44开关构成的Ω网：多路洗牌

如16输入4路洗牌：网路级数为log416=2

01第1级234567891011121314150123456789101112131415第0级级间变换:Sh(Sh())可以认为是由4个2*2开关组成多级互连网络2021/8/175444开关构成的Ω网：多路洗牌01第1级2345678910

Ω网的特点(3)：

当采用kk开关元件时，则可以定义k路洗牌函数来构造更大的级数为logkn的Ω网络。多级互连网络2021/8/1755 Ω网的特点(3)：多级互连网络2021/8/1755

C.蝶式网络（Butterflyswitchnetwork）

蝶式网络的开关不允许广播功能，它实际上是Omega网的一个子集。 两级6464的蝶式网络如下图所示：它采用16个88交叉开关构成，两级间采用8路洗牌连接。多级互连网络2021/8/1756 C.蝶式网络（Butterflyswitchnetw8888880...7888888第1级第0级8...1556...63.........078155663........................两级6464的蝶式网络多级互连网络2021/87888888第1级第0级8.1

总线本质上是一组导线和插座，用于处理器、存储模块和外围设备之间的数据传输。系统总线用于主设备如处理器和从设备如存储模块之间传输数据。总线仲裁逻辑每次只授予一个请求存储总线，因此也称争用总线。单总线层次总线

总线2021/8/1758总线本质上是一组导线和插座，用于处理器、存储模块和外围设

目前已建立了许多标准总线，例如PCI、VME、Multibus、Sbus、MicroChannel、IEEEFuturebus。大多数总线在构造单处理机系统时价格很低。我们关心的是多处理机总线和层次总线，用它们来构造SMP、NUMA和DSM机器。这些可扩展的总线一般用硬件来支持高速缓存一致性、快速多处理机同步、以及分离事务中断处理等。

总线2021/8/1759 目前已建立了许多标准总线，例如PCI、VME、MMPC高速缓存IF系统总线（在底板或中夹板上）局部总线存储器存储器总线CIFIOPIFIFIFIFC缓存器缓存器局部总线局部总线CPU板I/O板网络接口卡以太网打印机磁盘存储板总线2021/8/1760MPC高速缓存IF系统总线（在底板或中夹板上）局部总

总线互连的缺陷总线有多个处理机分时共享，因此即使当总线带宽很高，每个处理器的带宽也只是总带宽的一部分。此外总线由于缺乏冗余机制易于出错，请总线也有有限的可扩展性。这些缺陷主要是受封装技术和价格因素的约束。总线一般限制在很小的机架内，当层次总线扩展到几个机架时，始终扭转和全局时问题就变得难于克服。使用交叉开关和多级网络代替总线结构将在一定程度上克服这些缺陷。

总线2021/8/1761 总线互连的缺陷总线2021/8/1761基本术语与性能指标通信方式寻径算法软件开销多处理器通信问题2021/8/1762基本术语与性能指标多处理器通信问题2021/8/1762基本通信方式

无论网络拓扑结构如何，高性能计算机节点间通信对于用户是透明的。其通信模式无外乎以下4种：单播(Unicast):一个源节点到一个目的节点；多播(Multicast):一个源节点到多个目的节点;广播(Broadcast):一个源节点到全体节点；会议(Conference):多个源节点到一个目的节点。多处理器通信问题2021/8/1763基本通信方式多处理器通信问题2021/8/1763

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

它们的相互关系如下图：基本术语与性能指标2021/8/1764 1).消息、包和片基本术语与性能指标2021/8/176包……消息包据片头片尾片……顺序号数片bbbbbbbb基本术语与性能指标2021/8/1765包……消息包据片头片尾片……顺序号数片bbbbbbbb基本术

2).互连网络

互连网络用来在多处理机(计算机)系统的处理结点之间传递消息。

互连网络性能的两个重要指标：

传输时延（TransmissionLatency）

吞吐量（Throughput）

互连网络的描述：

拓扑（Topology）

寻径算法（Routing）

流控制（FlowControl）基本术语与性能指标2021/8/1766 2).互连网络 互连网络性能的两个重要指标：用户程序

3).传输时延与吞吐量

一个消息的传输时延：从它在源结点进行发送初始化到它在目的结点完整的被接收所耗费的时间。基本术语与性能指标2021/8/1767用户程序 3).传输时延与吞吐量基本术语与性能指标2021/

一个网络的传输时延：在一定条件下发送消息的平均时延。

网络的吞吐量：单位时间内网络所能传输的消息数目或长度。基本术语与性能指标2021/8/1768 一个网络的传输时延：在一定条件下发送消息的平均时 4).传输时延的公式

其中，Ts称为建立时延，Tn称为网络时延，Tb称为阻塞时延。 它们具体定义如下：基本术语与性能指标2021/8/1769 4).传输时延的公式 其中，Ts称为建立时延，Tn称

建立时延Ts：一个消息在源结点和目的结点上装配和分解、从存储器拷贝到通信缓冲区以及正确性验证等所耗费的时间。它和机器本身的硬件、软件技术有关。

其中：

Tss称为源结点时延：从发送进程开始消息发送初始化到消息的头部进入网络所经历的时间。

Tsd称为目的结点时延：从消息的尾部到达目的结点到消息完全被接收进程接收所经历的时间。基本术语与性能指标2021/8/1770 建立时延Ts：一个消息在源结点和目的结点上装配和分TssTsd基本术语与性能指标2021/8/1771TssTsd基本术语与性能指标2021/8/1771

网络时延Tn：消息头部从源结点进入网络到消息的尾部到达目的结点的时间间隔。其中：

TpD称为结点时延：其中Tp是消息在它所经过的路径上的每个中间结点上的平均时延，D为源结点与目的结点之间中间结点的数量。中间结点上的平均时延中间结点的数量L/B称为线路时延：其中L为消息长度，B为结点之间的通道带宽。基本术语与性能指标2021/8/1772 网络时延Tn：消息头部从源结点进入网络到消息的尾部到达目

阻塞时延Tb：消息传递过程中其他所有可能的时延（主要原因是资源冲突）。基本术语与性能指标2021/8/1773 阻塞时延Tb：消息传递过程中其他所有可能的时延（主要原因

5).网络的拓扑结构

第一代并行计算机：HyperCubeTMC:CM-2Intel:iPSCnCUBE

第二代并行计算机：n—Mesh

Stanford:DashMIT:AlewifeIntel:Paragon基本术语与性能指标2021/8/1774 5).网络的拓扑结构基本术语与性能指标2021/8/177

6).网络的寻径算法

决定发送一个消息到其目的地所经过的路径。 可以分为：

最短路径算法 非最短路径算法 或者：

确定性算法：路径的选择只依赖于它所发送的消息的源结点和目的结点。

可适应算法：消息从结点A到结点B可以由几条不同的路径。基本术语与性能指标2021/8/1775 6).网络的寻径算法基本术语与性能指标2021/8/177

7).网络的流控制

当一个消息在网络中沿着某条路径传送时，互连网络如何来为它分配通道和缓冲器。基本术语与性能指标2021/8/1776 7).网络的流控制基本术语与性能指标2021/8/1776

1)、同步通信方式

同步通信方式是指发送节点和接收节点在时间上和空间上都要同步动作，任何一个环节发生问题，都会形成阻塞。所谓时间上的同步是指发送节点和接收节点必须在做好传送准备后，才能开始进行消息传递。所谓空间上的同步是指从源节点到目的节点的通信路径都已开通。通信方式2021/8/1777 1)、同步通信方式通信方式2021/8/1777发方计算机收方计算机发送接收

因发生阻塞而使计算机节点等待的时间称为同步时间。处于等待状态的处理机是空闲的，特别是通信距离长时，每经过一个中继点，就会发生同步，是同步时间过长，并行处理的效率下降。在同步方式下，一般不设置通信缓冲区，一次传送的数据量不受缓冲区大小的限制。通信方式2021/8/1778发方计算机收方计算机发送接收因发生阻塞而使计2)、异步通信方式

异步通信方式是指在通信通道上设置足够大的缓冲区，发方计算机将消息写入缓冲区，在缓冲区写满之前，不必等待收方节点接收消息；而接收方只需在必要的时候，从缓冲区中把数据读走。在时间上，收发双方不必同步。在空间上，只要缓冲区不满，发方就可以写；缓冲区不空，收方就可以读。异步方式需要足够大的缓冲区，增加了硬件开销，但它是非阻塞的通信系统。通信方式2021/8/17792)、异步通信方式通信方式2021/8/1779发方计算机收方计算机发送接收

同步方式下，发送的数据量和接收的数据量必须相等；而异步方式下没有这种要求，因此，异步方式可以增加并行程序的灵活性。从速度上看，同步方式是收发双方同时工作，数据依次传递成功，而异步方式下，收发双方与缓冲区之间需要传递两次，因此异步方式所用时间较长。通信方式2021/8/1780发方计算机收方计算机发送接收同步方式下，发送的

在使用总线方式的消息传递通路中，可在发放或受方计算机中设置缓冲区，并采用向对方发中断信号的方式进行异步通信。以收方有缓冲区为例：发送方向收方发中断信号后，向接收方的缓冲区发送数据。收到中断信号的接收方计算机中断正常运行的程序，接收缓冲区的数据，接收完成后，重返被中断的程序。发方计算机收方计算机发送接收中断信号通信方式2021/8/1781 在使用总线方式的消息传递通路中，可在发放或受方计算

在使用中断的异步方式中，缓冲区的管理要占用CPU的时间，这与在互连线路中设置缓冲区的方式相比，效率相对要低，但比同步方式要高。发方计算机收方计算机发送接收中断信号通信方式2021/8/1782 在使用中断的异步方式中，缓冲区的管理要占用

介绍四种寻径方式：

存储转发（Store-and-Forward）

虚拟直通（Virtualcutthrough） 线路交换（CircuitSwitching） Wormhole交换（WormholeSwitching)寻径算法2021/8/1783 介绍四种寻径方式： 寻径算法2021/8/1783

1).存储转发 当一个消息到达中间结点A时，A把整个消息放入其通信缓冲器中，然后在寻径算法的控制下选择下一个相邻结点B，当从A到B的通道空闲并且B的通信缓冲器可用时，把消息从A发向B。缺点： 每个结点必须对整个消息进行缓冲，缓冲器较大。 网络时延与发送消息所经历的结点数成正比寻径算法2021/8/1784 1).存储转发寻径算法2021/8/1784

2).虚拟直通

中间结点没有必要等到整个消息全部被缓冲后再作出路由选择，只要消息的目的信息域可用后，就可以作出路由选择。

其中，Lh为消息头部开始到其目的信息域的长度，显然有L>>Lh，所以D的影响比较小。 而当通向下一结点的通道忙或结点的缓冲器非空闲时，必须把整个消息缓冲起来，这时和存储转发一样。寻径算法2021/8/1785 2).虚拟直通 其中，Lh为消息头部开始到其目的信息

3).线路开关

在传递一个消息之前，就为它建立一条从源结点到目的结点的物理通道。在传递的全部过程中，线路的每一段都被占用，当消息的尾部经过网络后，整条物理链路才被废弃。

其中，Lc是为消息建立物理通路所传递的控制信息的长度。当L>>Lh时，D的影响较小。 缺点： 物理通道非共享 传输过程中物理通道一直被占用寻径算法2021/8/1786 3).线路开关 其中，Lc是为消息建立物理通路所传递

4).Wormhole

Dally于1986年提出。 首先把一个消息分成许多片，消息的头片包含了这个消息的所有寻径信息。尾片是一个其最后包含了消息结束符的片。中间的片均为数据片。 片是最小信息单位。每个结点上只需要缓冲一个片就能满足要求。 用一个头片直接开辟一条从输入链路到输出链路的路径的方法来进行操作。每个消息中的片以流水的方式在网络中向前“蠕动”。每个片相当于Worm的一个节，“蠕动”以节为单位顺序的向前爬行。寻径算法2021/8/1787 4).Wormhole寻径算法2021/8/1787

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

（1）如果所选择的通道空闲而且所选择的结点B的通信缓冲器可用，那么这个头片就不必等待，直接通过结点A传向下一个结点B；随后的其它片跟着相应的向前“蠕动”一步。当消息的尾片向前“蠕动”一步后，它刚才所占用的结点就被放弃了。寻径算法2021/8/1788 当消息的头片到达一个结点A的寻径器后，寻径器根据头片

（2）如果所选择的通道非空闲或者所选择的结点的通信缓冲器非可用，那么这个头片就必须在此结点的通信缓冲器中等待，直到上述两者都可用为止；其它片也在原来的结点上等待。此时，被阻塞的消息不从网络中移去，片不放弃它所占有的结点和通道。这是Wormhole技术和其它流控制技术都不同的地方。寻径算法2021/8/1789 （2）如果所选择的通道非空闲或者所选择的结点的通信缓冲器优点：

（1）每个结点的缓冲器的需求量小，易于用VLSI实现。

（2）较低的网络传输延迟。所有的片以流水方式向前传送，时间并形性。而在存储转发中，消息是整个的从一个结点“跳”向另一个结点，通道的使用时串行的。所以它的传输延迟基本上正比于消息在网络中传输的距离。Wormhole与线路开关的网络传输延迟正比于消息包的长度，传输距离对它的影响很小（消息包较长时的情况）。寻径算法2021/8/1790优点：寻径算法2021/8/1790

（3）通道共享性好、利用率高。对通道的预约和释放是结合在一起的一个完整的过程：占有一段新的通道后将立即放弃用过的一段旧通道。

（4）易于实现Multicast和Broadcast。允许寻径器复制消息包的片并把它们从多个输出通道输出。

Wormhole方式中，同一个包中所有的片象不可分离的同伴一样以流水方式顺序的传送。包可看作是一列火车，由火车头（头片）和被牵引的车厢（数据片）组成。寻径算法2021/8/1791 （3）通道共享性好、利用率高。对通道的预约和释放是结合在BABABABABA55交叉开关节点机寻径算法2021/8/1792BABABABABA55节点机寻径算法2021/8/179S时间I1I2D

L/B

D

存储转发（Store-and-forward）寻径技术的时空图寻径算法2021/8/1793S时间I1I2DL/B存储转发（Store-aS时间I1I2D电路开关寻径技术的时空图寻径算法2021/8/1794S时间I1I2D电路开关寻径技术的时空图寻径算法2021/8S时间I1I2D

L/B

D

Wormhole寻径技术的时空图包头数据寻径算法2021/8/1795S时间I1I2DL/BTssTsd软件开销2021/8/1796TssTsd软件开销2021/8/1796传统互连接口性能的主要瓶颈：同一数据反复拷贝，极大增加消息发送的时间。许多研究都表明，数据拷贝占整个发送、接收时间的65％。TCP/IP等上层复杂协议管理机制，不但增加了消息收发的开销，而且占用了大量的CPU资源和存储资源。研究表明，在连接以太网的主机上，35％的通信时间都消耗在TCP/IP的协议处理开销和操作系统的开销之上。由于协议处于操作系统核内，因此用户程序在发送和接收消息时，操作系统在用户态与核心态之间进行切换频繁，增加了开销。软件开销2021/8/1797传统互连接口性能的主要瓶颈：软件开销2021/8/1797提高互连接口性能的手段:(1)

减少数据拷贝次数，实现一次数据拷贝，即用户发送数据直接由用户空间拷贝到接口硬件的缓冲区中，接收的数据直接由接口硬件缓冲区拷贝到用户接收缓冲区中。(2)

简化TCP/IP协议，降低处理开销。复杂的TCP/IP所具有的许多功能是不必要的，必须以精简的消息层、网络层替代。(3)

增强接口硬件的协议处理功能。将上层协议功能由接口板上的快速处理器或专用处理芯片来承担，降低CPU在网络通信处理上的开销。软件开销2021/8/1798提高互连接口性能的手段:软件开销2021/8/1798小结

减小通信时延是提高高性能计算机性能的一项非常关键的技术，其手段大体上有硬件和软件两种。

硬件上：对于通信网络可以通过改进拓扑结构、提高通信速度的手段实现；对于节点可以使用高速缓存、超线程技术等。

软件上：可以通过精简和优化协议改善通信过程的软件开销；同时在更高的层次上，可以通过改善任务划分和处理器的分配，以及适量的任务复制（即在不同节点上执行相同的任务）达到通信时延隐藏的效果。互连与通信的问题2021/8/1799小结互连与通信的问题2021/8/17992、编程模型问题如果能对计算机的系统结构进行高度的抽象，给出一个简洁的概念模型，那么，程序员在编写程序时，就不需要了解硬件结构的具体细节。这种抽象模型就是我们所说的编程模型。并行处理的基本问题2021/8/171002、编程模型问题并行处理的基本问题2021/8/17100

从用户角度看，一个理想的抽象模型应与一台工作站或PC给用户的映象接近，因而可以使用我们最熟悉的传统的编程方式：编程模型问题RAMFileSystemCPU2021/8/17101从用户角度看，一个理想的抽象模型应与一台工作站或PC就并行计算机而言，除了计算单元以外，通信体系结构也是非常重要的一个方面。在为并行计算机编写程序时，就不得不考虑到不同节点上不同进程之间的通信问题，而这是一项非常复杂的工作。因此，在并行编程模型中，就必须对节点之间的通信、同步、协作等各种问题给出很好的定义。共享地址空间、消息传递以及数据并行是最常见的三种并行编程模型。编程模型问题2021/8/17102就并行计算机而言，除了计算单元以外，共享存储：具有统一的地址空间。编程模型问题分布式存储：每个处理器的地址空间单独编址。“大厅式”“包间式”2021/8/17103共享存储：具有统一的地址空间。编程模型问题分布式存储：每个处

例：假设有两台4节点的的多机系统，一台为共享存储，另一台为分布式存储，计算矩阵乘A

B=C。编程模型问题P0P1P3P2SharedMemP0P1P3P2LMLMLMLMLM2021/8/17104例：假设有两台4节点的的多机系统，一台为共享存储，另一台1）、共享存储

将矩阵A按行逻辑的均匀分为4块，矩阵B按列逻辑的均匀分为4块，均存放在共享存储器中。编程模型问题A=(A0，A1，A2，A3)TB=(B0，B1，B2，B3)A0A1A2A3B0B1B2B3

C00C01C02C03C10C11C12C13C20C21C22C23C30C31C32C33=2021/8/171051）、共享存储编程模型问题A=(A0，A1，A2，A3)节点机Pi上程序执行步骤：K=i，j=0；各节点计算Ai

Bk；K=K+1mod4；j++；如果j<4,goto2；编程模型问题2021/8/17106节点机Pi上程序执行步骤：编程模型问题2021/8/17编程模型问题A0A1A2A3B0B1B2B3SharedMemoryP0P1P2P3C00C01C02C03C10C11C12C13C20C21C22C23C30C31C32C33矩阵C2021/8/17107编程模型问题A0A1A2A3B0B1B2B3SharedM2）、分布式存储

矩阵A按行物理的均匀分布在4个计算结点上，而矩阵B则按列物理的分布在4个计算结点上。编程模型问题A=(A0，A1，A2，A3)TB=(B0，B1，B2，B3)A0A1A2A3B0B1B2B3

C00C01C02C03C10C11C12C13C20C21C22C23C30C31C32C33=2021/8/171082）、分布式存储编程模型问题A=(A0，A1，A2，A3节点机Pi上程序执行步骤：K=i，J＝0；各节点计算Ai

Bk；Send(P4+i-1mod4，Bk)；Rev(Pi+1mod4，Bk+1mod4)；K=K+1mod4J++；如果J<4,goto2；编程模型问题2021/8/17109节点机Pi上程序执行步骤：编程模型问题2021/8/17编程模型问题P0P1P3P2A0A1A2A3B0B1B2B3数据分配2021/8/17110编程模型问题P0P1P3P2A0A1A2A3B0B1B2B3编程模型问题P0P1P3P2A0A1A2A3B0B1B2B3C00C11C22C33计算2021/8/17111编程模型问题P0P1P3P2A0A1A2A3B0B1B2B3编程模型问题P0P1P3P2A0A1A2A3B0B1B2B3C00C11C22C33数据交换2021/8/17112编程模型问题P0P1P3P2A0A1A2A3B0B1B2B3编程模型问题P0P1P3P2A0A1A2A3B1B2B3B0C00C11C22C33计算C01C12C23C302021/8/17113编程模型问题P0P1P3P2A0A1A2A3B1B2B3B0编程模型问题P0P1P3P2A0A1A2A3B1B2B3B0数据交换C00C01C11C12C33C30C22C232021/8/17114编程模型问题P0P1P3P2A0A1A2A3B1B2B3B0编程模型问题P0P1P3P2A0A1A2A3B2B3B0B1C00C11C22C33计算C01C12C23C30C02C13C31C202021/8/17115编程模型问题P0P1P3P2A0A1A2A3B2B3B0B1编程模型问题P0P1P3P2A0A1A2A3B2B3B0B1数据交换C00C01C02C11C12C13C33C30C31