并行計算機的同步與通信課件

單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,第6章 并行計算機的同步與通信,計算機系統(tǒng)結(jié)構(gòu),胡越明,計算機系,第6章 并行計算機的同步與通信計算機系統(tǒng)結(jié)構(gòu),Agenda,6.1 并行計算機系統(tǒng)的通信,6.2 Cache與存儲器數(shù)據(jù)一致性,6.3 并行計算機的同步,6.4 并行計算機程序設(shè)計,Agenda6.1 并行計算機系統(tǒng)的通信,6.1 并行計算機系統(tǒng)的通信,并行計算機對程序的要求,代碼的可重入,并行線程之間的競態(tài)現(xiàn)象,線程之間對共享變量的不同的讀-寫和寫-寫訪問順序?qū)е虏煌某绦驁?zhí)行結(jié)果,源自線程間的數(shù)據(jù)相關(guān)性,并行計算機的通信方式,共享存儲器,互連網(wǎng)絡(luò)的消息傳遞,6.1 并行計算機系統(tǒng)的通信并行計算機對程序的要求,共享存儲器通信,共享變量,最簡單的通信方式,沒有同步功能,信號,（signal）,一個二進制變量,可以表示條件、狀態(tài)、鎖和其它同步信息,不能傳遞數(shù)據(jù)內(nèi)容,信箱,固定格式的通信結(jié)構(gòu),通常包含一個標(biāo)志位,在發(fā)送方和接收方之間起到同步的作用,尋址和管理比較簡單，不夠靈活,消息,具有靈活格式的通信單位,共享存儲器通信共享變量,共享存儲器通信,線程同步,給線程執(zhí)行順序施加約束的機制,控制線程執(zhí)行的相對順序,建立在互斥機制的基礎(chǔ)上,互斥機制,使得一次只有一個線程對共享變量進行訪問,以保證每個線程對于共享變量訪問的完整性,常見的互斥機制,鎖,信號量,臨界區(qū),共享存儲器通信線程同步,共享存儲器通信,鎖,一種互斥變量,一次只能被一個線程獲得,信號量,通過PV操作在線程間傳遞同步信息,原子操作,P操作將一個變量減1,減后的變量小于0時線程被阻塞,V操作將一個變量加1,加后的變量大于或等于0時釋放一個線程,共享存儲器通信鎖,共享存儲器通信,臨界區(qū),短小的、不能被中斷的程序段,進入的線程數(shù)量是有限制的,通常只允許一個線程進入臨界區(qū),可以采用鎖機制來實現(xiàn),共享存儲器通信臨界區(qū),鎖,兩個基本的原子操作,Acquire,原子地等待鎖的狀態(tài)變成打開的狀態(tài),將打開的鎖狀態(tài)變成關(guān)閉的狀態(tài),這時該線程獲得了鎖,Release,原子地將鎖的狀態(tài)從關(guān)閉狀態(tài)變成打開的狀態(tài),這時線程釋放了鎖,鎖兩個基本的原子操作,鎖的類型,互斥量,用PV操作上鎖和解鎖,有阻塞,可以加上時間屬性,遞歸鎖,可以遞歸地獲得的鎖,用于遞歸程序,讀寫鎖,多讀單寫鎖,限制寫操作只能由一個線程執(zhí)行,用于對共享變量的讀寫操作,自旋鎖,非阻塞的鎖,用于多處理機系統(tǒng)和多核系統(tǒng),鎖的類型互斥量,阻塞型鎖機制的問題,優(yōu)先級的顛倒,priority inversion,當(dāng)一個低優(yōu)先級的線程占用了一個鎖之后，需要同一個鎖的高優(yōu)先級線程就只能等待。,護航,Convoying,當(dāng)一個線程擁有一個鎖而被切換出去時其他的線程如果需要同一個鎖的話都不能運行下去,其他線程都圍著擁有鎖的線程團團轉(zhuǎn),死鎖,Deadlock,鎖的擁有和依賴關(guān)系形成一個環(huán),阻塞型鎖機制的問題優(yōu)先級的顛倒priority invers,死鎖及其解決,死鎖的原因,對資源（鎖）的訪問是獨占的,線程在已經(jīng)持有一個資源時繼續(xù)請求其他資源,所有線程都不放棄已經(jīng)持有的資源,線程對資源的請求形成一個環(huán),解決方法,復(fù)制需要獨占訪問的資源,按照一定的順序獲取資源,有序嵌套,無法獲取其他資源時放棄已持有的資源,調(diào)用構(gòu)件時避免使用鎖,死鎖及其解決死鎖的原因,信號,硬件信號,一種黏滯性的邏輯電平,一旦被設(shè)置就一直保持不變,直到被清除,如訪存完成、cache失效、時鐘信號,可以表示為一個寄存器變量,對于信號變量的讀操作清除這個信號,軟件信號,表示為共享變量,如進程中止信號,信號硬件信號,互連網(wǎng)絡(luò)的消息傳遞通信方式,消息,結(jié)點間通信的基本邏輯單位,消息頭,目標(biāo)結(jié)點號、源結(jié)點號、消息類型和消息長度等,消息體,通信數(shù)據(jù),互連網(wǎng)絡(luò)的消息傳遞通信方式 消息,互連網(wǎng)絡(luò)的消息傳遞通信方式,數(shù)據(jù)包,數(shù)據(jù)傳輸?shù)奈锢韱挝?尋徑信息,序號,數(shù)據(jù)內(nèi)容,校驗位,協(xié)議號,時間戳,存儲轉(zhuǎn)發(fā),store-and-forward,電路交換,circuit switching,虛擬切換,virtual cut-through,蟲孔尋徑,wormhole,互連網(wǎng)絡(luò)的消息傳遞通信方式數(shù)據(jù)包存儲轉(zhuǎn)發(fā),互連網(wǎng)絡(luò)的消息傳遞通信方式,存儲轉(zhuǎn)發(fā),store-and-forward,問題：延遲大，緩存多,互連網(wǎng)絡(luò)的消息傳遞通信方式存儲轉(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 cut-t,互連網(wǎng)絡(luò)的消息傳遞通信方式,蟲孔尋徑,wormhole,問題：死鎖和活鎖,互連網(wǎng)絡(luò)的消息傳遞通信方式蟲孔尋徑wormhole,互連網(wǎng)絡(luò)的消息傳遞通信方式,蟲孔尋徑與存儲轉(zhuǎn)發(fā)的比較,互連網(wǎng)絡(luò)的消息傳遞通信方式蟲孔尋徑與存儲轉(zhuǎn)發(fā)的比較,互連網(wǎng)絡(luò)的消息傳遞通信方式,衡量指標(biāo),通信帶寬,單位時間能夠傳輸?shù)臄?shù)據(jù)量,取決于處理器的通信處理吞吐率、存儲器的吞吐率和互連網(wǎng)絡(luò)的傳輸帶寬,通信延遲,發(fā)送的時間開銷,信號傳輸時間,傳輸持續(xù)時間,接收方的時間開銷,通信延遲隱藏能力,通信時間與計算時間或者其他通信時間的重疊程度,互連網(wǎng)絡(luò)的消息傳遞通信方式衡量指標(biāo),例6-2,1個計算任務(wù)在單個核的計算機上運行的啟動時間為1秒，運算時間為10秒，數(shù)據(jù)結(jié)果匯總的時間為1秒。如果將該計算任務(wù)放在多核處理器的計算機上運行，將運算部分分解成多個線程并行執(zhí)行。,（1）假如任務(wù)的啟動和數(shù)據(jù)匯總操作不能并行執(zhí)行，運算部分可以進行任意的任務(wù)分解，任務(wù)之間的通信量可以忽略，也不考慮任務(wù)分解后存儲系統(tǒng)對性能的影響。問在處理器核的數(shù)量分別為2、4、8、16時的任務(wù)執(zhí)行時間和加速比。,（2）上述情況下，假如每兩個處理器核之間的通信時間為0.1秒，每對處理器核的通信串行進行，問在核的數(shù)量分別為2、4、8、16時的任務(wù)執(zhí)行時間和加速比。,例6-2 1個計算任務(wù)在單個核的計算機上運行的啟動時間為1秒,解,：（1）,任務(wù)在單個核的計算機上運行時間為12秒；,在雙核計算機上的運行時間為1+10/2+1=7秒，加速比為12/7=1.71；,在4核計算機上的運行時間為1+10/4+1=4.5秒，加速比為12/4.5=2.67；,在8核計算機上的運行時間為1+10/8+1=3.25秒，加速比為12/3.25=3.69；,在16核計算機上的運行時間為1+10/16+1=2.63秒，加速比為12/2.63=4.56。,解：（1）任務(wù)在單個核的計算機上運行時間為12秒；,解,：（2）,任務(wù)在單個核的計算機上沒有通信時間，運行時間為12秒；,在雙核計算機上的通信時間為1,0.1，運行時間為1+10/2+1+0.1=7.1秒，加速比為12/7.1=1.69；,在4核計算機上的通信時間為6,0.1=0.6，運行時間為1+10/4+1+0.6=5.1秒，加速比為12/5.1=2.35；,在8核計算機上的通信時間為28,0.1=2.8，運行時間為1+10/8+1+2.8=6.05秒，加速比為12/6.05=1.98；,在16核計算機上的通信時間為120,0.1=12，運行時間為1+10/16+1+12=14.63秒，加速比為12/14.63=0.82，即比單核計算機的計算時間更長。,解：（2）任務(wù)在單個核的計算機上沒有通信時間，運行時間為12,解,加速比,單核,2核,4核,8核,16核,無通信開銷,1,1.71,2.67,3.69,4.56,有通信開銷,1,1.69,2.35,1.98,0.82,解加速比單核2核4核8核16核無通信開銷11.712.673,習(xí)題,6,習(xí)題6,6.2 Cache與存儲器數(shù)據(jù)一致性,共享存儲器多處理機系統(tǒng)的問題,訪存沖突與數(shù)據(jù)一致性,數(shù)據(jù)多個副本之間的相同性,6.2 Cache與存儲器數(shù)據(jù)一致性 共享存儲器多處理機系統(tǒng),數(shù)據(jù)一致性的實現(xiàn),軟件方法,編譯分析,避免,cache,共享數(shù)據(jù),總線監(jiān)測,各,cache,設(shè)置監(jiān)測部件,MESI,協(xié)議,目錄表法,全映射,有限目錄,鏈?zhǔn)侥夸?SCI,數(shù)據(jù)一致性的實現(xiàn)軟件方法,總線監(jiān)測,所有cache不斷監(jiān)測總線上的每一個地址,總線使得寫操作變成串行的,Cache 失效時需要確定數(shù)據(jù)塊的位置,write invalidate protocol,invalidates other copies on a write.,write update or write broadcast protocol,update all the cached copies of a data item when it is written,cpu1,cpu2,cache1,cache2,Main,memory,總線監(jiān)測所有cache不斷監(jiān)測總線上的每一個地址cpu1cp,總線監(jiān)測,寫無效方式,多次寫操作時只需一次invalidate,對于整個cache數(shù)據(jù)塊進行,寫更新方式,對于數(shù)據(jù)塊中的個別字進行,讀操作的命中率高,所有寫操作通過總線寫入所以相關(guān)的其他cache中,寫操作的開銷較大,總線監(jiān)測寫無效方式,總線監(jiān)測,每個處理器的cache中設(shè)置一個監(jiān)測部件,監(jiān)測總線上的寫操作,根據(jù)監(jiān)測的情況改變本地cache塊的狀態(tài),無效、修改、獨占、共享,監(jiān)測條件,主存中有一個單元被其他處理器所修改,而這個單元在本地cache中也有一個副本,對于寫更新方法,擁有數(shù)據(jù)最新版本的cache需向其他cache提供數(shù)據(jù)塊內(nèi)容,阻止其他處理器從共享存儲器的讀操作,總線監(jiān)測每個處理器的cache中設(shè)置一個監(jiān)測部件,MESI,協(xié)議,MESI協(xié)議,例6-3,設(shè)單總線連接的兩個CPU中采用MESI協(xié)議進行一致性操作，初始時某cache塊都在無效狀態(tài)，然后兩個CPU對該存儲塊分別進行如下操作：,CPU A讀，CPU B讀，CPU A寫，CPU B讀，CPU B寫,試寫出每次訪問后兩個塊的狀態(tài)變化情況。,事件,狀態(tài)A,狀態(tài)B,說明,初始,無效,無效（I）,數(shù)據(jù)未裝入,CPU A讀,獨占,無效（I）,讀操作cache失效，裝入,CPU B讀,共享,共享（S）,讀操作cache失效，裝入后共享,CPU A寫,修改,無效（I）,寫操作命中,CPU B讀,共享,共享（S）,讀操作失效，裝入,CPU B寫,無效,修改（M）,寫操作命中,例6-3 設(shè)單總線連接的兩個CPU中采用MESI協(xié)議進行一致,例6-4,在一個共享L2 cache的雙核處理器芯片中，兩個L1 cache通過片內(nèi)總線與L2 cache連接，并采用MESI協(xié)議保持一致性。假設(shè)L1 cache各有4個塊，采用全相聯(lián)地址映像和LRU替換策略，每個塊的初始狀態(tài)都是無效的。在以下讀訪問塊地址序列下，試畫出兩個L1 cache中塊的分配情況，并標(biāo)出每個塊的狀態(tài)。,A核：1，0，6，7，8，0，1,B核：0，2，7，8，9，2，0,例6-4 在一個共享L2 cache的雙核處理器芯片中，兩個,解,解,目錄表法,全映射,每個快表目錄項包含,N,個指示位段,N,為系統(tǒng)中處理器的個數(shù),指示位段構(gòu)成一個位向量,0表示相應(yīng)的處理器cache沒有該塊,1表示有該塊,有限目錄,每個快表目錄項包含固定數(shù)量的指示位段,指示位段的位數(shù)與處理器數(shù)量無關(guān),鏈?zhǔn)侥夸?目錄表法全映射,例6-5,設(shè)4個CPU的并行計算機中采用全映射的目錄表法進行一致性操作，初始時某cache塊都在無效狀態(tài)，然后4個CPU對該存儲塊分別進行如下操作：,CPU 0讀，CPU 1讀，CPU 2讀，CPU 1替換，CPU 0寫,試寫出每次訪問后該塊的有效指示位段的變化情況，假設(shè)一致性操作采用寫無效策略。,事件,指示狀態(tài)位段,初始,0000,CPU 0讀,0001,CPU 1讀,0011,CPU 2讀,0111,CPU 1替換,0101,CPU 0寫,0001,