计算机系统结构(ch-5)

第5章并行处理技术5.1计算机系统结构中并行性的发展5.2SIMD并行处理机5.3SIMD计算机的互连网络5.4网络特性5.5静态互接网络5.6动态互接网络5.1.1并行性的基本概念1、并行性的定义指在数值计算、数据处理、信息处理或是人工智能等求解过程中可能存在某些可同时进行运算或操作的部分。开发并行性的目的是为了能进行并行处理，以提高计算机系统求解问题的效率。并行性有二重含义，即同时性(simultaneity)和并发性(concurrency)。同时性是指多个事件在同一时刻发生；并发性是指多个事件在同一时间段内发生。

5.1计算机系统结构中并行性的发展2、并行处理的概念是指一种相对于串行处理的信息处理方式，它着重开发计算过程中存在的并发事件。进行并行处理时，每次处理的规模大小可能是不同的，这可用并行性颗粒度(granularity)来表示。粗粒度开发主要采用MIMD方式，开发功能并行性；细粒度开发主要采用SIMD方式，开发数据并行性。5.1.1并行性的基本概念

5.1.1并行性的基本概念3、并行性的等级

层次1作业级（程序）

层次2任务级（程序段或过程）

层次3子任务级（例行程序，子程序）

层次4循环和迭代

层次5语句和指令

粗5.1.2并行性技术的实现途径1.时间重叠（timeinterleaving）引入时间因素，多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度。2.资源重复（resourcereplication）是指在并行性概念中引入空间因素，通过重复设置硬件资源来提高可靠性或性能。3.资源共享（resourcesharing）是指利用软件的方法让多个任务按一定的时间顺序（分时）轮流地使用同一套资源，以提高其利用率，这样相应地也可以提高整个系统的性能。如流水线如超标量处理机如多终端小型机5.1.3计算机系统结构中并行性的发展

标量

顺序

先行

I/E重叠

功能并行

多功能部件

流水线

隐式向量

显式向量

存储器-

寄存器-

存储器型

寄存器型

SIMD

MIMD

相联处理机

处理机阵列

多计算机

多处理机

多机系统多处理机：存储器共享，紧耦合多计算机：消息传递，松耦合5.2SIMD并行处理机5.2.1SIMD并行处理机的基本结构与特点按存储器的组成方式不同分为两类分布式存储器结构集中式共享存储器结构1.分布式存储器结构

LMN-1

LM0

主机

控制部件存储器

（程序与数据）

标量处理机

大容量存储器

阵列控制

部件

互连网络

PE0

LM1

PE1

PEN-1

标量指令

向量指令

指令

广播总线

网

络

控

制

数

据

总

线

I/O用户

···

2.集中式共享存储器结构SMK-1SM0主机控制部件存储器（程序与数据）标量处理机大容量存储器阵列控制部件互连网络PE0SM1PE1PEN-1标量指令向量指令指令广播总线网络控制数据总线I/O用户······3.SIMD并行处理机的主要特点(1)SIMD并行处理机利用的是资源重复，而不是时间重叠，利用并行性中的同时性，而不是并发性；(2)SIMD并行处理机是以某一类算法为背景的专用计算机；(3)SIMD并行处理机的研究必须与并行算法的研究密切结合，以使它的求解算法的适应性更强一些，应用面更广一些；(4)从处理单元上看，由于各处理单元都是相同的，因而可将SIMD并行处理机看成是一个同构型并行处理机。但从整体上看又是一个异构的多处理机系统（主机、处理单元阵列、标量处理机）5.2.2ILLIAC-IV的处理单元阵列结构是世界上最早采用SIMD结构的计算机，美国宝来公司和伊利诺依大学1965年开始研制，1972年正式生产。采用分布式存储器结构。阵列共由64个处理部件组成，排列成平面8×8阵列结构，每一个PU都与其四个邻近的PU相连，即按上、下、左、右方向可以与其它PU通信。PU在连接上采用了纵向连环，横向闭合螺线，又称闭合螺线阵列。在n×n个PU组成的阵列中，这种连接可以使任意两个PU间的最短距离不超过（n-1）步。5.2.2ILLIAC-IV的处理单元阵列结构

PU0

PU7

···

··

·

···

·

·

·

i-8

i-1

i

i+1

i+8

PU1PU8PU9PU15PU56PU57PU63·····

·

5.2.3阵列处理机的并行算法1.矩阵加并行算法设A和B是n×n阶矩阵，A、B的和矩阵为C，它也是n×n阶矩阵。矩阵加的算法为：A+B=C=(cij)n×ncij=aij+bij

αA（0，0）

α+1B（0，0）

α+2C（0，0）

A（0，1）

B（0，1）

C（0，1）

A（7，7）

B（7，7）

C（7，7）

LM0LM1LM63

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

···

1.矩阵加并行算法P≥n2TP=t加P＜n2

αA（0，0）

α+1B（0，0）

α+2C（0，0）

A（0，1）

B（0，1）

C（0，1）

A（7，7）

B（7，7）

C（7，7）

LM0LM1LM63

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

···

2.矩阵乘并行算法设A和B是n×n阶矩阵，A、B的乘积矩阵为C，它也是n×n阶矩阵。矩阵乘的传统串行算法为：A×B=C=(cij)n×n串行运行时间为T1=n3×(t乘+t加)设处理单元数P=m2，互连成m×m的二维双向链路环网结构，下面分两种情况讨论矩阵乘所需的总计算时间。(1)若处理单元的个数P＜n2

设n为m的整数倍。将A、B与C以适当方式分为P块Aij、Bij和Cij(0≤i,j≤m-1)，每块为(n/m×n/m)子矩阵，将这些块映像到m×m个逻辑处理阵列机上，每个处理机记为Pij，Pij存储Aij，Bij，并计算Cij。例图5.7。c[i,j]=0;for(i=0;i<n;i++)for(j=0;j<n;j++)for(k=0;k<n;k++)c[i,j]=c[i,j]+a[i,k]*b[k,j];(1)若处理单元的个数P＜n2

A(0，0)

A(0，1)

A(0，7)

A(0，56)

A(0，57)

A(0，63)

A(1，0)

A(1，1)

A(1，7)

A(1，56)

A(1，57)

A(1，63)

A(7，0)

A(7，1)

A(7，7)

A(7，56)

A(7，57)

A(7，63)

A(56，0)A(56，1)

A(56，7)

A(56，56)A(56，57)A(56，63)

A(57，0)A(57，1)A(57，7)

A(57，56)A(57，57)A(57，63)

A(63，0)A(63，1)A(63，7)

A(63，56)A(63，57)A(63，63)

64×64

A00LM0A07LM7

A70LM56

A77LM63

···

···

···

···

···

···

···

···

···

···

···

···

···

···

···

···

···

···

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

(1)若处理单元的个数P＜n2计算Cij时，需要所有子矩阵块Aik、Bkj(0≤k≤m-1)，因此A的块在处理机阵列每行作多对多广播，而B的块在处理机阵列每列作多对多广播。当Pij接收完Ai0，Ai1，…，Ai(m-1)；B0j，B1j，…，B(m-1)j后，执行子矩阵乘法和加法运算。计算时间用Pij计算Cij时，需对(n/m×n/m)阶子矩阵中的每个元素cij进行n次乘法和n次加法(cij=Σaikbkj)，故Pij的运行时间为：n×n/m×n/m×(t乘+t加)=n3/m2×(t乘+t加)=n3/P×(t乘+t加)通信时间ts：发送消息的启动时间，tw：传送每个浮点数时的通信时间，由于需要在m台处理机组成的组中作二次多对多广播，每次包含处理机阵列上所有行或列的m次并发广播，发送消息的个数由n2/P个元素的子矩阵组成，所以整个通信时间为：2(mts+mn2/P×tw)=2(mts+n2/m×tw)整个并行运行时间为：TP=n3/m2×(t乘+t加)+2(mts+n2/m×tw)c[i,j]=0;for(i=0;i<n/m;i++)for(j=0;j<n/m;j++)for(k=0;k<n;k++)c[i,j]=c[i,j]+a[i,k]*b[k,j];矩阵乘法C程序传统串行处理时：cij=0;for(i=0;i<n;i++)for(j=0;j<n;j++)for(k=0;k<n;k++)cij=cij+aik*bkj;n*n*n次加法和乘法分块并行后：cij=0;for(i=0;i<n/m;i++)for(j=0;j<n/m;j++)for(k=0;k<n;k++)cij=cij+aik*bkj;n*(n/m)*(n/m)次乘法和加法(2)若处理单元的个数P≥n2是前一种情况在m=n下的一个特例，将m=n代入前式得：①计算时间n(t乘+t加)②通信时间2(nts+ntw)=2n(ts+tw)③整个并行运行时间为：TP=n(t乘+t加)+2n(ts+tw)3.累加和并行算法为了加快并行计算，常采用递归折叠方法。一般而言，在P个处理单元上实现P个元素累加，需要折叠次，并行相加

次并行处理所需的总的时间为：nt加+xt传

第3步

A0+A1+A2+A3+A4+A5+A6+A7

第2步A0+A1+A2+A3A4+A5+A6+A7

第1步A0+A1

A2+A3

A4+A5A6+A7

PE值0A01A1

2A23A3

4A45A5

6A67A7

注意与向量方式的区别上次课内容回顾向量流水处理机性能参数R∞、n1/2、nv并行性的基本概念并行性与并行处理同时性与并发性并行性颗粒度并行性技术的实现途径时间重叠、资源重复、资源共享SIMD并行处理机分布式存储器结构集中式共享存储器结构处理单元阵列（PE）、标量处理机、阵列控制部件、主机、互连网络上次课内容回顾并行性的基本概念并行性与并行处理同时性与并发性并行性颗粒度并行性技术的实现途径时间重叠资源重复资源共享SIMD并行处理机分布式存储器结构集中式共享存储器结构组成：处理单元阵列（PE）、标量处理机、阵列控制部件、主机、互连网络ILLACⅣ、闭合螺线阵列阵列处理机并行算法矩阵加、矩阵乘、累加和5.3SIMD计算机的互连网络5.3.1互连网络的设计准则1.通信工作方式同步和异步两种同步方式由统一的时钟加以同步；异步方式则不用统一的时钟加以同步，各处理单元根据需要相互建立动态连接。SIMD并行机一般都采用同步方式2.控制策略集中和分散两种集中式控制由统一控制器对各互连开关的状态加以控制，而分散式控制则由各个互连开关自身进行管理。SIMD并行机一般都采用集中控制。5.3.1互连网络的设计准则3.交换方式线路交换和分组交换两种。线路交换是在整个交换过程中，在源和目标结点之间建立固定的物理通路，适用于成批数据传送。分组交换则把要传送的一个信息分成多个分组，分别送入互连网络。这些分组可通过不同的路由到达目标结点。因此，较适合于短数据报文的传送。SIMD并行机因为处理单元间的连接比较紧密，一般采用线路交换。MIMD多机系统则往往采用分组交换方式。4.网络拓扑指互连网络中各个结点间的连接关系，通常用图来描述。静态和动态两种。5.3.2互连函数的表示互连函数：描述各处理单元之间或处理单元与共享主存各模块之间传递数据时，互连网络的出端号和入端号的一一对应关系。如果定义互连网络的所有入端号分别为0、1、...、j、…、N-1，那么互连函数f(j)则表示的是入端号j连至出端号f(j)的函数对应关系。互连函数的分析工具一般有二种：(1)入、出端连接图。一般只在结点数比较少的情况下使用。(2)函数关系式。把所有入端j和出端f(j)都使用二进制编码，从二者的二进制编码上找出其对应的函数规律，并用函数关系式来表示。5.3.3单级互连网络1.立方体单级网络（Cube）二元三维处理单元编号（z,y,x）1.立方体单级网络（Cube）Cubei（Pn-1…Pi…P1P0）=Pn-1…Pi…P1P0n维立方体单级网络，实现任意两个PE之间的连接，最多需使用n次不同的互连函数，即：n维立方体单级网络的最大距离为n。000

001

100

101

110

111

Cube0=zyx010011000

001

110

111

100

101

Cube1=zyx010011000

001

110

111

100

101

Cube2=zyx0100112.PM2I单级网络是加减2i的简称，Plus-Minus2i。PM2+i（j）=（j+2i）modNPM2-i（j）=（j-2i）modN式中，0≤j≤N-1，0≤i≤n-1，n=log2N，N为处理器的个数。因此，它共有2n个互连函数例如，对于N=8，各互连循环为：PM2+0：（0→1→2→3→4→5→6→7）PM2-0：（7→6→5→4→3→2→1→0）PM2+1：（0→2→4→6）（1→3→5→7）PM2-1：（6→4→2→0）（7→5→3→1）PM2±2：（0→4）（1→5）（2→6）（3→7）8个处理单元的PM2I互连网络的部分连接图

0

1

2

3

4

5

6

7

PM2+0

0

1

2

3

4

5

6

7

PM2+1

0

1

2

3

4

5

6

7

PM2±2

2.PM2I单级网络可以证明：PM2+（n-1）=PM2-（n-1），所以实际上，PM2I网络只有2n-1种不同的互连函数。如何证明？ILLIAC-Ⅳ中的64个处理单元间的互连，实际上就是只采用了PM2I互连网络中的PM2±0和PM2±3这四个互连函数。验证PM2I单级网络的最大距离为，使用不同的PM2I函数。

0

1

2

3

4

5

6

7

PM2+0

0

1

2

3

4

5

6

7

PM2±2

分j+2n-1≤2n和j+2n-1>2n两种情况证明1）若j+2n-1≤2n则:PM2+（n-1)(j)=(j+2n-1)mod2n=(j+2n-1)PM2-（n-1)(j)=(j-2n-1)mod2n=2n+(j-2n-1)=PM2+（n-1)(j)同理2）也成立。3.混洗交换互连网络（Shuffle-Exchange）由全混洗和交换两种互连函数组成。(1)全混洗Shuffle（Pn-1Pn-2···P1P0）=Pn-2···P1P0Pn-1

0

01

1

2

2

3

3

4

45

5

6

6

7

7

循环左移1位洗扑克牌？3.混洗交换互连网络（Shuffle-Exchange）(2)交换由于单一的全混洗互连网络不能实现二进制编号为全“0”和全“1”的处理器与其它任何处理器的连接，所以又增加了Cube0交换互连函数。称为混洗交换单级互连网络，Shuffle+Cube0

。

0

1

2

3

4

5

67最远的两个入、出端的连接，需要经过n次交换和n-1次混洗，所以混洗交换网络的最大距离为2n-1。上次课内容回顾互连网络的设计准则通信工作方式同步、异步控制策略集中、分散交换方式线路交换、分组交换网络拓扑静态、动态单级互连网络CubeiPM2IShuffle-ExchangeButterfly4.蝶形互连网络（Butterfly）蝶形互连网络的互连函数为：Butterfly（bn-1bn-2……b1b0）=b0bn-2……b1bn-1

00

1

1

2

2

3

3

4

4

5

5

6

6

7

7

蝶形否？5.4网络特性与寻径功能5.4.1结点度和网络直径与结点相连接的边（链路或通道）数称为结点度(nodedegree)。在单向通道的情况下，进入结点的通道数叫做入度(indegree)，而从结点出来的通道数则称为出度(outdegree)。结点度就是入度与出度之和。反映结点所需端口数。网络直径(networkdiameter)：网络中任意两个结点之间最短路径的最大值。路径长度用遍历的链路数来度量。这是说明网络通信性能的一个指标。网络对称性(networksymmetry)：如果从网络任意结点看上去拓扑结构都是相同的，则称该网络是对称的，否则网络是非对称的。网络的对称性可提高可扩展性和寻径效率。5.4.2聚集带宽和等分带宽聚集带宽(aggregatebandwidth)从一半节点到另一半结点每秒传输的最大位数或字节数。例如：HPS是对称式网络，包含512个节点，每个端口带宽为40MB/s，则HPS的聚集带宽为：512/2×40MB/s=10GB/s。等分平面：有n个结点的网络的等分平面是一组连线，它的移动将把网络分为两个n/2个结点的网络。最小的等分平面是指具有最小连线数的等分平面。等分带宽(bisectionbandwidth)：每秒钟内在最小等分平面上通过所有连线的最大信息位数或字节数。设b为穿越最小等分平面的链路数，w为每条链路的连线数，r为每条连线的数据传输率（单位为：位/秒），那么该网络的等分带宽为B=bwr位/秒。5.4.3数据寻径功能数据寻径网络用来进行PE间数据交换。可以是静态的，如TMC/CM-2所用的超立方体寻径网络；也可以是动态的，如IBMGF11所用的多级网络（通过消息传递来实现）。硬件寻径器可用来在多个计算机结点之间寻径传送消息。常见的PE之间的数据寻径功能包括：个人通信（一对一或一对多）；广播、散射（一对多）；汇合/聚集、归约（多对一）；置换、循环移位、扫描、洗牌、全交换（多对多）等。5.4.3数据寻径功能一对一（点对点、point-to-point）通信，仅一个发送者和一个接收者。一对多通信包括广播(broadcast)和散射(scatter)两种，广播是指一个进程（或称根进程）向所有进程（包括自己）发送相同消息。散射是通用化的广播操作，因为根进程对不同进程发送不同消息。多对一通信包括汇合/聚集(gather)和归约(reduction)两种，汇合操作是指根进程从每个进程接收一个不同消息。归约是指某个根进程接收来自每个进程（包括自己）的局部值，并将它们在根进程中归约求和形成一个最后值。多对多通信中最简单的形式是置换(permutation)，其中每个进程只向一个进程发送并只接收一个进程发来的消息。如循环移位(circularshift)、扫描(scan)、全交换(totalexchange)等。5.4.3数据寻径功能P11P23P35P11P23P35，1P11P23P35P11，1P23，1P35，1（a）点对点：P1发1给P3（b）广播：P1发1给全体5.4.3数据寻径功能P11，3，5P2

P3

P11，3，5P23P35P11P23P35P11，3，5P23P35（c）散射：P1向每个结点发送一个值（d）汇合：P1从每个结点接收一个值5.4.3数据寻径功能P11P23P35P11，9P23P35P11P23P35P11，5P23，1P35，3（e）归约：P1得到和1+3+5=9（f）循环移位：每个结点向下一结点发送一个值，并接收来自上一结点的一个值5.4.3数据寻径功能P11P23P35P11，1P23，4P35，9P11，2，3P24，5，6P37，8，9P11，4，7P22，5，8P33，6，9（g）扫描：P1得到1，P2得到和1+3=4，P3得到和1+3+5=9（h）全交换：每个结点向其他结点发送一个不同消息5.5静态连接网络互连网络的网络拓扑(networkingtopology)可以采用静态或动态的结构。这两类网络已在SIMD计算机中实现了PE间的数据寻径要求。静态网络(staticnetwork)由点-点直接相连而成，这种连接方式在程序执行过程中不会改变。常用来实现集中式系统的子系统之间或分布式系统的多个计算结点之间的固定连接。比较适合于构造通信模式可预测或可用静态连接实现的计算机。动态网络(dynamicnetwork)是用开关通道实现的，它可动态地改变结构，使之与用户程序中的通信要求匹配。包括总线、交叉开关和多级网络等，它们常用于共享存储器型多处理机中。5.5.1线性阵列是一种一维网络，N个结点用N-1条链路连成一行。内部结点度为2，端结点度为1。网络直径为N-1，N较大时，网络直径就比较大，等分带宽为1。不具有对称性，当N很大时，通信效率很低。5.5.2环和带弦环用一条附加链路将线性阵列的两个端结点连接在一起，就构成了环形网络，或简称环(ring)。环可以分为单向环和双向环两种。若两个环在同一处出现故障，则这种双向环结构就变成了线性阵列。单向环和双向环结构的结点度均为2，并且它们都是对称的。单向环的网络直径为N-1，双向环的网络直径为[N/2]。5.5.2环和带弦环分别增加一条和两条附加链路就可以得到结点度分别为3和4的带弦环(chordalring)。增加的链路愈多，则结点度愈高，网络直径愈小。5.5.3循环移数网络和全连接循环移数(barrelshifter)网络：将环上每个结点到与其距离为2整数幂的结点之间增加一条附加链而构成的。即如果|j-i|=2r，r=0，1，2，…，n-1，网络规模N=2n，则结点i与结点j连接。这种循环移数网络的结点度为2n-1，网络直径为n/2。全连接：任意两个结点间都有固定的线路连接。是对称的网络，当网络规模为N时，结点度为N-1，网络直径为1，链路数为N(N-1)/2。5.5.4树形和星形一般来说，一棵h层完全平衡二叉树应有N=2h-1个结点。最大结点度为3，网络直径为2(h-1)。星形(star)是一种2层树，若结点的个数为N，则结点度为N-1，网络直径为2。5.5.5胖树形5.5.6网格形和环网形5.5.7超立方体5.5.8带环立方体5.5.9k元n-立方体网络4元3-立方体静态连接网络的特性网络特性结点度网络直径链路数等分带宽对称性网络规模和说明线性阵列2N-1N-11非N个结点环形2[N/2]N2是N个结点全连接N-11N(N-1)/2(N/2)2是N个结点二叉树32(h-1)N-11非树高h=[lbN]星形N-12N-1[N/2]非N个结点2D网格42(r-1)2N-2rr非N=r2Illiac网4r-12N2r非等效N=r2带弦环2D环网42[r/2]2N2r是N=r2超立方体nnnN/2N/2是N结点，log2N维3-CCC32k-1+[k/2]3N/2N/(2k)是k×2k结点环长k≥3K元n-立方体2nn[k/2]nN2kn-1是N=kn个结点n维环网n[r/2]n[r/2]nN2rn-1是N=rn个结点上次课内容回顾互连网络的设计准则通信工作方式同步、异步控制策略集中、分散交换方式线路交换、分组交换网络拓扑静态、动态单级互连网络CubeiPM2IShuffle-ExchangeButterfly网络特性结点度与网络直径聚集带宽与等分带宽数据寻径功能上次课内容回顾静态互连网络线性阵列环和带弦环循环移数网和全连接树型和星型胖树型网格型和环网型超立方体带环超立方体K元n-立方体例5.2设计一种采用加、乘和数据寻径操作的算法，分别在下面两种计算机系统上用最短的时间来计算表达式S=A1×B1+A2×B2+…+A32×B32。假设加法和乘法分别需要2个和4个单位时间，从存储器取指令、取数据、译码的时间忽略不计，所有的指令和数据已装入有关的PE。试确定下列每种情况的最小计算时间。(1)一台串行计算机，处理机中有一个加法器和乘法器，同一时刻只有其中一个可以使用。不需要数据寻径操作。(2)一台有8个PE(PE0，PE1，…，PE7)的SIMD计算机，8个PE连成双向环结构。每个PE用1个单位时间可以把数据直接送给它的相邻PE。操作数Ai和Bi最初存放在PEi(mod8)中，其中i=1，2，…，32。每个PE可在不同时刻执行加法或乘法。(3)若将(2)中8个PE之间的连接改为单向环结构，结果如何？例5.2解：(1)采用单处理机系统串行处理所需的时间为：t=32×4+31×2=190(单位时间)(2)根据题意，画出8个PE的连接图和操作数的初始存放位置如下图所示。

PE5PE4

A8B8/A16B16/A24B24/A32B32

A1B1/A9B9/A17B17/A25B25

PE0PE1

PE7PE2

PE6PE3

例5.2数据寻径操作的算法如下：①每个PE同时执行乘法4次，加法3次；②PE0→PE7、PE1→PE2、PE6→PE5、PE3→PE4同时传递和1次，再加法1次；③PE7→PE6→PE5、PE2→PE3→PE4同时传递和2次，再加法1次；④PE4→PE5传递和1次，最后加法1次。因此，采用8个PE并行处理所需的最小时间为：t=4×4+3×2+1+2+2+2+1+2=32(单位时间)PE5PE4

PE0PE1

PE7PE2

PE6PE3

例5.2(3)若将(2)中8个PE之间的连接由双向环结构改为单向环结构，8个PE的连接图和操作数的初始存放位置如下图所示。

A8B8/A16B16/A24B24/A32B32

A1B1/A9B9/A17B17/A25B25

PE0PE1

PE7PE2

PE6PE3

PE5PE4

例5.2数据寻径操作的算法如下：①每个PE同时执行乘法4次，加法3次；②PE0→PE1、PE2→PE3、PE4→PE5、PE6→PE7同时传递和1次，再加法1次；③PE1→PE2→PE3、PE5→PE6→PE7同时传递和2次，再加法1次；④PE3→PE4→PE5→PE6→PE7传递和4次，最后加法1次。因此，采用8个PE并行处理所需的最小时间为：t=4×4+3×2+1+2+2+2+4+2=35(单位时间)例5.2推广到一般情形，假设处理器的个数N=2m，一次乘法需t1时间，一次加法需t2时间，相邻PE间传送数据需t3时间，则计算所需时间为：(1)若各处理器之间采用双向环连接：[n/N]t1+([n/N]-1)t2+mt2+2m-1t3(２)若各处理器之间采用单向环连接：[n/N]t1+([n/N]-1)t2+mt2+（2m-1）t3每个ＰＥ同时执行加、乘时间折叠相加时间数据传送时间5.6动态互连网络静态互连网络只适用于通信模式可预测的情况。为了达到多用或通用的目的，需要采用动态互连网络，能根据程序要求实现所有的通信互连模式。常见动态互连网络方式总线互连方式交叉开关互连方式多级网络互连方式蝶式网络组合网络5.6.1总线互连方式是多机系统中实现互连的最简单的一种结构形式。多个处理机、存储器和I/O部件通过各自的接口部件（或通过公共的接口部件）与一条公用系统总线相连。信息以分时或多路转换方式在系统的主设备（如处理器）及从设备（如存储器模块）之间传送。目前已建立了许多标准总线，例如PCI、VME、Multibus、Sbus、Microchannel、IEEEFuturebus等，大多数标准总线在构造单处理机系统时价格很低。而多处理机总线和层次总线，常用来构筑SMP（SymmetricMultiprocessor）、NUMA（Non-UniformMemoryAccess）和DSM（DistributedSharedMemoryMultiprocessor）机器。1.多处理机总线

IF

CC

缓冲器

IF

IFMC

存储器

LMCPUIOC

高速缓存

IF

本地总线

系统总线(在底板上或中夹板上)

存储器总线

IOPIF

局部总线(I/O总线)

局部总线

缓冲器

IF

CPU板

存储器板

I/O板

通信板

磁盘或磁带

部件

本地外围设备

打印机或

绘图仪

网络

(以太网等)

(SCSI总线)

…

2.层次总线

CCCCCC

存储器

存储器

存储器

机群间总线

P

P

P

PP

P

C

C

C

CC

C

…

…

…

…

…

机群高速缓存

高速缓存

机群总线

处理器

机群1

机群2机群N

…

CC-NUMA的层次总线3.总线互连的缺点因为总线由多个处理机分时共享，因此即使当总线带宽很高，每个处理器的带宽也只是总带宽的一部分。另外由于总线缺乏冗余机制易于出错，且总线的可扩展性有限。总线一般限制在很小的机架内，当层次总线扩展到几个机架时，时钟扭斜和全局定时就成了非常严重的问题。后面介绍的交叉开关和多级互连网络可在一定程度上克服这些缺点。5.6.2交叉开关互连方式一个交叉开关(crossbar)是一个单级交换网络，可以实现所有处理机结点之间、处理机结点与存储器模块之间或处理机结点与I/O模块之间的无阻塞连接，可为每个端口提供更高的带宽。与总线互连中采用分时使用机制不同，交叉开关采用的是空间分配机制。在并行处理中，交叉开关一般有两种使用方式：一种是用于对称式多处理机或多计算机机群中的处理器间的通信；另一种是用于SMP服务器或向量超级计算机中处理器和存储器之间的存取。5.6.2交叉开关互连方式交叉开关互连由一组二维阵列的开关组成。它将横向的处理机P及纵向的存储器模块M连接起来。总线条数=处理器数p+存储器模块数m。只要m≥p就必然可以使每个处理机都能有一套总线与某一存储器模块相连，从而可以大大加宽带宽。

···

Pp

P2

P1

·

·

·

M1

M2

Mm

交叉开关5.6.2交叉开关互连方式每个交叉点都是一套开关，除了有多路转换逻辑外，为了处理多个处理机同时访问某一存储器模块所发生的冲突，纵横交叉互连方式需要有相应的仲裁部件。若P个处理机还要通过交叉开关与i个I/O模块相连，这时阵列中的总线条数等于p+m+i。只有当m≥p+i时，才能实现无阻塞连接。为了降低复杂性，通常可将多个规模较小的交叉开关串并连接，构成多级交叉开关网络以取代单级较大规模具有相同互连能力的交叉开关。例如，由16×16交叉开关构成的单级网络将有256个交叉点，若用8个4×4交叉开关模块构成的二级16×16的交叉开关网络，如图所示，则仅需128个交叉点，比起单级交叉开关来可节省一半设备量。采用多级交叉开关网络虽然降低了硬件复杂性，但是时延随着网络级数的增加而增大。8个4×4交叉开关构成二级16×16交叉开关网络4×4交叉开关5.6.3多级互连网络多级互连网络(multistageinterconnectionnetwork，简称MIN)是指将多套单级互连网络通过交换开关或交叉开关串连扩展而成的网络。与单级网络相比，多级网络可以通过改变开关的控制方式，灵活地实现各种连接，满足系统应用的需要。正是因为多级网络互连的灵活性，在SIMD和MIMD计算机设计中已经使用了MIN。多级互连网络在每级上使用多个开关模块，相邻级间的开关使用了固定的级间连接，常见的多级互连网络有多级立方体互连网络、多级混洗交换网络(Omega网络)、多级PM2I网络、BENES二进制转换网络和多级CLOS网络等。多级互连网络的基本结构输入端开关开关输出端级间固定连接1.多级互连网络的3个参量1）交换开关是具有两个入端和两个出端的交换单元，用作各种多级互连的基本构件。交换开关的4种开关状态或连接方式如下图所示。

①直连i入i出

j入j出

②交换

i入j出j入i出④下播

i入j出j入i出③上播

i入i出j入j出1.多级互连网络的3个参量把只具有直连和交换两种功能的交换开关称为二功能交换单元。把具有直连、交换、上播和下播等全部4种功能的交换开关称为四功能交换单元。2）拓扑结构:指各级之间出端和入端互连模式。3）控制方式①级控制：同一级的所有开关只用一个控制信号控制，同时只能处于同一种状态；②部分级控制：第i级的所有开关分别用i+1个信号控制，0≤i≤n-1，n为级数；③单元控制：每一个开关都有自己单独的控制信号控制，可各自处于不同的状态。2.常见的多级互连网络按照多级互连网络对输入与输出连接程度的不同，可将它们分为阻塞网络、非阻塞网络和可重排非阻塞网络。阻塞网络：同时实现两对或多对入端与出端之间的连接时，可能会出现开关状态设置的冲突。如多级立方体网络、多级混洗交换网络（Omega网络）、多级PM2I网络、基准网络等。非阻塞网络（全排列网络）：不具有上述性质的互连网络。如多级CLOS网络。可重排非阻塞网络：为一对空闲的输入输出结点建立一条通路时，可能要影响到当前正在使用的配置。但通过重新设置通路，仍可以同时实现原配置及新的一对结点的通路。如多级BENES网络。上次课内容回顾静态互连网络线性阵列环和带弦环循环移数网和全连接树型和星型胖树型网格型和环网型超立方体带环超立方体K元n-立方体动态互连网络总线方式交叉开关互连方式多级互连网络多级互连网络的三个量交叉开关直连、交叉、上播、下播两功能交换单元、四功能交换单元拓扑结构控制方式级控制、部分级控制、单元控制多级立方体网络1）多级立方体网络由n级组成，从输入到输出端依次为K0、K1、……、Kn-1级。n+1个级间连接依次为C0、C1、……、Cn，其中C0为恒等置换、C1为子蝶式置换、C2为蝶式置换、C3为逆均匀洗牌置换，每级2n-1个二功能交换开关。教材有误

I

J

K

L

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

入端

出端

0

2

1

3

4

6

5

7

0

1

2

3

4

5

6

7

0

2

1

3

4

6

5

7

0

4

1

5

2

6

3

7

0

1

2

3

4

5

6

7

0

4

1

5

2

6

3

7

K0级K1级K2级

A

B

C

D

E

F

G

H

C0C1C2C31）多级立方体网络常见的有STARAN网络和间接二进制n方体网络。相同点：当第i级（0≤i≤n-1）交换单元处于交换状态时，实现的是Cubei互连函数，且都采用二功能交换单元；不同点：交换开关的控制方式不同，STARAN网络采用级控制（称交换网络）或部分级控制（称移数网络）；而间接二进制n方体网络采用单元控制。STARAN网络用作交换网络时，采用级控制。级控制信号为0时，交换开关都完成直连功能；级控制信号为1时，交换开关都完成Cubei交换函数的功能。STARAN交换网络(N=8)级控制信号的组合及所实现的功能级控制信号（K2K1K0）000001010011100101110111入端号012345670123456710325476230167453210765445670123547610236745230176543210执行的交换函数功能恒等四组二元四组二元+二组四元二组四元四组二元+一组八元四组二元+二组四元+一组八元四组二元+一组八元一组八元iCube0Cube1Cube0+Cube1Cube2Cube0+Cube2Cube1+Cube2Cube0+Cube1+Cube2K2K1K0=011时的各级交换开关状态

E

F

G

H

0

4

1

5

2

6

3

7

0

4

1

5

2

6

3

7

0

2

1

3

4

6

5

7

0

2

1

3

4

6

5

7

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

I

J

K

L

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

入

端

出

端

0级1级2级

A

B

C

D

K0=1K1=1K2=0

Cube0+Cube1K2K1K0=101时，实现4组2元+2组4元+1组8元交换入端排列：01234567分成4组：|01|23|45|67|每组2元交换：|10|32|54|76|分成2组：|1032|5476|每组4元交换：|2301|6745|分成1组：|23016745|每组8元交换：54761032Cube0+Cube2STARAN网络用作移数网络采用部分级控制，第i级的2n-1个二功能交换开关分成i+1组，每组用一个控制信号控制。对于n级STARAN移数网络来说，从第0级到第n-1级所需的控制信号个数分别为1，2，3，…，n个。当处理单元个数N=8时，共需要6个控制信号，每一级控制信号的分组和控制结果如表5.3所示。STARAN移数网络的置换函数可以表示为：α(x)=(x+2m)mod2pp和m为整数，且0≤m＜p≤n。三级移数网络能实现的入出端连接及移数函数功能部分级控制信号2级K，LJI0010111110000000000001级F，HE，G011100011100000级A，B，C，D1001010入端号0123456712345670234567014567012312305674230167451032547601234567相当于实现的移数功能移1mod8移2mod8移4mod8移1mod4移2mod4移1mod2不移全等三级移数网举例（表5.3功能部分第一列）

I

J

K

L

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

入端

出端

0

2

1

3

4

6

5

7

0

1

2

3

4

5

6

7

0

2

1

3

4

6

5

7

0

4

1

5

2

6

3

7

0

1

2

3

4

5

6

7

0

4

1

5

2

6

3

7

0级1级2级

A

B

C

D

E

F

G

H

α(x)=(x+20)mod23三级移数网举例（表5.3功能部分第五列）

I

J

K

L

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

入端

出端

0

2

1

3

4

6

5

7

0

1

2

3

4

5

6

7

0

2

1

3

4

6

5

7

0

4

1

5

2

6

3

7

0

1

2

3

4

5

6

7

0

4

1

5

2

6

3

7

0级1级2级

A

B

C

D

E

F

G

H

α(x)=(x+22)mod22分2组，组内循环移2位2）多级混洗交换网络又称Omega网络，由n级相同的网络组成，每一级都包含一个全混洗拓扑和随后一列2n-1个四功能交换单元，采用单元控制方式。一个2n输入的Omega网络需要n级2×2开关，每级都包含2n-1个采用单元控制方式的四功能交换单元。如果Omega网络采用级控制，并且四功能单元只完成直连和交换两种功能，则它就成为了STARAN网络的逆网络，即它们的输入端和输出端的数据流向相反。N=8的多级混洗交换网络

0

2

1

3

4

6

5

7

0

2

1

3

4

6

5

7

0

4

1

5

2

6

3

7

0

1

2

3

4

5

6

7

I

J

K

L

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

入

端

出

端

0

4

1

5

2

6

3

7

0

1

2

3

4

5

6

7

2级1级

0级

A

B

C

D

E

F

G

H

C3C2C1C0每级间都是全混洗级编号与STARAN相反N=8的多级立方体网络和Omega网络的关系

I

J

K

L

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

入

端

出

端

0

2

1

3

4

6

5

7

0

1

2

3

4

5

6

7

0

2

1

3

4

6

5

7

0

4

1

5

2

6

3

7

0

1

2

3

4

5

6

7

0

4

1

5

2

6

3

7

0级1级2级

A

B

C

D

E

G

F

H

多级立方体网络0

2

1

3

4

6

5

7

0

2

1

3

4

6

5

7

0

4

1

5

2

6

3

7

0

1

2

3

4

5

6

7

I

J

K

L

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

入

端

出

端

0

4

1

5

2

6

3

7

0

1

2

3

4

5

6

7

2级1级

0级

A

B

C

D

E

F

G

H

Omega网络互为逆网络上次课内容回顾多级立方体网络STARAN网交换网络：级控制移数网络：部分级控制间接二进制n方体网络单元控制相同点：第i级处于交换像状态时，实现Cubei互连函数；都采用两功能交换单元多级混洗交换网又称Omega网络，采用四功能交换单元、单元控制如采用级控制、二功能交换单元，则是STARAN的逆网络动态互连网络总线方式交叉开关互连方式多级互连网络多级互连网络的三个量交叉开关直连、交叉、上播、下播两功能交换单元、四功能交换单元拓扑结构控制方式级控制、部分级控制、单元控制3）多级PM2I网络多级PM2I网络包含n级单元间连接，每一级都是把前后两列各N=2n个单元按PM2I拓扑互连起来。8个处理单元的多级PM2I网络如图5.32所示。就第i级而言(0≤i≤n-1，这里为0≤i≤2)，每个输入端j(0≤j≤N-1)都有3根线分别连接到输出端(j-2i)modN、j和(j+2i)modN。第0级完成的是PM2±0，第1级完成的是PM2±1，第2级完成的是PM2±2。单级PM2I网络的最大距离为┌n/2┐，但组成多级PM2I网络时用了多级。在这种网络中，从一个处理单元到另一个处理单元的路由有多条路径可供选择。如为实现6号处理单元将信息传送4号处理单元，可以经6→6→4→4，或6→2→4→4等多条路径完成。显然在多级网络中提供的这种冗余通路，有利于提高系统的可靠性。N=8的多级PM2I网络

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

PM2+2

PM2-2

PM2+1PM2-1

PM2+0PM2-0

入端

出端

a

b

c

d

a

b

c

d

e

f

g

h

e

f

g

h

i

j

j

i

k

l

k

l

m

m

n

n

2级1级0级

多级PM2I网络中各级各单元的单元控制原理

上播（上控）

下播

直连

上播

下播（下控）

直连（平控）

D

H

U

5种多级互连网络的比较多级互连网络的3个参量多级互连网络的类型交换开关控制方式拓扑结构多级立方体网络STARAN交换网络二功能交换单元级控制单级立方体网络STARAN移数网络二功能交换单元部分级控制单级立方体网络间接二进制n方体网络二功能交换单元单元控制单级立方体网络多级混洗交换网络（Omega网络）四功能交换单元单元控制单级混洗交换网络强化数据变换网络（ADM网络）多功能交换单元单元控制单级PM2I网络4）基准网络从结构上看，它与二进制立方体网络的逆网络非常相似，只是在第1级的级间互连有所不同。基准网络的级间互连从输入到输出依次为恒等、逆均匀混洗、子逆均匀混洗和恒等置换，所有的开关均为二功能交换单元，采用单元控制方式。基准网络常用于在多级互连网络的研究过程中，将基准网络作为中间介质，模拟一种网络的拓扑和功能等。N=8的基准网络

I

J

K

L

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

入

端

出