体系结构课件chapter62章节.pptVIP

* PM2I单级网络（续） 当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单级网络（续） 1 2 3 4 5 6 7 0 PM2+0 PM2-0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 PM2-1 PM2+1 PM2-2 PM2+2 * (3)混洗交换单级网络 包含两个函数：混洗、交换 shuffle(pn-1 pn-2,,, p1 p0)= pn-2,,, p1 p0 pn-1 说明： 不是可逆函数 特性：作n次后，恢复到原来---〉多次混洗后，每个处理器都会遇到与其他处理器连接的机会（除全0和全1）； 增加交换函数，得到全混交换单级网络； 全混连接与立方体连接存在对应关系,此性质便于构成多级连接，并与立方体具有相似的关系； 最大距离为2n-1 * 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 一次混洗 二次混洗 * N=8时全混交换互连网络连接图 1 2 3 4 5 6 7 0 虚线：全混 实线：交换 * 蝶形单级网络 互连函数 Butterfly(pn-1 pn-2,,, p1 p0)= p0 pn-2,,, p1 pn-1 即将二进制的最高位和最低位相互交换位置。 * 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 0 1 2 3 4 5 6 7 * 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 * 总结 单级互连网络特性 任一单级互连网络均可表示成N入、N出的过程。 任一单级互连网络可实现部分结点(一对或几对)间的连接，不能实现任意多对结点间的同时连接。 单级互连网络含义：某些连接方法或拓扑结构。 单级互连网络应用 利用单级互连网络的特性作为实际IN的拓扑结构； 通过交换开关作为IN的可变因素； 通过交换开关多次控制实现IN的结点间任意互连。 * 3.基本多级互联网络 能够实现结点到结点之间的任意互连是互连网络的一种基本功能。 多级互连网络采用多个相同的或不同的互连网络直接连接起来。属于组合逻辑线路，一个时钟周期就能够实现任意结点到结点之间的互连。 多级互连网络采用的关键技术： 交换开关 交换开关之间的拓扑连接 对交换开关的不同控制方式 * 交换开关 一个a×b交换开关有a个输入和b个输出。 最常用的二元开关：a=b=2。 每个输入可与一个或多个输出相连，但是在输出端必须避免发生冲突。一对一和一对多映射是容许的；但不容许有多对一映射。 直连 交换 上播 下播 模块大小 合法状态 交换连接 2×2 4 2 4×4 256 24 8×840320 n×n nn n! 交换开关和合法状态 i入 j入 i出 j出 * 只容许一对一映射时称为置换连接，称这种开关为n×n交叉开关。 具有直通和交换两种功能的交换开关称为二功能开关，或交换开关。用一位控制信号控制。 具有所有四种功能的交换开关称为四功能开关，用两位控制信号控制。 * 拓扑结构 前一级交换开关的输出端与后一级交换开关的输入端之间的连接模式称为拓扑结构。 通常采用前面介绍的互连函数实现拓扑结构 实际上，从结点的输出到第一级交换开关的输入，以及从最后一级交换开关的输出到结点的输入也可以采用拓扑结构连接。 * 控制方式 在多级互连网络中有多级交换开关，每一级又有多个交换开关。 通常有三种控制方式 级控制：同一级交换开关使用同一个控制信号控制。 单元级控制：每个交换开关分别控制。 部分级控制：例如，第i级使用i+1个控制信号控制 (0 ￡ i ￡ n-1)。 同一个多级互连网络分别常用三种不同的控制方式，可以构成三种不同的互连网络。 * 基本多级互连网络 多级立方网络(Single Stored Cube Network) 多级混洗交换网络 多级PM2I网络(Plus-minus 2i) 基准网络 多