第六章 重叠、流水和向量处理机1.ppt

2 SIMD计算机的互连网络n互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用于实现计算机系统内部多个处理机或多个功能部件之间的相互连接。n在SIMD计算机中，处理单元与处理单元或存储分体之间要通过互连网络进行信息交换。互连网络的作用n用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接。n互连网络已成为并行处理系统的核心组成部分。n互连网络对整个计算机系统的性能价格比有着决定性的影响。磁盘SM1SM2SMmIPMNCnPnLMC1P1LMIPCNPION磁带打印机终端网络(共享存储器)(共享I/O与外设)具有本地存储器、私有高速缓存、共享存储器和共享外围设备的一般处理机系统的互连结构互连网络的特性n互连网络通常是用有向边或无向边连接有限个结点的组成n互连网络的主要特性有：n网络规模：网络中结点的个数n结点度：与结点相连接的边数称为结点度。包括入度和出度。进入结点的边数叫入度，从结点出来的边数则叫出度n距离：两个结点之间相连的最少边数n网络直径：网络中任意两个结点间距离的最大值。用结点间的连接边数表示n结点间的线长：两个结点间连线的长度。用米、公里等表示n对称性：从任何结点看到拓扑结构都是一样的网络称为对称网络。对称网络比较易实现，编程也较容易。互连网络在传输方面的主要性能参数n频带宽度(Bandwidth)：互连网络传输信息的最大速率。n传输时间(Transmission time)：等于消息长度除以频宽。n飞行时间(Time of flight)：第一位信息到达接收方所花费的时间。n传输时延(Transport latency)：等于飞行时间与传输时间之和。n发送方开销(Sender overhead)：处理器把消息放到互连网络的时间。n 接收方开销(Receiver overhead)：处理器把消息从网络取出来的时间。n一个消息的总时延可以用下面公式表示： 总时延发送方开销飞行时间消息长度/频宽接收方开销例7.1：假设一个网络的频宽为10Mb/S，发送方开销为230us，接收方开销为270us。如果两台机器相距100米，现在要发送一个1000字节的消息给另一台机器，试计算总时延。如果两台机器相距1000公里，那么总时延为多大？n解：光的速度为299792.5KM/S，信号在导体中传递速度大约是光速的50，相距100米时总时延为：n相距1000公里时的总时延为：sssssssKmKmsT130127080067. 0230270/1081000/5 .2997925 . 01 . 0230秒兆位位接收方开销频宽消息长度飞行时间发送方开销sssssssssT7971= 2708006671230= 27010810005 .2997925 . 01010002306目录n互连网络的设计目标及互连函数n互连网络应抉择的几个问题n基本的单级互连网络n基本的多级互连网络n全排列网络互连网络的设计目标 n结构不要复杂，降低成本； n互连灵活，满足算法和应用的需要；n处理单元间信息交换所需最大传送步数要尽量少，提高速度；n互连网络采用规整单一的基本构件组成；模块化，可扩充性；n互连网络的标准化互连网络应抉择的几个问题n操作方式n控制策略n交换方法n网络的拓扑结构互连网络的分类n操作方式：同步、异步、同步异步 n阵列处理机采用同步方式n多处理机采用异步、同步异步组合方式n控制方式：集中、分布n多数采用集中互连网络的分类（续）n交换方法：线路交换、包交换、线路交换/包交换n线路交换，建立实际通路，适合大批量数据传输，常采用。n包交换，建立虚电路，适合于短数据传送，常用于多处理机系统和计算机网络n网络上通常采用分组交换线路交换：无冲突，独享，资源浪费报文（包）交换：有冲突，有缓冲，路由Stored and Forward（存储转发）BufferBufferBuffer分组交换：有冲突，有缓冲，分片，路由Stored and Forward（存储转发）BufferBufferBuffer互连网络的分类（续）n拓扑结构：互连网络入、出端可以实现连接的模式。n静态：连接固定。灵活性、适应性差。少使用。n一维线形n二维环形、星形、树形、胖树形、网格形、脉动阵列形n三维旋环形、立方体形、环立方体n动态环形网n采用移数函数。使用不同的移数函数，可以构成多种环形网。n单向环行网：右环网，采用PM2+0函数。左环网，采用PM2-0函数。n双向环行网：又称为一维邻居网，采用PM2+0，PM2-0函数。n环行网是对称的，结点度是常数2。双向环网的直径为N/2，单向环形网的直径是Nn如果将结点度由2提高至3，可得到弦环网。增加的弦愈多，则结点度愈高，网络直径愈小。10234576循环移数网10234576度为3的弦环网10234576环形网树形和星形网n一棵k层二叉树有N2k1个结点，结点度是3，直径是2(k-1)。n星形是一种特殊的2层树，结点度很高，为d=N-1，直径是2。n二叉胖树的结点度从叶子结点往根结点逐渐增加。胖树缓解了一般二叉树根结点通信速度高的矛盾。二叉树网二叉胖树网星形网网格形网n是一种比较流行的网络结构，有各种变体形式。在Illiac IV、MPP、DAP、CM-2和Inetl Paragon中得到了实现。n一般网格网，Nnk 结点的k维网格的结点度为2k，直径为k(n-1)。n环网形网格网沿阵列每行每列都有环形连接。一个nn二元环网的结点度为4。环网是一种对称的拓扑结构。nIlliac IV的88 Illiac网格，其结点度为4，直径为7。一个nn Illiac 网格的直径为d=n-1，为纯网格直径的一半互连网络的分类（续）n动态网络：n单级：只有有限几种连接，循环网络。n多级：多个单级网络串联组合而成。n多级互连网络与循环互连网络相比n前者增加设备与成本，缩短通过时间、提高速度n前者利用单级网络组合，灵活性好n常采用多级互连网络和多级循环互连网络n静态互连网络：连接通路是固定的，一般静态互连网络不能实现任意结点到结点之间的互连。n循环互连网络：通过多次重复使用同一个单级互连网络以实现任意结点到结点之间的互连。n多级互连网络：将多套相同的单级互连网络连接起来，实现任意结点到结点之间的互连。n全排列互连网络：不仅能够实现任意结点到结点之间的互连，而且能够同时实现任意结点到结点之间的互连n全交叉开关网络：除了能够同时实现任意结点到结点之间的互连之外，还能够实现广播和多播。 互联函数的表示方式n互连函数表示 n例：N=8,n=3 (000),(001),(010),(011), , ,()(), , ,()(.2*2*), , ,(log0211032022110212bbbjfbbbbjfbbbbbbjNnNnnnnnnnnnnn例如：为节点数，设互联函数的表示方式（续）n循环表示 n例：N=8 (0,1,2,3,4,5,6,7)012110110)(,)(, , ,)(,)(), , ,( : )(jjfjjfjjfjjfjjjjjfxxxxx基本的单级互连网络n立方体单级网络nPM2I单级网络n换洗交换单级网络n蝶性单级网络立方体单级网络 n共有 个互连函数；n最大距离为n；n任意两个节点之间至少有n条不同的路径，容错性强；nn3超立方体（Hyper-Cube） 011011, , , , ,), , , , ,(,ppppppppCubeiCubeininii位互为反码。第互连函数：Nn2logYXZ011000010110111101100001011010110111101100001Cube1011010110111101100001Cube0011010110111101100001Cube2PM2I单级网络 n共有2n个互连函数： PM2+i(j)=j+2i mod N PM2-i(j)=j-2i mod Nn说明n普遍有： PM2+(n-1)(j) = PM2-(n-1)(j) n最大距离为 / 2nPM2I单级网络（续）n当N=8时，有n=log2N,2n=6个互联函数 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) PM2-2: (4 0)(5 1)(6 2)(7 3)PM2I单级网络（续）12345670PM2+0PM2-01234567012345670PM2-1PM2+1PM2-2PM2+2混洗交换单级网络 n包含两个函数：混洗、交换 shuffle(pn-1 pn-2, p1 p0)= pn-2, p1 p0 pn-1 n说明： n不是可逆函数n特性：作n次后，恢复到原来-多次混洗后，每个处理器都会遇到与其他处理器连接的机会（除全0和全1）；n增加交换函数，得到全混交换单级网络；n全混连接与立方体连接存在对应关系,此性质便于构成多级连接，并与立方体具有相似的关系；n最大距离为2n-1 76543210765432100000010100111001011101110000010100111001011101117654321076543210000001010011100101110111000001010011100101110111一次混洗二次混洗N=8时全混交换互连网络连接图12345670蝶形单级网络n互连函数 Butterfly(pn-1 pn-2, p1 p0)= p0 pn-2, p1 pn-1 n即将二进制的最高位和最低位相互交换位置。000001010011100101110111000001010011100101110111012345677654321076543210总结n单级互连网络特性n任一单级互连网络均可表示成N入、N出的过程。n任一单级互连网络可实现部分结点(一对或几对)间的连接，不能实现任意多对结点间的同时连接。n单级互连网络含义：某些连接方法或拓扑结构。n单级互连网络应用n利用单级互连网络的特性作为实际IN的拓扑结构；n通过交换开关作为IN的可变因素；n通过交换开关多次控制实现IN的结点间任意互连。基本多级互联网络 n能够实现结点到结点之间的任意互连是互连网络的一种基本功能。n多级互连网络采用多个相同的或不同的互连网络直接连接起来。属于组合逻辑线路，一个时钟周期就能够实现任意结点到结点之间的互连。n多级互连网络采用的关键技术：n交换开关n交换开关之间的拓扑连接n对交换开关的不同控制方式交换开关n一个ab交换开关有a个输入和b个输出。n最常用的二元开关：a=b=2。n每个输入可与一个或多个输出相连，但是在输出端必须避免发生冲突。一对一和一对多映射是容许的；但不容许有多对一映射。n只容许一对一映射时称为置换连接，称这种开关为nn交叉开关。n具有直通和交换两种功能的交换开关称为二功能开关，或交换开关。用一位控制信号控制。n具有所有四种功能的交换开关称为四功能开关，用两位控制信号控制。直连交换上播下播模块大小合法状态交换连接22424425624881677721640320nnnnn!交换开关和合法状态拓扑结构n前一级交换开关的输出端与后一级交换开关的输入端之间的连接模式称为拓扑结构。n通常采用前面介绍的互连函数实现拓扑结构n实际上，从结点的输出到第一级交换开关的输入，以及从最后一级交换开关的输出到结点的输入也可以采用拓扑结构连接。控制方式n在多级互连网络中有多级交换开关，每一级又有多个交换开关。n通常有三种控制方式n级控制：同一级交换开关使用同一个控制信号控制。n单元级控制：每个交换开关分别控制。n部分级控制：例如，第i级使用i+1个控制信号控制 (0 i n-1)。n同一个多级互连网络分别常用三种不同的控制方式，可以构成三种不同的互连网络。基本多级互连网络n多级立方网络(Single Stored Cube Network) n多级换洗交换网络n多级PM2I网络(Plus-minus 2i)n基准网络n多级交叉开关网络n多级碟式网络多级立方体网络n采用二功能开关。n采用交换函数构成拓扑结构，各级分别采用E0、E1、En-1交换函数。n当所有开关都直通时，实现恒等变换。n当A、B、C、D四个开关交换，其余直通时实现 E0 互连函数。n当E、F、G、H四个开关交换，其余直通时实现 E1 互连函数。n当I、J、K、L四个开关交换，其余直通时实现 E2 互连函数。多级立方体网络（续）n第I级交换单元处于交换状态时，实现的是Cubei互连函数。n采用三种不同的控制方式，可以构成三种不同的互连网络。n采用级控制可以构成STARAN交换网。n采用部分级控制，可以构成STARAN移数网。n采用单元控制可以构成间接二进制n方体网。ABCDEFGHIJKL0123456701234567k = 0k = 1k = 2交换功能级控制信号（k2k1k0）000001010011100101110111入 端001234567110325476223016745332107654445670123554761032667452301776543210功能iCube0Cube1Cube0+Cube1Cube2Cube0+Cube2Cube1+Cube2Cube0+Cube1+Cube2移位功能2级K,L0010000J0110000I11100001级F,H0100100E,G11011000级A,B,C,D1001010功 能移1Mod 8移2Mod 8移4Mod 8移1Mod 4移2Mod 4移1Mod 2不移衡等多级混洗交换网络n又称omega网络n交换开关：四功能（允许实现一对多的连接）n拓扑结构：不同级相同，均为全混洗结构；n控制方式：级控制、部分级控制、单元控制n连接图：第n-1级靠近入端；ABCDEFGHIJKL0123456701234567级210输入多级PM2I网络(Plus-minus 2i)n包含n级单元间连接，每一级都是把前后两列各N=2n个单元按PM2I拓扑相互连接起来。n可转化为强化数据交换网络（Augmented Data Manipulator）n控制线多，成本较高基准网络n与二进制立方体网络的逆网络相似n采用单元控制n作为中间介质，模拟一种网络的拓扑和功能多级交叉开关网络n非阻塞式网络多级蝶式网络n蝶式网络的开关不允许广播功能，它实际上是Omega网的一个子集。n两级64 64的蝶式网络如下图所示：它采用16个8 8交叉开关构成，两级间采用8路洗牌连接。两级64 64的蝶式网络8888880.7888888第1级第0级8.1556.63.078155663.多级网络比较n灵活性(低高)： STARAN、间接二进制n方体、 Omega()、ADM(混洗四功能)n成本(低高)：同上n用途： STARAN、Omega PEM 间接二进制n方体 PEPEn功能：只能实现同时部分多对多功能。全排列网络n定义：所有入端、出端的连接均不发生冲突的网络，又称非阻塞型网络，即：N入N出有N！种排列。n互连网络要求：全排列网络(非阻塞型网络)。n非阻塞型网络（Non-Blocking Network）n灵活性好，连线多，控制复杂，成本高nSTARAN等网络属于阻塞型网络。n阻塞型网络（Blocking Network）：同时实现两对或多对入端与出端之间连接时，都有可能因争用数据传送路径而发生冲突。