川大学系统结构第六章.ppt

《川大学系统结构第六章.ppt》由会员分享，可在线阅读，更多相关《川大学系统结构第六章.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章第六章 互连网络互连网络6.1 互连网络的基本概念互连网络的基本概念6.2 静态互连网络静态互连网络6.3 动态互连网络动态互连网络6.1 互连网络的基本概念互连网络的基本概念一一.互连网络的功能互连网络的功能1什么是互连网络什么是互连网络?n从广义上讲，凡是用以实现部件、设备或系统从广义上讲，凡是用以实现部件、设备或系统之间连接用的部件都可以称为互连网络。之间连接用的部件都可以称为互连网络。n狭义上讲，互连网络是一种由开关元件按一定狭义上讲，互连网络是一种由开关元件按一定的拓扑结构和控制方式构成的网络，用来实现的拓扑结构和控制方式构成的网络，用来实现计算机系统内部多处理机或多功能部件之

2、间的计算机系统内部多处理机或多功能部件之间的相互连接。相互连接。它通过硬件线路，实现设备之间的连接；通过它通过硬件线路，实现设备之间的连接；通过开关选择，构成一对一或一对多的信息通路。开关选择，构成一对一或一对多的信息通路。6.1 互连网络的基本概念互连网络的基本概念 系统存储器部件系统存储器部件 控制控制 处理机处理机 数据传数据传 送部件送部件 主存储器主存储器 标量部件标量部件 数据传数据传 送部件送部件 主存储主存储 器部件器部件 量部件量部件 向量标向量标 处理部件处理部件 1 2 222 1 224224交叉开关交叉开关 处理部件处理部件 VP2000 二级二级 存储器存储器 数据

3、传数据传 送部件送部件 主存储器主存储器 标量部件标量部件 数据传数据传 送部件送部件 主存储主存储 器部件器部件 量部件量部件 向量标向量标互连网络互连网络富士通富士通VPP500VPP500并行向量处理机并行向量处理机:更为一般的系统：更为一般的系统：存储器存储器存储器存储器存储器存储器处处理理机机存存储储器器网网络络m12共共享享存存储储器器处理机间网络处理机间网络处理机处理机存储器存储器处理机处理机存储器存储器处处理理机机外外设设网网络络磁带设备磁带设备磁盘设备磁盘设备 打印设备打印设备 网网 络络共共享享外外设设 系统以多处理机为核心，各处理机有自己专用系统以多处理机为核心，各处理机

4、有自己专用的存储器，称为的存储器，称为本地存储器本地存储器，处理机内包含有，处理机内包含有独用的独用的Cache。此外还有各处理机公用的存储。此外还有各处理机公用的存储器，称为器，称为共享存储器共享存储器，各处理机对共享存储器，各处理机对共享存储器的访问通过处理机的访问通过处理机存储器网络进行交换。存储器网络进行交换。6.1 互连网络的基本概念互连网络的基本概念2互连网络的主要功能互连网络的主要功能1）连接各个结点，构成信息通路，传送数据或控）连接各个结点，构成信息通路，传送数据或控制命令。制命令。2）通过路径选择，实现有目的的信息交换，其中）通过路径选择，实现有目的的信息交换，其中包括一到一

5、和一到多的选择与交换。包括一到一和一到多的选择与交换。6.1 互连网络的基本概念互连网络的基本概念二二.互连网络的主要特性互连网络的主要特性1）网络规模）网络规模：即一个网络中所连接的结点数。：即一个网络中所连接的结点数。2）结点度）结点度：每个结点与外部连接的边数称为一个：每个结点与外部连接的边数称为一个结点的度，用结点的度，用d表示。表示。结点结点A结点结点B线路线路(b)双向双向结点结点A结点结点B线路线路(a)单单向向6.1 互连网络的基本概念互连网络的基本概念3）距离）距离：任意两结点之间相连的最少边数。：任意两结点之间相连的最少边数。4）网络直径（）网络直径（D）：网络中任意结点之

6、间距离中：网络中任意结点之间距离中的最大值。的最大值。BACDAB的距离的距离:1 AC的距离的距离:1 AD的距离的距离:1BC的距离的距离:2 BD的距离的距离:1 CD的距离的距离:1网络直径网络直径:D=25）结点间线长结点间线长：两个结点之间实际连接用的线长。：两个结点之间实际连接用的线长。6.1 互连网络的基本概念互连网络的基本概念6）等分宽度）等分宽度：n通道等分宽度：通道等分宽度：一个网络被切割成对等的两半一个网络被切割成对等的两半时，沿切口所具有的边数（通道数），称为通时，沿切口所具有的边数（通道数），称为通道等分宽度，用道等分宽度，用k表示。表示。n线等分宽度：线等分宽度：

7、若用若用w表示通道宽度（用位表示）表示通道宽度（用位表示），则线等分宽度为：，则线等分宽度为：B=kw。7）对称性）对称性：如果从任一个结点观察网络，所看到：如果从任一个结点观察网络，所看到的网络拓扑结构都是相同的，该网络是一个对的网络拓扑结构都是相同的，该网络是一个对称网络。称网络。8）数据寻经功能：）数据寻经功能：表示互连网络把数据从一端传表示互连网络把数据从一端传送到另一端的方式和能力。寻径方式分为静态送到另一端的方式和能力。寻径方式分为静态和动态两种。寻径功能有一到一、一到多、散和动态两种。寻径功能有一到一、一到多、散射、汇合射、汇合/聚集等。聚集等。6.1 互连网络的基本概念互连网络

8、的基本概念三三.互连函数互连函数1互连网络的功能表示互连网络的功能表示 无论何种互连网络，在系统中所起的作无论何种互连网络，在系统中所起的作用都是一样的，用都是一样的，即进行有关部件（或设备）即进行有关部件（或设备）间的有效连接，完成信息的传输。间的有效连接，完成信息的传输。如果将互连网络看作一个黑盒子，盒如果将互连网络看作一个黑盒子，盒子的输出端口与输入端口间就存在一定的子的输出端口与输入端口间就存在一定的位置变换关系，这就是位置变换关系，这就是互连函数互连函数。6.1 互连网络的基本概念互连网络的基本概念 特别应该强调指出，这里所谓的变换关系并不特别应该强调指出，这里所谓的变换关系并不是信

9、号形式的变换，而只是端口位置的变换关是信号形式的变换，而只是端口位置的变换关系，所以用以表征黑盒子特性的不是传输函数，系，所以用以表征黑盒子特性的不是传输函数，而是互连函数。而是互连函数。互连网络互连网络f(i)12N 1 2 N6.1 互连网络的基本概念互连网络的基本概念 2.互连函数表示法互连函数表示法 1）函数表示法：）函数表示法：在函数表示法中，通常用在函数表示法中，通常用x表示输入端变量（即端表示输入端变量（即端口编号），口编号），f(x)就用以表示互连函数。其中就用以表示互连函数。其中x常用常用端口编号的二进制值表示，端口编号的二进制值表示，x=xn-1 xn-2 x1 x0。而相

10、应的互连函数就可以写成：而相应的互连函数就可以写成：f(xn-1 xn-2 x1 x0)。如果变换函数发生了变化，其表示也就可以。如果变换函数发生了变化，其表示也就可以相应的写成：相应的写成：(xn-1 xn-2 x1 x0)。一个完整的函数就应在其等式的右边写出该函数的一个完整的函数就应在其等式的右边写出该函数的值，即变换的结果。例如：值，即变换的结果。例如：(xn-1 xn-2 x1 x0)=xn-2 xn-3 x1 x0 xn-16.1 互连网络的基本概念互连网络的基本概念 2）输入输出对应表示法：）输入输出对应表示法：即列出对应端口间的对应关系表，输入输即列出对应端口间的对应关系表，输

11、入输出对应关系列出在符号框内，其表示形式为：出对应关系列出在符号框内，其表示形式为：在符号框内，上一个元素与下一个元素分别对应在符号框内，上一个元素与下一个元素分别对应输入与输出的连接关系。输入与输出的连接关系。3）图形表示法）图形表示法 图形表示法是直接用连线将输入与输出的关系连图形表示法是直接用连线将输入与输出的关系连接在一起，非常直观。其缺点是不容易从中看出接在一起，非常直观。其缺点是不容易从中看出规律性的东西，即函数关系不能一目了然。规律性的东西，即函数关系不能一目了然。6.1 互连网络的基本概念互连网络的基本概念 3.基本互连函数基本互连函数 1）恒等互连函数）恒等互连函数 如果相同

12、输入如果相同输入/输出编号的端口对应互连，所实现输出编号的端口对应互连，所实现的变换称为恒等变换。其表示式为：的变换称为恒等变换。其表示式为：I(xn-1xn-2x1x0)=xn-1xn-2x1x0000001010011100101110111000001010011100101110111 等式左边和右边端口编号等式左边和右边端口编号的二进制编码完全相等。的二进制编码完全相等。图形表示的恒等变换如右图形表示的恒等变换如右图所示：图所示：6.1 互连网络的基本概念互连网络的基本概念 2）交换互连函数）交换互连函数 将输入端口编号的二进制码中的第将输入端口编号的二进制码中的第0位取反，得到位取

13、反，得到的互连函数称为交换互连函数。其表示式为：的互连函数称为交换互连函数。其表示式为：0000010100111001011101110000010100111001011101112-()1210101nnnnxxxxxxxxE-=6.1 互连网络的基本概念互连网络的基本概念 3）方体互连函数）方体互连函数 将输入端口编号的二进制码内的某一位（第将输入端口编号的二进制码内的某一位（第k位）位）作取反操作，所得的值就是与之相连的输出端口作取反操作，所得的值就是与之相连的输出端口编码。其表示式为：编码。其表示式为：如果输入端口有如果输入端口有N个，每个端口编号的二进个，每个端口编号的二进制编码

14、就有制编码就有n=log2 N位，位，k可以是其中的可以是其中的任意一位，所以方体变换也就可以有任意一位，所以方体变换也就可以有n种。种。按照被变换位的位置，分别可以表示成：按照被变换位的位置，分别可以表示成：C0，C1，Cn-1等。等。()011121011121xxxxxxxxxxxxxxCkkknnkkknnk-+-+-=6.1 互连网络的基本概念互连网络的基本概念 比如，网络结点比如，网络结点N=8时，允许有三种方体互连函数，他们分别时，允许有三种方体互连函数，他们分别是：是：()0120120 xxxxxxC=()0120121xxxx xxC=()0120122xxxxxxC=(c

15、)C2方体方体 (a)C0方体方体000001010011100101110111 (b)C1方体方体0000010100111001011101110000010100111001011101110000010100111001011101110000010100111001011101110000010100111001011101116.1 互连网络的基本概念互连网络的基本概念 4）均匀洗牌（全混洗）互连函数）均匀洗牌（全混洗）互连函数 均匀洗牌互连函数是将输入端分为数目相同的两均匀洗牌互连函数是将输入端分为数目相同的两个部分，分别与输出端进行均匀洗牌，即一个隔个部分，分别与输出端进行均

16、匀洗牌，即一个隔一个地与输出端相连。函数表示式为：一个地与输出端相连。函数表示式为：()101320121-=nnnnnxxxxxxxxxS 均匀洗牌互连函数均匀洗牌互连函数0000010100111001011101110000010100111001011101116.1 互连网络的基本概念互连网络的基本概念 循环移位也可以由左移改为循环移位也可以由左移改为右移，这时就成了逆均匀洗右移，这时就成了逆均匀洗牌，这种方式可以看作是均牌，这种方式可以看作是均匀洗牌的逆函数。函数表达匀洗牌的逆函数。函数表达式为：式为：()121001211xxxxxxxxnnnn-=S 逆均匀洗牌逆均匀洗牌000

17、001010011100101110111000001010011100101110111 5）PM2I互连函数互连函数 “加减加减2i”互连函数也称为循环移数互连函数，其移数互连函数也称为循环移数互连函数，其移数的值为的值为2的某一个幂次。其表示式为：的某一个幂次。其表示式为：式中，式中，0 X N-1，0 i n 1，n=log2N，N为网络结点数。为网络结点数。即：结点数为即：结点数为N的网络，其的网络，其PM2IPM2I互连函数的个数为互连函数的个数为2 2n n，（n n=log=log2 2N N）。）。()()NXXiimod2PM2I+=+()()NXXiimod2PM2I-=

18、-6.1 互连网络的基本概念互连网络的基本概念按互连函数画出的图形如下图所示。按互连函数画出的图形如下图所示。012345670123456701234567012345670123456701234567(a)i=0(b)i=+1(c)i=+26.1 互连网络的基本概念互连网络的基本概念6.1 互连网络的基本概念互连网络的基本概念 6）蝶式互连函数蝶式互连函数 将输入端编号的二进制码的最高位和最低位对将输入端编号的二进制码的最高位和最低位对调，所得的二进制编码就是与之相连的输出端口调，所得的二进制编码就是与之相连的输出端口编号，这种连接称为蝶式置换。其函数表示式为：编号，这种连接称为蝶式置换

19、。其函数表示式为：()11200121-=nnnnxxxxxxxxB0000010100111001011101110000010100111001011101116.1 互连网络的基本概念互连网络的基本概念 7）混洗交换互连函数混洗交换互连函数 就是由全混洗互连函数与交换互连函数构成的就是由全混洗互连函数与交换互连函数构成的复合函数，其函数表示式为：复合函数，其函数表示式为：()1020121-=nnnnxxxExxxxSE102-=nnxxx6.1 互连网络的基本概念互连网络的基本概念 例：设有例：设有64个处理器，其编号依次是个处理器，其编号依次是0，1，2，63。当按照互连函数。当按照

20、互连函数Exchange()4连接时连接时,第第21号处理器应与哪个处理器连接号处理器应与哪个处理器连接?解解:设待求处理器的序号为设待求处理器的序号为i，表示为，表示为Pi，则，则 Pi=Exchange(010101)4 =010101 =000101 所以，第所以，第21号处理器应与第号处理器应与第5号处理器连接。号处理器连接。6.2 静态互连网络静态互连网络 静态互连网络是指在点到点之间使用直接链静态互连网络是指在点到点之间使用直接链路，一旦设计成功，固定不变。即使在工作过路，一旦设计成功，固定不变。即使在工作过程中，也不能用程序改变。程中，也不能用程序改变。系统中的每一个结点往往不止

21、只连接一个相系统中的每一个结点往往不止只连接一个相邻结点，即结点的度往往大于邻结点，即结点的度往往大于1。于是在信息传。于是在信息传递时，就必须解决正确选择通信对象的问题。递时，就必须解决正确选择通信对象的问题。为此，每个结点中都必须设置为此，每个结点中都必须设置“寻径器寻径器”，所，所以，这种网络又被称作以，这种网络又被称作基于寻径器的网络基于寻径器的网络。6.2 静态互连网络静态互连网络一一.网络拓扑结构网络拓扑结构n线性阵列线性阵列 0 1 2 N-1 N-2 N-3网络直径：网络直径：N-1n环和带弦环环和带弦环 012 3 4 56 7 8 910111213 14 15（a）环形网

22、）环形网单向连接时，网络直径：单向连接时，网络直径：双向连接时，网络直径：双向连接时，网络直径：N-1N/2网络直径越大，传输延时越大网络直径越大，传输延时越大6.2 静态互连网络静态互连网络n环和带弦环环和带弦环 012 3 4 5 6 7 89101112 13 14 15(b)3度度带带弦弦环环形网络形网络 012 3 4 56 7 8 910111213 14 15(c)4度度带带弦弦环环形网络形网络 01 2 3 4 5 6 7 89101112 13 1415（a）环形网）环形网网络直径为网络直径为5 网络直径为网络直径为36.2 静态互连网络静态互连网络n循环移数网络循环移数网络

23、 这也是通过在环形网络结构上增加这也是通过在环形网络结构上增加“弦弦”的方的方法使直径减小的改进网络。只是，加弦的规律法使直径减小的改进网络。只是，加弦的规律是：是：从任一结点出发与距该结点距离为从任一结点出发与距该结点距离为2的整数的整数幂结点相连幂结点相连 01 2 3 4 5 6 7 8 91011 12 13 14 15 网络直径为网络直径为26.2 静态互连网络静态互连网络n树形与胖树形树形与胖树形二叉树结构网络二叉树结构网络二叉胖树结构网络二叉胖树结构网络6.2 静态互连网络静态互连网络n网格形和环形网格网格形和环形网格(c)环形网格环形网格(a)网格形网格形(b)Illiac网网

24、6.2 静态互连网络静态互连网络n超立方体和带环立方体超立方体和带环立方体(c)带环立方体带环立方体(a)3维立方体维立方体(b)4维立方体维立方体6.2 静态互连网络静态互连网络二二.静态网络特性表静态网络特性表6.3 动态互连网络动态互连网络 动态互连网络使用开关或者裁决器提供动态动态互连网络使用开关或者裁决器提供动态连接特性，在运行过程中由程序来确定具体连接特性，在运行过程中由程序来确定具体的连接方式。的连接方式。一一.总线互连方式总线互连方式n总线互连方式是多处理机实现互连的一种最总线互连方式是多处理机实现互连的一种最简单的方式。简单的方式。n在总线互连方式中，多个处理机、存储模块在总

25、线互连方式中，多个处理机、存储模块及及I/O部件等通过各自的接口部件连接在一条部件等通过各自的接口部件连接在一条公共总线上，或多个计算机模块通过各自的公共总线上，或多个计算机模块通过各自的接口部件与一条总线连接。接口部件与一条总线连接。6.3 动态互连网络动态互连网络二二.交叉开关互连方式交叉开关互连方式 交叉开关互连方式通过开关把多个处理机、存交叉开关互连方式通过开关把多个处理机、存储器模块或其他储器模块或其他I/O设备连接在一起，形成一设备连接在一起，形成一种网络结构种网络结构。P1 P2 P16 M1 M2 M16网络中行线和列线交叉点网络中行线和列线交叉点有开关控制其接通与否。有开关控

26、制其接通与否。每个开关只需两种状态：每个开关只需两种状态：通与断。通与断。6.3 动态互连网络动态互连网络三三.多级网络互连方式多级网络互连方式 是把多个单级互连网络通过交换开关或交叉开关串是把多个单级互连网络通过交换开关或交叉开关串联起来而构成的网络。联起来而构成的网络。ab开关开关ab开关开关ab开关开关ab开关开关ab开关开关ab开关开关ab开关开关ab开关开关ab开关开关ISC1ISC2ISCn第第1级级第第n-1级级01b-1b2b-1b+1bm-bbm-1第第0级级01a-1aa+12a-1am-aam-1构成多级互连网络的三要素：构成多级互连网络的三要素：1 1）交换开关）交换开

27、关2 2）拓扑结构）拓扑结构3 3）控制方式）控制方式6.3 动态互连网络动态互连网络（）交换开关（）交换开关n简单开关逻辑简单开关逻辑 C 0 0 1 16.3 动态互连网络动态互连网络n22开关的四种连接方式开关的四种连接方式0011 (a)直送直送0011 (b)交叉交叉0011 (c)上播上播0011 (d)下播下播图中表示了直通、交叉、上播和下播四种允图中表示了直通、交叉、上播和下播四种允许的状态，称为合法状态。如果出现两个输许的状态，称为合法状态。如果出现两个输入端连接到同一个输出端的状态，就会造成入端连接到同一个输出端的状态，就会造成信号的冲突，此状态为非法。信号的冲突，此状态为

28、非法。6.3 动态互连网络动态互连网络n开关模块的合法状态开关模块的合法状态 输入与输出之间只有一对一的输入与输出之间只有一对一的关系关系,即排除了上播和下播的可即排除了上播和下播的可能性时的连接能性时的连接.6.3 动态互连网络动态互连网络（2）控制方式）控制方式对开关的控制方式有三种不同的控制方式：对开关的控制方式有三种不同的控制方式：1）级控制级控制 即每一级中所有的开关模块使用同一个控制信号，所以该级中的即每一级中所有的开关模块使用同一个控制信号，所以该级中的每一个开关都处于同一种状态。每一个开关都处于同一种状态。2）单元控制单元控制 系统中的每一个开关模块都有自己专用的控制信号，实施

29、个别控系统中的每一个开关模块都有自己专用的控制信号，实施个别控制，各开关均可处于自己特定的状态。制，各开关均可处于自己特定的状态。3）部分级控制部分级控制 在一个在一个n级的网络中，取级的网络中，取0 i n 1，第，第i级的所有开关用级的所有开关用i+1个信号进行控制。个信号进行控制。四四.几种主要多级网络几种主要多级网络1（Omega）网络（多级混洗交换网络）网络（多级混洗交换网络）n一个用若干级全混洗网络将开关连接起来组成一个用若干级全混洗网络将开关连接起来组成的多级网络称为的多级网络称为网络。网络。n由于采用全混洗网络是这个多级网络组织的基由于采用全混洗网络是这个多级网络组织的基本特色

30、，所以本特色，所以网络又称为网络又称为多级混洗交换网络。多级混洗交换网络。1 2 0 3 4 5 6 7 1 2 0 3 4 5 6 7输输入入端端输输出出端端C3 C1 C0 C2 K2 K1 K0网络中，开关采用的是网络中，开关采用的是单元控制单元控制方式。方式。6.3 动态互连网络动态互连网络2STARAN网络网络 1 2 0 3 4 5 6 7 1 2 0 3 4 5 6 7输输入入端端输输出出端端 C0C2C3C1 K0 K1 K2 I A B C D E G F H J K L STARAN网络的开关可以按级控制，也可以网络的开关可以按级控制，也可以按组控制。按组控制。fi 0 0

31、 1 16.3 动态互连网络动态互连网络n按级控制方式按级控制方式以级为单位，即一个控制信号可以级为单位，即一个控制信号可对一级中的全部开关作同样的控制。按级控制对一级中的全部开关作同样的控制。按级控制方式可以实现输入输出端的交换置换，这时的方式可以实现输入输出端的交换置换，这时的网络又可以称作交换网络。网络又可以称作交换网络。n按组控制方式按组控制方式则是将第则是将第i级的开关分成级的开关分成i+1组，组，给每组施以控制信号，使组内各开关产生同样给每组施以控制信号，使组内各开关产生同样的动作。按组控制方式可以实现移数置换，这的动作。按组控制方式可以实现移数置换，这时可以称作移数网络。时可以称

32、作移数网络。6.3 动态互连网络动态互连网络 按级控制和交换置换按级控制和交换置换 在右上图有一个开关控制示意图，假定开关在右上图有一个开关控制示意图，假定开关的两个输入端分别标注以的两个输入端分别标注以“0”和和“1”，同样，同样也给输出端标上也给输出端标上“0”和和“1”的标注。在直送的标注。在直送方式下，方式下，00，11；而在交叉方式下，则；而在交叉方式下，则有有01，10。如果将这种传输情况看作二。如果将这种传输情况看作二进制运算，那末控制信号进制运算，那末控制信号fi就是参与逻辑运算就是参与逻辑运算的一个变量，其逻辑关系可以表示为：的一个变量，其逻辑关系可以表示为：fi 0 0 1

33、 1iiifxxE=)(fi=0时，表示直送；时，表示直送；fi=时，表示交叉。时，表示交叉。除了除了F=（000）时，实现的是恒）时，实现的是恒等置换外，其余等置换外，其余7种种F值所实现的值所实现的是交换式的置换。比如，是交换式的置换。比如，F=（010）时，输入与输出都分成）时，输入与输出都分成从从03和和47两组，在对应组中进两组，在对应组中进行前两位与后两位之间的位置交行前两位与后两位之间的位置交换。换。F=(101)01234567012345670123456701234567F=(010)0123456701234567F=(011)0123456701234567F=(100

34、)0123456701234567F=(110)0123456701234567F=(111)0123456701234567F=(001)0123456701234567F=(000)也就是说，也就是说，STARAN网络所实现的正是输入与输出端之网络所实现的正是输入与输出端之间的三种方体置换，而且他们分别实现的是间的三种方体置换，而且他们分别实现的是C0、C1和和C2置换。非常有意思的是，置换。非常有意思的是，C0 是是 f0=1 时得到的置换，时得到的置换，C1 是是 f1=1 时得到的置换，同样，时得到的置换，同样，C2 是是 f2=1 时得到时得到的置换。因此，的置换。因此，STARA

35、NSTARAN网络网络又称为多立方体网络。又称为多立方体网络。由此推出的结论是：当由此推出的结论是：当fi=1时，就有时，就有Ci置换。置换。于是，如果于是，如果F=（011），就有），就有C0置换，再有置换，再有C1置换，置换，简写成：简写成：C1（C0），或者），或者Cube0+Cube1。6.3 动态互连网络动态互连网络 按组控制及移数置换按组控制及移数置换n在在NN的的STARAN网络中，第网络中，第i级的开关分成级的开关分成i+1组，每组一个控制信号。对于组，每组一个控制信号。对于N=8时，共时，共3级开关级开关K0，K1，K2，共包含有，共包含有6个控制信号：个控制信号：F=（f2

36、3 f22 f21 f12 f11 f0）。）。n一个一个NN的的STARAN网络，在采用按组控制网络，在采用按组控制后，可以实现后，可以实现(n+n+2)/2种移数置换。种移数置换。N=8时，可实现的移数置换为时，可实现的移数置换为7种。种。第七章第七章 多处理机多处理机n1986-2002年间，随着微处理器的发展，单处年间，随着微处理器的发展，单处理机的性能增长达到了顶峰。理机的性能增长达到了顶峰。n2002年以后，单处理机的性能增长明显放缓。年以后，单处理机的性能增长明显放缓。主要原因有：主要原因有：（1）功耗问题（已经很大）。）功耗问题（已经很大）。（2）可以进一步有效开发的）可以进一

37、步有效开发的指令级并行性指令级并行性已经很已经很少。少。n近两年来，我们已经开始进入近两年来，我们已经开始进入多处理机多处理机将起主将起主要作用的新时期。要作用的新时期。第七章第七章 多处理机多处理机一、并行计算机系统结构的分类一、并行计算机系统结构的分类1.Flynn1.Flynn分类法：分类法：SISD SISD、SIMDSIMD、MISDMISD、MIMDMIMD2.SISD2.SISD：主要指：主要指单处理机单处理机，标量流水线处理机是，标量流水线处理机是利用利用时间重叠原理时间重叠原理实现其并行性实现其并行性 3.SIMD3.SIMD：主要指：主要指并行处理机并行处理机，也称为阵列处

38、理机。，也称为阵列处理机。n阵列处理机是阵列处理机是操作级并行操作级并行的的SIMDSIMD计算机。计算机。n主要用于对向量和数组进行高速运算的场合主要用于对向量和数组进行高速运算的场合n典型代表：典型代表：ILLIAC IVILLIAC IV阵列处理机阵列处理机4.MIMD4.MIMD：主要指：主要指多处理机多处理机第七章第七章 多处理机多处理机二、多处理机的相关概念二、多处理机的相关概念n多处理机是由多台独立的计算机组成，多处理机是由多台独立的计算机组成，每一台计算机可以独立工作，执行其内每一台计算机可以独立工作，执行其内部的程序，对数据进行处理。部的程序，对数据进行处理。n各处理机可以各

39、处理机可以并行并行工作，共同完成某一工作，共同完成某一项大的计算或处理任务，相互之间通过项大的计算或处理任务，相互之间通过专门的网络连接，实现数据的交换与通专门的网络连接，实现数据的交换与通信。信。n多处理机的并行性是建立在程序段的基多处理机的并行性是建立在程序段的基础上，即础上，即作业或任务级的并行性。作业或任务级的并行性。第七章第七章 多处理机多处理机三三.多处理机的分类：多处理机的分类：包括两种系统结构：包括两种系统结构：n对称式共享存储器系统结构对称式共享存储器系统结构n分布式共享存储器系统结构分布式共享存储器系统结构第七章第七章 多处理机多处理机四、多处理机并行处理面临着重要的挑战四

40、、多处理机并行处理面临着重要的挑战 1.程序中的并行性有限，有限的并行性使机器程序中的并行性有限，有限的并行性使机器要达到好的加速比十分困难。要达到好的加速比十分困难。通常，假设程序只在两种模式下运行：使用所通常，假设程序只在两种模式下运行：使用所有处理器的并行模式和只用一个处理器的串行有处理器的并行模式和只用一个处理器的串行模式。那么在并行模式下的理论加速比即为处模式。那么在并行模式下的理论加速比即为处理器的个数，可加速部分的比例即为并行部分理器的个数，可加速部分的比例即为并行部分所占的比例。所占的比例。例：例：假设想用假设想用100100个处理器达到个处理器达到8080的加速比，求的加速比，求原计算程序中串行部分最多可占多大的比例？原计算程序中串行部分最多可占多大的比例？解：解：AmdahlAmdahl定律为定律为可得：可得：并行比例并行比例99.75%99.75%，即，即串行比例串行比例=0.25%=0.25%2.相对较高的通信开销相对较高的通信开销 主要指多处理机中远程访问的较大延迟。主要指多处理机中远程访问的较大延迟。