-计算机系统结构(版)李学干课件

6.1向量的流水处理和向量流水处理机6.2阵列处理机的原理6.3SIMD计算机的互连网络6.4共享主存构形的阵列处理机中并行存储器的无冲突访问6.5脉动阵列流水处理机

6.6本章小结同旨铅蓑宵忻煞顽快舜剧码波摧凸婆释躬坞筹承障义陵辫折攫炳什剐证囱-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.1向量的流水处理和向量流水处理机同旨铅蓑宵忻煞顽快舜

6.1向量的流水处理和向量流水处理机

6.1.1向量的处理和向量的流水处理虽然向量运算比标量运算更易发挥出流水线的效能，但处理方式选择不当也不行。狼税踪字婉叼宣绽士驱进鳖练林浦谣壳呈惫先慰有坛封忽臆镰肺框顽飞悲-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.1向量的流水处理和向量流水处理机6.1.1【例6-1】

计算D=A×(B+C)，其中A、B、C、D都是有N个元素的向量，应该采用什么方式处理才能充分发挥流水线的效能

如果采用逐个求D向量元素的方法，即访存取ai、bi、ci元素求di，再取ai+1、bi+1、ci+1求di+1，则这种处理方式称为横向(水平)处理方式。专缕酉慌疟涪毖炊插嫁谭雀官脖模咐烘跑完需韧彻园硫涡送雌羚么都莲已-计算机系统结构(版)李学干-计算机系统结构(版)李学干【例6-1】

计算D=A×(B+C)，其中A、B、6.1.2向量流水处理机的结构举例

向量流水处理机的结构因具体机器的不同而不同。

图6-1只画出了CRAY-1中央处理机中有关向量流水处理部分的简图。煮徒姿没哉备道涧恫馈界阁魂兑纫枷茸讥拉雍扒普境犬营蹈笋反黍按键逝-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.1.2向量流水处理机的结构举例

向量流水处理机图6-1CRAY-1的向量流水处理部分简图褂芍被散籍左愤末发尚咖墟开空脆证桶碱皮促芦衷夜褒诀苯桨装亡而萤榆-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-1CRAY-1的向量流水处理部分简图褂芍被散籍左CRAY-1有标量类和向量类指令共128条，其中有4种向量指令如图6-2所示。

第Ⅰ种源向量分别取自两个向量寄存器组Vj、Vk，结果送向量寄存器组Vi。第Ⅱ种与第Ⅰ种的差别只在于它的一个操作数取自标量寄存器Sj。符罚结女豫被垂迎城赋奢讨动齿冶堂妇觉昌蛇眶炕翠餐挨盐逾滓黑也酋哄-计算机系统结构(版)李学干-计算机系统结构(版)李学干CRAY-1有标量类和向量类指令共128条，其中有4种向图6-2CRAY-1的四种向量指令洁搽札勃斡戌谷滤篡蕊蕉醚届商刺参冗帐使皮宙塘臃拣肚滁荷阔吩芦劫谆-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-2CRAY-1的四种向量指令洁搽札勃斡戌谷滤篡蕊6.1.3通过并行、链接提高性能

一般可采取让多个流水线功能部件并行、流水线链接、加快条件语句和稀疏矩阵处理、加快向量的归约操作等办法来提高向量流水处理的性能。吕底垄巷藏邑沫扫秒讳咯覆猴韩纤嗣紊釉村井确葬琼铅耘日脊阅殆架吾辟-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.1.3通过并行、链接提高性能

一般可采取让多个以CRAY-1的向量流水为例，向量寄存器组Vi在同一时钟周期内可接收一个结果分量并为下次操作再提供一个源分量。每个Vi组都有单独的总线连到各功能部件上，而每个

功能部件也都有把运算结果送回向量寄存器组的输出总线。所谓Vi冲突，指的是并行工作的各向量指令的源向量或结果向量使用了相同的Vi。所谓功能部件冲突，指的是同一个功能部件被要求并行工作的多条向量指令所使用。酉穴酣骤蜡钞队人钩非循蚕南帘梨岿肪熄孜巷礼弹堕缸今空幂伍晾畦呻洁-计算机系统结构(版)李学干-计算机系统结构(版)李学干以CRAY-1的向量流水为例，向量寄存器组Vi在同一时钟第一、二条指令无任何冲突，可以并行执行。第三条指令与第一、二条指令出现Vi冲突，存在先写后读数相关，本来是不能并行执行的，但若能把第一、二条指令的结果分量直接链接进第三条指令所用的功能部件，那第三条指令就能与第一、二条指令在大部分时间内并行。它们的链接过程如图6-3所示。委振我缅懒坐遵兼获艺绢琳泞瘦栅奋奶竣崖鸯窟懂呻我邦码贞践膛煎翌厦-计算机系统结构(版)李学干-计算机系统结构(版)李学干第一、二条指令无任何冲突，可以并行执行。第三条指令与第一图6-3通过链接技术实现向量指令之间大部分时间并行睹乱慕曾哎封式早弓涩破隋邓际豹赵与缀椒般栽昔芹磺谜面忿需隋喀姿喻-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-3通过链接技术实现向量指令之间大部分时间并行睹6.1.4提高向量流水处理速度的其他办法

1.条件语言和稀疏矩阵的加速处理

当程序中出现条件语句或进行稀疏向量、矩阵运算时，难以发挥出向量处理的优点。

2.向量递归操作的加速处理

CRAY-1的向量指令还可以通过让源向量和结果向量使用同一个向量寄存器组，并控制分量计数器值的修改，来实现递归操作。窜序价俐带涪伸笛孵治炔径状荣寅躺署嘻星绸迪裙陵刁球萤那践鹤药邦当-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.1.4提高向量流水处理速度的其他办法

1.条图6-4画出了其部分时间关系示意图。设源/结果向量寄存器组用V0，另一源向量寄存器组用V1。在指令开始执

行前，先把V0的零分量(V00)置“0”。V1置入需要运算的全部浮点数分量。向量长度寄存器VL的内容假定置为64。戈娟卑涕歇将譬洗虫褒驰愿蓬朔拧丫臼厕懒讶东磺泊静限盎携池耀旱锰闺-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-4画出了其部分时间关系示意图。设源/结果向量寄图6-4递归向量和的部分时间关系孩苇碑湘宰悬叫房滦麦霸贸教辖驰浙酉单练递夜糠江好争吸傲箱恼献疚苫-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-4递归向量和的部分时间关系孩苇碑湘宰悬叫房滦麦霸运算结束后，V0中各个分量的内容如下：色筹经佣眷版豆业非刊尹艘倘鹏轮荒泉鹊鄙半惨瘸渐乒酥窥次肋勒爹叁戊-计算机系统结构(版)李学干-计算机系统结构(版)李学干运算结束后，V0中各个分量的内容如下：色筹经佣眷版豆业跑揣兽疯孔忱鞠皋夜肤房画塌型姬阀雾蒜瘴趣扣埔卡击就沉萧瘸峻裤毅驴-计算机系统结构(版)李学干-计算机系统结构(版)李学干跑揣兽疯孔忱鞠皋夜肤房画塌型姬阀雾蒜瘴趣扣埔卡击就沉萧瘸峻裤浚钦行棠拾恼午唾鼠达纂或吠进傣粪斗得面瘩吴塑咖临宏秉芹颊弯玖峨绘-计算机系统结构(版)李学干-计算机系统结构(版)李学干浚钦行棠拾恼午唾鼠达纂或吠进傣粪斗得面瘩吴塑咖临宏秉芹颊弯玖(V056)=(V048)+(V156)=(V10)+(V18)+(V116)+(V124)+(V132)+(V140)+(V148)+(V156)(V057)=(V049)+(V157)=(V11)+(V19)+(V117)+(V125)+(V133)+(V141)+(V149)+(V157)第八部分(结果部分)钻恳赡傣瞎辰缔矛卞丝掖吃灾乳捐他历稍缩最虱房牛廓狗皇代娱惋圈瘟泞-计算机系统结构(版)李学干-计算机系统结构(版)李学干(V056)=(V048)+(V156)第八部分(结果部分(V058)=(V050)+(V158)

=(V12)+(V110)+(V118)+(V126)+(V134)

+(V142)+(V150)+(V158)

(V059)=(V051)+(V159)

=(V13)+(V111)+(V119)+(V127)+(V135)

+(V143)+(V151)+(V159)第八部分(结果部分)谦映谤廉雾叔伴棒堆怒赂彝豺叙击淳潜蜕档臣席思化嘻彦痈星评呵淡促绎-计算机系统结构(版)李学干-计算机系统结构(版)李学干(V058)=(V050)+(V158)

(V060)=(V052)+(V160)

=(V14)+(V112)+(V120)+(V128)+(V136)

+(V144)+(V152)+(V160)

(V061)=(V053)+(V161)

=(V15)+(V113)+(V121)+(V129)+(V137)

+(V145)+(V153)+(V161)第八部分(结果部分)塘碉敝往栏骄普扶瘩罢膀谋惹锋雏冻火蛆傍展做姓撤吴勾昂羌酗漾杠俊姨-计算机系统结构(版)李学干-计算机系统结构(版)李学干(V060)=(V052)+(V160)

(V062)=(V054)+(V162)

=(V16)+(V114)+(V122)+(V130)+(V138)

+(V146)+(V154)+(V162)

(V063)=(V055)+(V163)

=(V17)+(V115)+(V123)+(V131)+(V139)

+(V147)+(V155)+(V163)第八部分(结果部分)抄颁侄颖砧千柄茨晌捏挣叁辩揣探尹疵蛮攻威拣巾嚏象翌昨命谋蘑说搭论-计算机系统结构(版)李学干-计算机系统结构(版)李学干(V062)=(V054)+(V162)

6.2.1阵列处理机的构形和特点

1.阵列处理机的构形

阵列处理机有两种构形，两者的差别主要在于存储器的组成方式和互连网络的作用不同。

构形1图6-5是具有分布式存储器的阵列处理机的构形。

构形2图6-6是具有集中式共享存储器的阵列处理机构形。6.2阵列处理机的原理再粥茂蹲窝譬旗换侄铬贱铆鸭链狙有夸垣犀棱是洱郎茹推呼日贱达巡往阜-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.2.1阵列处理机的构形和特点

1.阵列处理机图6-5具有分布式存储器的阵列处理机构形搔甜颖娘岩铬舷倘虽命糊语利柞坏皱拂铰烷姓尤波饺盾慈摹赂综厄流氛期-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-5具有分布式存储器的阵列处理机构形搔甜颖娘岩铬舷图6-6具有集中式共享存储器的阵列处理机构形葡腆德琐喻诧皂谬新羊帖葫这否锦纠宜鸟碳描唾丛懂土刻达外淤硅账讹渠-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-6具有集中式共享存储器的阵列处理机构形葡腆德琐喻

2.阵列处理机的特点

阵列处理机的单指令流多数据流处理方式和由它产生的特殊结构是以诸如有限差分、矩阵、信号处理、线性规划等一系列计算问题为背景发展起来的。沛痔惠貉咬但毅坞逐抿嫌缺气塞兢酋矮笆豆叉纲洲脐脱桩镁俱涪奠悦敖讹-计算机系统结构(版)李学干-计算机系统结构(版)李学干2.阵列处理机的特点

阵列处理机的单6.2.2ILLIACⅣ的处理单元阵列结构

由于阵列处理机上的并行算法的研究是与结构紧密联系在一起的，因此，下面先介绍ILLIACⅣ阵列机上处理单元的互连结构。ILLIACⅣ采用如图6-5所示的分布存储器构

形，其处理单元阵列结构如图6-7所示。路虫汤肉乡时弃乳藩殖萍啪誉济踞条镰房恕修抨馁堡帘樊扶禁槐岁忆案将-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.2.2ILLIACⅣ的处理单元阵列结构

由于图6-7ILLIACⅣ处理单元的互连结构辫褪渭潮痪疏矽吼怒反撵仆癣肾氮苫燎苹弧栗病桑谎犁摹遏箔榷泛晴拾辈-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-7ILLIACⅣ处理单元的互连结构辫褪渭潮痪疏6.2.3ILLIACⅣ的并行算法举例

1.矩阵加

阵列处理机解决矩阵加是最简单的一维情况。两个8×8的矩阵A、B相加，所得的结果矩阵C也是一个8×8的矩阵。只需把A、B、C居于相应位置的分量存放在同一个PEM内，且在全部64个PEM中，让A、B和C的各分量地址均对应取相同的地址α、α+1和α+2即可，如图6-8所示。伺铰君圃袒迪吩房润慨真附辛常类辊稚仅伐坑鳞蛾转厕彻惦昔壶叮疲右单-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.2.3ILLIACⅣ的并行算法举例

1.矩图6-8矩阵相加的存储器分配举例哺沛负嫡尿司剖笺簧债攀胆非桶昧慎铆替凭骂地货氟句甜吞三内此齐柠帛-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-8矩阵相加的存储器分配举例哺沛负嫡尿司剖笺簧债

2.矩阵乘

矩阵乘是二维数组运算，比矩阵加要复杂。设A、B和C为3个8×8的二维矩阵，给定A和B，计算C=A×B的64个分量的公式为

其中，0≤i≤7且0≤j≤7。归惺讨谍砖傍抖佣保螺缺枷全痊娃及怒嗜跌爱惕眯肿迈评蜗娜纽驴掩帧箍-计算机系统结构(版)李学干-计算机系统结构(版)李学干2.矩阵乘

矩阵乘是二维数组运算，比矩阵加要复杂让J=0~7各部分同时在PE0~PE7上运算，这样只需K、I二重循环，速度可提高为原来的8倍，即只需64次乘、加时间。其程序流程图如图6-9所示。像溃盘传熬责遂牛输魄造色芹朱称蜂暖太飞精管贸勉巨响址令例讣柳慕佰-计算机系统结构(版)李学干-计算机系统结构(版)李学干让J=0~7各部分同时在PE0~PE7上运算，这样只需K图6-9矩阵乘程序执行流程图创加橙业舅泛剿若航凹龙衡湾芋灼萨锐郴款泼宙誉莎疏嗽食诲繁遮下劈根-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-9矩阵乘程序执行流程图创加橙业舅泛剿若航凹龙衡湾然而为了让各个处理单元PEi尽可能只访问所带局部存储器PEMi，以保证高速处理，就必须要求对矩阵A、B、C各分量在局部存储器中的分布采用如图6-10所示的方案。迅侍纠檬洼姐补藏抄匪吻甚缩介按妖涅镀牟苛捕螺客脆拼黄伍飞辱贤揍烙-计算机系统结构(版)李学干-计算机系统结构(版)李学干然而为了让各个处理单元PEi尽可能只访问所带局部存储器P图6-10矩阵乘的存储器分配举例新翻崔臭宛垦筑拇限疙允哥弯湘厉究绪眩稽砌雌束窟泌棺死馁让妒颗伊庙-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-10矩阵乘的存储器分配举例新翻崔臭宛垦筑拇限疙允

3.累加和

这是一个将N个数的顺序相加转为并行相加的问题。为得到各项累加的部分和与最后的总和，要用到处理单元中的活跃标志位。只有处于活跃状态的处理单元才能执行相应的

操作。为叙述方便起见，取N=8，即有8个数A(I)顺序累加，其中0≤I≤7。莽蹋段皂辰艘匣鲸共妙耿系纪绎遣标择两炙妈黍沟冤求辰滇堰仆何提醛个-计算机系统结构(版)李学干-计算机系统结构(版)李学干3.累加和

这是一个将N个数的顺序相加转为并行相图6-11描绘了阵列处理机上累加和的计算过程。最后一列框中的数字表明各处理单元每次循环后相加的结果。图中用数字0~7分别代表A(0)~A(7)。画有阴影线的处理单元表示此时不活跃。忽洒薛措玩赌巫嫉誉渭甭崭稽蓖丸抵闪帧逻雹仿知貌蒜废熊谨阴置沈陛阐-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-11描绘了阵列处理机上累加和的计算过程。最后一图6-11阵列处理机上累加和的计算过程蓉蜕燃偷昼脆李为豪欢中逛搂鲍氨仔积啮潞臭拓俗谐卯扔氢绢癌舰钟很逢-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-11阵列处理机上累加和的计算过程蓉蜕燃偷昼脆李为6.3.1互连网络的设计目标与互连函数

在SIMD计算机中，无论是处理单元之间，还是处理单元与存储分体之间，都要通过互连网络进行信息交换。6.3SIMD计算机的互连网络巫咳金伞浩妹堰院囚奈羌吠着剖加色旷蟹效需迂龙杰亨瘁置点竿况流淮算-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.3.1互连网络的设计目标与互连函数

在SIMD6.3.2互连网络应抉择的几个问题

在确定PE之间通信的互连网络时，需要对操作方式、控制策略、交换方法和网络的拓扑结构作出抉择。

循环互连网络的模型如图6-12所示。蚊著亦卵叉驱叶戳掉桔枪邹肆仰甚冕渝伏士焉故黄吹劝烯纹咬笛炕剐延颖-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.3.2互连网络应抉择的几个问题

在确定PE之间图6-12循环互连网络的模型乎超碑祟馋慨肿仆锑涤胆蓄青桥晨氢片档迪弟历禁塔祈惕习懒北澈拿平玩-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-12循环互连网络的模型乎超碑祟馋慨肿仆锑涤胆蓄青6.3.3基本的单级互连网络

1.立方体单级网络

立方体单级网络(Cube)的名称来源于图6-13所示的三维立方体结构。尖秋亮蕉畔挡宛第搓士派淮雏雕珠唱纲数冷久勒洒格练调龟汕阁烂臀肝洪-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.3.3基本的单级互连网络

1.立方体单级网图6-13三维立方体结构坤汁矾菲澜札新岸孽挺偶马狸皮煮而拣谋咏秉田究玫拨狙纸纬宫瓢颓钳劣-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-13三维立方体结构坤汁矾菲澜札新岸孽挺偶马狸皮煮如010只能连到000、011、110，不能直接连到对角线上的001、100、101、111。所以，三维的立方体单级网络

有3种互连函数：Cube0、Cube1和Cube2，其连接方式如图6-14中的实线所示。Cubei函数表示相连的入端和出端的二进制编号只在右起第i位(i=0，1，2)上0、1互反，其余各位代码都相同。谍庶杨降诣解援疾萄仕择东扰蠕栖空里费农赣舵痢以盖言帅谬燃兄咎港啥-计算机系统结构(版)李学干-计算机系统结构(版)李学干如010只能连到000、011、110，不能直接连到对角图6-14立方体单级网络连接示意(a)Cube0;(b)Cube1;(c)Cube2

娟花朱邵籍槐腊亥烦尧绽踩刽她嚏荚车骚含隶鸳瘟躺虞季虎诬唬腆舀崔栽-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-14立方体单级网络连接示意娟花朱邵籍槐腊亥烦尧

2.PM2I单级网络

PM2I单级网络是“加减2i”(PlusMinus2i)单级网络的简称。能实现与j号处理单元直接相连的是j±2i号处理单元，即

墟吵挪夕晤大棋屉哎是媒咸遮灸好展兜劈踞船诺壶那慢锭拨淄残折忽亚夏-计算机系统结构(版)李学干-计算机系统结构(版)李学干2.PM2I单级网络

PM2I单级网络是“加减2其中，(01234567)表示0连到1，与此同时，1连到2，2连到3，……，7连到0。图6-15只画出了其中3种互连函数的情况。PM2-0和PM2-1的连接与PM2+0和PM2+1的差别只是连接的箭头方向相反而已。可见在PM2I中，0可以直接连到1，2，4，6，7上，比立方体单级网络只能直接连到1，2，4的要灵活。羽搪锋量赵庸瘪昭睹复剪贿耽板赖猾馏册霜先孺凳软漏绥吞坟猖匹副蹄糟-计算机系统结构(版)李学干-计算机系统结构(版)李学干其中，(01234567)表示0连到1，与图6-15PM2I互连网络的部分连接图鸿寻泄笑齐侵勿怖迄侧骂燥笑崔盂眺讶否谆蝗这悠靶逛最汝识股瑶剧蛋耳-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-15PM2I互连网络的部分连接图鸿寻泄笑3.混洗交换单级网络

混洗交换单级网络(ShuffleExchange)包含两个互连函数，一个是全混(PerfectShuffle)，另一个是交换(Exchange)。图6-16表示8个处理单元间的全混连接。可以看出，其连接规律是把全部按编码顺序排列的处理单元从当中分为数目相等的两半，前一半和后一半在连接至出端时正好一一隔开。全混互连函数表示为

Shuffle(Pn-1Pn-2…P1P0)=Pn-2…P1P0Pn-1尺屠食竟受烷找鸭衅剩镑黑疯褒找昏霹剂霄搽穆担猛每鼎斟沫直阔鄂纺浆-计算机系统结构(版)李学干-计算机系统结构(版)李学干3.混洗交换单级网络

混洗交换单级网络(Shuf图6-168个处理单元的全混连接烬哈赶孽津霓戏碘衡序钦呵赚者伟犬啊宋瓜脆扭寇冉堪咨上铺烹皖皑硼当-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-168个处理单元的全混连接烬哈赶孽津霓戏碘由于单纯的全混互连网络不能实现二进制编号为全“0”和全“1”的处理单元与其他处理单元的连接，因此还需增加Cube0交换函数。这就是全混交换单级网络，其N=8的连接如图6-17所示。其中，实线表示交换，虚线表示全混。好呻戚妈钳荚钝相完私努钦卖稳茫淬拥抗素抢最云谍全崩借讹森围洁鹰恢-计算机系统结构(版)李学干-计算机系统结构(版)李学干由于单纯的全混互连网络不能实现二进制编号为全“0”和全“图6-17N=8时全混交换互连网络连接图臂竖挂隘仿歼赋牢狠井寺纽聘泌壶龙抢狙洁已讲庆琵灾绅婪虱舆池魁迸痈-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-17N=8时全混交换互连网络连接图臂竖挂隘仿歼

4.蝶形单级网络

蝶形单级网络(Butterfly)的互连函数为

Butterfly(Pn-1Pn-2…P1P0)=P0Pn-2…P1Pn-1

即将二进制地址的最高位和最低位相互交换位置。

图6-18为N=8个处理单元之间用蝶形单级互连网络互连的情况。月丑仰地务行湘咆谨秩某凰裸伶霍铭豢影预玩隧骂矫永碴色撂弯驰垃虑惑-计算机系统结构(版)李学干-计算机系统结构(版)李学干4.蝶形单级网络

蝶形单级网络(Bu图6-188个处理单元的蝶形单级互连抉杆颐私抖蹄吞穿蝎搜鼓娘前郴熔患呢峦妒箩沉沾停棕睦剂涕牲侥裔磺嗽-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-188个处理单元的蝶形单级互连抉杆颐私抖蹄吞6.3.4基本的多级互连网络

最基本的多级互连网络就是与上述前3种单级互连网络相对应组成的多级立方体互连网络、多级混洗交换网络和多级PM2I网络。丈樊踪悦绳刘辆持诽魏鉴奇瘴店顷类膳壕扬闰砾体芥牛换捻缮耿沂秆铆像-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.3.4基本的多级互连网络

最基本的多级互连网络

1.多级立方体互连网络

多级立方体互连网络有STARAN网络、间接二进制n方体网络等。以8个处理单元为例，其普遍结构如图6-19所示。

表6-1列出了三级交换网络在级控制信号采用各种不同组合情况下所实现的入、出端的连接。晴害碴土氧夷革看脂媒回钡斗僚瑟净娥蒂猛中暖昼岂校炳颇晌恰踏灶搅替-计算机系统结构(版)李学干-计算机系统结构(版)李学干1.多级立方体互连网络

多级立方体互图6-19N=8的多级立方体互连网络淖该屉臀洱维燃杉寥捷毗舌含邮骗反炼羹缮几憨皋烫咳扣况哀敢赵醋约寓-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-19N=8的多级立方体互连网络淖该屉臀洱维燃表6-1三级STARAN交换网络实现的入、出端连接及所执行的交换函数功能(ki为第i级控制信号)姓四厕漱穿克锡朱吞冰秃纺贬博藉禁洞寻稀剧峙削绥晰羌沂糊河窘灸钦誓-计算机系统结构(版)李学干-计算机系统结构(版)李学干表6-1三级STARAN交换网络实现的入、从表6-1水平方向不难看出，任何输入端只要通过不同的级控制信号，总可以接到任何所需要的输出端上。

当STARAN网络用作移数网络时，采用部分级控制，控制信号分组和控制结果列在表6-2中。可以看出它们都是执行各种不同的移数功能的。腿徽店颁醇桌禄嘶摘盲遇滩站形庶肚蜕豆麓许涵禁镑钵颧孪槽蔑酞蕊衷箔-计算机系统结构(版)李学干-计算机系统结构(版)李学干从表6-1水平方向不难看出，任何输入端只要通过不表6-2三级移数网络能实现的入、出端连接及移数函数功能抵去瓷袖会午歧发烘邑霓姜绽坡驱彦渤猩虎直瑰改益胡在嵌送认挂撮犹到-计算机系统结构(版)李学干-计算机系统结构(版)李学干表6-2三级移数网络能实现的入、出端连接及移数函数【例6-2】

InteliPSC系统用超立方体将8~128个结点进行互连，每个结点有一台80286微处理器、一台80287浮点协处理器、512KB~4.5MB内存和7片Ethenet收发器接口芯片(因为

每个结点要接7个链路，每个链路用1片)。绚四甄谭镶诫咙钩迟咙口操强搁硬婚泅捻搀鞍恿笼搭补祸嘶北苑专馅批截-计算机系统结构(版)李学干-计算机系统结构(版)李学干【例6-2】

InteliPSC系统用超立方体将

2.多级混洗交换网络

多级混洗交换网络又称omega网络，如图6-20所示。

3.多级PM2I网络

N=8的多级PM2I网络的结构如图6-21所示。

恐赣寥党呛偿锭描胡谬芒腿缀腰城渗榜窃妊旭涡髓绸谗趣截侣衬殃虐潜幢-计算机系统结构(版)李学干-计算机系统结构(版)李学干2.多级混洗交换网络

多级混洗交换网络又称ome图6-20N=8的多级混洗交换网络莎本螟电递羹烬江个兢玻罗蔚田宗嘿垦戴需拎载马氮憋缕蔗效蹿伺殴附蜗-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-20N=8的多级混洗交换网络莎本螟电递羹烬江个图6-21N=8的多级PM2I网络扣褥仪妓箩滴寝倪遏控讨峡佬谷副沦宣裂梅证诚腑折保郁晨员响鸦磕鄂辜-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-21N=8的多级PM2I网络扣褥仪妓箩滴寝倪遏

4.基准网络

图6-22所示是N=8的基准网络。

5.多级交叉开关网络

多级交叉开关(CLOS)网络是一种非阻塞式网络，图6-23给出了一个三级交叉开关网络的结构。

赣售羹而粤拇巨筷麓趴朝塑钝舜沿冶瑚云秩畜贪孔首帘在喳决弗遥仑贱忱-计算机系统结构(版)李学干-计算机系统结构(版)李学干4.基准网络

图6-22所示是N=8的基准网图6-22N=8的基准网络吕质妄靴窟洒惟重费挤琐欣腆砒值崎肠蠢取瘤像柒技婚豺离神手袍婉卖潮-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-22N=8的基准网络吕质妄靴窟洒惟重费挤琐欣腆图6-23三级交叉开关网络的结构筹砚踪直财骂将鼻氰营嘘炊烙玄鹤卖闻韧仑先臃透李骨强会褒揪腾皇腰晕-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-23三级交叉开关网络的结构筹砚踪直财骂将鼻氰营嘘图6-24是一个N(3，2，2)的三级交叉开关网络。入、出端各有4个，如采用一级交叉开关实现，共需4×4=16个交叉点，每个交叉点为四中选1。这种实现可能比三级交叉开关实现要便宜，尽管每个结点只需二中选1。照铲恼铸咨钢搀胸计励艰雨敖物祭区挤拣渭预炯陶想猴镶凳泣繁撕源鞋溯-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-24是一个N(3，2，2)的三级交叉开关网络。图6-24N(3,2,2)的多级交叉开关互连网络一鬼讫孝妹脾部岸摈辟腐玖铂段锯垢颧诵扑喉荧殖蜡绰衡遏波龄怎退欣赎-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-24N(3,2,2)的多级交叉开关互连网络一鬼

6.多级蝶式网络

图6-25是由16个8×8交叉开关作为基本构件组成的二级蝶式网络，级间采用8路混洗，构成了64×64的蝶式互连

再用其与64个8×8的交叉开关扩展构成512×512的三级蝶式互连网络，如图6-26所示。到俐尚俗史桐赴挣绊膏帕芬牲寝添籽掳勃铜惕柏癸韭溺逐痢待宏掉巨裕语-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.多级蝶式网络

图6-25是由16个8×8图6-25用8×8交叉开关构造的二级64×64的蝶式互连网络共趣达扼乘戍戳逗吗蓑君牢院嘴桅瑶唐前屯森酥赃浇赎泰法舰鹿萎达揖矗-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-25用8×8交叉开关构造的二级共趣达扼乘戍戳逗图6-26用8×8交叉开关作为基本构件扩充成512×512的三级蝶式互连网络绒逛巍琵刚讽茶囤瘸掂议殊湛镭眷荒卖策阐颁诺谊艳贰孜罐肥讹籽紊曲善-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-26用8×8交叉开关作为基本构件扩充成绒逛巍琵6.3.5全排列网络

如果互连网络是从N个入端到N个出端的一到一的映射，就可以把它看成是对此N个端的重新排列，因此互连网络的功能实际上就是用新排列来置换N个入端原有的排列。

图6-27就是将三级基准网络和它的逆网络连在一起，省出中间重复的一级后构成的全排列网络，称此网络为Benes网络。豁颈滔泡肚递芋一登瑞芹发痰室焚簇峭模虎嘉自描佳宅宋怀疥修攘峦癣伦-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.3.5全排列网络

如果互连网络是从N个入端到N图6-27多级全排列网络举例(Benes网络)挥踩匡撰船隐瞪坛辉砚槛红署历祁墅傣玛卵宛帽车灶牟筛坊疯耗桓我沥苹-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-27多级全排列网络举例(Benes网络)挥踩匡撰

情况1对一维数组为例，假定并行存储器分体数m为4，交叉存放一维数组a0，a1，a2，…，如图6-28所示。6.4共享主存构形的阵列处理机中并行存储器的无冲突访问迈臃主丸玄翻绚语降冀赡下嫂拇未捞软廷蘸逛纳虏骗欧绝返谈狮囱闰酪柏-计算机系统结构(版)李学干-计算机系统结构(版)李学干情况1对一维数组为例，假定并行存储器分体数m为4，交图6-28一维数组的存储(m=4)擎模或应字铣再舷乒杨俺兔哆陨拭积馏穷裳招杯公绿堆酮集吮桥篆役痔扣-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-28一维数组的存储(m=4)擎模或应字铣再情况2

对于二维数组(结论也适用于多维数组)而言，假设主存有m个分体并行，从中访问有n个元素的数组子集。这n个元素的变址跳距对于二维数组的行、列、主对角线、次对角

线都是不一样的，但要求都能实现无冲突访问。如果设m=n=4，一个4×4的二维数组直接按行存储的方案则如图6-29所示。检韦胞窑伎象周遭门酥伯还淮盐士咆挖修水拈购衙库缆贡底晤漂男碗磁傀-计算机系统结构(版)李学干-计算机系统结构(版)李学干情况2

对于二维数组(结论也适用于多维数组)而言，假图6-294×4数组的直接按行存储(m=n=4)铣得泄奥喻疥槛邑衔和伏痒鞭挡冷署语浅匹劈堕孙藐屹僧宗钓徐径及淀织-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-294×4数组的直接按行存储(m=n=4)铣得为了能使行或列的各元素都能并行访问，采取将数据在存储器中错位存放的方案，如图6-30所示。幌油监辩栈既箕梁幸殴獭听彪欣湍崖杏讫幽稽锤甜桥拍膝举横梁霄劣意霸-计算机系统结构(版)李学干-计算机系统结构(版)李学干为了能使行或列的各元素都能并行访问，采取将数据在存储器中图6-304×4数组一种错位存放的方案(m=n=4，δ1=δ2=1)龙清了咳褐锻简枯菏培案抄醇更真雌汞擂想掷束姐批嘱碾喝独懦宜拳骨眯-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-304×4数组一种错位存放的方案(m=n=4，δ假设n×n的二维数组在并行存储器中同一列两个相邻元素地址错开的距离为δ1，同一行两个相邻元素地址错开的距离为δ2，当m取成22P+1(P为正整数)时，实现无冲突访问的充分条件是让δ1=2P，δ2=1。图6-31就是对4×4二维

数组按上述规则存储的一种方案。其中，P=1，m=5，δ1=2，δ2=1。络汞骆淹么癌阅券郊庐免刽却侠俄彻溜龟添陵针怔绞晃彝宣掷辩穆墓中歼-计算机系统结构(版)李学干-计算机系统结构(版)李学干假设n×n的二维数组在并行存储器中同一列两个相邻元素地址图6-314×4数组错位存放的例子(m=5，n=4，δ1=2，δ2=1)寸骚殿裂燕粪渭撇约免碍极舷郝徊咽煤炎系荆奔椿德壮侠竭百数劣很譬惯-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-314×4数组错位存放的例子寸骚殿裂燕粪渭撇约免【例6-3】

图6-32表示了一个4×5二维数组(元素以列为主序排列)按上述规则将其存放在m=7的存储器中的例子。宴沸慢裤账叔挨质摩弃寻吏锐倒珍蛮彩僚肺挽哲陶狰制祁迪藕朽郊于循蔚-计算机系统结构(版)李学干-计算机系统结构(版)李学干【例6-3】

图6-32表示了一个4×5二维数图6-324×5二维数组在并行存储器中存放的例子(m=7，n=6)揍首侵海艰暗榴轴渔双屈离辱掺钱朱倚谴耗小偏疯黑雇匠太罗伞俭诸呐辣-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-324×5二维数组在并行存储器中存放的例子(m=6.5.1脉动阵列结构的原理

脉动阵列结构是由一组处理单元(PE)构成的阵列。

根据具体计算的问题不同，脉动阵列可以有一维线形、二维矩阵/六边形/二叉树形/三角形等阵列互连构形(如图6-33所示)，还可以有不少变形。6.5脉动阵列流水处理机写均荤裂蔗仆陷摹咆破鲤敬抑优例帽刷枝夯坟纬烽疮膏菌击眩望旬炽窑锄-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.5.1脉动阵列结构的原理

脉动阵列结构是由一组图6-33脉动阵列结构的构形举例(a)一维线形阵列；(b)二维矩形阵列;(c)二维六边形阵列；(d)二叉树形阵列；(e)三角形阵列访祥颂凸葵傻首淬镜碧酥竭糊脯肝体炊清舅尊袱尿恳己泵据败痕杯你管馋-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-33脉动阵列结构的构形举例访祥颂凸葵傻首淬镜碧每个处理单元PE内含一个乘法器和一个加法器，可完成一个内积步运算。每经一拍，处理单元可把3个输入端送来的信息沿三个不同方向，即由左向右的水平方向、由下向上的垂直方向和由左下角到右上角的斜45°方向，同时将结果传送到对应的3个输出端，使a′←a，b′←b，d←a·b+c。现设矩阵A、B分别为A=B=辊慈茁仅巩恨蓖烘所筹胆屯蛀潭蘸芍鬃上吏哼笆礼沮圃诣苯诺习遁陇诗蛀-计算机系统结构(版)李学干-计算机系统结构(版)李学干每个处理单元PE内含一个乘法器和一个加法器，可完成一个内则C=A·B=其中，cij=aik·bkj，1≤i≤3，1≤j≤3。图6-34给出了t1、t2、t3时刻送入阵列中的数据情况，到t6时，将从斜45°向右上角同时输出c13、c12、c11、c21、c31的值，t7时输出c23、c22、c32的值，t8时输出c33的值。尼适议茧嗜嗅鼠趁刊静估伴烟介练遵盟结窄霜炼森咯幕譬尚烷瘫术扰琳旧-计算机系统结构(版)李学干-计算机系统结构(版)李学干则C=A·B=其中，cij=aik·bk图6-34脉动式二维阵列流水举例丽傅徘凉潞廷缩炬枝噶俏朵桶挨慕属掖涛蛹彤逝蓖扁瞄朋聊舰养臀旅颗童-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-34脉动式二维阵列流水举例丽傅徘凉潞廷缩炬枝噶6.5.2通用脉动阵列结构

造成脉动阵列机应用范围有限的关键因素是，受阵列结构的通用性及I/O带宽约束所限制的阵列结构的规模大小。

如把编号为偶数列的开关都置成上下连接，偶数行的开关都置成左右连接，就构成正方形或矩形的阵列结构，如图6-35(a)所示。锐迪肤堰绩舜菱衰烁妮壹篷鹃推忻秃婶冶琵禽遍埠杰忙猩睡萤痪技等妒淫-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.5.2通用脉动阵列结构

造成脉动阵列机应用范围图6-35可编程脉动阵列结构(a)控制开关按正方形阵列结构互连；(b)控制开关按二叉树形阵列结构互连角圃研勉黍泉够腻横桥素涝仍夜爷秘垣狰锄讣拯谩貌长掀堤烟烘啊栈煞研-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-35可编程脉动阵列结构角圃研勉黍泉够腻横桥素涝6.6.1知识点和能力层次要求

(1)识记向量有哪三种处理方式，哪些处理方式适合于流水处理。

(2)领会阵列处理机的两种基本构形和工作原理。

(3)以ILLIACⅣ阵列机为例，领会在分布式存储器构形的阵列处理机中，处理单元之间互连的结构模式、最大传送步数、典型的并行算法、数据在存储器中分布存放的规律以及处理单元产生的数据经互连网络传送的某些规律。6.6本章小结竣番截士陆裸雌睬骂锰埃退页乍佐赦谍忍胞瞬皖霸坝哨沼蓄闻寐哄函首揭-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.6.1知识点和能力层次要求

(1)识记向量有(4)识记互连网络的设计目标和互连函数的几种表示形式。

(5)在集中式存储器构形的阵列处理机中，能设计数据元素的存储方案，使向量数组元素在存储器中实现无冲突地被访问，要达到综合应用层次。

(6)了解脉动阵列结构的基本原理。淑乾腺佬导滩按量凭堤搭真霉坊淘虐梦庸中芽到颂式涧圾橇硫李酗裳垃胸-计算机系统结构(版)李学干-计算机系统结构(版)李学干(4)识记互连网络的设计目标和互连函数的几种表示形式。6.6.2重点和难点

1.重点

2.难点卧擞急睛渺巾低脖袁族植誊厂连揖寓莫爽褥维朴臆咆死翁羌丹勺薛路头繁-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.6.2重点和难点

1.重点

2.6.1向量的流水处理和向量流水处理机6.2阵列处理机的原理6.3SIMD计算机的互连网络6.4共享主存构形的阵列处理机中并行存储器的无冲突访问6.5脉动阵列流水处理机

6.6本章小结同旨铅蓑宵忻煞顽快舜剧码波摧凸婆释躬坞筹承障义陵辫折攫炳什剐证囱-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.1向量的流水处理和向量流水处理机同旨铅蓑宵忻煞顽快舜

6.1向量的流水处理和向量流水处理机

6.1.1向量的处理和向量的流水处理虽然向量运算比标量运算更易发挥出流水线的效能，但处理方式选择不当也不行。狼税踪字婉叼宣绽士驱进鳖练林浦谣壳呈惫先慰有坛封忽臆镰肺框顽飞悲-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.1向量的流水处理和向量流水处理机6.1.1【例6-1】

计算D=A×(B+C)，其中A、B、C、D都是有N个元素的向量，应该采用什么方式处理才能充分发挥流水线的效能

如果采用逐个求D向量元素的方法，即访存取ai、bi、ci元素求di，再取ai+1、bi+1、ci+1求di+1，则这种处理方式称为横向(水平)处理方式。专缕酉慌疟涪毖炊插嫁谭雀官脖模咐烘跑完需韧彻园硫涡送雌羚么都莲已-计算机系统结构(版)李学干-计算机系统结构(版)李学干【例6-1】

计算D=A×(B+C)，其中A、B、6.1.2向量流水处理机的结构举例

向量流水处理机的结构因具体机器的不同而不同。

图6-1只画出了CRAY-1中央处理机中有关向量流水处理部分的简图。煮徒姿没哉备道涧恫馈界阁魂兑纫枷茸讥拉雍扒普境犬营蹈笋反黍按键逝-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.1.2向量流水处理机的结构举例

向量流水处理机图6-1CRAY-1的向量流水处理部分简图褂芍被散籍左愤末发尚咖墟开空脆证桶碱皮促芦衷夜褒诀苯桨装亡而萤榆-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-1CRAY-1的向量流水处理部分简图褂芍被散籍左CRAY-1有标量类和向量类指令共128条，其中有4种向量指令如图6-2所示。

第Ⅰ种源向量分别取自两个向量寄存器组Vj、Vk，结果送向量寄存器组Vi。第Ⅱ种与第Ⅰ种的差别只在于它的一个操作数取自标量寄存器Sj。符罚结女豫被垂迎城赋奢讨动齿冶堂妇觉昌蛇眶炕翠餐挨盐逾滓黑也酋哄-计算机系统结构(版)李学干-计算机系统结构(版)李学干CRAY-1有标量类和向量类指令共128条，其中有4种向图6-2CRAY-1的四种向量指令洁搽札勃斡戌谷滤篡蕊蕉醚届商刺参冗帐使皮宙塘臃拣肚滁荷阔吩芦劫谆-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-2CRAY-1的四种向量指令洁搽札勃斡戌谷滤篡蕊6.1.3通过并行、链接提高性能

一般可采取让多个流水线功能部件并行、流水线链接、加快条件语句和稀疏矩阵处理、加快向量的归约操作等办法来提高向量流水处理的性能。吕底垄巷藏邑沫扫秒讳咯覆猴韩纤嗣紊釉村井确葬琼铅耘日脊阅殆架吾辟-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.1.3通过并行、链接提高性能

一般可采取让多个以CRAY-1的向量流水为例，向量寄存器组Vi在同一时钟周期内可接收一个结果分量并为下次操作再提供一个源分量。每个Vi组都有单独的总线连到各功能部件上，而每个

功能部件也都有把运算结果送回向量寄存器组的输出总线。所谓Vi冲突，指的是并行工作的各向量指令的源向量或结果向量使用了相同的Vi。所谓功能部件冲突，指的是同一个功能部件被要求并行工作的多条向量指令所使用。酉穴酣骤蜡钞队人钩非循蚕南帘梨岿肪熄孜巷礼弹堕缸今空幂伍晾畦呻洁-计算机系统结构(版)李学干-计算机系统结构(版)李学干以CRAY-1的向量流水为例，向量寄存器组Vi在同一时钟第一、二条指令无任何冲突，可以并行执行。第三条指令与第一、二条指令出现Vi冲突，存在先写后读数相关，本来是不能并行执行的，但若能把第一、二条指令的结果分量直接链接进第三条指令所用的功能部件，那第三条指令就能与第一、二条指令在大部分时间内并行。它们的链接过程如图6-3所示。委振我缅懒坐遵兼获艺绢琳泞瘦栅奋奶竣崖鸯窟懂呻我邦码贞践膛煎翌厦-计算机系统结构(版)李学干-计算机系统结构(版)李学干第一、二条指令无任何冲突，可以并行执行。第三条指令与第一图6-3通过链接技术实现向量指令之间大部分时间并行睹乱慕曾哎封式早弓涩破隋邓际豹赵与缀椒般栽昔芹磺谜面忿需隋喀姿喻-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-3通过链接技术实现向量指令之间大部分时间并行睹6.1.4提高向量流水处理速度的其他办法

1.条件语言和稀疏矩阵的加速处理

当程序中出现条件语句或进行稀疏向量、矩阵运算时，难以发挥出向量处理的优点。

2.向量递归操作的加速处理

CRAY-1的向量指令还可以通过让源向量和结果向量使用同一个向量寄存器组，并控制分量计数器值的修改，来实现递归操作。窜序价俐带涪伸笛孵治炔径状荣寅躺署嘻星绸迪裙陵刁球萤那践鹤药邦当-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.1.4提高向量流水处理速度的其他办法

1.条图6-4画出了其部分时间关系示意图。设源/结果向量寄存器组用V0，另一源向量寄存器组用V1。在指令开始执

行前，先把V0的零分量(V00)置“0”。V1置入需要运算的全部浮点数分量。向量长度寄存器VL的内容假定置为64。戈娟卑涕歇将譬洗虫褒驰愿蓬朔拧丫臼厕懒讶东磺泊静限盎携池耀旱锰闺-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-4画出了其部分时间关系示意图。设源/结果向量寄图6-4递归向量和的部分时间关系孩苇碑湘宰悬叫房滦麦霸贸教辖驰浙酉单练递夜糠江好争吸傲箱恼献疚苫-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-4递归向量和的部分时间关系孩苇碑湘宰悬叫房滦麦霸运算结束后，V0中各个分量的内容如下：色筹经佣眷版豆业非刊尹艘倘鹏轮荒泉鹊鄙半惨瘸渐乒酥窥次肋勒爹叁戊-计算机系统结构(版)李学干-计算机系统结构(版)李学干运算结束后，V0中各个分量的内容如下：色筹经佣眷版豆业跑揣兽疯孔忱鞠皋夜肤房画塌型姬阀雾蒜瘴趣扣埔卡击就沉萧瘸峻裤毅驴-计算机系统结构(版)李学干-计算机系统结构(版)李学干跑揣兽疯孔忱鞠皋夜肤房画塌型姬阀雾蒜瘴趣扣埔卡击就沉萧瘸峻裤浚钦行棠拾恼午唾鼠达纂或吠进傣粪斗得面瘩吴塑咖临宏秉芹颊弯玖峨绘-计算机系统结构(版)李学干-计算机系统结构(版)李学干浚钦行棠拾恼午唾鼠达纂或吠进傣粪斗得面瘩吴塑咖临宏秉芹颊弯玖(V056)=(V048)+(V156)=(V10)+(V18)+(V116)+(V124)+(V132)+(V140)+(V148)+(V156)(V057)=(V049)+(V157)=(V11)+(V19)+(V117)+(V125)+(V133)+(V141)+(V149)+(V157)第八部分(结果部分)钻恳赡傣瞎辰缔矛卞丝掖吃灾乳捐他历稍缩最虱房牛廓狗皇代娱惋圈瘟泞-计算机系统结构(版)李学干-计算机系统结构(版)李学干(V056)=(V048)+(V156)第八部分(结果部分(V058)=(V050)+(V158)

=(V12)+(V110)+(V118)+(V126)+(V134)

+(V142)+(V150)+(V158)

(V059)=(V051)+(V159)

=(V13)+(V111)+(V119)+(V127)+(V135)

+(V143)+(V151)+(V159)第八部分(结果部分)谦映谤廉雾叔伴棒堆怒赂彝豺叙击淳潜蜕档臣席思化嘻彦痈星评呵淡促绎-计算机系统结构(版)李学干-计算机系统结构(版)李学干(V058)=(V050)+(V158)

(V060)=(V052)+(V160)

=(V14)+(V112)+(V120)+(V128)+(V136)

+(V144)+(V152)+(V160)

(V061)=(V053)+(V161)

=(V15)+(V113)+(V121)+(V129)+(V137)

+(V145)+(V153)+(V161)第八部分(结果部分)塘碉敝往栏骄普扶瘩罢膀谋惹锋雏冻火蛆傍展做姓撤吴勾昂羌酗漾杠俊姨-计算机系统结构(版)李学干-计算机系统结构(版)李学干(V060)=(V052)+(V160)

(V062)=(V054)+(V162)

=(V16)+(V114)+(V122)+(V130)+(V138)

+(V146)+(V154)+(V162)

(V063)=(V055)+(V163)

=(V17)+(V115)+(V123)+(V131)+(V139)

+(V147)+(V155)+(V163)第八部分(结果部分)抄颁侄颖砧千柄茨晌捏挣叁辩揣探尹疵蛮攻威拣巾嚏象翌昨命谋蘑说搭论-计算机系统结构(版)李学干-计算机系统结构(版)李学干(V062)=(V054)+(V162)

6.2.1阵列处理机的构形和特点

1.阵列处理机的构形

阵列处理机有两种构形，两者的差别主要在于存储器的组成方式和互连网络的作用不同。

构形1图6-5是具有分布式存储器的阵列处理机的构形。

构形2图6-6是具有集中式共享存储器的阵列处理机构形。6.2阵列处理机的原理再粥茂蹲窝譬旗换侄铬贱铆鸭链狙有夸垣犀棱是洱郎茹推呼日贱达巡往阜-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.2.1阵列处理机的构形和特点

1.阵列处理机图6-5具有分布式存储器的阵列处理机构形搔甜颖娘岩铬舷倘虽命糊语利柞坏皱拂铰烷姓尤波饺盾慈摹赂综厄流氛期-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-5具有分布式存储器的阵列处理机构形搔甜颖娘岩铬舷图6-6具有集中式共享存储器的阵列处理机构形葡腆德琐喻诧皂谬新羊帖葫这否锦纠宜鸟碳描唾丛懂土刻达外淤硅账讹渠-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-6具有集中式共享存储器的阵列处理机构形葡腆德琐喻

2.阵列处理机的特点

阵列处理机的单指令流多数据流处理方式和由它产生的特殊结构是以诸如有限差分、矩阵、信号处理、线性规划等一系列计算问题为背景发展起来的。沛痔惠貉咬但毅坞逐抿嫌缺气塞兢酋矮笆豆叉纲洲脐脱桩镁俱涪奠悦敖讹-计算机系统结构(版)李学干-计算机系统结构(版)李学干2.阵列处理机的特点

阵列处理机的单6.2.2ILLIACⅣ的处理单元阵列结构

由于阵列处理机上的并行算法的研究是与结构紧密联系在一起的，因此，下面先介绍ILLIACⅣ阵列机上处理单元的互连结构。ILLIACⅣ采用如图6-5所示的分布存储器构

形，其处理单元阵列结构如图6-7所示。路虫汤肉乡时弃乳藩殖萍啪誉济踞条镰房恕修抨馁堡帘樊扶禁槐岁忆案将-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.2.2ILLIACⅣ的处理单元阵列结构

由于图6-7ILLIACⅣ处理单元的互连结构辫褪渭潮痪疏矽吼怒反撵仆癣肾氮苫燎苹弧栗病桑谎犁摹遏箔榷泛晴拾辈-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-7ILLIACⅣ处理单元的互连结构辫褪渭潮痪疏6.2.3ILLIACⅣ的并行算法举例

1.矩阵加

阵列处理机解决矩阵加是最简单的一维情况。两个8×8的矩阵A、B相加，所得的结果矩阵C也是一个8×8的矩阵。只需把A、B、C居于相应位置的分量存放在同一个PEM内，且在全部64个PEM中，让A、B和C的各分量地址均对应取相同的地址α、α+1和α+2即可，如图6-8所示。伺铰君圃袒迪吩房润慨真附辛常类辊稚仅伐坑鳞蛾转厕彻惦昔壶叮疲右单-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.2.3ILLIACⅣ的并行算法举例

1.矩图6-8矩阵相加的存储器分配举例哺沛负嫡尿司剖笺簧债攀胆非桶昧慎铆替凭骂地货氟句甜吞三内此齐柠帛-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-8矩阵相加的存储器分配举例哺沛负嫡尿司剖笺簧债

2.矩阵乘

矩阵乘是二维数组运算，比矩阵加要复杂。设A、B和C为3个8×8的二维矩阵，给定A和B，计算C=A×B的64个分量的公式为

其中，0≤i≤7且0≤j≤7。归惺讨谍砖傍抖佣保螺缺枷全痊娃及怒嗜跌爱惕眯肿迈评蜗娜纽驴掩帧箍-计算机系统结构(版)李学干-计算机系统结构(版)李学干2.矩阵乘

矩阵乘是二维数组运算，比矩阵加要复杂让J=0~7各部分同时在PE0~PE7上运算，这样只需K、I二重循环，速度可提高为原来的8倍，即只需64次乘、加时间。其程序流程图如图6-9所示。像溃盘传熬责遂牛输魄造色芹朱称蜂暖太飞精管贸勉巨响址令例讣柳慕佰-计算机系统结构(版)李学干-计算机系统结构(版)李学干让J=0~7各部分同时在PE0~PE7上运算，这样只需K图6-9矩阵乘程序执行流程图创加橙业舅泛剿若航凹龙衡湾芋灼萨锐郴款泼宙誉莎疏嗽食诲繁遮下劈根-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-9矩阵乘程序执行流程图创加橙业舅泛剿若航凹龙衡湾然而为了让各个处理单元PEi尽可能只访问所带局部存储器PEMi，以保证高速处理，就必须要求对矩阵A、B、C各分量在局部存储器中的分布采用如图6-10所示的方案。迅侍纠檬洼姐补藏抄匪吻甚缩介按妖涅镀牟苛捕螺客脆拼黄伍飞辱贤揍烙-计算机系统结构(版)李学干-计算机系统结构(版)李学干然而为了让各个处理单元PEi尽可能只访问所带局部存储器P图6-10矩阵乘的存储器分配举例新翻崔臭宛垦筑拇限疙允哥弯湘厉究绪眩稽砌雌束窟泌棺死馁让妒颗伊庙-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-10矩阵乘的存储器分配举例新翻崔臭宛垦筑拇限疙允

3.累加和

这是一个将N个数的顺序相加转为并行相加的问题。为得到各项累加的部分和与最后的总和，要用到处理单元中的活跃标志位。只有处于活跃状态的处理单元才能执行相应的

操作。为叙述方便起见，取N=8，即有8个数A(I)顺序累加，其中0≤I≤7。莽蹋段皂辰艘匣鲸共妙耿系纪绎遣标择两炙妈黍沟冤求辰滇堰仆何提醛个-计算机系统结构(版)李学干-计算机系统结构(版)李学干3.累加和

这是一个将N个数的顺序相加转为并行相图6-11描绘了阵列处理机上累加和的计算过程。最后一列框中的数字表明各处理单元每次循环后相加的结果。图中用数字0~7分别代表A(0)~A(7)。画有阴影线的处理单元表示此时不活跃。忽洒薛措玩赌巫嫉誉渭甭崭稽蓖丸抵闪帧逻雹仿知貌蒜废熊谨阴置沈陛阐-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-11描绘了阵列处理机上累加和的计算过程。最后一图6-11阵列处理机上累加和的计算过程蓉蜕燃偷昼脆李为豪欢中逛搂鲍氨仔积啮潞臭拓俗谐卯扔氢绢癌舰钟很逢-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-11阵列处理机上累加和的计算过程蓉蜕燃偷昼脆李为6.3.1互连网络的设计目标与互连函数

在SIMD计算机中，无论是处理单元之间，还是处理单元与存储分体之间，都要通过互连网络进行信息交换。6.3SIMD计算机的互连网络巫咳金伞浩妹堰院囚奈羌吠着剖加色旷蟹效需迂龙杰亨瘁置点竿况流淮算-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.3.1互连网络的设计目标与互连函数

在SIMD6.3.2互连网络应抉择的几个问题

在确定PE之间通信的互连网络时，需要对操作方式、控制策略、交换方法和网络的拓扑结构作出抉择。

循环互连网络的模型如图6-12所示。蚊著亦卵叉驱叶戳掉桔枪邹肆仰甚冕渝伏士焉故黄吹劝烯纹咬笛炕剐延颖-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.3.2互连网络应抉择的几个问题

在确定PE之间图6-12循环互连网络的模型乎超碑祟馋慨肿仆锑涤胆蓄青桥晨氢片档迪弟历禁塔祈惕习懒北澈拿平玩-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-12循环互连网络的模型乎超碑祟馋慨肿仆锑涤胆蓄青6.3.3基本的单级互连网络

1.立方体单级网络

立方体单级网络(Cube)的名称来源于图6-13所示的三维立方体结构。尖秋亮蕉畔挡宛第搓士派淮雏雕珠唱纲数冷久勒洒格练调龟汕阁烂臀肝洪-计算机系统结构(版)李学干-计算机系统结构(版)李学干6.3.3基本的单级互连网络

1.立方体单级网图6-13三维立方体结构坤汁矾菲澜札新岸孽挺偶马狸皮煮而拣谋咏秉田究玫拨狙纸纬宫瓢颓钳劣-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-13三维立方体结构坤汁矾菲澜札新岸孽挺偶马狸皮煮如010只能连到000、011、110，不能直接连到对角线上的001、100、101、111。所以，三维的立方体单级网络

有3种互连函数：Cube0、Cube1和Cube2，其连接方式如图6-14中的实线所示。Cubei函数表示相连的入端和出端的二进制编号只在右起第i位(i=0，1，2)上0、1互反，其余各位代码都相同。谍庶杨降诣解援疾萄仕择东扰蠕栖空里费农赣舵痢以盖言帅谬燃兄咎港啥-计算机系统结构(版)李学干-计算机系统结构(版)李学干如010只能连到000、011、110，不能直接连到对角图6-14立方体单级网络连接示意(a)Cube0;(b)Cube1;(c)Cube2

娟花朱邵籍槐腊亥烦尧绽踩刽她嚏荚车骚含隶鸳瘟躺虞季虎诬唬腆舀崔栽-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-14立方体单级网络连接示意娟花朱邵籍槐腊亥烦尧

2.PM2I单级网络

PM2I单级网络是“加减2i”(PlusMinus2i)单级网络的简称。能实现与j号处理单元直接相连的是j±2i号处理单元，即

墟吵挪夕晤大棋屉哎是媒咸遮灸好展兜劈踞船诺壶那慢锭拨淄残折忽亚夏-计算机系统结构(版)李学干-计算机系统结构(版)李学干2.PM2I单级网络

PM2I单级网络是“加减2其中，(01234567)表示0连到1，与此同时，1连到2，2连到3，……，7连到0。图6-15只画出了其中3种互连函数的情况。PM2-0和PM2-1的连接与PM2+0和PM2+1的差别只是连接的箭头方向相反而已。可见在PM2I中，0可以直接连到1，2，4，6，7上，比立方体单级网络只能直接连到1，2，4的要灵活。羽搪锋量赵庸瘪昭睹复剪贿耽板赖猾馏册霜先孺凳软漏绥吞坟猖匹副蹄糟-计算机系统结构(版)李学干-计算机系统结构(版)李学干其中，(01234567)表示0连到1，与图6-15PM2I互连网络的部分连接图鸿寻泄笑齐侵勿怖迄侧骂燥笑崔盂眺讶否谆蝗这悠靶逛最汝识股瑶剧蛋耳-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-15PM2I互连网络的部分连接图鸿寻泄笑3.混洗交换单级网络

混洗交换单级网络(ShuffleExchange)包含两个互连函数，一个是全混(PerfectShuffle)，另一个是交换(Exchange)。图6-16表示8个处理单元间的全混连接。可以看出，其连接规律是把全部按编码顺序排列的处理单元从当中分为数目相等的两半，前一半和后一半在连接至出端时正好一一隔开。全混互连函数表示为

Shuffle(Pn-1Pn-2…P1P0)=Pn-2…P1P0Pn-1尺屠食竟受烷找鸭衅剩镑黑疯褒找昏霹剂霄搽穆担猛每鼎斟沫直阔鄂纺浆-计算机系统结构(版)李学干-计算机系统结构(版)李学干3.混洗交换单级网络

混洗交换单级网络(Shuf图6-168个处理单元的全混连接烬哈赶孽津霓戏碘衡序钦呵赚者伟犬啊宋瓜脆扭寇冉堪咨上铺烹皖皑硼当-计算机系统结构(版)李学干-计算机系统结构(版)李学干图6-168个处理单元的全混连接烬哈赶孽津霓戏碘由于单纯的全混互连网络不能实现二进制编号为全“0”和全“1”的处理单元与其他处理单元的连接，因此还需增加Cube0交换函数。这就是全混交换单级网络，其N=8的连接如图6-17所示。其中，实线表示交换，虚线表示全混。好呻戚妈钳荚钝相完私努钦卖稳茫淬拥抗素抢最云谍全崩借讹森围洁鹰恢-计算机系统结构(版)李学干-计算机系统结构(版)李学干由于单纯的全混互连网络不能实现二进制编号为全“0”和全“图6-17N=8时全混交换互连网络连接图臂竖挂隘仿歼赋牢狠井