第7计算机体系结构.ppt

计算机系统结构 第七章 互连网络 第7章 互连网络 7.1 互连网络的基本概念 7.2 互连网络的种类 7.1 互连网络的基本概念 7.1.1 互连网络的作用 7.1.2 互连网络的表示方法 7.1.3 互连函数 7.1.1 互连网络的作用 用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接，是一种由开关元件按照一定的拓扑结构和控制方式构成的网络。 互连网络已成为并行处理系统的核心组成部分。 互连网络对整个计算机系统的性能价格比有着决定性的影响。 一个例子：具有本地存储器、私有高速缓存、共享存储器和共享外围设备的一般处理机系统的互连结构 7.1.2 互连网络的表示方法 为了在输入结点与输出结点之间建立对应关系，互连网络有三种表示方法： (1)互连函数表示法： 如：f(xn-1…x1x0) = x0xn-2…x1xn-1 (2)图形表示法 (3)输入输出对应表示法 7.1.3 互连函数 2.全混洗函数（Perfect shuffle） 函数关系：把二进制结点号循环左移一位 子混洗(subshuffle)S(k) ,最低k位循环左移一位 超混洗(supershuffle)S(k),最高k位循环左移一位 3. 蝶式函数（Butterfly） 蝶式函数的名称来自于FFT变换时的图形，如蝴蝶式样。函数关系：将输入端二进制结点号的最高位和最低位互换位置。 子蝶式(subbutterfly)B(k) 最低k位的高低位互换 超蝶式(superbutterfly)B(k) 最高k位的高低位互换 显然成立： 4. 反位序函数（Bit Reversal） 函数关系：将二进制自变量的位序反过来。 子反位序函数，最低k位的位序反过来 超反位序函数，最高k位的位序反过来 5. 移数函数 函数关系：将输入端向量循环移动一定的位置 经常取r＝2i，因此移数函数又称为加减2i函数、PM2I函数等。 子移数函数： 其中：0 ? x ? N-1，0 ? i, k ? n-1，n = log2N。 Illiac函数包含PM2?0和PM2?n/2等4个互连函数 每个接点与它的上下左右4个相邻接点连接 例7.1：假设16个处理机的编号分别为0、1、…、15，采用单级互连网络。互连函数分别为： (1)Cube3 (2)PM2+3 (3)PM2-0 (4)Shuffle (5)Butterfly (6)Reversal 第12号处理机分别与哪一个处理机相连？ 解： (12)10 = (1100)2 (1) Cube3， (2) PM2+3， (3) PM2-0， (4) Shuffle，(5) Butterfly， (6) Reversal 1100最高位取反得0100， 4号处理机 (12 + 8) MOD 16 = 4， 4号处理机 12 – 1 = 11， 11号处理机 1100循环左移1位得到1001, 9号处理机 1100的最高最低位交换0101, 5号处理机 1100的位序反过来为0011, 3号处理机 补充: 基本的单级互连网络 1.立方体单级网络 立方体的每个顶点代表一个结点，结点的编号用二进制码（C2C1C0）表示。 3.混洗交换(shuffle exchange) 混洗交换互连网络包含全混洗和交换两种互连函数。 （1）全混洗 全混洗的互连函数为 Shuffle（Pn－1Pn－2…P1P0） ＝ Pn－2…P1P0Pn－1 7.2 互连网络的种类 7.2.1 静态互连网络 7.2.2 循环互连网络 7.2.3 多级互连网络 静态互连网络：在各结点之间有固定的连接通路，在运行过程中不能改变。一般不能实现任意结点到结点之间的互连。 循环互连网络：通过多次重复使用同一个单级互连网络以实现任意结点到结点之间的互连 。 多级互连网络：将多套相同的单级互连网络连接起来，实现任意结点到结点之间的互连，是动态互连网络的一种，适用于SIMD和MIMD。 7.2.1 静态互连网络 在各结点之间有固定的连接通路，在运行过程中不能改变的网络结构。 一般静态互连网络不能实现任意结点到结点之间的互连。 一维的有线性阵列结构；二维的有环形、星形、树形、网格形等；三维的有立方体等；三维以上的有超立方体等。 7.2.2 循环互连网络 一般静态互连网不能实现任意两结点之间的互连。有两种解