并行计算机体系结构第六章课件.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《并行计算机体系结构第六章课件.ppt》由会员分享,可在线阅读,更多相关《并行计算机体系结构第六章课件.ppt(75页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第六章第六章 互互联网网络互互连网网络的作用的作用用来实现计算机系统内部多个处理机或多个功用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接。能部件之间的相互连接。互连网络已成为并行处理系统的核心组成部分。互连网络已成为并行处理系统的核心组成部分。互连网络对整个计算机系统的性能价格比有着互连网络对整个计算机系统的性能价格比有着决定性的影响。决定性的影响。一个例子:具有本地存储器、私有高速缓存、一个例子:具有本地存储器、私有高速缓存、共享存储器和共享外围设备的一般处理机系共享存储器和共享外围设备的一般处理机系统的互连结构统的互连结构磁盘SM1SM2SMmPMNCnPnLMC1P1LMP
2、CNPION磁带打印机终端网络(共享存储器)(共享I/O与外设)互连网络通常是用有向边或无向边连接有限个互连网络通常是用有向边或无向边连接有限个结点的组成。互连网络的主要特性有:结点的组成。互连网络的主要特性有:(1)(1)网络规模:网络中结点的个数网络规模:网络中结点的个数(2)(2)结点度:与结点相连接的边数称为结点度结点度:与结点相连接的边数称为结点度 进入结点的边数叫入度进入结点的边数叫入度 从结点出来的边数则叫出度从结点出来的边数则叫出度(3)(3)距离:两个结点之间相连的最少边数距离:两个结点之间相连的最少边数(4)(4)网络直径:网络中任意两个结点间距离的网络直径:网络中任意两个
3、结点间距离的最大值。用结点间的连接边数表示最大值。用结点间的连接边数表示互互连网网络的特性的特性互互连网网络的性能参数的性能参数发送方的步骤如下:发送方的步骤如下:(1)(1)用户程序把要发送的数据拷贝到系统缓冲区。用户程序把要发送的数据拷贝到系统缓冲区。(2)(2)缓冲区中的数据打包并发送到网络接口部件。缓冲区中的数据打包并发送到网络接口部件。(3)(3)网络接口硬件开始发送消息。网络接口硬件开始发送消息。数据包的接收步骤如下:数据包的接收步骤如下:(1)(1)把数据包从网络接口部件拷贝到系统缓冲区。把数据包从网络接口部件拷贝到系统缓冲区。(2)(2)检查收到的数据包,如果正确,发回答信号。
4、检查收到的数据包,如果正确,发回答信号。(3)(3)把接收到的数据拷贝到用户地址空间。把接收到的数据拷贝到用户地址空间。发送方接收到回答信号后释放系统缓冲区发送方接收到回答信号后释放系统缓冲区互连网络的主要性能参数:互连网络的主要性能参数:(1)频带宽度频带宽度(Bandwidth):传输信息的最大速率:传输信息的最大速率(2)传输时间传输时间(Transmission time):等于消息长度除:等于消息长度除以频宽。以频宽。(3)飞行时间飞行时间(Time of flight):第一位信息到达接收方:第一位信息到达接收方所花费的时间。所花费的时间。(4)传输时延传输时延(Transport
5、 latency):等于飞行时间与传:等于飞行时间与传输时间之和。输时间之和。(5)发送方开销发送方开销(Sender overhead):处理器把消息放:处理器把消息放到互连网络的时间。到互连网络的时间。(6)接收方开销接收方开销(Receiver overhead):处理器把消息:处理器把消息从网络取出来的时间。从网络取出来的时间。一个消息的总时延可以用下面公式表示:一个消息的总时延可以用下面公式表示:总时延发送方开销飞行时间总时延发送方开销飞行时间 消息长消息长度度/频宽接收方开销频宽接收方开销例例7.1:假设一个网络的频宽为:假设一个网络的频宽为10Mb/S,发,发送方开销为送方开销为
6、230us,接收方开销分别为,接收方开销分别为270us。如果两台机器相距。如果两台机器相距100米,现在要米,现在要发送一个发送一个1000字节的消息给另一台机器,字节的消息给另一台机器,试计算总时延。如果两台机器相距试计算总时延。如果两台机器相距1000公公里,那么总时延为多大?里,那么总时延为多大?解解:光光的的速速度度为为299792.5KM/S,信信号号在在导导体体中中传递速度大约是光速的传递速度大约是光速的50。相距相距100米时总时延为:米时总时延为:相距相距1000公里时的总时延为:公里时的总时延为:为了在输入结点与输出结点之间建立对应为了在输入结点与输出结点之间建立对应关系,
7、互连网络有三种表示方法:关系,互连网络有三种表示方法:(1)互连函数表示法:互连函数表示法:如:如:f(xn-1x1x0)=x0 xn-2x1xn-1(2)图形表示法图形表示法(3)输入输出对应表示法输入输出对应表示法互连网络0011n-1n-1输入:0 1 2 3 4 5 6 7输出:1 0 3 2 5 4 7 6互互连网网络的表示方法的表示方法互互连函数函数互连函数也称为互连置换或互连排列等。1.交换函数(交换函数(Exchange)当n3时,有3种函数,每种能表示8个结点之间的连接关系。由于交换函数主要用于超超立立方方体体互互连连网网中,因此也称为超立方体函数,用Cube表示,如:Cub
8、e0、Cube1、Cube2等。2.2.全混洗函数(全混洗函数(Perfect shufflePerfect shuffle)函数关系:把二进制结点号循环左移一位函数关系:把二进制结点号循环左移一位子混洗子混洗(subshuffle)S(subshuffle)S(k)(k),最低最低k k位循环左移一位位循环左移一位 超混洗超混洗(supershuffle)S(supershuffle)S(k)(k),最高最高k k位循环左移一位位循环左移一位 3.蝶式函数(蝶式函数(Butterfly)蝶蝶式式函函数数的的名名称称来来自自于于FFT变变换换时时的的图图形形,如如蝴蝴蝶式样。函数关系:蝶式样。
9、函数关系:将将输输入入端端二二进进制制结结点点号号的最高位和最低位互换位置。的最高位和最低位互换位置。子蝶式子蝶式(subbutterfly)B(k)最低最低k位的位的高低位互换高低位互换超蝶式超蝶式(superbutterfly)B(k)最高最高k位的位的高低互换高低互换 显然成立:显然成立:4.反位序函数(反位序函数(Bit Reversal)函数关系:将二进制自变量的位序反过来。函数关系:将二进制自变量的位序反过来。子反位序函数,子反位序函数,最低最低k位的位的位序反过来位序反过来超反位序函数,超反位序函数,最高最高k位的位的位序反过来位序反过来5.移数函数移数函数函数关系:将输入端向量
10、循环移动一定的位置函数关系:将输入端向量循环移动一定的位置经经常常取取r2 2i i,因因此此移移数数函函数数又又称称为为加加减减2i函函数数、PM2I函数等。函数等。子移数函数:子移数函数:其中:其中:0 x N-1,0 i,k n-1,n=log2N。Illiac函数包含函数包含PM2 0和和PM2 n/2等等4个互连函数个互连函数 每个接点与它的上下左右每个接点与它的上下左右4个相邻接点连接个相邻接点连接例例6.2:假假设设16个个处处理理机机的的编编号号分分别别为为0、1、15,采采用用单单级级互互连连网网络络。互互连连函函数数分分别别为:为:(1)Cube3 (2)PM2+3 (3)
11、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号处理机号
12、处理机 1100的位序反过来为的位序反过来为0011,3号处理机号处理机 补充补充:基本的单级互连网络基本的单级互连网络1.立方体单级网络立方体单级网络立立方方体体的的每每个个顶顶点点代代表表一一个个结结点点,结结点点的的编编号号用用二二进制码(进制码(C2C1C0)表示。)表示。N8的三维立方体结构 立立方方体体单单级级网网络络的的互互连连函函数数实实现现二二进进制制编编号号中中第第k位位值值不不同同的的结结点点之之间间的的连连接接。故故三三维维的的立立方方体体单单级级网网络络有有三三种种互互连连函函数数:Cube0、Cube1和和Cube2,分分别别建建立立结结点点编编号号中中C0不不同同
13、或或C1不不同同或或C2不不同同的的结结点点之之间间的的连结。连结。N8的三维立方体三种互连方式的三维立方体三种互连方式一般情况下,一个一般情况下,一个n维立方体有维立方体有N2n个结个结点,共有点,共有n种互连函数,分别由种互连函数,分别由n位编号中的每位编号中的每一位的位值求反来确定。当维数一位的位值求反来确定。当维数n3时,称为时,称为超立方体超立方体(Hyper Cube)网络。对于网络。对于n维立方体维立方体单级网络,要实现任意两个结点之间的连接,单级网络,要实现任意两个结点之间的连接,最多需使用最多需使用n次不同的互连函数次不同的互连函数 因此因此n维立方维立方体单级网络的最大距离
14、为体单级网络的最大距离为n。2PM2I(是加减(是加减2i的简称,的简称,plusminus2i)PM2I单级网络能实现单级网络能实现j号结点与号结点与j2i mod N号结点号结点的直接相连,的直接相连,N为处理器的个数,为处理器的个数,nlog2N。因此,它。因此,它共有共有2n个互连函数,即个互连函数,即PM2i(j)j2i mod NPM2i(j)j2i mod N式中,式中,0jN1,0in1。设设N8,则各互连循环为,则各互连循环为PM20:(:(01234567)PM20:(:(76543210)PM21:(:(0246)()(1357)PM21:(:(6420)()(7531)
15、PM22:(:(04)()(15)()(26)()(37)N8的的PM2I互连网络的部分连接图互连网络的部分连接图 网网络络的的最最大大距距离离为为 n/2 =log2N/2 ,这这里里 表表示示向向上上取取整整。由由三三维维PM2I互互连连网网络络可可以以看看出出,最最多多只要两次使用,即可实现任意一对入出端号间的连接。只要两次使用,即可实现任意一对入出端号间的连接。PM2I互连特性互连特性3.3.混洗交换混洗交换(shuffle exchange)(shuffle exchange)混洗交换互连网络包含全混洗和交换两种互连函数。混洗交换互连网络包含全混洗和交换两种互连函数。(1 1)全混洗
16、)全混洗全混洗的互连函数为全混洗的互连函数为ShuffleShuffle(P Pn n1 1P Pn n2 2PP1 1P P0 0)P Pn n2 2PP1 1P P0 0P Pn n1 1 全混洗互连示意图全混洗互连示意图(2)交换)交换由于单一的全混洗互连网络不能实现二进制编号为全由于单一的全混洗互连网络不能实现二进制编号为全“0”和全和全“1”的结点与其他任何结点的连接,所以又增加了的结点与其他任何结点的连接,所以又增加了Cube0交换互连函数。同时采用了全混洗和交换的单级互连网络称为混交换互连函数。同时采用了全混洗和交换的单级互连网络称为混洗交换单级互连网络。洗交换单级互连网络。N8
17、的全混交换互连网络连接图的全混交换互连网络连接图 在在混混洗洗交交换换网网络络中中,最最远远的的两两个个入入出出端端号号是是全全“0”和和全全“1”,它们的连接需要,它们的连接需要n次交换和次交换和n-1次混洗,所以其最大距离为次混洗,所以其最大距离为2n-1。互互连网网络的种的种类静静态互互连网网络 循循环互互连网网络多多级互互连网网络静静态态互互连连网网络络:在在各各结结点点之之间间有有固固定定的的连连接接通通路路,在在运运行行过过程程中中不不能能改改变变。一一般般不不能能实实现现任任意意结结点点到到结结点点之之间的互连。间的互连。循环互连网络:通过多次重复使用同一个单级互连网络循环互连网
18、络:通过多次重复使用同一个单级互连网络以实现任意结点到结点之间的互连以实现任意结点到结点之间的互连。多级互连网络:将多套相同的单级互连网络连接起来,多级互连网络:将多套相同的单级互连网络连接起来,实现任意结点到结点之间的互连,是动态互连网络的实现任意结点到结点之间的互连,是动态互连网络的一种,适用于一种,适用于SIMD和和MIMD。静静态互互连网网络 在各结点之间有固定的连接通路,在运行过程中不能在各结点之间有固定的连接通路,在运行过程中不能改变的网络结构。改变的网络结构。一般静态互连网络不能实现任意结点到结点之间的互连。一般静态互连网络不能实现任意结点到结点之间的互连。一维的有线性阵列结构;
19、二维的有环形、星形、树形、一维的有线性阵列结构;二维的有环形、星形、树形、网格形等;三维的有立方体等;三维以上的有超立方网格形等;三维的有立方体等;三维以上的有超立方体等。体等。循循环互互连网网络一般静态互连网不能实现任意两结点之间的互连。一般静态互连网不能实现任意两结点之间的互连。有两种解决办法:有两种解决办法:循环互连网:多次重复使用同一个单级互连网络循环互连网:多次重复使用同一个单级互连网络多级互连网:将多套相同的单级互连网络连接起来多级互连网:将多套相同的单级互连网络连接起来前一种方法是牺牲时间换取设备,后一种方法是以前一种方法是牺牲时间换取设备,后一种方法是以设备换取时间。设备换取时
20、间。多多级互互连网网络 多级网络互连是将多套单级互连网络通过关模块多级网络互连是将多套单级互连网络通过关模块串连扩展成多级互连网络(简称串连扩展成多级互连网络(简称MINMIN)的方式。与单)的方式。与单级网络相比,多级网络可以通过改变开关的控制方式级网络相比,多级网络可以通过改变开关的控制方式灵活地实现各种连接,满足系统应用的需要灵活地实现各种连接,满足系统应用的需要 。多级互连网络采用多个相同的或不同的单级互连多级互连网络采用多个相同的或不同的单级互连网络直接连接起来。一个时钟周期就能够实现任意结网络直接连接起来。一个时钟周期就能够实现任意结点到结点之间的互连。点到结点之间的互连。常见的有
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 并行 计算机体系结构 第六 课件
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内