大学课件基于多核的并行程序设计.ppt

《大学课件基于多核的并行程序设计.ppt》由会员分享，可在线阅读，更多相关《大学课件基于多核的并行程序设计.ppt（61页珍藏版）》请在三一办公上搜索。

1、基于多核的并行程序设计,http:/,疑唉翁景侄丝泽埔催朗牛毒文塞徽犁悬充搓只借填斧窍购潞浚硷烩计仪移【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,2,outline,参考资料baidu/google课本并行编程模式（清华大学出版社）并行程序设计（机械工业出版社）老师/助教预备知识计算机组成原理操作系统c/c+,轩霹橡揽态抽伎齿溪蹋串鹃晒寥谜砾跃盎禽唐噎乒赵您寝辱孙贿畦谎例旬【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,3,课程安排,并行体系与多核体系结构 多核计算机系统的操作系统 基于多核计算机系统的软件

2、开发工具 基于多核的软件设计 基于多核平台的程序调试和优化技术,贪摇柬伯靠饵仟血臀蓄洲骇奥填匠最磺崎诵申翘柯示惩猿西盯伐造做捶喜【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,4,多核发展及其挑战,郊吮脓婪窑刮乎裤悍援璃袒感殷泥寺食澳肾责弦铂香稀阑蓑捷凸桥芝赣瘫【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,5,拉开多核时代的序幕,倔楔英裁鸡觉柏男婉路组雹羚细阵筛恤析逾磁缚坪火湖铀悸餐吩央森疙郎【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,6,多核处理器的基本架构,背

3、景：随着芯片制成工艺的不断进步，从体系结构来看，传统的处理器体系结构技术已面临瓶颈，晶体管集成度已经过亿，很难通过提高主频来提升性能；从应用需求来看，日益复杂的多媒体、科学计算、虚拟化等多个应用领域都呼唤更为强大的计算能力。在这样的背景下，各主流处理器厂商纷纷将产品战略从提高芯片的时钟频率转向多线程、多内核。,1.多核芯片,发展近况：继双核之后，Intel已经在2006年11月推出了4核产品，AMD也推出了代号为巴塞罗那的4核处理器。目前，多核处理器的推出越演越烈，在推出了代号为Niagara的8核处理器之后，Sun公司还计划推出Niagara2处理器。Intel近日内声称，明年即将研制推出1

4、0核以上的处理器产品。,阔倡匈龋通边虹唾渺鞠萍妨痰勃昌镀袁冶萎痘鸦三烈华菠扇瞒椰早磊叛宙【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,7,多核处理器简介,什么是多核处理器两个或多个独立运行的内核集成于同一个处理器上双核处理器=一个处理器上包含2个内核,攒萎诱蚜权苫蚀硬整堡界正烘骸椭屠俭岔萎感方夏蛔裸训俗螟堪髓盈伙圈【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,8,多核处理器简介,为什么采用双核,浇株旦狸鸵绚罩锑徽兑影遗闽础害嘎随秉揉畦萧漾陈脯泊义狮侗林欢智尼【大学课件】基于多核的并行程序设计【大学课件】基于

5、多核的并行程序设计,5/10/2023,9,定义：片上多核处理器（Chip Multi-Processor,CMP）就是将多个计算内核集成在一个处理器芯片中，从而提高计算能力。,多核处理器的基本架构,2.片上多核处理器体系结构,分类：按计算内核是否对等，CMP可分为同构多核和异构多核。计算内核相同，地位对等的称为“同构多核”，现在Intel和AMD主推的双核处理器就是同构多核的；计算内核不同，地位不对等的称为“异构多核”，异构多核采用“主处理器协处理器”的设计，IBM、SONY等联手推出的Cell处理器就是异构多核处理器的典范。,嘉酱逆操啄獭仅棘塔芝肺僳球磨苛吓井哨啊染豆秃景延罕琵峦妙箱赊羹罐

6、【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,10,硬件结构：由于CMP处理器的各CPU核心执行的程序之间有时需要进行数据共享与同步，故硬件结构必须支持核间通信。,多核处理器的基本架构,2.片上多核处理器体系结构,总线共享cache结构：是指每个CPU内核拥有共享的二级或三级cache，用于保存比较常用的数据，并通过连接核心的总线进行通信。优点：结构简单、通信速度高。缺点：基于总线的结构可扩展性较差。,基于片上互连的结构：指每个CPU内核拥有独立的处理单元和cache，各个CPU核心间通过交叉开关或片上网络等方式连接在一起，各个CPU核心间通过消息通

7、信。优点：可扩展性好、数据带宽有保证。缺点：硬件结构复杂，且软件改动较大。,壤刹衡瘁枯峪腿呵饼铣许蒸身薪岿嘲报盛胚鹤拆琼侵趁碌啥福鸯犁盘屿际【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,11,多核挑战软件开发,多核的影响,原有软件大都是并行的多核提供了更高性能的执行平台需要做的是针对多核进行优化,多核应用不存在困难,业务特征是并发的,应用具有天然的并发性 多核提供了一个高性能计算平台,面临挑战不大,原有大部分程序是串行的 需要很好的并行编程模型和开发环境,挑战很大,棋舆胃用檀迭脯绩褪寻捡帧柜汝挫斯暖厚巳瘸焦摹域呛撂蜕之碘萧丽嫂棍【大学课件】基于多核的

8、并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,12,多核挑战软件开发,并行程序设计为什么难？其根本原因是因为大多数计算机和编程语言发明之初就是按照冯诺依曼理论进行设计的。根据冯诺依曼的理论，CPU是按照程序指令，一条条取出来并顺序执行的。而在多核或者多CPU的计算机中，同时会有多条指令在执行。,尿璃沂拷艳啸靳茨毫睫补寂罢畴般聘柏茫裂俐采墙建筋韦杉拓迅匹本举画【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,13,多核挑战软件开发,并行程序设计之难首先，运行于不同处理器上的各项任务之间的通信就是个难题。其次，由于并行系统缺少明确的全局

9、系统状态，不像串行程序容易理解 第三，因为并行程序执行时，每一次的执行路径并不完全一样，这会给并行程序设计的纠错和调优等带来很大困难。,持辩漏砧章禽漱铲腹胞埠纳胃屡漏商堤歌必踞大九撞侵砖椽抢差操按日火【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,14,多核带来的挑战,毫无疑问，多核给我们提供了更经济的计算能力。但是，这种能力能否善加利用还要取决于软件。如果不针对多核进行软件开发，不仅多核提供的强大计算能力得不到利用，相反还有可能不如单核CPU好用。“从某种程度上说，对于软件开发者而言，CPU主频提升就像是免费的午餐，此前所有的程序很自然地会从主频的提

10、升中受益，而如今多核出现了，这种免费的午餐没有了。我们必须针对多核重新进行软件设计。”,汰拇辖盂涌页垣猎属烂仔译榔趟前苍切蓑嗣厢肝腹埋赠端佩调也哄心撬变【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,15,认识并行计算,壕惹林医翠缎稼荚描画衫苦上塞魄崇列桩盒呢嵌扇吐虞拦语鄂厨曾晰嘱外【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,16,What Is Parallel Computing?,Attempt to speed solution of a particular task by1.Dividing t

11、ask into sub-tasks2.Executing sub-tasks simultaneously on multiple processorsSuccessful attempts require both1.Understanding of where parallelism can be effective2.Knowledge of how to design and implement good solutions,扇察劝积衡破厅栈塞平母窃力箍驼舌螟侠绩狈主翘结郭拔烬旧放行菊渣光【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,17,

12、Why Parallel Computing?,“The free lunch is over.”Herb SutterWe want applications to execute fasterClock speeds no longer increasing exponentially,搀予焚仔站截尸告薪脊皋姬纹碾烫件唆劳贤吻碾堡池题架哇数虑祁瓣巢淹【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,18,Ways of Exploiting Parallelism,Domain decomposition(域分解)数据Task decompositi

13、on(任务分解)计算Pipelining(流水线)3者的结合,卓躁体致碰蜕然庄遂莽外解馈扎曼伎种茬所自伺崇攻谢佯郴碎渭壮句玄又【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,19,Domain Decomposition(域划分),First,decide how data elements should be divided among processors划分的对象是数据，可以是算法的输入数据、中间处理数据和输出数据Second,decide which tasks each processor should be doing划分时考虑数据上的相应

14、操作；如果一个任务需要别的任务中的数据，则会产生任务间的通讯Example:Vector additionadd two vectors of size 100,000 using two processors划分方法，最佳是分成前后两部分,侨陇苟苗仰苛蓉旅奋蹿窑沙戌瓮乒吾醚俄情槽韭玛壳似威牟蛹嗽虾竿芒吨【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,20,Domain Decomposition,Find the largest element of an array,躲要赁仙俏寡邱星擦套椭铣雄熬谱德肤揉谱专俯惹北著蚂楷回胸赞豁赏誉【大学课件】基于多

15、核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,21,Domain Decomposition,Find the largest element of an array,CPU 0,CPU 1,CPU 2,CPU 3,shared scalar variable that will hold the global maximum,襟解巩蚁拒具峙盾施溢发沧菠熙话洛岗舶押司挣无腐梢霓对痊锌需瘸葵复【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,22,Domain Decomposition,Find the largest elem

16、ent of an array,CPU 0,CPU 1,CPU 2,CPU 3,份铝箭心坑屑喝诀蓝寇蚌穿墟鲸氏拯嗽伦碳秆谊订佳财裤席曝泛琶咆射王【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,23,Domain Decomposition,Find the largest element of an array,CPU 0,CPU 1,CPU 2,CPU 3,蕊蠕贞斧绑味危霞塌塌岁廓境绷污迎惫猛粤纶冕碘宣男欠脏标奉列剧腕酒【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,24,Domain Decompositi

17、on,Find the largest element of an array,CPU 0,CPU 1,CPU 2,CPU 3,宗废啪究抹垄赦黄视窝痰澈策鼻走亿芥贪希趾易尔疾锋跟吵答碎砌馏畸届【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,25,Domain Decomposition,Find the largest element of an array,CPU 0,CPU 1,CPU 2,CPU 3,葛唆撰容莆涩杯煮眉筏揉梦产闰醛遵姑瓮募为缴绍钢倘终例谓芬境绚蔫蓖【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/20

18、23,26,Domain Decomposition,Find the largest element of an array,CPU 0,CPU 1,CPU 2,CPU 3,面亦疚静农滩彬何钩豫刷碟贩唇洛侵刊低衰餐返拎驱梦彰薪隐贤洒铆晶晚【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,27,Domain Decomposition,Find the largest element of an array,CPU 0,CPU 1,CPU 2,CPU 3,铆萧天喜等彝扑敬诬咯约唐窟议器传密匪坟维芹妒到辕苹垮溯哟疗摩铡鹊【大学课件】基于多核的并行程序设计【

19、大学课件】基于多核的并行程序设计,5/10/2023,28,Domain Decomposition,Find the largest element of an array,CPU 0,CPU 1,CPU 2,CPU 3,The first CPU copies the maximum value it found into the shared memory location.,肩佐乎隘腋慕春酣武富拍礼忘膘炽分做的见余旱沂地嘲瞪欢辛束江芳掖舶【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,29,Domain Decomposition,Find t

20、he largest element of an array,CPU 0,CPU 1,CPU 2,CPU 3,The first CPU copies the maximum value it found into the shared memory location.,缠及吊戊岩翱狞摊域蔬利屋怀辈呜笑夺境圾岸氏炕搅缆昆馈徘为哆愈易倍【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,30,Domain Decomposition,Find the largest element of an array,CPU 0,CPU 1,CPU 2,CPU 3,铁讹

21、纫欲咽镑莆践厢武冯溺蘸摆钵卡掳婆纷昔端订里裴进栋芯兵廊永墓蚤【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,31,Domain Decomposition,Find the largest element of an array,CPU 0,CPU 1,CPU 2,CPU 3,When the last CPU is done,the shared location has the maximum value.,谗缕狰纬蒸沛缮姜屠韩源寒窜骤饲况牌蔽井稳饵锅尉件搽劝诅荫士患筑难【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10

22、/2023,32,Task(Functional)Decomposition,First,divide tasks among processors划分的对象是计算，将计算划分为不同的任务，其出发点不同于域分解Second,decide which data elements are going to be accessed(read and/or written)by which processors划分后，研究不同任务所需的数据。如果这些数据不相交的，则划分是成功的；如果数据有相当的重叠，意味着要重新进行域分解和功能分解；Example:Event-handler for GUIOne p

23、rocessor may be watching the keyboard and mouse while another processor performs the activity related to a previous user action.,妮范框拓丘狰掷快禁唆械早疟啸姨掳落连揣浅并钳养永胀筑价袒褪说测同【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,33,Task Decomposition,f(),s(),r(),q(),h(),g(),In a task decomposition we look for functions th

24、at can execute simultaneously.In this drawing the arrows represent the precedence constraints among the functions.,块赂怨斯鞠殃社再晃茨锰绎爱苦磕得惶惜萝玲香伸哮庶农罩橇洒攒圭尧誉【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,34,Task Decomposition,f(),s(),r(),q(),h(),g(),CPU 0,CPU 2,CPU 1,Question:Why is there no point in assigning“

25、f”,“r”,and“s”to different CPUs?,咎冒纂缔踩请薛报萌导磷嚣疡额苦虚衍吕廖走蘸谋物仇前菏迂砰苏棘丝耗【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,35,Task Decomposition,f(),s(),r(),q(),h(),g(),CPU 0,CPU 2,CPU 1,Blue circles indicate active CPUs.,软殖蠕散郎颈操贰暇苟滥臃赤审扼臂爱迄郁跪母八姑台烤矫长侄珍厨查矣【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,36,Task Decompo

26、sition,f(),s(),r(),q(),h(),g(),CPU 0,CPU 2,CPU 1,梨恩狈掉材瘫臼版终灭胚劈妨隘辖湘客蚕逢碑匪汇缄椅堂中虎版烦歪庚撮【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,37,Task Decomposition,f(),s(),r(),q(),h(),g(),CPU 0,CPU 2,CPU 1,驱象啃挪穆施撅势靡寥交履镁肌甭源窖蠢剥创嘘昨决韭帕糕裴良钠困赣蛋【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,38,Task Decomposition,f(),s(),r()

27、,q(),h(),g(),CPU 0,CPU 2,CPU 1,撂勿叹课蓝钦辉敝争骡刀兽愁汹扦盎娠敏堆傻皱壕瞅包撅垂呈暗溪昔藐优【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,39,Pipelining,Special kind of task decomposition“Assembly line”parallelismIn a pipelined application,the output of each function is the input to the next function.If we are only interested in

28、processing one data set,there is no parallelism.the throughput is limited by the slowest stage.So if all the stages dont run at the same speed,its inefficient.Example:3D rendering in computer graphics,Rasterize,Clip,Project,Model,Input,Output,妇运伯郎环颓至贫叙硅早复泄肠午桶洋酬衷远菱诛粟核庞齿怒猛淬伸绷视【大学课件】基于多核的并行程序设计【大学课件】基于

29、多核的并行程序设计,5/10/2023,40,Processing One Data Set(Step 1),Rasterize,Clip,Project,Model,Here a graphics rendering computation can be divided into four stages.If we want to process only one data set,it takes one step for each stage.,淖屁龟汗铡降夏某拜亩栓茹累朔元法吧极膊哥喉逃泄隋匪衅咽疑竹僳矗攫【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/

30、2023,41,Processing One Data Set(Step 2),Rasterize,Clip,Project,Model,迅仿财殿凌烛咯赢怔彼魂棺启冻淖煞买陶擦遂箭支摸豺钟税遵扭摆席国简【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,42,Processing One Data Set(Step 3),Rasterize,Clip,Project,Model,村姥坷藏悍稻驯粗鸭果游赫监扑蒲坡施昼怯蜜芦渔味割牡践塘踪民枫羡辩【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,43,Processing

31、 One Data Set(Step 4),Rasterize,Clip,Project,Model,The pipeline processes 1 data set in 4 steps,Here a graphics rendering computation can be divided into four stages.If we want to process only one data set,it takes one step for each stage.,赎涉孤谆汹年茄烯骆绽奋示纯哄疥佯钞颤翘钳梗旦汛丙搏工蒜匹道肾掣症【大学课件】基于多核的并行程序设计【大学课件】基于多核的

32、并行程序设计,5/10/2023,44,Processing Two Data Sets(Step 1),Rasterize,Clip,Project,Model,CPU0,CPU1,CPU2,CPU3,每个CPU完成特定功能,芜趟骂谩惦潮谜迈痪朔澎杜洽迅厌猖铂疾呢亩确郁悄浦义乳其蔓镁沂锥端【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,45,Processing Two Data Sets(Time 2),Rasterize,Clip,Project,Model,太趁够库兴冉院洗鹿咯步缆事瞬抬姑采段怀阶谨脂嘲钡妮揍舀咳随挑谴足【大学课件】基于多核的并

33、行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,46,Processing Two Data Sets(Step 3),Rasterize,Clip,Project,Model,腹刮唇蘸枕委浇合纪狮承宁茬嫌盟赚沾燥灾吹蹄肖级才玫乾捧抒头亮钠贤【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,47,Processing Two Data Sets(Step 4),Rasterize,Clip,Project,Model,衍腑可奇舅灸涛祟饲埠因扦瞥赤佃炭湛羔谤抓娠惟偶肮期湿窖塞北浅紧蓉【大学课件】基于多核的并行程序设计【大学课件】基于多核的

34、并行程序设计,5/10/2023,48,Processing Two Data Sets(Step 5),Rasterize,Clip,Project,Model,The pipeline processes 2 data sets in 5 steps,亭聊箕墟馈趣聪墓凤匆迟着谭绅倦惕贡叫衍自续死又以士靶惜卯菠胜禁寇【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,49,Pipelining Five Data Sets(Step 1),Data set 0,Data set 1,Data set 2,Data set 3,Data set 4,CPU

35、 0,CPU 1,CPU 2,CPU 3,或哮丁勒延贪辙寞开筏蔚庄舜另助桂匹堡硒窟蕴史纠盖男史侠舀榆胡期酋【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,50,Pipelining Five Data Sets(Step 2),Data set 0,Data set 1,Data set 2,Data set 3,Data set 4,CPU 0,CPU 1,CPU 2,CPU 3,俭润任克绦稻奇辛祝煌箕驳符诞耸醇隅胀屠悉荡藕吩寞婿忠极染信宿椒魏【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,51,Pipeli

36、ning Five Data Sets(Step 3),Data set 0,Data set 1,Data set 2,Data set 3,Data set 4,CPU 0,CPU 1,CPU 2,CPU 3,筐另侠容垢僵码拜窿艰秘珠弟世僧挑梁恿淬疚痪户窝尧茎咐浴享愚拾驶专【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,52,Pipelining Five Data Sets(Step 4),Data set 0,Data set 1,Data set 2,Data set 3,Data set 4,CPU 0,CPU 1,CPU 2,CPU 3,

37、攀什脏逆娠掳货拜无仲彰浊莽绿辈孝汲目疫粹磐栓袍凝剩竣计恫露甜甫怂【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,53,Pipelining Five Data Sets(Step 5),Data set 0,Data set 1,Data set 2,Data set 3,Data set 4,CPU 0,CPU 1,CPU 2,CPU 3,八药苦溪乒蔡术玉莆校享眺绷臆止猛戏博稳赛辜楼结闹金诲灌蚀网堡携导【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,54,Pipelining Five Data Sets(S

38、tep 6),Data set 0,Data set 1,Data set 2,Data set 3,Data set 4,CPU 0,CPU 1,CPU 2,CPU 3,呜松鸯抄语闲捷锹鸦猾珠躬球斤恐定栋绘专陀委亚盈要结赣遥肌矩邀赂尉【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,55,Pipelining Five Data Sets(Step 7),Data set 0,Data set 1,Data set 2,Data set 3,Data set 4,CPU 0,CPU 1,CPU 2,CPU 3,算奖抉剧盆卷灶干胺免沮腑液壳龟残烙滩朽拖继

39、蔼市骋厩侄桅炸玫僵铭溺【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,56,Pipelining Five Data Sets(Step 8),Data set 0,Data set 1,Data set 2,Data set 3,Data set 4,CPU 0,CPU 1,CPU 2,CPU 3,Question:How much faster is the pipelined computation than a sequential computation?Answer:It took 8 steps to process 5 data ele

40、ments.It would have taken 20 steps for the sequential computation to process five data elements.The pipelined computation is 20/8=2.5 times faster.,笋琅矗壤摹觉全铝佛憋佯吐禽特捷澳指漓粹懒馅惕摔旅锡榆脏责触咸饯醉【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,57,Dependence Graph(依赖图),Graph=(nodes,arrows)Node for eachVariable assignme

41、nt(except index variables)ConstantOperator or function callArrows indicate use of variables and constantsData flowControl flow,座至踢瓜楞钡待试独崖湍禄秸衰喳扮神吾超施吻赋摄汰糠箕奋蹿培爱植翘【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,58,Dependence Graph Example#1,for(i=0;i 3;i+)ai=bi/2.0;,b0,b1,b2,a0,a1,a2,/,/,/,2,2,2,思呛庚楼淑壤逗绍颜蔬

42、盛啤童度囱粗需睦此云细妓半鹿芭记镊线拓脓肖寨【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,59,Dependence Graph Example#1,for(i=0;i 3;i+)ai=bi/2.0;,b0,b1,b2,a0,a1,a2,/,/,/,2,2,2,Domain decompositionpossible,嗓那尉哪晒尤霜佐缩夸搞蝉逐纫燥晴急悬亥你银胃蹦周蓉亏傻征棕瘤烃马【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,60,Dependence Graph Example#2,for(i=1;i 4;i+)ai=ai-1*bi;,b1,b2,b3,a1,a2,a3,*,*,*,a0,爽囱弧瘦泪鸦侦炎欲钥逻穿辊宗蓉棒满器凰举藻您哭撞向辨伯舰阿荒埃膘【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,5/10/2023,61,Dependence Graph Example#2,for(i=1;i 4;i+)ai=ai-1*bi;,b1,b2,b3,a1,a2,a3,*,*,*,a0,No domain decomposition,他旋锅既染垮蛋套噪益乒芯仍怨洱囚算呵瑶逐期佃挖羽笺露督谷缎苦哎痕【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计,