计算机系统结构_第7章

《计算机系统结构_第7章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章互连网络7.1互连网络的基本概念7.2互连网络的种类7.3消息传递机制7.1互连网络的基本概念7.1.1互连网络的作用7.1.2互连网络的特性7.1.3互连网络的性能参数7.1.4互连网络的表示方法7.1.5互连函数7.1.1互连网络的作用用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接。互连网络已成为并行处理系统的核心组成部分。互连网络对整个计算机系统的性能价格比有着决定性的影响。一个例子：具有本地存储器、私有高速缓存、共享存储器和共享外围设备的一般处理机系统的互连结构7.1.2互连网络的特性

2、互连网络通常是用有向边或无向边连接有限个结点的组成。互连网络的主要特性有：（1）网络规模：网络中结点的个数（2）结点度：与结点相连接的边数称为结点度进入结点的边数叫入度从结点出来的边数则叫出度（3）距离：两个结点之间相连的最少边数（4）网络直径：网络中任意两个结点间距离的最大值。用结点间的连接数表示7.1.3互连网络的性能参数发送方的步骤如下：（1）用户程序把要发送的数据拷贝到系统缓冲区。（2）缓冲区中的数据打包并发送到网络接口部件。（3）网络接口硬件开始发送消息。数据包的接收步骤如下：（1）把数据包从网络接口部

3、件拷贝到系统缓冲区。（2）检查收到的数据包，如果正确，发回答信号。（3）把接收到的数据拷贝到用户地址空间。发送方接收到回答信号后释放系统缓冲区互连网络的主要性能参数：（1）频带宽度（Bandwidth）：传输信息的最大速率（2）传输时间（Transmissiontime）:等于消息长度除以频带宽度（3）飞行时间（Timeofflight）：第一位信息到达接收方所花费的时间。（4）传输时延（Transportlatency）：等于飞行时间与传输时间之和。（5）发送方开销（Senderoverhead）：处理器把消息

4、放到互连网络所用的时间。（6）接收方开销（Receiveroverhead）：处理器把消息从互连网络上取出来所用的时间。一个消息的总时延可以用下面的公式表示：总时延＝发送方开销＋飞行时间＋消息长度/频带宽度＋接收方开销例7.1：假设一个网络的频宽为10Mb/S，发送方开销为230us，接收方开销分别为270us。如果两台机器相距100米，现在要发送一个1000字节的消息给另一台机器，试计算总时延。如果两台机器间距1000公里，那么总时延为多大？解：光的速度为299792.5KM/S，信号在导体中传递的速度大约为光

5、速的50％。相距100米时总时延为：相距1000公里时的总时延为：7.1.4互连网络的表示方法为了在输入结点与输出结点之间建立对应关系，互连网络有三种表示方法：（1）互连函数表示法：如：f(x…xx)=xx…xx（2）图形表示法（3）输入输出对应表示法n-1120n-21n-17.1.5互连函数1.交换函数（Exchange）函数关系：把二进制结点号的某一位取反当n＝3时，有3种函数，表示8个结点之间的连接关系。由于交换函数主要用于超立方体互联网中，因此也称为超立方体函数，用Cube表示，如Cube0、Cube1

6、、Cube2等。2.全混洗函数（Perfectshuffle）函数关系：把二进制结点号循环左移一位子混洗（subshuffle）S,最低k位循环左移一位超混洗（supershuffle）S,最高k位循环左移一位逆混洗函数：(k)(k)3.蝶式函数（Butterfly）蝶式函数的名称来自于FFT变换时的图形，如蝴蝶式样。函数关系：将二进制结点号的最高位和最低位互换位置。子蝶式（subbutterfly）B最低k位的高低位互换超蝶式（superbutterfly）B最高k位的高低位互换(k)(k)4.反位序函数（Bi

7、tReversal）函数关系：将二进制自变量的位序反过来子反位序函数，最低k位的位序反过来超反位序函数，最高k位的位序反过来对于n＝3的情况，蝶式函数与反位序函数正好相同，因此有：R＝B，R＝B，R＝B。(2)(2)(2)(2)5.移数函数函数关系：将输入端结点循环移动一定的位置经常取r＝2，因此移数函数又称为加减2函数、PM2I函数等。ii例6.2：假设16个处理机的变化分别为0、1、…、15，采用单级互连网络。互连函数分别为：（1）Cube3（2）PM2＋3（3）PM2－0（4）Shuffle（5）Butte

8、rfly（6）Reversal计算第12号处理机分别与哪一个处理机相连接？解：（12）＝（1100）（1）Cube3，1100最高位取反得0100，与4号处理机连接（2）PM2＋3，（12＋8）MOD16＝4，与4号处理机连接（3）PM2－0，12－1＝11，与11号处理机连接（4）Shuffle，1100循环左移1位得1001，与9号处理机连接（5）Butterfly，