高等计算机系统结构,清华大学计算机科学与技术系高性能计算研究所 郑纬民 教授 2007年11月,计算机科学与技术系研究生课程,高等计算机系统结构,第一章 高等计算机的核心技术并行处理 第二章 加速比性能模型与可扩展性分析 第三章 互连与通信 第四章 划分与调度 第五章 并行存储器系统 第六章 Cache Coherence 第七章 Memory Consistency 第八章 指令级并行处理,第三章 互连与通信,3.1 互连网络的作用 3.2 静态网络 3.3 动态网络 3.4 通信问题,3.1 互连网络的作用,定义：由开关元件按一定拓扑结构和控制方式构成的网络以实现计算机系统内部多个处理机或多个功能部件间的相互连接。 操作方式： 同步通信（Synchronous Communication) 异步通信(Asynchronous Communication) 控制策略： 集中控制(Centralized control) 分布控制(Distributed control),交换方式： 电路交换(Circuit switching) 分组交换(Packet switching) Wormhole交换(Wormhole switching) 网络拓扑结构： 静态网络(Static network) 动态网络(Dynamic network),第三章 互连与通信,3.1 互连网络的作用 3.2 静态网络 3.2.1 静态网络的特点与指标 3.2.2 典型的静态网络 3.3 动态网络 3.4 通信问题,3.2 静态网络,3.2.1 静态网络的特点与指标 1.静态网络的特点 静态网络由点点直接相连而成，这种连结方式在程序执行过程中不会改变。 如果用图来表示，结点代表开关，边代表通信链路，则 (1) 结点间的链路无源，不能重构 (2) 开关元件与处理机相连 (3) 不直接相连结点间的通信需通过中间结点中转。,2.静态网络的指标 结点度：与结点相连接的边（链路或通道）数，表示节点所需要的I/O端口数，模块化要求结点度保持恒定。根据通道到结点的方向，结点度可以进一步表示为： 结点度 = 入度 + 出度 其中入度是进入结点的通道数，出度是从结点出来的通道数。 距离：与两个结点之间相连的最少边数。 网络直径：网络中任意两个结点间距离的最大值。,网络规模：网络中结点数，表示该网络功能连结部件的多少。 等分宽度：某一网络被切成相等的两半时，沿切口的最小边数称为该网络的等分宽度。 结点间的线长：两个结点间的线的长度。 对称性：从任何结点看，拓扑结构都一样，这种网络实现和编程都很容易。 结点是否同构。 通道是否有缓冲。,3.2.2 典型的静态网络 1.线性阵列,对N个结点的线性阵列，有N-1条链路，直径为N-1（任意两点之间距离的最大值），度为2，不对称，等分宽度为1。 N很大时，通信效率很低。,线性阵列与总线的区别： 线性阵列：允许不同的源结点和目的结点对并发使用系统的不同部分。 总线：通过切换与其相连的许多结点来实现时分特性，同一时刻只有一对结点在传送数据。,2.环,对N个结点的环，考虑相邻结点数据传送方向： 双向环：链路数为N，直径N/2，度为2，对称，等分宽度为2。比如KSR-1（1990）。 单向环：链路数为N，直径N-1，度为2，对称，等分宽度为2。,3.带弦环,对上图中12个结点的带弦双向环， 结点度为3：链路数为18，直径4（比如红色结点），度为3，不对称，等分宽度为2。 结点度为4：链路数为24，直径3（比如红色结点），度为4，对称，等分宽度为8。,4.全链接 全链接是带弦环的一种特殊情形。全链接中的每个结点和其他结点之间都有单一的直接链路。如下图中8个结点的全链接：,有28条链路，直径为1，度为7，对称，等分宽度为16。,5.树形,4层的二叉树,一棵K层完全二叉树应有N = 2K - 1个结点，大多数结点的结点度为3，直径为2（K - 1）（即右边任意一个叶子结点到左边任意一个叶子结点）。不对称，等分度为1。 由于结点度为常数，所以树是一种可扩展的系统结构。,树形的扩展：,带环树,这两种结构都可以缓解根结点的瓶颈问题。,6.星形,星形实际上是一种二层树（如右图）。有N个结点的星形网络，有N - 1条链路，直径为2，最大结点度为N - 1，非对称，等分宽度为1。,7.网格,有N个结点的rr网格（其中 )，有2N - 2r条链路，直径为2（r-1)，结点度为4，非对称，等分宽度为r。,网格的变形： a. Illiac 网,有N个结点的rr网格（其中 )，有2N条链路，直径为r-1，结点度为4。,b. 环形网（2DTorus）,有N个结点的rr网（其中 )，有2N 条链路，直径为2r/2，结点度为4，对称。,c. 搏动式阵列（Systolic Array）,8.超立方体,0-立方体,1-立方体,2-立方体,3-立方体,4-立方体,一个n-立方体由N = 2n个结点构成，它们分布在n维上，每维有两个结点。直径为n，结点度为n，对称。由于结点度随维数线性增加，所以超立方体不是一种可扩展结构。 例子： Intel的iPSC/1、iPSC/2、nCUBE,9.带环立方体,一个带环n-立方体由N = 2n个结点环构成，每个结点环是一个有n个结点的环，所以结点总数为n 2n个。直径通常为2n，结点度为3，对称。,带环3-立方体,10.k元n-立方体网络,4元3-立方体（隐藏的结点与连接没有画出),在一个k元n-立方体网络中，结点的数目N = kn，即：,其中，k称为基数（radix），n称为维数（dimension）。 k元n-立方体的结点可以用基数为k的n位地址A = a0 a1 a2 . an来表示，其中ai代表第i维结点的位置。,传统的环网等价于4元2-立方体。,第三章 互连与通信,3.1 互连网络的作用 3.2 静态网络 3.3 动态网络 3.3.1 互连函数 3.3.2 多级互联网络 3.4 通信问题,3.3 动态网络,特点： 网络的开关元件有源，链路可通过设置这些开关的状态来重构。 只有在网络边界上的开关元件才能与处理机相连。,3.3.1 互连函数 排列：N个数的每一种有确定次序的放置方法叫做一个N排列。 置换：把一个N排列变成另一个N排列的变换叫做N阶置换。 在有N个输入端和N个输出端的网络中，输入端和输出端的连接关系可以用置换来表示（输入端与输出端一一对应）。 一些常见的置换方式可以用下面的函数表示：,1. 恒等函数,其中，Xn-1 Xn-2Xk X0是PE的地址（通常为二进制）。n为3时的恒等函数的连接情形如下：,000,001,010,011,100,101,110,111,000,001,010,011,100,101,110,111,2. 方体函数（cube0，cube1，cuben-1),方体函数是由n个互连函数组成，其中0kn。 比如，n为3时，3-立方体各结点地址如下：,Y,Z,X,010,011,110,000,111,001,100,101,000,001,010,011,100,101,110,111,000,001,010,011,100,101,110,111,Cube0:,0,1,2,3,4,5,6,7,000,001,010,011,100,101,110,111,000,001,010,011,100,101,110,111,Cube1:,0,1,2,3,4,5,6,7,000,001,010,011,100,101,110,111,000,001,010,011,100,101,110,111,Cube2:,0,1,2,3,4,5,6,7,000,001,010,011,100,101,110,111,000,001,010,011,100,101,110,111,3. 洗牌函数,0,1,2,3,4,5,6,7,洗牌函数的变形： a. 均匀洗牌（Shuffle-Exchange) 是洗牌函数与Cube0函数的组合。,0,1,2,3,4,5,6,7,：洗牌,b. 第k个子洗牌,即最低k位循环左移一位。,000,001,010,011,100,101,110,111,000,001,010,011,100,101,110,111,4. 逆洗牌函数,0,1,2,3,4,5,6,7,000,001,010,011,100,101,110,111,000,001,010,011,100,101,110,111,5. 蝶式,0,1,2,3,4,5,6,7,6. PM2I函数（加减2i） 共有2n个互连函数，对N个结点的网络为,例1： N = 8（8个结点），则n = log28 = 3，所以：i = 0，1，2；j = 0，1，7。 6个PM2I函数如下：,PM2+0: ( 0 1 2 3 4 5 6 7）,0,1,2,3,4,5,6,7,PM2-0: ( 7 6 5 4 3 2 1 0）,0,1,2,3,4,5,6,7,PM2+1: ( 0 2 4 6）（1 3 5 7）,0,1,2,3,4,5,6,7,PM2-1: ( 6 4 2 0）（7 5 3 1）,0,1,2,3,4,5,6,7,PM22: ( 0 4）（1 5）（2 6）（3 7）,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,例2：,8,9,10,11,12,13,14,15,上面的网络可以用四个PM2I函数表示。,PM2+0: ( 0 1 2 15 ),PM2-0: ( 15 14 13 0 ),PM22: ( 0 4）（1 5）（2 6）（3 7） ( 4 8）（5 9）（6 10）（7 11） ( 8 12）（9 13）（10 14）（11 15） ( 12 0）（13 1）（14 2）（15 3）,3.3.2 多级互连网络 1. 多级网络的三要素 （1）开关单元：a个输入a个输出的开关单元记做aa的开关单元，其中，a是2的整数倍。常见的有2 2、 4 4、8 8等。 根据开关单元功能的多少， 2 2