并行計(jì)算機(jī)的同步與通信課件

1、第6章 并行計(jì)算機(jī)的同步與通信計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)胡越明計(jì)算機(jī)系第6章 并行計(jì)算機(jī)的同步與通信計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)Agenda6.1 并行計(jì)算機(jī)系統(tǒng)的通信 6.2 Cache與存儲(chǔ)器數(shù)據(jù)一致性 6.3 并行計(jì)算機(jī)的同步 6.4 并行計(jì)算機(jī)程序設(shè)計(jì) Agenda6.1 并行計(jì)算機(jī)系統(tǒng)的通信 6.1 并行計(jì)算機(jī)系統(tǒng)的通信并行計(jì)算機(jī)對程序的要求代碼的可重入 并行線程之間的競態(tài)現(xiàn)象 線程之間對共享變量的不同的讀-寫和寫-寫訪問順序?qū)е虏煌某绦驁?zhí)行結(jié)果 源自線程間的數(shù)據(jù)相關(guān)性并行計(jì)算機(jī)的通信方式共享存儲(chǔ)器互連網(wǎng)絡(luò)的消息傳遞6.1 并行計(jì)算機(jī)系統(tǒng)的通信并行計(jì)算機(jī)對程序的要求共享存儲(chǔ)器通信共享變量最簡單的通信方式?jīng)]有

2、同步功能信號（signal）一個(gè)二進(jìn)制變量可以表示條件、狀態(tài)、鎖和其它同步信息不能傳遞數(shù)據(jù)內(nèi)容信箱固定格式的通信結(jié)構(gòu)通常包含一個(gè)標(biāo)志位在發(fā)送方和接收方之間起到同步的作用尋址和管理比較簡單，不夠靈活消息具有靈活格式的通信單位共享存儲(chǔ)器通信共享變量共享存儲(chǔ)器通信線程同步給線程執(zhí)行順序施加約束的機(jī)制控制線程執(zhí)行的相對順序建立在互斥機(jī)制的基礎(chǔ)上 互斥機(jī)制使得一次只有一個(gè)線程對共享變量進(jìn)行訪問以保證每個(gè)線程對于共享變量訪問的完整性常見的互斥機(jī)制鎖信號量臨界區(qū)共享存儲(chǔ)器通信線程同步共享存儲(chǔ)器通信鎖一種互斥變量一次只能被一個(gè)線程獲得信號量通過PV操作在線程間傳遞同步信息原子操作P操作將一個(gè)變量減1減后的變量

3、小于0時(shí)線程被阻塞V操作將一個(gè)變量加1加后的變量大于或等于0時(shí)釋放一個(gè)線程共享存儲(chǔ)器通信鎖共享存儲(chǔ)器通信臨界區(qū)短小的、不能被中斷的程序段進(jìn)入的線程數(shù)量是有限制的通常只允許一個(gè)線程進(jìn)入臨界區(qū)可以采用鎖機(jī)制來實(shí)現(xiàn)共享存儲(chǔ)器通信臨界區(qū)鎖兩個(gè)基本的原子操作Acquire原子地等待鎖的狀態(tài)變成打開的狀態(tài)將打開的鎖狀態(tài)變成關(guān)閉的狀態(tài)這時(shí)該線程獲得了鎖Release原子地將鎖的狀態(tài)從關(guān)閉狀態(tài)變成打開的狀態(tài)這時(shí)線程釋放了鎖鎖兩個(gè)基本的原子操作鎖的類型互斥量用PV操作上鎖和解鎖有阻塞可以加上時(shí)間屬性遞歸鎖可以遞歸地獲得的鎖用于遞歸程序讀寫鎖多讀單寫鎖限制寫操作只能由一個(gè)線程執(zhí)行 用于對共享變量的讀寫操作自旋鎖非

4、阻塞的鎖用于多處理機(jī)系統(tǒng)和多核系統(tǒng)鎖的類型互斥量阻塞型鎖機(jī)制的問題優(yōu)先級的顛倒priority inversion當(dāng)一個(gè)低優(yōu)先級的線程占用了一個(gè)鎖之后，需要同一個(gè)鎖的高優(yōu)先級線程就只能等待。護(hù)航Convoying當(dāng)一個(gè)線程擁有一個(gè)鎖而被切換出去時(shí)其他的線程如果需要同一個(gè)鎖的話都不能運(yùn)行下去其他線程都圍著擁有鎖的線程團(tuán)團(tuán)轉(zhuǎn)死鎖Deadlock鎖的擁有和依賴關(guān)系形成一個(gè)環(huán)阻塞型鎖機(jī)制的問題優(yōu)先級的顛倒priority invers死鎖及其解決死鎖的原因?qū)Y源（鎖）的訪問是獨(dú)占的線程在已經(jīng)持有一個(gè)資源時(shí)繼續(xù)請求其他資源所有線程都不放棄已經(jīng)持有的資源線程對資源的請求形成一個(gè)環(huán)解決方法復(fù)制需要獨(dú)占訪問的

5、資源 按照一定的順序獲取資源有序嵌套無法獲取其他資源時(shí)放棄已持有的資源 調(diào)用構(gòu)件時(shí)避免使用鎖死鎖及其解決死鎖的原因信號硬件信號一種黏滯性的邏輯電平一旦被設(shè)置就一直保持不變直到被清除如訪存完成、cache失效、時(shí)鐘信號可以表示為一個(gè)寄存器變量對于信號變量的讀操作清除這個(gè)信號 軟件信號表示為共享變量如進(jìn)程中止信號信號硬件信號互連網(wǎng)絡(luò)的消息傳遞通信方式 消息結(jié)點(diǎn)間通信的基本邏輯單位消息頭目標(biāo)結(jié)點(diǎn)號、源結(jié)點(diǎn)號、消息類型和消息長度等消息體通信數(shù)據(jù)互連網(wǎng)絡(luò)的消息傳遞通信方式 消息互連網(wǎng)絡(luò)的消息傳遞通信方式數(shù)據(jù)包數(shù)據(jù)傳輸?shù)奈锢韱挝粚叫畔⑿蛱枖?shù)據(jù)內(nèi)容校驗(yàn)位協(xié)議號時(shí)間戳存儲(chǔ)轉(zhuǎn)發(fā)store-and-forwar

6、d電路交換circuit switching虛擬切換virtual cut-through蟲孔尋徑wormhole互連網(wǎng)絡(luò)的消息傳遞通信方式數(shù)據(jù)包存儲(chǔ)轉(zhuǎn)發(fā)互連網(wǎng)絡(luò)的消息傳遞通信方式存儲(chǔ)轉(zhuǎn)發(fā)store-and-forward問題：延遲大，緩存多互連網(wǎng)絡(luò)的消息傳遞通信方式存儲(chǔ)轉(zhuǎn)發(fā)store-and-for互連網(wǎng)絡(luò)的消息傳遞通信方式電路交換circuit switching問題：沖突多，利用率低互連網(wǎng)絡(luò)的消息傳遞通信方式電路交換circuit switc互連網(wǎng)絡(luò)的消息傳遞通信方式虛擬切換virtual cut-through問題：緩存多flits互連網(wǎng)絡(luò)的消息傳遞通信方式虛擬切換virtual cu

7、t-t互連網(wǎng)絡(luò)的消息傳遞通信方式蟲孔尋徑wormhole問題：死鎖和活鎖互連網(wǎng)絡(luò)的消息傳遞通信方式蟲孔尋徑wormhole互連網(wǎng)絡(luò)的消息傳遞通信方式蟲孔尋徑與存儲(chǔ)轉(zhuǎn)發(fā)的比較互連網(wǎng)絡(luò)的消息傳遞通信方式蟲孔尋徑與存儲(chǔ)轉(zhuǎn)發(fā)的比較互連網(wǎng)絡(luò)的消息傳遞通信方式衡量指標(biāo)通信帶寬單位時(shí)間能夠傳輸?shù)臄?shù)據(jù)量取決于處理器的通信處理吞吐率、存儲(chǔ)器的吞吐率和互連網(wǎng)絡(luò)的傳輸帶寬通信延遲發(fā)送的時(shí)間開銷信號傳輸時(shí)間傳輸持續(xù)時(shí)間接收方的時(shí)間開銷 通信延遲隱藏能力通信時(shí)間與計(jì)算時(shí)間或者其他通信時(shí)間的重疊程度 互連網(wǎng)絡(luò)的消息傳遞通信方式衡量指標(biāo)例6-2 1個(gè)計(jì)算任務(wù)在單個(gè)核的計(jì)算機(jī)上運(yùn)行的啟動(dòng)時(shí)間為1秒，運(yùn)算時(shí)間為10秒，數(shù)據(jù)結(jié)果

8、匯總的時(shí)間為1秒。如果將該計(jì)算任務(wù)放在多核處理器的計(jì)算機(jī)上運(yùn)行，將運(yùn)算部分分解成多個(gè)線程并行執(zhí)行。（1）假如任務(wù)的啟動(dòng)和數(shù)據(jù)匯總操作不能并行執(zhí)行，運(yùn)算部分可以進(jìn)行任意的任務(wù)分解，任務(wù)之間的通信量可以忽略，也不考慮任務(wù)分解后存儲(chǔ)系統(tǒng)對性能的影響。問在處理器核的數(shù)量分別為2、4、8、16時(shí)的任務(wù)執(zhí)行時(shí)間和加速比。（2）上述情況下，假如每兩個(gè)處理器核之間的通信時(shí)間為0.1秒，每對處理器核的通信串行進(jìn)行，問在核的數(shù)量分別為2、4、8、16時(shí)的任務(wù)執(zhí)行時(shí)間和加速比。例6-2 1個(gè)計(jì)算任務(wù)在單個(gè)核的計(jì)算機(jī)上運(yùn)行的啟動(dòng)時(shí)間為1秒解：（1）任務(wù)在單個(gè)核的計(jì)算機(jī)上運(yùn)行時(shí)間為12秒；在雙核計(jì)算機(jī)上的運(yùn)行時(shí)間為1+

9、10/2+1 = 7秒，加速比為12/7 = 1.71；在4核計(jì)算機(jī)上的運(yùn)行時(shí)間為1+10/4+1 = 4.5秒，加速比為12/4.5 = 2.67；在8核計(jì)算機(jī)上的運(yùn)行時(shí)間為1+10/8+1 = 3.25秒，加速比為12/3.25 = 3.69；在16核計(jì)算機(jī)上的運(yùn)行時(shí)間為1+10/16+1 = 2.63秒，加速比為12/2.63 = 4.56。解：（1）任務(wù)在單個(gè)核的計(jì)算機(jī)上運(yùn)行時(shí)間為12秒；解：（2）任務(wù)在單個(gè)核的計(jì)算機(jī)上沒有通信時(shí)間，運(yùn)行時(shí)間為12秒；在雙核計(jì)算機(jī)上的通信時(shí)間為10.1，運(yùn)行時(shí)間為1+10/2+1+0.1 = 7.1秒，加速比為12/7.1 = 1.69；在4核計(jì)算機(jī)上

10、的通信時(shí)間為60.1=0.6，運(yùn)行時(shí)間為1+10/4+1+0.6 = 5.1秒，加速比為12/5.1 = 2.35；在8核計(jì)算機(jī)上的通信時(shí)間為280.1=2.8，運(yùn)行時(shí)間為1+10/8+1+2.8 = 6.05秒，加速比為12/6.05 = 1.98；在16核計(jì)算機(jī)上的通信時(shí)間為1200.1=12，運(yùn)行時(shí)間為1+10/16+1+12 = 14.63秒，加速比為12/14.63 = 0.82，即比單核計(jì)算機(jī)的計(jì)算時(shí)間更長。解：（2）任務(wù)在單個(gè)核的計(jì)算機(jī)上沒有通信時(shí)間，運(yùn)行時(shí)間為12解加速比單核2核4核8核16核無通信開銷11.712.673.694.56有通信開銷11.692.351.980.8

11、2解加速比單核2核4核8核16核無通信開銷11.712.673習(xí)題6習(xí)題66.2 Cache與存儲(chǔ)器數(shù)據(jù)一致性 共享存儲(chǔ)器多處理機(jī)系統(tǒng)的問題訪存沖突與數(shù)據(jù)一致性數(shù)據(jù)多個(gè)副本之間的相同性6.2 Cache與存儲(chǔ)器數(shù)據(jù)一致性 共享存儲(chǔ)器多處理機(jī)系統(tǒng)數(shù)據(jù)一致性的實(shí)現(xiàn)軟件方法編譯分析避免cache共享數(shù)據(jù)總線監(jiān)測各cache設(shè)置監(jiān)測部件MESI協(xié)議目錄表法全映射有限目錄鏈?zhǔn)侥夸汼CI數(shù)據(jù)一致性的實(shí)現(xiàn)軟件方法總線監(jiān)測所有cache不斷監(jiān)測總線上的每一個(gè)地址總線使得寫操作變成串行的Cache 失效時(shí)需要確定數(shù)據(jù)塊的位置write invalidate protocol invalidates other

12、copies on a write.write update or write broadcast protocolupdate all the cached copies of a data item when it is writtencpu1cpu2cache1cache2Mainmemory總線監(jiān)測所有cache不斷監(jiān)測總線上的每一個(gè)地址cpu1cp總線監(jiān)測寫無效方式多次寫操作時(shí)只需一次invalidate對于整個(gè)cache數(shù)據(jù)塊進(jìn)行 寫更新方式對于數(shù)據(jù)塊中的個(gè)別字進(jìn)行 讀操作的命中率高所有寫操作通過總線寫入所以相關(guān)的其他cache中寫操作的開銷較大總線監(jiān)測寫無效方式總線監(jiān)測每個(gè)處理器

13、的cache中設(shè)置一個(gè)監(jiān)測部件監(jiān)測總線上的寫操作 根據(jù)監(jiān)測的情況改變本地cache塊的狀態(tài)無效、修改、獨(dú)占、共享監(jiān)測條件主存中有一個(gè)單元被其他處理器所修改而這個(gè)單元在本地cache中也有一個(gè)副本對于寫更新方法擁有數(shù)據(jù)最新版本的cache需向其他cache提供數(shù)據(jù)塊內(nèi)容阻止其他處理器從共享存儲(chǔ)器的讀操作總線監(jiān)測每個(gè)處理器的cache中設(shè)置一個(gè)監(jiān)測部件MESI協(xié)議MESI協(xié)議例6-3 設(shè)單總線連接的兩個(gè)CPU中采用MESI協(xié)議進(jìn)行一致性操作，初始時(shí)某cache塊都在無效狀態(tài)，然后兩個(gè)CPU對該存儲(chǔ)塊分別進(jìn)行如下操作：CPU A讀，CPU B讀，CPU A寫，CPU B讀，CPU B寫試寫出每次訪問

14、后兩個(gè)塊的狀態(tài)變化情況。事件狀態(tài)A狀態(tài)B說明初始無效無效（I）數(shù)據(jù)未裝入CPU A讀獨(dú)占無效（I）讀操作cache失效，裝入CPU B讀共享共享（S）讀操作cache失效，裝入后共享CPU A寫修改無效（I）寫操作命中CPU B讀共享共享（S）讀操作失效，裝入CPU B寫無效修改（M）寫操作命中例6-3 設(shè)單總線連接的兩個(gè)CPU中采用MESI協(xié)議進(jìn)行一致例6-4 在一個(gè)共享L2 cache的雙核處理器芯片中，兩個(gè)L1 cache通過片內(nèi)總線與L2 cache連接，并采用MESI協(xié)議保持一致性。假設(shè)L1 cache各有4個(gè)塊，采用全相聯(lián)地址映像和LRU替換策略，每個(gè)塊的初始狀態(tài)都是無效的。在以下

15、讀訪問塊地址序列下，試畫出兩個(gè)L1 cache中塊的分配情況，并標(biāo)出每個(gè)塊的狀態(tài)。A核：1，0，6，7，8，0，1B核：0，2，7，8，9，2，0例6-4 在一個(gè)共享L2 cache的雙核處理器芯片中，兩個(gè)解解目錄表法全映射每個(gè)快表目錄項(xiàng)包含N個(gè)指示位段N為系統(tǒng)中處理器的個(gè)數(shù) 指示位段構(gòu)成一個(gè)位向量0表示相應(yīng)的處理器cache沒有該塊1表示有該塊 有限目錄每個(gè)快表目錄項(xiàng)包含固定數(shù)量的指示位段指示位段的位數(shù)與處理器數(shù)量無關(guān)鏈?zhǔn)侥夸浤夸洷矸ㄈ成淅?-5 設(shè)4個(gè)CPU的并行計(jì)算機(jī)中采用全映射的目錄表法進(jìn)行一致性操作，初始時(shí)某cache塊都在無效狀態(tài)，然后4個(gè)CPU對該存儲(chǔ)塊分別進(jìn)行如下操作：CPU

16、 0讀，CPU 1讀，CPU 2讀，CPU 1替換，CPU 0寫試寫出每次訪問后該塊的有效指示位段的變化情況，假設(shè)一致性操作采用寫無效策略。事件指示狀態(tài)位段初始0000CPU 0讀0001CPU 1讀0011CPU 2讀0111CPU 1替換0101CPU 0寫0001例6-5 設(shè)4個(gè)CPU的并行計(jì)算機(jī)中采用全映射的目錄表法進(jìn)行例6-6 在一個(gè)由2個(gè)CPU構(gòu)成的并行計(jì)算機(jī)中采用全映射的目錄表法進(jìn)行一致性操作。假設(shè)各CPU的cache都只有4個(gè)塊，采用全相聯(lián)地址映像和LRU替換策略，每個(gè)塊的初始狀態(tài)都是無效的。在以下讀訪問塊地址序列下，試畫出兩個(gè)L1 cache中塊的分配情況，并標(biāo)出每個(gè)塊的指示

17、狀態(tài)位段。CPU A：1，0，6，7，8，0，1CPU B：0，2，7，8，9，2，0例6-6 在一個(gè)由2個(gè)CPU構(gòu)成的并行計(jì)算機(jī)中采用全映射的目解解目錄表法鏈?zhǔn)侥夸泴⒛夸浄植嫉礁鱾€(gè)cache 每個(gè)cache的塊表中只需存放一個(gè)cache指針 單鏈或雙鏈SCI目錄表法鏈?zhǔn)侥夸洈?shù)據(jù)一致性對cache性能的影響影響cache性能的因素單個(gè)處理器cache失效的數(shù)據(jù)傳輸數(shù)據(jù)通信引起的傳輸導(dǎo)致invalidations和后繼cache失效一致性失效處理機(jī)數(shù)量Cache容量塊大小數(shù)據(jù)一致性對cache性能的影響影響cache性能的因素?cái)?shù)據(jù)一致性對cache性能的影響一致性失效真共享失效true shar

18、ing misses 由cache一致性操作的通信引起對共享數(shù)據(jù)的第一個(gè)寫操作引起invalidation偽共享失效false sharing misses 由每個(gè)cache塊只有一個(gè)有效位引起一個(gè)塊中其他數(shù)據(jù)的寫操作引起cache塊讀操作的失效Cache塊是共享的，但是數(shù)據(jù)字并沒有共享數(shù)據(jù)一致性對cache性能的影響一致性失效數(shù)據(jù)一致性對cache性能的影響一致性失效的例子假定數(shù)據(jù)字x1和x2在同一個(gè)數(shù)據(jù)塊中數(shù)據(jù)塊在 P1和P2之間共享假定以下事件序列數(shù)據(jù)一致性對cache性能的影響一致性失效的例子存儲(chǔ)器數(shù)據(jù)的一致性時(shí)間一致性（consistency） 一個(gè)寫操作寫入共享存儲(chǔ)器中的數(shù)值什么時(shí)

19、候能夠被讀到 串行一致性弱化一致性處理機(jī)一致性松散一致性存儲(chǔ)器數(shù)據(jù)的一致性時(shí)間一致性（consistency） 存儲(chǔ)器數(shù)據(jù)的一致性串行一致性sequential consistency處理機(jī)P對于存儲(chǔ)單元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，再讀

20、得1。存儲(chǔ)器數(shù)據(jù)的一致性串行一致性sequential consi存儲(chǔ)器數(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ù)保持一致，從而減少對硬件一致性處理的要求。存儲(chǔ)器數(shù)據(jù)的一致性弱化一致性weak consistencySCIscalab

21、le coherence interface IEEE 1596-1992支持鏈?zhǔn)侥夸洷矸p向鏈表 采用雙向鏈路 采用虛擬切換傳輸方式 支持大規(guī)模并行系統(tǒng) 不要求消息按順序提交 使用64位固定長度地址的分布式存儲(chǔ)器的尋址方案 高16位用于尋找結(jié)點(diǎn)低48位地址指定結(jié)點(diǎn)內(nèi)的存儲(chǔ)器地址 采用16位差分ECL信號鏈路 信號時(shí)鐘250MHz鏈路的數(shù)據(jù)傳輸帶寬為1GB/s SCIscalable coherence interfac習(xí)題11121314習(xí)題116.3 并行計(jì)算機(jī)的同步 同步機(jī)制并行系統(tǒng)中保持各并行程序正確運(yùn)行的控制機(jī)制建立在通信機(jī)制的基礎(chǔ)上 需要采用的硬件提供的機(jī)制來實(shí)現(xiàn) 硬件原語6.3

22、并行計(jì)算機(jī)的同步 同步機(jī)制硬件原語原子交換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操作硬件原語原子交換atomic exchange原子交換將一個(gè)寄存器的數(shù)值與一個(gè)存儲(chǔ)器中的數(shù)值進(jìn)行交換難以在并行機(jī)中實(shí)現(xiàn)要求存儲(chǔ)器讀寫操作在一條不可中斷的指令中完成硬件不能在讀寫操作之間響應(yīng)中斷AB原子交換將一個(gè)寄存器的數(shù)值與一個(gè)存儲(chǔ)器中的數(shù)值進(jìn)行交換AB原子交換解決方案用兩條指令實(shí)現(xiàn)鏈接裝載load linked條件存儲(chǔ)store conditional返回一個(gè)數(shù)值表示其

23、存儲(chǔ)操作是否成功兩條指令按順序執(zhí)行如果鏈接裝載指令指定的存儲(chǔ)單元在對應(yīng)的條件存儲(chǔ)指令執(zhí)行之間被改變，則存儲(chǔ)指令執(zhí)行時(shí)失敗。如果處理機(jī)在這兩條指令之間進(jìn)行了上下文交換，則該條件存儲(chǔ)指令也將失敗。原子交換解決方案原子交換原子交換的實(shí)現(xiàn) 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宏指令macroin

24、structionR3BR4R2原子交換原子交換的實(shí)現(xiàn) exch R4,0(R1)宏指令ma讀取并加1try: ll R2,0(R1);load linkedaddi R2,R2,#1;incrementsc R2,0(R1);store conditionalbeqz R2,try;branch store failsR2BR2+1讀取并加1try: ll R2,0(R1);load派生原語轉(zhuǎn)鎖spin lock處理機(jī)用循環(huán)方法試圖得到的鎖沒有cache一致性機(jī)制時(shí)li R2,#1;load immediatelockit: exch R2,0(R1);atomic exchangebnez

25、 R2,lockit;already locked?有cache一致性機(jī)制時(shí)lockit: lw R2,0(R1);load of lockbnez R2,lockit;not available-spinli R2,#1;load locked valueexch R2,0(R1);swapbnez R2,lockit;branch if lock wasnt 0派生原語轉(zhuǎn)鎖spin lock派生原語采用鏈接裝載/條件存儲(chǔ)實(shí)現(xiàn)轉(zhuǎn)鎖lockit: ll R2,0(R1);load linkedbnez R2,lockit;not available-spinli R2,#1;locked va

26、luesc R2,0(R1);storebeqz R2,lockit;branch if store failes1BR2派生原語采用鏈接裝載/條件存儲(chǔ)實(shí)現(xiàn)轉(zhuǎn)鎖1BR2派生原語屏障同步barrier強(qiáng)制所有的線程等待直到所有的線程都到達(dá)屏障時(shí)釋放所有的線程用一個(gè)計(jì)數(shù)器對到達(dá)的線程計(jì)數(shù) (Gather階段)用一個(gè)信號釋放所有的線程 (release 階段)用兩個(gè)自旋鎖實(shí)現(xiàn)一個(gè)用于保護(hù)計(jì)數(shù)器一個(gè)用于鎖住線程release派生原語屏障同步barrierrelease派生原語屏障同步的實(shí)現(xiàn)lock (counterlock);/* ensure update atomic */if (count=0)

27、 release=0;/* first arrival reset release */count = count +1;/* count arrivals */unlock(counterlock);/* release lock */if (count=total) /* all arrived */ count = 0; /* reset counter */ release=1;/* release processes */else /* more to come */ spin(release=1);/* wait for arrivals */派生原語屏障同步的實(shí)現(xiàn)派生原語問題屏障

28、可能循環(huán)使用從屏障離開的線程可能再次進(jìn)入屏障一個(gè)線程可能在另一個(gè)線程離開屏障之前又進(jìn)入屏障代碼的bugrelease派生原語問題release派生原語解決方案對離開的線程計(jì)數(shù)不允許線程在其他線程都離開上一個(gè)屏障之前又進(jìn)入屏障從而又初始化屏障傳感反相屏障sense-reversing使用線程局部變量初始化為1交替地等待1和0release派生原語解決方案release派生原語屏障同步的實(shí)現(xiàn)傳感反相屏障local_sense =! local_sense; /*toggle local_sense*/lock (counterlock); /* ensure update atomic */cou

29、nt=count+1; /* count arrivals */if (count=total) /* all arrived */count=0; /* reset counter */release=local_sense; /* release processes */unlock (counterlock); /* unlock */spin (release=local_sense); /*wait for signal*/第一個(gè)到達(dá)屏障的線程并不改變r(jià)elease的值派生原語屏障同步的實(shí)現(xiàn)第一個(gè)到達(dá)屏障的線程并不改變r(jià)elea同步操作的性能問題Contention for the

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

31、e */ 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 */同步操作的性能問題組合樹同步操作的性能問題組合樹/* function to implement barrier */barrier

32、(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 */ elserelease = local_sense;treemynode.

33、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);同步操作的性能問題組合樹事務(wù)存儲(chǔ)器 同步機(jī)制的硬件解決方案 非互鎖的機(jī)制使得系統(tǒng)能夠并行地執(zhí)行原子操作 事務(wù)鎖的作用范圍每個(gè)事務(wù)由一個(gè)線程推測性地執(zhí)行而不請求鎖 沒

34、有遇到?jīng)_突時(shí)提交否則事務(wù)將放棄（abort）進(jìn)行卷回（roll back）并重新開始 事務(wù)沒有成功提交之前不會(huì)對其它線程產(chǎn)生作用 事務(wù)存儲(chǔ)器 同步機(jī)制的硬件解決方案 事務(wù)存儲(chǔ)器事務(wù)由線程中的一組指令構(gòu)成串行性從其他線程看來不會(huì)有不同的執(zhí)行順序 原子性整體提交或者整體放棄 提交之前對其它線程看不到 事務(wù)存儲(chǔ)器事務(wù)同步與多線程 多線程的程序的問題數(shù)據(jù)競爭由各線程對共享數(shù)據(jù)讀-寫訪問和寫-寫訪問順序的不確定性引起同步同步機(jī)制會(huì)帶來的開銷線程停頓一個(gè)鎖未解開使等待這個(gè)鎖的線程停頓死鎖線程的無限期的停頓現(xiàn)象偽共享線程之間的非真正的數(shù)據(jù)共享而引起的相關(guān)性同步與多線程 多線程的程序的問題多線程的程序的問題數(shù)

35、據(jù)競爭數(shù)據(jù)相關(guān)性險(xiǎn)象以下兩個(gè)if語句的表達(dá)式可能都為真嗎？多線程的程序的問題數(shù)據(jù)競爭多線程的程序的問題線程1線程2原始代碼t = x;x = t+1;u = x;x = u+2;并行情況1t = x; /x is 0 x = t+1; /x is 1u = x;x = u+2; /x is 2并行情況2t = x;x = t+1; /x is 1u = x /x is 0 x = u+2 / x is 2并行情況3t = x; /x is 0 x = t+1; /x is 1u = x;x = u+2; /x is 3數(shù)據(jù)競爭之二多線程的程序的問題線程1線程2原始代碼t = x;u = x多線

36、程的程序的問題數(shù)據(jù)競爭之三if (list-next = NULL) insert(list-next, node1)if (list-next = NULL) insert(list-next, node2)node2node1多線程的程序的問題數(shù)據(jù)競爭之三if (list-next 數(shù)據(jù)競爭的解決變量局部化將變量改為線程局部的如將全局和分解為部分和用臨界區(qū)控制共享變量的訪問通過鎖、信號量等實(shí)現(xiàn)每個(gè)共享數(shù)據(jù)用一把鎖互斥機(jī)制數(shù)據(jù)競爭的解決變量局部化同步與多線程并行線程與臨界區(qū)critical section訪問共享數(shù)據(jù)的程序段在某段時(shí)間內(nèi)僅允許一定數(shù)目的線程訪問的一段代碼大多數(shù)情況下一次只有一

37、個(gè)線程能夠進(jìn)入同一個(gè)臨界區(qū)可采用互斥機(jī)制實(shí)現(xiàn)同步與多線程并行線程與臨界區(qū)critical section同步與多線程并行線程與屏障同步與多線程并行線程與屏障習(xí)題1618202122習(xí)題166.5 并行計(jì)算機(jī)程序的軟件支持 并行程序的概念 任務(wù)劃分將一個(gè)任務(wù)劃分成多個(gè)并行子任務(wù)使得處理器負(fù)載平衡數(shù)據(jù)劃分將數(shù)據(jù)對象劃分成多個(gè)并行子集提高訪存的效率以及cache的命中率 數(shù)據(jù)流劃分根據(jù)數(shù)據(jù)處理的過程劃分一個(gè)子任務(wù)的輸出是另一個(gè)子任務(wù)的輸入劃分的目標(biāo)負(fù)載平衡降低調(diào)度開銷、通信開銷和同步開銷6.5 并行計(jì)算機(jī)程序的軟件支持 并行程序的概念 并行程序的概念任務(wù)task應(yīng)用級的計(jì)算單位單任務(wù)線程為每個(gè)任務(wù)動(dòng)

38、態(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è)纖程 并行程序的概念任務(wù)task并行程序的概念線程化的優(yōu)點(diǎn)創(chuàng)建速度較進(jìn)程快資源利用率高便于數(shù)據(jù)共享線程化的缺點(diǎn)增加程序設(shè)計(jì)的復(fù)雜性程序調(diào)試較難數(shù)據(jù)競爭、同步、死鎖并行程序的概念線程化的優(yōu)點(diǎn)多線程的執(zhí)行硬件多線程每個(gè)線程運(yùn)行在不同邏輯處理器上優(yōu)先級相同硬件的通信開銷真正的并行執(zhí)行軟件多線程運(yùn)行在同一個(gè)邏輯處理器上OS動(dòng)態(tài)改變優(yōu)先級共享本地存儲(chǔ)器通信開銷小互斥容易解決多線程的執(zhí)行硬件多線程共享存儲(chǔ)器系統(tǒng)程序設(shè)計(jì)例子8個(gè)處理機(jī)，單總線連接su

39、mPn=0;for(i=8000*Pn;i8000*(Pn+1);i=i+1) sumPn=sumPn+Ai; /* sum the assigned areas */half=8; /* 8 processors in single-bus MIMD */do synch(); /* wait for completion of partial sums */ half=half/2; /* dividing line on two sums */ if(Pn1); /* exit with final sum in sum0 */其中synch()函數(shù)是一個(gè)屏障同步函數(shù)。共享存儲(chǔ)器系統(tǒng)程序

40、設(shè)計(jì)例子8個(gè)處理機(jī)，單總線連接分布消息傳遞型系統(tǒng)程序例子假設(shè)64個(gè)處理機(jī)，各處理機(jī)具有不同的地址空間。sum=0;for(i=0;i=half & Pnlimit) send(Pn%half,sum); if(Pn1); /* exit with final sum */分布消息傳遞型系統(tǒng)程序例子假設(shè)64個(gè)處理機(jī)，各處理機(jī)具有不同任務(wù)劃分對數(shù)據(jù)進(jìn)行劃分使得不同的子任務(wù)對不同的數(shù)據(jù)子集進(jìn)行處理對計(jì)算過程中的步驟進(jìn)行使得每個(gè)線程具有不同的程序代碼任務(wù)分解的一般方法根據(jù)數(shù)據(jù)運(yùn)算流程圖進(jìn)行 任務(wù)劃分對數(shù)據(jù)進(jìn)行劃分例6-8 對于數(shù)組運(yùn)算E = A*(B+C*D);其中，A、B、C和D都是具有n個(gè)元素的數(shù)

41、組，試畫出其數(shù)據(jù)流程圖，指出兩種子任務(wù)劃分方式。例6-8 對于數(shù)組運(yùn)算解橫向劃分縱向劃分解橫向劃分實(shí)現(xiàn)并行程序設(shè)計(jì)的方法 庫函數(shù)在串行程序的標(biāo)準(zhǔn)庫的基礎(chǔ)上增加支持并行操作的函數(shù)如MPI的消息傳遞庫和POSIX的Pthread多線程庫容易實(shí)現(xiàn)（不需要改變編譯程序）程序中的并行性沒有經(jīng)過編譯程序的檢查、分析、優(yōu)化新的語言構(gòu)造程序設(shè)計(jì)語言中增加新的構(gòu)造語句如Fortran 90中增加了向量運(yùn)算語句編譯程序可以進(jìn)行并行性檢查和優(yōu)化增加了編譯程序的復(fù)雜性。編譯指導(dǎo)在原有的語言中增加表達(dá)并行運(yùn)算的編譯指導(dǎo)語句并行編譯程序跟據(jù)指導(dǎo)語句將代碼轉(zhuǎn)換成在并行代碼如OpenMP介于上述兩種方法之間實(shí)現(xiàn)并行程序設(shè)計(jì)的

42、方法 庫函數(shù)線程操作函數(shù)線程的創(chuàng)建和消除分叉和匯集（fork-join）機(jī)制線程的啟動(dòng)和終止線程同步機(jī)制的建立和刪除線程通信機(jī)制的建立和刪除如MPI線程操作函數(shù)線程的創(chuàng)建和消除多線程并行程序設(shè)計(jì)方法將獨(dú)立的循環(huán)程序變成多線程并行執(zhí)行的線程可能改變相對執(zhí)行的進(jìn)度或順序要求不存在循環(huán)帶來的相關(guān)性將獨(dú)立的程序段變成多線程變串行為并行纖程（fiber）執(zhí)行一個(gè)任務(wù)創(chuàng)建開銷小應(yīng)用層可控多線程并行程序設(shè)計(jì)方法將獨(dú)立的循環(huán)程序變成多線程Win32線程APICreateThreadMyThreadStartCloseHandleWaitForSingleObjectWaitForMultipleObjects

43、CreateMutexReleaseMutexInitializeCriticalSectionDeleteCriticalSectionEnterCriticalSectionLeaveCriticalSectionCreateSemaphoreReleaseSemaphoreWin32線程APICreateThreadWin32線程APIConvertThreadToFiber GetFiberData CreateFiber fiberProc SwitchToFiber DeleteFiber GetCurrentFiber Win32線程APIConvertThreadToFiber

44、例#include #include 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

45、);例#include OpenMP 編寫可移植的多線程應(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ì)編程適用于共享存儲(chǔ)器的并行計(jì)算機(jī)#pragma omp parallel for for (i=0;iMAX;i+) Ai= c*Ai + Bi;線程OpenMP 編寫可移植的多線程應(yīng)用程序的API#pragmfork-join的執(zhí)行模式主線程 分裂出一組線程并行性逐漸增加串行程序中

46、嵌入并行性Parallel RegionsMaster Threadfork-join的執(zhí)行模式主線程 Parallel RegOpenMP的編譯指令parallelforprivatesinglemasterreductionschedulesectionifbarrieratomicreductionchunk-size#pragma omp construct clause clause#pragma omp parallelThread1Thread2Thread3#pragma omp parallel blockOpenMP的編譯指令parallel#pragma ompParal

47、lel for#pragma omp parallel for for ( i=0; inumPixels; i+) pGrayScalBitmapi = (unsigned BYTE) ( pRGBBitmapi.red * 0.299 + pRGBBitmapi.green*0.587 + pRGBBitmapi.blue*0.114); Parallel for#pragma omp parallParallel for reductionsum = 0;for (i=0; i 100; i+)sum += arrayi;/ this variable needs to be share

48、d to generate / the correct results, but private to avoid / race conditions from parallel executionsum = 0;#pragma omp parallel for reduction(+:sum)for (i=0; i 100; i+)sum += arrayi;Parallel for reductionsum = 0;Parallel section#pragma omp parallel sections #pragma omp section phase1(); #pragma omp

49、section phase2(); #pragma omp section phase3();SerialParallelParallel section#pragma omp paOpenMP的線程調(diào)度算法靜態(tài)將循環(huán)程序的各個(gè)迭代劃分成相等大小的迭代束或者近似相等大小的迭代束每個(gè)迭代束包含大致相等的迭代數(shù)量動(dòng)態(tài)使用內(nèi)部的工作隊(duì)列將迭代束分配給各個(gè)線程線程空閑時(shí)從工作隊(duì)列中獲取下一個(gè)迭代束運(yùn)行時(shí)迭代束的大小先比較大然后逐漸縮小在開始時(shí)減少調(diào)度時(shí)間，然后考慮負(fù)載平衡指導(dǎo)性的使用環(huán)境變量以指定三種調(diào)度方式中的哪一個(gè)用于調(diào)度OpenMP的線程調(diào)度算法靜態(tài)Parallel for scheduleFl

50、oat x1000, y1000;#pragma omp parallel for schedule(dynamic, 8) for (k=0; k1000; k+) xk=cos(a)*xk + sin(a)*yk Parallel for scheduleFloat x1例6-9 假設(shè)如圖6-11所示的線程模式在一個(gè)4核的處理器芯片上運(yùn)行，子任務(wù)1到子任務(wù)6的執(zhí)行時(shí)間分別為1到6個(gè)單位。試畫出4個(gè)線程的時(shí)空圖并分析系統(tǒng)的加速比。 例6-9 假設(shè)如圖6-11所示的線程模式在一個(gè)4核的處理器芯解執(zhí)行時(shí)間 = 1+2+3+4+5+6=21個(gè)單位加速比 = 21/12=1.75解執(zhí)行時(shí)間 = 1+

51、2+3+4+5+6=21個(gè)單位并行程序的性能優(yōu)化并行程序的優(yōu)化線程調(diào)度分析程序的調(diào)用關(guān)系分析程序的關(guān)鍵調(diào)用路徑分析程序中的熱點(diǎn)執(zhí)行時(shí)間最長的函數(shù)分析線程負(fù)載平衡分析關(guān)鍵路徑并行程序的性能優(yōu)化并行程序的優(yōu)化例6-10 對于例6-9的情況，假設(shè)在一個(gè)雙核的處理器上運(yùn)行，試畫出4個(gè)線程的時(shí)空圖并分析系統(tǒng)的加速比。假設(shè)：（1）采用動(dòng)態(tài)調(diào)度，子任務(wù)按編號順序進(jìn)入隊(duì)列進(jìn)行調(diào)度。（2）子任務(wù)采用運(yùn)行時(shí)調(diào)度。例6-10 對于例6-9的情況，假設(shè)在一個(gè)雙核的處理器上運(yùn)行解：（1）總的執(zhí)行時(shí)間 = 15個(gè)單位加速比 = 21/15=1.40解：（1）總的執(zhí)行時(shí)間 = 15個(gè)單位解：（2）總的執(zhí)行時(shí)間 = 14個(gè)單

52、位加速比 = 21/14=1.50解：（2）總的執(zhí)行時(shí)間 = 14個(gè)單位習(xí)題293132習(xí)題29MPIMessage 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)通信群集通信MPIMessage passing interface MPI的點(diǎn)對點(diǎn)通信機(jī)制發(fā)送操作模型標(biāo)準(zhǔn)的同步或緩存的（取決于實(shí)現(xiàn)）緩存的把發(fā)送緩存復(fù)制到緩存后返回同步的緩存被接收方讀取后返回就緒的在接收方就緒時(shí)啟動(dòng)發(fā)送（啟動(dòng)發(fā)送后即返回）發(fā)送/接收操作模型阻塞的等到消息復(fù)制到緩存后返回非阻塞

53、的啟動(dòng)發(fā)送/接收后即返回MPI的點(diǎn)對點(diǎn)通信機(jī)制發(fā)送操作模型MPI點(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ā)送一條非阻塞消息MPI_IBSEND發(fā)送一條緩存的非阻塞消息MPI_ISSEND發(fā)送一條同步的非阻塞消息MPI_RESEND發(fā)送一條就緒的非阻塞消息MPI_RECV標(biāo)準(zhǔn)地接收一條消息MPI_IRECV非

54、阻塞地接收一條消息MPI_BCAST廣播一條消息MPI_WAIT等待發(fā)送/接收完成MPI_TEST測試發(fā)送/接收是否完成MPI點(diǎn)對點(diǎn)通信函數(shù)例子MPI_INITMPI_ISENDMPI的聚合通信機(jī)制同步方式同步發(fā)送和阻塞接收所有進(jìn)程都完成調(diào)用時(shí)返回（屏障同步）特異方式 distinguished一對多通信散播廣播多對一通信歸約求最大值、最小值、總和、乘積等收集MPI的聚合通信機(jī)制同步方式MPI群集通信函數(shù)例子MPI_Bcast一對多廣播同樣的消息MPI_Gather多對一收集各個(gè)進(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屏障同步MPI群集通信函數(shù)例子MPI_Bcast例6-11 在一個(gè)雙核的處理器芯片中運(yùn)行了兩個(gè)線程。線程A在開始運(yùn)行2秒后向線程B發(fā)送數(shù)據(jù)，線程B在開始運(yùn)行后的1秒后等待