《高级计算机体系结构第五章互连路由》由会员分享，可在线阅读，更多相关《高级计算机体系结构第五章互连路由（70页珍藏版）》请在金锄头文库上搜索。
1、PCA L5 Chp3.1 Wu Spring 10 USTC Parallel Computer Architecture 并行计算机体系结构并行计算机体系结构 Lecture 5 March 29, 2010 Wu junmin () PCA L5 Chp3.2 Wu Spring 10 USTC Overview Review of Lec4 交换技术交换技术 路由算法路由算法 PCA L5 Chp3.3 Wu Spring 10 USTC 系统互连系统互连 不同带宽与距离的互连技术不同带宽与距离的互连技术 局部总线I/O 总线SCI HiPPI Myrinet千兆位 以太网光纤 通道快
2、速以太网以太网10 Base TFDDIATM总线或开关SANLANMANWAN100 Gb/s10 Gb/s1 Gb/s100 Mb/s10 Mb/sIsoEnet网络带宽交叉开关MIN 或100 Base TPCA L5 Chp3.4 Wu Spring 10 USTC 静态互连网络静态互连网络 与动态互连网络与动态互连网络 静态互连网络：又称为直接连接网络。处理单元间有着静态互连网络：又称为直接连接网络。处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点的固定连接的一类网络，在程序执行期间，这种点到点的 连接保持不变；典型的静态网络有一维线性阵列、二维连接保持不变；典型的静态网
3、络有一维线性阵列、二维网孔、树连接、超立方网络、立方环等。网孔、树连接、超立方网络、立方环等。 动态网络：又称为间接连接网络。用交换开关构成的，动态网络：又称为间接连接网络。用交换开关构成的，可按应用程序的要求动态地改变连接组态；典型的动态可按应用程序的要求动态地改变连接组态；典型的动态网络包括总线、交叉开关和多级互连网络等。网络包括总线、交叉开关和多级互连网络等。 PCA L5 Chp3.5 Wu Spring 10 USTC 静态网络性能指标静态网络性能指标 节点度（节点度（Node Degree）：射入或射出一个节点的边数）：射入或射出一个节点的边数。在单向网络中，入射和出射边之和称为节
4、点度。在单向网络中，入射和出射边之和称为节点度。 网络直径（网络直径（Network Diameter）：）： 网络中任何两个节网络中任何两个节 点之间的最长距离，即最大路径数。点之间的最长距离，即最大路径数。 如果从任一节点观看网络都一样，则称网络为对称的（如果从任一节点观看网络都一样，则称网络为对称的（Symmetry）。）。 边连通度（边连通度（arc connectivity)：将网络分成两个不连通：将网络分成两个不连通的部分所必须移去的边数。的部分所必须移去的边数。 代价（代价（cost）：可以用总边数（链路数）来衡量。）：可以用总边数（链路数）来衡量。 PCA L5 Chp3.6
5、Wu Spring 10 USTC 静态互连网络拓扑静态互连网络拓扑 大多数都是正交拓扑大多数都是正交拓扑 网络拓扑正交的充要条件是：节点可以在一个正交的网络拓扑正交的充要条件是：节点可以在一个正交的n维空间内组织维空间内组织 起来，每条链路的安排都要在一维中产生一个偏移量。起来，每条链路的安排都要在一维中产生一个偏移量。 正交拓扑可以进一步分为严格正交和弱正交。正交拓扑可以进一步分为严格正交和弱正交。 严格正交拓扑每个节点至少有一条链路通过每一维。严格正交拓扑每个节点至少有一条链路通过每一维。 在弱正交中，某些节点在某些维上没有链路，因此不可在弱正交中，某些节点在某些维上没有链路，因此不可
6、能从任意节点穿过任意维，从给定的节点到结定的维首能从任意节点穿过任意维，从给定的节点到结定的维首先要转移到其他维。先要转移到其他维。 模型可用图模型可用图G(N,C)表示，其中顶点表示，其中顶点N代表处理节点的集代表处理节点的集 合，边合，边C代表通信信道的集合。代表通信信道的集合。 PCA L5 Chp3.7 Wu Spring 10 USTC 严格正交拓扑严格正交拓扑 路由简单，可以用硬件实现高效路由算法路由简单，可以用硬件实现高效路由算法 在严格正交拓扑中，可以用节点在在严格正交拓扑中，可以用节点在n维空间中的坐标作维空间中的坐标作 为节点的编号。为节点的编号。 由于每条链路都遍历了一维
7、，而且每一个节点在每一维由于每条链路都遍历了一维，而且每一个节点在每一维上至少有一条链路，两个节点间的距离就可以用每一维上至少有一条链路，两个节点间的距离就可以用每一维的偏移量的和来计算。的偏移量的和来计算。 给定链路上的偏移量仅仅影响相应维的偏移量。由于从给定链路上的偏移量仅仅影响相应维的偏移量。由于从 网络中的任意节点可以直接到达任意维，路由实现只需网络中的任意节点可以直接到达任意维，路由实现只需在某一维上选择绝对偏移量减小的链路就可以了。在某一维上选择绝对偏移量减小的链路就可以了。 各维的偏移量可以存储在报文头中，报文每次成功地经各维的偏移量可以存储在报文头中，报文每次成功地经过中间节点
8、时将会更新偏移量（增加或减少一个单位）过中间节点时将会更新偏移量（增加或减少一个单位） PCA L5 Chp3.8 Wu Spring 10 USTC 严格正交拓扑严格正交拓扑超立方超立方 超立方是超立方是n维网格和维网格和k元元n立方的特例。立方的特例。 超立方是一个超立方是一个n维网格，每维节点数均为维网格，每维节点数均为2，也称，也称2元元n立方或二进制立方或二进制n方。方。 PCA L5 Chp3.9 Wu Spring 10 USTC 动态互连网络特性动态互连网络特性 动态互连网络没有提供节点间的直接连接，任何两个节动态互连网络没有提供节点间的直接连接，任何两个节点间的通信必须通过某
9、些交换机进行。点间的通信必须通过某些交换机进行。 每个节点都有一个网络适配器连接在网络开关上。每个节点都有一个网络适配器连接在网络开关上。 每个开关都有一组端口，每个端口包括一条输入和一条每个开关都有一组端口，每个端口包括一条输入和一条输出链路。每个开关的端口或连接到处理器，或者悬空输出链路。每个开关的端口或连接到处理器，或者悬空，或者连接到其他开关的端口上，以实现处理器间的连，或者连接到其他开关的端口上，以实现处理器间的连接。这些开关的互连方式决定了不同的网络拓扑。接。这些开关的互连方式决定了不同的网络拓扑。 间接网络的模型也可以用图间接网络的模型也可以用图G(N,C)表示，其中表示，其中N
10、是开关是开关 的集合，的集合，C是开关之间的单向或双向链路集合。是开关之间的单向或双向链路集合。 从一个节点向另一个节点发送消息时，需要经过源节点从一个节点向另一个节点发送消息时，需要经过源节点和它连接的开关之间的链路及传输路径中最后一个开关和它连接的开关之间的链路及传输路径中最后一个开关 和目的节点之间的链路。因此两个节点间的距离要在直和目的节点之间的链路。因此两个节点间的距离要在直 接连接两个节点的开关之间的距离上再加上两个单位。接连接两个节点的开关之间的距离上再加上两个单位。 类似地，网络直径等于连接到节点的开关之间的最大距类似地，网络直径等于连接到节点的开关之间的最大距离加上两个单位。
11、离加上两个单位。 PCA L5 Chp3.10 Wu Spring 10 USTC 动态互连网络类型动态互连网络类型 与直接网络相似，间接网络的主要属性由三个要素来描与直接网络相似，间接网络的主要属性由三个要素来描述：拓扑、路由和交换。述：拓扑、路由和交换。 拓扑定义了开关是如何通过通道互连的，可以图建模。拓扑定义了开关是如何通过通道互连的，可以图建模。 对于具有对于具有N个节点的网络，理想环境是使用一个个节点的网络，理想环境是使用一个NxN的的开关连接它们，这种开关就是交叉开关。开关连接它们，这种开关就是交叉开关。 使用一个使用一个NxN的交叉开关比使用全连接的直接网络拓扑的交叉开关比使用全
12、连接的直接网络拓扑 （有（有N个路由器，每个路由器都有一个个路由器，每个路由器都有一个NxN内部交叉开内部交叉开 关）便宜，但是交叉开关的成本仍然限制了它在大型网关）便宜，但是交叉开关的成本仍然限制了它在大型网络中的使用。络中的使用。 于是，又提出其他的拓扑结构。在这些拓扑中，消息到于是，又提出其他的拓扑结构。在这些拓扑中，消息到达目的节点之前要经过多个开关。规整网络中的开关通达目的节点之前要经过多个开关。规整网络中的开关通常都是相同的，传统上采用多级结构。常都是相同的，传统上采用多级结构。 除了输人输出级以外，每一级使用规整连接与前一级和除了输人输出级以外，每一级使用规整连接与前一级和 下一
13、级相连。输人输出级既连接节点，又连接了网络中下一级相连。输人输出级既连接节点，又连接了网络中的其他级，这种网络称作多级互连网络。的其他级，这种网络称作多级互连网络。 PCA L5 Chp3.11 Wu Spring 10 USTC 交叉开关交叉开关 交叉开关（交叉开关（Crossbar）网络是单级交换网络，可为每）网络是单级交换网络，可为每 个端口提供更高的带宽。象电话交换机一样，交叉点开个端口提供更高的带宽。象电话交换机一样，交叉点开 关可由程序控制动态设置其处于关可由程序控制动态设置其处于“开开”或或“关关”状态，状态，而能提供所有（源、目的）对之间的动态连接。而能提供所有（源、目的）对之
14、间的动态连接。 在并行处理中，交叉开关一般有两种使用方式：一种是在并行处理中，交叉开关一般有两种使用方式：一种是用于对称的多处理机或多计算机机群中的处理器间的通用于对称的多处理机或多计算机机群中的处理器间的通信；另一种是用于信；另一种是用于SMP服务器或向量超级计算机中处服务器或向量超级计算机中处 理器和存储器之间的存取。理器和存储器之间的存取。 PCA L5 Chp3.12 Wu Spring 10 USTC 交叉开关特性交叉开关特性 交叉开关具有良好的带宽特性交叉开关具有良好的带宽特性 Non-Blocking: 两个节点之间的通信，不会阻塞其他节两个节点之间的通信，不会阻塞其他节 点之间
15、的通信点之间的通信 代价不可扩放，代价不可扩放，O(P2) PCA L5 Chp3.13 Wu Spring 10 USTC 多级互连网络多级互连网络 交换开关模块交换开关模块 一个交换开关模块有一个交换开关模块有a个输入和个输入和b个输出，每个输入可连接到任意输出个输出，每个输入可连接到任意输出 端口，但只允许一对一或一对多的映射，不允许多对一的映射，因为端口，但只允许一对一或一对多的映射，不允许多对一的映射，因为 这将发生输出冲突这将发生输出冲突 第第i级开关级开关Gi，有，有wi个个ai,j*bi,j开关，开关，Gi级共有级共有pi个输入和个输入和qi个输出个输出 通常实现中所有开关都是
16、相同的通常实现中所有开关都是相同的 级间互连（级间互连（Interstage Connection ）：定义了每一级）：定义了每一级 输入与上一级输出之间连接方式输入与上一级输出之间连接方式 如果网络具有如果网络具有N=kn个端口，令个端口，令X=xn-1xn-2x1x0表示任表示任 意一个端口号，其中意一个端口号，其中0=i，则使用，则使用c1i。 新的算法中新的算法中c00和和c13永远不会被使用永远不会被使用 c12的队列中如果存储了一个报文，那么它的目的只能是的队列中如果存储了一个报文，那么它的目的只能是n3，从而该，从而该 消息必然在消息必然在n3被吸收；被吸收； 如果如果c11中存储了报文，其目的可能是中存储了报文，其目的可能是n2或或n3；如果是；如果是n2，则马上在，则马上在 n2被吸收；如果是被吸收；如果是n
