并行计算机体系结构.ppt

1、Parallel Computer Architecture并行计算机体系结构Lecture 5,March 16, 2009 Wu junmin (),Overview,Review of Lec4 间接互连网络 交换技术,Review of Lec4,性能提高（任务划分、分配、调度） pcam 任务划分的方法 粒度与并发度 静态调度与动态调度 互连网络,系统互连,不同带宽与距离的互连技术,基本网络部件链路,链路（link)：传输信息的物理介质，也称为通道或电缆 不同的物理介质：双绞线(STP)、同轴电缆、光纤 可用来连接两个Switch或主机与Switch 长度: 短链路在任一时刻仅包含一

2、个逻辑信号；而长链路允许同时在链路上传输逻辑信号 宽度: 一条窄链路只有一位信号线；一条宽链路有多位信号线。 时钟：一条链路常由同步或异步两种时钟机制驱动；同步时钟是指源和目的操作使用全局相同的时钟；异步时钟允许两端使用不同的时钟握手,网络性能指标（1）,通信时延：从源节点到目的节点传输一条消息所需的总时间 在网络两端相应收发消息的软件开销 由于通道占用导致的通道时延（即总的消息长度除以通道带宽） 沿选路路径作一系列选路决策期间花费在后续交换开关上的选路时延 由于网络传输竞争导致的竞争时延 软件开销主要取决于主机内核，与竞争时延均依赖于程序行为 网络时延 ：通道时延和选路时延之和 ，完全由网络

3、硬件特征决定，（通常1微秒左右）大大小于软件开销和竞争时延（几十或几百微秒）,网络性能指标（2）,每端口带宽 ：从任意端口到另外端口每秒钟传输消息的最大位（或字节）数 如IBM HPS 每端口带宽40MB/s 聚集带宽 ：从一半节点到另一半节点，每秒钟传输消息的最大位（或字节）数 如IBM HPS端口数最多为512 ，聚集带宽为512*40/2 = 10.24GB/s 对剖宽度：将网络分成两个相等部分所必须移去的最少边数。 对剖带宽（Bisection Bandwidth） ：每秒钟内，在最小的对剖平面上通过所有连线的最大信息位（或字节）数。等于对剖宽度与通道带宽之积。,静态互连网络 与动态互

4、连网络,静态互连网络：又称为直接连接网络。处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点的链接保持不变；典型的静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环等。 动态网络：又称为间接连接网络。用交换开关构成的，可按应用程序的要求动态地改变连接组态；典型的动态网络包括总线、交叉开关和多级互连网络等。,静态网络性能指标,节点度（Node Degree）：射入或射出一个节点的边数。在单向网络中，入射和出射边之和称为节点度。 网络直径（Network Diameter）： 网络中任何两个节点之间的最长距离，即最大路径数。 如果从任一节点观看网络都一样，则称网络为对称的（Sy

5、mmetry） 边连通度（arc connectivity)：将网络分成两个不连通的部分所必须移去的边数。 代价（cost）：可以用总边数（链路数）来衡量。,静态互连网络拓扑,大多数都是正交拓扑 网络拓扑正交的充要条件是：节点可以在一个正交的n维空间内组织起来，每条链路的安排都要在一维中产生一个偏移量。 正交拓扑可以进一步分为严格正交和弱正交。 严格正交拓扑每个节点至少有一条链路通过每一维。 在弱正交中，某些节点在某些维上没有链路，因此不可能从任意节点穿过任意维，从给定的节点到结定的维首先要转移到其他维。 模型可用图G(N,C)表示，其中顶点N代表处理节点的集合，边C代表通信信道的集合。,严格

6、正交拓扑,路由简单，可以用硬件实现高效路由算法 在严格正交拓扑中，可以用节点在n维空间中的坐标作为节点的编号。 由于每条链路都遍历了一维，而且每一个节点在每一维上至少有一条链路，两个节点间的距离就可以用每一维的偏移量的和来计算。 给定链路上的偏移量仅仅影响相应维的偏移量。由于从网络中的任意节点可以直接到达任意维，路由实现只需在某一维上选择绝对偏移量减小的链路就可以了。 各维的偏移量可以存储在报文头中，报文每次成功地经过中间节点时将会更新偏移量（增加或减少一个单位）,严格正交拓扑n维网格,最流行的直接网络是n维网格、k元n立方或环网和超立方。它们都是严格正交的。 n维网格有K0 xK1xKn-2

7、xKn-1个节点，Ki是第i维的节点数，Ki2且0=i=n一1。每个节点X由i维坐标（Xn-1,Xn-2,X1,X0) 定义，其中，对于0=Xi= Ki -1。 X和 Y两个节点相邻的充要条件是：存在j使得yj=xj+1或xj-1，而对其他的0=i=n-1，有yixi。 一个节点根据它们在网格中的位置，有n到2n个相邻节点，因此这种拓扑结构不是规整的。,严格正交拓扑k元n立方,在双向 k元n立方中，所有节点的相邻节点数目相同。 k元n立方与 n维网格的定义有所区别，它所有的ki都等于k，并且X和Y两个节点相邻的充要条件是： 存在j使得yj= (xj+1）mod k 或 yj= (xj-1）mo

8、d k ，而对于其他任意 0=2，所有的节点都有2n个相邻节点。 当n=1时，k元n立方变成了具有k个节点的双向环。,严格正交拓扑超立方,超立方是n维网格和k元n立方的特例。 超立方是一个n维网格，其中ki=2且0i=n一1，2元n立方也叫做二进制n方。,其他直接互连网络,树形连接： 二叉树中除了根节点和叶节点之外，每个内节点只与其父节点和两个子节点相连，故称为三近邻连接。 节点度为3，对剖宽度为1，而树的直径为 ，N为树的总节点数。 如果尽量增大根节点度为N-1，其他所有节点都与它直接相连，则直径缩小为2，此时就变成了星形连接，其对剖宽度为 ，从某种意义上讲类似于基于总线的网络。 树的主要问

9、题是根易成为通信瓶颈。1985年Leiserson提出的胖树（Fat Tree）可缓解此问题。胖树节点间的通路自叶向根逐渐变宽，它更像真实的树，连向根部的枝叉变得愈来愈粗。,Overview,Review of Lec4 间接互连网络 交换技术,动态互连网络特性,动态互联网络没有提供节点间的直接连接，任何两个节点间的通信必须通过某些交换机进行。 每个节点都有一个网络适配器连接在网络开关上。 每个开关都有一组端口，每个端口包括一条输入和一条输出链路。每个开关的端口或连接到处理器，或者悬空，或者连接到其他开关的端口上，以实现处理器间的连接。这些开关的互连方式决定了不同的网络拓扑。 间接网络的模型也

10、可以用图G(N,C)表示，其中N是开关的集合，C是开关之间的单向或双向链路集合。 从一个节点向另一个节点发送消息时，需要经过源节点和它连接的开关之间的链路及传输路径中最后一个开关和目的节点之间的链路。因此两个节点间的距离要在直接连接两个节点的开关之间的距离上再加上两个单位。类似地，网络直径等于连接到节点的开关之间的最大距离加上两个单位。,动态互联网络类型,与直接网络相似，间接网络的主要属性由三个要素来描述：拓扑、路由和交换。 拓扑定义了开关是如何通过通道互连的，可以图建模。 对于具有N个节点的网络，理想环境是使用一个NxN的开关连接它们，这种开关就是交叉开关。 使用一个NxN的交叉开关比使用全

11、连接的直接网络拓扑（有N个路由器，每个路由器都有一个NxN内部交叉开关）便宜，但是交叉开关的成本仍然限制了它在大型网络中的使用。 于是，又提出其他的拓扑结构。在这些拓扑中，消息到达目的节点之前要经过多个开关。规整网络中的开关通常都是相同的，传统上采用多级结构。 除了输人输出级以外，每一级使用规整连接与前一级和下一级相连。输人输出级既连接节点，又连接了网络中的其他级，这种网络称作多级互连网络。,交叉开关,交叉开关（Crossbar）网络是单级交换网络，可为每个端口提供更高的带宽。象电话交换机一样，交叉点开关可由程序控制动态设置其处于“开”或“关”状态，而能提供所有（源、目的）对之间的动态连接。

12、在并行处理中，交叉开关一般有两种使用方式：一种是用于对称的多处理机或多计算机机群中的处理器间的通信；另一种是用于SMP服务器或向量超级计算机中处理器和存储器之间的存取。,交叉开关点的状态,a中该行输入允许访问相应的输出，而从上面发出的对同一输出的访问被阻塞。 b 中上面发出的输入允许访问输出，通过开关点的行输入不请求同一输出并可以传向其他开关。 c 中从上面发出的输入允许访问输出，但是通过开关点的行输入也请求同一输出，被阻塞。 d 中状态只用于要求交叉开关支持多播的情形。,交叉开关应用,千兆开关/FDDI: 一种用于构造Alpha工作站和服务器互连的交叉开关 ，带宽3.6Gbps Sun Mi

13、crosystem公司在它们的Ultra Enterprise l0000（StarFire）SMP服务器中，将Gigaplane总线升级成Gigaplane-XB互连,交叉开关应用,处理器和存储器间的交叉开关 ： 交叉开关代替处理器和存储器间的连接总线 提供了多个处理器模块并行存取存储器的可能性 每个时刻每个存储器模块只能由一个处理器进行访问,交叉开关特性,交叉开关具有良好的带宽特性 Non-Blocking: 两个节点之间的通信，不会阻塞其他节点之间的通信。 代价不可扩放，O(P2),多级互连网络,交换开关模块 一个交换开关模块有a个输入和b个输出，每个输入可连接到任意输出端口，但只允许一

14、对一或一对多的映射，不允许多对一的映射，因为这将发生输出冲突 第i级开关Gi，有wi个ai,j*bi,j开关，Gi级共有pi个输入和qi个输出。 通常实现中所有开关都是相同的。 级间互连（Interstage Connection ）：定义了每一级输入与上一级输出之间连接方式 如果网络具有N=kn个端口，令X=xn-1xn-2x1x0表示任意一个端口号，其中0=Xi=k-1，如k=2,Generalized MIN Arch,典型的级间互联模式,完全混洗排列: C(xn-1xn-2x1x0)=xn-2x1x0 xn-1 把X中的数循环左移一位（图a) 逆完全混洗正好相反(图b）,典型的级间互联

15、模式,数字反转排列: C(xn-1xn-2x1x0)=x0 x1xn-2xn-1 通常称为位反转排列（图c所示）,典型的级间互连,蝶形连接: Ci(xn-1xi+1xixi-1x1x0)=xn-1xi+1x0 xi-1x1xi 第i个蝶形排列交换索引中的第0和第i个数,典型的级间互连,立方体排列: Ci(xn-1xi+1xixi-1x1x0)=xn-1xi+1xixi-1x0 第i个立方体排列将索引中的第i位求反,典型的级间互连,基准连接: Ci(xn-1xi+1xixi-1x1x0)=xn-1xi+1x0 xixi-1x1 第i个基准排列将索引中的最低i+1个有效数循环右移一位,多级互连网络

16、的分类,阻塞型：空闲的输入和输出之间不是总能建立连接，因为有可能与现有的连接冲突。 非阻塞型：任意输入端口可以连接任意空闲的输出端口而不会影响现有连接。如clos网，代价太高。 可重组型：任何输入端口可以连接到任何空闲的输出端口，但是可能要求重组现有连接的路径。如Benes网，在集中式控制器机器中可以实现，但在异步访问模式下很难重组。,开关及其连接,基准网络,C0为完全混洗连接，Ci为第n-i个基准排列（i=1，2，n）,Butterfly MIN,Ci为第i个蝶形排列（i=0，1,，n-1） ，Cn为恒等排列。,立方网络,Ci为第n-i个蝶形排列（i=1，2，n） ，C0为完全混洗排列,Om

17、ega MIN,Ci为完全混洗排列（i=0，1，n-1） ，Cn为恒等排列。,等价性,以上四种网络在拓扑上是等价的，属于Delta网的一类 对于X的索引而言，每一个开关内部的连接都只改变最低一位。为了能够连接任意输入到任意输出，应该能改变索引中所有位的值。 所以级间的互连方式可以如此定义：索引的位置序列在改变，经过n级后，所有的数位都占据过最低位置。 上面定义的MIN，其不同之处在于索引地址中的数占据最低有效位置的顺序不同。,Switch Architecture forBidirectional-MIN (BiDi-MIN),Buttefly BMIN,16-node BMIN,Fat-Tr

18、ee Irregular Topology,Hybrid Network and Convergence,Hybrid/Hierarchical Networks Cray T3D two processors connected to each node SGI origin two processors connected to a Hub (a node) multiple nodes connected to hypercube (up to 64 nodes) fat hypercube architecture (intermediate routers do not have a

19、ny node connected to them) NUMA-Q hierarchical ring SMP clusters bus within a node and regular/irregular across nodes Direct Networks a node connected to each router Indirect Networks switches at the intermediate stages are not connected to nodes,Overview,Review of Lec5 间接互连网络 交换技术,消息交换层,多处理器中的通信服务可

20、分为三层： 路由层：做出路由决策，选择中间路由器节点的候选输出通道，建立通过网络的路径。 交换层：利用物理层协议，通过网络实现消息的传输。 物理层：称为链路层协议，用来传输消息以及相邻路由器间物理通道的管理。 一般的路由器包括： 缓冲器 开关 路由和仲裁单元 链路控制器 处理器接口,一般路由器模型,延迟,路由延迟：消息第一次到达路由器时必须接受检查，以确定转发该消息的输出通道，这段延迟称作路由延迟，通常包括开关设置时间。 内部延迟：消息通过开关的传播延迟，输入和输出缓冲器之间数据同步信号的延迟。 外部延迟：通过物理链路延迟（路由器间延迟）,基本概念,流控是发送和接收单位信息的同步协议。 流控单

21、位是指传输时必须同步的那部分消息，该单位定义为发送端请求发送且接收端给与应答的最小信息单位 交换技术的差别在于物理流控单位和消息流控单位之间的关系 消息可以分为固定长度的报文，报文可以进一步分成微片（flit)，每个微片可能需要多个物理周期传输。 物理通道上每一步或每一周期可以传输的信息单位称为物理微片（phit)，即一个周期可以并行传输的位数。 物理微片与微片在许多机器中是相等的。,同步物理通道流控,基本交换技术,网络路径示意图：假设物理微片与微片大小相等，等于物理通道宽度W，路由头假设为一个微片，消息大小为L+W位，路由延迟为tr秒，两个路由器间物理通道的操作频率为BHz，路由器间物理通道

22、的带宽为BW位，假设连线足够短，一个时钟周期能够完成一次传输，路由器间传输延迟为tw=1/B 秒，路由器内部延迟为ts,电路交换,在数据传输前要在源和目的之间预订一条物理路径。 通过向网络中注入路由头微片实现 路由头微片包括目的地址和其他控制信息 路由头在向目的前进时，在通过中间路由器传输的同时保留物理链路 路由头到达目的时就建立了一条完整的路径并向源返回应答 源收到应答后就可以以硬件路径的整个带宽传送消息内容 电路可以由目的或消息的最后几位释放 消息传送不是很频繁而消息很长时，电路交换有优势 路由头在每个路由器被缓冲，而数据位不用缓冲，就像从源到目的节点直接用线连接一样 不足：整个消息发送期

23、间都要保留物理路径,电路交换,报文交换,将消息划分为固定长度的报文，每个报文的前几个字节包含路由和控制信息（称作报文头） 每个报文从源节点到目的节点独立路由 报文在向下一个节点转发之前完全缓冲在每个中间节点，因此通常也称为存储转发（SAF）交换。 如果消息较短且发送频繁，那么报文交换有优势。 只要路径空闲就可以用来传输数据 一个消息的多个报文可以同时在网络中传输 不足： 消息分割和拼装开销 路由器需要缓冲多个报文，需要较大的存储容量 延迟与距离成正比,报文交换,虚跨步交换（Virtual Cut Through),报文交换假定在制定路由决策及报文转发到目的之前报文必须完全被接收。 实际上在接收到报文头后就可以进行路由决策，而且如果输出通道是空闲的，路由器可以马上转发报文头随后的数据字节。 虚跨步：路由器在接收完整报文前，如果输出通道无阻塞可以直接跨接到下一个路由器的输入；如果输出通道阻塞，整个报文在该节点缓冲。 无阻塞时，报文头经过每个节点的延迟为路由延迟和传播延迟，消息可以流水地通过各个开关。 网络负载很重时，VCT与报文交换一样。 成功跨过每个中间节点的延迟公式见下页,虚跨步交换(VCT),虫孔交换,VCT消息流控的单位仍然为报文，即使消息可以跨过路由器，也必须为整个报文