《并行計(jì)算機(jī)的同步與通信課件》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《并行計(jì)算機(jī)的同步與通信課件（120頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,第6章 并行計(jì)算機(jī)的同步與通信,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),胡越明,計(jì)算機(jī)系,第6章 并行計(jì)算機(jī)的同步與通信計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),Agenda,6.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ī)對(duì)程序的要求,代碼的可重入,并行線(xiàn)程之間的競(jìng)態(tài)現(xiàn)象,線(xiàn)程之間對(duì)共享變量的不同的讀-寫(xiě)和寫(xiě)-寫(xiě)訪(fǎng)問(wèn)順序?qū)е虏煌某绦驁?zhí)行結(jié)果,源自線(xiàn)程間的數(shù)據(jù)相關(guān)性,并行計(jì)算機(jī)的通信方式,共享存儲(chǔ)器,

2、互連網(wǎng)絡(luò)的消息傳遞,6.1 并行計(jì)算機(jī)系統(tǒng)的通信并行計(jì)算機(jī)對(duì)程序的要求,共享存儲(chǔ)器通信,共享變量,最簡(jiǎn)單的通信方式,沒(méi)有同步功能,信號(hào),（signal）,一個(gè)二進(jìn)制變量,可以表示條件、狀態(tài)、鎖和其它同步信息,不能傳遞數(shù)據(jù)內(nèi)容,信箱,固定格式的通信結(jié)構(gòu),通常包含一個(gè)標(biāo)志位,在發(fā)送方和接收方之間起到同步的作用,尋址和管理比較簡(jiǎn)單，不夠靈活,消息,具有靈活格式的通信單位,共享存儲(chǔ)器通信共享變量,共享存儲(chǔ)器通信,線(xiàn)程同步,給線(xiàn)程執(zhí)行順序施加約束的機(jī)制,控制線(xiàn)程執(zhí)行的相對(duì)順序,建立在互斥機(jī)制的基礎(chǔ)上,互斥機(jī)制,使得一次只有一個(gè)線(xiàn)程對(duì)共享變量進(jìn)行訪(fǎng)問(wèn),以保證每個(gè)線(xiàn)程對(duì)于共享變量訪(fǎng)問(wèn)的完整性,常見(jiàn)的互斥機(jī)制

3、,鎖,信號(hào)量,臨界區(qū),共享存儲(chǔ)器通信線(xiàn)程同步,共享存儲(chǔ)器通信,鎖,一種互斥變量,一次只能被一個(gè)線(xiàn)程獲得,信號(hào)量,通過(guò)PV操作在線(xiàn)程間傳遞同步信息,原子操作,P操作將一個(gè)變量減1,減后的變量小于0時(shí)線(xiàn)程被阻塞,V操作將一個(gè)變量加1,加后的變量大于或等于0時(shí)釋放一個(gè)線(xiàn)程,共享存儲(chǔ)器通信鎖,共享存儲(chǔ)器通信,臨界區(qū),短小的、不能被中斷的程序段,進(jìn)入的線(xiàn)程數(shù)量是有限制的,通常只允許一個(gè)線(xiàn)程進(jìn)入臨界區(qū),可以采用鎖機(jī)制來(lái)實(shí)現(xiàn),共享存儲(chǔ)器通信臨界區(qū),鎖,兩個(gè)基本的原子操作,Acquire,原子地等待鎖的狀態(tài)變成打開(kāi)的狀態(tài),將打開(kāi)的鎖狀態(tài)變成關(guān)閉的狀態(tài),這時(shí)該線(xiàn)程獲得了鎖,Release,原子地將鎖的狀態(tài)從關(guān)閉

4、狀態(tài)變成打開(kāi)的狀態(tài),這時(shí)線(xiàn)程釋放了鎖,鎖兩個(gè)基本的原子操作,鎖的類(lèi)型,互斥量,用PV操作上鎖和解鎖,有阻塞,可以加上時(shí)間屬性,遞歸鎖,可以遞歸地獲得的鎖,用于遞歸程序,讀寫(xiě)鎖,多讀單寫(xiě)鎖,限制寫(xiě)操作只能由一個(gè)線(xiàn)程執(zhí)行,用于對(duì)共享變量的讀寫(xiě)操作,自旋鎖,非阻塞的鎖,用于多處理機(jī)系統(tǒng)和多核系統(tǒng),鎖的類(lèi)型互斥量,阻塞型鎖機(jī)制的問(wèn)題,優(yōu)先級(jí)的顛倒,priority inversion,當(dāng)一個(gè)低優(yōu)先級(jí)的線(xiàn)程占用了一個(gè)鎖之后，需要同一個(gè)鎖的高優(yōu)先級(jí)線(xiàn)程就只能等待。,護(hù)航,Convoying,當(dāng)一個(gè)線(xiàn)程擁有一個(gè)鎖而被切換出去時(shí)其他的線(xiàn)程如果需要同一個(gè)鎖的話(huà)都不能運(yùn)行下去,其他線(xiàn)程都圍著擁有鎖的線(xiàn)程團(tuán)團(tuán)轉(zhuǎn),死

5、鎖,Deadlock,鎖的擁有和依賴(lài)關(guān)系形成一個(gè)環(huán),阻塞型鎖機(jī)制的問(wèn)題優(yōu)先級(jí)的顛倒priority invers,死鎖及其解決,死鎖的原因,對(duì)資源（鎖）的訪(fǎng)問(wèn)是獨(dú)占的,線(xiàn)程在已經(jīng)持有一個(gè)資源時(shí)繼續(xù)請(qǐng)求其他資源,所有線(xiàn)程都不放棄已經(jīng)持有的資源,線(xiàn)程對(duì)資源的請(qǐng)求形成一個(gè)環(huán),解決方法,復(fù)制需要獨(dú)占訪(fǎng)問(wèn)的資源,按照一定的順序獲取資源,有序嵌套,無(wú)法獲取其他資源時(shí)放棄已持有的資源,調(diào)用構(gòu)件時(shí)避免使用鎖,死鎖及其解決死鎖的原因,信號(hào),硬件信號(hào),一種黏滯性的邏輯電平,一旦被設(shè)置就一直保持不變,直到被清除,如訪(fǎng)存完成、cache失效、時(shí)鐘信號(hào),可以表示為一個(gè)寄存器變量,對(duì)于信號(hào)變量的讀操作清除這個(gè)信號(hào),軟件信

6、號(hào),表示為共享變量,如進(jìn)程中止信號(hào),信號(hào)硬件信號(hào),互連網(wǎng)絡(luò)的消息傳遞通信方式,消息,結(jié)點(diǎn)間通信的基本邏輯單位,消息頭,目標(biāo)結(jié)點(diǎn)號(hào)、源結(jié)點(diǎn)號(hào)、消息類(lèi)型和消息長(zhǎng)度等,消息體,通信數(shù)據(jù),互連網(wǎng)絡(luò)的消息傳遞通信方式 消息,互連網(wǎng)絡(luò)的消息傳遞通信方式,數(shù)據(jù)包,數(shù)據(jù)傳輸?shù)奈锢韱挝?尋徑信息,序號(hào),數(shù)據(jù)內(nèi)容,校驗(yàn)位,協(xié)議號(hào),時(shí)間戳,存儲(chǔ)轉(zhuǎn)發(fā),store-and-forward,電路交換,circuit switching,虛擬切換,virtual cut-through,蟲(chóng)孔尋徑,wormhole,互連網(wǎng)絡(luò)的消息傳遞通信方式數(shù)據(jù)包存儲(chǔ)轉(zhuǎn)發(fā),互連網(wǎng)絡(luò)的消息傳遞通信方式,存儲(chǔ)轉(zhuǎn)發(fā),store-and-forwa

7、rd,問(wèn)題：延遲大，緩存多,互連網(wǎng)絡(luò)的消息傳遞通信方式存儲(chǔ)轉(zhuǎn)發(fā)store-and-for,互連網(wǎng)絡(luò)的消息傳遞通信方式,電路交換,circuit switching,問(wèn)題：沖突多，利用率低,互連網(wǎng)絡(luò)的消息傳遞通信方式電路交換circuit switc,互連網(wǎng)絡(luò)的消息傳遞通信方式,虛擬切換,virtual cut-through,問(wèn)題：緩存多,flits,互連網(wǎng)絡(luò)的消息傳遞通信方式虛擬切換virtual cut-t,互連網(wǎng)絡(luò)的消息傳遞通信方式,蟲(chóng)孔尋徑,wormhole,問(wèn)題：死鎖和活鎖,互連網(wǎng)絡(luò)的消息傳遞通信方式蟲(chóng)孔尋徑wormhole,互連網(wǎng)絡(luò)的消息傳遞通信方式,蟲(chóng)孔尋徑與存儲(chǔ)轉(zhuǎn)發(fā)的比較,互連

8、網(wǎng)絡(luò)的消息傳遞通信方式蟲(chóng)孔尋徑與存儲(chǔ)轉(zhuǎn)發(fā)的比較,互連網(wǎng)絡(luò)的消息傳遞通信方式,衡量指標(biāo),通信帶寬,單位時(shí)間能夠傳輸?shù)臄?shù)據(jù)量,取決于處理器的通信處理吞吐率、存儲(chǔ)器的吞吐率和互連網(wǎng)絡(luò)的傳輸帶寬,通信延遲,發(fā)送的時(shí)間開(kāi)銷(xiāo),信號(hào)傳輸時(shí)間,傳輸持續(xù)時(shí)間,接收方的時(shí)間開(kāi)銷(xiāo),通信延遲隱藏能力,通信時(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é)果匯總的時(shí)間為1秒。如果將該計(jì)算任務(wù)放在多核處理器的計(jì)算機(jī)上運(yùn)行，將運(yùn)算部分分解成多個(gè)線(xiàn)程并行執(zhí)行。,（1）假如任務(wù)的啟動(dòng)和數(shù)據(jù)匯總操作不能并行執(zhí)行，運(yùn)算

9、部分可以進(jìn)行任意的任務(wù)分解，任務(wù)之間的通信量可以忽略，也不考慮任務(wù)分解后存儲(chǔ)系統(tǒng)對(duì)性能的影響。問(wèn)在處理器核的數(shù)量分別為2、4、8、16時(shí)的任務(wù)執(zhí)行時(shí)間和加速比。,（2）上述情況下，假如每?jī)蓚€(gè)處理器核之間的通信時(shí)間為0.1秒，每對(duì)處理器核的通信串行進(jìn)行，問(wè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+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；,

10、在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ī)上沒(méi)有通信時(shí)間，運(yùn)行時(shí)間為12秒；,在雙核計(jì)算機(jī)上的通信時(shí)間為1,0.1，運(yùn)行時(shí)間為1+10/2+1+0.1=7.1秒，加速比為12/7.1=1.69；,在4核計(jì)算機(jī)上的通信時(shí)間為6,0.1=0.6，運(yùn)行時(shí)間為1+10/4+1+0.6=5.1秒，加速比為12/5.1=2.35；,在8核計(jì)算機(jī)上的通信時(shí)間為28,0.1=2.8

11、，運(yùn)行時(shí)間為1+10/8+1+2.8=6.05秒，加速比為12/6.05=1.98；,在16核計(jì)算機(jī)上的通信時(shí)間為120,0.1=12，運(yùn)行時(shí)間為1+10/16+1+12=14.63秒，加速比為12/14.63=0.82，即比單核計(jì)算機(jī)的計(jì)算時(shí)間更長(zhǎng)。,解：（2）任務(wù)在單個(gè)核的計(jì)算機(jī)上沒(méi)有通信時(shí)間，運(yùn)行時(shí)間為12,解,加速比,單核,2核,4核,8核,16核,無(wú)通信開(kāi)銷(xiāo),1,1.71,2.67,3.69,4.56,有通信開(kāi)銷(xiāo),1,1.69,2.35,1.98,0.82,解加速比單核2核4核8核16核無(wú)通信開(kāi)銷(xiāo)11.712.673,習(xí)題,6,習(xí)題6,6.2 Cache與存儲(chǔ)器數(shù)據(jù)一致性,共享存儲(chǔ)器

12、多處理機(jī)系統(tǒng)的問(wèn)題,訪(fǎng)存沖突與數(shù)據(jù)一致性,數(shù)據(jù)多個(gè)副本之間的相同性,6.2 Cache與存儲(chǔ)器數(shù)據(jù)一致性 共享存儲(chǔ)器多處理機(jī)系統(tǒng),數(shù)據(jù)一致性的實(shí)現(xiàn),軟件方法,編譯分析,避免,cache,共享數(shù)據(jù),總線(xiàn)監(jiān)測(cè),各,cache,設(shè)置監(jiān)測(cè)部件,MESI,協(xié)議,目錄表法,全映射,有限目錄,鏈?zhǔn)侥夸?SCI,數(shù)據(jù)一致性的實(shí)現(xiàn)軟件方法,總線(xiàn)監(jiān)測(cè),所有cache不斷監(jiān)測(cè)總線(xiàn)上的每一個(gè)地址,總線(xiàn)使得寫(xiě)操作變成串行的,Cache 失效時(shí)需要確定數(shù)據(jù)塊的位置,write invalidate protocol,invalidates other copies on a write.,write update or

13、write broadcast protocol,update all the cached copies of a data item when it is written,cpu1,cpu2,cache1,cache2,Main,memory,總線(xiàn)監(jiān)測(cè)所有cache不斷監(jiān)測(cè)總線(xiàn)上的每一個(gè)地址cpu1cp,總線(xiàn)監(jiān)測(cè),寫(xiě)無(wú)效方式,多次寫(xiě)操作時(shí)只需一次invalidate,對(duì)于整個(gè)cache數(shù)據(jù)塊進(jìn)行,寫(xiě)更新方式,對(duì)于數(shù)據(jù)塊中的個(gè)別字進(jìn)行,讀操作的命中率高,所有寫(xiě)操作通過(guò)總線(xiàn)寫(xiě)入所以相關(guān)的其他cache中,寫(xiě)操作的開(kāi)銷(xiāo)較大,總線(xiàn)監(jiān)測(cè)寫(xiě)無(wú)效方式,總線(xiàn)監(jiān)測(cè),每個(gè)處理器的cache中設(shè)置一個(gè)監(jiān)測(cè)部件,

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

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

16、址映像和LRU替換策略，每個(gè)塊的初始狀態(tài)都是無(wú)效的。在以下讀訪(fǎng)問(wèn)塊地址序列下，試畫(huà)出兩個(gè)L1 cache中塊的分配情況，并標(biāo)出每個(gè)塊的狀態(tài)。,A核：1，0，6，7，8，0，1,B核：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沒(méi)有該塊,1表示有該塊,有限目錄,每個(gè)快表目錄項(xiàng)包含固定數(shù)量的指示位段,指示位段的位數(shù)與處理器數(shù)量無(wú)關(guān),鏈?zhǔn)侥夸?目錄表法全映射,例6-5,設(shè)4個(gè)CPU的并行計(jì)算機(jī)中采用全映射的目錄表法進(jìn)行一致性操作，初始時(shí)某cache塊都在無(wú)效狀態(tài)，然后4個(gè)CPU對(duì)該存儲(chǔ)塊分別進(jìn)行如下操作：,CPU 0讀，CPU 1讀，CPU 2讀，CPU 1替換，CPU 0寫(xiě),試寫(xiě)出每次訪(fǎng)問(wèn)后該塊的有效指示位段的變化情況，假設(shè)一致性操作采用寫(xiě)無(wú)效策略。,事件,指示狀態(tài)位段,初始,0000,CPU 0讀,0001,CPU 1讀,0011,CPU 2讀,0111,CPU 1替換,0101,CPU 0寫(xiě),0001,