多核體系結構與并行編程模型計算機科學導論第八講教學課件

多核體系結構與并行編程模型

計算機科學導論第八講計算機科學技術學院陳意iyun@多核體系結構與并行編程模型

計算機科學導論第八講計算機科學技課程內容課程內容圍繞學科理論體系中的模型理論,程序理論和計算理論1.模型理論關心的問題

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

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

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

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

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

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

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

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

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

體系結構越來越復雜，若這些復雜的特征都要反映到編程語言中，才能寫出較好利用體系結構優(yōu)點的程序，則編寫程序將是很困難的工作

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

任何對內存位置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

左邊不符合嚴格一致性

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

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

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

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

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

共享內存并行編程模型鎖prev和curr:初值分為0和1的共享內存并行編程模型鎖用來體現一種互斥的并行控制策略一個線程在同一個時刻只能使用一個鎖，一個鎖至多由一個線程獲得。鎖有兩個原子操作：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();共享內存并行編程模型鎖prev和curr:初值分為0和1的共享內存并行編程模型臨界區(qū)（criticalsection）

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

多線程編程的主要挑戰(zhàn)在于需要以多個線程執(zhí)行互斥操作的方式實現臨界區(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();共享內存并行編程模型臨界區(qū)（criticalsection條件變量例：生產者/消費者問題一個典型的同步問題也稱有限緩沖區(qū)問題生產者向緩沖區(qū)中寫入

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

據并對數據進行操作生產者和消費者并行執(zhí)

行共享內存并行編程模型voidproducer(){//臨界區(qū)開始//產生下一個數據//臨界區(qū)結束}voidconsumer(){//臨界區(qū)開始//消費下一個數據//臨界區(qū)結束}條件變量共享內存并行編程模型voidproducer()條件變量

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

while(1){

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

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

while(1){

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

C->wait(L);}//產生下一個數據LC=true;

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

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

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

while(1){

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

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

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

L->acquire();

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

C->wait(L);

C->wait(L); } } //產生下一個數據 //消費下一個數據 LC=true; LC=false;

C->signal(L);

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

L->release();

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

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

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

C->wait(L);}//產生下一個數據LC=true;

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

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

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

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

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

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

計算機科學導論第八講計算機科學技術學院陳意iyun@多核體系結構與并行編程模型

計算機科學導論第八講計算機科學技課程內容課程內容圍繞學科理論體系中的模型理論,程序理論和計算理論1.模型理論關心的問題

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

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

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

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

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

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

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

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

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

體系結構越來越復雜，若這些復雜的特征都要反映到編程語言中，才能寫出較好利用體系結構優(yōu)點的程序，則編寫程序將是很困難的工作

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

任何對內存位置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

左邊不符合嚴格一致性

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

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

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

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

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

共享內存并行編程模型鎖prev和curr:初值分為0和1的共享內存并行編程模型鎖用來體現一種互斥的并行控制策略一個線程在同一個時刻只能使用一個鎖，一個鎖至多由一個線程獲得。鎖有兩個原子操作：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();共享內存并行編程模型鎖prev和curr:初值分為0和1的共享內存并行編程模型臨界區(qū)（criticalsection）

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

多線程編程的主要挑戰(zhàn)在于需要以多個線程執(zhí)行互斥操作的方式實現臨界區(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();共享內存并行編程模型臨界區(qū)（criticalsection條件變量例：生產者/消費者問題一個典型的同步問題也稱有限緩沖區(qū)問題生產者向緩沖區(qū)中寫入

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

據并對數據進行操作生產者和消費者并行執(zhí)

行共享內存并行編程模型voidproducer(){//臨界區(qū)開始//產生下一個數據//臨界區(qū)結束}voidconsumer(){//臨界區(qū)開始//消費下一個數據//臨界區(qū)結束}條件變量共享內存并行編程模型voidproducer()條件變量

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

while(1){

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

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

while(1){

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

C->wait(L);}//產生下一個數據LC=true;

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

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

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

while(1){

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

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

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

L->acquire();

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

C->wait(L);

C->wait(L); } } //產生下一個數據 //消費下一個數據 LC=true; LC=false;

C->signal(L);

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

L->release();

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

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

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

C->wait(L);}//產生下一個數據LC=true;

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