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

1、多核體系結(jié)構(gòu)與并行多核體系結(jié)構(gòu)與并行編程編程模型模型計算機(jī)科學(xué)導(dǎo)論第八講計算機(jī)科學(xué)導(dǎo)論第八講計算機(jī)科學(xué)技術(shù)學(xué)院計算機(jī)科學(xué)技術(shù)學(xué)院陳意云陳意 http:/ 程程 內(nèi)內(nèi) 容容 課程內(nèi)容課程內(nèi)容圍繞學(xué)科理論體系中的模型理論圍繞學(xué)科理論體系中的模型理論, 程序理論和計算理論程序理論和計算理論1. 模型理論關(guān)心的問題模型理論關(guān)心的問題 給定模型給定模型M，哪些問題可以由模型，哪些問題可以由模型M解決；如何解決；如何比較模型的表達(dá)能力比較模型的表達(dá)能力2. 程序理論關(guān)心的問題程序理論關(guān)心的問題 給定模型給定模型M，如何用模型，如何用模型M解決問題解決問題 包括包括程序設(shè)計范型

2、、程序設(shè)計語言、程序設(shè)計、程序設(shè)計范型、程序設(shè)計語言、程序設(shè)計、形式語義、類型論、程序驗證、程序分析等形式語義、類型論、程序驗證、程序分析等3. 計算理論關(guān)心的問題計算理論關(guān)心的問題給定模型給定模型M和一類問題和一類問題, 解決該類問題需多少資源解決該類問題需多少資源2本講座概要介紹并行編程模本講座概要介紹并行編程模型及一些相關(guān)概念型及一些相關(guān)概念講講 座座 提提 綱綱 基本知識基本知識 多核體系結(jié)構(gòu)、并行編程模型多核體系結(jié)構(gòu)、并行編程模型 內(nèi)存一致性模型內(nèi)存一致性模型 嚴(yán)格一致性模型、順序一致性模型、內(nèi)存一致性嚴(yán)格一致性模型、順序一致性模型、內(nèi)存一致性模型的重要性模型的重要性 共享變量并行編

3、程模型共享變量并行編程模型 同步、鎖、臨界區(qū)、條件變量、死鎖、數(shù)據(jù)競爭同步、鎖、臨界區(qū)、條件變量、死鎖、數(shù)據(jù)競爭 消息傳遞并行編程模型消息傳遞并行編程模型 消息傳遞、同步與異步消息傳遞、同步與異步3 對稱多處理器對稱多處理器 對稱多處理器的體系結(jié)構(gòu)對稱多處理器的體系結(jié)構(gòu)二級二級緩存緩存內(nèi)存內(nèi)存總線總線二級二級緩存緩存二級二級緩存緩存二級二級緩存緩存一級一級緩存緩存一級一級緩存緩存一級一級緩存緩存一級一級緩存緩存處理器處理器處理器處理器處理器處理器處理器處理器基基 本本 知知 識識 必須在必須在處理器的處理器的緩存中找緩存中找到它操作到它操作的大部分的大部分?jǐn)?shù)據(jù)，以數(shù)據(jù)，以保證性能保證性能 通過

4、共通過共享內(nèi)存來享內(nèi)存來進(jìn)行通信進(jìn)行通信4 幾個概念的粗略解釋幾個概念的粗略解釋 任務(wù)：一般性的抽象術(shù)語，指由軟件完成的一個任務(wù)：一般性的抽象術(shù)語，指由軟件完成的一個活動。例如，矩陣分塊乘就是把矩陣乘分成多個活動。例如，矩陣分塊乘就是把矩陣乘分成多個任務(wù)任務(wù), 以便于在對稱多處理器上并行執(zhí)行這些任務(wù)以便于在對稱多處理器上并行執(zhí)行這些任務(wù) 進(jìn)程：任務(wù)在程序中的對應(yīng)物，它有自己的數(shù)據(jù)進(jìn)程：任務(wù)在程序中的對應(yīng)物，它有自己的數(shù)據(jù)和代碼，需要在處理器上運(yùn)行直至結(jié)束。進(jìn)程是和代碼，需要在處理器上運(yùn)行直至結(jié)束。進(jìn)程是操作系統(tǒng)為其進(jìn)行操作系統(tǒng)為其進(jìn)行資源分配和調(diào)度資源分配和調(diào)度的獨立單位的獨立單位 線程：是把

5、進(jìn)程細(xì)分出現(xiàn)的實際運(yùn)行單位，線程線程：是把進(jìn)程細(xì)分出現(xiàn)的實際運(yùn)行單位，線程是進(jìn)程中一段順序執(zhí)行的語句序列。把進(jìn)程分成是進(jìn)程中一段順序執(zhí)行的語句序列。把進(jìn)程分成若干線程是為了提高進(jìn)程執(zhí)行過程中的并行性。若干線程是為了提高進(jìn)程執(zhí)行過程中的并行性。線程是操作系統(tǒng)線程是操作系統(tǒng)調(diào)度調(diào)度的基本單位的基本單位 下面未嚴(yán)格區(qū)分進(jìn)程和線程下面未嚴(yán)格區(qū)分進(jìn)程和線程基基 本本 知知 識識5 幾個概念的粗略解釋幾個概念的粗略解釋 并行并行(parallel): 多個可以同時執(zhí)行的任務(wù)，在多處多個可以同時執(zhí)行的任務(wù)，在多處理器上同時執(zhí)行理器上同時執(zhí)行 并發(fā)并發(fā)(cuncorrent)：多個可以同時執(zhí)行的任務(wù)，在：多個

6、可以同時執(zhí)行的任務(wù)，在單處理器上交錯執(zhí)行單處理器上交錯執(zhí)行并發(fā)并發(fā)是邏輯上同時發(fā)生，而并行是邏輯上和物理是邏輯上同時發(fā)生，而并行是邏輯上和物理上都同時發(fā)生。下面不區(qū)分并行和并發(fā)上都同時發(fā)生。下面不區(qū)分并行和并發(fā)基基 本本 知知 識識tABtAB6 對稱多處理器對稱多處理器 對稱多處理器的體系結(jié)構(gòu)對稱多處理器的體系結(jié)構(gòu)二級二級緩存緩存內(nèi)存內(nèi)存總線總線二級二級緩存緩存二級二級緩存緩存二級二級緩存緩存一級一級緩存緩存一級一級緩存緩存一級一級緩存緩存一級一級緩存緩存處理器處理器處理器處理器處理器處理器處理器處理器基基 本本 知知 識識 多個高性能處理器多個高性能處理器可以集成在一塊芯片可以集成在一塊芯

7、片上上7基基 本本 知知 識識 單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu)單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu)執(zhí)行單元執(zhí)行單元 緩存緩存CPU狀態(tài)狀態(tài)中斷邏輯中斷邏輯執(zhí)行單元執(zhí)行單元 緩存緩存CPU狀態(tài)狀態(tài)中斷邏輯中斷邏輯執(zhí)行單元執(zhí)行單元 緩存緩存CPU狀態(tài)狀態(tài)中斷邏輯中斷邏輯單核結(jié)構(gòu)單核結(jié)構(gòu)多處理器結(jié)構(gòu)多處理器結(jié)構(gòu)執(zhí)行單元執(zhí)行單元 緩存緩存CPU狀態(tài)狀態(tài)中斷邏輯中斷邏輯CPU狀態(tài)狀態(tài)中斷邏輯中斷邏輯超線程結(jié)構(gòu)超線程結(jié)構(gòu) 超線程技術(shù)充分利用執(zhí)行超線程技術(shù)充分利用執(zhí)行單元中的空閑資源，以便在單元中的空閑資源，以便在相同時間內(nèi)完成更多工作相同時間內(nèi)完成更多工作 執(zhí)行單元中的資源：內(nèi)存執(zhí)行單元中的資源：內(nèi)存訪問部件、算術(shù)運(yùn)算部件和訪

8、問部件、算術(shù)運(yùn)算部件和浮點功能部件等浮點功能部件等8基基 本本 知知 識識 單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu)單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu)執(zhí)行單元執(zhí)行單元 緩存緩存CPU狀態(tài)狀態(tài)中斷邏輯中斷邏輯執(zhí)行單元執(zhí)行單元 緩存緩存CPU狀態(tài)狀態(tài)中斷邏輯中斷邏輯執(zhí)行單元執(zhí)行單元 緩存緩存CPU狀態(tài)狀態(tài)中斷邏輯中斷邏輯單核結(jié)構(gòu)單核結(jié)構(gòu)多處理器結(jié)構(gòu)多處理器結(jié)構(gòu)執(zhí)行單元執(zhí)行單元 緩存緩存CPU狀態(tài)狀態(tài)中斷邏輯中斷邏輯CPU狀態(tài)狀態(tài)中斷邏輯中斷邏輯超線程結(jié)構(gòu)超線程結(jié)構(gòu) 超線程技術(shù)本質(zhì)上就是多超線程技術(shù)本質(zhì)上就是多個線程共享一個執(zhí)行核個線程共享一個執(zhí)行核 兩套兩套CPU狀態(tài)狀態(tài) +中斷邏輯中斷邏輯是為了適應(yīng)兩個線程同時執(zhí)是為了適應(yīng)兩

9、個線程同時執(zhí)行的需要行的需要9基基 本本 知知 識識 單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu)單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu)共享緩存的多核體系結(jié)構(gòu)共享緩存的多核體系結(jié)構(gòu)執(zhí)行單元執(zhí)行單元 緩存緩存CPU狀態(tài)狀態(tài)中斷邏輯中斷邏輯執(zhí)行單元執(zhí)行單元 緩存緩存CPU狀態(tài)狀態(tài)中斷邏輯中斷邏輯多核體系結(jié)構(gòu)多核體系結(jié)構(gòu)執(zhí)行單元執(zhí)行單元緩緩 存存CPU狀態(tài)狀態(tài)中斷邏輯中斷邏輯執(zhí)行單元執(zhí)行單元CPU狀態(tài)狀態(tài)中斷邏輯中斷邏輯 多核處理器是多核處理器是把兩個甚至更多把兩個甚至更多的獨立執(zhí)行核嵌的獨立執(zhí)行核嵌入到一個處理器入到一個處理器的內(nèi)部，每個線的內(nèi)部，每個線程都有完整的硬程都有完整的硬件執(zhí)行環(huán)境，各件執(zhí)行環(huán)境，各線程之間實現(xiàn)了線程之間實現(xiàn)

10、了真正意義上的并真正意義上的并行行10基基 本本 知知 識識 單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu)單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu)體系結(jié)構(gòu)越來越復(fù)雜，若這些復(fù)雜的特征都要反體系結(jié)構(gòu)越來越復(fù)雜，若這些復(fù)雜的特征都要反映到編程語言中，才能寫出較好利用體系結(jié)構(gòu)優(yōu)點映到編程語言中，才能寫出較好利用體系結(jié)構(gòu)優(yōu)點的程序，則編寫程序?qū)⑹呛芾щy的工作的程序，則編寫程序?qū)⑹呛芾щy的工作需要設(shè)計好的編程模型并通過編譯器和操作系統(tǒng)需要設(shè)計好的編程模型并通過編譯器和操作系統(tǒng)的幫助和支持來解決的幫助和支持來解決采用超線程技術(shù)的多核體系結(jié)構(gòu)采用超線程技術(shù)的多核體系結(jié)構(gòu)執(zhí)行單元執(zhí)行單元緩存緩存CPU狀態(tài)狀態(tài)中斷邏輯中斷邏輯CPU狀態(tài)狀態(tài)中斷邏輯中

11、斷邏輯執(zhí)行單元執(zhí)行單元緩存緩存CPU狀態(tài)狀態(tài)中斷邏輯中斷邏輯CPU狀態(tài)狀態(tài)中斷邏輯中斷邏輯11基基 本本 知知 識識 并行編程模型并行編程模型 是底層體系結(jié)構(gòu)與上層應(yīng)用程序之間的橋梁是底層體系結(jié)構(gòu)與上層應(yīng)用程序之間的橋梁 向上隱藏并行處理器的細(xì)節(jié)，并向程序員提供表向上隱藏并行處理器的細(xì)節(jié)，并向程序員提供表達(dá)并行的方法達(dá)并行的方法 向下充分利用硬件資源，高效且正確地完成應(yīng)用向下充分利用硬件資源，高效且正確地完成應(yīng)用需求需求 任務(wù)劃分、任務(wù)映射、數(shù)據(jù)分布、通信和同步是任務(wù)劃分、任務(wù)映射、數(shù)據(jù)分布、通信和同步是設(shè)計并行編程模型時需要考慮的五個關(guān)鍵要素設(shè)計并行編程模型時需要考慮的五個關(guān)鍵要素并行編程模

12、型的另一種說法并行編程模型的另一種說法 并行編程模型是編寫可被編譯和運(yùn)行的并行程序并行編程模型是編寫可被編譯和運(yùn)行的并行程序的一種抽象并行機(jī)器模型的一種抽象并行機(jī)器模型12基基 本本 知知 識識 并行編程模型的分類并行編程模型的分類1. 按進(jìn)程交互的機(jī)制來分按進(jìn)程交互的機(jī)制來分 共享變量模型：進(jìn)程共享可以異步地讀寫的全局共享變量模型：進(jìn)程共享可以異步地讀寫的全局變量變量 消息傳遞模型消息傳遞模型: 進(jìn)程通過相互傳遞消息來交換數(shù)據(jù)進(jìn)程通過相互傳遞消息來交換數(shù)據(jù) 隱式模型：進(jìn)程之間交互是用戶不可訪問的隱式模型：進(jìn)程之間交互是用戶不可訪問的2. 按問題分解按問題分解 任務(wù)并行：每個處理器執(zhí)行不同的任

13、務(wù)任務(wù)并行：每個處理器執(zhí)行不同的任務(wù) 數(shù)據(jù)并行：把大任務(wù)分解成若干個相同的子任務(wù)數(shù)據(jù)并行：把大任務(wù)分解成若干個相同的子任務(wù)3. 13內(nèi)存一致性模型內(nèi)存一致性模型 并行計算給共享變量讀寫帶來的問題并行計算給共享變量讀寫帶來的問題串行程序串行程序并行程序并行程序 x的初值為的初值為0 x在共享存儲中，初值為在共享存儲中，初值為0 x = x + 1x = x + 1 | x = x + 2 x = x + 2 （注：（注：| 分隔兩段并行代碼）分隔兩段并行代碼）結(jié)果結(jié)果 ：x = 3 x可能但并非一定是可能但并非一定是3為什么？為什么？在一個進(jìn)程執(zhí)行在一個進(jìn)程執(zhí)行x = x +1期間，共享的期間，

14、共享的x有可能被有可能被其它進(jìn)程讀寫其它進(jìn)程讀寫14內(nèi)存一致性模型內(nèi)存一致性模型 并行計算給共享變量讀寫帶來的問題并行計算給共享變量讀寫帶來的問題并行程序并行程序 x = x + 1 | x = x + 2 x結(jié)果不等于結(jié)果不等于3的情況的情況x = R x = R x = RR+1 = R R+2 = R x = R R = x R+1 = R R = x R+2 = R R = x R = x結(jié)果：結(jié)果：x = 1 結(jié)果：結(jié)果：x = 2 x = x +1的執(zhí)行：取的執(zhí)行：取x到寄存器到寄存器R, R增增1, 把把R存到存到x 各處理器有各自的各處理器有各自的R，不共享；，不共享；x是共享

15、的是共享的15t內(nèi)存一致性模型內(nèi)存一致性模型 內(nèi)存一致性模型內(nèi)存一致性模型 內(nèi)存一致性模型內(nèi)存一致性模型(memory consistency model)描述描述程序員和系統(tǒng)之間的一種協(xié)議程序員和系統(tǒng)之間的一種協(xié)議。若程序員若程序員書寫的書寫的軟件軟件遵循內(nèi)存操作的專門規(guī)則，系統(tǒng)遵循內(nèi)存操作的專門規(guī)則，系統(tǒng)就就保證內(nèi)存保證內(nèi)存表現(xiàn)得有規(guī)律并且內(nèi)存操作的結(jié)果可預(yù)測表現(xiàn)得有規(guī)律并且內(nèi)存操作的結(jié)果可預(yù)測 專門規(guī)則描述的是，在有共享內(nèi)存的多處理器系專門規(guī)則描述的是，在有共享內(nèi)存的多處理器系統(tǒng)上，在它們讀寫共享內(nèi)存操作的可能執(zhí)行順序統(tǒng)上，在它們讀寫共享內(nèi)存操作的可能執(zhí)行順序中，哪些順序是正確的中，哪些

16、順序是正確的 有些模型的專門規(guī)則有些模型的專門規(guī)則對軟件只有少量限制，而有對軟件只有少量限制，而有些則使普通編程幾乎成為不可能。些則使普通編程幾乎成為不可能。規(guī)則規(guī)則限制少的限制少的模型沒有限制多的模型執(zhí)行效果好模型沒有限制多的模型執(zhí)行效果好16內(nèi)存一致性模型內(nèi)存一致性模型 內(nèi)存一致性模型內(nèi)存一致性模型 內(nèi)存一致性模型是理解并行程序語義的一個關(guān)鍵內(nèi)存一致性模型是理解并行程序語義的一個關(guān)鍵 為確保寫出正確的并行程序，程序員必須準(zhǔn)確理為確保寫出正確的并行程序，程序員必須準(zhǔn)確理解并行程序的語義解并行程序的語義 隨著多核處理器的廣泛應(yīng)用，并行程序設(shè)計已經(jīng)隨著多核處理器的廣泛應(yīng)用，并行程序設(shè)計已經(jīng)由一種

17、特殊的、只需少數(shù)高端技術(shù)人才掌握的技由一種特殊的、只需少數(shù)高端技術(shù)人才掌握的技巧，變?yōu)橐环N大多數(shù)程序員都應(yīng)該掌握的基本技巧，變?yōu)橐环N大多數(shù)程序員都應(yīng)該掌握的基本技能能17內(nèi)存一致性模型內(nèi)存一致性模型 嚴(yán)格一致性（原子一致性）模型嚴(yán)格一致性（原子一致性）模型一個進(jìn)程對一個進(jìn)程對任何內(nèi)存位置任何內(nèi)存位置x的讀操作，的讀操作，得到的是得到的是最近一次最近一次對對x的寫操作所寫入的值的寫操作所寫入的值 在在下面的圖示中下面的圖示中, P1和和P2是處理器是處理器, x的初值是的初值是0 W(x)1表示：把表示：把1寫到寫到x中中；R(x)3表示：表示：讀取讀取x，得到得到值值3P1: W(x)1 P1

18、: W(x)1P2: R(x)1 R(x)1 P2: R(x)0 R(x)1P1: W(x)1P2: R(x)0 R(x)1ttt 左下圖不符左下圖不符合嚴(yán)格一致性合嚴(yán)格一致性 18內(nèi)存一致性模型內(nèi)存一致性模型 嚴(yán)格一致性（原子一致性）模型嚴(yán)格一致性（原子一致性）模型一個進(jìn)程對一個進(jìn)程對任何內(nèi)存位置任何內(nèi)存位置x的讀操作，的讀操作，得到的是得到的是最近一次最近一次對對x的寫操作所寫入的值的寫操作所寫入的值 單處理器遵守嚴(yán)格一致性單處理器遵守嚴(yán)格一致性 在在多處理器多處理器+共享內(nèi)存的共享內(nèi)存的系統(tǒng)中，要實現(xiàn)嚴(yán)格系統(tǒng)中，要實現(xiàn)嚴(yán)格一致性模型幾乎是不可能的一致性模型幾乎是不可能的 19 順序一致性

19、模型順序一致性模型 比嚴(yán)格一致性弱的模型比嚴(yán)格一致性弱的模型 在多處理器共享內(nèi)存情況下，所有處理器的內(nèi)存在多處理器共享內(nèi)存情況下，所有處理器的內(nèi)存訪問操作都按照某個順序逐個執(zhí)行，并且每個處訪問操作都按照某個順序逐個執(zhí)行，并且每個處理器執(zhí)行的單個線程，嚴(yán)格按照程序規(guī)定的順序理器執(zhí)行的單個線程，嚴(yán)格按照程序規(guī)定的順序逐語句地進(jìn)行內(nèi)存訪問操作逐語句地進(jìn)行內(nèi)存訪問操作P1: W(x)1P2: W(x)2P3: R(x)2 R(x)1P4: R(x)2 R(x)1內(nèi)存一致性模型內(nèi)存一致性模型20tttt 左圖符合順序左圖符合順序一致性：一致性： W(x)2先于先于W(x)1發(fā)生發(fā)生 順序一致性模型順序一

20、致性模型 比嚴(yán)格一致性弱的模型比嚴(yán)格一致性弱的模型 在多處理器共享內(nèi)存情況下，所有處理器的內(nèi)存在多處理器共享內(nèi)存情況下，所有處理器的內(nèi)存訪問操作都按照某個順序逐個執(zhí)行，并且每個處訪問操作都按照某個順序逐個執(zhí)行，并且每個處理器執(zhí)行的單個線程，嚴(yán)格按照程序規(guī)定的順序理器執(zhí)行的單個線程，嚴(yán)格按照程序規(guī)定的順序逐語句地進(jìn)行內(nèi)存訪問操作逐語句地進(jìn)行內(nèi)存訪問操作P1: W(x)1P2: W(x)2P3: R(x)2 R(x)1P4: R(x)1 R(x)2內(nèi)存一致性模型內(nèi)存一致性模型21tttt 左圖不符合順左圖不符合順序一致性：序一致性： 不論不論W(x)1和和W(x)2誰先發(fā)生誰先發(fā)生 順序一致性模型

21、順序一致性模型 比嚴(yán)格一致性弱的模型比嚴(yán)格一致性弱的模型 在多處理器共享內(nèi)存情況下，所有處理器的內(nèi)存在多處理器共享內(nèi)存情況下，所有處理器的內(nèi)存訪問操作都按照某個順序逐個執(zhí)行，并且每個處訪問操作都按照某個順序逐個執(zhí)行，并且每個處理器執(zhí)行的單個線程，嚴(yán)格按照程序規(guī)定的順序理器執(zhí)行的單個線程，嚴(yán)格按照程序規(guī)定的順序逐語句地進(jìn)行內(nèi)存訪問操作逐語句地進(jìn)行內(nèi)存訪問操作 比順序一致性還弱的有多種弱內(nèi)存模型比順序一致性還弱的有多種弱內(nèi)存模型 大多數(shù)程序員假定并行程序的運(yùn)行滿足順序一致大多數(shù)程序員假定并行程序的運(yùn)行滿足順序一致性，但現(xiàn)實中幾乎所有的并行程序都在某種弱內(nèi)存性，但現(xiàn)實中幾乎所有的并行程序都在某種弱內(nèi)

22、存模型下運(yùn)行，而且不同的并行語言和處理器的內(nèi)存模型下運(yùn)行，而且不同的并行語言和處理器的內(nèi)存模型不同模型不同內(nèi)存一致性模型內(nèi)存一致性模型22 順序一致性模型順序一致性模型例：互斥使用臨例：互斥使用臨界區(qū)的并行線程界區(qū)的并行線程 若兩個線程嚴(yán)格按照給出的語句順序逐條執(zhí)行，若兩個線程嚴(yán)格按照給出的語句順序逐條執(zhí)行，則它們能實現(xiàn)互斥功能，因為則它們能實現(xiàn)互斥功能，因為r1和和r2不可能同時為不可能同時為0現(xiàn)實中，編譯器和處理器內(nèi)部進(jìn)行的優(yōu)化都會導(dǎo)現(xiàn)實中，編譯器和處理器內(nèi)部進(jìn)行的優(yōu)化都會導(dǎo)致內(nèi)存操作的實際順序和代碼中的語句順序不一致致內(nèi)存操作的實際順序和代碼中的語句順序不一致,例：上述兩線程的前兩個語句

23、被編譯器交換次序例：上述兩線程的前兩個語句被編譯器交換次序,使得兩個條件判斷都為真，兩個線程都進(jìn)入臨界區(qū)使得兩個條件判斷都為真，兩個線程都進(jìn)入臨界區(qū)內(nèi)存一致性模型內(nèi)存一致性模型x和和y: 共享變量共享變量, 初始初始:x = 0, y = 0 x = 1;y = 1;r1 = y;r2 = x;if (r1= 0)if (r2= 0) critical region critical region23r1 = y;x = 1; r2 = x;y = 1; t 內(nèi)存一致性模型的重要性內(nèi)存一致性模型的重要性 它作為系統(tǒng)實現(xiàn)和程序員之間的接口，對處理器它作為系統(tǒng)實現(xiàn)和程序員之間的接口，對處理器體系結(jié)

24、構(gòu)的實現(xiàn)、并行語言的設(shè)計和實現(xiàn)、并行體系結(jié)構(gòu)的實現(xiàn)、并行語言的設(shè)計和實現(xiàn)、并行程序的開發(fā)和驗證都有重要意義程序的開發(fā)和驗證都有重要意義以并行語言的設(shè)計和實現(xiàn)為例以并行語言的設(shè)計和實現(xiàn)為例 編譯器的優(yōu)化算法會調(diào)整源程序中的內(nèi)存操作順編譯器的優(yōu)化算法會調(diào)整源程序中的內(nèi)存操作順序，使得目標(biāo)程序和源程序的順序不一致序，使得目標(biāo)程序和源程序的順序不一致 目標(biāo)程序的執(zhí)行順序又可能被處理器進(jìn)一步改變目標(biāo)程序的執(zhí)行順序又可能被處理器進(jìn)一步改變 并行語言的設(shè)計和實現(xiàn)必須考慮到這兩種情況及并行語言的設(shè)計和實現(xiàn)必須考慮到這兩種情況及其效果的疊加，對源程序可能表現(xiàn)出的行為進(jìn)行其效果的疊加，對源程序可能表現(xiàn)出的行為進(jìn)行

25、準(zhǔn)確描述準(zhǔn)確描述(并行語言的內(nèi)存模型并行語言的內(nèi)存模型)，便于正確編程，便于正確編程內(nèi)存一致性模型內(nèi)存一致性模型24 編程語言內(nèi)存一致性模型的現(xiàn)狀編程語言內(nèi)存一致性模型的現(xiàn)狀由于優(yōu)化算法的多樣性，編程語言內(nèi)存模型比體由于優(yōu)化算法的多樣性，編程語言內(nèi)存模型比體系結(jié)構(gòu)的內(nèi)存模型復(fù)雜系結(jié)構(gòu)的內(nèi)存模型復(fù)雜 Gosling等為第一版等為第一版Java語言給出的內(nèi)存一致性模語言給出的內(nèi)存一致性模型型, 無法支持常用的優(yōu)化算法無法支持常用的優(yōu)化算法, 是一個失敗的模型是一個失敗的模型 Manson等給出的等給出的Java模型，雖被語言新標(biāo)準(zhǔn)所采模型，雖被語言新標(biāo)準(zhǔn)所采納，但模型十分晦澀，是納，但模型十分晦澀

26、，是Java語言中最復(fù)雜部分語言中最復(fù)雜部分, 極少有人能正確理解其含義極少有人能正確理解其含義 Boehm和和Adve試圖為試圖為C+提供一個簡單的模型，提供一個簡單的模型，但很多地方有歧義或不清晰但很多地方有歧義或不清晰內(nèi)存一致性模型內(nèi)存一致性模型25共享變量并行編程模型共享變量并行編程模型 使用共享變量的錯誤例子使用共享變量的錯誤例子 并行計算并行計算Fibonacci序列下一個元素的序列下一個元素的兩個線程兩個線程 對兩個線程的執(zhí)行沒有任何約束對兩個線程的執(zhí)行沒有任何約束 下面是兩個線程某次并行時的語句執(zhí)行順序下面是兩個線程某次并行時的語句執(zhí)行順序prev和和curr: 初值分為初值分

27、為0和和1的共享變量的共享變量int retval; int retval;retval = curr; retval = curr; curr = curr+prev; curr = curr+prev; prev = retval; prev = retval; t26共享變量并行編程模型共享變量并行編程模型 使用共享變量的錯誤例子使用共享變量的錯誤例子 并行計算并行計算Fibonacci序列下一個元素的序列下一個元素的兩個線程兩個線程 對兩個線程的執(zhí)行沒有任何約束對兩個線程的執(zhí)行沒有任何約束 下面是兩個線程某次并行時的語句執(zhí)行順序下面是兩個線程某次并行時的語句執(zhí)行順序prev和和curr

28、: 初值分為初值分為0和和1的共享變量的共享變量int retval; int retval;retval = curr; retval = curr; curr = curr+prev; curr = curr+prev; prev = retval; prev = retval; t11111127共享變量并行編程模型共享變量并行編程模型 使用共享變量的錯誤例子使用共享變量的錯誤例子 并行計算并行計算Fibonacci序列下一個元素的序列下一個元素的兩個線程兩個線程 對兩個線程的執(zhí)行沒有任何約束對兩個線程的執(zhí)行沒有任何約束 下面是兩個線程某次并行時的語句執(zhí)行順序下面是兩個線程某次并行時的語

29、句執(zhí)行順序 結(jié)果應(yīng)是結(jié)果應(yīng)是 0 +1 = 1 1 +1 = 2 原因：原因： 對共享變對共享變量的訪問缺量的訪問缺乏約束乏約束prev和和curr: 初值分為初值分為0和和1的共享變量的共享變量int retval; int retval;retval = curr; retval = curr; curr = curr+prev; curr = curr+prev; prev = retval; prev = retval; t11111128共享變量并行編程模型共享變量并行編程模型 同步同步 同步是對線程執(zhí)行的順序進(jìn)行強(qiáng)行限制的一種機(jī)同步是對線程執(zhí)行的順序進(jìn)行強(qiáng)行限制的一種機(jī)制，用來控制

30、線程執(zhí)行的相對順序，可以有效解制，用來控制線程執(zhí)行的相對順序，可以有效解決任何線程之間的沖突，而這些沖突有可能會導(dǎo)決任何線程之間的沖突，而這些沖突有可能會導(dǎo)致線程的執(zhí)行出現(xiàn)異常行為致線程的執(zhí)行出現(xiàn)異常行為 簡言之，同步主要用于協(xié)調(diào)線程執(zhí)行和管理共享簡言之，同步主要用于協(xié)調(diào)線程執(zhí)行和管理共享數(shù)據(jù)數(shù)據(jù) 同步機(jī)制同步機(jī)制 信號量、鎖（又可細(xì)分成多種）、條件變量、信號量、鎖（又可細(xì)分成多種）、條件變量、29共享變量并行編程模型共享變量并行編程模型 鎖鎖用來體現(xiàn)一種互斥的并行控制策略用來體現(xiàn)一種互斥的并行控制策略 一個線程在同一個時刻只能使用一個鎖，一個鎖一個線程在同一個時刻只能使用一個鎖，一個鎖至多由

31、一個線程獲得。鎖有兩個至多由一個線程獲得。鎖有兩個原子操作原子操作：1. acquire:prev和和curr: 初值分為初值分為0和和1的共享變量的共享變量L是鎖是鎖int retval; int retval;L-acquire(); L-acquire();retval = curr; retval = curr;curr = curr+prev; curr = curr+prev;prev = retval; prev = retval; 30 鎖狀態(tài)改鎖狀態(tài)改為為已加鎖已加鎖，若鎖已被占若鎖已被占用則等待，用則等待，鎖的狀態(tài)保鎖的狀態(tài)保持持未加鎖未加鎖 t共享變量并行編程模型共享變量

32、并行編程模型 鎖鎖用來體現(xiàn)一種互斥的并行控制策略用來體現(xiàn)一種互斥的并行控制策略 一個線程在同一個時刻只能使用一個鎖，一個鎖一個線程在同一個時刻只能使用一個鎖，一個鎖至多由一個線程獲得。鎖有兩個原子操作：至多由一個線程獲得。鎖有兩個原子操作：2. release: 將鎖狀態(tài)將鎖狀態(tài)由已加鎖變由已加鎖變?yōu)槲醇渔i為未加鎖prev和和curr: 初值分為初值分為0和和1的共享變量的共享變量L是鎖是鎖int retval; int retval;L-acquire(); L-acquire();retval = curr; retval = curr;curr = curr+prev; curr = c

33、urr+prev;prev = retval; prev = retval;L-release(); L-release(); 31t共享變量并行編程模型共享變量并行編程模型 鎖鎖用來體現(xiàn)一種互斥的并行控制策略用來體現(xiàn)一種互斥的并行控制策略 一個線程在同一個時刻只能使用一個鎖，一個鎖一個線程在同一個時刻只能使用一個鎖，一個鎖至多由一個線程獲得。鎖有兩個原子操作：至多由一個線程獲得。鎖有兩個原子操作：3. 問題問題怎么等待怎么等待? 忙等待：忙等待：不斷嘗試不斷嘗試 睡眠：睡眠： 等待喚醒等待喚醒prev和和curr: 初值分為初值分為0和和1的共享變量的共享變量L是鎖是鎖int retval;

34、 int retval;L-acquire(); L-acquire();retval = curr; retval = curr;curr = curr+prev; curr = curr+prev;prev = retval; prev = retval;L-release(); L-release(); 32t共享變量并行編程模型共享變量并行編程模型 臨界區(qū)（臨界區(qū)（critical section）指包含有共享變量的一段代碼，這些共享變量和指包含有共享變量的一段代碼，這些共享變量和多個線程之間存在相關(guān)關(guān)系多個線程之間存在相關(guān)關(guān)系多線程編程的主要挑戰(zhàn)在于需要以多個線程執(zhí)行多線程編程的主要

35、挑戰(zhàn)在于需要以多個線程執(zhí)行互斥操作的互斥操作的方式實現(xiàn)臨方式實現(xiàn)臨界區(qū)，以保界區(qū)，以保證多個線程證多個線程不會同時訪不會同時訪問臨界區(qū)問臨界區(qū)prev和和curr: 初值分為初值分為0和和1的共享變量的共享變量L是鎖是鎖int retval; int retval;L-acquire(); L-acquire();retval = curr; retval = curr;curr = curr+prev; curr = curr+prev;prev = retval; prev = retval;L-release(); L-release(); 33t 條件變量條件變量共享變量的一種實現(xiàn)方式

36、共享變量的一種實現(xiàn)方式例：生產(chǎn)者例：生產(chǎn)者/消費者問題消費者問題 一個典型的同步問題，一個典型的同步問題，也稱有限緩沖區(qū)問題也稱有限緩沖區(qū)問題 生產(chǎn)者向緩沖區(qū)中寫入生產(chǎn)者向緩沖區(qū)中寫入數(shù)據(jù)數(shù)據(jù) 消費者從緩沖區(qū)取得數(shù)消費者從緩沖區(qū)取得數(shù)據(jù)并對數(shù)據(jù)進(jìn)行操作據(jù)并對數(shù)據(jù)進(jìn)行操作 生產(chǎn)者和消費者并行執(zhí)行生產(chǎn)者和消費者并行執(zhí)行共享變量并行編程模型共享變量并行編程模型void producer() / 臨界區(qū)開始臨界區(qū)開始 / 產(chǎn)生下一個數(shù)據(jù)產(chǎn)生下一個數(shù)據(jù) / 臨界區(qū)結(jié)束臨界區(qū)結(jié)束void consumer() / 臨界區(qū)開始臨界區(qū)開始 / 消費下一個數(shù)據(jù)消費下一個數(shù)據(jù) / 臨界區(qū)結(jié)束臨界區(qū)結(jié)束34 條件變

37、量條件變量右邊是生產(chǎn)者線程，右邊是生產(chǎn)者線程，條條件變量件變量C使用使用鎖鎖L來完成來完成對共享數(shù)據(jù)的訪問，可對對共享數(shù)據(jù)的訪問，可對條件變量條件變量C執(zhí)行執(zhí)行3種原子種原子操作操作（LC 的初值為的初值為false）1. wait(L): 釋放自身持有釋放自身持有的鎖并處于的鎖并處于C的等待隊列。的等待隊列。該執(zhí)行完畢時，鎖已經(jīng)可該執(zhí)行完畢時，鎖已經(jīng)可被其他線程獲得被其他線程獲得共享變量并行編程模型共享變量并行編程模型void producer() while(1) L-acquire(); / 臨界區(qū)開始臨界區(qū)開始 while(LC = true) C-wait(L); / 產(chǎn)生下一個數(shù)據(jù)

38、產(chǎn)生下一個數(shù)據(jù) LC = true; C-signal(L); / 臨界區(qū)結(jié)束臨界區(qū)結(jié)束 L-release(); 35Conditon C; Lock L;Bool LC = false; 條件變量條件變量右邊是生產(chǎn)者線程，右邊是生產(chǎn)者線程，條條件變量件變量C使用使用鎖鎖L來完成來完成對共享數(shù)據(jù)的訪問，可對對共享數(shù)據(jù)的訪問，可對條件變量條件變量C執(zhí)行執(zhí)行3種原子種原子操作操作（LC 的初值為的初值為false）2. signal(L): 發(fā)信號，允許發(fā)信號，允許等待等待C的一個線程繼續(xù)執(zhí)的一個線程繼續(xù)執(zhí)行。該操作完畢后，鎖仍行。該操作完畢后，鎖仍然由發(fā)信號的線程持有然由發(fā)信號的線程持有共享變

39、量并行編程模型共享變量并行編程模型void producer() while(1) L-acquire(); / 臨界區(qū)開始臨界區(qū)開始 while(LC = true) C-wait(L); / 產(chǎn)生下一個數(shù)據(jù)產(chǎn)生下一個數(shù)據(jù) LC = true; C-signal(L); / 臨界區(qū)結(jié)束臨界區(qū)結(jié)束 L-release(); 36Conditon C; Lock L;Bool LC = false; 條件變量條件變量右邊是生產(chǎn)者線程，右邊是生產(chǎn)者線程，條條件變量件變量C使用使用鎖鎖L來完成來完成對共享數(shù)據(jù)的訪問，可對對共享數(shù)據(jù)的訪問，可對條件變量條件變量C執(zhí)行執(zhí)行3種原子種原子操作操作（LC 的

40、初值為的初值為false）3. broadcast(L): 發(fā)信號，發(fā)信號，允許所有等待允許所有等待C的線程繼續(xù)的線程繼續(xù)執(zhí)行。該操作完畢后執(zhí)行。該操作完畢后, 鎖鎖仍然由發(fā)信號的線程持有仍然由發(fā)信號的線程持有共享變量并行編程模型共享變量并行編程模型void producer() while(1) L-acquire(); / 臨界區(qū)開始臨界區(qū)開始 while(LC = true) C-wait(L); / 產(chǎn)生下一個數(shù)據(jù)產(chǎn)生下一個數(shù)據(jù) LC = true; C-broadcast(L); / 臨界區(qū)結(jié)束臨界區(qū)結(jié)束 L-release(); 37Conditon C; Lock L;Bool

41、LC = false; 生產(chǎn)者生產(chǎn)者/消費者問題消費者問題void producer() void consumer() while(1) while(1) L-acquire(); L-acquire(); / 臨界區(qū)開始臨界區(qū)開始 / 臨界區(qū)開始臨界區(qū)開始 while(LC = true) while(LC= false) C-wait(L); C-wait(L); / 產(chǎn)生下一個數(shù)據(jù)產(chǎn)生下一個數(shù)據(jù)/ 消費下一個數(shù)據(jù)消費下一個數(shù)據(jù) LC = true;LC = false; C-signal(L);C-signal(L); / 臨界區(qū)結(jié)束臨界區(qū)結(jié)束/ 臨界區(qū)結(jié)束臨界區(qū)結(jié)束 L-releas

42、e();L-release() 共享變量并行編程模型共享變量并行編程模型Conditon C; Lock L;Bool LC = false;38 條件變量條件變量 條件變量用于多線程之條件變量用于多線程之間關(guān)于共享數(shù)據(jù)狀態(tài)變化間關(guān)于共享數(shù)據(jù)狀態(tài)變化的通信。當(dāng)一個動作需要的通信。當(dāng)一個動作需要等另一個動作等另一個動作(改變共享數(shù)改變共享數(shù)據(jù)狀態(tài)據(jù)狀態(tài))完成后才能進(jìn)行，完成后才能進(jìn)行，就可以使用條件變量就可以使用條件變量 當(dāng)特定條件滿足時，線當(dāng)特定條件滿足時，線程等待或者喚醒其他合作程等待或者喚醒其他合作線程線程共享變量并行編程模型共享變量并行編程模型void producer() while(

43、1) L-acquire(); / 臨界區(qū)開始臨界區(qū)開始 while(LC = true) C-wait(L); / 產(chǎn)生下一個數(shù)據(jù)產(chǎn)生下一個數(shù)據(jù) LC = true; C-signal(L); / 臨界區(qū)結(jié)束臨界區(qū)結(jié)束 L-release(); 39 死鎖死鎖當(dāng)一線程因等待另一線程占用的資源而阻塞，而當(dāng)一線程因等待另一線程占用的資源而阻塞，而同時該資源永遠(yuǎn)不會被釋放同時該資源永遠(yuǎn)不會被釋放 自死鎖或遞歸死鎖：線程自死鎖或遞歸死鎖：線程T試圖獲得一個鎖，而試圖獲得一個鎖，而該鎖已被線程該鎖已被線程T自己擁有自己擁有 錯序死鎖：線程錯序死鎖：線程T1占有資源占有資源r1并等待由線程并等待由線程T

44、2占有占有資源資源r2；而線程；而線程T2占有資源占有資源r2并等待由線程并等待由線程T1占有占有資源資源r1編程中的問題：怎樣避免出現(xiàn)死鎖編程中的問題：怎樣避免出現(xiàn)死鎖共享變量并行編程模型共享變量并行編程模型40 數(shù)據(jù)競爭數(shù)據(jù)競爭多個并行線程都訪問某個共享變量多個并行線程都訪問某個共享變量v，其中至少有，其中至少有一個線程修改一個線程修改v ，并且這些線程沒有使用鎖來控制，并且這些線程沒有使用鎖來控制它們對它們對v的訪問的訪問 在有數(shù)據(jù)競爭的場合，各線程對數(shù)據(jù)的訪問次序在有數(shù)據(jù)競爭的場合，各線程對數(shù)據(jù)的訪問次序是不確定的，計算結(jié)果依賴于這個次序是不確定的，計算結(jié)果依賴于這個次序 數(shù)據(jù)數(shù)據(jù)競爭

45、有時是共享數(shù)據(jù)和通競爭有時是共享數(shù)據(jù)和通信信的一種方式的一種方式，但但多數(shù)情況下屬于程序錯誤多數(shù)情況下屬于程序錯誤 編程中的問題：怎樣發(fā)現(xiàn)程序中的數(shù)據(jù)競爭編程中的問題：怎樣發(fā)現(xiàn)程序中的數(shù)據(jù)競爭共享變量并行編程模型共享變量并行編程模型41 消息傳遞消息傳遞 消息傳遞是進(jìn)程之間交換信息的一種方式，使用消息傳遞是進(jìn)程之間交換信息的一種方式，使用共享變量是另一種方式共享變量是另一種方式 在消息傳遞場合下，由于一個消息在被接收者接在消息傳遞場合下，由于一個消息在被接收者接收之前，必須由發(fā)送者發(fā)送，因此隱含了同步機(jī)收之前，必須由發(fā)送者發(fā)送，因此隱含了同步機(jī)制制 消息傳遞可以在分布式系統(tǒng)、共享內(nèi)存的多處理消

46、息傳遞可以在分布式系統(tǒng)、共享內(nèi)存的多處理器系統(tǒng)和單處理器系統(tǒng)中實現(xiàn)器系統(tǒng)和單處理器系統(tǒng)中實現(xiàn)。在分布式系統(tǒng)上。在分布式系統(tǒng)上實現(xiàn)共享變量有較大難度實現(xiàn)共享變量有較大難度 實現(xiàn)消息傳遞依靠兩個通信原語：實現(xiàn)消息傳遞依靠兩個通信原語：send和和receive消息傳遞并行編程模型消息傳遞并行編程模型42 用消息傳遞機(jī)制解決生產(chǎn)者用消息傳遞機(jī)制解決生產(chǎn)者/消費者問題消費者問題void producer() void consumer() message pmsg; message cmsg; while (1) while (1) receive(cbox, pmsg); receive(pbox, cmsg); pmsg = produce(); consume(cmsg); send(pbox, pmsg); send(cbox, NULL); /* 等待空消息、生產(chǎn)等待空消息、生產(chǎn)/* 接收消息、消耗消接收消息、消耗消 消息、發(fā)送消息消息、發(fā)送消息 */ 息、發(fā)送空消息息、發(fā)送空消息 */消息傳遞并行編程模型消息傳遞并行編程模型43 用消息傳遞機(jī)制解決生產(chǎn)者用消息傳遞機(jī)制解決生產(chǎn)者/消費者問題消費者問題void producer() void consumer() message pmsg; message cmsg; while (1) while (1) receive(