Title,PCA L5 Chp3.,*,Wu Spring 09 USTC,This is our 1st Level Bullet,This is our 2nd level bullet,This is our 3rd level bullet,This is our next 1st Level Bullet,This is our 2nd level bullet,This is our 3rd level bullet,Parallel C,omputer Architecture,并行计算机体系结构,Lecture 5,March 16,2009,Wu,junmin,(),Overview,Review of Lec4,间接互连网络,交换技术,Review of Lec4,性能提高（任务划分、分配、调度）,pcam,任务划分的方法,粒度与并发度,静态调度与动态调度,互连网络,系统互连,不同带宽与距离的互连技术,基本网络部件,链路,链路（,link),：传输信息的物理介质，也称为通道或电缆,不同的物理介质：双绞线,(STP),、同轴电缆、光纤,可用来连接两个,Switch,或主机与,Switch,长度,:,短链路在任一时刻仅包含一个逻辑信号；而长链路允许同时在链路上传输逻辑信号,宽度,:,一条窄链路只有一位信号线；一条宽链路有多位信号线。
时钟：一条链路常由同步或异步两种时钟机制驱动；同步时钟是指源和目的操作使用全局相同的时钟；异步时钟允许两端使用不同的时钟握手,网络性能指标（,1,）,通信时延：,从源节点到目的节点传输一条消息所需的总时间,在网络两端相应收发消息的软件开销,由于通道占用导致的通道时延（即总的消息长度除以通道带宽）,沿选路路径作一系列选路决策期间花费在后续交换开关上的选路时延,由于网络传输竞争导致的竞争时延,软件开销主要取决于主机内核，与竞争时延均依赖于程序行为,网络时延：通道时延和选路时延之和，完全由网络硬件特征决定，（通常,1,微秒左右）大大小于软件开销和竞争时延（几十或几百微秒）,网络性能指标（,2,）,每端口带宽：,从任意端口到另外端口每秒钟传输消息的最大位（或字节）数,如,IBM HPS,每端口带宽,40MB/s,聚集带宽：,从一半节点到另一半节点，每秒钟传输消息的最大位（或字节）数,如,IBM HPS,端口数最多为,512,，聚集带宽为,512*40/2=10.24GB/s,对剖宽度：将网络分成两个相等部分所必须移去的最少边数对剖带宽（,Bisection Bandwidth,）：,每秒钟内，在最小的对剖平面上通过所有连线的最大信息位（或字节）数。
等于对剖宽度与通道带宽之积静态互连网络 与动态互连网络,静态互连网络：又称为直接连接网络处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点的链接保持不变；典型的静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环等动态网络：又称为间接连接网络用交换开关构成的，可按应用程序的要求动态地改变连接组态；典型的动态网络包括总线、交叉开关和多级互连网络等静态网络性能指标,节点度（,Node Degree,）：射入或射出一个节点的边数在单向网络中，入射和出射边之和称为节点度网络直径（,Network Diameter,）：网络中任何两个节点之间的最长距离，即最大路径数如果从任一节点观看网络都一样，则称网络为对称的（,Symmetry,）,边连通度（,arc connectivity),：将网络分成两个不连通的部分所必须移去的边数代价（,cost,）：可以用总边数（链路数）来衡量静态互连网络拓扑,大多数都是正交拓扑,网络拓扑正交的充要条件是：节点可以在一个正交的,n,维空间内组织起来，每条链路的安排都要在一维中产生一个偏移量正交拓扑可以进一步分为严格正交和弱正交严格正交拓扑每个节点至少有一条链路通过每一维。
在弱正交中，某些节点在某些维上没有链路，因此不可能从任意节点穿过任意维，从给定的节点到结定的维首先要转移到其他维模型可用图,G(N,C),表示，其中顶点,N,代表处理节点的集合，边,C,代表通信信道的集合严格正交拓扑,路由简单，可以用硬件实现高效路由算法,在严格正交拓扑中，可以用节点在,n,维空间中的坐标作为节点的编号由于每条链路都遍历了一维，而且每一个节点在每一维上至少有一条链路，两个节点间的距离就可以用每一维的偏移量的和来计算给定链路上的偏移量仅仅影响相应维的偏移量由于从网络中的任意节点可以直接到达任意维，路由实现只需在某一维上选择绝对偏移量减小的链路就可以了各维的偏移量可以存储在报文头中，报文每次成功地经过中间节点时将会更新偏移量（增加或减少一个单位）,严格正交拓扑,n,维网格,最流行的直接网络是,n,维网格、,k,元,n,立方或环网和超立方它们都是严格正交的n,维网格有,K,0,xK,1,xK,n-2,xK,n-1,个节点，,K,i,是第,i,维的节点数，,K,i,2,且,0=,i,=n,一,1,每个节点,X,由,i,维坐标（,X,n-1,X,n-2,X,1,X,0,),定义，其中，对于,0=,X,i,=,K,i,-1,。
X,和,Y,两个节点相邻的充要条件是：存在,j,使得,y,j,=x,j,+1,或,x,j,-1,，而对其他的,0=,i,=n-1,，有,y,i,x,i,一个节点根据它们在网格中的位置，有,n,到,2n,个相邻节点，因此这种拓扑结构不是规整的严格正交拓扑,k,元,n,立方,在双向,k,元,n,立方中，所有节点的相邻节点数目相同k,元,n,立方与,n,维网格的定义有所区别，它所有的,k,i,都等于,k,，并且,X,和,Y,两个节点相邻的充要条件是：,存在,j,使得,y,j,=(x,j,+1,）,mod k,或,y,j,=(x,j,-1,）,mod k,，而对于其他任意,0=i2,，所有的节点都有,2n,个相邻节点当,n=1,时，,k,元,n,立方变成了具有,k,个节点的双向环严格正交拓扑,超立方,超立方是,n,维网格和,k,元,n,立方的特例超立方是一个,n,维网格，其中,ki,=2,且,0i=n,一,1,，,2,元,n,立方也叫做二进制,n,方其他直接互连网络,树形连接：,二叉树中除了根节点和叶节点之外，每个内节点只与其父节点和两个子节点相连，故称为三近邻连接节点度为,3,，对剖宽度为,1,，而树的直径为 ，,N,为树的总节点数。
如果尽量增大根节点度为,N-1,，其他所有节点都与它直接相连，则直径缩小为,2,，此时就变成了星形连接，其对剖宽度为 ，从某种意义上讲类似于基于总线的网络树的主要问题是根易成为通信瓶颈1985,年,Leiserson,提出的胖树（,Fat Tree,）可缓解此问题胖树节点间的通路自叶向根逐渐变宽，它更像真实的树，连向根部的枝叉变得愈来愈粗Overview,Review of Lec4,间接互连网络,交换技术,动态互连网络特性,动态互联网络没有提供节点间的直接连接，任何两个节点间的通信必须通过某些交换机进行每个节点都有一个网络适配器连接在网络开关上每个开关都有一组端口，每个端口包括一条输入和一条输出链路每个开关的端口或连接到处理器，或者悬空，或者连接到其他开关的端口上，以实现处理器间的连接这些开关的互连方式决定了不同的网络拓扑间接网络的模型也可以用图,G(N,C),表示，其中,N,是开关的集合，,C,是开关之间的单向或双向链路集合从一个节点向另一个节点发送消息时，需要经过源节点和它连接的开关之间的链路及传输路径中最后一个开关和目的节点之间的链路因此两个节点间的距离要在直接连接两个节点的开关之间的距离上再加上两个单位。
类似地，网络直径等于连接到节点的开关之间的最大距离加上两个单位动态互联网络类型,与直接网络相似，间接网络的主要属性由三个要素来描述：拓扑、路由和交换拓扑定义了开关是如何通过通道互连的，可以图建模对于具有,N,个节点的网络，理想环境是使用一个,NxN,的开关连接它们，这种开关就是交叉开关使用一个,NxN,的交叉开关比使用全连接的直接网络拓扑（有,N,个路由器，每个路由器都有一个,NxN,内部交叉开关）便宜，但是交叉开关的成本仍然限制了它在大型网络中的使用于是，又提出其他的拓扑结构在这些拓扑中，消息到达目的节点之前要经过多个开关规整网络中的开关通常都是相同的，传统上采用多级结构除了输人输出级以外，每一级使用规整连接与前一级和下一级相连输人输出级既连接节点，又连接了网络中的其他级，这种网络称作多级互连网络交叉开关,交叉开关（,Crossbar,）网络是单级交换网络，可为每个端口提供更高的带宽象电话交换机一样，交叉点开关可由程序控制动态设置其处于“开”或“关”状态，而能提供所有（源、目的）对之间的动态连接在并行处理中，交叉开关一般有两种使用方式：一种是用于对称的多处理机或多计算机机群中的处理器间的通信；另一种是用于,SMP,服务器或向量超级计算机中处理器和存储器之间的存取。
交叉开关点的状态,a,中该行输入允许访问相应的输出，而从上面发出的对同一输出的访问被阻塞b,中上面发出的输入允许访问输出，通过开关点的行输入不请求同一输出并可以传向其他开关c,中从上面发出的输入允许访问输出，但是通过开关点的行输入也请求同一输出，被阻塞d,中状态只用于要求交叉开关支持多播的情形交叉开关应用,千兆开关,/FDDI:,一种用于构造,Alpha,工作站和服务器互连的交叉开关，带宽,3.6Gbps,Sun,Microsystem,公司在它们的,Ultra Enterprise l0000,（,StarFire,）,SMP,服务器中，将,Gigaplane,总线升级成,Gigaplane,-XB,互连,交叉开关应用,处理器和存储器间的交叉开关：,交叉开关代替处理器和存储器间的连接总线,提供了多个处理器模块并行存取存储器的可能性,每个时刻每个存储器模块只能由一个处理器进行访问,交叉开关特性,交叉开关具有良好的带宽特性,Non-Blocking:,两个节点之间的通信，不会阻塞其他节点之间的通信代价不可扩放，,O(P,2,),多级互连网络,交换开关模块,一个交换开关模块有,a,个输入和,b,个输出，每个输入可连接到任意输出端口，但只允许一对一或一对多的映射，不允许多对一的映射，因为这将发生输出冲突,第,i,级开关,Gi,，有,w,i,个,a,i,j,*,b,i,j,开关，,Gi,级共有,pi,个输入和,qi,个输出。
通常实现中所有开关都是相同的级间互连（,Interstage,Connection,）：定义了每一级输入与上一级输出之间连接方式,如果网络具有,N=,k,n,个端口，令,X=x,n-1,x,n-2,x,1,x,0,表示任意一个端口号，其中,0=X,i,=k-1,，如,k=2,Generalized MIN Arch,典型的级间互联模式,完全混洗排列,:C(x,n-1,x,n-2,x,1,x,0,)=x,n-2,x,1,x,0,x,n-1,把,X,中的数循环左移一位（图,a),逆完全混洗正好相反,(,图,b,）,典型的级间互联模式,数字反转排列,:C(x,n-1,x,n-2,x,1,x,0,)=x,0,x,1,x,n-2,x,n-1,通常称为位反转排列（图,c,所示）,典型的级间互连,蝶形连接,:,Ci(x,n-1,x,i+1,x,i,x,i-1,x,1,x,0,)=x,n-1,x,i+1,x,0,x,i-1,x,1,x,i,第,i,个蝶形排列交换索引中的第,0,和第,i,个数,典型的级间互连,立方体排列,:,Ci(x,n-1,x,i+1,x,i,x,i-1,x,1,x,0,)=x,n-1,x,i+1,x,i,x,i-1,x,0,第,i,个立方体排列将索引中的第,i,位求反,典。
