并行计算机体系结构第六章教案资料.ppt

《并行计算机体系结构第六章教案资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、，发回答信号。(3)把接收到的数据拷贝到用户地址空间。发送方接收到回答信号后释放系统缓冲区互连网络的主要性能参数：(1)频带宽度(Bandwidth)：传输信息的最大速率(2)传输时间(Transmissiontime)：等于消息长度除以频宽。(3)飞行时间(Timeofflight)：第一位信息到达接收方所花费的时间。(4)传输时延(Transportlatency)：等于飞行时间与传输时间之和。(5)发送方开销(Senderoverhead)：处理器把消息放到互连网络的时间。(6)接收方开销(Receiveroverhead)：处理器把消息从网络取出来的时间。一个消息的总时延可以用下面公式

3、表示：总时延＝发送方开销＋飞行时间＋消息长度/频宽＋接收方开销例7.1：假设一个网络的频宽为10Mb/S，发送方开销为230us，接收方开销分别为270us。如果两台机器相距100米，现在要发送一个1000字节的消息给另一台机器，试计算总时延。如果两台机器相距1000公里，那么总时延为多大？解：光的速度为299792.5KM/S，信号在导体中传递速度大约是光速的50％。相距100米时总时延为：相距1000公里时的总时延为：为了在输入结点与输出结点之间建立对应关系，互连网络有三种表示方法：(1)互连函数表示法：如：f(xn-1…x1x0)=x0xn-2…x1xn-1(2)图形表示法(3)输入输

4、出对应表示法互连网络…0011…n-1n-1输入:01234567输出:10325476互连网络的表示方法互连函数互连函数也称为互连置换或互连排列等。1.交换函数（Exchange）当n＝3时，有3种函数，每种能表示8个结点之间的连接关系。由于交换函数主要用于超立方体互连网中，因此也称为超立方体函数，用Cube表示，如：Cube0、Cube1、Cube2等。2.全混洗函数（Perfectshuffle）函数关系：把二进制结点号循环左移一位子混洗(subshuffle)S(k),最低k位循环左移一位超混洗(supershuffle)S(k),最高k位循环左移一位3.蝶式函数（Butterfly

5、）蝶式函数的名称来自于FFT变换时的图形，如蝴蝶式样。函数关系：将输入端二进制结点号的最高位和最低位互换位置。子蝶式(subbutterfly)B(k)最低k位的高低位互换超蝶式(superbutterfly)B(k)最高k位的高低互换显然成立：4.反位序函数（BitReversal）函数关系：将二进制自变量的位序反过来。子反位序函数，最低k位的位序反过来超反位序函数，最高k位的位序反过来5.移数函数函数关系：将输入端向量循环移动一定的位置经常取r＝2i，因此移数函数又称为加减2i函数、PM2I函数等。子移数函数：其中：0xN-1，0i,kn-1，n=log2N。Illiac函数包含P

6、M20和PM2n/2等4个互连函数每个接点与它的上下左右4个相邻接点连接例6.2：假设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)Reversal1100最高位取反得0100，4号处理机(12+8)MOD16=4，4号处理机12–1=11，11号处理机1100循环左移1位

7、得到1001,9号处理机1100的最高最低位交换0101,5号处理机1100的位序反过来为0011,3号处理机补充:基本的单级互连网络1.立方体单级网络立方体的每个顶点代表一个结点，结点的编号用二进制码（C2C1C0）表示。N＝8的三维立方体结构立方体单级网络的互连函数实现二进制编号中第k位值不同的结点之间的连接。故三维的立方体单级网络有三种互连函数：Cube0、Cube1和Cube2，分别建立结