《大学课件基于多核的并行程序设计》由会员分享,可在线阅读,更多相关《大学课件基于多核的并行程序设计(61页珍藏版)》请在金锄头文库上搜索。
1、基于多核的并行程序设计基于多核的并行程序设计http:/ l多核计算机系统的操作系统 l基于多核计算机系统的软件开发工具 l基于多核的软件设计 l基于多核平台的程序调试和优化技术 贪摇柬伯靠饵仟血臀蓄洲骇奥填匠最磺崎诵申翘柯示惩猿西盯伐造做捶喜【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/20244多核发展及其挑战多核发展及其挑战郊吮脓婪窑刮乎裤悍援璃袒感殷泥寺食澳肾责弦铂香稀阑蓑捷凸桥芝赣瘫【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/20245拉开多核时代的序幕在在CPU快速发展的快速发展的20年里年里, CPU一次次地遭遇性
2、能极限,但都又一次次地冲破一次次地遭遇性能极限,但都又一次次地冲破了这个极限了这个极限.从奔腾到奔腾从奔腾到奔腾2,CPU也突破了也突破了1GHZ,从奔腾,从奔腾2到奔腾到奔腾3,CPU从从1GHZ突破了突破了2GHZ,从奔腾,从奔腾3到奔腾到奔腾4,CPU也终于突破了也终于突破了3GHZ,现在最高的,现在最高的CPU主频已经高达主频已经高达3.8GHZ 单核单核CPU的极限突破的极限突破单核单核CPU好象停止了前进,到好象停止了前进,到3.8G却怎么也超不过却怎么也超不过4G单核单核CPU遭遇终极瓶颈遭遇终极瓶颈英特尔不得不承认奔腾系列已经遭遇最终的主频极限,英特尔不得不承认奔腾系列已经遭遇
3、最终的主频极限,4G就象一场百年罕见地就象一场百年罕见地强降雪,将奔腾系列强降雪,将奔腾系列CPU的性能高速公路永远地封死了。因此,以英特尔为首的性能高速公路永远地封死了。因此,以英特尔为首的的CPU军团不得不另外找一条更宽的性能高速公路来继续他们的军团不得不另外找一条更宽的性能高速公路来继续他们的CPU神话神话 另寻出路另寻出路倔楔英裁鸡觉柏男婉路组雹羚细阵筛恤析逾磁缚坪火湖铀悸餐吩央森疙郎【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/20246多核处理器的基本架构l背景背景:随着芯片制成工艺的不断进步,从体系结构来看,传统的处理器体系结构技术已面临瓶颈,晶体
4、管集成度已经过亿,很难通过提高主频来提升性能;从应用需求来看,日益复杂的多媒体、科学计算、虚拟化等多个应用领域都呼唤更为强大的计算能力。在这样的背景下,各主流处理器厂商纷纷将产品战略从提高芯片的时钟频率转向多线程、多内核。1.1.多核芯片多核芯片l发展近况发展近况:继双核之后,Intel已经在2006年11月推出了4核产品,AMD也推出了代号为巴塞罗那的4核处理器。目前,多核处理器的推出越演越烈,在推出了代号为Niagara的8核处理器之后,Sun公司还计划推出Niagara2处理器。 Intel近日内声称,明年即将研制推出10核以上的处理器产品。阔倡匈龋通边虹唾渺鞠萍妨痰勃昌镀袁冶萎痘鸦三烈
5、华菠扇瞒椰早磊叛宙【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/20247Front Side BusFront Side Bus多核处理器简介多核处理器简介l什么是多核处理器l两个或多个独立运行的内核集成于同一个处理器上l双核处理器 =一个处理器上包含2个内核Core0Core0Core1Core1攒萎诱蚜权苫蚀硬整堡界正烘骸椭屠俭岔萎感方夏蛔裸训俗螟堪髓盈伙圈【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/20248多核处理器简介多核处理器简介l为什么采用双核双核共享封装和双核共享封装和I/O时时,总成本下降总成本下降封装和测试
6、占总成封装和测试占总成本的本的20%-50%, I/O通常占晶片面积的通常占晶片面积的15-20%功耗功耗成本成本性能性能单核多核主频超过主频超过2GHz时功耗超过时功耗超过100W仅靠主频驱动仅靠主频驱动平衡性能与功耗平衡性能与功耗由主频和每时钟周由主频和每时钟周期所执行的指令数期所执行的指令数来实现来实现浇株旦狸鸵绚罩锑徽兑影遗闽础害嘎随秉揉畦萧漾陈脯泊义狮侗林欢智尼【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/20249l定义:定义:片上多核处理器(Chip Multi-Processor,CMP)就是将多个计算内核集成在一个处理器芯片中,从而提高计算能力
7、。多核处理器的基本架构多核处理器的基本架构2.2.片上多核处理器体系结构片上多核处理器体系结构l分类:分类:按计算内核是否对等,CMP可分为同构多核和异构多核。计算内核相同,地位对等计算内核相同,地位对等的称为“同构多核”,现在Intel和AMD主推的双核处理器就是同构多核的;计算内核不同,地位计算内核不同,地位不对等不对等的称为“异构多核”,异构多核采用“主处理器协处理器”的设计,IBM、SONY等联手推出的Cell处理器就是异构多核处理器的典范。嘉酱逆操啄獭仅棘塔芝肺僳球磨苛吓井哨啊染豆秃景延罕琵峦妙箱赊羹罐【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/20
8、2410l硬件结构:硬件结构:由于CMP处理器的各CPU核心执行的程序之间有时需要进行数据共享与同步,故硬件结构必须支持核间通信。多核处理器的基本架构多核处理器的基本架构2.2.片上多核处理器体系结构片上多核处理器体系结构l总线共享总线共享cache结构:结构:是指每个CPU内核拥有共享的二级或三级cache,用于保存比较常用的数据,并通过连接核心的总线进行通信。优点:结构简单、通信速度高。缺点:基于总线的结构可扩展性较差。l基于片上互连的结构:基于片上互连的结构:指每个CPU内核拥有独立的处理单元和cache,各个CPU核心间通过交叉开关或片上网络等方式连接在一起,各个CPU核心间通过消息通
9、信。优点:可扩展性好、数据带宽有保证。缺点:硬件结构复杂,且软件改动较大。壤刹衡瘁枯峪腿呵饼铣许蒸身薪岿嘲报盛胚鹤拆琼侵趁碌啥福鸯犁盘屿际【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202411多核挑战软件开发多核挑战软件开发l多核的影响 传统的科学计算传统的科学计算 原有软件大都是并行的原有软件大都是并行的多核提供了更高性能的执行平台多核提供了更高性能的执行平台需要做的是针对多核进行优化需要做的是针对多核进行优化,多核应用不存在困难多核应用不存在困难服务器软件服务器软件 业务特征是并发的业务特征是并发的,应用具有天然的并发性应用具有天然的并发性 多核提供了一
10、个高性能计算平台多核提供了一个高性能计算平台, 面临挑战不大面临挑战不大 原有大部分程序是串行的原有大部分程序是串行的 需要很好的并行编程模型和开发环境需要很好的并行编程模型和开发环境,挑战很大挑战很大 桌面软件桌面软件棋舆胃用檀迭脯绩褪寻捡帧柜汝挫斯暖厚巳瘸焦摹域呛撂蜕之碘萧丽嫂棍【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202412多核挑战软件开发多核挑战软件开发l并行程序设计为什么难?l其根本原因是因为大多数计算机和编程语言发明之初就是按照冯诺依曼理论进行设计的。根据冯诺依曼的理论,CPU是按照程序指令,一条条取出来并顺序执行的。而在多核或者多CPU的
11、计算机中,同时会有多条指令在执行。 尿璃沂拷艳啸靳茨毫睫补寂罢畴般聘柏茫裂俐采墙建筋韦杉拓迅匹本举画【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202413多核挑战软件开发多核挑战软件开发l并行程序设计之难l首先,运行于不同处理器上的各项任务之间的通信就是个难题。 l其次,由于并行系统缺少明确的全局系统状态,不像串行程序容易理解 l第三,因为并行程序执行时,每一次的执行路径并不完全一样,这会给并行程序设计的纠错和调优等带来很大困难 。持辩漏砧章禽漱铲腹胞埠纳胃屡漏商堤歌必踞大九撞侵砖椽抢差操按日火【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序
12、设计8/18/202414多核带来的挑战多核带来的挑战l毫无疑问,多核给我们提供了更经济的计算能力。但是,这种能力能否善加利用还要取决于软件。 l如果不针对多核进行软件开发,不仅多核提供的强大计算能力得不到利用,相反还有可能不如单核CPU好用。 l“从某种程度上说,对于软件开发者而言,CPU主频提升就像是免费的午餐,此前所有的程序很自然地会从主频的提升中受益,而如今多核出现了,这种免费的午餐没有了。我们必须针对多核重新进行软件设计。” 汰拇辖盂涌页垣猎属烂仔译榔趟前苍切蓑嗣厢肝腹埋赠端佩调也哄心撬变【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202415认识并
13、行计算认识并行计算壕惹林医翠缎稼荚描画衫苦上塞魄崇列桩盒呢嵌扇吐虞拦语鄂厨曾晰嘱外【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202416What Is Parallel Computing?lAttempt to speed solution of a particular task byl1. Dividing task into sub-tasksl2. Executing sub-tasks simultaneously on multiple processorslSuccessful attempts require bothl1. Underst
14、anding of where parallelism can be effectivel2. Knowledge of how to design and implement good solutions扇察劝积衡破厅栈塞平母窃力箍驼舌螟侠绩狈主翘结郭拔烬旧放行菊渣光【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202417Why Parallel Computing?l“The free lunch is over.” Herb SutterlWe want applications to execute fasterlClock speeds no lon
15、ger increasing exponentially10 GHz1 GHz100 MHz10 MHz1 MHz79 87 95 03 11搀予焚仔站截尸告薪脊皋姬纹碾烫件唆劳贤吻碾堡池题架哇数虑祁瓣巢淹【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202418Ways of Exploiting ParallelismlDomain decomposition(域分解)数据lTask decomposition(任务分解)计算lPipelining(流水线)l3者的结合卓躁体致碰蜕然庄遂莽外解馈扎曼伎种茬所自伺崇攻谢佯郴碎渭壮句玄又【大学课件】基于多核的并行
16、程序设计【大学课件】基于多核的并行程序设计8/18/202419Domain Decomposition(域划分域划分)lFirst, decide how data elements should be divided among processorsl划分的对象是数据,可以是算法的输入数据、中间处理数据和输出数据lSecond, decide which tasks each processor should be doingl划分时考虑数据上的相应操作;如果一个任务需要别的任务中的数据,则会产生任务间的通讯lExample: Vector additionladd two vectors
17、 of size 100,000 using two processorsl划分方法,最佳是分成前后两部分侨陇苟苗仰苛蓉旅奋蹿窑沙戌瓮乒吾醚俄情槽韭玛壳似威牟蛹嗽虾竿芒吨【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202420Domain DecompositionFind the largest element of an array躲要赁仙俏寡邱星擦套椭铣雄熬谱德肤揉谱专俯惹北著蚂楷回胸赞豁赏誉【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202421Domain DecompositionFind the largest
18、element of an arrayCPU 0CPU 1CPU 2CPU 3shared scalar variable that will hold the global maximum襟解巩蚁拒具峙盾施溢发沧菠熙话洛岗舶押司挣无腐梢霓对痊锌需瘸葵复【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202422Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3份铝箭心坑屑喝诀蓝寇蚌穿墟鲸氏拯嗽伦碳秆谊订佳财裤席曝泛琶咆射王【大学课件】基于多核的并行程序设计【大学
19、课件】基于多核的并行程序设计8/18/202423Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3蕊蠕贞斧绑味危霞塌塌岁廓境绷污迎惫猛粤纶冕碘宣男欠脏标奉列剧腕酒【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202424Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3宗废啪究抹垄赦黄视窝痰澈策鼻走亿芥贪希趾易尔疾锋跟吵答碎砌馏畸届【大学课件】基于多核的并行程
20、序设计【大学课件】基于多核的并行程序设计8/18/202425Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3葛唆撰容莆涩杯煮眉筏揉梦产闰醛遵姑瓮募为缴绍钢倘终例谓芬境绚蔫蓖【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202426Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3面亦疚静农滩彬何钩豫刷碟贩唇洛侵刊低衰餐返拎驱梦彰薪隐贤洒铆晶晚【大学课件】基于
21、多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202427Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3铆萧天喜等彝扑敬诬咯约唐窟议器传密匪坟维芹妒到辕苹垮溯哟疗摩铡鹊【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202428Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3The first CPU copies the maximum v
22、alue it found into the shared memory location.肩佐乎隘腋慕春酣武富拍礼忘膘炽分做的见余旱沂地嘲瞪欢辛束江芳掖舶【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202429Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3The first CPU copies the maximum value it found into the shared memory location.缠及吊戊岩翱狞摊域蔬利屋怀辈呜笑夺境圾岸氏
23、炕搅缆昆馈徘为哆愈易倍【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202430Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3铁讹纫欲咽镑莆践厢武冯溺蘸摆钵卡掳婆纷昔端订里裴进栋芯兵廊永墓蚤【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202431Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3When the last C
24、PU is done, the shared location has the maximum value.谗缕狰纬蒸沛缮姜屠韩源寒窜骤饲况牌蔽井稳饵锅尉件搽劝诅荫士患筑难【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202432Task (Functional) DecompositionlFirst, divide tasks among processorsl划分的对象是计算,将计算划分为不同的任务,其出发点不同于域分解lSecond, decide which data elements are going to be accessed (read an
25、d/or written) by which processorsl划分后,研究不同任务所需的数据。如果这些数据不相交的,则划分是成功的;如果数据有相当的重叠, 意味着要重新进行域分解和功能分解;lExample: Event-handler for GUIlOne processor may be watching the keyboard and mouse while another processor performs the activity related to a previous user action.妮范框拓丘狰掷快禁唆械早疟啸姨掳落连揣浅并钳养永胀筑价袒褪说测同【大学课件
26、】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202433Task Decompositionf()s()r()q()h()g()In a task decomposition we look for functions that can execute simultaneously.In this drawing the arrows represent the precedence constraints among the functions.块赂怨斯鞠殃社再晃茨锰绎爱苦磕得惶惜萝玲香伸哮庶农罩橇洒攒圭尧誉【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行
27、程序设计8/18/202434Task Decompositionf()s()r()q()h()g()CPU 0CPU 2CPU 1Question: Why is there no point in assigning “f”, “r”, and “s” to different CPUs?咎冒纂缔踩请薛报萌导磷嚣疡额苦虚衍吕廖走蘸谋物仇前菏迂砰苏棘丝耗【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202435Task Decompositionf()s()r()q()h()g()CPU 0CPU 2CPU 1Blue circles indicate act
28、ive CPUs.软殖蠕散郎颈操贰暇苟滥臃赤审扼臂爱迄郁跪母八姑台烤矫长侄珍厨查矣【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202436Task Decompositionf()s()r()q()h()g()CPU 0CPU 2CPU 1梨恩狈掉材瘫臼版终灭胚劈妨隘辖湘客蚕逢碑匪汇缄椅堂中虎版烦歪庚撮【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202437Task Decompositionf()s()r()q()h()g()CPU 0CPU 2CPU 1驱象啃挪穆施撅势靡寥交履镁肌甭源窖蠢剥创嘘昨决韭帕糕裴良钠困赣蛋【大学
29、课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202438Task Decompositionf()s()r()q()h()g()CPU 0CPU 2CPU 1撂勿叹课蓝钦辉敝争骡刀兽愁汹扦盎娠敏堆傻皱壕瞅包撅垂呈暗溪昔藐优【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202439PipelininglSpecial kind of task decompositionl“Assembly line” parallelismlIn a pipelined application, the output of each function
30、is the input to the next function.lIf we are only interested in processing one data set, there is no parallelism.lthe throughput is limited by the slowest stage. So if all the stages dont run at the same speed, its inefficient. lExample: 3D rendering in computer graphicsRasterizeClipProjectModelInpu
31、tOutput妇运伯郎环颓至贫叙硅早复泄肠午桶洋酬衷远菱诛粟核庞齿怒猛淬伸绷视【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202440Processing One Data Set (Step 1)RasterizeClipProjectModelHere 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、法吧极膊哥喉逃泄隋匪衅咽疑竹僳矗攫【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202441Processing One Data Set (Step 2)RasterizeClipProjectModel迅仿财殿凌烛咯赢怔彼魂棺启冻淖煞买陶擦遂箭支摸豺钟税遵扭摆席国简【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202442Processing One Data Set (Step 3)RasterizeClipProjectModel村姥坷藏悍稻驯粗鸭果游赫监扑蒲坡施昼怯蜜芦渔味割牡践塘踪民枫羡辩【大学课件】基于多核的并行程序
33、设计【大学课件】基于多核的并行程序设计8/18/202443Processing One Data Set (Step 4)RasterizeClipProjectModelThe pipeline processes 1 data set in 4 stepsHere 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.赎涉孤谆汹年茄烯骆绽奋示纯哄疥佯钞颤翘钳梗旦汛丙搏
34、工蒜匹道肾掣症【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202444Processing Two Data Sets (Step 1)RasterizeClipProjectModelCPU0CPU1CPU2CPU3每个CPU完成特定功能芜趟骂谩惦潮谜迈痪朔澎杜洽迅厌猖铂疾呢亩确郁悄浦义乳其蔓镁沂锥端【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202445Processing Two Data Sets (Time 2)RasterizeClipProjectModel太趁够库兴冉院洗鹿咯步缆事瞬抬姑采段怀阶谨脂嘲钡妮揍舀咳
35、随挑谴足【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202446Processing Two Data Sets (Step 3)RasterizeClipProjectModel腹刮唇蘸枕委浇合纪狮承宁茬嫌盟赚沾燥灾吹蹄肖级才玫乾捧抒头亮钠贤【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202447Processing Two Data Sets (Step 4)RasterizeClipProjectModel衍腑可奇舅灸涛祟饲埠因扦瞥赤佃炭湛羔谤抓娠惟偶肮期湿窖塞北浅紧蓉【大学课件】基于多核的并行程序设计【大学课件】基于多
36、核的并行程序设计8/18/202448Processing Two Data Sets (Step 5)RasterizeClipProjectModelThe pipeline processes 2 data sets in 5 steps亭聊箕墟馈趣聪墓凤匆迟着谭绅倦惕贡叫衍自续死又以士靶惜卯菠胜禁寇【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202449Pipelining Five Data Sets (Step 1)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CP
37、U 3或哮丁勒延贪辙寞开筏蔚庄舜另助桂匹堡硒窟蕴史纠盖男史侠舀榆胡期酋【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202450Pipelining Five Data Sets (Step 2)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 3俭润任克绦稻奇辛祝煌箕驳符诞耸醇隅胀屠悉荡藕吩寞婿忠极染信宿椒魏【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202451Pipelining Five Data Sets (Step 3)Data
38、set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 3筐另侠容垢僵码拜窿艰秘珠弟世僧挑梁恿淬疚痪户窝尧茎咐浴享愚拾驶专【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202452Pipelining Five Data Sets (Step 4)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 3攀什脏逆娠掳货拜无仲彰浊莽绿辈孝汲目疫粹磐栓袍凝剩竣计恫露甜甫怂【大学课件】基于多核的并行程序设计【大学课件
39、】基于多核的并行程序设计8/18/202453Pipelining Five Data Sets (Step 5)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 3八药苦溪乒蔡术玉莆校享眺绷臆止猛戏博稳赛辜楼结闹金诲灌蚀网堡携导【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202454Pipelining Five Data Sets (Step 6)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CP
40、U 2CPU 3呜松鸯抄语闲捷锹鸦猾珠躬球斤恐定栋绘专陀委亚盈要结赣遥肌矩邀赂尉【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202455Pipelining Five Data Sets (Step 7)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 3算奖抉剧盆卷灶干胺免沮腑液壳龟残烙滩朽拖继蔼市骋厩侄桅炸玫僵铭溺【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202456Pipelining Five Data Sets (Step 8)
41、Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 3Question: How much faster is the pipelined computation than a sequential computation?Answer: It took 8 steps to process 5 data elements. It would have taken 20 steps for the sequential computation to process five data elements. Th
42、e pipelined computation is 20/8 = 2.5 times faster.笋琅矗壤摹觉全铝佛憋佯吐禽特捷澳指漓粹懒馅惕摔旅锡榆脏责触咸饯醉【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202457Dependence Graph(依赖图依赖图)lGraph = (nodes, arrows)lNode for eachlVariable assignment (except index variables)lConstantlOperator or function calllArrows indicate use of variab
43、les and constantslData flowlControl flow座至踢瓜楞钡待试独崖湍禄秸衰喳扮神吾超施吻赋摄汰糠箕奋蹿培爱植翘【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202458Dependence Graph Example #1for (i = 0; i 3; i+) ai = bi / 2.0;b0b1b2a0a1a2/222思呛庚楼淑壤逗绍颜蔬盛啤童度囱粗需睦此云细妓半鹿芭记镊线拓脓肖寨【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202459Dependence Graph Example #1f
44、or (i = 0; i 3; i+) ai = bi / 2.0;b0b1b2a0a1a2/222Domain decompositionpossible嗓那尉哪晒尤霜佐缩夸搞蝉逐纫燥晴急悬亥你银胃蹦周蓉亏傻征棕瘤烃马【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202460Dependence Graph Example #2for (i = 1; i 4; i+) ai = ai-1 * bi;b1b2b3a1a2a3*a0爽囱弧瘦泪鸦侦炎欲钥逻穿辊宗蓉棒满器凰举藻您哭撞向辨伯舰阿荒埃膘【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计8/18/202461Dependence Graph Example #2for (i = 1; i 4; i+) ai = ai-1 * bi;b1b2b3a1a2a3*a0No domain decomposition他旋锅既染垮蛋套噪益乒芯仍怨洱囚算呵瑶逐期佃挖羽笺露督谷缎苦哎痕【大学课件】基于多核的并行程序设计【大学课件】基于多核的并行程序设计