多核程序設(shè)計（曲冠南）2 并行計算基礎(chǔ)（字體修正版）

1、2小節(jié)小節(jié)章節(jié)章節(jié)重點內(nèi)容重點內(nèi)容2.0關(guān)于并行計算什么是并行計算，怎么并行計算2.1并行計算機(jī)體系結(jié)構(gòu)并行計算機(jī)體系結(jié)構(gòu)多級存儲體系，Cache，并行訪存模型。2.2并行計算模型并行計算模型同步并行計算和異步并行計算模型；PRAM，BSP，logP, C3模型2.3進(jìn)程復(fù)習(xí)進(jìn)程知識2.4線程復(fù)習(xí)線程知識2.5并行編程環(huán)境依據(jù)并行化粒度2.6編程語言與編譯器介紹幾種流行的并行編譯技術(shù)2.7并行計算性能評測并行計算性能評測三大定律，性能評測方法，程序性能優(yōu)化2.8常用并行數(shù)值算法常用并行數(shù)值算法從操作數(shù)的角度并行化2.9并行編譯器流分析、代碼優(yōu)化細(xì)粒度細(xì)粒度并行通常是在基本塊或循環(huán)級上通過并行化

2、或向量化編譯并行通常是在基本塊或循環(huán)級上通過并行化或向量化編譯器來開發(fā)的；器來開發(fā)的；中粒度并行一般要求由程序員和編譯器共同來開發(fā)；中粒度并行一般要求由程序員和編譯器共同來開發(fā)；粗粒度的并行性的開發(fā)則主要依賴于高效的操作系統(tǒng)和所用并行粗粒度的并行性的開發(fā)則主要依賴于高效的操作系統(tǒng)和所用并行算法的效率。算法的效率。在通信方面，在通信方面，共享變量的通信常用來支持細(xì)粒度和中粒度并行計算；共享變量的通信常用來支持細(xì)粒度和中粒度并行計算；消息傳遞的通信常用來支持中粒度和粗粒度并行計算。消息傳遞的通信常用來支持中粒度和粗粒度并行計算。一般而言，并行粒度越小，通信和調(diào)度的開銷也越大；粒度越大，一般而言，并

3、行粒度越小，通信和調(diào)度的開銷也越大；粒度越大，所開發(fā)的并行性的潛力也就越低，但是通信和調(diào)度的開銷也就越所開發(fā)的并行性的潛力也就越低，但是通信和調(diào)度的開銷也就越小。小。總之：總之：1011內(nèi)存模塊與節(jié)點分離內(nèi)存模塊與節(jié)點分離內(nèi)存模塊位于節(jié)點內(nèi)部內(nèi)存模塊位于節(jié)點內(nèi)部12131617More chancesEasy to be foundHard to be foundCould be occupied全相聯(lián) 直接映射組相聯(lián)Big hallCubicleClassroom212223242526P1P2PnI/OSM1SMm共享存儲器處理器（）系統(tǒng)互連總線 交叉開關(guān)多級,網(wǎng)絡(luò)2728LM1P1LM2

4、P2LMnPn互連網(wǎng)絡(luò)共享本地存儲模型29303132消 息 傳 遞 互 連 網(wǎng) 絡(luò)(網(wǎng) 絡(luò) ， 環(huán) 網(wǎng) ， 超 立 方 ，立 方 環(huán) 等 )PMPMMPMPMPMPMPPMPMPM.3334I/ONIC,DIR,RC系統(tǒng)互連網(wǎng)路MemP/CP/CI/ONIC,DIR,RCMemP/CP/C節(jié)點N節(jié)點 1總線或 交叉 開關(guān)總線或 交叉 開關(guān)353637383940424344454647484950515253545657585960616264pWWsWpWsSP/)1(11)1(pfppffffSWpWpfpWpfWfWWWpWWWWSOOOPSPS/) 1(1)1 (WWfSo/166程

5、 序 中 順 序 部 分 的 百 分 比f(c)0% 1% 2% 3% 4% 100%加速比SS1024=1024/(1+1023f)1024x91x48x31x24x1x WpWp Wp WpWp WpW1W1W1W1W1W1工作負(fù)載W處 理 器 數(shù)P (a)123456T1 T1 Tp Tp Tp Tp Tp Tp T1 T1 T1執(zhí)行時間T處 理 器 數(shù)P (b)T112345667686970PSSSSWWpWpWpWppWpWpWS/) p-f (p-p) f ( p -f) p ( f S 111WWfpfWWWpWWSOOPSPS/1171程 序 中 順 序 部 分 的 百 分

6、比f(c)S1024=1024-1023f0%1%2%3%4%1024x1014x 1004x993x983x加速比S 處 理 器 數(shù)P工作負(fù)載W (a)W1W1W1W1W1W1WpWpWpWpWpWp123456 TpT1T1T1T1T1T1執(zhí)行時間T處 理 器 數(shù)P (b)123456 Tp Tp Tp Tp Tp72 ppGffpGff/11 pWpGffWWpGffWS/11 73T1Tp執(zhí)行時間T處理器數(shù)P (b)T1T1T1T1T1TpTpTpTpTp處理器數(shù)P工作負(fù)載W (a)W1WpWpWpWpWpWpW1W1W1W1W112345612345675 微處理器的浮點峰值性能：C

7、PU內(nèi)部浮點乘加指令流水線的條數(shù)、每條流水線每個時鐘周期完成的浮點運(yùn)算次數(shù)、處理器主頻三者的乘積。 并行計算機(jī)的峰值性能得等于處理器峰值性能和處理器個數(shù)的乘積。 并行程序的實際浮點性能（衡量并行程序的絕對指標(biāo)）：總的浮點運(yùn)算次數(shù)和并行程序執(zhí)行時間的比值。 并行程序能否發(fā)揮并行計算機(jī)浮點峰值性能主要是看并行程序的實際浮點性能和并行計算機(jī)的峰值性能的比值。76TP Ci Di piTLrpii,.2 , 1piDOWiii,.2 , 1pCCipipiii1010maxTspCTNE TTTpDCCPEiiTiiTDDCC,pTTTpDCppTTTTsppPENEDCCCTpSE注釋： Sp為加速

8、比84對程序性能進(jìn)行評測的主要目的就是發(fā)現(xiàn)程序的性能瓶頸，對程序性能進(jìn)行評測的主要目的就是發(fā)現(xiàn)程序的性能瓶頸，實施有效的程序性能優(yōu)化。實施有效的程序性能優(yōu)化。878889000000000001000002000003000004000005000006000007FFFFFFFFFFFEFFFFFDFFFFFCM0M1M2M396979899 b0=a0*a0; c0=1/b0; b1=a1*a1; c1=1/b1; b2=a2*a2; c2=1/b2; 雖然因為雖然因為c0緊接著緊接著b0計算，讓計算的內(nèi)在含義計算，讓計算的內(nèi)在含義更明顯，也更符合通常的更明顯，也更符合通常的思維習(xí)慣，但對

9、于流水線思維習(xí)慣，但對于流水線來說效率極差。來說效率極差。 b0=a0*a0; b1=a1*a1; b2=a2*a2; c0=1/b0; c1=1/b1; c2=1/b2; 先把數(shù)組先把數(shù)組b計算出來，然后再計算出來，然后再計算數(shù)組計算數(shù)組c，此時，需要的，此時，需要的b數(shù)組數(shù)組中的數(shù)據(jù)都已經(jīng)計算出來了，就不中的數(shù)據(jù)都已經(jīng)計算出來了，就不會存在流水線停滯的問題。會存在流水線停滯的問題。1001051060001020304050607101112131415161720212223242526273031323334353637404142434445464750515253545556576

10、0616263646566677071727374757677aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa10810nkkjikijbac1, 11 , 10 , 11, 11 , 10 , 11, 01 , 00 , 01, 11 , 10 , 11, 11 , 10 , 11, 01 , 00 , 01, 11 , 10 , 11, 11 , 10 , 11, 01 , 00 , 0,)()()(nnnnnnnnnnnnnnnnnnnnijnnijnnijbbbbbbbbbaaaaaaaaacccccccccBACcCbBaA設(shè)jiABC109ENDDOENDDOENDDOENDDO110111112011011,TTTTppAAAABBBB,()()i jijCCA BTTif (if (i i !=p-1) then send( !=p-1) the