多處理器和線程級并行

第4章多處理器和線程級并行主要內(nèi)容1、簡介2、多處理器系統(tǒng)的Cache一致性1〕對稱式共享存儲器系統(tǒng)的Cache一致性2〕分布式共享存儲器系統(tǒng)的Cache一致性3、多處理器系統(tǒng)中同步機(jī)制4、本章小結(jié)簡介正如第三章提到的，由于開發(fā)ILP的空間正在減少，再加上對電源關(guān)注程度的增加，單處理器開展的速度正在逐步減少，這最終導(dǎo)致了計算機(jī)系統(tǒng)結(jié)構(gòu)的一個新時代的到來，即多處理器唱主角的時代。使用多個處理器來提高性能和增加可用性的思想應(yīng)追溯到最早的電子計算機(jī)。1966年Flynn提出了一種對所有計算機(jī)進(jìn)行分類的簡單模型，根據(jù)多處理器中限制要求最多的單元中的指令所調(diào)用的數(shù)據(jù)流和指令流的并行度，將計算機(jī)分為四類：1、單指令流，單數(shù)據(jù)流〔SISD〕：單處理器2、單指令流，多數(shù)據(jù)流〔SIMD〕：同一條指令被多個使用不同數(shù)據(jù)流的多處理器執(zhí)行。將相同的操作以并行的方式應(yīng)用于數(shù)據(jù)的各個項來實現(xiàn)數(shù)據(jù)級的并行。每個處理器有自己的數(shù)據(jù)存儲器，系統(tǒng)中有唯一的指令存儲器和控制存儲器，用來獲取和分配指令。3、多指令流，單數(shù)據(jù)流〔MISD〕：還不存在4、多指令流，多數(shù)據(jù)流〔MIMD〕：每個處理器取自己的指令并對自己的數(shù)據(jù)進(jìn)行操作，實現(xiàn)線程級并行。

使用多處理機(jī)的主要目的是利用多臺處理機(jī)并發(fā)地執(zhí)行一個作業(yè)，使得執(zhí)行速度比單處理機(jī)快；有時候，使用多處理機(jī)的主要目的是提高可靠性而不是高性能，如果某臺處理機(jī)出現(xiàn)故障，那么它的程序可以由系統(tǒng)中其它處理機(jī)來執(zhí)行。使用最多的就是MIMD多處理器，主要原因有兩個：1、靈活性強(qiáng)；2、能夠充分利用現(xiàn)有的微處理器的性價比優(yōu)勢。多處理器劃分的層次

按照組成規(guī)?？梢苑譃橐韵滤膫€層次：1、多核處理器2、中小規(guī)模多處理器3、大規(guī)模多處理器4、集群商業(yè)集群、客戶集群

多處理器的結(jié)構(gòu)根據(jù)存儲器組織方式分為兩類：1、集中式共享存儲器系統(tǒng)結(jié)構(gòu)存儲器一級或多級Cache圖4-1集中式共享存儲器的基本結(jié)構(gòu)處理器I/O系統(tǒng)一級或多級Cache處理器一級或多級Cache處理器一級或多級Cache處理器這種結(jié)構(gòu)只有一個存儲器，它對每個處理器而言都是對等的，每個處理器的訪問時間相同，因此也稱為對稱共享存儲器多處理器系統(tǒng)〔SMPS〕,這種系統(tǒng)結(jié)構(gòu)也稱為均勻存儲器訪問〔UMA〕。集中式共享存儲器多處理器系統(tǒng)的優(yōu)點(diǎn)是：〔1〕可以與傳統(tǒng)的單處理器系統(tǒng)軟件兼容?！?〕程序設(shè)計容易?！?〕通信開銷小。缺點(diǎn)是:集中式共享存儲器的結(jié)構(gòu)組成的處理器不能太多，主要受到訪存沖突和互聯(lián)網(wǎng)絡(luò)的帶寬和復(fù)雜性的限制2、分布式存儲器系統(tǒng)結(jié)構(gòu)圖4-2分布式存儲器多處理器的基本結(jié)構(gòu)處理器+CacheI/O存儲器處理器+CacheI/O存儲器處理器+CacheI/O存儲器處理器+CacheI/O存儲器處理器+CacheI/O存儲器處理器+CacheI/O存儲器處理器+CacheI/O存儲器處理器+CacheI/O存儲器互連網(wǎng)絡(luò)分布式存儲器的主要優(yōu)點(diǎn)是：〔1〕如果大局部訪存是對節(jié)點(diǎn)內(nèi)的本地存儲器進(jìn)行的，這樣做是增大存儲器帶寬的比較經(jīng)濟(jì)的方法；〔2〕縮短了本地存儲器訪問的時延；〔3〕具有較好的擴(kuò)展性。缺點(diǎn)是：由于處理器不再共享單一集中存儲器，處理器間的數(shù)據(jù)通信在某種程度上變得更加復(fù)雜，且時延也更大。通信和存儲器系統(tǒng)結(jié)構(gòu)模型根據(jù)處理器間傳遞數(shù)據(jù)所用的方法，有兩種不同的系統(tǒng)結(jié)構(gòu)分布式共享存儲器〔DSM〕系統(tǒng)物理上分開的存儲器能夠作為邏輯上共享的地址空間進(jìn)行尋址，即兩個處理器中相同的物理地址指向存儲器中的同一個位置。通過load和store操作在統(tǒng)一的地址空間上隱式地傳遞數(shù)據(jù)。消息傳遞多處理器系統(tǒng)各個處理器都有自己的私有地址空間，它們在邏輯上分散，相互獨(dú)立，不能被遠(yuǎn)程處理器尋址。兩個不同處理器中相同的物理地址分別指向兩個不同存儲器中的不同位置。數(shù)據(jù)通信往往通過顯式地在處理器之間傳遞消息來完成。〔集群就是使用消息傳遞的一類系統(tǒng)〕多處理器并行處理遇到的挑戰(zhàn)第一個障礙是程序可獲得并行度是有限的，這導(dǎo)致并行處理器很難得到較高的性價比。第二個障礙來自于通信相對較高的開銷，這主要與并行處理器中遠(yuǎn)程訪問的時延較長有關(guān)。要解決這兩個問題，一是在軟件中采用更好的并行算法來提高并行度。二是改進(jìn)系統(tǒng)結(jié)構(gòu)，如在硬件上緩存共享數(shù)據(jù)，在確保存儲器一致性的前提下，使用Cache來減少遠(yuǎn)程訪問頻率。三是在軟件上重新構(gòu)造數(shù)據(jù)來盡可能增加本地訪問。此外，還可以使用多線程或預(yù)取技術(shù)來減少時延的影響。多處理器系統(tǒng)的Cache一致性1、對稱式共享存儲器系統(tǒng)結(jié)構(gòu)2、什么是多處理器的Cache一致性3、對稱式基于監(jiān)聽協(xié)議實現(xiàn)Cache一致性4、分布式基于目錄協(xié)議實現(xiàn)Cache一致性1、對稱式共享存儲器系統(tǒng)結(jié)構(gòu)

系統(tǒng)結(jié)構(gòu)圖如圖4-1所示，對稱式共享存儲器系統(tǒng)支持共享和私有數(shù)據(jù)的緩存，私有數(shù)據(jù)被單個處理器使用，而共享數(shù)據(jù)那么被多個處理器使用，根本上是通過讀寫共享數(shù)據(jù)完成處理器之間的通信。把一個私有數(shù)據(jù)緩存之后，對該數(shù)據(jù)的訪問就可以在Cache中形成副本，這樣做除了會減少訪問時延和降低對存儲器帶寬的要求外，還能減少多個處理器同時讀取共享數(shù)據(jù)時的競爭現(xiàn)象。然而，把共享數(shù)據(jù)放入Cache又出現(xiàn)了一個新的問題：Cache一致性。2、什么是多處理器的Cache一致性所謂多處理器的Cache一致性問題，是指由于緩存共享數(shù)據(jù)，兩個不同的處理器所保存的存儲器視圖可能是通過各自的Cache得到的。因此，如果沒有其它的防范措施，那么會導(dǎo)致兩個處理器分別得到兩個不同的值。下面看一個例子來理解假設(shè)最初兩個Cache都不包含該變量而且X的值是1.當(dāng)X得值被A改寫后，A的Cache和存儲器中的副本都做了更新，但B中的Cache那么沒有，如果B讀取X，得到的值是1.表1Cache一致性問題一般情況下，如果在一個存儲器系統(tǒng)中讀取一個數(shù)據(jù)項的返回結(jié)果總是最近寫入的數(shù)值，那么就可以認(rèn)為該存儲器具有一致性。這包括了存儲器系統(tǒng)行為的兩個方面，一是一致性〔coherence〕，另一個是連貫性〔consistency〕。一致性要滿足三個性質(zhì)：1〕程序要順序執(zhí)行；2〕兩個操作間保證足夠的時間；3〕對同一個的地址的寫操作是串行執(zhí)行的。雖然上述的三個性質(zhì)足以保證一致性，但寫入的數(shù)據(jù)什么時候才可以讀取也是至關(guān)重要的，這就聯(lián)系到存儲器的連貫性。連貫性是指被一個處理器修改正的值，在何時可以被另一個處理器訪問。一致性和連貫性是互補(bǔ)的：一致性定義了對同一個存儲器地址進(jìn)行的讀寫操作行為，而連貫性定義了關(guān)于訪問其他存儲器地址的讀寫操作。3、對稱式實現(xiàn)Cache一致性用于維護(hù)多個處理器一致性的協(xié)議稱為Cache一致性協(xié)議〔cache-coherenceprotocols〕,實現(xiàn)時關(guān)鍵在于跟蹤所有共享數(shù)據(jù)塊的狀態(tài)。對稱式共享存儲器系統(tǒng)采用監(jiān)聽協(xié)議跟蹤共享數(shù)據(jù)。監(jiān)聽式：每個含有物理存儲器中數(shù)據(jù)塊副本的cache還要保存該數(shù)據(jù)塊共享狀態(tài)的副本。各個處理器上的Cache控制器對總線進(jìn)行監(jiān)視或監(jiān)聽，來確定它們是否含有總線或交換機(jī)上請求的數(shù)據(jù)塊的副本。監(jiān)聽協(xié)議的實現(xiàn)方法：1〕寫無效協(xié)議：處理器寫數(shù)據(jù)前保證該處理器能獨(dú)占地訪問數(shù)據(jù)項，所有的其他處理器中的副本無效。對寫直達(dá)，也更新存儲器的副本，結(jié)果只有一個cache和存儲器中的副本有效；對寫回，存儲器中的副本也失效，只有一個cache中的副本有效。2〕寫更新或?qū)懖ニ蛥f(xié)議：寫入數(shù)據(jù)項時更新該數(shù)據(jù)項的所有副本。對寫直達(dá)，也更新存儲器中的副本；

對寫回，存儲器中的副本更新延遲到這個cache被置換的時刻。該協(xié)議要求必須將所有的寫播送給共享Cache，所以需要更大的帶寬。故近期的多處理器都選擇執(zhí)行寫無效協(xié)議。寫無效協(xié)議實現(xiàn)的技術(shù)關(guān)鍵是使用總線或其他播送媒介來完成無效操作。處理器只要取得總線的控制權(quán)然后在總線上播送無效數(shù)據(jù)的地址即可。當(dāng)多個處理器同時對一個共享塊進(jìn)行操作時要經(jīng)過總線的仲裁實現(xiàn)串行化。例：使用寫回式Cache，假設(shè)兩個Cache最初都沒有X，并且存儲器中的X的值為0.處理器和存儲器中的內(nèi)容是在處理器和總線活動全部完成后的數(shù)值。空格表示沒有動作或沒有存放副本。表2監(jiān)聽總線方式的寫無效協(xié)議實例對稱式共享存儲器多處理器和監(jiān)聽協(xié)議的局限性隨著多處理器中處理器數(shù)目的增加，或是處理器對存儲器要求的增加，系統(tǒng)的任何集中式資源都會變成“瓶頸〞。在最簡單的基于總線的多處理器的例子中，總線必須同時支持一致性通信和由于Cache導(dǎo)致的存儲器通信。同樣，如果只有一個存儲器部件，它就必須處理所有的處理器請求。隨著處理器在過去幾年的飛速開展，單獨(dú)一條總線或單獨(dú)一個物理存儲器所能支持的處理器數(shù)量正在下降。監(jiān)聽協(xié)議的Cache一致性通信限制了處理器的擴(kuò)展和速度。4、分布式基于目錄協(xié)議實現(xiàn)Cache一致性分布式共享存儲器系統(tǒng)結(jié)構(gòu)圖如圖4-2所示，通過分配存儲器的方式來增加存儲器帶寬和互聯(lián)帶寬，可以將本地存儲器通信和遠(yuǎn)程通信迅速分開，減少了對存儲器系統(tǒng)和互聯(lián)網(wǎng)絡(luò)的帶寬要求。要充分利用分布式存儲器帶來的好處，就要消除一致性協(xié)議對每個Cache缺失都要播送的需求，這就產(chǎn)生了目錄協(xié)議。所謂目錄式協(xié)議，是指把物理存儲器的共享狀態(tài)存放在一個地點(diǎn)，稱之為目錄。目錄表中每項保存了每個Cache數(shù)據(jù)塊的使用情況。為了防止訪問目錄表成為瓶頸，需要使目錄隨存儲器分布。分布目錄使得數(shù)據(jù)塊的共享狀態(tài)總是位于一個的地點(diǎn)。正是這個特性防止了一致性協(xié)議中的播送。圖4-3各個節(jié)點(diǎn)帶有目錄的分布式存儲器多處理器系統(tǒng)的基本結(jié)構(gòu)處理器+CacheI/O存儲器處理器+CacheI/O存儲器目錄目錄處理器+CacheI/O存儲器處理器+CacheI/O存儲器目錄目錄處理器+CacheI/O存儲器處理器+CacheI/O存儲器目錄目錄處理器+CacheI/O存儲器處理器+CacheI/O存儲器目錄目錄互連網(wǎng)絡(luò)基于目錄的Cache一致性協(xié)議根底知識目錄協(xié)議也必須實現(xiàn)兩個根本操作：處理讀缺失和處理共享未修改Cache塊的寫操作〔處理共享數(shù)據(jù)塊的寫缺失由這兩個操作簡單組合而成〕。一般目錄表中記錄的Cache數(shù)據(jù)塊的狀態(tài)主要有：共享：一個或多個處理器擁有Cache的數(shù)據(jù)塊，并且存儲器中的數(shù)值也是最新的。未緩存：沒有任何一個處理器含有該數(shù)據(jù)塊的副本。修改：只有一個處理器擁有該Cache數(shù)據(jù)塊的正確副本并且對該塊執(zhí)行過寫操作，因此其它存儲器中與之對應(yīng)的副本是無效的。這個處理器成為該塊的所有者。無效：由于某個處理器執(zhí)行寫操作，使得本處理器含有該數(shù)據(jù)塊的副本被標(biāo)記為無效狀態(tài)。設(shè)置無效狀態(tài)的最簡單的方法是為每個存儲器保存一個位向量。當(dāng)塊處于共享狀態(tài)時，向量的每一位表示索對應(yīng)的處理器是否擁有該塊的副本。當(dāng)塊處于獨(dú)占狀態(tài)時，可以利用位向量來跟蹤塊的所有者。目錄表的具體作法可分為3種全映象目錄表法

有限目錄表法鏈?zhǔn)侥夸洷矸▋煞N協(xié)議的比較目錄式協(xié)議的實現(xiàn)要占據(jù)一些存儲空間，比監(jiān)聽式協(xié)議的開銷略微偏高，但是可以用來擴(kuò)展更多的處理器，很適合于分布式共享存儲器系統(tǒng)。監(jiān)聽式協(xié)議要求處理器在修改數(shù)據(jù)塊時向所有處理器播送Cache缺失的信息，這種方法實現(xiàn)簡單，但也限制了其擴(kuò)展性。多處理器系統(tǒng)中同步機(jī)制根本硬件原語用一致性實現(xiàn)鎖多線程同步機(jī)制帶來的問題根本硬件原語實現(xiàn)多處理器系統(tǒng)同步的關(guān)鍵是要有一個能夠以原子方式對存儲器執(zhí)行讀寫操作的硬件原語集合。硬件原語可有多種不同的形式，但都必須支持原子方式的讀寫操作，并能夠返回操作是否成功的信息。這些硬件原語是構(gòu)造多種不同的用戶層同步操作的根本構(gòu)件，比方鎖和屏障等。一般來說，硬件原語對應(yīng)用程序員是透明的，由系統(tǒng)程序員用這些硬件原語構(gòu)建一個同步庫來支持線程的同步機(jī)制?！?〕原子互換：它將一個存放器中的值與一個存儲器中的值進(jìn)行互換。應(yīng)用互換原語實現(xiàn)同步的關(guān)鍵是這種操作具有原子性：互換是不可分割的，兩個同時進(jìn)行的互換操作將由寫串行機(jī)制排序進(jìn)行。兩個試圖設(shè)置同步變量的處理器不可能同時完成設(shè)置?！?〕測試并置位〔test-and-set〕它先對一個數(shù)值進(jìn)行測試，假設(shè)該數(shù)值通過了檢測那么執(zhí)行設(shè)置。例如在測試數(shù)值為0時將其設(shè)置為1，這與前述原子互換類似?！?〕讀取并加1〔fetch-and-increment〕它返回存儲器中的值并以原子操作的方式使存儲器中的值加1。假設(shè)用0表示同步變量未被占用，那么可以像使用原子互換一樣得到類似的結(jié)果。〔4〕讀取并更新〔fetch-and-update〕這是一種新型的同步原子操作，可以包含上述同步原語的功能。這一對指令包括一條專門的裝載指令，稱為鏈接裝載〔loadlinked〕或上鎖裝載〔loadlocked〕即LL指令；還包括一條稱為條件存儲〔storecondition〕即SC指令。LL指令和SC指令按順序執(zhí)行。如果LL指令指定的存儲單元的地址值在對應(yīng)的SC指令執(zhí)行之前被改變了，那么條件存儲失敗。如果處理器在這兩條指令之間作了線程切換，那么條件存儲也失敗。SC指令返回一個數(shù)值，成功返回1，失敗返回0。用一致性實現(xiàn)鎖基于原子操作，就可以利用多處理器的一致性來實現(xiàn)自旋鎖〔spinlock〕。自旋鎖是指處理器通過循環(huán)的方法來不斷嘗試取得的鎖。自旋鎖適用于對鎖的占用時間很短并且上鎖時間很快的情況。因為自旋鎖要阻塞處理器并一直循環(huán)等待鎖被釋放，所以自旋鎖在某些環(huán)境下是不適用的。下面的代碼實現(xiàn)原子互換來鎖定R1指定的自旋鎖： DADDUIR2,R0,#1;讓R2=0lockit:EXCH R2,0(R1);互換，將0寫入鎖變量 BNEZ R2,lockit;假設(shè)未鎖定繼續(xù)嘗試雖然自旋鎖的方案簡單，但互斥的鎖操作會帶來較大的通信流量，對擁有較多數(shù)目的處理器系統(tǒng)來說會帶來困難。一種解決方法是將鎖的競爭分散到多個鎖上，防止頻繁進(jìn)行Cache塊的更新。還有采用鏈接裝載和條件存儲機(jī)制來實現(xiàn)非阻塞自旋鎖等。多線程同步機(jī)制帶來的問題〔1〕數(shù)據(jù)競爭數(shù)據(jù)競爭是由于各線程對共享數(shù)據(jù)讀-寫訪問和寫-寫訪問順序的不確定性引起的。〔2〕同步同步是解決數(shù)據(jù)競爭的措施，目的是使數(shù)據(jù)訪問按一定的順序進(jìn)行，但是同步機(jī)制會帶來許多復(fù)雜性和一定的開銷?！?〕線程停頓線程停頓是同步操作帶來的后果。在采用互斥量對共享資源進(jìn)行鎖定時，如果某個互斥量沒有被解鎖，那么會使等待這個鎖的線程停頓?！?〕死鎖死鎖是線程無限期的停頓現(xiàn)象。它通常出現(xiàn)在對資源的占有和對其它資源的等待出現(xiàn)環(huán)形依賴關(guān)系的時候?！?〕偽共享偽共享是線程之間的非真正的數(shù)據(jù)共享引起的相關(guān)性。常見的有Cache數(shù)據(jù)塊的偽共享現(xiàn)象。本來兩個線程并沒有真正共享同一個數(shù)據(jù)變量，但由于兩個線程的訪問數(shù)據(jù)都在同一個Cache塊中，從而導(dǎo)致對該數(shù)據(jù)塊的爭用。這種現(xiàn)象會使系統(tǒng)的性能下降。本章小結(jié)1．在單處理器中，現(xiàn)有的先進(jìn)技術(shù)不能使處理器到達(dá)理想的指令級并行處理器應(yīng)具備的條件，采用超線程技術(shù)和同時多線程技術(shù)能使指令級并行造成的空閑運(yùn)算單元發(fā)揮作用，有助于系統(tǒng)性能改進(jìn)。但由于指令級并行約束及超線程技術(shù)的限制、提高頻率帶來功耗和內(nèi)存、I/O速度平衡等問題，致使單核處理器根本停產(chǎn)，取而代之的是多核處理器。2．基于多個處理器組成計算機(jī)系統(tǒng)的方法來設(shè)計效勞器和超級計算機(jī)具有一是處理器性能的快速提高，許多過去在大中型計算機(jī)上用到的技術(shù)也在處理器上得以實現(xiàn)；二是批量生產(chǎn)比專門生產(chǎn)更具本錢優(yōu)勢，同種類型的多個處理器組成系統(tǒng)正好滿足這種優(yōu)勢；三是多處理器系統(tǒng)最能夠有效利用線程級并行，這對效勞器尤其重要。多處理器大致可分為4個層次：多核處理器，中小規(guī)模多處理器、大規(guī)模多處理器、集群〔包括商業(yè)集群和客戶集群〕。多核處理器是指在一個芯片上集成多個處理器核心，即CMP，通?？煞譃橥瑯?gòu)CMP和異構(gòu)CMP。一般每個處理器核心擁有私有的一級或二級Cache，且所有處理器核心共享下一級Cache。核間通信機(jī)制有兩種：基于總線共享的C