基于多核的并行程序设计

基于多核的并行程序设计/sundae_meng2026/1/252outline参考资料baidu/google课本并行编程模式（清华大学出版社）并行程序设计（机械工业出版社）老师/助教预备知识计算机组成原理操作系统c/c++2026/1/253课程安排并行体系与多核体系结构多核计算机系统的操作系统基于多核计算机系统的软件开发工具基于多核的软件设计基于多核平台的程序调试和优化技术2026/1/254多核发展及其挑战2026/1/255拉开多核时代的序幕在CPU快速发展的20年里,CPU一次次地遭遇性能极限，但都又一次次地冲破了这个极限.从奔腾到奔腾2，CPU也突破了1GHZ，从奔腾2到奔腾3，CPU从1GHZ突破了2GHZ，从奔腾3到奔腾4，CPU也终于突破了3GHZ，现在最高的CPU主频已经高达3.8GHZ

单核CPU的极限突破单核CPU好象停止了前进，到3.8G却怎么也超不过4G单核CPU遭遇终极瓶颈英特尔不得不承认奔腾系列已经遭遇最终的主频极限，4G就象一场百年罕见地强降雪，将奔腾系列CPU的性能高速公路永远地封死了。因此，以英特尔为首的CPU军团不得不另外找一条更宽的性能高速公路来继续他们的CPU神话

另寻出路2026/1/256多核处理器的基本架构背景：随着芯片制成工艺的不断进步，从体系结构来看，传统的处理器体系结构技术已面临瓶颈，晶体管集成度已经过亿，很难通过提高主频来提升性能；从应用需求来看，日益复杂的多媒体、科学计算、虚拟化等多个应用领域都呼唤更为强大的计算能力。在这样的背景下，各主流处理器厂商纷纷将产品战略从提高芯片的时钟频率转向多线程、多内核。1.多核芯片发展近况：继双核之后，Intel已经在2006年11月推出了4核产品，AMD也推出了代号为巴塞罗那的4核处理器。目前，多核处理器的推出越演越烈，在推出了代号为Niagara的8核处理器之后，Sun公司还计划推出Niagara2处理器。Intel近日内声称，明年即将研制推出10核以上的处理器产品。2026/1/257FrontSideBus多核处理器简介什么是多核处理器两个或多个独立运行的内核集成于同一个处理器上双核处理器=一个处理器上包含2个内核Core0Core12026/1/258多核处理器简介为什么采用双核双核共享封装和I/O时,总成本下降封装和测试占总成本的20%-50%,I/O通常占晶片面积的15-20%功耗成本性能单核多核主频超过2GHz时功耗超过100W仅靠主频驱动平衡性能与功耗由主频和每时钟周期所执行的指令数来实现2026/1/259定义：片上多核处理器（ChipMulti-Processor,CMP）就是将多个计算内核集成在一个处理器芯片中，从而提高计算能力。多核处理器的基本架构2.片上多核处理器体系结构分类：按计算内核是否对等，CMP可分为同构多核和异构多核。计算内核相同，地位对等的称为“同构多核”，现在Intel和AMD主推的双核处理器就是同构多核的；计算内核不同，地位不对等的称为“异构多核”，异构多核采用“主处理器＋协处理器”的设计，IBM、SONY等联手推出的Cell处理器就是异构多核处理器的典范。2026/1/2510硬件结构：由于CMP处理器的各CPU核心执行的程序之间有时需要进行数据共享与同步，故硬件结构必须支持核间通信。多核处理器的基本架构2.片上多核处理器体系结构总线共享cache结构：是指每个CPU内核拥有共享的二级或三级cache，用于保存比较常用的数据，并通过连接核心的总线进行通信。优点：结构简单、通信速度高。缺点：基于总线的结构可扩展性较差。基于片上互连的结构：指每个CPU内核拥有独立的处理单元和cache，各个CPU核心间通过交叉开关或片上网络等方式连接在一起，各个CPU核心间通过消息通信。优点：可扩展性好、数据带宽有保证。缺点：硬件结构复杂，且软件改动较大。2026/1/2511多核挑战软件开发多核的影响

传统的科学计算

原有软件大都是并行的多核提供了更高性能的执行平台需要做的是针对多核进行优化,多核应用不存在困难服务器软件

业务特征是并发的,应用具有天然的并发性多核提供了一个高性能计算平台,面临挑战不大

原有大部分程序是串行的需要很好的并行编程模型和开发环境,挑战很大

桌面软件2026/1/2512多核挑战软件开发并行程序设计为什么难？其根本原因是因为大多数计算机和编程语言发明之初就是按照冯·诺依曼理论进行设计的。根据冯·诺依曼的理论，CPU是按照程序指令，一条条取出来并顺序执行的。而在多核或者多CPU的计算机中，同时会有多条指令在执行。2026/1/2513多核挑战软件开发并行程序设计之难首先，运行于不同处理器上的各项任务之间的通信就是个难题。其次，由于并行系统缺少明确的全局系统状态，不像串行程序容易理解第三，因为并行程序执行时，每一次的执行路径并不完全一样，这会给并行程序设计的纠错和调优等带来很大困难。2026/1/2514多核带来的挑战毫无疑问，多核给我们提供了更经济的计算能力。但是，这种能力能否善加利用还要取决于软件。如果不针对多核进行软件开发，不仅多核提供的强大计算能力得不到利用，相反还有可能不如单核CPU好用。“从某种程度上说，对于软件开发者而言，CPU主频提升就像是免费的午餐，此前所有的程序很自然地会从主频的提升中受益，而如今多核出现了，这种免费的午餐没有了。我们必须针对多核重新进行软件设计。”

2026/1/2515认识并行计算2026/1/2516WhatIsParallelComputing?Attempttospeedsolutionofaparticulartaskby 1.Dividingtaskintosub-tasks 2.Executingsub-taskssimultaneouslyon multipleprocessorsSuccessfulattemptsrequireboth 1.Understandingofwhereparallelismcanbeeffective 2.Knowledgeofhowtodesignandimplement good solutions 2026/1/2517WhyParallelComputing?“Thefreelunchisover.”

—HerbSutterWewantapplicationstoexecutefasterClockspeedsnolongerincreasingexponentially10GHz1GHz100MHz10MHz1MHz’79’87’95’03’112026/1/2518WaysofExploitingParallelismDomaindecomposition(域分解)－数据Taskdecomposition(任务分解)－计算Pipelining(流水线)3者的结合2026/1/2519DomainDecomposition(域划分)First,decidehowdataelementsshouldbedivided amongprocessors划分的对象是数据，可以是算法的输入数据、中间处理数据和输出数据Second,decidewhichtaskseachprocessorshouldbedoing划分时考虑数据上的相应操作；如果一个任务需要别的任务中的数据，则会产生任务间的通讯Example:Vectoradditionaddtwovectorsofsize100,000usingtwoprocessors划分方法，最佳是分成前后两部分2026/1/2520DomainDecompositionFindthelargestelementofanarray2026/1/2521DomainDecompositionFindthelargestelementofanarrayCPU0CPU1CPU2CPU3sharedscalarvariablethatwillholdtheglobalmaximum2026/1/2522DomainDecompositionFindthelargestelementofanarrayCPU0CPU1CPU2CPU32026/1/2523DomainDecompositionFindthelargestelementofanarrayCPU0CPU1CPU2CPU32026/1/2524DomainDecompositionFindthelargestelementofanarrayCPU0CPU1CPU2CPU32026/1/2525DomainDecompositionFindthelargestelementofanarrayCPU0CPU1CPU2CPU32026/1/2526DomainDecompositionFindthelargestelementofanarrayCPU0CPU1CPU2CPU

32026/1/2527DomainDecompositionFindthelargestelementofanarrayCPU0CPU1CPU2CPU32026/1/2528DomainDecompositionFindthelargestelementofanarrayCPU0CPU1CPU2CPU3ThefirstCPUcopiesthemaximumvalueitfoundintothesharedmemorylocation.2026/1/2529DomainDecompositionFindthelargestelementofanarrayCPU0CPU1CPU2CPU3ThefirstCPUcopiesthemaximumvalueitfoundintothesharedmemorylocation.2026/1/2530DomainDecompositionFindthelargestelementofanarrayCPU0CPU1CPU2CPU32026/1/2531DomainDecompositionFindthelargestelementofanarrayCPU0CPU1CPU

2CPU

3WhenthelastCPUisdone,thesharedlocationhasthemaximumvalue.2026/1/2532Task(Functional)DecompositionFirst,dividetasksamongprocessors划分的对象是计算，将计算划分为不同的任务，其出发点不同于域分解Second,decidewhichdataelementsaregoingtobeaccessed(readand/orwritten)bywhichprocessors划分后，研究不同任务所需的数据。如果这些数据不相交的，则划分是成功的；如果数据有相当的重叠，意味着要重新进行域分解和功能分解；Example:Event-handlerforGUIOneprocessormaybewatchingthekeyboardandmousewhileanotherprocessorperformstheactivityrelatedtoaprevioususeraction.2026/1/2533TaskDecompositionf()s()r()q()h()g()Inataskdecompositionwelookforfunctionsthatcanexecutesimultaneously.Inthisdrawingthearrowsrepresenttheprecedenceconstraintsamongthefunctions.2026/1/2534TaskDecompositionf()s()r()q()h()g()CPU0CPU2CPU

1Question:Whyistherenopointinassigning“f”,“r”,and“s”todifferentCPUs?2026/1/2535TaskDecompositionf()s()r()q()h()g()CPU0CPU2CPU1BluecirclesindicateactiveCPUs.2026/1/2536TaskDecompositionf()s()r()q()h()g()CPU0CPU2CPU12026/1/2537TaskDecompositionf()s()r()q()h()g()CPU0CPU2CPU12026/1/2538TaskDecompositionf()s()r()q()h()g()CPU0CPU2CPU12026/1/2539PipeliningSpecialkindoftaskdecomposition“Assemblyline”parallelismInapipelinedapplication,theoutputofeachfunctionistheinputtothenextfunction.Ifweareonlyinterestedinprocessingonedataset,thereisnoparallelism.thethroughputislimitedbythesloweststage.Soifallthestagesdon’trunatthesamespeed,it’sinefficient.Example:3DrenderingincomputergraphicsRasterizeClipProjectModelInputOutput2026/1/2540ProcessingOneDataSet(Step1)RasterizeClipProjectModelHereagraphicsrenderingcomputationcanbedividedintofourstages.Ifwewanttoprocessonlyonedataset,ittakesonestepforeachstage.2026/1/2541ProcessingOneDataSet(Step2)RasterizeClipProjectModel2026/1/2542ProcessingOneDataSet(Step3)RasterizeClipProjectModel2026/1/2543ProcessingOneDataSet(Step4)RasterizeClipProjectModelThepipelineprocesses1datasetin4stepsHereagraphicsrenderingcomputationcanbedividedintofourstages.Ifwewanttoprocessonlyonedataset,ittakesonestepforeachstage.2026/1/2544ProcessingTwoDataSets(Step1)RasterizeClipProjectModelCPU0CPU1CPU2CPU3每个CPU完成特定功能2026/1/2545ProcessingTwoDataSets(Time2)RasterizeClipProjectModel2026/1/2546ProcessingTwoDataSets(Step3)RasterizeClipProjectModel2026/1/2547ProcessingTwoDataSets(Step4)RasterizeClipProjectModel2026/1/2548ProcessingTwoDataSets(Step5)RasterizeClipProjectModelThepipelineprocesses2datasetsin5steps2026/1/2549PipeliningFiveDataSets(Step1)Dataset0Dataset1Dataset2Dataset3Dataset4CPU0CPU1CPU2CPU32026/1/2550PipeliningFiveDataSets(Step2)Dataset0Dataset1Dataset2Dataset3Dataset4CPU0CPU1CPU2CPU32026/1/2551PipeliningFiveDataSets(Step3)Dataset0Dataset1Dataset2Dataset3Dataset4CPU0CPU1CPU2CPU32026/1/2552PipeliningFiveDataSets(Step4)Dataset0Dataset1Dataset2Dataset3Dataset4CPU0CPU1CPU2CPU32026/1/2553PipeliningFiveDataSets(Step5)Dataset0Dataset1Dataset2Dataset3Dataset4CPU0CPU1CPU2CPU32026/1/2554PipeliningFiveDataSets(Step6)Dataset0Dataset1Dataset2Dataset3Dataset4CPU0CPU1CPU2CPU32026/1/2555PipeliningFiveDataSets(Step7)Dataset0Dataset1Dataset2Dataset3Dataset4CPU0CPU1CPU2CPU32026/1/2556PipeliningFiveDataSets(Step8)Dataset0Dataset1Dataset2Dataset3Dataset4CPU0CPU1CPU2CPU3Question:Howmuchfasteristhepipelinedcomputationthanasequentialcomputation?Answer:Ittook