计算机系统结构第六章(互连网络).ppt

互连网络 基本概念 互连网络种类 消息传递机制 基本概念 互连网络的作用 互连网络的表示 常用互连函数 互连网络的特性 传输性能参数 互连网络的作用 互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用于实现计算机系统内部多个处理机或多个功能部件之间的相互连接。互连网络已成为并行处理系统的核心组成部分。互连网络对整个计算机系统的性能价格比有着决定性的影响。 举例说明(多处理机) 基本模型 互连网络的表示 为了在输入结点与输出结点之间建立对应关系，互连网络有两种表示方法： 互连函数表示法 自变量和函数常用二进制表示。 例如：f(xn-1…x1x0) = x0xn-2…x1xn-1 。 输入输出对应表示法 常用互连函数 恒等置换 交换置换 方体置换 均匀洗牌置换 蝶式置换 位序颠倒置换 移数置换 加减2i置换 恒等置换 I(xn-1xn-2...x1x0)= xn-1xn-2...x1x0 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 交换置换 E(xn-1xn-2...x1x0)= xn-1xn-2...x1x0 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 方体置换 — 互连函数 Ck(xn-1xn-2...xk...x1x0)=xn-1xn-2... xk...x1x0 例如：当N=8时，有3种函数，每种能表示8个结点之间的连接关系。 C2(x2x1x0)=x2x1x0 C1(x2x1x0)=x2x1x0 C0(x2x1x0)=x2x1x0 C0就是交换置换。 方体置换 — 图示（N=8） 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 C0方体置换 C1方体置换 C2方体置换 方体置换 — 提示 由于方体置换函数主要用于超立方体互连网中，因此也称为超立方体函数，用Cube表示，如：Cube0、Cube1、Cube2等。 均匀洗牌置换 — 互连函数 均匀洗牌(shuffle:循环左移一位) σ(xn-1xn-2...xk...x1x0)=xn-2...xk...x1x0xn-1 子洗牌(subshuffle:最低k位循环左移一位) σ(k)(xn-1xn-2...xkxk-1xk-2...x1x0)= xn-1xn-2...xkxk-2...x1x0xk-1 超洗牌(supershuffle:最高k位循环左移一位) σ(k)(xn-1xn-2...xn-kxn-k-1...x1x0)= xn-2...xn-kxn-1xn-k-1...x1x0 均匀洗牌置换 — 图示（N=8） 均匀洗牌置换 — 提示 三种置换之间的关系 逆洗牌（二进制结点号循环右移一位） σ-1(xn-1xn-2... x1x0)=x0xn-1xn-2... x1 均匀洗牌置换 — 应用 均匀洗牌与逆均匀洗牌是两个十分有用的互连函数，以它们代表的链路与以交换置换代表的开关多级组合起来可构成Omega（Ω）网络与逆Omega（Ω）网络。σ函数在实现多项式求值、矩阵转置和FFT等并行运算以及并行排序等方面都得到广泛的应用。 蝶式置换 — 互连函数 蝶式(butterfly:高低位互换) β(xn-1xn-2...xk...x1x0)=x0xn-2...xk...x1xn