【大學(xué)課件】基于多核的并行程序設(shè)計(jì)

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

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就象一場百年罕見地強(qiáng)降雪，將奔騰系列CPU的性能高速公路永遠(yuǎn)地封死了。因此，以英特爾為首的CPU軍團(tuán)不得不另外找一條更寬的性能高速公路來繼續(xù)他們的CPU神話 另尋出路2022/8/205ppt課件多核處理器的基本架構(gòu)背景：隨著芯片制成工藝的不斷進(jìn)步，從體系結(jié)構(gòu)來看，傳統(tǒng)的處理器體系結(jié)構(gòu)技術(shù)已面臨瓶頸，晶體管集成度已經(jīng)過億，

3、很難通過提高主頻來提升性能；從應(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)品。2022/8/206ppt課件Front Side Bus多核處理器簡介什么是多核處理

4、器兩個(gè)或多個(gè)獨(dú)立運(yùn)行的內(nèi)核集成于同一個(gè)處理器上雙核處理器 =一個(gè)處理器上包含2個(gè)內(nèi)核Core0Core12022/8/207ppt課件多核處理器簡介為什么采用雙核雙核共享封裝和I/O時(shí),總成本下降封裝和測試占總成本的20%-50%, I/O通常占晶片面積的15-20%功耗成本性能單核多核主頻超過2GHz時(shí)功耗超過100W僅靠主頻驅(qū)動(dòng)平衡性能與功耗由主頻和每時(shí)鐘周期所執(zhí)行的指令數(shù)來實(shí)現(xiàn)2022/8/208ppt課件定義：片上多核處理器（Chip Multi-Processor,CMP）就是將多個(gè)計(jì)算內(nèi)核集成在一個(gè)處理器芯片中，從而提高計(jì)算能力。多核處理器的基本架構(gòu)2.片上多核處理器體系結(jié)構(gòu)分類：

5、按計(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)多核處理器的典范。2022/8/209ppt課件硬件結(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ù)，并通過連接核心的

6、總線進(jìn)行通信。優(yōu)點(diǎn)：結(jié)構(gòu)簡單、通信速度高。缺點(diǎn)：基于總線的結(jié)構(gòu)可擴(kuò)展性較差?；谄匣ミB的結(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)較大。2022/8/2010ppt課件多核挑戰(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)不大 原有大部分程序是串行的 需要很好

7、的并行編程模型和開發(fā)環(huán)境,挑戰(zhàn)很大 桌面軟件2022/8/2011ppt課件多核挑戰(zhàn)軟件開發(fā)并行程序設(shè)計(jì)為什么難？其根本原因是因?yàn)榇蠖鄶?shù)計(jì)算機(jī)和編程語言發(fā)明之初就是按照馮諾依曼理論進(jìn)行設(shè)計(jì)的。根據(jù)馮諾依曼的理論，CPU是按照程序指令，一條條取出來并順序執(zhí)行的。而在多核或者多CPU的計(jì)算機(jī)中，同時(shí)會(huì)有多條指令在執(zhí)行。 2022/8/2012ppt課件多核挑戰(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)等帶來很大

8、困難 。2022/8/2013ppt課件多核帶來的挑戰(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ì)。” 2022/8/2014ppt課件認(rèn)識(shí)并行計(jì)算2022/8/2015ppt課件What Is Parallel Computing?Attempt to speed s

9、olution of a particular task by1. Dividing task 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 solutions2022/8/2016ppt課件Why Parallel Compu

10、ting?“The free lunch is over.” Herb SutterWe want applications to execute fasterClock speeds no longer increasing exponentially10 GHz1 GHz100 MHz10 MHz1 MHz79 87 95 03 112022/8/2017ppt課件Ways of Exploiting ParallelismDomain decomposition(域分解)數(shù)據(jù)Task decomposition(任務(wù)分解)計(jì)算Pipelining(流水線)3者的結(jié)合2022/8/2018

11、ppt課件Domain Decomposition(域劃分)First, decide how data elements should be divided among processors劃分的對(duì)象是數(shù)據(jù)，可以是算法的輸入數(shù)據(jù)、中間處理數(shù)據(jù)和輸出數(shù)據(jù)Second, decide which tasks each processor should be doing劃分時(shí)考慮數(shù)據(jù)上的相應(yīng)操作；如果一個(gè)任務(wù)需要?jiǎng)e的任務(wù)中的數(shù)據(jù)，則會(huì)產(chǎn)生任務(wù)間的通訊Example: Vector additionadd two vectors of size 100,000 using two processor

12、s劃分方法，最佳是分成前后兩部分2022/8/2019ppt課件Domain DecompositionFind the largest element of an array2022/8/2020ppt課件Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3shared scalar variable that will hold the global maximum2022/8/2021ppt課件Domain DecompositionFind the largest element of

13、an arrayCPU 0CPU 1CPU 2CPU 32022/8/2022ppt課件Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 32022/8/2023ppt課件Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 32022/8/2024ppt課件Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2C

14、PU 32022/8/2025ppt課件Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 32022/8/2026ppt課件Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 32022/8/2027ppt課件Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3The first CPU copies

15、 the maximum value it found into the shared memory location.2022/8/2028ppt課件Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3The first CPU copies the maximum value it found into the shared memory location.2022/8/2029ppt課件Domain DecompositionFind the largest element of an a

16、rrayCPU 0CPU 1CPU 2CPU 32022/8/2030ppt課件Domain DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3When the last CPU is done, the shared location has the maximum value.2022/8/2031ppt課件Task (Functional) DecompositionFirst, divide tasks among processors劃分的對(duì)象是計(jì)算，將計(jì)算劃分為不同的任務(wù)，其出發(fā)點(diǎn)不同于域分解S

17、econd, decide which data elements are going to be accessed (read and/or written) by which processors劃分后，研究不同任務(wù)所需的數(shù)據(jù)。如果這些數(shù)據(jù)不相交的，則劃分是成功的；如果數(shù)據(jù)有相當(dāng)?shù)闹丿B， 意味著要重新進(jìn)行域分解和功能分解；Example: Event-handler for GUIOne processor may be watching the keyboard and mouse while another processor performs the activity related

18、 to a previous user action.2022/8/2032ppt課件Task 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.2022/8/2033ppt課件Task Decompositionf()s()r()q()h()g()CPU 0CP

19、U 2CPU 1Question: Why is there no point in assigning “f”, “r”, and “s” to different CPUs?2022/8/2034ppt課件Task Decompositionf()s()r()q()h()g()CPU 0CPU 2CPU 1Blue circles indicate active CPUs.2022/8/2035ppt課件Task Decompositionf()s()r()q()h()g()CPU 0CPU 2CPU 12022/8/2036ppt課件Task Decompositionf()s()r()

20、q()h()g()CPU 0CPU 2CPU 12022/8/2037ppt課件Task Decompositionf()s()r()q()h()g()CPU 0CPU 2CPU 12022/8/2038ppt課件PipeliningSpecial 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 pro

21、cessing 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 graphicsRasterizeClipProjectModelInputOutput2022/8/2039ppt課件Processing One Data Set (Step 1)RasterizeClipP

22、rojectModelHere 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.2022/8/2040ppt課件Processing One Data Set (Step 2)RasterizeClipProjectModel2022/8/2041ppt課件Processing One Data Set (Step 3)RasterizeClipProjectMode

23、l2022/8/2042ppt課件Processing 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.2022/8/2043ppt課件Processing Two Data Se

24、ts (Step 1)RasterizeClipProjectModelCPU0CPU1CPU2CPU3每個(gè)CPU完成特定功能2022/8/2044ppt課件Processing Two Data Sets (Time 2)RasterizeClipProjectModel2022/8/2045ppt課件Processing Two Data Sets (Step 3)RasterizeClipProjectModel2022/8/2046ppt課件Processing Two Data Sets (Step 4)RasterizeClipProjectModel2022/8/2047ppt課

25、件Processing Two Data Sets (Step 5)RasterizeClipProjectModelThe pipeline processes 2 data sets in 5 steps2022/8/2048ppt課件Pipelining Five Data Sets (Step 1)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32022/8/2049ppt課件Pipelining Five Data Sets (Step 2)Data set 0Data set 1Data s

26、et 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32022/8/2050ppt課件Pipelining Five Data Sets (Step 3)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32022/8/2051ppt課件Pipelining Five Data Sets (Step 4)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32022/8/2052ppt課件

27、Pipelining Five Data Sets (Step 5)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32022/8/2053ppt課件Pipelining Five Data Sets (Step 6)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32022/8/2054ppt課件Pipelining Five Data Sets (Step 7)Data set 0Data set 1Data set 2Data set 3Data set 4CPU 0CPU 1CPU 2CPU 32022/8/2055ppt課件Pipelining 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 computat