清华郑纬民汤志忠计算机系统结构第7章ppt课件.ppt

《清华郑纬民汤志忠计算机系统结构第7章ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、本地存储器、私有高速缓存、共享存储器和共享外围设备的一般处理机系统的互连结构7/29/20213计算机系统结构第七章互连网络磁盘SM1SM2SMmPMN……CnPnLMC1P1LMPCN……………………PION磁带打印机终端网络…(共享存储器)(共享I/O与外设)7/29/20214计算机系统结构第七章互连网络互连网络通常是用有向边或无向边连接有限个结点的组成。互连网络的主要特性有：(1)网络规模：网络中结点的个数(2)结点度：与结点相连接的边数称为结点度进入结点的边数叫入度从结点出来的边数则叫出度(3)距离：两个结点之间相连

3、的最少边数(4)网络直径：网络中任意两个结点间距离的最大值。用结点间的连接边数表示7.1.2互连网络的特性7/29/20215计算机系统结构第七章互连网络7.1.3互连网络的性能参数发送方的步骤如下：(1)用户程序把要发送的数据拷贝到系统缓冲区。(2)缓冲区中的数据打包并发送到网络接口部件。(3)网络接口硬件开始发送消息。数据包的接收步骤如下：(1)把数据包从网络接口部件拷贝到系统缓冲区。(2)检查收到的数据包，如果正确，发回答信号。(3)把接收到的数据拷贝到用户地址空间。发送方接收到回答信号后释放系统缓冲区7/29/2021

4、6计算机系统结构第七章互连网络互连网络的主要性能参数：(1)频带宽度(Bandwidth)：传输信息的最大速率(2)传输时间(Transmissiontime)：等于消息长度除以频宽。(3)飞行时间(Timeofflight)：第一位信息到达接收方所花费的时间。(4)传输时延(Transportlatency)：等于飞行时间与传输时间之和。(5)发送方开销(Senderoverhead)：处理器把消息放到互连网络的时间。(6)接收方开销(Receiveroverhead)：处理器把消息从网络取出来的时间。7/29/20217计

5、算机系统结构第七章互连网络一个消息的总时延可以用下面公式表示：总时延＝发送方开销＋飞行时间＋消息长度/频宽＋接收方开销例7.1：假设一个网络的频宽为10Mb/S，发送方开销为230us，接收方开销分别为270us。如果两台机器相距100米，现在要发送一个1000字节的消息给另一台机器，试计算总时延。如果两台机器相距1000公里，那么总时延为多大？7/29/20218计算机系统结构第七章互连网络解：光的速度为299792.5KM/S，信号在导体中传递速度大约是光速的50％。相距100米时总时延为：相距1000公里时的总时延为：7

6、/29/20219计算机系统结构第七章互连网络为了在输入结点与输出结点之间建立对应关系，互连网络有三种表示方法：(1)互连函数表示法：如：f(xn-1…x1x0)=x0xn-2…x1xn-1(2)图形表示法(3)输入输出对应表示法互连网络…0011…n-1n-1输入:01234567输出:103254767.1.4互连网络的表示方法7/29/202110计算机系统结构第七章互连网络7.1.5互连函数互连函数也称为互连置换或互连排列等。1.交换函数（Exchange）当n＝3时，有3种函数，每种能表示8个结点之间的连接关系

7、。由于交换函数主要用于超立方体互连网中，因此也称为超立方体函数，用Cube表示，如：Cube0、Cube1、Cube2等。7/29/202111计算机系统结构第七章互连网络7/29/202112计算机系统结构第七章互连网络2.全混洗函数（Perfectshuffle）函数关系：把二进制结点号循环左移一位子混洗(subshuffle)S(k),最低k位循环左移一位超混洗(supershuffle)S(k),最高k位循环左移一位显然成立：逆混洗函数：7/29/202113计算机系统结构第七章互连网络7/29/202114计算机系统

8、结构第七章互连网络3.蝶式函数（Butterfly）蝶式函数的名称来自于FFT变换时的图形，如蝴蝶式样。函数关系：将输入端二进制结点号的最高位和最低位互换位置。子蝶式(subbutterfly)B(k)最低k位的高低位互换超蝶式(superbutterfly)B(k)最高k位