基于多核的并行程序設(shè)計(jì)編輯pptoutline參考資料baidu/google課本并行編程模式（清華大學(xué)出版社）并行程序設(shè)計(jì)（機(jī)械工業(yè)出版社）老師/助教預(yù)備知識(shí)計(jì)算機(jī)組成原理操作系統(tǒng)c/c++2023/4/152編輯ppt課程安排并行體系與多核體系結(jié)構(gòu)多核計(jì)算機(jī)系統(tǒng)的操作系統(tǒng)基于多核計(jì)算機(jī)系統(tǒng)的軟件開發(fā)工具基于多核的軟件設(shè)計(jì)基于多核平臺(tái)的程序調(diào)試和優(yōu)化技術(shù)2023/4/153編輯ppt多核發(fā)展及其挑戰(zhàn)2023/4/154編輯ppt拉開多核時(shí)代的序幕在CPU快速發(fā)展的20年里,CPU一次次地遭遇性能極限，但都又一次次地沖破了這個(gè)極限.從奔騰到奔騰2，CPU也突破了1GHZ，從奔騰2到奔騰3，CPU從1GHZ突破了2GHZ，從奔騰3到奔騰4，CPU也終于突破了3GHZ，現(xiàn)在最高的CPU主頻已經(jīng)高達(dá)3.8GHZ

單核CPU的極限突破單核CPU好象停止了前進(jìn)，到3.8G卻怎么也超不過4G單核CPU遭遇終極瓶頸英特爾不得不承認(rèn)奔騰系列已經(jīng)遭遇最終的主頻極限，4G就象一場(chǎng)百年罕見地強(qiáng)降雪，將奔騰系列CPU的性能高速公路永遠(yuǎn)地封死了。因此，以英特爾為首的CPU軍團(tuán)不得不另外找一條更寬的性能高速公路來繼續(xù)他們的CPU神話

另尋出路2023/4/155編輯ppt多核處理器的基本架構(gòu)背景：隨著芯片制成工藝的不斷進(jìn)步，從體系結(jié)構(gòu)來看，傳統(tǒng)的處理器體系結(jié)構(gòu)技術(shù)已面臨瓶頸，晶體管集成度已經(jīng)過億，很難通過提高主頻來提升性能；從應(yīng)用需求來看，日益復(fù)雜的多媒體、科學(xué)計(jì)算、虛擬化等多個(gè)應(yīng)用領(lǐng)域都呼喚更為強(qiáng)大的計(jì)算能力。在這樣的背景下，各主流處理器廠商紛紛將產(chǎn)品戰(zhàn)略從提高芯片的時(shí)鐘頻率轉(zhuǎn)向多線程、多內(nèi)核。1.多核芯片發(fā)展近況：繼雙核之后，Intel已經(jīng)在2006年11月推出了4核產(chǎn)品，AMD也推出了代號(hào)為巴塞羅那的4核處理器。目前，多核處理器的推出越演越烈，在推出了代號(hào)為Niagara的8核處理器之后，Sun公司還計(jì)劃推出Niagara2處理器。Intel近日內(nèi)聲稱，明年即將研制推出10核以上的處理器產(chǎn)品。2023/4/156編輯pptFrontSideBus多核處理器簡(jiǎn)介什么是多核處理器兩個(gè)或多個(gè)獨(dú)立運(yùn)行的內(nèi)核集成于同一個(gè)處理器上雙核處理器=一個(gè)處理器上包含2個(gè)內(nèi)核Core0Core12023/4/157編輯ppt多核處理器簡(jiǎn)介為什么采用雙核雙核共享封裝和I/O時(shí),總成本下降封裝和測(cè)試占總成本的20%-50%,I/O通常占晶片面積的15-20%功耗成本性能單核多核主頻超過2GHz時(shí)功耗超過100W僅靠主頻驅(qū)動(dòng)平衡性能與功耗由主頻和每時(shí)鐘周期所執(zhí)行的指令數(shù)來實(shí)現(xiàn)2023/4/158編輯ppt定義：片上多核處理器（ChipMulti-Processor,CMP）就是將多個(gè)計(jì)算內(nèi)核集成在一個(gè)處理器芯片中，從而提高計(jì)算能力。多核處理器的基本架構(gòu)2.片上多核處理器體系結(jié)構(gòu)分類：按計(jì)算內(nèi)核是否對(duì)等，CMP可分為同構(gòu)多核和異構(gòu)多核。計(jì)算內(nèi)核相同，地位對(duì)等的稱為“同構(gòu)多核”，現(xiàn)在Intel和AMD主推的雙核處理器就是同構(gòu)多核的；計(jì)算內(nèi)核不同，地位不對(duì)等的稱為“異構(gòu)多核”，異構(gòu)多核采用“主處理器＋協(xié)處理器”的設(shè)計(jì)，IBM、SONY等聯(lián)手推出的Cell處理器就是異構(gòu)多核處理器的典范。2023/4/159編輯ppt硬件結(jié)構(gòu)：由于CMP處理器的各CPU核心執(zhí)行的程序之間有時(shí)需要進(jìn)行數(shù)據(jù)共享與同步，故硬件結(jié)構(gòu)必須支持核間通信。多核處理器的基本架構(gòu)2.片上多核處理器體系結(jié)構(gòu)總線共享cache結(jié)構(gòu)：是指每個(gè)CPU內(nèi)核擁有共享的二級(jí)或三級(jí)cache，用于保存比較常用的數(shù)據(jù)，并通過連接核心的總線進(jìn)行通信。優(yōu)點(diǎn)：結(jié)構(gòu)簡(jiǎn)單、通信速度高。缺點(diǎn)：基于總線的結(jié)構(gòu)可擴(kuò)展性較差。基于片上互連的結(jié)構(gòu)：指每個(gè)CPU內(nèi)核擁有獨(dú)立的處理單元和cache，各個(gè)CPU核心間通過交叉開關(guān)或片上網(wǎng)絡(luò)等方式連接在一起，各個(gè)CPU核心間通過消息通信。優(yōu)點(diǎn)：可擴(kuò)展性好、數(shù)據(jù)帶寬有保證。缺點(diǎn)：硬件結(jié)構(gòu)復(fù)雜，且軟件改動(dòng)較大。2023/4/1510編輯ppt多核挑戰(zhàn)軟件開發(fā)多核的影響

傳統(tǒng)的科學(xué)計(jì)算

原有軟件大都是并行的多核提供了更高性能的執(zhí)行平臺(tái)需要做的是針對(duì)多核進(jìn)行優(yōu)化,多核應(yīng)用不存在困難服務(wù)器軟件

業(yè)務(wù)特征是并發(fā)的,應(yīng)用具有天然的并發(fā)性多核提供了一個(gè)高性能計(jì)算平臺(tái),面臨挑戰(zhàn)不大

原有大部分程序是串行的需要很好的并行編程模型和開發(fā)環(huán)境,挑戰(zhàn)很大

桌面軟件2023/4/1511編輯ppt多核挑戰(zhàn)軟件開發(fā)并行程序設(shè)計(jì)為什么難？其根本原因是因?yàn)榇蠖鄶?shù)計(jì)算機(jī)和編程語(yǔ)言發(fā)明之初就是按照馮·諾依曼理論進(jìn)行設(shè)計(jì)的。根據(jù)馮·諾依曼的理論，CPU是按照程序指令，一條條取出來并順序執(zhí)行的。而在多核或者多CPU的計(jì)算機(jī)中，同時(shí)會(huì)有多條指令在執(zhí)行。2023/4/1512編輯ppt多核挑戰(zhàn)軟件開發(fā)并行程序設(shè)計(jì)之難首先，運(yùn)行于不同處理器上的各項(xiàng)任務(wù)之間的通信就是個(gè)難題。其次，由于并行系統(tǒng)缺少明確的全局系統(tǒng)狀態(tài)，不像串行程序容易理解第三，因?yàn)椴⑿谐绦驁?zhí)行時(shí)，每一次的執(zhí)行路徑并不完全一樣，這會(huì)給并行程序設(shè)計(jì)的糾錯(cuò)和調(diào)優(yōu)等帶來很大困難。2023/4/1513編輯ppt多核帶來的挑戰(zhàn)毫無疑問，多核給我們提供了更經(jīng)濟(jì)的計(jì)算能力。但是，這種能力能否善加利用還要取決于軟件。如果不針對(duì)多核進(jìn)行軟件開發(fā)，不僅多核提供的強(qiáng)大計(jì)算能力得不到利用，相反還有可能不如單核CPU好用。“從某種程度上說，對(duì)于軟件開發(fā)者而言，CPU主頻提升就像是免費(fèi)的午餐，此前所有的程序很自然地會(huì)從主頻的提升中受益，而如今多核出現(xiàn)了，這種免費(fèi)的午餐沒有了。我們必須針對(duì)多核重新進(jìn)行軟件設(shè)計(jì)?！?/p>

2023/4/1514編輯ppt認(rèn)識(shí)并行計(jì)算2023/4/1515編輯pptWhatIsParallelComputing?Attempttospeedsolutionofaparticulartaskby 1.Dividingtaskintosub-tasks 2.Executingsub-taskssimultaneouslyon multipleprocessorsSuccessfulattemptsrequireboth 1.Understandingofwhereparallelismcanbeeffective 2.Knowledgeofhowtodesignandimplement good solutions 2023/4/1516編輯pptWhyParallelComputing?“Thefreelunchisover.”

—HerbSutterWewantapplicationstoexecutefasterClockspeedsnolongerincreasingexponentially10GHz1GHz100MHz10MHz1MHz’79’87’95’03’112023/4/1517編輯pptWaysofExploitingParallelismDomaindecomposition(域分解)－數(shù)據(jù)Taskdecomposition(任務(wù)分解)－計(jì)算Pipelining(流水線)3者的結(jié)合2023/4/1518編輯pptDomainDecomposition(域劃分)First,decidehowdataelementsshouldbedivided amongprocessors劃分的對(duì)象是數(shù)據(jù)，可以是算法的輸入數(shù)據(jù)、中間處理數(shù)據(jù)和輸出數(shù)據(jù)Second,decidewhichtaskseachprocessorshouldbedoing劃分時(shí)考慮數(shù)據(jù)上的相應(yīng)操作；如果一個(gè)任務(wù)需要?jiǎng)e的任務(wù)中的數(shù)據(jù)，則會(huì)產(chǎn)生任務(wù)間的通訊Example:Vectoradditionaddtwovectorsofsize100,000usingtwoprocessors劃分方法，最佳是分成前后兩部分2023/4/1519編輯pptDomainDecompositionFindthelargestelementofanarray2023/4/1520編輯pptDomainDecompositionFindthelargestelementofanarrayCPU0CPU1CPU2CPU3sharedscalarvariablethatwillholdtheglobalmaximum2023/4/1521編輯pptDomainDecompositionFindthelargestelementofanarrayCPU0CPU1CPU2CPU32023/4/1522編輯pptDomainDecompositionFindthelargestelementofanarrayCPU0CPU1CPU2CPU32023/4/1523編輯pptDomainDecompositionFindthelargestelementofanarrayCPU0CPU1CPU2CPU32023/4/1524編輯pptDomainDecompositionFindthelargestelementofanarrayCPU0CPU1CPU2CPU32023/4/1525編輯pptDomainDecompositionFindthelargestelementofanarrayCPU0CPU1CPU2CPU

32023/4/1526編輯pptDomainDecompositionFindthelargestelementofanarrayCPU0CPU1CPU2CPU32023/4/1527編輯pptDomainDecompositionFindthelargestelementofanarrayCPU0CPU1CPU2CPU3ThefirstCPUcopiesthemaximumvalueitfoundintothesharedmemorylocation.2023/4/1528編輯pptDomainDecompositionFindthelargestelementofanarrayCPU0CPU1CPU2CPU3ThefirstCPUcopiesthemaximumvalueitfoundintothesharedmemorylocation.2023/4/1529編輯pptDomainDecompositionFindthelargestelementofanarrayCPU0CPU1CPU2CPU32023/4/1530編輯pptDomainDecompositionFindthelargestelementofanarrayCPU0CPU1CPU

2CPU

3WhenthelastCPUisdone,thesharedlocationhasthemaximumvalue.2023/4/1531編輯pptTask(Functional)DecompositionFirst,dividetasksamongprocessors劃分的對(duì)象是計(jì)算，將計(jì)算劃分為不同的任務(wù)，其出發(fā)點(diǎn)不同于域分解Second,decidewhichdataelementsaregoingtobeaccessed(readand/orwritten)bywhichprocessors劃分后，研究不同任務(wù)所需的數(shù)據(jù)。如果這些數(shù)據(jù)不相交的，則劃分是成功的；如果數(shù)據(jù)有相當(dāng)?shù)闹丿B，意味著要重新進(jìn)行域分解和功能分解；Example:Event-handlerforGUIOneprocessormaybewatchingthekeyboardandmousewhileanotherprocessorperformstheactivityrelatedtoaprevioususeraction.2023/4/1532編輯pptTaskDecompositionf()s()r()q()h()g()Inataskdecompositionwelookforfunctionsthatcanexecutesimultaneously.Inthisdrawingthearrowsrepresenttheprecedenceconstraintsamongthefunctions.2023/4/1533編輯pptTaskDecompositionf()s()r()q()h()g()CPU0CPU2CPU

1Question:Whyistherenopointinassigning“f”,“r”,and“s”todifferentCPUs?2023/4/1534編輯pptTaskDecompositionf()s()r()q()h()g()CPU0CPU2CPU1BluecirclesindicateactiveCPUs.2023/4/1535編輯pptTaskDecompositionf()s()r()q()h()g()CPU0CPU2CPU12023/4/1536編輯pptTaskDecompositionf()s()r()q()h()g()CPU0CPU2CPU12023/4/1537編輯pptTaskDecompositionf()s()r()q()h()g()CPU0CPU2CPU12023/4/1538編輯pptPipeliningSpecialkindoftaskdecomposition“Assemblyline”parallelismInapipelinedapplication,theoutputofeachfunctionistheinputtothenextfunction.Ifweareonlyinterestedinprocessingonedataset,thereisnoparallelism.thethroughputislimitedbythesloweststage.Soifallthestagesdon’trunatthesamespeed,it’sinefficient.Example:3DrenderingincomputergraphicsRasterizeClipProjectModelInputOutput2023/4/1539編輯pptProcessingOneDataSet(Step1)RasterizeClipProjectModelHereagraphicsrenderingcomputationcanbedividedintofourstages.Ifwewanttoprocessonlyonedataset,ittakesonestepforeachstage.2023/4/1540編輯pptProcessingOneDataSet(Step2)RasterizeClipProjectModel2023/4/1541編輯pptProcessingOneDataSet(Step3)RasterizeClipProjectModel2023/4/1542編輯pptProcessingOneDataSet(Step4)RasterizeClipProjectModelThepipelineprocesses1datasetin4stepsHereagraphicsrenderingcomputationcanbedividedintofourstages.Ifwewanttoprocessonlyonedataset,ittakesonestepforeachstage.2023/4/1543編輯pptProcessingTwoDataSets(Step1)RasterizeClipProjectModelCPU0CPU1CPU2CPU3每個(gè)CPU完成特定功能2023/4/1544編輯pptProcessingTwoDataSets(Time2)RasterizeClipProjectModel2023/4/1545編輯pptProcessingTwoDataSets(Step3)RasterizeClipProjectModel2023/4/1546編輯pptProcessingTwoDataSets(Step4)RasterizeClipProjectModel2023/4/1547編輯pptProcessingTwoDataSets(Step5)RasterizeClipProjectModelThepipelineprocesses2datasetsin5steps2023/4/1548編輯pptPipeliningFiveDataSets(Step1)Dataset0Dataset1Dataset2Dataset3Dataset4CPU0CPU1CPU2CPU32023/4/1549編輯pptPipeliningFiveDataSets(Step2)Dataset0Dataset1Dataset2Dataset3Dataset4CPU0CPU1CPU2CPU32023/4/1550編輯pptPipeliningFiveDataSets(Step3)Dataset0Dataset1Dataset2Dataset3Dataset4CPU0CPU1CPU2CPU32023/4/1551編輯pptPipeliningFiveDataSets(Step4)Dataset0Dataset1Dataset2Dataset3Dataset4CPU0CPU1CPU2CPU32023/4/1552編輯pptPipeliningFiveDataSets(Step5)Dataset0Dataset1Dataset2Dataset3Dataset4CPU0CPU1CPU2CPU32023/4/1553編輯pptPipeliningFiveDataSets(Step6)Dataset0Dataset1Dataset2Dataset3Dataset4CPU0CPU1CPU2CPU32023/4/1554編輯pptPipeliningFiveDataSets(Step7)Dataset0Dataset1Dataset2Dataset3Dataset4CPU0CPU1CPU2CPU32023/4/1555編輯pptPipeliningFiveDataSets(Step8)Dataset0Dataset1Dataset2Dataset3Dataset4CPU0CPU1CPU2CPU3Question:Howmuchfasteristhepipelinedcomputationthanasequentialcomputation?Answer:Ittook8stepstopro