第1章 计算机系统设计基础 第2章 数据表示与指令系统性能分析 第3章 通道处理机 第4章 流水技术和向量处理 第5章 阵列计算机

Presentation on theme: "第1章 计算机系统设计基础 第2章 数据表示与指令系统性能分析 第3章 通道处理机 第4章 流水技术和向量处理 第5章 阵列计算机"— Presentation transcript:

1 第1章 计算机系统设计基础 第2章 数据表示与指令系统性能分析 第3章 通道处理机 第4章 流水技术和向量处理 第5章 阵列计算机
第1章 计算机系统设计基础 第2章 数据表示与指令系统性能分析 第3章 通道处理机 第4章 流水技术和向量处理 第5章 阵列计算机 第6章 多处理机系统 第7章 其它计算机结构 2019/1/17

2 第五章 阵列计算机 5.1 并行处理技术的基本概念 5.2 SIMD并行处理机结构 5.3 SIMD并行计算机算法
Wuhan University 2019/1/17

3 本章学习要求 了解并行性的基本概念、比较阵列机与多机系统并行性的特点 掌握典型的两种阵列机结构 重点掌握阵列机中的互连网络
2019/1/17

4 5.1并行处理的基本概念 1.并行性 在数值计算，数据处理，知识处理或人工智能求解过程中，可能存在某些能同时进行运算或操作的部分。包括同时性和并发性 同时性（simultaneity）:指两个或多个事件在同一时刻发生在多个资源中。 并发性（concurrency）:指两个或多个事件在同一时间间隔内发生在多个资源中 在同一时刻或同一时间间隔内完成多个性质相同或不同的任务 2019/1/17

5 2.并行处理 是一种相对串行处理的信息处理方式，侧重并发性。 (1)并行性粒度 粗粒度通常采用MIMD，细粒度则采用SIMD。
当TC较大时，通信量大，则G 较小，处理粒度较细。反之对于粗粒度的并行，通信量较小。 粗粒度通常采用MIMD，细粒度则采用SIMD。 2019/1/17

6 (2)并行性等级划分 MIMD方式 侧重软件 SIMD方式 侧重硬件 作业级（程序） 任务级（过程或程序段） 子任务级（例行程序，或子程序）
指令或语句 循环或递归循环 级5 级4 级3 级2 级1 通信需求与调度开销 并行程度 粗粒度 中粒度 细粒度 SIMD方式 侧重硬件 2019/1/17

7 ①指令级：并行性发生在指令内部微操作之间或指令之间。取决于程序的具体情况。可借助于优化编译器开发细粒度并行性。
②循环级：相当于迭代循环操作，典型循环包含的指令大约几百条，循环级并行性是并行机或向量计算机上运行的最优程序结构，并行处理主要由编译器在循环级中进行开发。 ③子任务级：属于中粒度。子程序是在单处理机或多处理机的多道程序设计这一级进行的。 ④任务级：这是与任务、过程、程序段、协同程序级相对应的中粒度或粗粒度规模。典型粒度包含的指令几千条，检测本级的并行性比细粒度级困难得多，需要更多地涉及过程间的相关性分析。 ⑤作业（程序）级：对于少量几台高性能处理机构成的超级计算机开发这种粗粒度并行性切实可行。 2019/1/17

8 3、并行处理技术及发展 提高计算机系统的并行性的技术途径：(单机系统)
时间重叠（Time Interleaving）：在并行性概念中引入时间因素。让多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度。 资源重复（Resource Replication）：并行性概念中引入空间因素。通过重复设置的硬件资源来提高系统可靠性或性能。例如，通过使用两台或多台完全相同的计算机完成同样的任务来提高可靠性。 2019/1/17

9 资源共享（Resource Sharing）：利用软件的方法让多个用户按一定时间顺序轮流地使用同一套资源，以提高其利用率，这样相应地提高整个系统的性能。例如多道程序分时系统.
2019/1/17

10 超级计算机---6种机器模型 SIMD阵列计算机 并行向量处理机(PVP) 对称多处理机(SMP) 大规模并行处理机(MPP)
工作站机群(COW) 分布式共享存储多处理机(DSM) 2019/1/17

11 5.2 SIMD并行计算机 并行处理机又叫SIMD计算机。它是单一控制部件控制下的多个处理单元构成的阵列，所以又称为阵列处理机。
多处理机是由多台独立的处理机组成的系统。 本节主要介绍并行计算机的硬件结构 2019/1/17

12 SIMD并行计算机（阵列处理机） 一、并行处理机的基本构成
并行处理机是通过重复设置大量相同的处理单元PE（Processing Element），将它们按一定的方式互连，在统一的控制部件CU（Control Unit）控制下，对各自分配来的不同数据并行地完成同一条指令所规定的操作。各PE之间的数据交换由ICN来实现。 从CU看，指令是串行执行的，从PE看，数据是并行处理的。按照佛林分类法，它属于SIMD计算机。 并行处理机的应用领域： 主要用于高速向量或矩阵运算中。 2019/1/17

13 并行处理机的操作模型可用五元组来表示： M＝(N，C，I，M，R),
其中： N 为PE个数。如IlliacIV有64个PE。 C 为由控制部件CU直接执行的指令集，包括标量指令和程序控制指令。 I 为所有PE并行执行的指令集，包括算术运算、逻辑运算、数据寻径、屏蔽以及其它由每个活动的PE对它的数据所执行的局部操作。 M 为屏蔽操作集，每种屏蔽将PE划分为允许操作和禁止操作两个子集。 R 是数据寻径集，说明互连网络中PE间通信所需要的各种设置模式。 2019/1/17

14 并行处理机根据存贮器采用的组成方式不同分成两种基本结构。 1.分布存贮的并行处理机
二、并行处理机分类 并行处理机根据存贮器采用的组成方式不同分成两种基本结构。 1.分布存贮的并行处理机 各个处理单元设有局部存贮器存放分布式数据，只能被本处理单元直接访问。此种局部存贮器称为处理单元存贮器（Processing Element Memory）PEM。 在控制部件CU内设有一个用来存放程序的主存贮器CUM。整个系统在CU统一控制下运行系统程序和用户程序。 2019/1/17

15 D 互连网络ICN 具有分布式存储器的并行处理机结构形式 PE0 PE1 PEM0 PEM1 PEMN-1 PEN-1 CU CUM …
I/O接口 D 管理处理机SC 控制 数据总线 控 制 … 控制总线 后端处理机 具有分布式存储器的并行处理机结构形式 2019/1/17

16 分布式存贮器构型是SIMD阵列机的主流。典型的分布式并行处理机是IILIAC-Ⅳ。
控制部件(CU)由一台标量处理机构成。控制存贮器(CUM)存放系统程序、用户程序和标量数据。整个系统是在CU控制下运行用户程序和部分系统程序的。 工作原理：所有指令都在控制部件中进行译码。译码后把只适合串行处理的标量或控制类指令留给控制部件自己执行，而把适合于并行处理的向量类指令“广播”给各个处理单元(PE)，控制让处于“活跃”的那些PE去并行地执行。各个处理单元可直接访问自已的局部存储器(PEM)，但它们之间的数据交换由互连网络(ICN)来实现。 分布式存贮器构型是SIMD阵列机的主流。典型的分布式并行处理机是IILIAC-Ⅳ。 2019/1/17

17 每个PE没有局部存储器，存储模块以集中形式为所有PE共享。互连网ICN受CU控制，具有双向性，采用分布式存贮器组成基本结构。
2.共享存贮的并行处理机 每个PE没有局部存储器，存储模块以集中形式为所有PE共享。互连网ICN受CU控制，具有双向性，采用分布式存贮器组成基本结构。 在采用集中式共享主存的构型中，K个存贮分体的数据经处理单元－主存模块互连网络ICN为全部N个处理单元所共享，要求K≥N。各处理单元在访问主存时,为避免发生分体冲突,也要求有合适的算法能将数据合理地分配到各个存储体中。 2019/1/17

18 I/O-CH I/O CU SC 具有集中式共享主存的并行处理机结构形式 PE0 PE1 PEN-1 ICN MM0 MM1 MMK-1 …
SM CU SC MMK-1 … 控制 具有集中式共享主存的并行处理机结构形式 2019/1/17

19 SIMD 依靠的是资源重复，而不是时间重叠。它依靠增加PE个数，与流水线处理机主要依靠缩短时钟周期相比，其提高速度的潜力要大得多。
三、并行(阵列)处理机的结构特点 速度快，特别适于高速数值计算。 SIMD 依靠的是资源重复，而不是时间重叠。它依靠增加PE个数，与流水线处理机主要依靠缩短时钟周期相比，其提高速度的潜力要大得多。 依赖于互连网络和并行算法。互连网络决定了PE之间的连接模式，也决定了并行处理机能够适应的算法。 不同结构对应的并行算法的实现方法不同，ICN的研究成为并行处理的又重点问题之一。 需要有一台高性能的标量处理机。 2019/1/17

20 并行处理机与流水处理机的比较 流水处理机 并行处理机 方式：时间重叠，并行性中的并发性 粒度：细粒度 灵活性：好 系统评价：成本低，速度受限
方式：资源重复，并行性中的同时性 粒度：粗粒度，操作级 灵活性：差 系统评价：成本高，速度潜力大 2019/1/17

21 四、并行处理机举例——ILLIAC-IV
1966年美国国防远景研究规划局ARPR与伊利诺依大学签定合同。原计划：256个PE，每个PE每240ns处理一个64位的浮点数，每个局部存储器PEM为2KX64位，总的运算速度为1GFLOPS。 美国Burroughs公司和伊利诺依大学于1972年共同设计和生产，1975年实际投入运行。用了4倍的经费，只达到1/20的速度。只实现了8X8＝64个PE，只达到50MFLOPS。 Illiac-IV系统的影响非常大。它是并行处理机的典型代表，也是分布存储器并行处理机的典型代表。 用于天气预报、核物理工程及高速科学运算。 2019/1/17

22 2019/1/17

23 ILLICA- IV 构成 Illiac-IV系统由三大部分组成：IlliacIV处理机阵列，阵列控制器CU，一台标准的Burroughs B6700输入输出计算机。 2019/1/17

24 1、处理单元阵列：由64个PUi构成,每个PUi包括(PEi和PEMi)
由64个结构完全相同的处理单元PEi 构成，每个处理单元PEi字长64位，PEMi为隶属于PEi的局部存储器，每个存储器有2K字，全部PEi由CU统一管理。 每一个PUi只和它的东、西、南、北四个近邻直接连接。{PUi+1 mod 64、PUi-1 mod 64、PUi+8 mod 64、PUi-8 mod 64} 南北方向上同一列的PU连成一个环，东西方向上构成一个闭合螺线。 采用闭合螺线最短距离不超过7步。而普通网格最短距离不超过8步。 2019/1/17

25 2019/1/17

26 ILLIAC-IV的处理单元互连图 2019/1/17

27 RGR RGB RGX RGA RGM RGS MAR AU LU SU ADA MUX T/R 东西南北 PEM、CU CU MLU
2019/1/17

28 2、阵列控制器 CU ：相当一台小型控制计算机
阵列控制器CU实际上是一台小型控制计算机。对阵列处理单元实行控制和完成标量操作。标量操作与各PE的数组操作可以重叠执行。 控制器的功能有以下五个方面： (1) 对指令进行译码，并执行标量指令； (2) 向各处理单元发出执行数组操作指令所需的控制信号； (3) 产生和向所有处理单元广播公共的地址和数据； (4) 接收和处理PE、I/O操作以及B6700产生的陷阱中断信号。 2019/1/17

29 IlliacIV的输入输出系统由磁盘文件系统DFS、I/O分系统和一台B6700处理机组成。
磁盘文件系统是两套大容量并行读写磁盘系统及其相应的控制器 I/O分系统又由输入输出开关IOS、控制描述字控制器CDC和输入输出缓冲存储器BIOM三个部分组成。 B6700管理计算机的作用是：管理全部系统资源，完成用户程序的编译或汇编，进行作业调度、存储分配、产生输入输出控制描述字送到CDC、处理中断，以及提供操作系统所具备的其他服务。 2019/1/17

30 B6700 2019/1/17

31 并行处理机举例——BSP科学计算机 2019/1/17

32 BSP的五级数据流水线构图 （集中式共享存贮器）
指令译码控制部件 处理器 存储器 NW2 NW1 17个存储块 16个处理单元 对准网络2 （NW2） 对准网络1 （NW1） 2019/1/17

33 （2）经对准网络NW1将16个操作数重新排列成16个处理单元所需要的次序；
BSP五级数据流水线的工作过程： （1）由17个存储器模块并行读出16个操作数； （2）经对准网络NW1将16个操作数重新排列成16个处理单元所需要的次序； （3）将排列好的16个操作送到并行处理单元完成操作； （4）所得的16个结果经过对准网络NW2重新排列成17个存储器模块所需要的次序； （5）写入存储器； 2019/1/17

34 无访问冲突的并行存储器 一维数组的无冲突访问（不讲） 行列相等的二维数组的无冲突访问 行列不相等的二维数组的无冲突访问
注：二维数组的无冲突访问是通过对数组元素的非顺序存储（错位存储）实现的。 2019/1/17

35 4x4二维数组无冲突访问的实现 a00 a01 a02 a03 a13 a10 a11 a12 a21 a22 a23 a20 a30
体号 体号 a00 a01 a02 a03 a13 a10 a11 a12 a21 a22 a23 a20 a30 a31 a32 a33 体内地址0 a00 a01 a02 a03 a10 a11 a12 a13 a20 a21 a22 a23 a30 a31 a32 a33 1 2 3 条件一：并行存储体的个数m≥并行访问元素个数n，要求m取质数。一般取m=n+1。 条件二：元素错位存放。即同一列相邻两元素错开的距离为d1，同一行相邻两元素错开的距离为d2，当m=22P+1时，d1=2P，d2=1。（“距离”指存储体与存储体之间的间隔） 2019/1/17

36 4x5二维数组无冲突访问的实现 a00 a01 a02 a03 a04 a10 a11 a12 a13 a14 a20 a21 a22
取存储体个数为m=7，并行访问元素的个数n=6 方案是：先将二维数组按一维线性排列，并给出地址a；然后分 别求出每个元素存储的体号地址和体内地址。 体号地址：k=a mod m 体内地址：j=⌊a/n⌋ 2019/1/17

37 数组元素 a00 a01 a02 a03 a04 a10 a11 a12 a13 a14 地址a 1 2 3 4 5 6 7 8 9 体号地址k 体内地址j 数组元素 a20 a21 a22 a23 a24 a30 a31 a32 a33 a34 地址a 10 11 12 13 14 15 16 17 18 19 体号地址k 3 4 5 6 1 2 体内地址j 体号 体内地址0 a00 a01 a02 a03 a04 a10 a12 a13 a14 a20 a21 a11 a24 a30 a31 a32 a22 a23 a33 a34 1 2 2019/1/17 3

38 5.3 SIMD并行计算机算法 结构决定算法 速度取决于数据的分布 2019/1/17

39 并行算法要求数据在存贮器中的分布 在分布式存储器构型的阵列处理机上，应能根据解题算法要求，解决好将数据合理分配到各个局部存贮器中的存贮器信息分布问题。使各PEi主要只访问本局部存贮器PEMi中的数据，且各PEi均能在同一条向量指令作用下，同时访问本局部存贮器PEMi中同一地址的单元。 在集中式存贮器构型中，存贮器的信息分布应能根据解题算法，着眼于解决好数据如何合理地分配到不同的存贮器分体中，使之可以被多个PE同时访问而不发生分体冲突。 2019/1/17

40 ILLIAC-IV的处理单元阵列结构 阵列处理机的并行算法举例 有限差分问题 矩阵加 矩阵乘 累加和 2019/1/17

41 一、图像处理算法 三基色原理：C=R(R)+G(G)+B(B) 深蓝 蓝 (0,255,255) (0,0,255) 深红 白
(255,0,255) (255,255,255) 黑 绿 (0,0,0) (0,255,0) 红 黄 (255,0,0) (255,255,0) 2019/1/17

42 图象像素的8-邻域表示 X3(i-1,j-1) X2(i-1,j) X1(i-1,j+1) X4(i,j-1) X (i,j)
对于512×512像素点，共完成262144次平滑处理。 若分成32×32个子图象块，每个子图象块由16×16个 像素点组成，需1024个PE并行工作。每个PE处理一 个子图象块，完成256次平滑处理。 2019/1/17

43 ADRN ALPHA+1；全部(α+1)与(RGAi)进行浮点规舍 加，结果送RGAi
二． 矩阵加 矩阵加(配比加)是最简单的情况。假定两个8*8的矩阵A，B相加，所得结果矩阵C也是一个8*8的矩阵。 设A 、B的分量元素分别存在PEMi的α,α+1单元中,所得结果矩阵C各分量存在PEMi 的α+2单元中只需下列3条ILLIAC Ⅳ的汇编指令就可以一次实现矩阵相加：(64个处理单元并行) LDA ALPHA ；全部(α)由PEMi送PEi的累加器RGAi ADRN ALPHA+1；全部(α+1)与(RGAi)进行浮点规舍 加，结果送RGAi STA ALPHA+2；全部(RGAi)由PEi送PEMi的α+2单元 (0≤i≤63) 2019/1/17

44 矩阵加数据在Illica中存储器的分配 α α α α+1 α+1 α+1 α+2 α+2 α+2 PEM0 PEM1 PEM63
B（0，0） α+1 B（0，1） ...... α+1 B（7，7） α+2 C（0，0） α+2 C（0，1） α+2 C（7，7） PEM0 PEM1 PEM63 2019/1/17

45 由矩阵加在ILLIAC-Ⅳ上执行可知： 在ILLIAC Ⅳ处理机上，其单指令流多数据流及数组全并行的工作特点。
可以看出由于64个处理单元是并行操作的，速度就提高为顺序处理的64倍。 分布式存贮器构型的阵列机能否发挥出阵列运算的并行能力是与数据元素在各个存贮体中的分布状况密切相关的。 2019/1/17

46 三． 矩阵乘 设A，B和C为3个8*8的二维矩阵。若给定A和B，则为计算C=A*B的64个分量，可用下列公式 0≤i≤7, 0≤j≤7 。
在SISD计算机上求解这个问题，可执行FORTRAN语言编写的下列程序（I,J,K三重循环，每重循环执行8次，共需512次乘、加的时间） DO I = 0，7 DO J= 0, 7 C（I，J）= 0 DO K = 0 ，7 10 C（I，J）= C（I，J）+A（I，K）*B（K，J） 2019/1/17

47 在SIMD计算机上求解这个问题，(相当于原来的J循环,用八个处理器同时进行一次乘、加运算,共需64次乘加时间)
DO 10 I = 0，7 C（I，J）= 0 DO 10 K = 0 ，7 C（I，J）= C（I，J）+A（I，K）*B（K，J） 然而，为了让各个处理单元PEi尽可能只访问所带局部存储器PEMi，以保证高速处理，就必须要求矩阵A、B、C各分量按下图所示的方案在局部存储器中分布。 2019/1/17

48 …… … PEM0 … PEM1 … PEM7 矩阵乘 的存储 器分配 举例 A(0,0) A(1,0) A(7,0) B(0,0)
C(0,0) C(1,0) C(7,0) PEM0 … A(0,1) A(1,1) A(7,1) B(0,1) B(1,1) B(7,1) C(0,1) C(1,1) C(7,1) PEM1 … A(0,7) A(1,7) A(7,7) B(0,7) B(1,7) B(7,7) C(0,7) C(1,7) C(7,7) 矩阵乘 的存储 器分配 举例 PEM7 …… 2019/1/17

49 在ILLIAC Ⅳ处理机上，由矩阵乘算法的实现，进一步说明了信息在存贮器中分布算法的重要性以及阵列处理机具有解题专用性的特点。同时，也表明了需要有能将处理单元的数据经互连网络播送给各个处理单元的功能。
进一步把K循环也改为并行,相当于64个单元全部并行运算, DO 10 I = 0，7 C（I，J）= 0 10 C（I，J）= C（I，J）+A（I，K）*B（K，J） 这时, 数据重新分配在64个局部存储器上, 同时, 八个中间积A（I，K）*B（K，J）能够并行加(累加),速度提高8/Log28 2019/1/17

50 四.累加和 其中SHFTR(C,2**K)是向量传送语句,C向量各分量向右传送步距为2的K次幂
这是一个将N个数的顺序相加过程转变为并行相加过程的问题。 设N为8，即有8个数A（I）顺序累加，其中0<=I<=7 在SISD计算机上可写成下列程序：需要8次加法 C=0 DO 10 I=0，7 10 C=C+A（I） 其中SHFTR(C,2**K)是向量传送语句,C向量各分量向右传送步距为2的K次幂 用成对递归算法,只需 Log2 8=3 在SISD计算机上可写成下列程序 C=A DO 10 K=0, Log 10 C=C+SHFTR(C,2**K) 2019/1/17

51 设原始数据A（I）分别存在PEMi的某个单元中
A0+A1 PE1 A1 PE2 A2 PE3 A3 A2+A3 A0+A1+A2+A3 PE4 A4 PE5 A5 A4+A5 PE6 A6 A0+A1+A2+A3 +A4+A5+A6+A7 PE7 A7 A6+A7 A4+A5+A6+A7 步 步 步3 2019/1/17

52 算法描述如下： 第一步：置全部PEi为活跃状态，0≤i≤7;
第二步：全部A（I）从PEMi的a单元读到相应PEi的累加寄存器RGAi中， 0≤i≤7; 第三步：令k＝0; 第四步：将全部PEi的（RGAi）转送到传送寄存器RGRi， 0≤i≤7; 第五步：将全部PEi的（RGRi）经过互连网络向右传送2k步距, 0≤i≤7; 第六步：令j＝2k-1; 第七步：置PE0至PEj为不活跃状态; 2019/1/17

53 第八步：处于活跃状态的所有PEi执行（RAGi）：＝（RGAi）＋（RGRi）, j≤i≤7; 第九步：k:＝k+1;
第十二步：将全部PEi的累加寄存器内容（RGAi）存入相应的a+1单元中， 0≤i≤7。 Wuhan University 2019/1/17

54 5.4 SIMD计算机的互连网络 并行处理机工作原理
由CU将指令广播给各个处理单元（PE），所有活跃的PE以同步方式执行相同的指令，并从不同的存储模块中取得不同的数据进行处理，各处理单元之间的数据交换由互连网络IN实现 互连网络 互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用于实现计算机系统内部多个输入结点与多个输出结点之间的相互连接。 2019/1/17

55 互连网络的特性 互连网络通常是用有向边或无向边连接有限个结点的组成。
互连网络的主要特性有： (1) 网络规模：网络中结点的个数 (2) 结点度：与结点相连接的边数称为结点度。包括入度和出度。进入结点的边数叫入度，从结点出来的边数则叫出度 (3) 距离：两个结点之间相连的最少边数 (4) 网络直径：网络中任意两个结点间距离的最大值。用结点间的连接边数表示 (5) 结点间的线长：两个结点间连线的长度。用米、公里等表示 (6) 对称性：从任何结点看到拓扑结构都是一样的网络称为对称网络。对称网络比较易实现，编程也较容易。 2019/1/17

56 中转传送的步数要少，以提高阵列运算速 度； 规整性、模块性要好，以便可以采用基本构件来组合，增强系统的可扩充性，也便于大规模集成。
SIMD互连网络的设计目标是： 结构要简单，以降低成本； 连接要灵活，以满足算法和应用的需要； 中转传送的步数要少，以提高阵列运算速 度； 规整性、模块性要好，以便可以采用基本构件来组合，增强系统的可扩充性，也便于大规模集成。 互连网络的标准化 2019/1/17

57 一、互连函数 互连网络的连接特征一般用互连函数表示
将互连网的N个输入和N个输出端分别用整数（0，1，2，…，N-1）来表示，则表示相互连接的输出端号和输入端号之间的一一对应关系称为互连函数。 函数表示法：x表示输入端变量，f(x)表示互连函数。x用n位二进制形式表示，写成：xn-1xn-2…x1x0 ,互连函数表示为：f(xn-1xn-2…x1x0 )。n=log2N 2019/1/17

58 几种常用的互连函数 恒等置换 方体置换 全混洗置换 交换置换 蝶式置换 移数置换 PM2I置换 2019/1/17

59 1、恒等置换 输入结点的二进制地址 输出结点的二进制地址 2、方体置换 2019/1/17

60 N=8个结点时的方体置换 (000)0 (001)1 (010)2 (011)3 (100)4 (101)5 (110)6 (111)7
输入 输出 K=0 K=1 K=2 2019/1/17

61 3、全混洗置换（均匀洗牌） 4、交换置换 5、蝶式置换 2019/1/17

62 输入 输出 输入 输出 输入 输出 (000)0 (000)0 (000)0 (000)0 (000)0 (000)0 (001)1
(010)2 (010)2 (010)2 (010)2 (010)2 (010)2 (011)3 (011)3 (011)3 (011)3 (011)3 (011)3 (100)4 (100)4 (100)4 (100)4 (100)4 (100)4 (101)5 (101)5 (101)5 (101)5 (101)5 (101)5 (110)6 (110)6 (110)6 (110)6 (110)6 (110)6 (111)7 (111)7 (111)7 (111)7 (111)7 (111)7 全混洗置换 交换置换 蝶式置换 2019/1/17

63 设有N个处理单元，n=log2N个互连函数，如当N=8时有3个子蝶式函数式为：
子蝶式置换 设有N个处理单元，n=log2N个互连函数，如当N=8时有3个子蝶式函数式为： 2019/1/17

64 通过输入端数组循环移动一定的位置，得到输出端的地址，表达式如下：
6、移数置换 通过输入端数组循环移动一定的位置，得到输出端的地址，表达式如下： 段内循环移数 把整个输入端数组分成若干个子数组，在子数组内进行循环移数，表达式有两个式子，如下所示： 2019/1/17

65 N个结点的PM2I置换函数共有2n(n=log2N)个。表达式如下所示，式中，0≤j≤N-1，0≤i≤n-1。由于
PM2＋（n-1)=PM2-(n-1)，所以PM2I互连函数只有2n-1种是不相同的。（实际上也是一种移数置换） 2019/1/17

66 互连函数举例 例1、当N=16时 (1)写出方体置换、PM2I置换和全混洗置换函数的一般表达式；
(2)对于C2、PM2+3和S(S)，分别求出第3号PE与哪一个PE相连？ 解(1)：因为N＝16，n=log216=4，故有方体置换函数4个，分别为： 2019/1/17

67 (2) 3号PE的二进制编号为：0011，所以对于C2，C2（0011）＝0111，与7号PE相连。
PM2I置换函数8个，分别为： PM2+i（j）=j+2imod N PM2-i（j）=j-2imod N 上两式中，0≤j≤15,0≤i≤3,N=16 全混洗置换函数为： S(x3x2x1x0)=x2x1x0x3 (2) 3号PE的二进制编号为：0011，所以对于C2，C2（0011）＝0111，与7号PE相连。 　PM2＋3（3）＝3＋23MOD16＝11，与11号PE相连。 　S（S（0011））＝S（0110）＝1100，所以3号PE与12号PE相连。 2019/1/17

68 例2、若有8×8矩阵A=(aij)以行为主的顺序存放在主存 中，用什么样的单级互连网络可使A矩阵转换成转置 矩阵AT？总共需要多少步？
解：矩阵A=(aij)以行为主的顺序存放在主存中，元素aij 的行、列地址可i2i1i0j2j1j0表示。而经转置以后， aij存放 的地址为j2j1j0i2i1i0。 可用均匀洗牌单级互连网络可使A矩阵转换成转置 矩阵AT？表达式如下： S(S(S(i2i1i0j2j1j0)))= j2j1j0i2i1i0。总共需要3步？ 2019/1/17

69 二、互连网络的特征与分类 互连网络的结构特征 静态互连网络 动态互连网络 2019/1/17

70 1、互连网络的结构特征 在确定PE之间通信的互连网络时，需要对操作方式、控制策略、交换方式和网络的拓扑结构作出选择。 1、操作方式：同步、异步、同步/异步组合等3种方式。现有的阵列处理机根据其SIMD性质均采用同步操作方式，让所有PE按时钟同步操作。异步或组合方式一般用于多处理机系统。 2、控制策略：集中和分布两种。互连网络是由许多开关单元和互连线路组成，互连通路的路径选择是通过置定开关单元的工作状态来控制的。多数现有的SIMD互连网络采用由集中控制部件对全部开关单元执行集中控制的策略。 2019/1/17

71 4、拓扑结构：指的是互连网络入、出端可以实现连接的模式，有静态和动态两种。
3、交换方式：线路交换、包交换、线路/包交换组合等3种不同的方法。SIMD互连网络一般采用硬连的线路交换，包交换一般多用于多处理机和计算机网络中。 4、拓扑结构：指的是互连网络入、出端可以实现连接的模式，有静态和动态两种。 静态互连网络：在运行中不能改变的网络。在静态互连网络中，每一个开关元件固定地与一个结点相连，建立该结点与邻近结点之间的连接通路，直接实现两结点间的通信。 动态拓扑结构设置有源开关，因而可以根据需要借助控制信号对连接通路加以重新组合，实现所要求的通信模式。 2019/1/17

72 2、静态互连网络 线性阵列 环和带弦环 0 1 2 3 循环移数网络 树形和星形 胖树形 7 6 5 4 网格和环网形 搏动式阵列 超立方体
带环立方体 k元n-立方体网络 线性阵列 2019/1/17

73 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 度为3的带弦环 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 环网 1 2 3 4 5 7 6 循环移数网 2019/1/17

74 二叉树网 二叉胖树网 星形网 2019/1/17

75 Illiac网 网格形 环形网 2019/1/17

76 静态：性能与带宽 1 N-1 N(N-1)/2 全互连 log2N (Nlog2N)/2 超立方 多维 3 8 立方体 三维
二叉树 结构 维数 2 星形 4 网格 N/2 N 环状 二维 线性 一维 结点最大间距 最大 连接度 连接数 拓扑结构 2019/1/17

77 3、动态互连网络 单级互连网络 动态单级网络：每级只有有限的几种连接，因而在阵列处理机中必须多次循环通过，才能实现任意两个处理单元之间的信息传送，故也称此动态单级网络为循环网络。 多级互连网络 动态多级网络：由多个单级网络串联组合而成，以实现任意两个处理单元之间的连接。还可将多级互连网络循环使用，以实现复杂的互连。 2019/1/17

78 三、单级互连网络 立方体网络 PM2I网络 混洗交换网络 2019/1/17

79 1、单级立方体网络 N个输入结点与N个输出结点的立方体互连函数n=log2N个。其中第k个函数为： 2019/1/17

80 立方体单级网络连接图 C0 C1 C2 三维立方体结构 010 110 100 000 111 011 001 101 010 110
y z x 010 110 100 000 111 011 001 101 三维立方体结构 立方体单级网络连接图 2019/1/17

81 立方体网络的寻径算法 对源结点和目的结点的二进制地址逐位异或，然后根据所得的结果进行寻址。
在异或结果中，若某位为0，表示在寻址过程中该位对应的方向上没有移动；若某位为1，则表示在相应的方向上移动一步。 例如从源结点101到目的结点100，二者异或和结果是001，这表示只在X方向上走一步，就从101结点走到了100。 2019/1/17

82 2、单级PM2I互连网络 PM2I单级互连网络(“加减Plus-Minus 2i”单级网络)中，共可以有2n个互连函数，分别是
PM2+i(j)=j+2i mod N PM2-i(j)=j-2i mod N 其中，0≤j≤N-1，0≤i≤n-1，n=㏒2N。这2n个互连函数中，PM2＋(n-1)=PM2-(n-1)。所以，只有2n-1个互连函数是不同的，PM2I互连的最大距离为 。例如，三维PM2I互连网络(N=8)的互连函数有PM2+0、PM2-0、PM2+1、PM2-1、PM2±2等5个不同的互连函数，分别是 PM2+0: ( ) PM2-0: ( ) PM2+1: ( )( ) PM2-1: ( )( ) PM2±2: (0 4)(1 5)(2 6)(3 7) 2019/1/17

83 1 2 3 4 5 6 7 PM2+0 PM2+1 PM2+/-2 PM2-1 PM2I在N=8时互连网络连接图 2019/1/17

84 结点最大间距 n/2 = log2N/2 ≤log2N/2 应用：几种互连函数混合，任意结点间可连接。
实例：闭合螺旋结构为PM2I±0及PM2I±3互连函数。 1 2 3 4 5 6 7 PM2±0：顺环圆周连 PM2±1：顺环内接N/2边形连接； PM2±2：顺环内接N/4边形连接； ±(n-1)：顺环内直径连接。 2019/1/17

85 3、混洗交换单级互连网络 　混洗交换单级互连网络(Shuffle-Exchange，简称SE网络)包括全混(Perfect Shuffle)和交换(Exchange)两个互连函数。 全混洗函数（均匀洗牌） 交换函数 2019/1/17

86 N=8个结点的全混洗(shuffle)网络
1 2 3 4 5 6 7 N=8个结点的交换(exchange)网络 1 2 3 4 5 6 7 2019/1/17

87 最大间距：n次交换，n-1次混洗，共2n-1次； 应用：多次调用混洗交换互连函数，可实现任意结点间的连接。
N=8个结点的混洗交换(SE)网络 1 2 3 4 5 6 7 最大间距：n次交换，n-1次混洗，共2n-1次； 应用：多次调用混洗交换互连函数，可实现任意结点间的连接。 2019/1/17

88 输入 混洗前二进制编码 经1次混洗后二进制编码 经2次混洗后二进制编码 经3次混洗后二进制编码 输出 000 1 001 010 100 2
000 1 001 010 100 2 3 011 110 101 4 5 6 7 111 N=8个处理单元的n次混洗后入出端的连接 2019/1/17

89 单级互连网络总结 单级互连网络应用 单级互连网络特性 任一单级互连网络均可表示成N入 N出的过程。
任一单级互连网络可实现部分结点(一对或几对)间的连接，不能实现任意多对结点间的同时连接。 单级互连网络含义：某些连接方法或拓扑结构。 单级互连网络应用 利用单级互连网络的特性作为实际IN的拓扑结构； 通过交换开关作为IN的可变因素； 通过交换开关多次控制实现IN的结点间任意互连。 2019/1/17

90 四、多级互连网络 2019/1/17

91 关键技术一：交换开关 交换开关是具有多个入端和多个出端的交换单元，用作各种多级互连网络的基本部件 直通 交换 上播 下播 2019/1/17

92 关键技术二：拓朴结构 2019/1/17

93 关键技术三：控制方式 2019/1/17

94 多级互连网络举例 多级立方体网络 STARAN网络 间接二进制n方体网络 多级混洗交换网络 多级PM2I网络(选讲) 基准网络 全排列网络
2019/1/17

95 1、STARAN网络 交换开关：N个结点，每级有N/2个交换开关，有n 级，n=log2N，每个开关为双功能（直连、交换），从输入到输出依次为K0,K1,…Kn-1 拓扑结构：共有n+1 级拓扑，编号从输入到输出端依次为C0, C1, …,Cn，其中C0为恒等置换，C1,…,Cn为逆混洗置换（循环右移） 控制方式：级控或部分级控 2019/1/17

96 以N=8为例，有n=3级交换开关K0、K1、K2， 每级有4个；有4级拓扑结构C0、C1、C2、C3；
控制方式：采用级控方式实现交换函数功能， 采用部分级控实现移位函数功能（图、表） P364、365 2019/1/17

97 N=8的STARAN网络 C1 --C3:S-1(x2x1x0)=x0x2x1 1 2 3 4 5 6 7 输 入 端 1 2 3 4 5
1 2 3 4 5 6 7 输 入 端 1 2 3 4 5 6 7 输 出 端 A B C D K0 E F G H K1 I J K L K2 C0 C2 C1 C3 N=8的STARAN网络 2019/1/17

98 级控制信号(K2K1K0)注：Ki为第i级控制信号，Ki=0为直连Ki=1为交换
采用级控制方式时为交换网络，它只能实现交换函数的功能。 级控制信号(K2K1K0)注：Ki为第i级控制信号，Ki=0为直连Ki=1为交换 000 001 010 011 100 101 110 111 入 端 号 1 2 3 4 5 6 7 执行的交换函数功能 恒等 4组2元 +2组4元 2组4元 2组4元+1组8元 4组2元+2组4元+1组8元 4组2元+1组8元 1组8元 i Cube0 cube1 C0+C1 Cube2 C0+C2 C1+C2 C0+C1+C2 2019/1/17

99 采用部分级控方式时，实现的是移数函数功能
制 信 号 2级 K,L 1 J I 1级 F,H E,G 0级 A,B，C,D 入 端 2 4 3 5 6 7 可实现的移数功能 移1 移2 移4 不移 mod8 mod4 mod2 全等 采用部分级控方式时，实现的是移数函数功能 2019/1/17

100 2、间接二进制n方体网络 采用单元控制的多级立方体网络称为间接二进制n方体网络。
交换开关：N个结点的n方体网络有n级，每级N/2个交换开关组成，每个开关为双功能（直连、交换），编号从输入端到输出端依次为k0, k1,…,kn-1 拓扑结构：共有n+1 级，从输入到输出依次为C0, C1, …,Cn，其中 C0恒等置换,C1 …,Cn-1为子蝶式置换，Cn为逆混洗置换 控制方式：单元控制 2019/1/17

101 以N=8为例，有n=3级交换开关K0、K1、K2， 每级有4个；有4级拓扑结构C0、C1、C2、C3；
逆混洗置换。 控制方式：单元控制，即每一个交换开关有 一个控制信号，同样，采用级控方式实现交 换函数功能，采用部分级控实现移位函数功 能（表6.1,6.2）P327、328 2019/1/17

102 N=8的间接二进制n方体网络 C1:B1(x2x1x0)=x2x0x1 C2:B2(x2x1x0)=x0x1x2
C3:S-1(x2x1x0)=x0x2x1 1 2 3 4 5 6 7 输 入 端 1 2 3 4 5 6 7 输 出 端 A B C D K0 E F G H K1 I J K L K2 C0 C2 C1 C3 N=8的间接二进制n方体网络 2019/1/17

103 多级立方体网络的特点是：交换开关用二功能，控制方式可以有级控制、部分级控制和单元控制。
采用级控制方式的多级立方体网络称为交换网络，它只能实现交换函数的功能。 采用部分级控制的多级立方体网络中的一种移数网络，可以实现移数函数的功能。 采用级控和部分级控的立方体网络最先用于STARAN计算机上，所以也称为STARAN网络。 STARAN可同时实现多对结点之间的连接，尚不能同时实现任意组合。 2019/1/17

104 交换网络的应用：对集中式共享存储的阵列处理机同时数据传输作用很大。
移数网络的应用：移数功能很适合于累加求和算法实现；不同的mod，可用作不同的分组操作。 2019/1/17

105 例6.1 编号分别为0、l、2、…、F的16个处理器之间要求按下列配对通信：
（B、l），（8、2），（7、D），（6、C），（E、4），（A、0），（9、3），（5、F）。试选择所用互连网络类型、控制方式，并画出该互连网络的拓扑结构和各级交换开关状态图。 2019/1/17

106 [分析]由处理器号所要求的配对传送关系转成处理器二进制编号的配对传送关系，分别为 （B、l）是（1011，0001）
（8、2）是（1000，0010） （7、D）是（0111，1101） （6、C）是（0110，1100） （E、4）是（1110，0100） （A、0）是（1010，0000） （9、3）是（1001，0011） （5、F）是（0101，1111） 不难得出其一般规律是二进制编号为P3P2P1P0的处理器与P3P2P1P0的处理器配对交换数据。由 　于实现的都是交换函数的功能，采用成本最低的级控制多级立方体互连网络即可完成。 2019/1/17

107 16个端的多级立方体网络，N=16。由n=㏒216=4级组成。每一级均使用N/2，即8个两功能交换开关。多级网络各级的级号由入端到出端依次为0，1，2，3。第i级的每个交换单元的配对用的是：Cubei(P3…Pi…P0)= ，其中，0≤i≤3。将各交换单元两个入/出端的号配好对之后，再将各级上同号的端用线连接，就可以画出此多级立方体互连网络的拓扑结构图。开关状态只需按本题算法所要求的规律，让第1，3级的各交换单元处于交换状态，第0，2级的交换单元处于直连状态即可。 [解答]采用4级立方体网络，级控制。互连网络的拓扑结构和各级交换开关的状态如下图。 2019/1/17

108 Cube Cube Cube Cube3 1 2 3 4 5 6 7 8 9 A B C D E F 2 1 3 4 6 5 7 8 A 9 B C E D F 4 1 5 2 6 3 7 8 C 9 D A E B F 8 1 9 2 A 3 B 4 C 5 D 6 E 7 F 1 2 3 4 5 6 7 8 9 A B C D E F 入端 出端 C0 K0 C1 K1 C2 K2 C3 K3 C4 开关状态： 直连 交换 直连 交换 2019/1/17

109 上面是间接二进制n方体网络的实现结构图，同样，也可以采用STARAN网络，实现结构如下页图所示。
上页图中，C0（P3P2P1P0）＝ P3P2P1P0 C1（P3P2P1P0）＝P3P2P0P1(子蝶式置换） C2（P3P2P1P0）＝P3P0P1P2 (子蝶式置换） C3（P3P2P1P0）＝P0P2P1P3 (子蝶式置换） C4（P3P2P1P0）＝P0P3P2P1 (逆混洗置换） 上面是间接二进制n方体网络的实现结构图，同样，也可以采用STARAN网络，实现结构如下页图所示。 2019/1/17

110 开关状态： 直连 交换 直连 交换 2019/1/17

111 当N=64时，要求输入PE3与输出PE31相连，各 级交换开关应处于什么状态？ 解：当N=64时，PE3和PE31的二进制地址分别
为(000011)、(001111)。那么各级控制信号为： K5K4K3K2K1K0=(000011)⊕(001111)=001100 第二、三级为交换，其它各级为直连。 2019/1/17

112 例6.2并行处理机有16个PE，实现相当于4组4元交换，然后2组8元交换，再1组16元交换功能。写出互连函数一般式、各级交换开关状态。
答：因需实现交换功能，故选择STARAN的交换网络(级控制方式）。 4组4元交换 Cube0+Cube1 2组8元交换 Cube0+Cube1+Cube2 1组16元交换 Cube0+Cube1+Cube2+Cube3 相加 Cube0+Cube1 +Cube3 各级开关状态：k3k2k1k0=(1011) 互连函数：f(b3b2b1b0)=(b3b2b1b0) 2019/1/17

113 另一种解法： 由于有16个处理器，它们的编号依次为0、1、2、┅、E、F，首先对其4组4元交换： 然后进行2组8元交换：
再次是1组16元交换： A B C D E F B A 9 8 F E D C B A 9 8 F E D C C D E F 8 9 A B C D E F 8 9 A B B A 9 8 F E D C 2019/1/17

114 由此对应关系，可知16个处理器之间的配对连接是(0,B),(1,A),(2,9),(3,8),(4,F),(5,E),(6,D),
最后得出输入与输出之间的对应关系为： 由此对应关系，可知16个处理器之间的配对连接是(0,B),(1,A),(2,9),(3,8),(4,F),(5,E),(6,D), (7,C)。根据这些配对处理器二进制地址的变化，很容易要求出互连函数的一般表达式 由于是实现交换函数之功能，可用STARAN网络来实现，并采用级控方式。互连网络图如下页图所示。其中，K2 级为直连，而其它级为交换，便可实现以上所要求处理器之间的配对连接。 A B C D E F B A F E D C 2019/1/17

115 开关状态： 交换 交换　　　　 直连　　　 交换 2019/1/17

116 例6.3：对于采用级控制的三级立方体网络，当第i级（0≤i≤2）为直连状态时，不能实现哪些结点之间的通信？为什么？反之，当第i级为交换状态呢？
能够实现互连的入、出端号的二进制码中的Pi位是 不能变反的，其它的Pj（j≠i）可以不变，也可以 变反。 如果第i级为交换状态时，能实现互连的入、出端 号的二进制码的Pi位必须变反，其它的Pj（j≠i） 可以不变，也可以变反。 2019/1/17

117 当第i级为“直连”时，不能实现入、出端的处理器二进制码的编号中第Pi位取反的处理器之间的连接，因为Pi位控制第i级开关只能直连。
[解答]： 当第i级为“直连”时，不能实现入、出端的处理器二进制码的编号中第Pi位取反的处理器之间的连接，因为Pi位控制第i级开关只能直连。 当第i级为“交换”时，不能实现入、出端的处理器二进制编号中第Pi位相同的处理器之间的连接。 2019/1/17

118 3、多级混洗交换网络 多级混洗交换网络又称为omega(Ω)网络.
交换开关： N个结点的Omega网络，由n=log2N级、每一级有N/2个交换开关组成；每个交换开关为4功能，即直连,交换,上播和下播。交换开关的级号编排，从输出端到输入端依次为K0、K1、···Kn-1 ； 拓扑结构： N个结点的Omega网络有n+1级拓朴结构，拓朴结构编号，从输出端到输入端依次为C0、C1、···Cn-1 、Cn；其中，C0为恒等置换，C1、···Cn 为混洗置换。 控制方式：级控制、部分级控制、单元控制。 Omega网络的寻径算法：采用终端地址标记控制算法。 2019/1/17

119 全混拓扑 全混拓扑 全混拓扑 1 1 A E I 2 3 2 3 B F J 入 端 出 端 4 5 4 5 C G K 6 7 6 7 D
1 1 A E I 2 3 2 3 B F J 入 端 出 端 4 5 4 5 C G K 6 7 6 7 D H L C3 K2 C2 K1 C1 K0 C0 N=8多级混洗交换网络 2019/1/17

120 利用交换开关的播送功能实现一对多的连接。如后面图所示。
级控制且开关为二功能： 是STARAN交换网络的逆网络； （F、G交换位置） 部分级控制且开关为二功能： 是STARAN移数网络的逆网络； 单元控制：可实现更强大的功能。 利用交换开关的播送功能实现一对多的连接。如后面图所示。 2019/1/17

121 终端地址标记控制寻径算法 在单元控制的多级混洗交换网络中，为了确定输入与输出结点对之间的连接路径，常采用终端地址标记控制寻径算法。
终端地址标记控制寻径算法：设网络终端（输出）地址为dn-1dn-2…d1d0 ,从输入端开始，第i级Ki的开关状态由终端地址相应位di控制。若di=0，则Ki级上对应开关的输入端与上输出端相连；若di=1，则Ki级上对应开关的输入端与下输出端相连。 2019/1/17

122 N=8多级混洗交换网络(采用4功能交换单元)
下播 上播 d2d1d0 0(000) 1(001) 1 E I A 2 3 2(010) 3(011) B F J 入 端 出 端 4 5 4(100) 5(101) C G K 6 7 6(110) 7(111) D H L 级 2 1 N=8多级混洗交换网络(采用4功能交换单元) 能一次实现入端2到全部8个出端的连接 2019/1/17

123 Omega网络和多级立方体网络之间存在的差别
①前者的数据流向是级号n-1、n-2、…、1、0，而后者的数据流向是级号0、1、…、n-1，正好相反； ②前者用四功能交换单元，后者用两功能交换单元。 可以由操作系统对Omega多级互连网络各个端的二进制编号首尾对称交换一下，即由二进制Pn-1Pn-2…P1P0更改成二进制P0P1 … Pn-2Pn-1 ，就可以使它与单元控制的立方体多级网络完全一致。从而，可以在Omega网络上运行原立方体多级网络所能运行的全部SIMD程序，实现软件的向上兼容。 2019/1/17

124 能同时实现5到0，7到1的连接，但不能同时实现0到5、1到7的连接
I E F G H 1 2 3 4 5 6 7 入 端 1 2 3 4 5 6 7 出 端 A B J C K D L 级 1 2 N=8多级立方体互连网络 能同时实现5到0，7到1的连接，但不能同时实现0到5、1到7的连接 2019/1/17

125 能同时实现0到5，1到7的连接，但不能同时实现5到0、7到1的连接
1 1 A E I 2 3 2 3 B F J 入 端 出 端 4 5 4 5 C G K 6 7 6 7 D H L 级 2 1 N=8多级混洗交换网络 能同时实现0到5，1到7的连接，但不能同时实现5到0、7到1的连接 2019/1/17

126 4、多级PM2I网络 PM2I网络的结构特点： 交换开关：N个结点的多级PM2I网络，由n+1级、每一级有N个交换开关组成；交换开关的级号编排，从输出端到输入端依次为K0、K1、···Kn； 拓朴结构：N个结点的多级PM2I网络有n级拓朴结构，拓朴结构编号，从输出端到输入端依次为C0、C1、···Cn-1 ；每级实现的是I+PM2I的功能，其中，I为恒等置换。 控制方式：当采用部分级控方式时，多级PM2I网络可实现数据变换功能；当采用单元控制方式时，由于控制更为灵活，故称之为强化数据变换网络。 2019/1/17

127 这种网络中提供了冗余路径。如为实现由7将信息传到2，所经路径可以是：7、3、3、2；或7、7、1、2；或7、3、1、2等多条。
每一级控制信号有平控H、下控D和上控U。为简化对这三类信号的产生，可将各级的单元分成两组。对于第i级，让H1i、D1i 、U1i控制第i位为0的那些入单元，让H2i、D2i 、U2i控制第i位为1的那些入单元。为了增强对各级单元控制的灵活性，采用单元控制方式，则称为强化数据变换网络(ADM—Augmented Data Manipulator)。 2019/1/17

128 a e b f g c i k d h m n j l 1 1 1 1 2 2 2 2 3 3 3 3 入端 出端 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 k l i j n m e f g h a b c d 级 N=8多级PM2I网络 2019/1/17

129 5、基准网络 基准网络的结构特点： 交换开关：N个结点的网络由n=log2N级构成，每级开关的编号从输入端到输出端依次为K0、K1、…、Kn-1；每级的交换开关数为N/2个，整个网络的开关数为(N/2)×log2N个。 拓朴结构：N个结点的网络共有n+1级拓朴结构，其编号从输入端到输出端依次为C0、C1、…、Cn；C0 和Cn为恒等置换，C1 是逆混洗置换，C2-Cn-1 为子逆混洗置换。 控制方式：单元控制 可以采用终端地址标记的寻径算法。 2019/1/17

130 N=8个结点的基准网络 C1: S-1(x2x1x0)=x0x2x1 C2:B2(x2x1x0)=x0x1x2 1 2 3 4 5 6 7
1 2 3 4 5 6 7 输 入 端 1 2 3 4 5 6 7 输 出 端 A B C D K0 E F G H K1 I J K L K2 C0 C2 C1 C3 N=8个结点的基准网络 2019/1/17

131 多级网络比较 灵活性(低→高)：STARAN、间接二进制n方体、Omega(ω)、ADM(混洗四功能) 成本(低→高)：同上
用途： STARAN、Omega PE←→M 间接二进制n方体 PE→PE 功能：只能实现同时部分多对多功能。 2019/1/17

132 立方体、混洗交换、PM2I等多级网络都能实现将任意一个入端连到任意一个出端上，但不能实现将多个入端一到一地同时连到各自任意的出端上，称为阻塞式网络(Blocking Network)。
因为N个端的一到一的全部排列有N！种，用单元控制的n=㏒2N级间接二进制n方体网络，每级有N/2个开关，全部开关总数为(N/2)×㏒2N ，就“直接”和“交换”两种状态的组合总数只有2(N/2)×㏒2N=N(N/2)种组合情况，远小于N!，所以无法实现N！种全排列的连接。 2019/1/17

133 6、全排列网络 定义：所有入端、出端的连接均不发生冲突的网络，又称非阻塞型网络，即：N入→N出有N！种排列。
互连网络要求：全排列网络(非阻塞型网络)。 实现全排列网络一般可以有两种做法: 思想：N!＜NN/2×NN/2＜NN。 一种做法是依据循环网络的思路，在多级网络的入、出端上设置缓冲器，让数据在多级互连网络上循环再次通过。 另一种做法是将两个互为逆网络的㏒2N级网络串联，且合并掉中间重复的一级这后，构成2㏒2N-1级的多级到连网络。如下图所示。 2019/1/17

134 立方体多级网络和它的逆网络连在一起，省去中间重复的一级
合并成一级 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 多级全排列网络举例(Benes网络) 立方体多级网络和它的逆网络连在一起，省去中间重复的一级 2019/1/17

135 改进的终端标记算法 全排列网络的开关控制算法是改进的终端标记算法
改进的终端地址标记控制的寻径算法只用一个输入端的控制信号di 来控制开关的工作状态。 如果用上输入端的di来控制，则当di =0时，开关处于直连状态，当di =1时，开关处于交换状态； 如果用开关的下输入端的di来控制，则当di=0时，开关处于交换状态，当di=1时，开关处于直连状态。 值得注意的是，虽然可用开关的上、下输入端控制开关的工作状态，但在一次置换中，只能采用一种控制方案。 位序颠倒置换：P(xn-1xn-1…x1x0)=x0x1…xn-2xn-1 2019/1/17

136 用改进的终端标记控制算法实现位序颠倒置换
1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 5 9 13 17 (000) (100) 2 6 10 14 18 (010) (110) (001) 3 7 11 15 19 (101) (011) 4 8 12 16 20 (111) K0 d0 K1 d1 K2 d2 K3 d1 K4 d0 2019/1/17

137 本章重点回顾 并行性的基本概念、阵列机与多机系统并行性开发的异同点 ILLIAC阵列机的结构和特点
互连函数、动态互连网络（STARAN、OMEGA、间接二进制n方体） 2019/1/17

138 第5章 结束，谢谢 作业：2、4、6 The End 2019/1/17

139 典型例题与习题分析与解答 题1.画出16台处理器仿ILLIAC Ⅳ的模式进行互连的互连结构图，列出PE0分别只经一步、二步和三步传送能将信息传送到的各个处理器号。 解：16台处理机仿ILLIAC Ⅳ的模式互连结构图如下页图所示。由图可知： PE0经一步可将信息传送到的处理器号有PE1、PE4、PE12、PE15。 PE0经二步可将信息传送到的处理器号有PE2、PE3、PE5、PE8、PE11、PE13、PE14。 PE0经三步可将信息传送到的处理器号有PE6、PE7、PE9、PE10。 可见，最多经3步就可以将PE0的信息传送到任何其它的处理器上，所以其最大的距离为3步。 2019/1/17

140 PE0 PE1 PE2 PE3 PE4 PE5 PE6 PE7 PE8 PE9 PE10 PE11 PE12 PE13 PE14 PE15
16台处理器仿ILLIAC Ⅳ机的互连机构 2019/1/17

141 例1（仿题2）：编号为0、1、·····14、15的16个处理器，用单级互连网络互连。当互连函数分别为
（1）Cube3 （2）PM2+3 （3）PM2-0 （4）Shuffle （5）Shuffle(Shuffle)时，第13号处理器各连至哪一个处理器？ ［分析］：由于是16个处理器组成的单级互连网络，每个处理器的二进制地址编号为4位。根据互连函数关系式，即可求出与第13号处理器相连的处理器号。 2019/1/17

142 解： （1） ， （2） 即第13号处理器连至第5号处理器； （3） 即第13号处理器连至第12号处理器； （4）
（1）　　　　　　　　　　　　　　　　　　， 　　第13号处理器连至5号处理器； （2） 　　　即第13号处理器连至第5号处理器； （3） 　即第13号处理器连至第12号处理器； （4） 第13号处理器与第11号处理器相连； （5） 第13(1101)号处理器连至第7(0111)号处理器。 2019/1/17

143 题9. 假定8×8矩阵A=（aij），顺序存放在存贮器的64个单元中，用什么样的单级互连网络可实现对该矩阵的转置变换？总共需要传送多少步？
[分析]因为顺序存放在64个单元的二进制地址码编号为P5P4P3P2P1P0。如果8×8的矩阵的各元素是以行为主序存放的，则其中P5P4P3就为行号，P2P1P0为列号。如果矩阵以列为主序也是类似的，只是此时P5P4P3为列号，P2P1P0为行号。实现矩阵的转置变换就是对存贮器存放的内容进行搬移，搬到行号变成列号，列号变成行号的那些单元中去。显然，这只需经过单级混洗互连网络，循环通过3次，即混洗传送3次即可。 [解答] 用单级全混网络传送，循环通过传送3步即可。 2019/1/17

144 [解答]0-7号共8个处理器的三级混洗互连网络及其交换开关状态设置如图。采用终端地址标记寻径算法 。
题12.画出0～7号共8个处理器的三级混洗交换网络，在该图上标出实现将6号处理器数据播送给0～4号，同时将3号处理器数据播送给其余3个处理器时的各有关交换开关的控制状态。 [分析]8个处理器的三级混洗交换网络可先从输入到输出重复画好8个入端到8个出端的三个全混加交换开关的拓扑结构图，每一级所用的交换开关均为4个。之后，沿各输入端的连线途径的各个交换单元的端子都标以同样的端号。最终，将这些端号与输出端端号相同者对应连在一起即可。 [解答]0-7号共8个处理器的三级混洗互连网络及其交换开关状态设置如图。采用终端地址标记寻径算法 。 2019/1/17

145 全混拓扑 全混拓扑 全混拓扑 1 1 A E I 4 2 1 1 4 2 2 3 B F J 2 3 5 6 3 出 端 入 端 2 1 4 4 5 4 5 C G K 6 3 5 3 5 6 6 7 6 7 D H L 7 7 7 级 2 1 N=8多级混洗交换网络 2019/1/17

146 例2.在16台PE的并行处理机上，要对存放在M个分体并行存贮器中的16×16二维数组实现行、列、主对角线、次对角线上各元素均无冲突访问，要求M至少为多少？此时数组在存贮器中应如何存放？写出其一般规则。证明这样存放，同时也可以无冲突访问该二维数组中任意4×4子数组的各个元素。 2019/1/17

147 [解答]16台PE的并行处理机，要同时对16×16的二维数组实现行、列、主对角线、次对角线上以及任意4×4子数组中的各元素同时进行访问又不发生冲突，只需将存贮器模块数M设成17即可。
由于17＝22×2＋1，让δ1取成22，δ2取成l。就是说，数组各元素在存贮器各模块中存放时，让同一行各相邻元素错开的体号距离为1，而同一列相邻行的二个相邻元素错开的体号距离为4。这样，任何4×4子数组中的16个元素肯定不会有两个以上的元素出现在同一个分体上，从而对各种子数组的元素也都可以实现无冲突的并行访问。 2019/1/17

148 解：N=8的立方体全排列多级网络可用三级立方体网络与其逆 网络串连，并去掉中间相同的一级，组成全排列网络。如下页图所示。
若采用单元控制，要求实现以上连接，各交换开关的一种工作状态如图所示。 2019/1/17

149 (011)0 (111)1 1 6 7 2 3 4 5 (100)2 (000)3 (010)4 (110)5 (101)6 (001)7 d0 d1 d2 d1 d0 N=8立方体全排列多级网络 2019/1/17

150 题14.具有N=2n个输入端的Omega网络，采用单元控制。 （1）N个输入总共可有多少种不同的排列；
2019/1/17

151 由于各交换开关是四种工作状态：直连、交换、上播和下播，建议采用终端地址标记寻径算法。
例3．画出8个处理单元组成的多级混洗交换网络结构图。指出输入端第5号处理单元与输出端第0、2、4、6单元相连，同时输入端第4号处理单元与输出端第1、3、5、7单元相连时，各交换开关所处的状态。 [答案与提示］： 多级混洗交换网络如下页图所示。N=8个处理机系统有3级交换开关，每级有4个，从输入端开依次为2、1、0级；有4级拓朴结构，从输入端开始依次为3、2、1、0级，0级为恒等，其它为混洗变换。 由于各交换开关是四种工作状态：直连、交换、上播和下播，建议采用终端地址标记寻径算法。 由图可知，第2级交换开关A、B处于上播，第1级4个交换开关均处于下播，第0级4个开关均处于交换状态。] 2019/1/17

152 A E I B F J C G K D H L 1 6 7 2 3 4 5 0(000) 1(001) 2(010) 3(011) 输入端
1 6 7 2 3 4 5 0(000) 1(001) A E I 2(010) 3(011) B F J 输入端 输出端 4(100) 5(101) C G K 6(110) 7(111) d2d1d0 D H L K2 　 K K0 N=8 多级混洗交换网络 2019/1/17