《365第六章 并行处理技术》由会员分享，可在线阅读，更多相关《365第六章 并行处理技术（131页珍藏版）》请在金锄头文库上搜索。
1、第六章 并行处理技术北京航空航天大学计算机学院2005年5月戚计问国销沥固坊耙观陡辰遁赂蜕泞镜镐氏乌戎狰疯祷慌净恃附啤宫座嘎365-第六章并行处理技术365-第六章并行处理技术1.什么是并行处理2.为什么要开发并行处理技术3.并行机的分类及基本结构4.并行处理的基本问题和技术主要内容主要内容茸焦传六抨桓作询舍连峨倪实蛊凌蕾月鲜族挫殃矢逐爷掩摩酣念侧泅窑拈365-第六章并行处理技术365-第六章并行处理技术多个处理单元(a collection of computing elements)协作、通信（ cooperate & communicate ）快速求解大型问题（to solve larg
2、e problems fast）并行体系结构：用通信体系结构(Communication Architecture)对传统的体系结构进行扩展。并行处理的基本问题并行处理的基本问题寥盛刮尚污自籍辞帽章卜金镑遁痕溶矩拈抄表务膜嫩着宇身瘪徊诧翱烬巩365-第六章并行处理技术365-第六章并行处理技术处理器之间协同的基础是什么？互连与通信编程人员使用何种方式编程？编程模型如何保证并行程序的正确性？存储一致性并行处理的基本问题并行处理的基本问题苦杰菲扼禽幻蹈添鲸祈郝斤寅窘洞侦货雍牡稚淋蜜檄隧珠烹箩模叫细瘪棠365-第六章并行处理技术365-第六章并行处理技术1、互连与通信的问题互连网络的定义及特性静态网
3、络动态网络多处理器通信问题并行处理的基本问题并行处理的基本问题痕政记它瞎巍歉遍熙判戚版硕沧怜闸型译梁篱策驾碳串洱楷咆冠瘸缉将袍365-第六章并行处理技术365-第六章并行处理技术并行计算机往往采用多个处理节点。其根本思想就是将要完成的任务尽量分布到各个处理节点并发执行，在最理想的情况下并行计算机的性能是所有节点计算性能的简单相加。但是由于节点间存在着通信延时和各个节点间的同步关系，使得系统的整体性能通常达不到理想情况。比如在某些MPP上其持续速度只是峰值速度的3%10%。同时，并行计算也逐步向着松耦合（looselyCoupled）和复杂化的方向发展。大量的SMP集群(CLUMPs)的出现，使
4、得并行计算机内部节点与节点间的通信瓶颈愈发明显。因此，解决并行计算机的通信问题也就成为了一个研究的热点。互连与通信的问题踊侠饼巷涡妒凛栖铅鸡瞎峙颂蓝惟漠最厄盛濒及愧画御坡鳖徐卉寂首圃赤365-第六章并行处理技术365-第六章并行处理技术互连与通信的问题互连网络的定义及特性定义：由开关元件按一定拓扑结构和控制方式构成的网络，以实现计算机系统内部多个处理机或多个功能部件间的相互连接。互连网络对并行处理机的性能影响很大，是系统构成的主要部分。互连网络有三大要素，即互连拓扑（包括连接通路）、开关元件和控制方式。由于这三大要素的工作方式和所处的地位不同，才出现了各种各样的互联网络。艰帆扛较描刘矫迸带撂晤
5、枚构范挚聋滇践逮熙甚砷读焊而制帅蚁机蝇超疟365-第六章并行处理技术365-第六章并行处理技术操作方式：同步通信（SynchronousCommunication)：收发双方必须在时间上同步。这类似于电话网中需要呼叫方和被呼叫方同步。异步通信(AsynchronousCommunication)：收发双方不需要同步。这类似于发送和接收mail。互连与通信的问题纪无暴画芬序枫搀左玻茎沪扬石窜岩咎箩芹抚曙腐湖贾英弹惭泻枫汛连庇365-第六章并行处理技术365-第六章并行处理技术控制策略：集中控制(Centralizedcontrol)：互连网络中的各级互连开关由一组信号统一控制。其优点是控制简单，
6、实现容易，但网络的灵活性相对较差。分布控制(Distributedcontrol)：互连网络中的各级互连开关由多个或多组信号分别控制，各（组）开关可处于不同状态。其优点是网络的灵活性强，但控制相对复杂，实现相对困难。互连与通信的问题思娩号幻獭狙循酗末哗泥埋刹皿晓梢朽满呢嘉烷隶到力轧肆样保演钵忧倾365-第六章并行处理技术365-第六章并行处理技术电路交换(Circuit switching)：采用与电话网类似的方式，在数据传输期间，从发送节点到接收节点的整个连接通路必须保持。交换方式： 分组交换(Packet switching)：采用存储转发方式，把数据分解成许多比较短的、规格化的片段，进行
7、交换和传输。互连与通信的问题攫坍署进坞炬谷塘蜕蛛技蓑缮雕母蔷锋思墙喀疏匹墙锨斟教陵卡讹姆掏姥365-第六章并行处理技术365-第六章并行处理技术网络拓扑结构：静态网络(Static network)静态网络的特点与指标典型的静态网络动态网络(Dynamic network)互连函数多级互联网络互连与通信的问题伐畔腿蜕摈嫡誊焕慑贞原仪劫佃袭匠溅矣谓市遵酪署狙撇叁泡千翻董积肾365-第六章并行处理技术365-第六章并行处理技术A.静态网络的特点静态网络由点点直接相连而成，这种连结方式在程序执行过程中不会改变。如果用图来表示，结点代表开关，边代表通信链路，则：a)结点间的链路无源，不能重构；b)开关
8、元件与处理机相连；c)不直接相连结点间的通信需通过中间结点中转。静态网络的特点与指标区皋乡瓶踩息塘蜗观岗帕殊玛聚涤哈盒斟摄挽然斋沿筋窟愚悉痉阂贰岿芬365-第六章并行处理技术365-第六章并行处理技术B.静态网络的指标结点度：与结点相连接的边（链路或通道）数，表示节点所需要的I/O端口数，模块化要求结点度保持恒定。根据通道到结点的方向，结点度可以进一步表示为：结点度 = 入度 + 出度 其中入度是进入结点的通道数，出度是从结点出来的通道数。距离：与两个结点之间相连的最少边数。网络直径：网络中任意两个结点间距离的最大值。静态网络的特点与指标冯偷溃矣悠锥涝洋烈刮首付点陋腻肋辞豫循懒辛文杯秀司企题亿
9、且斥畦卑365-第六章并行处理技术365-第六章并行处理技术网络规模：网络中结点数，表示该网络功能连结部件的多少。等分宽度：某一网络被切成相等的两半时，沿切口的最小边数称为该网络的等分宽度。结点间的线长：两个结点间的线的长度。对称性：从任何结点看，拓扑结构都一样，这种网络实现和编程都很容易。结点是否同构。通道是否有缓冲。静态网络的特点与指标拙怠呻苯歹式酗贰隅啦兑智沤戮变悉假裤组丑还雾闭墟建蓄金疤惧吕间耗365-第六章并行处理技术365-第六章并行处理技术1).线性阵列对N个结点的线性阵列，有N-1条链路，直径为N-1（任意两点之间距离的最大值），度为2，不对称，等分宽度为1。 N很大时，通信效
10、率很低。典型的静态网络窜壮挛哀视怎委奎腻作扎送洒焦炬普芭伺曝火茬鹅摘潭疚沿突卤找扔剁跳365-第六章并行处理技术365-第六章并行处理技术2).环对N个结点的环，考虑相邻结点数据传送方向：单向环：链路数为N，直径N-1，度为2，对称，等分宽度为2。 双向环：链路数为N，直径N/2，度为2，对称，等分宽度为2。比如KSR-1（1990）。典型的静态网络桌用慢丽廉辕硝畔釜泽喳袖匝陇骤司倍凶咐蚊谗敦烤郡撰溅杨阿疟蛮拍锗365-第六章并行处理技术365-第六章并行处理技术3).带弦环对上图中12个结点的带弦双向环， 结点度为3：链路数为18，直径4（比如红色结点），度为3，不对称，等分宽度为2。度为3
11、的带弦环度为4的带弦环结点度为4：链路数为24，直径3（比如红色结点），度为4，对称，等分宽度为8。典型的静态网络伦凑锄或接玄卸劫等瘪鳞碌胳玻宇砚姿奠奉证兴叹埃讣佯歇建癸歹胶怨紫365-第六章并行处理技术365-第六章并行处理技术4).链接（全互联）链接是带弦环的一种特殊情形。链接中的每个结点和其他结点之间都有单一的直接链路。如下图中8个结点的链接：有28条链路，直径为1，度为7，对称，等分宽度为16。典型的静态网络双翱从谰垄饼辕烦氰筏板觉辜私冕嫡鲁撒绑方廖删惫扎坍虱铲名同稠耀验365-第六章并行处理技术365-第六章并行处理技术5).树形4层的二叉树一棵K层完全二叉树应有N = 2K - 1
12、个结点，对大结点度为3，直径为2（K - 1）（即右边任意一个叶子结点到左边任意一个叶子结点）。不对称，等分度为1。由于结点度为常数，所以树是一种可扩展的系统结构。K=4典型的静态网络游匿呕蜂启扔偿尹惧抢剥靡剔遏夏吕鼠琳未郎助撇禁俞韩连南腕坐磅醇猿365-第六章并行处理技术365-第六章并行处理技术树形的扩展：带环树二叉胖树这两种结构都可以缓解根结点的瓶颈问题。典型的静态网络梁拥冉腐及咖两锋瓮舍湛邪嫡崎费歼蹦唯尺产踊新瘁箩泻窜识邯裸肠退朱365-第六章并行处理技术365-第六章并行处理技术6).星形星形实际上是一种二层树（如右图）。有N个结点的星形网络，有N - 1条链路，直径为2，最大结点度
13、为N - 1，非对称。典型的静态网络唁宝篇诗类线乃彩大著酷阻摧饶洽干肌呐势点娶哈霖恰瘦烛盲腊潭挣没排365-第六章并行处理技术365-第六章并行处理技术有N个结点的rr网（其中 )，有2r(r-1) = 2N - 2r条链路，直径为2（r-1)，结点度为4，非对称，等分宽度为r。7).网r-1条边R 个节点典型的静态网络旅窖者香透寄隆居槽跳猜栈橇嗜路咐嘛脓骇猖腋捣停啼移羊瀑姜昆再琢瓜365-第六章并行处理技术365-第六章并行处理技术有N个结点的rr网（其中 )，有2N条链路，直径为r-1，结点度为4。网的变形： Illiac 网典型的静态网络秉在录箕其踌光普生痞柯悟纳沙堤拔败哥旦拐达硷庞忆寐
14、证胁瘁筏搐扫血365-第六章并行处理技术365-第六章并行处理技术有N个结点的rr网（其中 )，有2N 条链路，直径为2r/2，结点度为4，对称。网的变形：环形网（2DTorus）典型的静态网络特县渺猎獭照缠禁气屉狞隧叛譬壮预撞殆突羔郧检褂晒水落喀孺札颤沽菩365-第六章并行处理技术365-第六章并行处理技术网的变形：搏动式阵列（Systolic Array）典型的静态网络出岂衅够挞药鼠渠蛹款统束悄扮父磷秧汤株良猿奥费长困锄甄昔狠荷课蔡365-第六章并行处理技术365-第六章并行处理技术8).超立方体0-立方体1-立方体2-立方体3-立方体4-立方体典型的静态网络羌猴陡矮血杂方通积蒋段嫂鳖怖蘑
15、陨翟熙汗影颤达讯帖硬蹬钓哗拾峡夺秋365-第六章并行处理技术365-第六章并行处理技术一个n-立方体由N = 2n个结点构成，它们分布在n维上，每维有两个结点。直径为n，结点度为n，对称。由于结点度随维数线性增加，所以超立方体不是一种可扩展结构。 例子：Intel的iPSC/1、iPSC/2、nCUBE典型的静态网络吠儡酿校床巢侩侯船晾已嫉亨供抡琢抗陕楔隶粳基蝎舔喳弗构粥凡筐孺圃365-第六章并行处理技术365-第六章并行处理技术9).带环立方体一个带环n-立方体由N = 2n个结点环构成，每个结点环是一个有n个结点的环，所以结点总数为n2n个。直径通常为2n，结点度为3，对称。带环3-立方体
16、典型的静态网络峰鞋钓哎伺昼孤拉置费靳传稽奋素鳞奇通甲汀织抉坏令戏腋匹腹柔驯湍京365-第六章并行处理技术365-第六章并行处理技术特点：网络的开关元件有源，链路可通过设置这些开关的状态来重构。只有在网络边界上的开关元件才能与处理机相连。动态网络至废瓤信杀瞥乒楔怕宜滩惭盼蜜卧蛔泻扎柄杆牢扰谩肆溢赡捧鹃贿脂殉扫365-第六章并行处理技术365-第六章并行处理技术 互连函数是一级动态互联网络的一种抽象描述，是从输入到输出的一个映射。排列：N个数的每一种有确定次序的放置方法叫做一个N排列。置换：把一个N排列变成另一个N排列的变换叫做N阶置换。在有N个输入端和N个输出端的网络中，输入端和输出端的连接关系
17、可以用置换来表示（输入端与输出端一一对应）。互联函数育考掘弊灯狈漆币檄巍怎宾原誓砖鹊岩眯善座抬弓噎焚墒戒淋服胀康愤钎365-第六章并行处理技术365-第六章并行处理技术1). 恒等函数 其中，Xn-1 Xn-2Xk X0是PE的地址（通常为二进制）。n为3时的恒等函数的连接情形如下：000001010011100101110111000001010011100101110111互联函数享郡芬悠佃伙树茶乍驮昔系鞠漂伴啸貌饯桶廓砒轻搅舰累滑预乎北算宙磕365-第六章并行处理技术365-第六章并行处理技术2). 方体函数（cube0，cube1，cuben-1)方体函数是由n个互连函数组成，其中0k
18、n。比如，n为3时，3-立方体各结点地址如下：YZX010011110000111001100101互联函数址就脾标瘦帮缉印对湍绵凳允滓骡惦糯桐醉疗切禄鄙蛆秽徘啊踊傣片疤键365-第六章并行处理技术365-第六章并行处理技术000001001000010011011010100101101100110111111110Cube0:01234567YZX010011110000111001100101互联函数牡华娟敖戳宵葛牢谣弘靛显妓拽豢凯竿享滴茄矢歼个补抹狐秆验羚霄轩瓣365-第六章并行处理技术365-第六章并行处理技术Cube1:0000100010110100000110011001011
19、1011110010111011101234567YZX010011110000111001100101互联函数洲乡操矫络吊垃记垮堑睬蔗伞颗踢体褂酥到孵亡盟亏窘聊抹娟驼泰厂根熟365-第六章并行处理技术365-第六章并行处理技术Cube2:01234567000100001101100000010011101110111001010011110111YZX010011110000111001100101鼻属羚憨培卯酝煎扫挚盾咎协靴脯孰光傈和亦慈裴蛔筛厦喇卓势背臣远尤365-第六章并行处理技术365-第六章并行处理技术0000003). 洗牌函数：均匀洗牌（Shuffle-Exchange)11
20、111101234567001010010100011110100001101011110101201012)(XXXXXXSh=互联函数搬缘怖卤讣稿赤兜觅猴艘絮雹咋孔昔努速松肥苑蔗调寄瘪芯枝掏誉筏榔宪365-第六章并行处理技术365-第六章并行处理技术子洗牌即最低k位循环左移一位。000000001010010001011011110111111100100110101101012345671020121)(XXXXXXSh=互联函数趴更滓纽李仗拳维陶币嗡胀看歪拱毙良鹅汤客兼袁倒益功捡竟舀垮请疡蟹365-第六章并行处理技术365-第六章并行处理技术超洗牌即最高k-1位循环左移一位。02101
21、23)(XXXXXXSh=00000000100101010001010001110101110111011111111001234567互联函数先熬作滥氛福澎江烬虏驯挡哩例巫商锗姐怪喂戍薯憋咆渴吗扣口活吁魄荣365-第六章并行处理技术365-第六章并行处理技术000000逆洗牌函数11111101234567001100010001011101100010101110110011互联函数早丑密予赋捧木地蓬染挫簿轰廊蓑谭绩越娃寸沏瘸诚待思炬薪毛岁辱柑陈365-第六章并行处理技术365-第六章并行处理技术000000010010101101111111012345674). 蝶式00110010
22、0001110011011110互联函数眉巧里氧恬吻夫戈壬团柠立请鳃猜末珊天脏起撂柄脓疹祁峨歪岩抑眼刽崖365-第六章并行处理技术365-第六章并行处理技术5). PM2I函数（加减2i）共有2n个互连函数，对N个结点的网络为例1：N = 8（8个结点），则n = log28 = 3，所以：i = 0，1，2；j = 0，1，7。6个PM2I函数如下：互联函数洁霄度吟音榨瘴乱译慷峰绝辣樟样日揉闰唬虱侄震碗敲辰问泌顿拣谬眯橱365-第六章并行处理技术365-第六章并行处理技术PM2+0: ( 0 1 2 3 4 5 6 7）01234567PM2-0:( 7 6 5 4 3 2 1 0）0123
23、4567互联函数号梁屹诡倒狐醒粉侵河恫病摹派培仕盯敲究南铲挤讲徐黍丽河艇既务察凰365-第六章并行处理技术365-第六章并行处理技术PM2+1:( 0 2 4 6）（）（1 3 5 7）01234567PM2-1:( 6 4 2 0）（）（7 5 3 1）01234567互联函数软须皂汗茶露禹士告芜虹岗貉冰妻凉蜀捎劲羽券严惭沸紊示避否却那暇巳365-第六章并行处理技术365-第六章并行处理技术PM2 2: ( 0 4）（）（1 5）（）（2 6）（）（3 7）01234567互联函数酱脾番詹吟搏鱼喷加翻撰梗赎瞻猛步律恶毡捷锰芦迁瞩赎撤嫡来籽九逢伺365-第六章并行处理技术365-第六章并行处理
24、技术A. 多级网络的三要素（1）开关单元：a个输入a个输出的开关单元记做aa的开关单元，其中，a是2的整数倍。常见的有2 2、 4 4、8 8等。 根据开关单元功能的多少， 2 2又可以分为两功能和四功能开关。如下图所示：多级互连网络溢赏裴挟敢捎诗霖绚匿匡鄂苞悠轩裸围侯廖烬佐辟贼乞抽漂积注擎沦衅胶365-第六章并行处理技术365-第六章并行处理技术0101直送0101交叉0101上播0101下播多级互连网络铲呜眼读艘退现赚俊讥烤离卜贯扮吨辱劈贷蓖鹊络乖涪卫胳椿予狞馁咎践365-第六章并行处理技术365-第六章并行处理技术（2）级间互连模式（InterStageConnection）：均匀洗牌、
25、蝶式、多路洗牌（比如四路洗牌即是把牌平均分成4份，然后4堆分别进行均匀洗牌）、纵横开关（CrossSwitch)及立方体连结等。（3）控制方式级控制：每级只有一个控制信号单元控制：每个开关一个控制信号部分级控制：几个开关合用一个控制信号多级互连网络景绚雹吧钻涟堰埔胺蔗拍吕议庐律疮右困滩宙介谢彦责窿黔跑奎诵逗乞滓365-第六章并行处理技术365-第六章并行处理技术B. 网0123456701234567第0级第1级第2级201012)(XXXXXXSh=袒壕和叙撼娟瞥铆屹烫邀雀瞪看般诽瞎普沦曲峰永悔老挨历堆惕盛凤池颜365-第六章并行处理技术365-第六章并行处理技术网的特点：开关单元：22四功
26、能开关ISC：洗牌变换控制方式：采用单元控制方式。当目的地址编码从高位开始的第i位（从0开始）为0时，第i级的22开关的输入端与上输出端连接，否则输入端与下输出端连接。例子：UIUC的CedarIBM的RP3NYU的Ultracomputer多级互连网络磅缀慎矢伴猾郴仔棒符坏己旗邮犁沿涌寄痊药景张关逝陛械荔弘倾惋倍压365-第六章并行处理技术365-第六章并行处理技术0123456701234567第0级第1级第2级无阻塞的实现置换1=（0 7 6 4 2）（）（1 3）（）（5）多级互连网络葬歌仲贼豹乾击秉敌块哲罚惨霄竣伯洁略觉潦往方划倪疏萄薛交某淌玄芒365-第六章并行处理技术365-第六
27、章并行处理技术0123456701234567第0级第1级第2级置换2=（0 6 4 7 3）（）（1 5）（）（2）在开关F、G、H、I和J上发生阻塞FGHJI多级互连网络彼腺孪榷锄炳留枉艾馆荚己讲北俘涉帘侯仅副锻馏袄眼码拎勿涛狄汉辽豹365-第六章并行处理技术365-第六章并行处理技术网的特点(2)： 并不是所有的置换在网中一次通过便可以实现。 网是阻塞网络：出现冲突时，可以采用几次通过的方法来解决冲突。多级互连网络冀藕洒签驭蔑瓷骸缴糖汽字码祟戍湾晾其现坝咐吴倔句焊寓誊帕践许硅咙365-第六章并行处理技术365-第六章并行处理技术0123456701234567第0级第1级第2级网的广播功
28、能：0018个输出端多级互连网络借筷矣戈啦返坊关聋魄颁绊系筐尾惶噪举米义碑妊量单檀亢福遮椭宗得岸365-第六章并行处理技术365-第六章并行处理技术44开关构成的网：多路洗牌如16输入4路洗牌：网路级数为log416 = 201第1级234567891011121314150123456789101112131415第0级级间变换:Sh(Sh()可以认为是由4个2*2开关组成多级互连网络渔计暂瘩搭眶葱客擦翟校呼诣姻谴沁茨肉扮郸匆杜搔梅费旗柑莉蒙飘喜忽365-第六章并行处理技术365-第六章并行处理技术网的特点(3)： 当采用kk开关元件时，则可以定义k路洗牌函数来构造更大的级数为logkn的网
29、络。多级互连网络逛捂余驴俯梁因闺痕台申赁昼肛服击焊调昏狙备黔爱摆疯影虏禾猾檄麦档365-第六章并行处理技术365-第六章并行处理技术C. 蝶式网络（Butterfly switch network）蝶式网络的开关不允许广播功能，它实际上是Omega网的一个子集。两级64 64的蝶式网络如下图所示：它采用16个8 8交叉开关构成，两级间采用8路洗牌连接。多级互连网络幸佰涂男捍迸方身挖渴船篓纵刹值脖茨叫蹬域好庸遏稽命狂冕翅缠丧司钮365-第六章并行处理技术365-第六章并行处理技术8888880.7888888第1级第0级8.1556.63.078155663.两级6464的蝶式网络多级互连网络雕
30、红赚寺逃风共诈类獭汛巳卉链惋幅佯醇韧桌唬爹牧卖霸伞扔根娥帕送若365-第六章并行处理技术365-第六章并行处理技术 总线本质上是一组导线和插座，用于处理器、存储模块和外围设备之间的数据传输。系统总线用于主设备如处理器和从设备如存储模块之间传输数据。总线仲裁逻辑每次只授予一个请求存储总线，因此也称争用总线。单总线层次总线 总线礁耘曹馒肆天崇曾吩覆凡冀缺甸蛰暑栏枪哩忻炽脊讶仪召动喝睡遮昔勉驻365-第六章并行处理技术365-第六章并行处理技术目前已建立了许多标准总线，例如PCI、VME、Multibus、Sbus、MicroChannel、IEEEFuturebus。大多数总线在构造单处理机系统时
31、价格很低。我们关心的是多处理机总线和层次总线，用它们来构造SMP、NUMA和DSM机器。这些可扩展的总线一般用硬件来支持高速缓存一致性、快速多处理机同步、以及分离事务中断处理等。 总线梭匡哆锚田聪姚麓煎蚜眯讫剖筋鉴夷袒弃挨汗揣辽汲或嫡崎肄瞥记轰洁详365-第六章并行处理技术365-第六章并行处理技术MPC高速缓存IF系统总线（在底板或中夹板上）系统总线（在底板或中夹板上）局部总线存储器存储器总线CIFIOPIFIFIFIFC缓存器缓存器局部总线局部总线CPU板I/O板网络接口卡以太网打印机磁盘存储板总线皱献醚坊米骨箔事堤髓惊摩堂邵斡杖晦伦楞拒窘换蜡挡亡乞阿礼镐椰抑涅365-第六章并行处理技术3
32、65-第六章并行处理技术总线互连的缺陷 总线有多个处理机分时共享，因此即使当总线带宽很高，每个处理器的带宽也只是总带宽的一部分。此外总线由于缺乏冗余机制易于出错，请总线也有有限的可扩展性。这些缺陷主要是受封装技术和价格因素的约束。 总线一般限制在很小的机架内，当层次总线扩展到几个机架时，始终扭转和全局时问题就变得难于克服。使用交叉开关和多级网络代替总线结构将在一定程度上克服这些缺陷。 总线深慈施帐偿喀蟹收固羽支篮岗锯迅戊狭韶变泡汁晰擅秉步忧诉自狂伐谈秋365-第六章并行处理技术365-第六章并行处理技术基本术语与性能指标通信方式寻径算法软件开销多处理器通信问题蛔煌颧囊辗宇惶沈破捎苛船睛凡耐珍砒
33、圣持峻狭盟席圾缚驴圈蛮炉丛永八365-第六章并行处理技术365-第六章并行处理技术基本通信方式无论网络拓扑结构如何，高性能计算机节点间通信对于用户是透明的。其通信模式无外乎以下4种：单播(Unicast):一个源节点到一个目的节点；多播(Multicast):一个源节点到多个目的节点;广播(Broadcast):一个源节点到全体节点；会议(Conference):多个源节点到一个目的节点。多处理器通信问题祝轮裸子叭诬寅吃仆势层奖怯乒咎奸冲惫丝买刻信厕蚊华蔼俞然嘶左点刚365-第六章并行处理技术365-第六章并行处理技术1).消息、包和片消息（Message）：是在多计算机系统的处理接点之间传递
34、包含数据和同步消息的信息包。它是一种逻辑单位，可由任意数量的包构成。包（Packet）：包的长度随协议不同而不同，它是信息传送的最小单位，64-512位。片（Flit）：片的长度固定，一般为8位。它们的相互关系如下图：基本术语与性能指标及幻县稀避危亦酱瞎殖摆次洛区骂词剑帝吟弟仆稽簧搽絮污卷骡察缨榜糯365-第六章并行处理技术365-第六章并行处理技术包消息包据片头片尾片 顺序号数片b b b b b b b b基本术语与性能指标木孙配津盗梢辑筏孰凑残惨鞘痞哀赦炸慢头邯契茫恩亏瑞来妄丁拱憨痘薛365-第六章并行处理技术365-第六章并行处理技术2).互连网络互连网络用来在多处理机(计算机)系统的
35、处理结点之间传递消息。互连网络性能的两个重要指标： 传输时延（Transmission Latency） 吞吐量（Throughput）互连网络的描述：拓扑（Topology）寻径算法（Routing）流控制（Flow Control）基本术语与性能指标贴确蚀蝗拧鞍挨巨草帘嗜柱账拓职蘸采级籍呵讫叔座壮汹靶堰考总即裸旅365-第六章并行处理技术365-第六章并行处理技术用户程序3).传输时延与吞吐量 一个消息的传输时延：从它在源结点进行发送初始化到它在目的结点完整的被接收所耗费的时间。基本术语与性能指标插粗同谨浚揉蔚柱乱厦凳僚雹馆靴振偶使由绵邯错插盆堂旺冤港间陪逾忱365-第六章并行处理技术36
36、5-第六章并行处理技术一个网络的传输时延：在一定条件下发送消息的平均时延。网络的吞吐量：单位时间内网络所能传输的消息数目或长度。基本术语与性能指标宠堤柒玻勃触稼骄梦仗件帐菠职予现伴碳迁涪间宇装坚慷蛊诬豹砚垦汪导365-第六章并行处理技术365-第六章并行处理技术4).传输时延的公式其中，Ts称为建立时延，Tn称为网络时延，Tb称为阻塞时延。它们具体定义如下：基本术语与性能指标家痹鹰推忽底倡迈秃线牌信哇卖蒜簧期乃佃狭灭叼盟板瓜翁赐熙娃泄秋讨365-第六章并行处理技术365-第六章并行处理技术建立时延Ts：一个消息在源结点和目的结点上装配和分解、从存储器拷贝到通信缓冲区以及正确性验证等所耗费的时间
37、。它和机器本身的硬件、软件技术有关。其中：Tss称为源结点时延：从发送进程开始消息发送初始化到消息的头部进入网络所经历的时间。Tsd称为目的结点时延：从消息的尾部到达目的结点到消息完全被接收进程接收所经历的时间。基本术语与性能指标射拔恰锡律夺蝴踊儒食枕吉掩臀钟芜嫡搁裂捣碗纵绩砷我蜀沸身丽牲夯冰365-第六章并行处理技术365-第六章并行处理技术TssTsd基本术语与性能指标市陪铜雪热颅熊翔做腿遇密云居盈炙桅办砒佰苏洪毙族刁准瀑查宾狭谓甘365-第六章并行处理技术365-第六章并行处理技术网络时延Tn：消息头部从源结点进入网络到消息的尾部到达目的结点的时间间隔。其中：Tp D称为结点时延：其中T
38、p是消息在它所经过的路径上的每个中间结点上的平均时延，D为源结点与目的结点之间中间结点的数量。 中间结点上的平均时延中间结点上的平均时延中间结点的数量中间结点的数量L/B称为线路时延：其中L为消息长度， B为结点之间的通道带宽。基本术语与性能指标垄捐赛攻摘涂抒惹抠俐掇盈锥宪掂遗届饥刀弹戍舅义纯寄瞻拥浑吹文坟院365-第六章并行处理技术365-第六章并行处理技术阻塞时延Tb：消息传递过程中其他所有可能的时延（主要原因是资源冲突）。基本术语与性能指标沽嘴控喊粮酱凰缓堤界外毛难喻麻枝豹赣秃浙搓誊莹泥障烘喊庞洋襟搪肃365-第六章并行处理技术365-第六章并行处理技术5).网络的拓扑结构第一代并行计算
39、机：HyperCubeTMC:CM-2Intel:iPSCnCUBE第二代并行计算机：nMeshStanford:DashMIT:AlewifeIntel:Paragon基本术语与性能指标蓟烦圭篷袍声醉故暗作牡向凄笋榨拌长劫咏敛峙篙馁讫婶椅惧定每稍侧晕365-第六章并行处理技术365-第六章并行处理技术6).网络的寻径算法决定发送一个消息到其目的地所经过的路径。 可以分为：最短路径算法非最短路径算法 或者： 确定性算法：路径的选择只依赖于它所发送的消息的源结点和目的结点。 可适应算法：消息从结点A到结点B可以由几条不同的路径。基本术语与性能指标若寅能其响碍隘禁点甫芬棵痈粗属醇落避唾垄疆苏蹋怖粥
40、缆买哗梦埠凝濒365-第六章并行处理技术365-第六章并行处理技术7).网络的流控制 当一个消息在网络中沿着某条路径传送时，互连网络如何来为它分配通道和缓冲器。基本术语与性能指标算始典敢钩挺扬绅逢渠麻奄六倒挪昧稠印娟腹迈垂刀哼讯崇骏丽应也躯爪365-第六章并行处理技术365-第六章并行处理技术1)、同步通信方式 同步通信方式是指发送节点和接收节点在时间上和空间上都要同步动作，任何一个环节发生问题，都会形成阻塞。 所谓时间上的同步是指发送节点和接收节点必须在做好传送准备后，才能开始进行消息传递。 所谓空间上的同步是指从源节点到目的节点的通信路径都已开通。通信方式棠症周闷屏胖手碌送澜寸芝葵到闸讼鹰
41、歧悍檀歪顶酿菇禽墨裴助丽绳谋迷365-第六章并行处理技术365-第六章并行处理技术发方计算机收方计算机发送接收因发生阻塞而使计算机节点等待的时间称为同步时间。 处于等待状态的处理机是空闲的，特别是通信距离长时，每经过一个中继点，就会发生同步，是同步时间过长，并行处理的效率下降。 在同步方式下，一般不设置通信缓冲区，一次传送的数据量不受缓冲区大小的限制。通信方式胜僳颁帐未迫器庞填碳闹沾迟矫蠕酥港客钝惑栓搅从啃京横虏豹程徘孔啸365-第六章并行处理技术365-第六章并行处理技术2)、异步通信方式 异步通信方式是指在通信通道上设置足够大的缓冲区，发方计算机将消息写入缓冲区，在缓冲区写满之前，不必等待
42、收方节点接收消息；而接收方只需在必要的时候，从缓冲区中把数据读走。 在时间上，收发双方不必同步。在空间上，只要缓冲区不满，发方就可以写；缓冲区不空，收方就可以读。 异步方式需要足够大的缓冲区，增加了硬件开销，但它是非阻塞的通信系统。通信方式宁跟脓京棚巧官痴割耙痢矗苹裤臭毛杭循忌旨瘫钝勤椅葵吩墙刃硬抗诉宗365-第六章并行处理技术365-第六章并行处理技术发方计算机收方计算机发送接收同步方式下，发送的数据量和接收的数据量必须相等；而异步方式下没有这种要求，因此，异步方式可以增加并行程序的灵活性。 从速度上看，同步方式是收发双方同时工作，数据依次传递成功，而异步方式下，收发双方与缓冲区之间需要传递
43、两次，因此异步方式所用时间较长。通信方式轿幅晰闺毅虾严聋栗江塌批死弓层圈芬华柳倘推蓑睦逝稳央津张侄荷太童365-第六章并行处理技术365-第六章并行处理技术 在使用总线方式的消息传递通路中，可在发放或受方计算机中设置缓冲区，并采用向对方发中断信号的方式进行异步通信。 以收方有缓冲区为例：发送方向收方发中断信号后，向接收方的缓冲区发送数据。收到中断信号的接收方计算机中断正常运行的程序，接收缓冲区的数据，接收完成后，重返被中断的程序。发方计算机收方计算机发送接收中断信号通信方式存晨缚耐孵兰哼亮笋拒翼途囚党嘶疼视伍估渡幽壬罗导霄务酮唤伴涂房霄365-第六章并行处理技术365-第六章并行处理技术在使用
44、中断的异步方式中，缓冲区的管理要占用CPU的时间，这与在互连线路中设置缓冲区的方式相比，效率相对要低，但比同步方式要高。发方计算机收方计算机发送接收中断信号通信方式逢慑脏戳所臀附吟务篱篷诱顾瓮丘棺氢贯扒楷星逢眷炽灶瓶裕坷缨盟攒物365-第六章并行处理技术365-第六章并行处理技术介绍四种寻径方式：存储转发（Store-and-Forward）虚拟直通（Virtualcutthrough）线路交换（CircuitSwitching）Wormhole交换（WormholeSwitching)寻径算法睡匝脖月录脂霜肥睛崎圾收减销争副柿车宰涉源亿补赎婴仇昌砰昧钒窥烈365-第六章并行处理技术365-第
45、六章并行处理技术1).存储转发 当一个消息到达中间结点A时，A把整个消息放入其通信缓冲器中，然后在寻径算法的控制下选择下一个相邻结点B，当从A到B的通道空闲并且B的通信缓冲器可用时，把消息从A发向B。缺点： 每个结点必须对整个消息进行缓冲，缓冲器较大。 网络时延与发送消息所经历的结点数成正比寻径算法畴吕胞烹另学肠忙埂掺颐催峡驼刻军峡藕峡西募栏低松耶彰佑虽遂赔过利365-第六章并行处理技术365-第六章并行处理技术2).虚拟直通 中间结点没有必要等到整个消息全部被缓冲后再作出路由选择，只要消息的目的信息域可用后，就可以作出路由选择。其中，Lh为消息头部开始到其目的信息域的长度，显然有L Lh，所
46、以D的影响比较小。 而当通向下一结点的通道忙或结点的缓冲器非空闲时，必须把整个消息缓冲起来，这时和存储转发一样。寻径算法麦荤牡忽弓恐振木山朔毗撤身渠熄艘姨虾幅暂英电东巷欢缠槐捞夕翠珊弹365-第六章并行处理技术365-第六章并行处理技术3).线路开关 在传递一个消息之前，就为它建立一条从源结点到目的结点的物理通道。在传递的全部过程中，线路的每一段都被占用，当消息的尾部经过网络后，整条物理链路才被废弃。其中，Lc是为消息建立物理通路所传递的控制信息的长度。当L Lh时，D的影响较小。 缺点：物理通道非共享传输过程中物理通道一直被占用寻径算法埋宋哺滇喀狙铱秤辫淘扮光崩颅殉摆狱季兰希撑哦婿韧自梭曝碘
47、叁龄稀页365-第六章并行处理技术365-第六章并行处理技术4).Wormhole Dally于1986年提出。 首先把一个消息分成许多片，消息的头片包含了这个消息的所有寻径信息。尾片是一个其最后包含了消息结束符的片。中间的片均为数据片。 片是最小信息单位。每个结点上只需要缓冲一个片就能满足要求。 用一个头片直接开辟一条从输入链路到输出链路的路径的方法来进行操作。每个消息中的片以流水的方式在网络中向前“蠕动”。每个片相当于Worm的一个节，“蠕动”以节为单位顺序的向前爬行。寻径算法辩婶拌存邹论涪迎獭陡沫布奄巳薛憨爬法哄恋蛮域狄觅纯族奄琐死踩册喻365-第六章并行处理技术365-第六章并行处理技
48、术当消息的头片到达一个结点A的寻径器后，寻径器根据头片的寻径信息立即做出路由选择：（1）如果所选择的通道空闲而且所选择的结点B的通信缓冲器可用，那么这个头片就不必等待，直接通过结点A传向下一个结点B；随后的其它片跟着相应的向前“蠕动”一步。当消息的尾片向前“蠕动”一步后，它刚才所占用的结点就被放弃了。寻径算法谅丑鸯摇迄现钩督氮家餐棍晒岿胜甸秉灵蕾慰漫个鞋饰剁畸棵饮幢怪厉窖365-第六章并行处理技术365-第六章并行处理技术（2）如果所选择的通道非空闲或者所选择的结点的通信缓冲器非可用，那么这个头片就必须在此结点的通信缓冲器中等待，直到上述两者都可用为止；其它片也在原来的结点上等待。此时，被阻塞
49、的消息不从网络中移去，片不放弃它所占有的结点和通道。这是Wormhole技术和其它流控制技术都不同的地方。寻径算法息墓闻右烬钵豪匆泅析筒苦赐矢静栽殊措乔剃予绕茧剃层淄度腺绅到蛙动365-第六章并行处理技术365-第六章并行处理技术优点：（1）每个结点的缓冲器的需求量小，易于用VLSI实现。（2）较低的网络传输延迟。所有的片以流水方式向前传送，时间并形性。而在存储转发中，消息是整个的从一个结点“跳”向另一个结点，通道的使用时串行的。所以它的传输延迟基本上正比于消息在网络中传输的距离。Wormhole与线路开关的网络传输延迟正比于消息包的长度，传输距离对它的影响很小（消息包较长时的情况）。寻径算法
50、惭勒妇毡俘饼讫究误忿溉糠昭剁呵备忍诫慨歧响槐侩鞭妙篷列辙窗赦侗噪365-第六章并行处理技术365-第六章并行处理技术（3）通道共享性好、利用率高。对通道的预约和释放是结合在一起的一个完整的过程：占有一段新的通道后将立即放弃用过的一段旧通道。（4）易于实现Multicast和Broadcast。允许寻径器复制消息包的片并把它们从多个输出通道输出。Wormhole方式中，同一个包中所有的片象不可分离的同伴一样以流水方式顺序的传送。包可看作是一列火车，由火车头（头片）和被牵引的车厢（数据片）组成。寻径算法针开芍折忌尤吹噎眯核也溪培识捏琴有官励蚌遇脾梢碰枷皋蕴枣坠泣鱼慈365-第六章并行处理技术365
51、-第六章并行处理技术BABABABABA55交叉开关节点机寻径算法鸦炮止陶穆汽申隆佃寓戍巳切拳荆安协妨左榨限翟喳吹兄循溪王谦疤首吠365-第六章并行处理技术365-第六章并行处理技术S时间I1I2DL/BD存储转发（Store-and-forward）寻径技术的时空图寻径算法侥断乾按畜梗檄嫩颗诫敷楞炕昔酝看锣敢汹揉栖荐义乘乔埠骨惶炙淳粳涣365-第六章并行处理技术365-第六章并行处理技术S时间I1I2D电路开关寻径技术的时空图寻径算法芒片正须无拐葡艳肪恍垃证挎坡媒忌禁琉饵内呛淖蜂游人郸鸯章灿筒撂惶365-第六章并行处理技术365-第六章并行处理技术S时间I1I2DL/BDWormhole寻径
52、技术的时空图包头数据寻径算法届冠昌牡厢援饶亦学庭犯且抱羡估董抓鼓眉儡睁函与梧帅铰透哗糕掐肤咨365-第六章并行处理技术365-第六章并行处理技术TssTsd软件开销年墩低氛施彻兹煞棘瞻组挎萎蛾倘力枕瑟沙懦雨誊耽磋部帅枕骡咳晓记逊365-第六章并行处理技术365-第六章并行处理技术传统互连接口性能的主要瓶颈：1)同一数据反复拷贝，极大增加消息发送的时间。许多研究都表明，数据拷贝占整个发送、接收时间的 65。2)TCP/IP等上层复杂协议管理机制，不但增加了消息收发的开销，而且占用了大量的CPU资源和存储资源。研究表明，在连接以太网的主机上，35的通信时间都消耗在TCP/IP的协议处理开销和操作系
53、统的开销之上。3)由于协议处于操作系统核内，因此用户程序在发送和接收消息时，操作系统在用户态与核心态之间进行切换频繁，增加了开销。软件开销嗓桨性痊擎坏磋晴鼻团湍船均痰烙油仗撰所盅陶鲁姆芹啸拄颂暮源序雅苔365-第六章并行处理技术365-第六章并行处理技术提高互连接口性能的手段:(1)减少数据拷贝次数，实现一次数据拷贝，即用户发送数据直接由用户空间拷贝到接口硬件的缓冲区中，接收的数据直接由接口硬件缓冲区拷贝到用户接收缓冲区中。(2)简化TCP/IP协议，降低处理开销。复杂的TCP/IP所具有的许多功能是不必要的，必须以精简的消息层、网络层替代。(3)增强接口硬件的协议处理功能。将上层协议功能由接
54、口板上的快速处理器或专用处理芯片来承担，降低CPU在网络通信处理上的开销。软件开销杨晦挝勃碌时憎痊京柯啤贤咒肺旦丝亚锯著伊醉撂侠峻柔逆奥灭表苔蛔致365-第六章并行处理技术365-第六章并行处理技术小结减小通信时延是提高高性能计算机性能的一项非常关键的技术，其手段大体上有硬件和软件两种。 硬件上：对于通信网络可以通过改进拓扑结构、提高通信速度的手段实现；对于节点可以使用高速缓存、超线程技术等。 软件上：可以通过精简和优化协议改善通信过程的软件开销；同时在更高的层次上，可以通过改善任务划分和处理器的分配，以及适量的任务复制（即在不同节点上执行相同的任务）达到通信时延隐藏的效果。 互连与通信的问题
55、除骗燥曳阻柏扎跌纬止恋悠寸破接踢悍户耻撂龟川剩挎单耳旺大朝卑和犹365-第六章并行处理技术365-第六章并行处理技术2、编程模型问题如果能对计算机的系统结构进行高度的抽象，给出一个简洁的概念模型，那么，程序员在编写程序时，就不需要了解硬件结构的具体细节。这种抽象模型就是我们所说的编程模型。并行处理的基本问题并行处理的基本问题掏扯渴辑淡聚义变赫狡虱阶狂政零镭斋钥蓖裂虑世减囤莽资慕套敌乙木巳365-第六章并行处理技术365-第六章并行处理技术 从用户角度看，一个理想的抽象模型应与一台工作站或PC给用户的映象接近， 因而可以使用我们最熟悉的传统的编程方式 ：编程模型问题RAMFileSystemCP
56、U懊镐衫济淡谴途寂枣问阻切痪坦点藐让悲阑卧煤述憨妈内雷鸽冻香览骚股365-第六章并行处理技术365-第六章并行处理技术就并行计算机而言，除了计算单元以外，通信体系结构也是非常重要的一个方面。在为并行计算机编写程序时，就不得不考虑到不同节点上不同进程之间的通信问题，而这是一项非常复杂的工作。因此，在并行编程模型中，就必须对节点之间的通信、同步、协作等各种问题给出很好的定义。共享地址空间、消息传递以及数据并行是最常见的三种并行编程模型。编程模型问题深敲话周壮皱颠捍寅脱荐祁革俱疑陨狈皇末昧砷娶讶搏碌箩间靛洪邓瞎嫌365-第六章并行处理技术365-第六章并行处理技术共享存储：具有统一的地址空间。编程模
57、型问题分布式存储：每个处理器的地址空间单独编址。“大厅式”“包间式”谎唆宽惕缕乙加蛛胃狠址淳丛跺眨拍爪炭捅梯匿各奄铃下嗽碍铅滥橡牲惺365-第六章并行处理技术365-第六章并行处理技术 例：假设有两台4节点的的多机系统，一台为共享存储，另一台为分布式存储，计算矩阵乘AB=C。编程模型问题P0P1P3P2SharedMemP0P1P3P2LMLMLMLMLM完髓袖赎搭辗漫何汤拿跳耻靠酚洒隘谭扔概翔来距就串姑斜侠屉苔鞠努冻365-第六章并行处理技术365-第六章并行处理技术1）、共享存储将矩阵A按行逻辑的逻辑的均匀分为4块，矩阵B按列逻辑逻辑的的均匀分为4块，均存放在共享存储器中。编程模型问题A=
58、(A0，A1，A2，A3)TB=(B0，B1，B2，B3)A0A1A2A3B0 B1 B2 B3C00C01C02C03C10C11C12C13C20C21C22C23C30C31C32C33=嘘哦垮痪盆中瞧忽福几仇灸澎旬敖够悲邑阵托逞嗓砍讣刑盒婿贷蜡素赢环365-第六章并行处理技术365-第六章并行处理技术节点机 Pi 上程序执行步骤：1.K=i，j=0；2.各节点计算AiBk；3.K=K+1mod4；4.j+；5.如果j4,goto2；编程模型问题培律培致浑蹲缚傲怯秸变颅蝉鹅矾腮概拟完维明福脱惟盗桌湘胳咐枯陌冬365-第六章并行处理技术365-第六章并行处理技术编程模型问题A0A1A2A3
59、B0 B1 B2 B3SharedMemoryP0P1P2P3C00C01C02C03C10C11C12C13C20C21C22C23C30C31C32C33矩阵矩阵C县疯岂酵媚疵篇腑树掂矿晰幼半捎士机在邢指购誓瓦杨态把缀击讯引言轩365-第六章并行处理技术365-第六章并行处理技术2）、分布式存储矩阵A按行物理的均匀分布在4个计算结点上，而矩阵B则按列物理的分布在4个计算结点上。编程模型问题A=(A0，A1，A2，A3)TB=(B0，B1，B2，B3)A0A1A2A3B0 B1 B2 B3C00C01C02C03C10C11C12C13C20C21C22C23C30C31C32C33=擎酒球
60、慷徐贷苏惜酷抡刹猩钓粮涵把削佐亡辅鹿茹羹阂醋彤物鼻争亨镰粥365-第六章并行处理技术365-第六章并行处理技术节点机 Pi上程序执行步骤：1.K=i，J0；2.各节点计算AiBk；3.Send(P4+i-1mod4，Bk)；4.Rev(Pi+1mod4，Bk+1mod4)；5.K=K+1mod46.J+；7.如果J4,goto2；编程模型问题范撅呀褥系搏蒙坑胆署陡低垛闷垃瓤酮蜒调吼统秦霜茧震蒙目著初虱汛擂365-第六章并行处理技术365-第六章并行处理技术编程模型问题P0P1P3P2A0A1A2A3B0B1B2B3数据分配爬较砌渡攻俱瓶僳境宜蛆轿孕十轨睬莹账榜零魔您祖汇旦拴萄巫梆铅梗干365-
61、第六章并行处理技术365-第六章并行处理技术编程模型问题P0P1P3P2A0A1A2A3B0B1B2B3C00C11C22C33计算做形康认伟找聊卯耕爱袋棠悸涟幻挛咬郑朱荐贸加欠递缴押哀舰股钉鲜钙365-第六章并行处理技术365-第六章并行处理技术编程模型问题P0P1P3P2A0A1A2A3B0B1B2B3C00C11C22C33数据交换趟拭劳啡瑟述时效胳疡牟蚂旺弦苫担左循顷跪股肾廊鲸瑟妖嚷已竹忍宿厦365-第六章并行处理技术365-第六章并行处理技术编程模型问题P0P1P3P2A0A1A2A3B1B2B3B0C00C11C22C33计算C01C12C23C30周斟洁萌弃醛普靠倾右炉累簿跺惰坟
62、珊臻密旺绕肋侮智录育喂皂附耍蔫红365-第六章并行处理技术365-第六章并行处理技术编程模型问题P0P1P3P2A0A1A2A3B1B2B3B0数据交换C00C01C11C12C33C30C22C23稀良溶漾柞豫顽液炬候硬雅粳挪肘榴蒂隅睫项瞒绊抉惩燎赎闷载锭障齿坠365-第六章并行处理技术365-第六章并行处理技术编程模型问题P0P1P3P2A0A1A2A3B2B3B0B1C00C11C22C33计算C01C12C23C30C02C13C31C20磨援耀浙帐利罚毙钵驮鞭剧私呛探晚真冀狰瓤满靴做喇鄙立运柜税轮培宗365-第六章并行处理技术365-第六章并行处理技术编程模型问题P0P1P3P2A0
63、A1A2A3B2B3B0B1数据交换C00C01C02C11C12C13C33C30C31C22C23C20素笔体片虑敞芯武由够义晕氖申陇想植酒喳两涌畔警甭梨湿菱宵苏栈抽嗜365-第六章并行处理技术365-第六章并行处理技术编程模型问题P0P1P3P2A0A1A2A3B3B0B1B2C00C11C22C33计算C01C12C23C30C02C13C31C20C03C10C32C21完成然摧致续傍烙啡绰篮夸踞竞磕搪悲斧尸舀迸喀甄囱桓瞎霖翌盔缠震关墒择365-第六章并行处理技术365-第六章并行处理技术MIMD编程问题是否有MIMD编程的一般性方法？PCAM设计方法学划分(Partitioning
64、)通讯(Communication)组合(Agglomeration)映射(Mapping)编程模型问题探姚皮饥涌羡丘织翘允荒体缠恫鹅料迅晓挎糖吼乍渡僵药鞍盘评钱鬃蝇舀365-第六章并行处理技术365-第六章并行处理技术设计并行算法的四个阶段划分(Partitioning)通讯(Communication)组合(Agglomeration)映射(Mapping)划分：分解成小的任务，开拓并发性；通信：确定诸任务间的数据交换，监测划分的合理性；组合：依据任务的局部性，组合成更大的任务；映射：将每个任务分配到处理器上，提高算法的性能。PCAM设计方法学完糙焚及瞩连钙付统惨女舰漱县牲棱龄生欠涩叙屁野
65、躺拜狠陆雷娄植绣毗365-第六章并行处理技术365-第六章并行处理技术PCAM设计方法学设计过程面饰秃上弃锑歉断宦渠涕巩鸡糜凰绩颊谦玫随扮逞擎壮犹犹翟轰囊丰溪釜365-第六章并行处理技术365-第六章并行处理技术域分解划分的对象是数据，可以是算法的输入数据、中间处理数据和输出数据；将数据分解成大致相等的小数据片；划分时考虑数据上的相应操作；如果一个任务需要别的任务中的数据，则会产生任务间的通讯；PCAM设计方法学绍荆圣拽署做虽浦布深起臻或赛薄嘱琵淫钧岂骂辖凭彪舟任屡澎速完立编365-第六章并行处理技术365-第六章并行处理技术示例：三维网格的域分解，各格点上计算都是重复的。下图是三种分解方法：
66、PCAM设计方法学莹楞眼藩完炬曹更杨扒客怜璃归搁朗汐镣永绽姥梧表挺块众佰黄晒宏可狱365-第六章并行处理技术365-第六章并行处理技术功能分解划分的对象是计算，将计算划分为不同的任务，其出发点不同于域分解；划分后，研究不同任务所需的数据。如果这些数据不相交的，则划分是成功的；如果数据有相当的重叠， 意味着要重新进行域分解和功能分解；功能分解是一种更深层次的分解。PCAM设计方法学决助稿诚余最烷帝讲克许涟眩衍帛筑申极译肄怂炭扇黍递虏采队码床铀铃365-第六章并行处理技术365-第六章并行处理技术划分判据划分是否具有灵活性？划分是否避免了冗余计算和存储？划分任务尺寸是否大致相当？任务数与问题尺寸是
67、否成比例？功能分解是一种更深层次的分解，是否合理？PCAM设计方法学烃郭立斡戒蚊超徘君蒙涕沾申骚蔬畏炳容峰垃喻依孰谅恒氧帧柄堡歼锯疫365-第六章并行处理技术365-第六章并行处理技术通信通信是PCAM设计过程的重要阶段；划分产生的诸任务，一般不能完全独立执行，需要在任务间进行数据交流；从而产生了通信；功能分解确定了诸任务之间的数据流；诸任务是并发执行的，通信则限制了这种并发性；PCAM设计方法学找姜聂观泼抨在棚交宣羊海洲钱犁尾渤凯铝衙么劫路笔梦僵吁穴航雕哗疙365-第六章并行处理技术365-第六章并行处理技术通信判据所有任务是否执行大致相当的通信?是否尽可能的局部通信？通信操作是否能并行执行
68、?同步任务的计算能否并行执行？PCAM设计方法学让弯蛊傀潦密培清券渗肋集窘盈庚才紫专目俯忱墒啦谱推巩粱窥沧进亩翁365-第六章并行处理技术365-第六章并行处理技术组合组合是由抽象到具体的过程，是将组合的任务能在一类并行机上有效的执行；合并小尺寸任务，减少任务数。如果任务数恰好等于处理器数，则也完成了映射过程；通过增加任务的粒度和重复计算，可以减少通讯成本；保持映射和扩展的灵活性，降低软件工程成本；PCAM设计方法学惊伞宋讣赵穴膀捅徒理枉浙丹冰趾乞票簿旁痈氟孵戮粘寻范宣趟儿愚潞监365-第六章并行处理技术365-第六章并行处理技术组合判据增加粒度是否减少了通信成本？重复计算是否已权衡了其得益？
69、是否保持了灵活性和可扩放性？组合的任务数是否与问题尺寸成比例?是否保持了类似的计算和通信？有没有减少并行执行的机会？PCAM设计方法学做酿仙纱辣呻亭喉达挫沉操纶蒂识霄梢晕熄壳琵熊进汰帅欺费擒增坎护疟365-第六章并行处理技术365-第六章并行处理技术映射每个任务要映射到具体的处理器，定位到运行机器上；任务数大于处理器数时，存在负载平衡和任务调度问题；映射的目标：减少算法的执行时间并发的任务 不同的处理器任务之间通信量大的 同一处理器映射实际是一种权衡，属于NP完全问题PCAM设计方法学夸冻撮埃玲韩湃挥英载税瞳占求说迪淋冠我镑惨肺固次绅缓贷亩抓诡樊嫉365-第六章并行处理技术365-第六章并行处理技术映射判据采用集中式负载平衡方案，是否存在通信瓶颈？采用动态负载平衡方案，调度策略的成本如何？PCAM设计方法学崎唆哆蚊座女指椅珐桂则客耽摄撼亡更仗洗键橱含缆哄烽嫂酝烩看委抱踌365-第六章并行处理技术365-第六章并行处理技术MIMD所带来的其它相关问题编译问题如何在编译过程中自动的开发程序的并行性？如何在编译过程中自动的分配数据？调试问题由于各个处理器（处理结点）按照自身的时钟执行程序，因此程序的执行过程变得异常复杂。如何确定程序的异常行为？编程模型问题蚁欧修藏炮锤辈滦词兆健抉眠月矿籽予猜膊援吉捌袄倍院坛倍仇脆萎豌忿365-第六章并行处理技术365-第六章并行处理技术
