计算机体系结构(张晨曦)第7章-PPT

第7章互连网络7.1互连网络的基本概念7.2互连网络的结构1.互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统中结点之间的相互连接。结点：处理器、存储模块或其他设备。互连网络在系统中的位置，如图所示。在拓扑上，互连网络为输入结点到输出结点之间的一组互连或映象。7.1互连网络的基本概念7.1.1互连网络的功能和特性7.1互连网络的基本概念互连网络结点链路结点链路结点链路……互连网络在系统中的位置7.1互连网络的基本概念2.可以从4个不同的方面来描述互连网络定时方式：有同步和异步两种。同步系统：使用一个统一的时钟。SIMD阵列处理机就属于这一种类型。异步系统：没有统一的时钟，系统中的各个处理机都是独立地工作。交换方法：有线路交换和分组交换两种。线路交换：源结点和目的结点之间的物理通路在整个数据传送期间一直保持连接。分组交换：把信息分割成许多组（又称为包），将它们分别送入互连网络。7.1互连网络的基本概念这些数据包可以通过不同的路径传送，到达目的结点后再拼合成原来的数据。结点之间不存在固定连接的物理通路。控制策略：有集中式和分散式两种集中控制方式：有一个全局的控制器接收所有的通信请求，并由它设置互连网络的开关连接。分散控制方式：不存在全局的控制器，通信请求的处理和开关的设置由互连网络分散地进行。7.1互连网络的基本概念拓扑结构：有静态和动态两种。静态拓扑结构：在各结点之间有专用的连接通路，且在运行过程中不能改变。动态拓扑结构：可根据需要设置互连网络中的开关，从而对结点之间的连接通路进行重新组合，实现所要求的通信模式。7.1互连网络的基本概念变量x：输入（设x=0，1，…，N－1）函数f(x)：输出通过数学表达式建立输入端与输出端的一一对应关系。即在互连函数f的作用下，输入端x连接到输出端f(x)。互连函数反映了网络输入数组和输出数组之间对应的置换关系或排列关系。（有时也称为置换函数或排列函数）7.1.2互连函数7.1互连网络的基本概念互连函数f(x)有时可以采用循环表示即：（x0x1x2…xj-1）表示：f(x0)=x1，f(x1)=x2，…，f(xj-1)=x0j称为该循环的长度。几种常用的基本互连函数及其主要特征：1.交换函数交换函数：实现二进制地址编码中第k位互反的输入端与输出端之间的连接。011121011121xxxxxxxxxxxxxxEkkknnkkknn7.1互连网络的基本概念主要用于构造立方体互连网络和各种超立方体互连网络。它共有n＝log2N种互连函数。（N为结点个数）当N＝8时，n＝3，可得到常用的立方体互连函数：012012201201210120120xxxxxxCxxxxxxCxxxxxxC7.1互连网络的基本概念变换图形0123456701234567(a)C0交换函数01234567012345670123456701234567(b)C1交换函数(c)C2交换函数N=8的立方体交换函数7.1互连网络的基本概念立方体网络7.1互连网络的基本概念2.均匀洗牌函数均匀洗牌函数：将输入端分成数目相等的两半，前一半和后一半按类似均匀混洗扑克牌的方式交叉地连接到输出端（输出端相当于混洗的结果）。函数关系即把输入端的二进制编号循环左移一位。101320121nnnnnxxxxxxxxxS7.1互连网络的基本概念N=8的均匀洗牌和逆均匀洗牌函数0123456701234567(a)均匀洗牌函数0123456701234567(b)逆均匀洗牌函数N=8的均匀洗牌和逆均匀洗牌函数7.1互连网络的基本概念逆均匀洗牌函数：将输入端的二进制编号循环右移一位而得到所连接的输出端编号。互连函数逆均匀洗牌是均匀洗牌的逆函数3.碟式函数蝶式互连函数：把输入端的二进制编号的最高位与最低位互换位置，便得到了输出端的编号。121001211xxxxxxxxSnnnn11200121nnnnxxxxxxxxB7.1互连网络的基本概念4.反位序函数反位序函数：将输入端二进制编号的位序颠倒过来求得相应输出端的编号。互连函数对于N＝8的情况，B(x)函数等于R(x)函数。12100121nnnnxxxxxxxxR7.1互连网络的基本概念N＝8的蝶式函数的变换图形0123456701234567(a)碟式函数(b)反位序函数0123456701234567N=8的碟式函数和反位序函数7.1互连网络的基本概念5.PM2I函数PM2I函数：一种移数函数，它是将各输入端都循环移动一定的位置连到输出端。互连函数PM2+i(x)＝x＋2imodNPM2-i(x)＝x－2imodN其中：0≤x≤N－1，0≤i≤n－1，n＝log2N，N为结点数。PM2I互连网络共有2n个互连函数。7.1互连网络的基本概念当N＝8时，有6个PM2I函数：PM2+0：（01234567）PM2-0：（76543210）PM2+1：（0246）（1357）PM2-1：（6420）（7531）PM2±2：（04）（15）（26）（37）7.1互连网络的基本概念N=8的PM2I函数0123456701234567(a)PM2+00123456701234567(b)PM2+10123456701234567(c)PM2+2阵列计算机ILLIACⅣ采用PM2±0和PM2±n/2构成其互连网络，实现各处理单元之间的上下左右互连。0123456789101112131415用移数函数构成ILLIACⅣ阵列机的互连网络7.1互连网络的基本概念1.网络通常是用有向边或无向边连接有限个结点的图来表示。2.互连网络的主要特性参数有：网络规模：网络中结点的个数。表示该网络所能连接的部件的数量。结点度：与结点相连接的边数（通道数），包括入度和出度。进入结点的边数称为入度。从结点出来的边数称为出度。7.1.3互连网络的特性参数7.1互连网络的基本概念距离：对于网络中的任意两个结点，从一个结点出发到另一个结点终止所需要跨越的边数的最小值。网络直径：网络中任意两个结点之间距离的最大值。网络直径应当尽可能地小。结点之间的线长：两个结点之间连线的长度，用米、千米等表示。等分宽度：当某一网络被切成相等的两半时，沿切口的边数（通道数）的最小值称为通道等分宽度，用b表示。7.1互连网络的基本概念线等分宽度：B＝b×w其中：w为通道宽度（用位表示）。该参数主要反映了网络最大流量。对称性：从任何结点看到的拓扑结构都是相同的网络称为对称网络。对称网络比较容易实现，编程也比较容易。互连网络通常可以分为两大类：静态互连网络各结点之间有固定的连接通路且在运行中不能改变的网络。动态互连网络由交换开关构成、可按运行程序的要求动态地改变连接状态的网络。下面介绍几种静态互连网络。（其中：N表示结点的个数）7.2互连网络的结构7.2.1静态互连网络7.2互连网络的结构1.线性阵列一种一维的线性网络，其中N个结点用N-1个链路连成一行。端结点的度：1其余结点的度：2直径：N－1等分宽度b=17.2互连网络的结构7.2互连网络的结构对称结点的度：2双向环的直径：N/2单向环的直径：N2.环和带弦环环用一条附加链路将线性阵列的两个端点连接起来而构成。可以单向工作，也可以双向工作。7.2互连网络的结构带弦环增加的链路愈多，结点度愈高，网络直径就愈小。7.2互连网络的结构全连接网络结点度：15直径最短，为1。3.循环移数网络通过在环上每个结点到所有与其距离为2的整数幂的结点之间都增加一条附加链而构成。N=16结点度：7直径：27.2互连网络的结构一般地，如果｜j-i｜=2r（r=0,1,2,…,n-1，n=log2N），则结点i与结点j连接。结点度：2n－1直径：n/27.2互连网络的结构4.树形和星形一棵5层31个结点的二叉树一般说来，一棵k层完全平衡的二叉树有N=2k-1个结点。最大结点度：3直径：2(k-1)星形结点度较高，为N－1。直径较小，是一常数2。可靠性比较差，只要中心结点出故障，整个系统就会瘫痪。7.2互连网络的结构7.2互连网络的结构5.胖树形7.2互连网络的结构6.网格形和环网形网格形一个3×3的网格形网络一般来说，N=nk个结点的k维网络的内部结点度是2k，网络直径为k(n-1)。环形网可看作是直径更短的另一种网格。将环形和网格形组合在一起，并能向高维扩展。沿阵列的每行和每列都有环形连接。一个n×n二元环网结点度：4直径：2×n/27.2互连网络的结构7.2互连网络的结构7.超立方体一种二元n维立方体结构一般来说，一个二元n维立方体由N=2n个结点组成，它们分布在n维上，每维有两个结点。例8个结点的3维立方体4维立方体为实现一个n维立方体，只要把两个（n－1）维立方体中相对应的结点用链路连接起来即可。共需要2n-1条链路。n维立方体中结点的度都是n，直径也是n。7.2互连网络的结构静态互连网络一览表网络类型结点度d网络直径D链路数l等分宽度B对称性网络规格说明线线阵列2N-1N-11非N个结点环形2[N/2]N2是N个结点全连接N-11N(N-1)/2(N/2)2是N个结点二叉树32(h-1)N-11非树高h=[log2N]星形N-12N-1[N/2]非N个结点2D网格42(r-1)2N-2rr非r×r网格，Illiac网4r-12N2r非与的带弦环等效2D环网42[r/2]2N2r是r×r网格，超立方体nnnN/2N/2是N个结点n=[log2N]CCC32k-1+[k/2]3N/2N/(2k)是N=k×2k结点环长k≥3NrNrNr7.2互连网络的结构1.总线一组导线和插座，用于进行与总线相连的处理机、存储模块和外围设备等之间的数据传送。每一次总线只能用于一个源（主部件）到一个或多个目的（从部件）之间的数据传送。多个功能模块之间的争用总线或时分总线。特点价格低带宽较窄7.2.2动态互连网络7.2互连网络的结构一种由总线连接的多处理机系统7.2互连网络的结构2.多级互连网络MIMD和SIMD计算机都使用多级互连网络MIN（MultistageInterconnectionNetwork）一种通用的多级互连网络由a×b开关模块和级间连接构成的通用多级互连网络结构每一级都用了多个a×b开关a个输入和b个输出在理论上，a和b不一定相等，然而实际上a和b经常选为2的整数幂，即a＝b＝2k，k≥1。相邻各级开关之间都有固定的级间连接7.2互连网络的结构7.2互连网络的结构几种常用的开关模块模块大小合法状态置换连接2×2424×4256248×81677721640320n×nnnn!7.2互连网络的结构最简单的开关模块：2×2开关2×2开关的4种连接方式7.2互连网络的结构各种多级互连网络的区别在于所用开关模块、控制方式和级间互连模式的不同。控制方式：对各个开关模块进行控制的方式。级控制：每一级的所有开关只用一个控制信号控制，只能同时处于同一种状态；单元控制：每一个开关都有一个独立的控制信号，可各自处于不同的状态；部分级控制：第i级的所有开关分别用i＋1个信号控制，0≤i≤n－1，n为级数。常用的级间互连模式：均匀洗牌、蝶式、多路洗牌、纵横交叉、立方体连接等7.2互连网络的结构两种多级互连网络Omega网络00000421112214256333442146355566356777778×8的Omega网络7.2互连网络的结构一个N输入的Omega网络有log2N级，每级用N/2个2×2开关模块，共需要Nlog2N/2个开关。每个开关模块均采用单元控制方式。不同的开关状态组合可实现各种置换、广播或从输入到输出