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

多核體系結(jié)構(gòu)與并行編程模型 計(jì)算機(jī)科學(xué)導(dǎo)論第八講,計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 陳意云,課 程 內(nèi) 容,課程內(nèi)容 圍繞學(xué)科理論體系中的模型理論, 程序理論和計(jì)算理論 1. 模型理論關(guān)心的問(wèn)題 給定模型M，哪些問(wèn)題可以由模型M解決；如何比較模型的表達(dá)能力 2. 程序理論關(guān)心的問(wèn)題 給定模型M，如何用模型M解決問(wèn)題 包括程序設(shè)計(jì)范型、程序設(shè)計(jì)語(yǔ)言、程序設(shè)計(jì)、形式語(yǔ)義、類型論、程序驗(yàn)證、程序分析等 3. 計(jì)算理論關(guān)心的問(wèn)題 給定模型M和一類問(wèn)題, 解決該類問(wèn)題需多少資源,講 座 提 綱,基本知識(shí) 多核體系結(jié)構(gòu)、并行編程模型 內(nèi)存一致性模型 嚴(yán)格一致性模型、順序一致性模型、內(nèi)存一致性模型的重要性 共享內(nèi)存并行編程模型 同步、鎖、臨界區(qū)、條件變量、死鎖、數(shù)據(jù)競(jìng)爭(zhēng) 消息傳遞并行編程模型 消息傳遞、同步與異步,對(duì)稱多處理器 對(duì)稱多處理器的體系結(jié)構(gòu),基 本 知 識(shí),必須在處理器的緩存中找到它操作的大部分?jǐn)?shù)據(jù)，以保證性能,通過(guò)共 享內(nèi)存來(lái) 進(jìn)行通信,幾個(gè)概念的粗略解釋 任務(wù)：一般性的抽象術(shù)語(yǔ)，指由軟件完成的一個(gè)活動(dòng)。例如，矩陣分塊乘就是把矩陣乘分成多個(gè)任務(wù), 以便于在對(duì)稱多處理器上并行執(zhí)行這些任務(wù) 進(jìn)程：任務(wù)在程序中的對(duì)應(yīng)物，它有自己的數(shù)據(jù)和代碼，需要在處理器上運(yùn)行直至結(jié)束。進(jìn)程是操作系統(tǒng)進(jìn)行資源分配和調(diào)度的獨(dú)立單位 線程：是把進(jìn)程細(xì)分出現(xiàn)的實(shí)際運(yùn)行單位，線程是進(jìn)程中一段順序執(zhí)行的語(yǔ)句序列。把進(jìn)程分成若干線程是為了提高進(jìn)程執(zhí)行過(guò)程中的并行性。線程是操作系統(tǒng)調(diào)度的基本單位 下面未嚴(yán)格區(qū)分進(jìn)程和線程,基 本 知 識(shí),幾個(gè)概念的粗略解釋 并行(parallel): 多個(gè)可以同時(shí)執(zhí)行的任務(wù)，在多處理器上同時(shí)執(zhí)行 并發(fā)(cuncorrent)：多個(gè)可以同時(shí)執(zhí)行的任務(wù)，在單處理器上交錯(cuò)執(zhí)行 并發(fā)是邏輯上同時(shí)發(fā)生，而并行是物理上同時(shí)發(fā) 生。下面不區(qū)分并行和并發(fā),基 本 知 識(shí),對(duì)稱多處理器 對(duì)稱多處理器的體系結(jié)構(gòu),基 本 知 識(shí),多個(gè)高性能處理器可以集成在一塊芯片上,基 本 知 識(shí),單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu),單核結(jié)構(gòu),多處理器結(jié)構(gòu),超線程技術(shù)充分利用執(zhí)行單元中的空閑資源，以便在相同時(shí)間內(nèi)完成更多工作 執(zhí)行單元中的資源：內(nèi)存訪問(wèn)部件、算術(shù)運(yùn)算部件和浮點(diǎn)功能部件等,基 本 知 識(shí),單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu),單核結(jié)構(gòu),多處理器結(jié)構(gòu),超線程技術(shù)本質(zhì)上就是多個(gè)線程共享一個(gè)執(zhí)行核 兩套CPU狀態(tài) +中斷邏輯是為了適應(yīng)兩個(gè)線程同時(shí)執(zhí)行的需要,基 本 知 識(shí),單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu),共享緩存的多核體系結(jié)構(gòu),多核體系結(jié)構(gòu),多核處理器是把兩個(gè)甚至更多的獨(dú)立執(zhí)行核嵌入到一個(gè)處理器的內(nèi)部，每個(gè)線程都有完整的硬件執(zhí)行環(huán)境，各線程之間實(shí)現(xiàn)了真正意義上的并行,基 本 知 識(shí),單核結(jié)構(gòu)與多核系統(tǒng)結(jié)構(gòu) 體系結(jié)構(gòu)越來(lái)越復(fù)雜，若這些復(fù)雜的特征都要反 映到編程語(yǔ)言中，才能寫(xiě)出較好利用體系結(jié)構(gòu)優(yōu)點(diǎn) 的程序，則編寫(xiě)程序?qū)⑹呛芾щy的工作 需要設(shè)計(jì)好的編程模型并通過(guò)編譯器和操作系統(tǒng) 的幫助和支持來(lái)解決,基 本 知 識(shí),并行編程模型 是底層體系結(jié)構(gòu)與上層應(yīng)用程序之間的橋梁 向上隱藏并行處理器的細(xì)節(jié)，并向程序員提供表達(dá)并行的方法 向下充分利用硬件資源，高效且正確地完成應(yīng)用需求 任務(wù)劃分、任務(wù)映射、數(shù)據(jù)分布、通信和同步是設(shè)計(jì)并行編程模型時(shí)需要考慮的五個(gè)關(guān)鍵要素 并行編程模型的另一種說(shuō)法 并行編程模型是編寫(xiě)可被編譯和運(yùn)行的并行程序的一種模型,基 本 知 識(shí),并行編程模型的分類 1. 按進(jìn)程交互的機(jī)制來(lái)分 共享內(nèi)存模型：進(jìn)程共享可以異步地讀寫(xiě)的全局?jǐn)?shù)據(jù)空間 消息傳遞模型: 進(jìn)程通過(guò)相互傳遞消息來(lái)交換數(shù)據(jù) 隱式模型：進(jìn)程之間交互是用戶不可訪問(wèn)的 2. 按問(wèn)題分解 任務(wù)并行：每個(gè)處理器執(zhí)行不同的任務(wù) 數(shù)據(jù)并行：把大任務(wù)分別成若干個(gè)相同的子任務(wù) 3. ,內(nèi)存一致性模型,內(nèi)存一致性模型 描述的是，在有共享內(nèi)存的多處理器系統(tǒng)上，在它們讀寫(xiě)共享內(nèi)存操作的可能執(zhí)行順序中，哪些順序是正確的 內(nèi)存一致性模型是理解并行程序語(yǔ)義的一個(gè)關(guān)鍵 為確保寫(xiě)出正確的并行程序，程序員必須準(zhǔn)確理解并行程序的語(yǔ)義 隨著多核處理器的廣泛應(yīng)用，并行程序設(shè)計(jì)已經(jīng)由一種特殊的、只需少數(shù)高端技術(shù)人才掌握的技巧，變?yōu)橐环N大多數(shù)程序員都應(yīng)該掌握的基本技能,內(nèi)存一致性模型,嚴(yán)格一致性（原子一致性）模型 任何對(duì)內(nèi)存位置x的讀操作，得到的是最近一次對(duì) x的寫(xiě)操作所寫(xiě)入的值 單處理器遵守嚴(yán)格一致性 下面, P1和P2是處理器, x是共享變量, 初值是0。 W(x)1表示: 把1寫(xiě)到x中；R(x)3表示: 讀取x,得值3 P1: W(x)1 P1: W(x)1 P2: R(x)1 R(x)1 P2: R(x)0 R(x)1 P1: W(x)1 P2: R(x)0 R(x)1,t,t,t,左邊不符合嚴(yán)格一致性 多處理器+共享內(nèi)存時(shí), 會(huì)出現(xiàn)讀寫(xiě)或?qū)憣?xiě)操作的沖突,順序一致性模型 比嚴(yán)格一致性弱的模型 在多處理器共享內(nèi)存情況下，每個(gè)處理器執(zhí)行的單個(gè)線程嚴(yán)格按照程序規(guī)定的順序逐語(yǔ)句地進(jìn)行內(nèi)存訪問(wèn)操作 比順序一致性還弱的統(tǒng)稱為弱內(nèi)存模型（不同情況有不同名稱） 大多數(shù)程序員假定并行程序的運(yùn)行滿足順序一致 性，但現(xiàn)實(shí)中幾乎所有的并行程序都在某種弱內(nèi)存 模型下運(yùn)行，而且不同的并行語(yǔ)言和處理器的內(nèi)存 模型不同,內(nèi)存一致性模型,順序一致性模型 例：互斥使用臨 界區(qū)的并行線程 若兩個(gè)線程嚴(yán)格按照給出的語(yǔ)句順序逐條執(zhí)行， 則它們能實(shí)現(xiàn)互斥功能，因?yàn)閞1和r2不可能同時(shí)為0 現(xiàn)實(shí)中，編譯器和處理器內(nèi)部進(jìn)行的優(yōu)化都會(huì)導(dǎo) 致內(nèi)存操作的實(shí)際順序和代碼中的語(yǔ)句順序不一致, 使得兩個(gè)條件判斷都為真，兩個(gè)線程都進(jìn)入臨界區(qū),內(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 region ,內(nèi)存一致性模型的重要性 它作為系統(tǒng)實(shí)現(xiàn)和程序員之間的接口，對(duì)處理器體系結(jié)構(gòu)的實(shí)現(xiàn)、并行語(yǔ)言的實(shí)現(xiàn)、并行程序的開(kāi)發(fā)和驗(yàn)證都有重要意義 以并行語(yǔ)言的設(shè)計(jì)和實(shí)現(xiàn)為例 編譯器的優(yōu)化算法會(huì)調(diào)整源程序中的內(nèi)存操作順序，使得目標(biāo)程序和源程序的順序不一致 目標(biāo)程序的執(zhí)行順序又可能被處理器進(jìn)一步改變 并行語(yǔ)言的設(shè)計(jì)和實(shí)現(xiàn)必須考慮到這兩種情況及其效果的疊加，對(duì)源程序可能表現(xiàn)出的行為進(jìn)行準(zhǔn)確描述(并行語(yǔ)言的內(nèi)存模型)，便于正確編程,內(nèi)存一致性模型,編程語(yǔ)言內(nèi)存一致性模型的現(xiàn)狀 由于優(yōu)化算法的多樣性，編程語(yǔ)言內(nèi)存模型比體 系結(jié)構(gòu)的內(nèi)存模型復(fù)雜 Gosling等為第一版Java語(yǔ)言給出的內(nèi)存一致性模型, 無(wú)法支持常用的優(yōu)化算法, 是一個(gè)失敗的模型 Manson等給出的Java模型，雖被語(yǔ)言新標(biāo)準(zhǔn)所采納，但模型十分晦澀，是Java語(yǔ)言中最復(fù)雜部分, 極少有人能正確理解其含義 Boehm和Adve試圖為C+提供一個(gè)簡(jiǎn)單的模型，但很多地方有歧義或不清晰,內(nèi)存一致性模型,共享內(nèi)存并行編程模型,使用共享內(nèi)存的錯(cuò)誤例子 并行計(jì)算Fibonacci序列下一個(gè)元素的兩個(gè)線程 對(duì)兩個(gè)線程的執(zhí)行沒(méi)有任何約束 下面是兩個(gè)線程某次并行時(shí)的語(yǔ)句執(zhí)行順序,prev和curr: 初值分為0和1的共享變量 int retval; int retval; retval = curr; retval = curr; curr = curr+prev; curr = curr+prev; prev = retval; prev = retval;,t,共享內(nèi)存并行編程模型,使用共享內(nèi)存的錯(cuò)誤例子 并行計(jì)算Fibonacci序列下一個(gè)元素的兩個(gè)線程 對(duì)兩個(gè)線程的執(zhí)行沒(méi)有任何約束 下面是兩個(gè)線程某次并行時(shí)的語(yǔ)句執(zhí)行順序,prev和curr: 初值分為0和1的共享變量 int retval; int retval; retval = curr; retval = curr; curr = curr+prev; curr = curr+prev; prev = retval; prev = retval;,t,1,1,1,1,1,1,共享內(nèi)存并行編程模型,使用共享內(nèi)存的錯(cuò)誤例子 并行計(jì)算Fibonacci序列下一個(gè)元素的兩個(gè)線程 對(duì)兩個(gè)線程的執(zhí)行沒(méi)有任何約束 下面是兩個(gè)線程某次并行時(shí)的語(yǔ)句執(zhí)行順序 顯然結(jié)果 不對(duì) 原因： 對(duì)共享變 量的訪問(wèn)缺 乏約束,prev和curr: 初值分為0和1的共享變量 int retval; int retval; retval = curr; retval = curr; curr = curr+prev; curr = curr+prev; prev = retval; prev = retval;,t,1,1,1,1,1,1,共享內(nèi)存并行編程模型,同步 同步是對(duì)線程執(zhí)行的順序進(jìn)行強(qiáng)行限制的一種機(jī)制，用來(lái)控制線程執(zhí)行的相對(duì)順序，可以有效解決任何線程之間的沖突，而這些沖突有可能會(huì)導(dǎo)致線程的執(zhí)行出現(xiàn)異常行為 簡(jiǎn)言之，同步主要用于協(xié)調(diào)線程執(zhí)行和管理共享數(shù)據(jù) 同步機(jī)制 信號(hào)量、鎖（又可細(xì)分成多種）、條件變量、,共享內(nèi)存并行編程模型,鎖 用來(lái)體現(xiàn)一種互斥的并行控制策略 一個(gè)線程在同一個(gè)時(shí)刻只能使用一個(gè)鎖，一個(gè)鎖至多由一個(gè)線程獲得。鎖有兩個(gè)原子操作： 1. acquire: 等待鎖狀 態(tài)變?yōu)槲醇?鎖狀態(tài)，然 后將其置為 已加鎖狀態(tài),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;,共享內(nèi)存并行編程模型,鎖 用來(lái)體現(xiàn)一種互斥的并行控制策略 一個(gè)線程在同一個(gè)時(shí)刻只能使用一個(gè)鎖，一個(gè)鎖至多由一個(gè)線程獲得。鎖有兩個(gè)原子操作： 2. release: 將鎖狀態(tài) 由已加鎖變 為未加鎖,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();,共享內(nèi)存并行編程模型,臨界區(qū)（critical section） 指包含有共享變量的一段代碼，這些共享變量和 多個(gè)線程之間存在相關(guān)關(guān)系 多線程編程的主要挑戰(zhàn)在于需要以多個(gè)線程執(zhí)行 互斥操作的 方式實(shí)現(xiàn)臨 界區(qū)，以保 證多個(gè)線程 不會(huì)同時(shí)訪 問(wèn)臨界區(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();,條件變量 例：生產(chǎn)者/消費(fèi)者問(wèn)題 一個(gè)典型的同步問(wèn)題 也稱有限緩沖區(qū)問(wèn)題 生產(chǎn)者向緩沖區(qū)中寫(xiě)入 數(shù)據(jù) 消費(fèi)者從緩沖區(qū)取得數(shù) 據(jù)并對(duì)數(shù)據(jù)進(jìn)行操作 生產(chǎn)者和消費(fèi)者并行執(zhí) 行,共享內(nèi)存并行編程模型,void producer() / 臨界區(qū)開(kāi)始 / 產(chǎn)生下一個(gè)數(shù)據(jù) / 臨界區(qū)結(jié)束 void consumer() / 臨界區(qū)開(kāi)始 / 消費(fèi)下一個(gè)數(shù)據(jù) / 臨界區(qū)結(jié)束 ,條件變量 右邊是生產(chǎn)者線程，條 件變量C使用鎖L來(lái)完成 對(duì)共享數(shù)據(jù)的訪問(wèn)，可對(duì) 條件變量C執(zhí)行3種原子操 作（LC 的初值為false） 1. wait(L): 釋放自身持有 的鎖并處于C的等待隊(duì)列。 執(zhí)行完畢時(shí)，鎖已被其他 線程獲得,共享內(nèi)存并行編程模型,void producer() while(1) L-acquire(); / 臨界區(qū)開(kāi)始 while(LC = true) C-wait(L); / 產(chǎn)生下一個(gè)數(shù)據(jù) LC = true; C-signal(L); / 臨界區(qū)結(jié)束 L-release(); ,條件變量 右邊是生產(chǎn)者線程，條 件變量C使用鎖L來(lái)完成 對(duì)共享數(shù)據(jù)的訪問(wèn)，可對(duì) 條件變量C執(zhí)行3種原子操 作（LC 的初值為false） 2. signal(L): 發(fā)信號(hào)，允許 等待C的一個(gè)線程往下執(zhí) 行。該操作完畢后，鎖仍 然被發(fā)信號(hào)的線程持有,共享內(nèi)存并行編程模型,void producer() while(1) L-acquire(); / 臨界區(qū)開(kāi)始 while(LC = true) C-wait(L); / 產(chǎn)生下一個(gè)數(shù)據(jù) LC = true; C-signal(L); / 臨界區(qū)結(jié)束 L-release(); ,條件變量 右邊是生產(chǎn)者線程，條 件變量C使用鎖L來(lái)完成 對(duì)共享數(shù)據(jù)的訪問(wèn)，可對(duì) 條件變量C執(zhí)行3種原子操 作（LC 的初值為false） 3. broadcast(L): 發(fā)信號(hào)， 允許所有等待C的線程往 下執(zhí)行。該操作完畢后, 鎖 仍然被發(fā)信號(hào)的線程持有,共享內(nèi)存并行編程模型,void producer() while(1) L-acquire(); / 臨界區(qū)開(kāi)始 while(LC = true) C-wait(L); / 產(chǎn)生下一個(gè)數(shù)據(jù) LC = true; C-signal(L); / 臨界區(qū)結(jié)束 L-release(); ,生產(chǎn)者/消費(fèi)者問(wèn)題 void producer() void consumer() while(1) while(1) L-acquire(); L-acquire(); / 臨界區(qū)開(kāi)始 / 臨界區(qū)開(kāi)始 while(LC = true) while(LC= false) C-wait(L); C-wait(L); / 產(chǎn)生下一個(gè)數(shù)據(jù) / 消費(fèi)下一個(gè)數(shù)據(jù) LC = true; LC = false; C-signal(L); C-signal(L); / 臨界區(qū)結(jié)束 / 臨界區(qū)結(jié)束 L-release(); L-release() ,共享內(nèi)存并行編程模型,Conditon C; Lock L; BooL LC = false;,條件變量 條件變量本身實(shí)質(zhì)上 并沒(méi)有需要檢驗(yàn)的條件 值，而是使用共享數(shù)據(jù) 的狀態(tài)來(lái)保存線程的條 件值，用于多線程之間 關(guān)于共享數(shù)據(jù)狀態(tài)變化 的通信 當(dāng)特定條件滿足時(shí)， 線程等待或者喚醒其他 合作線程,共享內(nèi)存并行編程模型,void producer() while(1) L-acquire(); / 臨界區(qū)開(kāi)始 while(LC = true) C-wait(L); / 產(chǎn)生下一個(gè)數(shù)據(jù) LC = true; C-signal(L); / 臨界區(qū)結(jié)束 L-release(); ,死鎖 當(dāng)一個(gè)線程因等待另一個(gè)線程的資源而阻塞，而 同時(shí)該資源永遠(yuǎn)不會(huì)被釋放 自死鎖或遞歸死鎖：線程T試圖獲得一個(gè)鎖，而該鎖已被線程T自己擁有 錯(cuò)序死鎖：線程T1占有資源r1并等待由線程T2占有資源r2；而線程T2占有資源r2并等待由線程T1占有資源r1 編程中的問(wèn)題：怎樣避免出現(xiàn)死鎖,共享內(nèi)存并行編程模型,數(shù)據(jù)競(jìng)爭(zhēng) 多個(gè)并行線程都訪問(wèn)某個(gè)共享變量v，其中至少有 一個(gè)線程修改v ，并且這些線程沒(méi)有使用鎖來(lái)控制 它們對(duì)v的訪問(wèn) 在有數(shù)據(jù)競(jìng)爭(zhēng)的場(chǎng)合，各線程對(duì)數(shù)據(jù)的訪問(wèn)次序是不確定的，計(jì)算結(jié)果依賴于這個(gè)次序 數(shù)據(jù)競(jìng)爭(zhēng)有時(shí)是共享數(shù)據(jù)和通信的一種方式，但多數(shù)情況下屬于程序錯(cuò)誤 編程中的問(wèn)題：怎樣發(fā)現(xiàn)程序中的數(shù)據(jù)競(jìng)爭(zhēng),共享內(nèi)存并行編程模型,消息傳遞 消息傳遞是進(jìn)程之間交換信息的一種方式，使用共享變量是另一種方式 在消息傳遞場(chǎng)合下，由于一個(gè)消息在被接收者接收之前，必須由發(fā)送者發(fā)送，因此隱含了同步機(jī)制 消息傳遞可以在分布式系統(tǒng)、共享內(nèi)存的多處理器系統(tǒng)和單處理器系統(tǒng)中實(shí)現(xiàn)。在分布式系統(tǒng)上實(shí)現(xiàn)共享變量有較大難度 實(shí)現(xiàn)消息傳遞依靠?jī)蓚€(gè)通信原語(yǔ)：send和receive,消息傳遞并行編程模型,消息傳遞的發(fā)送和接收對(duì)象 進(jìn)程對(duì)進(jìn)程的傳遞：兩個(gè)進(jìn)程不依賴于線程自行進(jìn)行通信，是最常見(jiàn)的消息傳遞方式 進(jìn)程間的傳遞：屬于不同進(jìn)程的線程之間進(jìn)行通信 進(jìn)程內(nèi)的傳遞：屬于同一個(gè)進(jìn)程的線程之間進(jìn)行通信,消息傳遞并行編程模型,消息傳遞的同步與異步 同步：消息發(fā)送后，發(fā)送者必須等待，直到接收者的響應(yīng)才能進(jìn)行其他操作 異步：發(fā)送者不必等待接收者的響應(yīng)就可以繼續(xù)執(zhí)行 對(duì)于采用共享存儲(chǔ)模型的系統(tǒng)來(lái)說(shuō)，消息傳遞必須是同步的 對(duì)于采用分布式存儲(chǔ)模型的系統(tǒng)來(lái)說(shuō)，消息傳遞則是異步的,消息傳遞并行編程模型,用消息傳遞機(jī)制解決生產(chǎn)者/消費(fèi)者問(wèn)題 void producer() void consumer() message pmsg; message cmsg; while (1) while (1) receive(cbox, pmsg); receive(pbox, cmsg); pmsg = produce(); c