《基于多核的并行程序设计.ppt》由会员分享,可在线阅读,更多相关《基于多核的并行程序设计.ppt(61页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、基于多核的并行程序设计基于多核的并行程序设计2023/4/162outlinel参考资料lbaidu/googlel课本l并行编程模式(清华大学出版社)l并行程序设计(机械工业出版社)l老师/助教l预备知识l计算机组成原理l操作系统lc/c+2023/4/163课程安排课程安排l并行体系与多核体系结构 l多核计算机系统的操作系统 l基于多核计算机系统的软件开发工具 l基于多核的软件设计 l基于多核平台的程序调试和优化技术 2023/4/164多核发展及其挑战多核发展及其挑战2023/4/165拉开多核时代的序幕在在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遭遇终极瓶颈遭遇终极瓶颈英特尔不得不承认奔腾系列已经遭遇最终的主频极限,英特尔不得不承认奔腾系列已经遭遇最终的主频极限,4G
3、就象一场百年罕见地就象一场百年罕见地强降雪,将奔腾系列强降雪,将奔腾系列CPU的性能高速公路永远地封死了。因此,以英特尔为首的性能高速公路永远地封死了。因此,以英特尔为首的的CPU军团不得不另外找一条更宽的性能高速公路来继续他们的军团不得不另外找一条更宽的性能高速公路来继续他们的CPU神话神话 另寻出路另寻出路2023/4/166多核处理器的基本架构l背景背景:随着芯片制成工艺的不断进步,从体系结构来看,传统的处理器体系结构技术已面临瓶颈,晶体管集成度已经过亿,很难通过提高主频来提升性能;从应用需求来看,日益复杂的多媒体、科学计算、虚拟化等多个应用领域都呼唤更为强大的计算能力。在这样的背景下,
4、各主流处理器厂商纷纷将产品战略从提高芯片的时钟频率转向多线程、多内核。1.1.多核芯片多核芯片l发展近况发展近况:继双核之后,Intel已经在2006年11月推出了4核产品,AMD也推出了代号为巴塞罗那的4核处理器。目前,多核处理器的推出越演越烈,在推出了代号为Niagara的8核处理器之后,Sun公司还计划推出Niagara2处理器。Intel近日内声称,明年即将研制推出10核以上的处理器产品。2023/4/167Front Side BusFront Side Bus多核处理器简介多核处理器简介l什么是多核处理器l两个或多个独立运行的内核集成于同一个处理器上l双核处理器=一个处理器上包含2
5、个内核Core0Core0Core1Core12023/4/168多核处理器简介多核处理器简介l为什么采用双核双核共享封装和双核共享封装和I/O时时,总成本下降总成本下降封装和测试占总成封装和测试占总成本的本的20%-50%,I/O通常占晶片面积的通常占晶片面积的15-20%功耗功耗成本成本性能性能单核多核主频超过主频超过2GHz时功耗超过时功耗超过100W仅靠主频驱动仅靠主频驱动平衡性能与功耗平衡性能与功耗由主频和每时钟周由主频和每时钟周期所执行的指令数期所执行的指令数来实现来实现2023/4/169l定义:定义:片上多核处理器(Chip Multi-Processor,CMP)就是将多个计
6、算内核集成在一个处理器芯片中,从而提高计算能力。多核处理器的基本架构多核处理器的基本架构2.2.片上多核处理器体系结构片上多核处理器体系结构l分类:分类:按计算内核是否对等,CMP可分为同构多核和异构多核。计算内核相同,地位对等计算内核相同,地位对等的称为“同构多核”,现在Intel和AMD主推的双核处理器就是同构多核的;计算内核不同,地位计算内核不同,地位不对等不对等的称为“异构多核”,异构多核采用“主处理器协处理器”的设计,IBM、SONY等联手推出的Cell处理器就是异构多核处理器的典范。2023/4/1610l硬件结构:硬件结构:由于CMP处理器的各CPU核心执行的程序之间有时需要进行
7、数据共享与同步,故硬件结构必须支持核间通信。多核处理器的基本架构多核处理器的基本架构2.2.片上多核处理器体系结构片上多核处理器体系结构l总线共享总线共享cache结构:结构:是指每个CPU内核拥有共享的二级或三级cache,用于保存比较常用的数据,并通过连接核心的总线进行通信。优点:结构简单、通信速度高。缺点:基于总线的结构可扩展性较差。l基于片上互连的结构:基于片上互连的结构:指每个CPU内核拥有独立的处理单元和cache,各个CPU核心间通过交叉开关或片上网络等方式连接在一起,各个CPU核心间通过消息通信。优点:可扩展性好、数据带宽有保证。缺点:硬件结构复杂,且软件改动较大。2023/4
8、/1611多核挑战软件开发多核挑战软件开发l多核的影响 传统的科学计算传统的科学计算 原有软件大都是并行的原有软件大都是并行的多核提供了更高性能的执行平台多核提供了更高性能的执行平台需要做的是针对多核进行优化需要做的是针对多核进行优化,多核应用不存在困难多核应用不存在困难服务器软件服务器软件 业务特征是并发的业务特征是并发的,应用具有天然的并发性应用具有天然的并发性 多核提供了一个高性能计算平台多核提供了一个高性能计算平台,面临挑战不大面临挑战不大 原有大部分程序是串行的原有大部分程序是串行的 需要很好的并行编程模型和开发环境需要很好的并行编程模型和开发环境,挑战很大挑战很大 桌面软件桌面软件
9、2023/4/1612多核挑战软件开发多核挑战软件开发l并行程序设计为什么难?l其根本原因是因为大多数计算机和编程语言发明之初就是按照冯诺依曼理论进行设计的。根据冯诺依曼的理论,CPU是按照程序指令,一条条取出来并顺序执行的。而在多核或者多CPU的计算机中,同时会有多条指令在执行。2023/4/1613多核挑战软件开发多核挑战软件开发l并行程序设计之难l首先,运行于不同处理器上的各项任务之间的通信就是个难题。l其次,由于并行系统缺少明确的全局系统状态,不像串行程序容易理解 l第三,因为并行程序执行时,每一次的执行路径并不完全一样,这会给并行程序设计的纠错和调优等带来很大困难。2023/4/16
10、14多核带来的挑战多核带来的挑战l毫无疑问,多核给我们提供了更经济的计算能力。但是,这种能力能否善加利用还要取决于软件。l如果不针对多核进行软件开发,不仅多核提供的强大计算能力得不到利用,相反还有可能不如单核CPU好用。l“从某种程度上说,对于软件开发者而言,CPU主频提升就像是免费的午餐,此前所有的程序很自然地会从主频的提升中受益,而如今多核出现了,这种免费的午餐没有了。我们必须针对多核重新进行软件设计。”2023/4/1615认识并行计算认识并行计算2023/4/1616What Is Parallel Computing?lAttempt to speed solution of a p
11、articular task byl1.Dividing task into sub-tasksl2.Executing sub-tasks simultaneously on multiple processorslSuccessful attempts require bothl1.Understanding of where parallelism can be effectivel2.Knowledge of how to design and implement good solutions2023/4/1617Why Parallel Computing?l“The free lu
12、nch is over.”Herb SutterlWe want applications to execute fasterlClock speeds no longer increasing exponentially10 GHz1 GHz100 MHz10 MHz1 MHz79 87 95 03 112023/4/1618Ways of Exploiting ParallelismlDomain decomposition(域分解)数据lTask decomposition(任务分解)计算lPipelining(流水线)l3者的结合2023/4/1619Domain Decomposit
13、ion(域划分域划分)lFirst,decide how data elements should be divided among processorsl划分的对象是数据,可以是算法的输入数据、中间处理数据和输出数据lSecond,decide which tasks each processor should be doingl划分时考虑数据上的相应操作;如果一个任务需要别的任务中的数据,则会产生任务间的通讯lExample:Vector additionladd two vectors of size 100,000 using two processorsl划分方法,最佳是分成前后两部
14、分2023/4/1620Domain DecompositionFind the largest element of an array2023/4/1621Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3shared scalar variable that will hold the global maximum2023/4/1622Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 320
15、23/4/1623Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 32023/4/1624Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 32023/4/1625Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 32023/4/1626Domain DecompositionFind the l
16、argest element of an arrayCPU 0CPU 1CPU 2CPU 32023/4/1627Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 32023/4/1628Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3The first CPU copies the maximum value it found into the shared memory location.
17、2023/4/1629Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3The first CPU copies the maximum value it found into the shared memory location.2023/4/1630Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 32023/4/1631Domain DecompositionFind the larges
18、t element of an arrayCPU 0CPU 1CPU 2CPU 3When the last CPU is done,the shared location has the maximum value.2023/4/1632Task(Functional)DecompositionlFirst,divide tasks among processorsl划分的对象是计算,将计算划分为不同的任务,其出发点不同于域分解lSecond,decide which data elements are going to be accessed(read and/or written)by
19、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.2023/4/1633Task Decompositionf()s()r()q()h()g()In a task
20、 decomposition we look for functions that can execute simultaneously.In this drawing the arrows represent the precedence constraints among the functions.2023/4/1634Task Decompositionf()s()r()q()h()g()CPU 0CPU 2CPU 1Question:Why is there no point in assigning“f”,“r”,and“s”to different CPUs?2023/4/163
21、5Task Decompositionf()s()r()q()h()g()CPU 0CPU 2CPU 1Blue circles indicate active CPUs.2023/4/1636Task Decompositionf()s()r()q()h()g()CPU 0CPU 2CPU 12023/4/1637Task Decompositionf()s()r()q()h()g()CPU 0CPU 2CPU 12023/4/1638Task Decompositionf()s()r()q()h()g()CPU 0CPU 2CPU 12023/4/1639PipelininglSpecia
22、l kind of task decompositionl“Assembly line”parallelismlIn a pipelined application,the output of each function 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
23、 at the same speed,its inefficient.lExample:3D rendering in computer graphicsRasterizeClipProjectModelInputOutput2023/4/1640Processing 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 o
24、ne step for each stage.2023/4/1641Processing One Data Set(Step 2)RasterizeClipProjectModel2023/4/1642Processing One Data Set(Step 3)RasterizeClipProjectModel2023/4/1643Processing One Data Set(Step 4)RasterizeClipProjectModelThe pipeline processes 1 data set in 4 stepsHere a graphics rendering comput
25、ation can be divided into four stages.If we want to process only one data set,it takes one step for each stage.2023/4/1644Processing Two Data Sets(Step 1)RasterizeClipProjectModelCPU0CPU1CPU2CPU3每个CPU完成特定功能2023/4/1645Processing Two Data Sets(Time 2)RasterizeClipProjectModel2023/4/1646Processing Two
26、Data Sets(Step 3)RasterizeClipProjectModel2023/4/1647Processing Two Data Sets(Step 4)RasterizeClipProjectModel2023/4/1648Processing Two Data Sets(Step 5)RasterizeClipProjectModelThe pipeline processes 2 data sets in 5 steps2023/4/1649Pipelining Five Data Sets(Step 1)Data set 0Data set 1Data set 2Dat
27、a set 3Data set 4CPU 0CPU 1CPU 2CPU 32023/4/1650Pipelining Five Data Sets(Step 2)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32023/4/1651Pipelining Five Data Sets(Step 3)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32023/4/1652Pipelining Five Data Set
28、s(Step 4)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32023/4/1653Pipelining Five Data Sets(Step 5)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32023/4/1654Pipelining Five Data Sets(Step 6)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU
29、 2CPU 32023/4/1655Pipelining Five Data Sets(Step 7)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32023/4/1656Pipelining Five Data Sets(Step 8)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 3Question:How much faster is the pipelined computation than a sequ
30、ential 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.The pipelined computation is 20/8=2.5 times faster.2023/4/1657Dependence Graph(依赖图依赖图)lGraph=(nodes,arrows)lNode for eachlVariable assignment
31、(except index variables)lConstantlOperator or function calllArrows indicate use of variables and constantslData flowlControl flow2023/4/1658Dependence Graph Example#1for(i=0;i 3;i+)ai=bi/2.0;b0b1b2a0a1a2/2222023/4/1659Dependence Graph Example#1for(i=0;i 3;i+)ai=bi/2.0;b0b1b2a0a1a2/222Domain decompositionpossible2023/4/1660Dependence Graph Example#2for(i=1;i 4;i+)ai=ai-1*bi;b1b2b3a1a2a3*a02023/4/1661Dependence Graph Example#2for(i=1;i 4;i+)ai=ai-1*bi;b1b2b3a1a2a3*a0No domain decomposition
限制150内