多核體系結(jié)構(gòu)與并行編程模型計算機科學(xué)導(dǎo)論第八講教學(xué)課件

多核體系結(jié)構(gòu)與并行編程模型

計算機科學(xué)導(dǎo)論第八講計算機科學(xué)技術(shù)學(xué)院陳意iyun@多核體系結(jié)構(gòu)與并行編程模型

計算機科學(xué)導(dǎo)論第八講計算機科學(xué)技課程內(nèi)容課程內(nèi)容圍繞學(xué)科理論體系中的模型理論,程序理論和計算理論1.模型理論關(guān)心的問題

給定模型M，哪些問題可以由模型M解決；如何比較模型的表達能力2.程序理論關(guān)心的問題給定模型M，如何用模型M解決問題包括程序設(shè)計范型、程序設(shè)計語言、程序設(shè)計、形式語義、類型論、程序驗證、程序分析等3.計算理論關(guān)心的問題

給定模型M和一類問題,解決該類問題需多少資源課程內(nèi)容課程內(nèi)容講座提綱基本知識多核體系結(jié)構(gòu)、并行編程模型內(nèi)存一致性模型嚴格一致性模型、順序一致性模型、內(nèi)存一致性模型的重要性共享內(nèi)存并行編程模型同步、鎖、臨界區(qū)、條件變量、死鎖、數(shù)據(jù)競爭消息傳遞并行編程模型消息傳遞、同步與異步講座提綱基本知識對稱多處理器對稱多處理器的體系結(jié)構(gòu)二級緩存內(nèi)存總線二級緩存二級緩存二級緩存一級緩存一級緩存一級緩存一級緩存處理器處理器處理器處理器基本知識必須在處理器的緩存中找到它操作的大部分數(shù)據(jù)，以保證性能

通過共享內(nèi)存來進行通信對稱多處理器二級內(nèi)存總線二級二級二級一級一級一級一級處理器處幾個概念的粗略解釋任務(wù)：一般性的抽象術(shù)語，指由軟件完成的一個活動。例如，矩陣分塊乘就是把矩陣乘分成多個任務(wù),以便于在對稱多處理器上并行執(zhí)行這些任務(wù)進程：任務(wù)在程序中的對應(yīng)物，它有自己的數(shù)據(jù)和代碼，需要在處理器上運行直至結(jié)束。進程是操作系統(tǒng)進行資源分配和調(diào)度的獨立單位線程：是把進程細分出現(xiàn)的實際運行單位，線程是進程中一段順序執(zhí)行的語句序列。把進程分成若干線程是為了提高進程執(zhí)行過程中的并行性。線程是操作系統(tǒng)調(diào)度的基本單位下面未嚴格區(qū)分進程和線程基本知識幾個概念的粗略解釋基本知識幾個概念的粗略解釋并行(parallel):多個可以同時執(zhí)行的任務(wù)，在多處理器上同時執(zhí)行并發(fā)(cuncorrent)：多個可以同時執(zhí)行的任務(wù)，在單處理器上交錯執(zhí)行

并發(fā)是邏輯上同時發(fā)生，而并行是物理上同時發(fā)生。下面不區(qū)分并行和并發(fā)基本知識tABtAB幾個概念的粗略解釋基本知識tAtA對稱多處理器對稱多處理器的體系結(jié)構(gòu)二級緩存內(nèi)存總線二級緩存二級緩存二級緩存一級緩存一級緩存一級緩存一級緩存處理器處理器處理器處理器基本知識多個高性能處理器可以集成在一塊芯片上對稱多處理器二級內(nèi)存總線二級二級二級一級一級一級一級處理器處基本知識單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu)執(zhí)行單元緩存CPU狀態(tài)中斷邏輯執(zhí)行單元緩存CPU狀態(tài)中斷邏輯執(zhí)行單元緩存CPU狀態(tài)中斷邏輯單核結(jié)構(gòu)多處理器結(jié)構(gòu)執(zhí)行單元緩存CPU狀態(tài)中斷邏輯CPU狀態(tài)中斷邏輯超線程結(jié)構(gòu)

超線程技術(shù)充分利用執(zhí)行單元中的空閑資源，以便在相同時間內(nèi)完成更多工作

執(zhí)行單元中的資源：內(nèi)存訪問部件、算術(shù)運算部件和浮點功能部件等基本知識單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu)執(zhí)行單元緩存CPU狀態(tài)中基本知識單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu)執(zhí)行單元緩存CPU狀態(tài)中斷邏輯執(zhí)行單元緩存CPU狀態(tài)中斷邏輯執(zhí)行單元緩存CPU狀態(tài)中斷邏輯單核結(jié)構(gòu)多處理器結(jié)構(gòu)執(zhí)行單元緩存CPU狀態(tài)中斷邏輯CPU狀態(tài)中斷邏輯超線程結(jié)構(gòu)

超線程技術(shù)本質(zhì)上就是多個線程共享一個執(zhí)行核

兩套CPU狀態(tài)+中斷邏輯是為了適應(yīng)兩個線程同時執(zhí)行的需要基本知識單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu)執(zhí)行單元緩存CPU狀態(tài)中基本知識單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu)共享緩存的多核體系結(jié)構(gòu)執(zhí)行單元緩存CPU狀態(tài)中斷邏輯執(zhí)行單元緩存CPU狀態(tài)中斷邏輯多核體系結(jié)構(gòu)執(zhí)行單元緩存CPU狀態(tài)中斷邏輯執(zhí)行單元CPU狀態(tài)中斷邏輯

多核處理器是把兩個甚至更多的獨立執(zhí)行核嵌入到一個處理器的內(nèi)部，每個線程都有完整的硬件執(zhí)行環(huán)境，各線程之間實現(xiàn)了真正意義上的并行基本知識單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu)共享緩存的多核體系結(jié)構(gòu)執(zhí)基本知識單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu)

體系結(jié)構(gòu)越來越復(fù)雜，若這些復(fù)雜的特征都要反映到編程語言中，才能寫出較好利用體系結(jié)構(gòu)優(yōu)點的程序，則編寫程序?qū)⑹呛芾щy的工作

需要設(shè)計好的編程模型并通過編譯器和操作系統(tǒng)的幫助和支持來解決采用超線程技術(shù)的多核體系結(jié)構(gòu)執(zhí)行單元緩存CPU狀態(tài)中斷邏輯CPU狀態(tài)中斷邏輯執(zhí)行單元緩存CPU狀態(tài)中斷邏輯CPU狀態(tài)中斷邏輯基本知識單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu)采用超線程技術(shù)的多核體系基本知識并行編程模型是底層體系結(jié)構(gòu)與上層應(yīng)用程序之間的橋梁向上隱藏并行處理器的細節(jié)，并向程序員提供表達并行的方法向下充分利用硬件資源，高效且正確地完成應(yīng)用需求任務(wù)劃分、任務(wù)映射、數(shù)據(jù)分布、通信和同步是設(shè)計并行編程模型時需要考慮的五個關(guān)鍵要素并行編程模型的另一種說法并行編程模型是編寫可被編譯和運行的并行程序的一種模型基本知識并行編程模型基本知識并行編程模型的分類1.按進程交互的機制來分共享內(nèi)存模型：進程共享可以異步地讀寫的全局數(shù)據(jù)空間消息傳遞模型:進程通過相互傳遞消息來交換數(shù)據(jù)隱式模型：進程之間交互是用戶不可訪問的2.按問題分解任務(wù)并行：每個處理器執(zhí)行不同的任務(wù)數(shù)據(jù)并行：把大任務(wù)分別成若干個相同的子任務(wù)3.……基本知識并行編程模型的分類內(nèi)存一致性模型內(nèi)存一致性模型描述的是，在有共享內(nèi)存的多處理器系統(tǒng)上，在它們讀寫共享內(nèi)存操作的可能執(zhí)行順序中，哪些順序是正確的內(nèi)存一致性模型是理解并行程序語義的一個關(guān)鍵為確保寫出正確的并行程序，程序員必須準確理解并行程序的語義隨著多核處理器的廣泛應(yīng)用，并行程序設(shè)計已經(jīng)由一種特殊的、只需少數(shù)高端技術(shù)人才掌握的技巧，變?yōu)橐环N大多數(shù)程序員都應(yīng)該掌握的基本技能內(nèi)存一致性模型內(nèi)存一致性模型內(nèi)存一致性模型嚴格一致性（原子一致性）模型

任何對內(nèi)存位置x的讀操作，得到的是最近一次對x的寫操作所寫入的值單處理器遵守嚴格一致性

下面,P1和P2是處理器,x是共享變量,初值是0。W(x)1表示:把1寫到x中；R(x)3表示:讀取x,得值3P1:W(x)1 P1: W(x)1P2:R(x)1R(x)1 P2:R(x)0R(x)1P1:W(x)1P2:R(x)0R(x)1ttt

左邊不符合嚴格一致性

多處理器+共享內(nèi)存時,會出現(xiàn)讀寫或?qū)憣懖僮鞯臎_突內(nèi)存一致性模型嚴格一致性（原子一致性）模型ttt左邊不符順序一致性模型比嚴格一致性弱的模型在多處理器共享內(nèi)存情況下，每個處理器執(zhí)行的單個線程嚴格按照程序規(guī)定的順序逐語句地進行內(nèi)存訪問操作比順序一致性還弱的統(tǒng)稱為弱內(nèi)存模型（不同情況有不同名稱）大多數(shù)程序員假定并行程序的運行滿足順序一致性，但現(xiàn)實中幾乎所有的并行程序都在某種弱內(nèi)存模型下運行，而且不同的并行語言和處理器的內(nèi)存模型不同內(nèi)存一致性模型順序一致性模型內(nèi)存一致性模型順序一致性模型例：互斥使用臨界區(qū)的并行線程

若兩個線程嚴格按照給出的語句順序逐條執(zhí)行，則它們能實現(xiàn)互斥功能，因為r1和r2不可能同時為0

現(xiàn)實中，編譯器和處理器內(nèi)部進行的優(yōu)化都會導(dǎo)致內(nèi)存操作的實際順序和代碼中的語句順序不一致,使得兩個條件判斷都為真，兩個線程都進入臨界區(qū)內(nèi)存一致性模型x和y:共享變量,初始:x=0,y=0x=1; y=1;r1=y; r2=x;if(r1==0){ if(r2==0){criticalregion criticalregion} }順序一致性模型內(nèi)存一致性模型x和y:共享變量,初始:x內(nèi)存一致性模型的重要性它作為系統(tǒng)實現(xiàn)和程序員之間的接口，對處理器體系結(jié)構(gòu)的實現(xiàn)、并行語言的實現(xiàn)、并行程序的開發(fā)和驗證都有重要意義以并行語言的設(shè)計和實現(xiàn)為例編譯器的優(yōu)化算法會調(diào)整源程序中的內(nèi)存操作順序，使得目標(biāo)程序和源程序的順序不一致目標(biāo)程序的執(zhí)行順序又可能被處理器進一步改變并行語言的設(shè)計和實現(xiàn)必須考慮到這兩種情況及其效果的疊加，對源程序可能表現(xiàn)出的行為進行準確描述(并行語言的內(nèi)存模型)，便于正確編程內(nèi)存一致性模型內(nèi)存一致性模型的重要性內(nèi)存一致性模型編程語言內(nèi)存一致性模型的現(xiàn)狀

由于優(yōu)化算法的多樣性，編程語言內(nèi)存模型比體系結(jié)構(gòu)的內(nèi)存模型復(fù)雜Gosling等為第一版Java語言給出的內(nèi)存一致性模型,無法支持常用的優(yōu)化算法,是一個失敗的模型Manson等給出的Java模型，雖被語言新標(biāo)準所采納，但模型十分晦澀，是Java語言中最復(fù)雜部分,極少有人能正確理解其含義Boehm和Adve試圖為C++提供一個簡單的模型，但很多地方有歧義或不清晰內(nèi)存一致性模型編程語言內(nèi)存一致性模型的現(xiàn)狀內(nèi)存一致性模型共享內(nèi)存并行編程模型使用共享內(nèi)存的錯誤例子并行計算Fibonacci序列下一個元素的兩個線程對兩個線程的執(zhí)行沒有任何約束下面是兩個線程某次并行時的語句執(zhí)行順序prev和curr:初值分為0和1的共享變量intretval; intretval;retval=curr; retval=curr;curr=curr+prev; curr=curr+prev; prev=retval;prev=retval;t共享內(nèi)存并行編程模型使用共享內(nèi)存的錯誤例子prev和curr共享內(nèi)存并行編程模型使用共享內(nèi)存的錯誤例子并行計算Fibonacci序列下一個元素的兩個線程對兩個線程的執(zhí)行沒有任何約束下面是兩個線程某次并行時的語句執(zhí)行順序prev和curr:初值分為0和1的共享變量intretval; intretval;retval=curr; retval=curr;curr=curr+prev; curr=curr+prev; prev=retval;prev=retval;t111111共享內(nèi)存并行編程模型使用共享內(nèi)存的錯誤例子prev和curr共享內(nèi)存并行編程模型使用共享內(nèi)存的錯誤例子并行計算Fibonacci序列下一個元素的兩個線程對兩個線程的執(zhí)行沒有任何約束下面是兩個線程某次并行時的語句執(zhí)行順序顯然結(jié)果不對原因：

對共享變量的訪問缺乏約束prev和curr:初值分為0和1的共享變量intretval; intretval;retval=curr; retval=curr;curr=curr+prev; curr=curr+prev; prev=retval;prev=retval;t111111共享內(nèi)存并行編程模型使用共享內(nèi)存的錯誤例子prev和curr共享內(nèi)存并行編程模型同步同步是對線程執(zhí)行的順序進行強行限制的一種機制，用來控制線程執(zhí)行的相對順序，可以有效解決任何線程之間的沖突，而這些沖突有可能會導(dǎo)致線程的執(zhí)行出現(xiàn)異常行為簡言之，同步主要用于協(xié)調(diào)線程執(zhí)行和管理共享數(shù)據(jù)同步機制信號量、鎖（又可細分成多種）、條件變量、…共享內(nèi)存并行編程模型同步共享內(nèi)存并行編程模型鎖用來體現(xiàn)一種互斥的并行控制策略一個線程在同一個時刻只能使用一個鎖，一個鎖至多由一個線程獲得。鎖有兩個原子操作：1.acquire:

等待鎖狀態(tài)變?yōu)槲醇渔i狀態(tài)，然后將其置為已加鎖狀態(tài)prev和curr:初值分為0和1的共享變量L是鎖intretval; intretval;L->acquire();

L->acquire();retval=curr; retval=curr;curr=curr+prev;curr=curr+prev;prev=retval; prev=retval;

共享內(nèi)存并行編程模型鎖prev和curr:初值分為0和1的共享內(nèi)存并行編程模型鎖用來體現(xiàn)一種互斥的并行控制策略一個線程在同一個時刻只能使用一個鎖，一個鎖至多由一個線程獲得。鎖有兩個原子操作：2.release:

將鎖狀態(tài)由已加鎖變?yōu)槲醇渔iprev和curr:初值分為0和1的共享變量L是鎖intretval; intretval;L->acquire();

L->acquire();retval=curr; retval=curr;curr=curr+prev;curr=curr+prev;prev=retval; prev=retval;L->release(); L->release();共享內(nèi)存并行編程模型鎖prev和curr:初值分為0和1的共享內(nèi)存并行編程模型臨界區(qū)（criticalsection）

指包含有共享變量的一段代碼，這些共享變量和多個線程之間存在相關(guān)關(guān)系

多線程編程的主要挑戰(zhàn)在于需要以多個線程執(zhí)行互斥操作的方式實現(xiàn)臨界區(qū)，以保證多個線程不會同時訪問臨界區(qū)prev和curr:初值分為0和1的共享變量L是鎖intretval; intretval;L->acquire();

L->acquire();retval=curr; retval=curr;curr=curr+prev;curr=curr+prev;prev=retval; prev=retval;L->release(); L->release();共享內(nèi)存并行編程模型臨界區(qū)（criticalsection條件變量例：生產(chǎn)者/消費者問題一個典型的同步問題也稱有限緩沖區(qū)問題生產(chǎn)者向緩沖區(qū)中寫入

數(shù)據(jù)消費者從緩沖區(qū)取得數(shù)

據(jù)并對數(shù)據(jù)進行操作生產(chǎn)者和消費者并行執(zhí)

行共享內(nèi)存并行編程模型voidproducer(){//臨界區(qū)開始//產(chǎn)生下一個數(shù)據(jù)//臨界區(qū)結(jié)束}voidconsumer(){//臨界區(qū)開始//消費下一個數(shù)據(jù)//臨界區(qū)結(jié)束}條件變量共享內(nèi)存并行編程模型voidproducer()條件變量

右邊是生產(chǎn)者線程，條件變量C使用鎖L來完成對共享數(shù)據(jù)的訪問，可對條件變量C執(zhí)行3種原子操作（LC的初值為false）1.wait(L):釋放自身持有的鎖并處于C的等待隊列。執(zhí)行完畢時，鎖已被其他線程獲得共享內(nèi)存并行編程模型voidproducer(){

while(1){

L->acquire();//臨界區(qū)開始while(LC==true){C->wait(L);}//產(chǎn)生下一個數(shù)據(jù)LC=true;C->signal(L);//臨界區(qū)結(jié)束L->release();}}條件變量共享內(nèi)存并行編程模型voidproducer()條件變量

右邊是生產(chǎn)者線程，條件變量C使用鎖L來完成對共享數(shù)據(jù)的訪問，可對條件變量C執(zhí)行3種原子操作（LC的初值為false）2.signal(L):發(fā)信號，允許等待C的一個線程往下執(zhí)行。該操作完畢后，鎖仍然被發(fā)信號的線程持有共享內(nèi)存并行編程模型voidproducer(){

while(1){

L->acquire();//臨界區(qū)開始while(LC==true){

C->wait(L);}//產(chǎn)生下一個數(shù)據(jù)LC=true;

C->signal(L);//臨界區(qū)結(jié)束

L->release();}}條件變量共享內(nèi)存并行編程模型voidproducer()條件變量

右邊是生產(chǎn)者線程，條件變量C使用鎖L來完成對共享數(shù)據(jù)的訪問，可對條件變量C執(zhí)行3種原子操作（LC的初值為false）3.broadcast(L):發(fā)信號，允許所有等待C的線程往下執(zhí)行。該操作完畢后,鎖仍然被發(fā)信號的線程持有共享內(nèi)存并行編程模型voidproducer(){

while(1){

L->acquire();//臨界區(qū)開始while(LC==true){C->wait(L);}//產(chǎn)生下一個數(shù)據(jù)LC=true;

C->signal(L);//臨界區(qū)結(jié)束

L->release();}}條件變量共享內(nèi)存并行編程模型voidproducer()生產(chǎn)者/消費者問題voidproducer(){ voidconsumer(){while(1){ while(1){

L->acquire();

L->acquire(); //臨界區(qū)開始 //臨界區(qū)開始 while(LC==true){ while(LC==false){

C->wait(L);

C->wait(L); } } //產(chǎn)生下一個數(shù)據(jù) //消費下一個數(shù)據(jù) LC=true; LC=false;

C->signal(L);

C->signal(L); //臨界區(qū)結(jié)束 //臨界區(qū)結(jié)束

L->release();

L->release()}} }}共享內(nèi)存并行編程模型ConditonC;LockL;BooLLC=false;生產(chǎn)者/消費者問題共享內(nèi)存并行編程模型ConditonC;條件變量

條件變量本身實質(zhì)上并沒有需要檢驗的條件值，而是使用共享數(shù)據(jù)的狀態(tài)來保存線程的條件值，用于多線程之間關(guān)于共享數(shù)據(jù)狀態(tài)變化的通信當(dāng)特定條件滿足時，線程等待或者喚醒其他合作線程共享內(nèi)存并行編程模型voidproducer(){

while(1){ L->acquire();//臨界區(qū)開始while(LC==true){

C->wait(L);}//產(chǎn)生下一個數(shù)據(jù)LC=true;

C->signal(L);//臨界區(qū)結(jié)束

L->release();}}條件變量共享內(nèi)存并行編程模型voidproducer()死鎖

當(dāng)一個線程因等待另一個線程的資源而阻塞，而同時該資源永遠不會被釋放自死鎖或遞歸死鎖：線程T試圖獲得一個鎖，而該鎖已被線程T自己擁有錯序死鎖：線程T1占有資源r1并等待由線程T2占有資源r2；而線程T2占有資源r2并等待由線程T1占有資源r1編程中的問題：怎樣避免出現(xiàn)死鎖共享內(nèi)存并行編程模型死鎖共享內(nèi)存并行編程模型數(shù)據(jù)競爭

多個并行線程都訪問某個共享變量v，其中至少有一個線程修改v，并且這些線程沒有使用鎖來控制它們對v的訪問在有數(shù)據(jù)競爭的場合，各線程對數(shù)據(jù)的訪問次序是不確定的，計算結(jié)果依賴于這個次序數(shù)據(jù)競爭有時是共享數(shù)據(jù)和通信的一種方式，但多數(shù)情況下屬于程序錯誤

編程中的問題：怎樣發(fā)現(xiàn)程序中的數(shù)據(jù)競爭共享內(nèi)存并行編程模型數(shù)據(jù)競爭共享內(nèi)存并行編程模型消息傳遞消息傳遞是進程之間交換信息的一種方式，使用共享變量是另一種方式在消息傳遞場合下，由于一個消息在被接收者接收之前，必須由發(fā)送者發(fā)送，因此隱含了同步機制消息傳遞可以在分布式系統(tǒng)、共享內(nèi)存的多處理器系統(tǒng)和單處理器系統(tǒng)中實現(xiàn)。在分布式系統(tǒng)上實現(xiàn)共享變量有較大難度實現(xiàn)消息傳遞依靠兩個通信原語：send和receive消息傳遞并行編程模型消息傳遞消息傳遞并行編程模型消息傳遞的發(fā)送和接收對象進程對進程的傳遞：兩個進程不依賴于線程自行進行通信，是最常見的消息傳遞方式進程間的傳遞：屬于不同進程的線程之間進行通信進程內(nèi)的傳遞：屬于同一個進程的線程之間進行通信消息傳遞并行編程模型消息傳遞的發(fā)送和接收對象消息傳遞并行編程模型消息傳遞的同步與異步同步：消息發(fā)送后，發(fā)送者必須等待，直到接收者的響應(yīng)才能進行其他操作異步：發(fā)送者不必等待接收者的響應(yīng)就可以繼續(xù)執(zhí)行對于采用共享存儲模型的系統(tǒng)來說，消息傳遞必須是同步的對于采用分布式存儲模型的系統(tǒng)來說，消息傳遞則是異步的消息傳遞并行編程模型消息傳遞的同步與異步消息傳遞并行編程模型用消息傳遞機制解決生產(chǎn)者/消費者問題voidproducer(){ voidconsumer(){messagepmsg; messagecmsg;while(1){ while(1){ receive(cbox,pmsg); receive(pbox,cmsg); pmsg=produce(); consume(cmsg); send(pbox,pmsg); send(cbox,NULL);} }} }/*等待空消息、生產(chǎn) /*接收消息、消耗消

消息、發(fā)送消息*/ 息、發(fā)送空消息*/消息傳遞并行編程模型用消息傳遞機制解決生產(chǎn)者/消費者問題消息傳遞并行編程模型用消息傳遞機制解決生產(chǎn)者/消費者問題voidproducer(){ voidconsumer(){messagepmsg; messagecmsg;while(1){ while(1){ receive(cbox,pmsg); receive(pbox,cmsg); pmsg=produce(); consume(cmsg); send(pbox,pmsg); send(cbox,NULL);} }} }voidmain(){創(chuàng)建消息信箱pbox,cbox;

給cbox發(fā)NULL消息;創(chuàng)建進程producer和consumer;}消息傳遞并行編程模型用消息傳遞機制解決生產(chǎn)者/消費者問題消息傳遞并行編程模型小結(jié)本講座小結(jié)計算機體系結(jié)構(gòu)的多樣性，導(dǎo)致難以從它們概括出一種能代表它們的抽象機，并進一步抽象出統(tǒng)一的并行編程模型（即并行編程語言）更難做到的是：基于這種并行編程模型編寫的程序，通過編譯器和操作系統(tǒng)的支持，目標(biāo)程序運行時充分發(fā)揮各種體系結(jié)構(gòu)的長處通過對共享內(nèi)存和消息傳遞兩種并行編程模型的簡單介紹，遠未體現(xiàn)多核時代對并行軟件開發(fā)的各個方面（并行算法的設(shè)計和分析、程序的測試和調(diào)試、程序的分析和驗證）的挑戰(zhàn)小結(jié)本講座小結(jié)小結(jié)本講座小結(jié)并行編程模型（model）：是編寫可被編譯和運行的并行程序的一種模型并行編程模式（pattern）：是面向一類問題的并行程序的框架兩者被混用：常用編程模式中的主要機制經(jīng)常出現(xiàn)在編程模型中相關(guān)課程計算機體系結(jié)構(gòu)、操作系統(tǒng)、編譯原理、并行計算小結(jié)本講座小結(jié)小結(jié)研究方向怎樣從現(xiàn)代體系結(jié)構(gòu)抽象出計算模型面向體系結(jié)構(gòu)的編譯優(yōu)化并行程序的形式驗證方法小結(jié)研究方向多核體系結(jié)構(gòu)與并行編程模型

計算機科學(xué)導(dǎo)論第八講計算機科學(xué)技術(shù)學(xué)院陳意iyun@多核體系結(jié)構(gòu)與并行編程模型

計算機科學(xué)導(dǎo)論第八講計算機科學(xué)技課程內(nèi)容課程內(nèi)容圍繞學(xué)科理論體系中的模型理論,程序理論和計算理論1.模型理論關(guān)心的問題

給定模型M，哪些問題可以由模型M解決；如何比較模型的表達能力2.程序理論關(guān)心的問題給定模型M，如何用模型M解決問題包括程序設(shè)計范型、程序設(shè)計語言、程序設(shè)計、形式語義、類型論、程序驗證、程序分析等3.計算理論關(guān)心的問題

給定模型M和一類問題,解決該類問題需多少資源課程內(nèi)容課程內(nèi)容講座提綱基本知識多核體系結(jié)構(gòu)、并行編程模型內(nèi)存一致性模型嚴格一致性模型、順序一致性模型、內(nèi)存一致性模型的重要性共享內(nèi)存并行編程模型同步、鎖、臨界區(qū)、條件變量、死鎖、數(shù)據(jù)競爭消息傳遞并行編程模型消息傳遞、同步與異步講座提綱基本知識對稱多處理器對稱多處理器的體系結(jié)構(gòu)二級緩存內(nèi)存總線二級緩存二級緩存二級緩存一級緩存一級緩存一級緩存一級緩存處理器處理器處理器處理器基本知識必須在處理器的緩存中找到它操作的大部分數(shù)據(jù)，以保證性能

通過共享內(nèi)存來進行通信對稱多處理器二級內(nèi)存總線二級二級二級一級一級一級一級處理器處幾個概念的粗略解釋任務(wù)：一般性的抽象術(shù)語，指由軟件完成的一個活動。例如，矩陣分塊乘就是把矩陣乘分成多個任務(wù),以便于在對稱多處理器上并行執(zhí)行這些任務(wù)進程：任務(wù)在程序中的對應(yīng)物，它有自己的數(shù)據(jù)和代碼，需要在處理器上運行直至結(jié)束。進程是操作系統(tǒng)進行資源分配和調(diào)度的獨立單位線程：是把進程細分出現(xiàn)的實際運行單位，線程是進程中一段順序執(zhí)行的語句序列。把進程分成若干線程是為了提高進程執(zhí)行過程中的并行性。線程是操作系統(tǒng)調(diào)度的基本單位下面未嚴格區(qū)分進程和線程基本知識幾個概念的粗略解釋基本知識幾個概念的粗略解釋并行(parallel):多個可以同時執(zhí)行的任務(wù)，在多處理器上同時執(zhí)行并發(fā)(cuncorrent)：多個可以同時執(zhí)行的任務(wù)，在單處理器上交錯執(zhí)行

并發(fā)是邏輯上同時發(fā)生，而并行是物理上同時發(fā)生。下面不區(qū)分并行和并發(fā)基本知識tABtAB幾個概念的粗略解釋基本知識tAtA對稱多處理器對稱多處理器的體系結(jié)構(gòu)二級緩存內(nèi)存總線二級緩存二級緩存二級緩存一級緩存一級緩存一級緩存一級緩存處理器處理器處理器處理器基本知識多個高性能處理器可以集成在一塊芯片上對稱多處理器二級內(nèi)存總線二級二級二級一級一級一級一級處理器處基本知識單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu)執(zhí)行單元緩存CPU狀態(tài)中斷邏輯執(zhí)行單元緩存CPU狀態(tài)中斷邏輯執(zhí)行單元緩存CPU狀態(tài)中斷邏輯單核結(jié)構(gòu)多處理器結(jié)構(gòu)執(zhí)行單元緩存CPU狀態(tài)中斷邏輯CPU狀態(tài)中斷邏輯超線程結(jié)構(gòu)

超線程技術(shù)充分利用執(zhí)行單元中的空閑資源，以便在相同時間內(nèi)完成更多工作

執(zhí)行單元中的資源：內(nèi)存訪問部件、算術(shù)運算部件和浮點功能部件等基本知識單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu)執(zhí)行單元緩存CPU狀態(tài)中基本知識單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu)執(zhí)行單元緩存CPU狀態(tài)中斷邏輯執(zhí)行單元緩存CPU狀態(tài)中斷邏輯執(zhí)行單元緩存CPU狀態(tài)中斷邏輯單核結(jié)構(gòu)多處理器結(jié)構(gòu)執(zhí)行單元緩存CPU狀態(tài)中斷邏輯CPU狀態(tài)中斷邏輯超線程結(jié)構(gòu)

超線程技術(shù)本質(zhì)上就是多個線程共享一個執(zhí)行核

兩套CPU狀態(tài)+中斷邏輯是為了適應(yīng)兩個線程同時執(zhí)行的需要基本知識單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu)執(zhí)行單元緩存CPU狀態(tài)中基本知識單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu)共享緩存的多核體系結(jié)構(gòu)執(zhí)行單元緩存CPU狀態(tài)中斷邏輯執(zhí)行單元緩存CPU狀態(tài)中斷邏輯多核體系結(jié)構(gòu)執(zhí)行單元緩存CPU狀態(tài)中斷邏輯執(zhí)行單元CPU狀態(tài)中斷邏輯

多核處理器是把兩個甚至更多的獨立執(zhí)行核嵌入到一個處理器的內(nèi)部，每個線程都有完整的硬件執(zhí)行環(huán)境，各線程之間實現(xiàn)了真正意義上的并行基本知識單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu)共享緩存的多核體系結(jié)構(gòu)執(zhí)基本知識單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu)

體系結(jié)構(gòu)越來越復(fù)雜，若這些復(fù)雜的特征都要反映到編程語言中，才能寫出較好利用體系結(jié)構(gòu)優(yōu)點的程序，則編寫程序?qū)⑹呛芾щy的工作

需要設(shè)計好的編程模型并通過編譯器和操作系統(tǒng)的幫助和支持來解決采用超線程技術(shù)的多核體系結(jié)構(gòu)執(zhí)行單元緩存CPU狀態(tài)中斷邏輯CPU狀態(tài)中斷邏輯執(zhí)行單元緩存CPU狀態(tài)中斷邏輯CPU狀態(tài)中斷邏輯基本知識單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu)采用超線程技術(shù)的多核體系基本知識并行編程模型是底層體系結(jié)構(gòu)與上層應(yīng)用程序之間的橋梁向上隱藏并行處理器的細節(jié)，并向程序員提供表達并行的方法向下充分利用硬件資源，高效且正確地完成應(yīng)用需求任務(wù)劃分、任務(wù)映射、數(shù)據(jù)分布、通信和同步是設(shè)計并行編程模型時需要考慮的五個關(guān)鍵要素并行編程模型的另一種說法并行編程模型是編寫可被編譯和運行的并行程序的一種模型基本知識并行編程模型基本知識并行編程模型的分類1.按進程交互的機制來分共享內(nèi)存模型：進程共享可以異步地讀寫的全局數(shù)據(jù)空間消息傳遞模型:進程通過相互傳遞消息來交換數(shù)據(jù)隱式模型：進程之間交互是用戶不可訪問的2.按問題分解任務(wù)并行：每個處理器執(zhí)行不同的任務(wù)數(shù)據(jù)并行：把大任務(wù)分別成若干個相同的子任務(wù)3.……基本知識并行編程模型的分類內(nèi)存一致性模型內(nèi)存一致性模型描述的是，在有共享內(nèi)存的多處理器系統(tǒng)上，在它們讀寫共享內(nèi)存操作的可能執(zhí)行順序中，哪些順序是正確的內(nèi)存一致性模型是理解并行程序語義的一個關(guān)鍵為確保寫出正確的并行程序，程序員必須準確理解并行程序的語義隨著多核處理器的廣泛應(yīng)用，并行程序設(shè)計已經(jīng)由一種特殊的、只需少數(shù)高端技術(shù)人才掌握的技巧，變?yōu)橐环N大多數(shù)程序員都應(yīng)該掌握的基本技能內(nèi)存一致性模型內(nèi)存一致性模型內(nèi)存一致性模型嚴格一致性（原子一致性）模型

任何對內(nèi)存位置x的讀操作，得到的是最近一次對x的寫操作所寫入的值單處理器遵守嚴格一致性

下面,P1和P2是處理器,x是共享變量,初值是0。W(x)1表示:把1寫到x中；R(x)3表示:讀取x,得值3P1:W(x)1 P1: W(x)1P2:R(x)1R(x)1 P2:R(x)0R(x)1P1:W(x)1P2:R(x)0R(x)1ttt

左邊不符合嚴格一致性

多處理器+共享內(nèi)存時,會出現(xiàn)讀寫或?qū)憣懖僮鞯臎_突內(nèi)存一致性模型嚴格一致性（原子一致性）模型ttt左邊不符順序一致性模型比嚴格一致性弱的模型在多處理器共享內(nèi)存情況下，每個處理器執(zhí)行的單個線程嚴格按照程序規(guī)定的順序逐語句地進行內(nèi)存訪問操作比順序一致性還弱的統(tǒng)稱為弱內(nèi)存模型（不同情況有不同名稱）大多數(shù)程序員假定并行程序的運行滿足順序一致性，但現(xiàn)實中幾乎所有的并行程序都在某種弱內(nèi)存模型下運行，而且不同的并行語言和處理器的內(nèi)存模型不同內(nèi)存一致性模型順序一致性模型內(nèi)存一致性模型順序一致性模型例：互斥使用臨界區(qū)的并行線程

若兩個線程嚴格按照給出的語句順序逐條執(zhí)行，則它們能實現(xiàn)互斥功能，因為r1和r2不可能同時為0

現(xiàn)實中，編譯器和處理器內(nèi)部進行的優(yōu)化都會導(dǎo)致內(nèi)存操作的實際順序和代碼中的語句順序不一致,使得兩個條件判斷都為真，兩個線程都進入臨界區(qū)內(nèi)存一致性模型x和y:共享變量,初始:x=0,y=0x=1; y=1;r1=y; r2=x;if(r1==0){ if(r2==0){criticalregion criticalregion} }順序一致性模型內(nèi)存一致性模型x和y:共享變量,初始:x內(nèi)存一致性模型的重要性它作為系統(tǒng)實現(xiàn)和程序員之間的接口，對處理器體系結(jié)構(gòu)的實現(xiàn)、并行語言的實現(xiàn)、并行程序的開發(fā)和驗證都有重要意義以并行語言的設(shè)計和實現(xiàn)為例編譯器的優(yōu)化算法會調(diào)整源程序中的內(nèi)存操作順序，使得目標(biāo)程序和源程序的順序不一致目標(biāo)程序的執(zhí)行順序又可能被處理器進一步改變并行語言的設(shè)計和實現(xiàn)必須考慮到這兩種情況及其效果的疊加，對源程序可能表現(xiàn)出的行為進行準確描述(并行語言的內(nèi)存模型)，便于正確編程內(nèi)存一致性模型內(nèi)存一致性模型的重要性內(nèi)存一致性模型編程語言內(nèi)存一致性模型的現(xiàn)狀

由于優(yōu)化算法的多樣性，編程語言內(nèi)存模型比體系結(jié)構(gòu)的內(nèi)存模型復(fù)雜Gosling等為第一版Java語言給出的內(nèi)存一致性模型,無法支持常用的優(yōu)化算法,是一個失敗的模型Manson等給出的Java模型，雖被語言新標(biāo)準所采納，但模型十分晦澀，是Java語言中最復(fù)雜部分,極少有人能正確理解其含義Boehm和Adve試圖為C++提供一個簡單的模型，但很多地方有歧義或不清晰內(nèi)存一致性模型編程語言內(nèi)存一致性模型的現(xiàn)狀內(nèi)存一致性模型共享內(nèi)存并行編程模型使用共享內(nèi)存的錯誤例子并行計算Fibonacci序列下一個元素的兩個線程對兩個線程的執(zhí)行沒有任何約束下面是兩個線程某次并行時的語句執(zhí)行順序prev和curr:初值分為0和1的共享變量intretval; intretval;retval=curr; retval=curr;curr=curr+prev; curr=curr+prev; prev=retval;prev=retval;t共享內(nèi)存并行編程模型使用共享內(nèi)存的錯誤例子prev和curr共享內(nèi)存并行編程模型使用共享內(nèi)存的錯誤例子并行計算Fibonacci序列下一個元素的兩個線程對兩個線程的執(zhí)行沒有任何約束下面是兩個線程某次并行時的語句執(zhí)行順序prev和curr:初值分為0和1的共享變量intretval; intretval;retval=curr; retval=curr;curr=curr+prev; curr=curr+prev; prev=retval;prev=retval;t111111共享內(nèi)存并行編程模型使用共享內(nèi)存的錯誤例子prev和curr共享內(nèi)存并行編程模型使用共享內(nèi)存的錯誤例子并行計算Fibonacci序列下一個元素的兩個線程對兩個線程的執(zhí)行沒有任何約束下面是兩個線程某次并行時的語句執(zhí)行順序顯然結(jié)果不對原因：

對共享變量的訪問缺乏約束prev和curr:初值分為0和1的共享變量intretval; intretval;retval=curr; retval=curr;curr=curr+prev; curr=curr+prev; prev=retval;prev=retval;t111111共享內(nèi)存并行編程模型使用共享內(nèi)存的錯誤例子prev和curr共享內(nèi)存并行編程模型同步同步是對線程執(zhí)行的順序進行強行限制的一種機制，用來控制線程執(zhí)行的相對順序，可以有效解決任何線程之間的沖突，而這些沖突有可能會導(dǎo)致線程的執(zhí)行出現(xiàn)異常行為簡言之，同步主要用于協(xié)調(diào)線程執(zhí)行和管理共享數(shù)據(jù)同步機制信號量、鎖（又可細分成多種）、條件變量、…共享內(nèi)存并行編程模型同步共享內(nèi)存并行編程模型鎖用來體現(xiàn)一種互斥的并行控制策略一個線程在同一個時刻只能使用一個鎖，一個鎖至多由一個線程獲得。鎖有兩個原子操作：1.acquire:

等待鎖狀態(tài)變?yōu)槲醇渔i狀態(tài)，然后將其置為已加鎖狀態(tài)prev和curr:初值分為0和1的共享變量L是鎖intretval; intretval;L->acquire();

L->acquire();retval=curr; retval=curr;curr=curr+prev;curr=curr+prev;prev=retval; prev=retval;

共享內(nèi)存并行編程模型鎖prev和curr:初值分為0和1的共享內(nèi)存并行編程模型鎖用來體現(xiàn)一種互斥的并行控制策略一個線程在同一個時刻只能使用一個鎖，一個鎖至多由一個線程獲得。鎖有兩個原子操作：2.release:

將鎖狀態(tài)由已加鎖變?yōu)槲醇渔iprev和curr:初值分為0和1的共享變量L是鎖intretval; intretval;L->acquire();

L->acquire();retval=curr; retval=curr;curr=curr+prev;curr=curr+prev;prev=retval; prev=retval;L->release(); L->release();共享內(nèi)存并行編程模型鎖prev和curr:初值分為0和1的共享內(nèi)存并行編程模型臨界區(qū)（criticalsection）

指包含有共享變量的一段代碼，這些共享變量和多個線程之間存在相關(guān)關(guān)系

多線程編程的主要挑戰(zhàn)在于需要以多個線程執(zhí)行互斥操作的方式實現(xiàn)臨界區(qū)，以保證多個線程不會同時訪問臨界區(qū)prev和curr:初值分為0和1的共享變量L是鎖intretval; intretval;L->acquire();

L->acquire();retval=curr; retval=curr;curr=curr+prev;curr=curr+prev;prev=retval; prev=retval;L->release(); L->release();共享內(nèi)存并行編程模型臨界區(qū)（criticalsection條件變量例：生產(chǎn)者/消費者問題一個典型的同步問題也稱有限緩沖區(qū)問題生產(chǎn)者向緩沖區(qū)中寫入

數(shù)據(jù)消費者從緩沖區(qū)取得數(shù)

據(jù)并對數(shù)據(jù)進行操作生產(chǎn)者和消費者并行執(zhí)

行共享內(nèi)存并行編程模型voidproducer(){//臨界區(qū)開始//產(chǎn)生下一個數(shù)據(jù)//臨界區(qū)結(jié)束}voidconsumer(){//臨界區(qū)開始//消費下一個數(shù)據(jù)//臨界區(qū)結(jié)束}條件變量共享內(nèi)存并行編程模型voidproducer()條件變量

右邊是生產(chǎn)者線程，條件變量C使用鎖L來完成對共享數(shù)據(jù)的訪問，可對條件變量C執(zhí)行3種原子操作（LC的初值為false）1.wait(L):釋放自身持有的鎖并處于C的等待隊列。執(zhí)行完畢時，鎖已被其他線程獲得共享內(nèi)存并行編程模型voidproducer(){

while(1){

L->acquire();//臨界區(qū)開始while(LC==true){C->wait(L);}//產(chǎn)生下一個數(shù)據(jù)LC=true;C->signal(L);//臨界區(qū)結(jié)束L->release();}}條件變量共享內(nèi)存并行編程模型voidproducer()條件變量

右邊是生產(chǎn)者線程，條件變量C使用鎖L來完成對共享數(shù)據(jù)的訪問，可對條件變量C執(zhí)行3種原子操作（LC的初值為false）2.signal(L):發(fā)信號，允許等待C的一個線程往下執(zhí)行。該操作完畢后，鎖仍然被發(fā)信號的線程持有共享內(nèi)存并行編程模型voidproducer(){

while(1){

L->acquire();//臨界區(qū)開始while(LC==true){

C->wait(L);}//產(chǎn)生下一個數(shù)據(jù)LC=true;

C->signal(L);//臨界區(qū)結(jié)束

L->release();}}條件變量共享內(nèi)存并行編程模型voidproducer()條件變量

右邊是生產(chǎn)者線程，條件變量C使用鎖L來完成對共享數(shù)據(jù)的訪問，可對條件變量C執(zhí)行3種原子操作（LC的初值為false）3.broadcast(L):發(fā)信號，允許所有等待C的線程往下執(zhí)行。該操作完畢后,鎖仍然被發(fā)信號的線程持有共享內(nèi)存并行編程模型voidproducer(){

while(1){

L->acquire();//臨界區(qū)開始while(LC==true){C->wait(L);}//產(chǎn)生下一個數(shù)據(jù)LC=true;

C->signal(L);//臨界區(qū)結(jié)束

L->release();}}條件變量共享內(nèi)存并行編程模型voidproducer()生產(chǎn)者/消費者問題voidproducer(){ voidconsumer(){while(1){ while(1){

L->acquire();

L->acquire(); //臨界區(qū)開始 //臨界區(qū)開始 while(LC==true){ while(LC==false){

C->wait(L);

C->wait(L); } } //產(chǎn)生下一個數(shù)據(jù) //消費下一個數(shù)據(jù) LC=true; LC=false;

C->signal(L);

C->signal(L); //臨界區(qū)結(jié)束 //臨界區(qū)結(jié)束

L->release();

L->release()}} }}共享內(nèi)存并行編程模型ConditonC;LockL;BooLLC=false;生產(chǎn)者/消費者問題共享內(nèi)存并行編程模型ConditonC;條件變量

條件變量本身實質(zhì)上并沒有需要檢驗的條件值，而是使用共享數(shù)據(jù)的狀態(tài)來保存線程的條件值，用于多線程之間關(guān)于共享數(shù)據(jù)狀態(tài)變化的通信當(dāng)特定條件滿足時，線程等待或者喚醒其他合作線程共享內(nèi)存并行編程模型voidproducer(){

while(1){ L->acquire();//臨界區(qū)開始while(LC==true){

C->wait(L);}//產(chǎn)生下一個數(shù)據(jù)LC=true;

C->signal(L);//臨界區(qū)結(jié)束