1、第九章 并行計(jì)算機(jī)系統(tǒng)的程序設(shè)計(jì)第一節(jié) 并行計(jì)算機(jī)系統(tǒng)的數(shù)據(jù)通信第二節(jié) Cache與存儲器的數(shù)據(jù)一致性第三節(jié) 多處理機(jī)的同步第四節(jié) 并行程序設(shè)計(jì)模型1第一節(jié) 并行計(jì)算機(jī)系統(tǒng)的數(shù)據(jù)通信數(shù)據(jù)包尋徑信息序號數(shù)據(jù)內(nèi)容校驗(yàn)位協(xié)議號時(shí)間戳存儲轉(zhuǎn)發(fā)store-and-forward電路交換circuit switching虛擬切換virtual cut-through蟲孔尋徑wormhole2MPIMessage passing interface 用于多處理器系統(tǒng)和集群系統(tǒng)進(jìn)程通過調(diào)用庫函數(shù)進(jìn)行消息收發(fā)通信支持異構(gòu)計(jì)算標(biāo)準(zhǔn)的消息傳遞函數(shù)庫點(diǎn)到點(diǎn)通信函數(shù)群集通信函數(shù)不是一種語言消息傳遞機(jī)制點(diǎn)對點(diǎn)通信群集通信

2、3MPI的點(diǎn)對點(diǎn)通信機(jī)制發(fā)送操作模型標(biāo)準(zhǔn)的同步或緩存的（取決于實(shí)現(xiàn)）緩存的把發(fā)送緩存復(fù)制到緩存后返回同步的緩存被接收方讀取后返回就緒的在接收方就緒時(shí)啟動(dòng)發(fā)送（啟動(dòng)發(fā)送后即返回）發(fā)送/接收操作模型阻塞的等到消息復(fù)制到緩存后返回非阻塞的啟動(dòng)發(fā)送/接收后即返回4MPI點(diǎn)對點(diǎn)通信函數(shù)例子MPI_INIT啟動(dòng)MPI計(jì)算MPI_FINALIZE結(jié)束MPI計(jì)算MPI_COMM_SIZE確定進(jìn)程數(shù)MPI_COMM_RANK確定自己的進(jìn)程號MPI_SEND標(biāo)準(zhǔn)地發(fā)送一條消息MPI_BSEND發(fā)送一條緩存的消息MPI_SSEND發(fā)送一條同步的消息MPI_RESEND發(fā)送一條就緒的消息MPI_ISEND標(biāo)準(zhǔn)地發(fā)送一

3、條非阻塞消息MPI_IBSEND發(fā)送一條緩存的非阻塞消息MPI_ISSEND發(fā)送一條同步的非阻塞消息MPI_RESEND發(fā)送一條就緒的非阻塞消息MPI_RECV標(biāo)準(zhǔn)地接收一條消息MPI_IRECV非阻塞地接收一條消息MPI_BCAST廣播一條消息MPI_WAIT等待發(fā)送/接收完成MPI_TEST測試發(fā)送/接收是否完成5MPI的聚合通信機(jī)制同步方式同步發(fā)送和阻塞接收所有進(jìn)程都完成調(diào)用時(shí)返回（屏障同步）特異方式 distinguished一對多通信散播廣播多對一通信歸約求最大值、最小值、總和、乘積等收集6MPI群集通信函數(shù)例子MPI_Bcast一對多廣播同樣的消息MPI_Gather多對一收集各個(gè)

4、進(jìn)程的消息MPI_Allgather全局收集MPI_Scatter一對多散播不同的消息MPI_Alltoall每個(gè)進(jìn)程給所有其他進(jìn)程發(fā)送一個(gè)消息每個(gè)進(jìn)程從所有其他進(jìn)程接收一個(gè)消息MPI_Reduce多對一歸約MPI_Reduce_scatter歸約并散播MPI_Barrier屏障同步7第一節(jié) 并行計(jì)算機(jī)系統(tǒng)的數(shù)據(jù)通信1. 存儲轉(zhuǎn)發(fā)store-and-forward問題：延遲大，緩存多8第一節(jié) 并行計(jì)算機(jī)系統(tǒng)的數(shù)據(jù)通信2. 電路交換circuit switching問題：沖突多，利用率低9第一節(jié) 并行計(jì)算機(jī)系統(tǒng)的數(shù)據(jù)通信3. 虛擬切換virtual cut-through問題：緩存多flits1

5、0第一節(jié) 并行計(jì)算機(jī)系統(tǒng)的數(shù)據(jù)通信4. 蟲孔尋徑wormhole問題：死鎖和活鎖11第一節(jié) 并行計(jì)算機(jī)系統(tǒng)的數(shù)據(jù)通信蟲孔尋徑與存儲轉(zhuǎn)發(fā)的比較12例9-1設(shè)多處理器計(jì)算機(jī)中兩個(gè)結(jié)點(diǎn)之間的距離為10，一個(gè)處理器發(fā)出的消息包含100個(gè)片段（flit），假設(shè)每個(gè)時(shí)鐘周期可以在連路上傳遞一個(gè)片段，問在存儲轉(zhuǎn)發(fā)和蟲孔尋徑兩種方式下消息的傳遞最快分別需要花費(fèi)多少時(shí)間？解：存儲轉(zhuǎn)發(fā)方式，消息傳遞時(shí)間為10*100=1000個(gè)時(shí)鐘周期蟲孔尋徑方式，消息的第一個(gè)片段在網(wǎng)絡(luò)上的傳遞時(shí)間為10個(gè)時(shí)鐘周期，后99個(gè)片段增加99個(gè)時(shí)鐘周期，共109個(gè)時(shí)鐘周期。13第二節(jié) Cache與存儲器的數(shù)據(jù)一致性共享存儲器多處理機(jī)系

6、統(tǒng)的問題訪存沖突與數(shù)據(jù)一致性數(shù)據(jù)多個(gè)副本之間的相同性14數(shù)據(jù)的一致性類型串行一致性弱化一致性處理機(jī)一致性松散一致性15數(shù)據(jù)一致性串行一致性sequential consistency處理機(jī)P對于存儲單元X的寫操作之后進(jìn)行的讀操作，其間如果沒有其它處理機(jī)對X進(jìn)行寫訪問，則總是返回由P寫入的數(shù)值。在一個(gè)處理機(jī)P1對于單元X進(jìn)行寫操作之后，另一處理機(jī)P2對于單元X的讀操作只要兩者足夠分離并且沒有其它對于X的寫操作發(fā)生，就能夠返回P1寫入的數(shù)值。對于同一單元的寫操作是順序進(jìn)行的，即兩個(gè)處理機(jī)對于相同單元進(jìn)行的寫操作的順序從任何處理機(jī)看都相同。如果數(shù)值1和2依次寫入一個(gè)位置，處理機(jī)不可能先讀得2，再讀得

7、1。16數(shù)據(jù)一致性弱化一致性weak consistency程序通過同步操作強(qiáng)調(diào)一致性，使得在這些同步點(diǎn)上數(shù)據(jù)保持一致，而不要求數(shù)據(jù)隨時(shí)都是一致的。處理機(jī)一致性processor consistency每個(gè)處理機(jī)發(fā)出的寫操作被其它處理機(jī)看到的都保持原順序，但兩個(gè)不同處理機(jī)的寫操作順序可被其他處理機(jī)以不同的順序看到。松散一致性release consistency采用acquire-release同步操作使得數(shù)據(jù)保持一致，從而減少對硬件一致性處理的要求。17數(shù)據(jù)一致性的實(shí)現(xiàn)軟件方法編譯分析避免cache共享數(shù)據(jù)總線監(jiān)測各cache設(shè)置監(jiān)測部件MESI協(xié)議目錄表法全映射有限目錄鏈?zhǔn)侥夸汼CI18總

8、線監(jiān)測所有cache不斷監(jiān)測總線上的每一個(gè)地址總線使得寫操作變成串行的Cache 失效時(shí)需要確定數(shù)據(jù)塊的位置write invalidate protocol invalidates other copies on a write.多次寫操作時(shí)只需一次invalidatewrite update or write broadcast protocolupdate all the cached copies of a data item when it is written讀操作的命中率高cpu1cpu2cache1cache2Mainmemory19MESI協(xié)議20數(shù)據(jù)一致性的實(shí)現(xiàn)目錄表法鏈?zhǔn)?/p>

9、目錄SCIscalable coherence interface IEEE 1596-199221數(shù)據(jù)一致性對cache性能的影響影響cache性能的因素單個(gè)處理器cache失效的數(shù)據(jù)傳輸數(shù)據(jù)通信引起的傳輸導(dǎo)致invalidations和后繼cache失效一致性失效處理機(jī)數(shù)量Cache容量塊大小22數(shù)據(jù)一致性對cache性能的影響一致性失效真共享失效true sharing misses 由cache一致性操作的通信引起對共享數(shù)據(jù)的第一個(gè)寫操作引起invalidation偽共享失效false sharing misses 由每個(gè)cache塊只有一個(gè)有效位引起一個(gè)塊中其他數(shù)據(jù)的寫操作引起cac

10、he塊讀操作的失效Cache塊是共享的，但是數(shù)據(jù)字并沒有共享23數(shù)據(jù)一致性對cache性能的影響一致性失效的例子假定數(shù)據(jù)字x1和x2在同一個(gè)數(shù)據(jù)塊中數(shù)據(jù)塊在 P1和P2之間共享假定以下事件序列24第三節(jié) 多處理機(jī)的同步多線程并行程序設(shè)計(jì)面臨的挑戰(zhàn)同步給線程執(zhí)行順序施加約束的強(qiáng)化機(jī)制影響程序的正確性和性能可能導(dǎo)致死鎖通信線程間的數(shù)據(jù)傳遞負(fù)載平衡線程之間執(zhí)行時(shí)間的平衡可伸縮性線程數(shù)量增加的挑戰(zhàn)25Issues in MIMD multiprocessors architectures多線程程序運(yùn)行中的問題Data racesUncertainty of data access orderSynch

11、ronizationCost of data access orderThread stallsForgetting unlock of mutexDead locksUnlimited processor stallFalse sharingSlowdown processors26并行程序設(shè)計(jì)面臨的挑戰(zhàn)數(shù)據(jù)競爭數(shù)據(jù)相關(guān)性險(xiǎn)象以下兩個(gè)if語句的表達(dá)式可能都為真嗎？27數(shù)據(jù)競爭之二28數(shù)據(jù)競爭之三if (list-next = NULL) insert(list-next, node1)if (list-next = NULL) insert(list-next, node2)node2nod

12、e129數(shù)據(jù)競爭的解決變量局部化將變量改為線程局部的如將全局和分解為部分和用臨界區(qū)控制共享變量的訪問通過鎖、信號量等實(shí)現(xiàn)每個(gè)共享數(shù)據(jù)用一把鎖互斥機(jī)制30同步機(jī)制臨界區(qū)critical section訪問共享數(shù)據(jù)的程序段在某段時(shí)間內(nèi)僅允許一定數(shù)目的線程訪問的一段代碼大多數(shù)情況下一次只有一個(gè)線程能夠進(jìn)入同一個(gè)臨界區(qū)可采用互斥機(jī)制實(shí)現(xiàn)31同步機(jī)制共享存儲器型多處理機(jī)信號量PV操作互斥機(jī)制鎖條件變量屏障柵欄消息傳遞型多處理機(jī)消息的發(fā)送和接收32信號量通過PV操作在線程間傳遞同步信息P操作將一個(gè)變量減1減后的變量小于0時(shí)線程被阻塞V操作將一個(gè)變量加1加后的變量大于或等于0時(shí)釋放一個(gè)線程變量初始化為0或1

13、互斥量MutexPV操作都是原子的不可中斷的操作用于保護(hù)共享的資源生產(chǎn)者-消費(fèi)者問題33鎖兩個(gè)基本的原子操作Acquire原子地等待鎖的狀態(tài)變成打開的狀態(tài)將打開的鎖狀態(tài)變成關(guān)閉的狀態(tài)這時(shí)該線程獲得了鎖Release原子地將鎖的狀態(tài)從關(guān)閉狀態(tài)變成打開的狀態(tài)這時(shí)線程釋放了鎖34鎖的類型互斥量用PV操作上鎖和解鎖有阻塞可以加上時(shí)間屬性遞歸鎖可以遞歸地獲得的鎖用于遞歸程序讀寫鎖多讀單寫鎖限制寫操作只能由一個(gè)線程執(zhí)行 用于對共享變量的讀寫操作自旋鎖非阻塞的鎖用于多處理機(jī)系統(tǒng)和多核系統(tǒng)35阻塞型鎖機(jī)制的問題 優(yōu)先級的顛倒priority inversion當(dāng)一個(gè)低優(yōu)先級的線程占用了一個(gè)鎖之后，需要同一個(gè)鎖

14、的高優(yōu)先級線程就只能等待。護(hù)航Convoying當(dāng)一個(gè)線程擁有一個(gè)鎖而被切換出去時(shí)其他的線程如果需要同一個(gè)鎖的話都不能運(yùn)行下去其他線程都圍著擁有鎖的線程團(tuán)團(tuán)轉(zhuǎn)死鎖Deadlock鎖的擁有和依賴關(guān)系形成一個(gè)環(huán)36死鎖及其解決死鎖的原因?qū)Y源（鎖）的訪問是獨(dú)占的線程在已經(jīng)持有一個(gè)資源時(shí)繼續(xù)請求其他資源所有線程都不放棄已經(jīng)持有的資源線程對資源的請求形成一個(gè)環(huán)解決方法復(fù)制需要獨(dú)占訪問的資源 按照一定的順序獲取資源有序嵌套無法獲取其他資源時(shí)放棄已持有的資源 調(diào)用構(gòu)件時(shí)避免使用鎖37條件變量基于信號量機(jī)制但操作不涉及存儲的數(shù)值等待的線程被阻塞條件滿足時(shí)才被喚醒而不是循環(huán)等待滿足條件時(shí)喚醒其他協(xié)作的線程三種

15、操作等待發(fā)信號廣播38柵欄與屏障柵欄fence通過指令實(shí)現(xiàn)保證存儲器操作的一致性保證所有在柵欄之前的訪存操作完成在此之前停下所有在柵欄之后的訪存操作屏障barrier線程執(zhí)行的協(xié)調(diào)機(jī)制通過同步機(jī)制實(shí)現(xiàn)運(yùn)行的線程必須等待所有的線程都運(yùn)行到指定同步點(diǎn)然后各線程才繼續(xù)下一步的運(yùn)行需要對到達(dá)的線程進(jìn)行原子的計(jì)數(shù)操作39同步操作中的硬件原語原子交換atomic exchange實(shí)現(xiàn)鎖測試并設(shè)置test-and-set實(shí)現(xiàn)鎖讀取并加1fetch-and-increment實(shí)現(xiàn)屏障讀取并更新test-and-update實(shí)現(xiàn)PV操作40原子交換將一個(gè)寄存器的數(shù)值與一個(gè)存儲器中的數(shù)值進(jìn)行交換難以在并行機(jī)中實(shí)現(xiàn)

16、it requires both a memory read and a write in a single, uninterruptible instructionhardware cannot allow any other operations between the read and the write without deadlockAB41原子交換解決方案用兩條指令實(shí)現(xiàn)鏈接裝載load linked條件存儲store conditional返回一個(gè)數(shù)值表示其存儲操作是否成功兩條指令按順序執(zhí)行如果鏈接裝載指令指定的存儲單元在對應(yīng)的條件存儲指令執(zhí)行之間被改變，則存儲指令執(zhí)行時(shí)失敗。如果

17、處理機(jī)在這兩條指令之間進(jìn)行了上下文交換，則該條件存儲指令也將失敗。42派生原語1.原子交換 exch R4,0(R1)try: mov R3,R4;move exchange value from R4 to R3ll R2,0(R1);load linkedsc R3,0(R1);store conditionalbeqz R3,try;branch store failesmov R4,R2;put load value in R4宏指令macroinstructionR3BR4R243派生原語2. 讀取并加1：try: ll R2,0(R1);load linkedaddi R2,R2,

18、#1;incrementsc R2,0(R1);store conditionalbeqz R2,try;branch store failsR2BR2+144派生原語3. 轉(zhuǎn)鎖spin lock處理機(jī)用循環(huán)方法試圖得到的鎖沒有cache一致性機(jī)制時(shí)li R2,#1;load immediatelockit: exch R2,0(R1);atomic exchangebnez R2,lockit;already locked?有cache一致性機(jī)制時(shí)lockit: lw R2,0(R1);load of lockbnez R2,lockit;not available-spinli R2,#1

19、;load locked valueexch R2,0(R1);swapbnez R2,lockit;branch if lock wasnt 01L45派生原語采用鏈接裝載/條件存儲實(shí)現(xiàn)轉(zhuǎn)鎖lockit: ll R2,0(R1);load linkedbnez R2,lockit;not available-spinli R2,#1;locked valuesc R2,0(R1);storebeqz R2,lockit;branch if store failes1BR246派生原語屏障同步barrier強(qiáng)制所有的線程等待直到所有的線程都到達(dá)屏障時(shí)釋放所有的線程用一個(gè)計(jì)數(shù)器對到達(dá)的線程計(jì)數(shù)

20、(Gather階段)用一個(gè)信號釋放所有的線程 (release 階段)用兩個(gè)自旋鎖實(shí)現(xiàn)一個(gè)用于保護(hù)計(jì)數(shù)器一個(gè)用于鎖住線程release47派生原語屏障同步的實(shí)現(xiàn)lock (counterlock);/* ensure update atomic */if (count=0) release=0;/* first arrival reset release */count = count +1;/* count arrivals */unlock(counterlock);/* release lock */if (count=total) /* all arrived */ count = 0

21、; /* reset counter */ release=1;/* release processes */else /* more to come */ spin(release=1);/* wait for arrivals */48派生原語問題屏障可能循環(huán)使用從屏障離開的線程可能再次進(jìn)入屏障一個(gè)線程可能在另一個(gè)線程離開屏障之前又進(jìn)入屏障代碼的bugrelease49派生原語解決方案對離開的線程計(jì)數(shù)不允許線程在其他線程都離開上一個(gè)屏障之前又進(jìn)入屏障從而又初始化屏障傳感反相屏障sense-reversing使用線程局部變量初始化為1交替地等待1和0release50派生原語屏障同步的實(shí)現(xiàn)傳

22、感反相屏障local_sense =! local_sense; /*toggle local_sense*/lock (counterlock); /* ensure update atomic */count=count+1; /* count arrivals */if (count=total) /* all arrived */count=0; /* reset counter */release=local_sense; /* release processes */unlock (counterlock); /* unlock */spin (release=local_sens

23、e); /*wait for signal*/第一個(gè)到達(dá)屏障的線程并不改變r(jià)elease的值51同步操作的性能問題Contention for the lock(2i+1) = n2+2n鎖變量訪問的串行化大大增加完成同步操作的時(shí)間解決方案增量資源或分解資源如散列表的分割指數(shù)退避exponential backoff訪問等待時(shí)間以指數(shù)增加防止活鎖隊(duì)列鎖鎖變量釋放時(shí)通知下一個(gè)線程組合樹樹中每個(gè)結(jié)點(diǎn)組合k個(gè)線程的同步將對一個(gè)變量的競爭按樹形結(jié)構(gòu)分散52同步操作的性能問題指數(shù)等待53同步操作的性能問題組合樹struct node /* a node in the combining tree */

24、int counterlock; /* lock for this node */ int count; /* counter for this node */ int parent; /* parent in the tree = 0.P-1 except for root */;struct node tree 0.P1; /* the tree of nodes */int local_sense; /* private per processor */int release; /* global release flag */54同步操作的性能問題組合樹/* function to i

25、mplement barrier */barrier (int mynode, int local_sense) lock (treemynode.counterlock); /* protect count */treemynode.count=treemynode.count+1;/* increment count */if (treemynode.count=k) /* all arrived at mynode */if (treemynode.parent =0) barrier(treemynode.parent); /* recursive call */ elsereleas

26、e = local_sense;treemynode.count = 0; /* reset for the next time */unlock (treemynode.counterlock); /* unlock */spin (release=local_sense); /* wait */;/* code executed by a processor to join barrier */local_sense =! local_sense;barrier (mynode);55第四節(jié) 并行程序設(shè)計(jì)模型并行化程序設(shè)計(jì)方法向量化開發(fā)數(shù)據(jù)并行性多線程化開發(fā)線程級并行性線程優(yōu)化技術(shù)線程險(xiǎn)象

27、檢測技術(shù)并行化程序設(shè)計(jì)的必要性并行機(jī)的普及56向量化與包裝字16x bytes8x words4x dwords2x qwords1x dqword2x doublesMMX*SSESSE2SSE357向量化與包裝字標(biāo)量運(yùn)算128-bit RegistersA0B0C0+A1B1C1not usednot usednot usednot usednot usednot usednot usednot usednot usedfor (i=0;i=MAX;i+) ci=ai+bi;58向量化與包裝字向量化運(yùn)算128-bit RegistersA3A2B3B2C3C2+A1A0B1B0C1C0+f

28、or (i=0;i=MAX;i+) ci=ai+bi;59基于編譯的向量化處理器相關(guān)描述UseMac*Linux*Windows*Generate instructions and optimize for Intel Pentium 4 compatible processors including MMX, SSE and SSE2. WDoes not apply-xW/QxWGenerate instructions and optimize for Intel processors with SSE3 capability including Core Duo. These proc

29、essors support SSE3 as well as MMX,SSE and SSE2. PVector-ization occurs by default-xP,-axP/QxP/QaxP60向量化可向量化的情況大部分可計(jì)數(shù)內(nèi)循環(huán)不可向量化的情況函數(shù)調(diào)用條件轉(zhuǎn)移嵌套循環(huán)中的外循環(huán)混合數(shù)據(jù)類型不同封裝格式數(shù)組下標(biāo)非均勻跨步不可計(jì)數(shù)循環(huán)循環(huán)變量上界不是常數(shù)表達(dá)式包含不可向量化的運(yùn)算如超越函數(shù)61多線程化可重入性共享變量的保護(hù)訪問順序保護(hù)互斥保護(hù)臨界區(qū)的保護(hù)線程安全性無死鎖無數(shù)據(jù)競爭62多線程化例1編譯器通常會將循環(huán)不變的讀操作移到循環(huán)之外，這樣讀操作就只會進(jìn)行一次，而不是每次迭代都執(zhí)行一

30、次。在多線程的情況下，這樣做會產(chǎn)生什么問題？for (i=0; i100; i+0) int x; x = GlobalX； . . . int x = GlobalX；for (i=0; i100; i+0) . . . 63多線程化例2指令調(diào)度時(shí)通常可以將一條load指令提到它前面的的一條與之不相關(guān)的store指令之前執(zhí)行，在多線程的情況下，這樣做會產(chǎn)生什么問題？64多線程化線程化的優(yōu)點(diǎn)創(chuàng)建速度較進(jìn)程快資源利用率高便于數(shù)據(jù)共享線程化的缺點(diǎn)增加程序設(shè)計(jì)的復(fù)雜性程序調(diào)試較難數(shù)據(jù)競爭、同步、死鎖65多線程并行程序設(shè)計(jì)方法任務(wù)劃分將一個(gè)任務(wù)劃分成多個(gè)并行子任務(wù)使得處理器負(fù)載平衡數(shù)據(jù)劃分將數(shù)據(jù)對象劃

31、分成多個(gè)并行子集提高訪存的效率以及cache的命中率 數(shù)據(jù)流劃分根據(jù)數(shù)據(jù)處理的過程劃分一個(gè)子任務(wù)的輸出是另一個(gè)子任務(wù)的輸入劃分的目標(biāo)負(fù)載平衡降低調(diào)度開銷、通信開銷和同步開銷66任務(wù)與線程任務(wù)task應(yīng)用級的計(jì)算單位單任務(wù)線程為每個(gè)任務(wù)動(dòng)態(tài)創(chuàng)建和終止創(chuàng)建和終止開銷問題大量線程時(shí)的開銷線程池預(yù)先創(chuàng)建的固定數(shù)量的線程與處理器數(shù)量匹配可完成多個(gè)任務(wù)應(yīng)用程序中動(dòng)態(tài)任務(wù)分配和調(diào)度線程中任意時(shí)刻只能運(yùn)行一個(gè)纖程 6711122333333333344445555555555555536679838338891107611多線程并行程序設(shè)計(jì)方法任務(wù)劃分的例子按顏色劃分按區(qū)域劃分68多線程并行程序設(shè)計(jì)方法線程（

32、數(shù)據(jù)流）劃分的例子建筑工程砌墻、鋸木、砌瓦、水電、粉刷存在相關(guān)性人力資源利用率問題69多線程并行程序設(shè)計(jì)方法數(shù)據(jù)劃分的例子批考卷流水并行負(fù)載平衡問題70多線程的執(zhí)行環(huán)境邏輯處理器操作系統(tǒng)看到的處理器資源硬件線程支持多線程的處理器核中的一個(gè)CU多核單線程處理器中的一個(gè)核一個(gè)單核單線程的處理器芯片71多線程的執(zhí)行硬件多線程每個(gè)線程運(yùn)行在不同邏輯處理器上優(yōu)先級相同硬件的通信開銷真正的并行執(zhí)行軟件多線程運(yùn)行在同一個(gè)邏輯處理器上OS動(dòng)態(tài)改變優(yōu)先級共享本地存儲器通信開銷小互斥容易解決72多線程與多處理器的映像操作系統(tǒng)實(shí)現(xiàn)動(dòng)態(tài)線程調(diào)度算法無法考慮應(yīng)用的特征應(yīng)用程序?qū)崿F(xiàn)需要由應(yīng)用程序員優(yōu)化調(diào)試通過線程映像屏蔽

33、向量位向量進(jìn)程映像屏蔽向量的子集需要?jiǎng)討B(tài)獲知邏輯處理器的數(shù)量需要區(qū)分不同的硬件環(huán)境超線程、多核、多芯片73多線程并行程序設(shè)計(jì)中的問題負(fù)載平衡挑戰(zhàn)：線程執(zhí)行時(shí)間的不確定性通過動(dòng)態(tài)線程調(diào)度解決線程的開銷創(chuàng)建、刪除、同步、通信適度的并行并行顆粒度死鎖Cache ping-pong74多線程并行程序設(shè)計(jì)方法將獨(dú)立的循環(huán)程序變成多線程并行執(zhí)行的線程可能改變相對執(zhí)行的進(jìn)度或順序要求不存在循環(huán)帶來的相關(guān)性將獨(dú)立的程序段變成多線程變串行為并行纖程（fiber）執(zhí)行一個(gè)任務(wù)創(chuàng)建開銷小應(yīng)用層可控75Win32線程APICreateThreadMyThreadStartCloseHandleWaitForSingl

34、eObjectWaitForMultipleObjectsCreateMutexReleaseMutexInitializeCriticalSectionDeleteCriticalSectionEnterCriticalSectionLeaveCriticalSectionCreateSemaphoreReleaseSemaphore76Win32線程APIConvertThreadToFiber GetFiberData CreateFiber fiberProc SwitchToFiber DeleteFiber GetCurrentFiber 77Example#include #in

35、clude const int numThreads = 4;DWORD WINAPI helloFunc(LPVOID arg ) printf(“Hello Threadn”); return 0; main() HANDLE hThreadnumThreads; for (int i = 0; i numThreads; i+) hThreadi = CreateThread(NULL, 0, helloFunc, NULL, 0, NULL ); WaitForMultipleObjects(numThreads, hThread,TRUE, INFINITE);78OpenMP編寫可

36、移植的多線程應(yīng)用程序的API提供與平臺無關(guān)的并行編程機(jī)制編譯指令 pragma編譯指示符 directive函數(shù)調(diào)用環(huán)境變量循環(huán)程序多線程化支持多線程間的同步和局部數(shù)據(jù)變量采用fork-join的執(zhí)行模式程序員不需要對線程的創(chuàng)建和刪除進(jìn)行編程程序員不需要對同步操作進(jìn)行詳細(xì)編程適用于共享存儲器的并行計(jì)算機(jī)#pragma omp parallel for for (i=0;iMAX;i+) Ai= c*Ai + Bi;線程79fork-join的執(zhí)行模式主線程 分裂出一組線程并行性逐漸增加串行程序中嵌入并行性Parallel RegionsMaster Thread80OpenMP的編譯指令par

37、allelforprivatesinglemasterreductionschedulesectionifbarrieratomicreductionchunk-size#pragma omp construct clause clause#pragma omp parallelThread1Thread2Thread3#pragma omp parallel block81Parallel for#pragma omp parallel for for ( i=0; inumPixels; i+) pGrayScalBitmapi = (unsigned BYTE) ( pRGBBitmap

38、i.red * 0.299 + pRGBBitmapi.green*0.587 + pRGBBitmapi.blue*0.114); 82Parallel for reductionsum = 0;for (i=0; i 100; i+)sum += arrayi;/ this variable needs to be shared to generate / the correct results, but private to avoid / race conditions from parallel executionsum = 0;#pragma omp parallel for re

39、duction(+:sum)for (i=0; i 100; i+)sum += arrayi;83Parallel section#pragma omp parallel sections #pragma omp section phase1(); #pragma omp section phase2(); #pragma omp section phase3();SerialParallel84OpenMP的線程調(diào)度算法靜態(tài)將循環(huán)程序的各個(gè)迭代劃分成相等大小的迭代束或者近似相等大小的迭代束每個(gè)迭代束包含大致相等的迭代數(shù)量動(dòng)態(tài)使用內(nèi)部的工作隊(duì)列將迭代束分配給各個(gè)線程線程空閑時(shí)從工作隊(duì)列中獲取

40、下一個(gè)迭代束運(yùn)行時(shí)迭代束的大小先比較大然后逐漸縮小在開始時(shí)減少調(diào)度時(shí)間，然后考慮負(fù)載平衡指導(dǎo)性的使用環(huán)境變量以指定三種調(diào)度方式中的哪一個(gè)用于調(diào)度85Parallel for scheduleFloat x1000, y1000;#pragma omp parallel for schedule(dynamic, 8) for (k=0; k1000; k+) xk=cos(a)*xk + sin(a)*yk 86并行程序的性能優(yōu)化并行程序的優(yōu)化分析程序的調(diào)用關(guān)系分析程序的關(guān)鍵調(diào)用路徑分析程序中的熱點(diǎn)執(zhí)行時(shí)間最長的函數(shù)分析線程負(fù)載平衡分析關(guān)鍵路徑87關(guān)鍵路徑多線程程序包含多個(gè)執(zhí)行流執(zhí)行流在同步點(diǎn)相關(guān)關(guān)鍵路徑是最長的執(zhí)行流Thread 1Thread 2Thread 3T0T1T2T3T4T5T6T7T8T9T10T11T12T13T14T15Acquire LTh