計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 陳智勇 第8章 并行算法

第8章并行算法8.1并行算法的基礎(chǔ)知識8.2同步技術(shù)8.3程序并行性的分析8.4并行編程概述8.5并行編程模型習(xí)題88.1并行算法的基礎(chǔ)知識

8.1.1并行算法的定義和分類1.并行算法的定義算法是指解題方法的精確描述，是一組有窮的規(guī)則，它們規(guī)定了解決某一特定類型問題的一系列運(yùn)算。并行算法(parallelalgorithm)是指一些可同時執(zhí)行的諸進(jìn)程的集合，這些進(jìn)程相互作用和協(xié)調(diào)動作從而達(dá)到給定問題的求解。2.并行算法的分類并行機(jī)的出現(xiàn)來源于實(shí)際應(yīng)用程序中存在內(nèi)在并行度這一基本事實(shí)，因此，應(yīng)用程序中是否存在可挖掘并行度是并行計(jì)算機(jī)應(yīng)用的關(guān)鍵，而并行算法作為應(yīng)用程序開發(fā)的基礎(chǔ)，自然在并行計(jì)算機(jī)應(yīng)用中具有舉足輕重的地位。并行算法根據(jù)運(yùn)算基本對象的不同可分為數(shù)值并行算法和非數(shù)值并行算法。數(shù)值計(jì)算是指基于代數(shù)關(guān)系運(yùn)算的一類諸如矩陣運(yùn)算、多項(xiàng)式求值、求解線性方程組等數(shù)字計(jì)算問題。主要為數(shù)值計(jì)算方法而設(shè)計(jì)的并行算法稱為數(shù)值并行算法(numericalparallelalgorithm)。非數(shù)值計(jì)算是指基于比較關(guān)系運(yùn)算的一類諸如排序、選擇、搜索、匹配等符號處理問題。主要為符號運(yùn)算而設(shè)計(jì)的并行算法稱為非數(shù)值并行算法(non-numericalparallelalgorithm)。如神經(jīng)網(wǎng)絡(luò)算法、遺傳算法等。根據(jù)并行進(jìn)程間相互執(zhí)行順序關(guān)系的不同可分為同步并行算法、異步并行算法和獨(dú)立并行算法。同步并行算法(synchronizedparallelalgorithm)是指算法的諸進(jìn)程間由于運(yùn)算執(zhí)行順序而必須相互等待的并行算法。如通常的向量算法、SIMD算法及MIMD并行機(jī)上進(jìn)程間需要相互等待通信結(jié)果的算法等。異步并行算法(asynchronizedparallelalgorithm)是指算法的諸進(jìn)程間執(zhí)行相對獨(dú)立，不需要相互等待的一種算法。通常對消息傳遞MIMD并行機(jī)進(jìn)行設(shè)計(jì)，其主要特征是在計(jì)算的整個過程中均不需要等待，而是根據(jù)最新消息決定進(jìn)程的繼續(xù)或終止。獨(dú)立并行算法(independentparallelalgorithm)是指算法的諸進(jìn)程間執(zhí)行完全獨(dú)立，計(jì)算的整個過程不需要任何通信的并行算法。例如氣象預(yù)報應(yīng)用中通常需要同時計(jì)算多個模型，以保證預(yù)報的實(shí)時性。根據(jù)各處理機(jī)承擔(dān)的計(jì)算任務(wù)粒度的不同，可分為細(xì)粒度并行算法、中粒度并行算法和粗粒度并行算法。細(xì)粒度并行算法(finegrainparallelalgorithm)通常指基于向量和循環(huán)級并行的算法。中粒度并行算法(middlegrainparallelalgorithm)通常指基于較大的循環(huán)級并行，且并行的好處足以彌補(bǔ)并行來的額外開銷的算法。粗粒度并行算法(coarsegrainparallelalgorithm)通常指基于子任務(wù)級并行的算法，例如通常的基于區(qū)域分解的并行算法，它們是當(dāng)前并行算法設(shè)計(jì)的主流。8.1.2進(jìn)程中的同構(gòu)性如前所述，并行算法是對一些可同時執(zhí)行的諸進(jìn)程之間相互關(guān)系的描述，因此，我們這里先討論進(jìn)程中的同構(gòu)性，再來介紹并行算法的表達(dá)方法。進(jìn)程中的同構(gòu)性是指在執(zhí)行并行程序時，并行機(jī)中各處理機(jī)執(zhí)行的進(jìn)程相似到何種程度。圖8.1描述了程序執(zhí)行時進(jìn)程中的同構(gòu)性。圖8.1進(jìn)程中的同構(gòu)性在多程序多數(shù)據(jù)流(MPMD)程序中的分進(jìn)程是異構(gòu)的，因?yàn)槎鄠€進(jìn)程可以執(zhí)行不同的程序代碼；在單程序多數(shù)據(jù)流(SPMD)程序中的分進(jìn)程是同構(gòu)的，因?yàn)槎鄠€進(jìn)程在不同的數(shù)據(jù)范疇內(nèi)執(zhí)行相同的程序代碼，但不需在指令級達(dá)到同步；在單指令多數(shù)據(jù)流(SIMD)程序中的分進(jìn)程是同構(gòu)的，并且要求所有分進(jìn)程必須在同一時間執(zhí)行相同的指令。也就是說，SIMD程序是SPMD程序的一個特例。MPMD和SPMD程序在執(zhí)行時，由于各分進(jìn)程在同一時間執(zhí)行的是不同的指令，同時產(chǎn)生多個數(shù)據(jù)流，因此這兩者均屬于MIMD類型的程序。8.1.3并行算法的表達(dá)描述一個算法，可以使用自然語言進(jìn)行物理描述，也可用某種編程語言進(jìn)行形式化描述。語言的選用，應(yīng)避免二義性，且力圖直觀、易懂而不苛求嚴(yán)格的語法格式。像描述串行算法所選用的語言一樣，類Algol、Pidgin-Algol、類Pascal、類C等語言均可選用。在這些語言中，允許使用的任何數(shù)據(jù)類型都可引進(jìn)。在描述并行算法時，所有描述串行算法的語句及過程調(diào)用等均可使用，如數(shù)組、集合、記錄等等。根據(jù)進(jìn)程中的同構(gòu)性不同，對并行算法的表達(dá)采用了不同的并行語句。1.par語句當(dāng)算法的若干個進(jìn)程要并行執(zhí)行時，可使用par語句進(jìn)行描述。其格式如下：parbeginS1；S2；…；Sn；parendpar語句主要用來描述MPMD的功能并行性，其中S1，S2，…，Sn是分進(jìn)程，它們可含不同代碼。當(dāng)par語句執(zhí)行時，它的n個分進(jìn)程S1，S2，…，Sn就開始同時執(zhí)行。它們的執(zhí)行是互相獨(dú)立的而且以不同的速率進(jìn)行。當(dāng)所有n個分進(jìn)程終止時，par語句也就終止。2.parfor語句當(dāng)par語句中的所有分進(jìn)程共享相同的程序代碼時，可使用parfor語句進(jìn)行描述。其格式如下：parfor(i=1；i<=n；i++)/類C語言/{process(i)；}或parfori:=1tondo/類Pascal語言/beginprocess(i)；end；parfor語句用來描述SPMD的數(shù)據(jù)并行性，其中process(i)表示某一個進(jìn)程。盡管所有的進(jìn)程都執(zhí)行相同的程序代碼，但各進(jìn)程所需的參數(shù)是不相同的。3.forall語句當(dāng)parfor語句中的所有分進(jìn)程被分派到指定的處理機(jī)上并行執(zhí)行時，可使用forall語句進(jìn)行描述。其格式如下：forall(i=1；i<=k；i++)/類C語言/{process(i)；}或forallPiwhere0≤i≤kdo/類Pascal語言/process(i)；endfor；8.1.4并行算法中的同步與通信1.同步同步是在時間上強(qiáng)迫使各進(jìn)程在某一點(diǎn)必須相互等待。在并行算法的各進(jìn)程異步執(zhí)行過程中，為了確保各處理機(jī)的正確工作順序以及對共享可寫數(shù)據(jù)的正確訪問（互斥訪問），程序員需在算法的適當(dāng)點(diǎn)設(shè)置同步點(diǎn)。下面以MIMD-SD多處理器系統(tǒng)中n個數(shù)的求和為例，說明如何用同步語句lock和unlock來確保對共享可寫數(shù)據(jù)的互斥訪問。假定系統(tǒng)中有p個處理器P0，P1，…，Pp-1，輸入數(shù)組A=(a0，a1，…，an-1)存放在共享存儲器中，全局變量用于存放結(jié)果，局部變量L包含各處理機(jī)計(jì)算的部分和。lock和unlock語句實(shí)現(xiàn)臨界區(qū)操作，鎖語句是個原子性操作。在for循環(huán)中各進(jìn)程異步地執(zhí)行各語句，并結(jié)束在“endfor”。算法8.1共享存儲器多處理器上的求和算法n-1i=0輸入：A=(a0，a1，……，an-1)，處理器數(shù)p輸出：S=∑aibeginS=0；forallPiwhere0≤i≤p-1doL=0；forj=itonsteppdoL=L+aj；endfor；lock(S)；S=S+L；unlock(S)；endfor；end；2.通信通信是在空間上對各并發(fā)執(zhí)行的進(jìn)程施行數(shù)據(jù)交換，通信可使用通信原語來表達(dá)。在共享存儲器的多處理機(jī)中，可使用globalread(X,Y)和globalwrite(U,V)來交換數(shù)據(jù)，前者將全局存儲器中數(shù)據(jù)X讀入局部變量Y中，后者將局部數(shù)據(jù)U寫入共享存儲變量V中；在分布存儲器的多計(jì)算機(jī)中，可使用send(X,i)和receive(Y,j)來交換數(shù)據(jù)，前者是處理機(jī)發(fā)送數(shù)據(jù)X給Pi，后者是處理機(jī)從Pj接收數(shù)據(jù)Y。下面以MIMD-DM多計(jì)算機(jī)系統(tǒng)中矩陣向量乘法為例說明。假定分布式連接拓?fù)錇榄h(huán)，矩陣A和向量X劃分成p塊，A=(A1,…,Ap)和X=(x1,…,xp)，其中Ai的大小為n×r，xi的大小為r。假定有p≤n臺處理機(jī)，r=n/p為一整數(shù)。為了計(jì)算y=AX，先由處理機(jī)i計(jì)算zi=Aixi(1≤i≤p),再累加求和z1+…+zp。如果Pi開始在其局存中保存B=Ai和w=xi(1≤i≤p)，則各處理機(jī)可局部計(jì)算乘積Bwi；然后采用在環(huán)中順時針循環(huán)部分和的方法將這些向量累加起來；最終輸出向量保存在P1中。對于每個處理器都執(zhí)行如下算法：算法8.2分布式存儲器多計(jì)算機(jī)上矩陣向量乘算法輸入：處理器數(shù)p，第i個大小為n×r的子矩陣B=A(1:n,(i-1)r+1:ir)，其中r=n/p；第i個大小為r的子向量w=x((i-1)r+1:ir)。輸出：Pi計(jì)算y=A1x1+…+Aixi，并向右傳送此結(jié)果；算法結(jié)束時，P1保存乘積AX。beginComputez=Bw；ifi=1thenyi=0elsereceive(y,left)endif；y=y+z；send(y,right)；ifi=1thenreceive(y,left)endif；end；8.2同步技術(shù)同步是個豐富的概念，且是個活躍的研究課題，跨越了許多計(jì)算機(jī)領(lǐng)域。在多門課程中，例如計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)、數(shù)據(jù)庫、操作系統(tǒng)、并行處理以及編程語言都涉及到同步。在學(xué)習(xí)同步概念時，以下4個方面必須弄清楚：(1)用戶面臨的同步問題，如互斥、原子性、生產(chǎn)者和消費(fèi)者問題、哲學(xué)家就餐問題及路障同步等。(2)用戶用來解決同步問題的語言結(jié)構(gòu)。這種結(jié)構(gòu)可以是新語言構(gòu)造、庫函數(shù)或編譯制導(dǎo)等形式。在目前共享存儲器編程環(huán)境中，流行的結(jié)構(gòu)是鎖、信號量（若只有兩個狀態(tài)就是鎖）、事件、臨界區(qū)和路障等。這些構(gòu)造稱為高級構(gòu)造。(3)在多處理機(jī)體系結(jié)構(gòu)中可用的同步原語，例如Decrement/Increment、Test-and-Set、Compare-and-Swap、Fetch-and-Add等，它們常常由系統(tǒng)硬件直接提供，因此稱為低級構(gòu)造。(4)用低級同步構(gòu)造實(shí)現(xiàn)高級同步構(gòu)造的算法。在目前的許多系統(tǒng)中，鎖仍是最基本的構(gòu)造，以它為基礎(chǔ)可構(gòu)筑其它構(gòu)造。一般而言，同步操作可分為三類：原子性、控制同步和數(shù)據(jù)同步。詳細(xì)的層次結(jié)構(gòu)如圖8.2所示。當(dāng)前的多處理機(jī)編程模型都支持路障、互斥、信號量和鎖，以及生產(chǎn)者和消費(fèi)者同步，但它們不能很好地支持原子性和“我找到了”同步。所有在共享存儲器的機(jī)器（PVP、SMP、DSM等）中的同步通常使用鎖原語實(shí)現(xiàn)，而在分布存儲器的機(jī)器（MPP和機(jī)群）中的同步使用消息傳遞原語實(shí)現(xiàn)。圖8.2各種同步類型8.2.1原子性原子性(atomicity)是指一個進(jìn)程需要以單原子操作方式加以執(zhí)行。一個原子操作是指有如下特性的一種操作。(1)不可分：從程序員的觀點(diǎn)看，原子操作作為單一、不可分的一步來執(zhí)行，一旦開始便不可在中間加以中斷，即其它進(jìn)程無法見到其中間狀態(tài)，僅僅原子操作最后的結(jié)果對其它進(jìn)程是可見的。如果由于某種原因使原子操作中途放棄，那么必須消除已執(zhí)行部分操作的影響，卷回到原子操作的初始狀態(tài)。(2)有限：一旦啟動原子操作，它將在有限時間內(nèi)執(zhí)行完。(3)可順序化：不可分性質(zhì)的推論是可順序化。意思是說當(dāng)幾個原子操作并行執(zhí)行時，最后的結(jié)果就如同這些操作按某種任意的一次序一個接一個地執(zhí)行所得到的結(jié)果一樣。如以下代碼所示：parfor(i=1；i<=n；i++){atomic{x=x+1；y=y-1；}}此例中，盡管x=x+1；y=y-1；是串行操作的，atomic將以上兩條語句強(qiáng)制捆綁在一起，使其同時輸出，達(dá)到同步。關(guān)鍵字atomic表示n個進(jìn)程中的每一個必須以原子操作方式執(zhí)行兩條賦值語句。由并行系統(tǒng)強(qiáng)制原子性方式完成隱式同步。8.2.2控制同步執(zhí)行控制同步(controlsynchronization)操作的進(jìn)程將處于等待狀態(tài)，直到程序的執(zhí)行到達(dá)某種控制狀態(tài)。控制同步有路障、“我找到了”(eureka)和互斥(multualexclusive)等三種。路障同步是為了保證一組進(jìn)程全都到達(dá)某一控制點(diǎn)后再繼續(xù)執(zhí)行。“我找到了”同步則與路障同步完全相反，當(dāng)某個進(jìn)程到達(dá)某一控制點(diǎn)時，立即異步通知其它所有進(jìn)程，而勿需處于等待狀態(tài)?；コ馐峭ㄟ^各進(jìn)程互斥地執(zhí)行臨界段的內(nèi)容，來保證對共享數(shù)據(jù)讀寫的正確性，從而實(shí)現(xiàn)同步的技術(shù)。下面我們主要介紹路障同步和互斥。1.路障同步路障同步是通過設(shè)置路障來達(dá)到同步的，如以下代碼所示：parfor(i=1；i<=n；i++){Pi；barrier；Qi；}代碼中有n個進(jìn)程。執(zhí)行Pi的第i個進(jìn)程后跟一個barrier(路障同步)，在其之后是Qi。當(dāng)執(zhí)行完P(guān)i并到達(dá)barrier語句時，它必須處于等待狀態(tài)，直到所有其它進(jìn)程也到達(dá)了它們各自的路障時，才開始并行執(zhí)行Qi。2.互斥在實(shí)現(xiàn)互斥操作時，各處理機(jī)處理的相同代碼段具有原子性且各處理機(jī)只能串行執(zhí)行這一代碼段。一個互斥操作是指有如下特性的一種操作。(1)互斥：每個時刻，僅允許一個進(jìn)程執(zhí)行臨界段。(2)保證前進(jìn)：如果多個進(jìn)程試圖進(jìn)入臨界區(qū)執(zhí)行它們的臨界段程序，那么至少有一個進(jìn)程最后獲得成功。換句話說，程序不會出現(xiàn)死鎖或活鎖。(3)無饑餓：企圖執(zhí)行臨界段的進(jìn)程最后應(yīng)該獲得成功，它不會由于其它進(jìn)程的協(xié)同作用而處于饑餓狀態(tài)。如以下代碼所示：parfor(i=1；i<=n；i++)/有n個進(jìn)程/{/每個進(jìn)程執(zhí)行一個parfor迭代/whileCONDITION

{independentcomputation，noncriticalsection/獨(dú)立計(jì)算，非臨界區(qū)/critical/互斥代碼進(jìn)入點(diǎn)/{criticalsection}/退出互斥代碼段/independentcomputation，noncriticalsection}}臨界段(criticalsection)是應(yīng)以互斥方式執(zhí)行的代碼段。CONDITION是可以被臨界區(qū)修改的邏輯表達(dá)式，關(guān)鍵字critical指明了臨界區(qū)(criticalregion)。應(yīng)注意臨界區(qū)是互斥的，因?yàn)槊看沃辉试S一個進(jìn)程執(zhí)行臨界段的內(nèi)容。與此相反，只要原子性是強(qiáng)制的，多個進(jìn)程就可執(zhí)行它們自己的原子區(qū)。但兩者的時間復(fù)雜度是相同的，均為O(n)，其中n為進(jìn)程的個數(shù)。8.2.3數(shù)據(jù)同步執(zhí)行一個數(shù)據(jù)同步(datasynchronization)操作的進(jìn)程將處于等待狀態(tài)，直到程序執(zhí)行到達(dá)某種數(shù)據(jù)狀態(tài)。數(shù)據(jù)同步的例子包括信號量和鎖(semaphore&lock)、生產(chǎn)者和消費(fèi)者(producer&consumer)、池和隊(duì)列(pool&queue)等。在大多數(shù)當(dāng)今的系統(tǒng)中，都用數(shù)據(jù)同步來實(shí)現(xiàn)原子性。如以下代碼所示：parfor(i=1；i<=n；i++){lock(S)；x=x+1；y=y-1；unlock(S)；}其中鎖同步依賴于信號量S中的數(shù)據(jù)狀態(tài)?？刂仆街灰蕾囉诔绦虻目刂茽顟B(tài)，它不受程序數(shù)據(jù)狀態(tài)的影響。數(shù)據(jù)同步使用時非常靈活，但控制同步通常要比數(shù)據(jù)同步更容易理解。8.2.4高級同步結(jié)構(gòu)當(dāng)前，共享存儲器的多處理機(jī)系統(tǒng)的并行編程環(huán)境提供了4類同步原語：事件、路障、鎖/信號量和臨界區(qū)。事件操作用來實(shí)現(xiàn)生產(chǎn)者-消費(fèi)者同步，路障用在路障同步中，鎖和臨界區(qū)主要用來實(shí)現(xiàn)互斥方式的原子性。我們這里只介紹信號量和鎖。1.信號量和鎖信號量S是一個非負(fù)整數(shù)變量，僅由兩個原子操作P(S)和V(S)處理。P(S)操作用來延時一個進(jìn)程，直到S變?yōu)榇笥?，然后S減1。V(S)操作簡單地將S加1。二元信號量S(也就是S或?yàn)檎婊驗(yàn)榧?也叫做鎖。對鎖信號量S的操作P(S)和V(S)常分別寫為lock(S)和unlock(S)。鎖的一般用途是通過互斥將臨界區(qū)轉(zhuǎn)變?yōu)樵硬僮?，例如：在銀行交易中，我們用單個鎖S。進(jìn)程在能夠做任何取款、存款、轉(zhuǎn)帳交易之前，必須通過執(zhí)行l(wèi)ock(S)操作首先獲得鎖S，在完成交易之后，通過執(zhí)行unlock(S)釋放鎖。一個進(jìn)程已獲得鎖但還沒有釋放，就說該進(jìn)程正持有鎖。轉(zhuǎn)帳交易可用下面代碼實(shí)現(xiàn)：lock(S)；/進(jìn)入代碼/if(balance[X]>100)/臨界區(qū)/{balance[X]=balance[X]-100；balance[Z]=balance[Z]+100；}unlock(S)；/退出代碼/2.鎖的副作用鎖的優(yōu)點(diǎn)是它已有大多數(shù)多處理器支持它，并且已研究得相當(dāng)深入。鎖是一種非常靈活的機(jī)制，幾乎能實(shí)現(xiàn)任何同步。然而互斥鎖技術(shù)用于實(shí)現(xiàn)原子性操作時具有某些嚴(yán)重的缺點(diǎn)，從而導(dǎo)致如下一些問題：(1)非結(jié)構(gòu)性：鎖不是一種結(jié)構(gòu)化的結(jié)構(gòu)，容易用錯它，如果lock/unlock語句漏掉或冗余，則編譯器不能查出它。(2)重疊說明：鎖不是用戶所真正想要的，它只是達(dá)到原子性操作的一種方法。鎖損害了程序的可移植性，且使代碼難于理解。(3)狀態(tài)相關(guān)：鎖引入了信號量S及使用條件原子操作lock(S)，一個進(jìn)程能否穿過lock(S)依賴于信號量S的值，一般而言，像這樣與狀態(tài)有關(guān)的數(shù)據(jù)是難于理解的。(4)順序執(zhí)行：對于有些事務(wù)處理操作，即使可并行訪問，但由于使用鎖互斥，它們只能一次執(zhí)行一個，同樣這種順序執(zhí)行也不是用戶想要的。如在上例的代碼段中，若X向Z轉(zhuǎn)帳的同時，Y也要求向W轉(zhuǎn)帳。(5)鎖開銷：順序執(zhí)行l(wèi)ock(S)和unlock(S)也存在著附加的開銷，而且當(dāng)n個進(jìn)程每個都執(zhí)行l(wèi)ock(S)操作時，它們中至多一個能成功，其余的均必須重復(fù)訪問S而再試。(6)優(yōu)先權(quán)倒置：當(dāng)一個高優(yōu)先權(quán)進(jìn)程所需的鎖被低優(yōu)先權(quán)進(jìn)程搶先持有時，高優(yōu)先權(quán)進(jìn)程并不能向前執(zhí)行，因?yàn)樗绘i阻塞等待。(7)傳遞阻塞：當(dāng)一個保持鎖的進(jìn)程因缺頁或超時被中斷時，其它的進(jìn)程因等待鎖不能前進(jìn)。(8)死鎖：假定兩個進(jìn)程P與Q，欲進(jìn)行X與Y操作，當(dāng)進(jìn)程P已為X保持了一把鎖并想為Y申請一把鎖，而進(jìn)程Q已為Y保持了一把鎖并想為X申請一把鎖時，此時沒有任何進(jìn)程在其得到鎖之前釋放一把鎖，結(jié)果誰也得不到要求的鎖。使用二相鎖協(xié)議的代碼段如下：lock(S[X])；/對帳戶X(的信號量)加鎖/if(balance[X]>100){balance[X]=balance[X]-100；lock(S[Y])；/對帳戶Y(的信號量)加鎖/balance[Y]=balance[Y]+100；unlock(S[Y])；/使用帳戶Y結(jié)束/}unlock(S[X])；/使用帳戶X結(jié)束/這段代碼限制了并發(fā)性，因?yàn)楫?dāng)一個進(jìn)程已完成處理帳戶X，并且正在處理帳戶Y時，帳戶X仍然封鎖。因此，盡管帳戶X不再需要該進(jìn)程作任何處理，其它進(jìn)程也不能使用它。此代碼段最嚴(yán)重的問題是死鎖的可能性，假設(shè)進(jìn)程P從帳戶X中轉(zhuǎn)帳100美元到帳戶Y中，另一進(jìn)程Q從帳戶Y中轉(zhuǎn)帳50美元到X中，因?yàn)镻和Q是并行執(zhí)行的，將形成爭持不下的情形：P持有帳戶X的鎖，并試圖獲取帳戶Y的鎖；Q持有帳戶Y的鎖，并試圖獲取帳戶X的鎖。根據(jù)二相鎖協(xié)議，進(jìn)程在獲得它需求的所有鎖之前，不釋放任何鎖。因此，P和Q都不能得到它們要求的鎖。在P等待執(zhí)行l(wèi)ock(S[Y])和Q等待執(zhí)行l(wèi)ock(S[X])時，它們就進(jìn)入了死鎖狀態(tài)。3.臨界區(qū)保證臨界段互斥的結(jié)構(gòu)化構(gòu)造是臨界區(qū)，它的語法類似如下：critical_regionresource{S1；S2；…；Sn；/臨界段/}其中resource表示一組共享變量，共享相同resource的臨界區(qū)必須互斥執(zhí)行，這種需求由系統(tǒng)(編譯器和運(yùn)行支持系統(tǒng))實(shí)現(xiàn)。而且，臨界區(qū)結(jié)構(gòu)原先是為操作系統(tǒng)應(yīng)用提出來的。當(dāng)它用于并行編程時，作了兩個修改：第一，resource部分并非真正有用，因此可以拋棄。用在真正多處理機(jī)系統(tǒng)中的臨界區(qū)結(jié)構(gòu)具有下面語法：critical_region等效的鎖機(jī)制代碼{lock(S)；S1；S2；…Sn；S1；S2；…Sn；}unlock(S)；第二，如上所述，多處理機(jī)系統(tǒng)中的臨界區(qū)是一定意義上的鎖的結(jié)構(gòu)化方法。系統(tǒng)將自動聲明和初始化一個隱含的信號量S，并生成正確的lock/unlock語句。臨界區(qū)是結(jié)構(gòu)化的和狀態(tài)獨(dú)立的，因此更容易使用。使用臨界區(qū)的交易可串行化且無死鎖，其描述量少，對體系結(jié)構(gòu)依賴弱。臨界區(qū)意味著代碼段將互斥執(zhí)行，不意味著必須使用鎖機(jī)制。8.2.5低級同步原語許多多處理機(jī)的硬件保證了對基本變量進(jìn)行單個讀或?qū)懖僮鞯脑有浴Ａ硗?，大多?shù)多處理機(jī)硬件提供了一些原子性指令，每條指令實(shí)現(xiàn)對基本變量的一個讀、修改、寫操作。共同使用這些指令可實(shí)現(xiàn)更大粒度的原子操作，下面我們討論4種低級結(jié)構(gòu)，并按復(fù)雜性增大的順序，指出如何使用它們實(shí)現(xiàn)鎖機(jī)制。1.Test-and-Set(測試和設(shè)置)Test-and-Set指令用Test-and-Set(S,temp)表示，它是一個原子操作，它讀取共享變量S的值存入本地變量temp中，然后設(shè)置S為true。Test-and-Set的主要用途是實(shí)現(xiàn)鎖，例如：while(S)do；Test-and-Set(S,temp)；while(temp)doTest-and-Set(S,temp)；/完成lock(S)操作/ifbalance[X]>100then/臨界段/beginbalance[X]:=balance[X]-100；balance[Z]:=balance[Z]+100；end；S:=False；/完成unlock(S)操作/每次執(zhí)行Test-and-Set(S,temp)都需要寫共享變量S，這將導(dǎo)致繁重的存儲器存取傳輸。lock(S)的上述實(shí)現(xiàn)辦法使用了Test-and-Set操作。第一個while循環(huán)在本地高速緩存中重復(fù)檢查共享變量S的拷貝。進(jìn)程只有當(dāng)檢測到鎖S被其它進(jìn)程釋放(處于開鎖)時，才離開第一個while循環(huán)。在所有進(jìn)程并行執(zhí)行第一條Test-and-Set語句時，根據(jù)原子性操作的可順序化特性，只有一個進(jìn)程的temp值被置為False，從而獲得鎖，其它進(jìn)程的temp值均為True。在執(zhí)行第二個while循環(huán)時，只有獲得鎖的進(jìn)程才能跳過此循環(huán)，執(zhí)行臨界段的內(nèi)容，執(zhí)行完成后，將共享變量S的值置為False，從而釋放鎖。其它所有進(jìn)程在循環(huán)執(zhí)行第二條Test-and-Set語句(等待鎖)，直到鎖被釋放時，又有一個新的進(jìn)程獲得鎖并執(zhí)行臨界段的內(nèi)容，如此循環(huán)，直到所有進(jìn)程都執(zhí)行完臨界段的內(nèi)容。2.Decrement和Increment(減1和增1)實(shí)現(xiàn)Decrement和Increment指令的具體方法是每條指令在執(zhí)行期間“擁有”一個指定的存儲單元。當(dāng)指定的存儲單元正在被讀訪問時，其它任何指令都不能訪問它，直到修改過的內(nèi)容重新寫入該單元為止。即Decrement和Increment指令具有讀/修改/寫的不可中斷性質(zhì)。在具有不可中斷的Decrement和Increment指令的計(jì)算機(jī)系統(tǒng)中，用Decrement和Increment指令來實(shí)現(xiàn)同步，要比用Test-and-Set指令來實(shí)現(xiàn)同步所需要的指令要少。因?yàn)門est-and-Set指令返回的信息只有一位，而Decrement和Increment指令返回一個存儲單元的全部內(nèi)容。因?yàn)榉祷氐男畔⒍啵詫?shí)現(xiàn)同步所需的指令數(shù)少。用Test-and-Set指令實(shí)現(xiàn)的信號燈只允許一個進(jìn)程通過，在信號燈被解鎖之前，禁止其它進(jìn)程訪問。這種信號燈只適宜于控制一個長度為1的緩沖區(qū)。擴(kuò)充的信號燈允許M個進(jìn)程同時通過。如果已經(jīng)有M個進(jìn)程正在長度為M的共享緩沖區(qū)活動，那么在信號燈被解鎖之前，以后的進(jìn)程被禁止通過。如此每解鎖一次允許一個進(jìn)程通過該信號燈。有一種使用Decrement和Increment指令實(shí)現(xiàn)這種擴(kuò)充信號燈的簡單方法，開始時給該信號燈賦一個初值M，然后每個請求進(jìn)程對信號燈進(jìn)行減1操作。如果在Decrement(減1)操作之后，發(fā)現(xiàn)信號燈是一個非負(fù)的數(shù)，則該進(jìn)程可以訪問該緩沖區(qū)；如果信號燈是一個負(fù)數(shù)，則該進(jìn)程被阻止訪問，被阻止訪問的進(jìn)程隨后立即對信號燈執(zhí)行Increment(增1)操作，以表示該進(jìn)程沒有對緩沖區(qū)操作。如同我們早先討論的Test-and-Set指令一樣，被阻塞的進(jìn)程可以入隊(duì)或不斷測試信號燈。一臺處理機(jī)在完成對緩沖區(qū)的訪問之后，對信號燈執(zhí)行Increment(增1)操作，以表示有空間可供其它進(jìn)程使用。這種簡單的同步實(shí)現(xiàn)方法有時會出現(xiàn)一種稱之為活鎖的錯誤。所謂活鎖，是指系統(tǒng)進(jìn)入一種狀態(tài)，一方面緩沖區(qū)中有可用空間，另一方面有用工作無法進(jìn)入緩沖區(qū)。如下例：whileDecrement(semaphore)<0do/有活鎖現(xiàn)象的同步/Increment(semaphore)；{臨界程序區(qū)}Increment(semaphore)；這里的臨界程序區(qū)與互斥臨界區(qū)不一樣，互斥臨界區(qū)在任何時刻只允許一個進(jìn)程執(zhí)行臨界區(qū)的內(nèi)容，而這里的臨界程序區(qū)允許最多M個進(jìn)程同時執(zhí)行臨界程序區(qū)的內(nèi)容。下面我們來分析上面程序進(jìn)入活鎖狀態(tài)的原因。我們假設(shè)在信號燈為零時有大量處理機(jī)同時對該信號燈申請Decrement(減1)操作，那么信號燈值將變?yōu)?∞，它還能變?yōu)檎龜?shù)嗎？如果每臺被阻塞的處理機(jī)先執(zhí)行Increment(增1)操作，然后返回去重新測試信號燈并執(zhí)行Decrement(減1)操作，這整個過程是不可中斷的，然后才把信號燈傳送給下一臺處理機(jī)，那么信號燈值將從-∞變?yōu)?∞+1，然后又回到-∞。如果這時有M臺處理機(jī)同時從緩沖區(qū)退出，它們將信號燈值增加到-∞+M，但這仍是一個負(fù)數(shù)，所以不允許處理訪問緩沖區(qū)。這時就出現(xiàn)有用的工作因?yàn)槭录l(fā)生的順序不合理而被阻塞的現(xiàn)象。如果改變事件的順序，就可以使信號燈非負(fù)，進(jìn)而使有用的工作只要緩沖區(qū)有空間就能開始執(zhí)行。下面的程序中采用了一種能消去前面程序中活鎖現(xiàn)象的機(jī)制。它是在信號燈執(zhí)行Decrement(減1)操作之前測試信號燈。Loop:whilesemaphore<0do；/無活鎖現(xiàn)象的同步/ifDecrement(semaphore)<0thenbeginIncrement(semaphore)；gotoLoop；end；{程序臨界區(qū)}Increment(semaphore)；最壞的情況是大量的處理機(jī)發(fā)現(xiàn)信號燈為非負(fù)時，對信號燈進(jìn)行Decrement(減1)操作而使它變?yōu)?∞。這時若有其它處理機(jī)執(zhí)行while語句，將處于循環(huán)等待狀態(tài)。當(dāng)大量處理機(jī)執(zhí)行完Increment(加1)操作并使信號燈重新變?yōu)榉秦?fù)時，至少有一個進(jìn)程可以在該值再次變?yōu)樨?fù)數(shù)之前獲準(zhǔn)通過。因此有用的工作可以繼續(xù)執(zhí)行，不會出現(xiàn)活鎖現(xiàn)象。3.Compare-and-Swap(比較和交換)Compare-and-Swap指令用Compare-and-Swap(S,Old,New,Flag)表示，是一個原子操作。它比較共享變量S和本地變量Old中的值，如果兩變量值相等，本地變量New的值存入S中，并且本地標(biāo)志Flag設(shè)置為True，表示S已被修改。如果兩變量不等，則S的值存入變量Old中，并且Flag設(shè)置為False。Compare-and-Swap可能的應(yīng)用通過下面銀行存錢交易代碼演示如下：Old:=balance[X]；/讀共享變量/repeatNew:=Old+100；/修改/Compare-and-Swap(balance[X],Old,New,Flag)；/寫/untilFlag=True；作為對比，通過鎖實(shí)現(xiàn)的相同存錢交易代碼如下：lock(S)；balance[X]:=balance[X]+100；/讀、修改、寫/unlock(S)；鎖實(shí)現(xiàn)方法使整個讀、修改、寫序列是互斥的。但是，Compare-and-Swap實(shí)現(xiàn)方法允許多個進(jìn)程并發(fā)讀和修改，只是寫作為互斥操作完成。因此，使用Compare-and-Swap的優(yōu)點(diǎn)是臨界段的長度可減小到僅為一條指令。Compare-and-Swap也有幾個缺點(diǎn)：首先，它是一種低級結(jié)構(gòu)，難于使用；第二，盡管可以使用，但很難用于存取多于一個共享變量的交易處理；第三，在某些特殊情況下，該指令無法感知共享變量的歷史變化情況，如下面的ABA問題。關(guān)于Compare-and-Swap(S,Old,New,Flag)指令隱含的假設(shè)是：當(dāng)Old=S時，S還沒有被修改過。但這個假設(shè)并不是始終成立的。例如，假設(shè)進(jìn)程P在帳戶balance[X]中讀一個A美元值，然后進(jìn)程Q存100美元到帳戶balance[X]中，改變余額為B=A+100。接著，進(jìn)程R從帳戶balance[X]中取走100美元，修改余額后又變?yōu)锳。這樣，當(dāng)以后進(jìn)程P執(zhí)行一個Compare-and-Swap操作時，它將發(fā)現(xiàn)帳戶balance[X]中的值為A美元，由此得出結(jié)論，認(rèn)為該帳戶一直未被修改過，很顯然這是錯誤的。此處的ABA問題并不影響簡單存錢交易代碼執(zhí)行的正確性。但是，在其它情況下，特別是在共享變量為一個指針時，它可能導(dǎo)致不正確的結(jié)果。Compare-and-Swap指令的最有意義的應(yīng)用是不需要加鎖和解鎖操作即可實(shí)現(xiàn)入隊(duì)和出隊(duì)。因?yàn)殛?duì)列指針是共享變量，所以典型的入隊(duì)/出隊(duì)程序在修改隊(duì)列指針前要加鎖，但這種方法限制了操作的并行性。下面我們以隊(duì)列為例，來介紹使用Compare-and-Swap指令并發(fā)地完成數(shù)據(jù)入隊(duì)列的過程和出隊(duì)列的過程。圖8.3顯示了隊(duì)列的數(shù)據(jù)結(jié)構(gòu)并說明了未使用比較與交換指令時并行完成數(shù)據(jù)入隊(duì)的情況。圖8.3(a)顯示的是一個單鏈表隊(duì)列，頭指針Head指向隊(duì)列的第一結(jié)點(diǎn)，即待出隊(duì)數(shù)據(jù)所在的結(jié)點(diǎn)，尾指針Tail指向隊(duì)列的最后一個結(jié)點(diǎn)，若有新的數(shù)據(jù)要入隊(duì)就插入到尾指針?biāo)赶蚪Y(jié)點(diǎn)的后面。假設(shè)鏈表中結(jié)點(diǎn)的類型定義如下：nodepointer=^node；node=recorddata:real；next:nodepointer；end；將一個數(shù)據(jù)項(xiàng)插入隊(duì)列只要執(zhí)行下面三條語句就可實(shí)現(xiàn)，即把指針p所指向的結(jié)點(diǎn)插入到隊(duì)列的隊(duì)尾。p^.next:=nil；Tail^.next:=p；Tail:=p；由于Tail為共享變量，因此在執(zhí)行上述三條語句的后兩條語句時不可中斷，否則在多個進(jìn)程并行執(zhí)行入隊(duì)操作時，將會產(chǎn)生錯誤。下面我們來分析錯誤的原因。圖8.3隊(duì)列的插入操作當(dāng)程序正確執(zhí)行時，執(zhí)行一個插入操作后的新隊(duì)列如圖8.3(b)所示。如果進(jìn)程1要把數(shù)據(jù)x插入隊(duì)列，進(jìn)程2要把數(shù)據(jù)y插入隊(duì)列，兩個進(jìn)程并行執(zhí)行，其中Tail為共享的指針變量，p為局部(本地)指針變量，兩者類型如前所述。假設(shè)進(jìn)程1先執(zhí)行第二條語句讀取Tail的當(dāng)前值，接著進(jìn)程2執(zhí)行第二條語句也讀取Tail的當(dāng)前值。若進(jìn)程1和進(jìn)程2仍按這個順序執(zhí)行第三條語句對Tail值進(jìn)行修改，那么進(jìn)程1執(zhí)行的結(jié)點(diǎn)插入操作將無效，如圖8.3(c)所示。反過來，若進(jìn)程2在進(jìn)程1之前先執(zhí)行第三條語句，那么隊(duì)列將在剛插入的這兩個結(jié)點(diǎn)之間斷開，如圖8.3(d)所示。為避免上述錯誤，傳統(tǒng)的編程方法總是在執(zhí)行第二條語句前加鎖，執(zhí)行完第三條語句后再解鎖，但這樣使得對共享指針變量Tail的讀、修改、寫過程均是互斥的，限制了程序的并行性，用比較與交換指令可較好地解決這個問題。一個基于比較與交換指令實(shí)現(xiàn)入隊(duì)(ENQUEUE)操作的程序如下：p^.next:=nil；/把插入隊(duì)尾的數(shù)據(jù)項(xiàng)初始化/Old:=Tail；/讀共享指針變量Tail到局部指針變量Old/Loop:Compare-and-Swap(Tail,Old,p,Flag)；ifFlag=FalsethengotoLoop；/比較與交換指令執(zhí)行失敗時返回Loop/Old^.next:=p；在執(zhí)行上述程序時，所有進(jìn)程首先將各自插入隊(duì)尾的數(shù)據(jù)項(xiàng)初始化，然后讀共享指針變量Tail的值存入局部指針變量Old中，再并行執(zhí)行原子性指令Compare-and-Swap，將當(dāng)前共享指針變量Tail的值與局部指針變量Old的值進(jìn)行比較。若相等，即隊(duì)尾指針未發(fā)生變化，則插入指針p所指向的新結(jié)點(diǎn)，并將Flag值置為True；若不相等，即在此進(jìn)程執(zhí)行入隊(duì)操作前已有其它進(jìn)程執(zhí)行了入隊(duì)操作，修改了隊(duì)尾指針，則重新讀取共享變量Tail的值賦給局部指針變量Old，并將Flag值置為False，重新執(zhí)行比較與交換指令，直到結(jié)點(diǎn)入隊(duì)操作成功為止。所有進(jìn)程并行執(zhí)行最后一條語句，完成對局部變量Old^.next的賦值操作。前述程序能實(shí)現(xiàn)并發(fā)的入隊(duì)操作，但該程序沒有考慮空表情況。如果入隊(duì)(ENQUEUE)操作和出隊(duì)(DEQUEUE)操作并發(fā)執(zhí)行，此程序也有可能出錯，下面我們要分析這種出錯的原因。如果這個程序剛好在Compare-and-Swap指令執(zhí)行之前被中斷，接著有兩個進(jìn)程分別執(zhí)行DEQUEUE操作和ENQUEUE操作。一個DEQUEUE操作可能已把Old所指向的結(jié)點(diǎn)從隊(duì)列中移走，緊跟著一個ENQUEUE操作執(zhí)行一個比較與交換指令又把移走的數(shù)據(jù)項(xiàng)存入隊(duì)列。這時Tail的值仍為原先的值，即與Old的值相同。于是，出現(xiàn)了兩個進(jìn)程同時用不同的指針修改了Tail^.next的情況。出錯的原因是Compare-and-Swap指令并不具備能感知Tail變化歷史的功能，所以一看到Tail=Old就認(rèn)為Tail從上次讀出以來一直未被修改過，而這一結(jié)論有時是不正確的。為了提高程序的可靠性，采用了一種擴(kuò)充的雙比較與交換指令，使它能同時處理兩個變量。這兩個變量必須相鄰存放，以便通過一次讀和寫操作就能同時完成這兩個變量的存取。改進(jìn)后的程序如下：p^.next:=nil；/把插入隊(duì)尾的數(shù)據(jù)項(xiàng)初始化/Old&Old_Count:=Tail&Count；/把雙變量Tail和Count值讀到Old和Old_Count/Loop:New_Count:=Old_Count+1；DoubleCompare-and-Swap(Tail&Count,Old&Old_Count,p&New_Count,Flag)；ifFlag=FalsethengotoLoop；Old^.next:=p；變量Tail和Count相鄰存放。Tail/Count對的當(dāng)前值讀到Old和Old_Count。僅在雙比較與交換(DoubleCompare-and-Swap)指令執(zhí)行之前，把Old_Count的內(nèi)容加1后傳送到New_Count。DoubleCompare-and-Swap指令驗(yàn)證Tail/Count未被修改后，用p/New_Count的內(nèi)容修改Tail/Count的值。因?yàn)镈oubleCompare-and-Swap指令執(zhí)行成功后，既修改Tail值又修改Count值，所以如果發(fā)現(xiàn)Tail和Count值被修改過，那么就表示其它隊(duì)列操作已經(jīng)發(fā)生過或正在執(zhí)行。這將強(qiáng)行使DoubleCompare-and-Swap指令失敗，轉(zhuǎn)到Loop執(zhí)行，阻止錯誤的修改操作。只有當(dāng)Tail和Count都沒有修改過時才能進(jìn)行修改操作。

例8.1分別用Compare-and-Swap指令和DoubleCompare-and-Swap指令來實(shí)現(xiàn)DEQUEUE（出隊(duì)）操作。解：把一個數(shù)據(jù)項(xiàng)從隊(duì)列的頭部移走只要執(zhí)行下面三條語句就可實(shí)現(xiàn)：p:=Head；Head:=p^.next；p^.next:=nil；用Compare-and-Swap指令實(shí)現(xiàn)DEQUEUE（出隊(duì)）操作的程序如下：Old:=Head；Loop:Compare-and-Swap(Head,Old,Old^.next,Flag)；ifFlag=FalsethengotoLoop；p:=Old；p^.next:=nil；用DoubleCompare-and-Swap指令DEQUEUE（出隊(duì)）操作的程序如下：Old&Old_Count:=Head&Count；Loop:DoubleCompare-and-Swap(Head&Count,Old&Old_Count,Old^.next&Count,Flag)；ifFlag=FalsethengotoLoop；p:=Old；p^.next:=nil；4.Fetch-and-Add(取和加)上面討論的各種技術(shù)(鎖、臨界區(qū)、測試和設(shè)置、比較和交換)都是順序地實(shí)現(xiàn)原子性。當(dāng)n個事務(wù)執(zhí)行時，每次只能執(zhí)行一個。即使用無鎖方案如Compare-and-Swap，也是這樣，因?yàn)楸M管n個進(jìn)程能并行執(zhí)行n個事務(wù)，但只有一個事務(wù)能夠成功提交，其它n-1個進(jìn)程必須重試。所以，執(zhí)行n個事務(wù)需O(n)時間。一條Fetch-and-Add指令的執(zhí)行結(jié)果，記為Result:=Fetch-and-Add(S,V)，是一個原子操作，它返回共享變量S的值到本地變量Result中。然后，在S中加上局部變量V的值。Fetch-and-Add指令，意味著允許多個事務(wù)真正地并行執(zhí)行。用Fetch-and-Add編寫帳戶存款交易代碼只用1條指令：Fetch&Add(balance[X]，100)；該代碼不僅更簡單，而且比以前代碼速度更快。使用一種稱為組合(combining)的技術(shù)，n個處理器在O(log2n)時間內(nèi)同時執(zhí)行n個Fetch-and-Add指令(訪問相同共享變量)是可能的。有關(guān)組合技術(shù)的內(nèi)容已在第五章作了較為詳細(xì)的介紹。用Fetch-and-Add指令實(shí)現(xiàn)ENQUEUE(入隊(duì))操作的最佳方法是以計(jì)數(shù)器為基礎(chǔ)。這種實(shí)現(xiàn)方法的基本思想是使用一個計(jì)數(shù)器Tail，執(zhí)行入隊(duì)操作時，計(jì)數(shù)器Tail增1。Tail的值是一個偏移量，用來表示下一個項(xiàng)的插入位置。下面是用Fetch-and-Add指令實(shí)現(xiàn)入隊(duì)操作的簡單但不完全的程序：ProcedureEnqueue(item，Queue)；beginPlace:=Fetch-and-Add(Tail，1)；Queue[Place]:=item；endofEnqueue；Fetch-and-Add指令使Tail增1，同時返回增1以前的Tail的值。該返回值是偏移量用來表示插入點(diǎn)的位置。如果N臺處理機(jī)同時執(zhí)行取和加指令，Tail接收到的是增量的和，而返回給每一臺處理機(jī)的是不同的位置值。這樣，每臺處理機(jī)在隊(duì)列中有不同的插入位置。這是用Fetch-and-Add指令實(shí)現(xiàn)入隊(duì)操作的最基本思想。但是，完整的實(shí)現(xiàn)因?yàn)樾枰紤]各種不同的條件而變得非常復(fù)雜。這些條件包括：(1)隊(duì)列應(yīng)該是循環(huán)的，這樣當(dāng)Tail值超過Queue向量的長度時，把Tail值置為0；(2)隊(duì)列中活動項(xiàng)總數(shù)不能超過Queue向量的長度；(3)Dequeue操作允許把多個項(xiàng)從隊(duì)列中并行地移出；(4)不允許對一個空隊(duì)進(jìn)行Dequeue操作；(5)Enqueue和Dequeue操作都必須避免出現(xiàn)活鎖。8.3程序并行性的分析幾個任務(wù)能否并行執(zhí)行，除了算法外，很大程度上還取決于程序的結(jié)構(gòu)形式。程序中各種類型的數(shù)據(jù)相關(guān)和控制相關(guān)都是限制程序并行性的重要因素。數(shù)據(jù)相關(guān)和控制相關(guān)既可存在于指令之間，也可存在于程序段之間。8.3.1數(shù)據(jù)相關(guān)數(shù)據(jù)相關(guān)(datadependence)是指鄰近的指令之間出現(xiàn)了要求對同一數(shù)據(jù)地址(寄存器、存儲單元地址或文件)進(jìn)行讀寫操作而發(fā)生的關(guān)聯(lián)，它用來說明語句之間的有序關(guān)系。常見的四種數(shù)據(jù)相關(guān)如下：(1)先寫后讀相關(guān)：如果從語句S1到語句S2存在執(zhí)行通路，即S1執(zhí)行完后，一定可以執(zhí)行S2，而且如果S1至少有一個輸出(賦值變量)可供S2用作輸入(用作操作數(shù))，則稱語句S2與語句S1存在先寫后讀相關(guān)。(2)先讀后寫相關(guān)：如果在程序次序中語句S2緊接語句S1，而且如果S2的輸出與S1的輸入重疊，則語句S2與語句S1存在先讀后寫相關(guān)。(3)寫-寫相關(guān)：如果在程序次序中語句S2緊接語句S1，而且兩條語句能產(chǎn)生(寫)同一輸出變量，則它們就是輸出相關(guān)。(4)I/O相關(guān)：讀和寫都是I/O語句。存在I/O相關(guān)不是因?yàn)樯婕巴蛔兞浚且驗(yàn)閮蓷lI/O語句引用同一文件。

例8.2并行程序中的數(shù)據(jù)相關(guān)性分析假設(shè)有如下并行程序段：parfor(i=1；i<=n；i++){A[i]=B[i]/10；A[i-1]=B[i]+C[i]；}解：在上述并行程序段的循環(huán)體部分，下標(biāo)只出現(xiàn)了i和i-1，即下標(biāo)的變化范圍為2，因此，只需將上述并行循環(huán)展開2層，即可分析出2條語句在并行執(zhí)行時可能會發(fā)生的數(shù)據(jù)相關(guān)性。假設(shè)i=1對應(yīng)的指令序列在處理機(jī)P1上實(shí)現(xiàn)，i=2對應(yīng)的指令序列在處理機(jī)P2上執(zhí)行，如下所示：P1(i=1)P2(i=2)…

A[1]=B[1]/10；A[2]=B[2]/10；…A[0]=B[1]+C[1]；A[1]=B[2]+C[2]；…由上述加下劃線的語句可以看出，兩條語句都要求寫同一輸出變量A[1]，為保證程序運(yùn)行的正確性，即在順序程序中語句“A[1]=B[2]+C[2]；”應(yīng)在語句“A[1]=B[1]/10；”之后執(zhí)行，因此并行程序段中存在寫寫相關(guān)。值得注意的是，并不是循環(huán)體中兩條語句的輸出變量只要是數(shù)組A的分量，就一定發(fā)生寫寫相關(guān)，例如，將本例中的步長改為2，程序如下：parfor(i=1；i<=n；i=i+2){A[i]=B[i]/10；A[i-1]=B[i]+C[i]；}例8.3并行程序中的數(shù)據(jù)相關(guān)性分析假設(shè)有如下并行程序段：parfor(i=2；i<=n；i++)A[i]=A[i-2]/B[i]；解：在上述并行程序段的循環(huán)體部分只有一條語句，下標(biāo)只出現(xiàn)了i和i-2，即下標(biāo)的變化范圍為3，因此，只需將上述并行循環(huán)展開3層，即可分析出此條語句在并行執(zhí)行時可能會出現(xiàn)的數(shù)據(jù)相關(guān)性。假設(shè)i=2、3、4對應(yīng)的指令分別在處理機(jī)P2、P3、P4上執(zhí)行，如下所示：P2(i=2)P3(i=3)P4(i=4)…

A[2]=A[0]/B[2]；A[3]=A[1]/B[3]；A[4]=A[2]/B[4]；…由上述加下劃線的語句可以看出，兩條語句都要求對同一變量A[2]進(jìn)行讀寫操作，為保證程序運(yùn)行的正確性，即在順序程序中語句“A[4]=A[2]/B[4]；”應(yīng)在語句“A[2]=A[0]/B[2]；”之后執(zhí)行，因此并行程序段中存在先寫后讀相關(guān)。

例8.4并行程序中的數(shù)據(jù)相關(guān)性分析假設(shè)有如下并行程序段：parfor(i=1；i<=n；i++)A[i]=A[C[i]]；解：在此例中，由于C[i]的值未知，因此不能直接判斷數(shù)據(jù)相關(guān)性。此例與例8.3非常相似，數(shù)組A的不同分量既出現(xiàn)在賦值號的左邊，又出現(xiàn)在賦值號的右邊。根據(jù)C[i]與i的關(guān)系，可得出如下結(jié)論：(1)當(dāng)C[i]＜i時，此并行程序段存在先寫后讀相關(guān)；(2)當(dāng)C[i]＞i時，此并行程序段存在先讀后寫相關(guān)。8.3.2控制相關(guān)控制相關(guān)(controldependence)指的是語句執(zhí)行次序運(yùn)行前不能確定的情況。影響程序執(zhí)行次序的指令通常有無條件轉(zhuǎn)移指令、條件轉(zhuǎn)移指令、子程序調(diào)用與返回指令、中斷調(diào)用與返回指令等。這里主要介紹由條件語句引起的控制相關(guān)。條件語句(如Fortran中的IF語句)直到運(yùn)行時才能確定條件判斷的結(jié)果。條件轉(zhuǎn)移后所執(zhí)行的不同分支可以導(dǎo)致、也可以消除指令間的數(shù)據(jù)相關(guān)，在完成一個循環(huán)的連續(xù)迭代操作之間也可能存在相關(guān)性。這里我們舉一個無控制相關(guān)迭代的例子和一個有控制相關(guān)迭代的例子。下面循環(huán)的連續(xù)迭代是無控制相關(guān)的：DO10I=1，NA(I)=C(I)IF(A(I).LT.0)A(I)=010CONTINUE下面循環(huán)的連續(xù)迭代存在控制相關(guān)：DO10I=1，NIF(A(I-1).EQ.0)A(I)=010CONTINUE將循環(huán)展開后如下所示：I=1，IF(A(0).EQ.0)A(1)=0I=2，IF(A(1).EQ.0)A(2)=0從上面加有下劃線的語句可以看出，語句“A(1).EQ.0”在判斷之前可能會被修改，由于條件語句的存在，使得對于I從1到N，所有的條件語句不能并行執(zhí)行。控制相關(guān)常使正在開發(fā)的并行性中止。為了開發(fā)更多的并行性，必須用編譯技術(shù)克服控制相關(guān)。例8.5一個程序的內(nèi)部循環(huán)如下：A[i,j]=A[i+1,j-1]；假設(shè)此條語句位于雙重循環(huán)內(nèi)，外部循環(huán)控制變量為i，內(nèi)部的為j。設(shè)計(jì)一段循環(huán)控制程序，使之對變量j的操作集中，而對i的操作分布到相互獨(dú)立的處理器上，從而可以并行處理。

解：假定滿足上述條件的雙重循環(huán)如下:parfor(i=1；i<n；i++){for(j=1；j<n；j++){A[i,j]=A[i+1,j-1]；}}若直接使之對變量j的操作集中，而對i的操作分布到相互獨(dú)立的處理器上，來完成并行處理，將會出現(xiàn)先讀后寫數(shù)據(jù)相關(guān)。將上述循環(huán)展開后如下：P1(i=1)P2(i=2)P3(i=3)…j=1A[1,1]=A[2,0]A[2,1]=A[3,0]A[3,1]=A[4,0]…j=2A[1,2]=A[2,1]A[2,2]=A[3,1]

A[3,2]=A[4,1]…j=3A[1,3]=A[2,2]

A[2,3]=A[3,2]A[3,3]=A[4,2]…j=4A[1,4]=A[2,3]…在上述加框語句、加下劃線語句、斜體表示的語句對之間均出現(xiàn)了先讀后寫數(shù)據(jù)相關(guān)。因此，需對并行循環(huán)體中的順序程序部分進(jìn)行修改，修改后的循環(huán)控制程序如下：parfor(i=1；i<n；i++){for(j=1；j<n；j++){B[i,j]=A[i+1,j-1]；}barrier；for(j=1；j<n；j++){A[i,j]=B[i,j]；}}8.4并行編程概述8.4.1并行編程概況對于所希望的應(yīng)用，很多現(xiàn)存的并行代碼似乎是不存在的，即使有，也常不能用于用戶的并行機(jī)上，因?yàn)椴⑿写a原來都是為不同的并行結(jié)構(gòu)(如SMP、MPP等)而寫的。并行編程的問題是：(1)并行算法范例至今尚不能被很好地理解和廣泛地接受；(2)并行編程是建立在不同的計(jì)算模型（PRAM模型、異步PRAM模型、BSP模型、logP模型、C3模型）上的，而它們沒有誰能象馮·諾依曼模型那樣被普遍的接受和認(rèn)可；(3)絕大部分被使用的并行編程語言都是Fortran和C的推廣，它們都不能充分地表達(dá)不同并行結(jié)構(gòu)的特點(diǎn)，既不成熟也不通用；(4)并行編程工具依賴于具體的并行機(jī)結(jié)構(gòu)和計(jì)算機(jī)代的更迭，既不通用也不穩(wěn)定，在某個平臺上開發(fā)的并行程序，很難移植到別的或?qū)淼牟⑿袡C(jī)上。盡管并行編程問題很多，但也有不少進(jìn)展：(1)已經(jīng)開發(fā)了很多并行算法，雖然它們大多基于理想的PRAM(ParallelRandom-AccessMachine)模型，但有些已被實(shí)際采用；(2)少量的并行算法范例已出現(xiàn)，并且正逐漸被接受；(3)編程類型漸趨匯聚于兩類：用于PVP、SMP和DSM的共享變量的單地址空間模型和用于MPP和機(jī)群的消息傳遞的多地址空間模型，SIMD模型已退出主流，但對專用領(lǐng)域(如信號、圖像處理，多媒體處理等)仍是有用的；(4)并行編程模型漸趨匯聚于三類標(biāo)準(zhǔn)模型：數(shù)據(jù)并行(如HPF)，消息傳遞(如PVM和MPI)和共享變量(如ANSI和X3H5)。在表8.1中，將并行編程所獲得的進(jìn)展在五個方面與串行編程進(jìn)行了比較。表8.1串行編程和并行編程比較一覽表

串行編程并行編程應(yīng)用領(lǐng)域科學(xué)和工程計(jì)算，數(shù)據(jù)處理，商務(wù)應(yīng)用等算法范例分而治之，分枝限界，動態(tài)規(guī)劃，回溯，貪心計(jì)算交互，異步迭代，分而治之，流水線，進(jìn)程農(nóng)莊，工作池編程模型馮·諾依曼隱式并行、數(shù)據(jù)并行、共享變量、消息傳遞編程語言Fortran，C，Cobol，4GLKAP，F(xiàn)ortran90，HPF，X3H5，PVM，MPI體系結(jié)構(gòu)不同類型的單處理機(jī)共享內(nèi)存（PVP，SMP，DSM）數(shù)據(jù)并行（SIMD）消息傳遞（MPP，Cluster）現(xiàn)在人們希望高性能的并行機(jī)應(yīng)是具有單一系統(tǒng)映象的巨大的工作站，使得很多用戶都能利用增強(qiáng)的處理能力和存儲容量來運(yùn)行多個串行作業(yè)，這就是所謂的串行程序并行系統(tǒng)SPPS(SerialProgramParallelSystem)。8.4.2并行編程方法現(xiàn)今編程模型主要有隱式并行、數(shù)據(jù)并行、消息傳遞和共享變量等四種。當(dāng)在實(shí)際的并行機(jī)上根據(jù)它們設(shè)計(jì)并行程序時，絕大部分均是采用擴(kuò)展Fortran和C語言的方法。目前有三種擴(kuò)展的方法：(1)庫函數(shù)(librarysubroutines)法：除了串行語言所包含的庫函數(shù)外，一組新的支持并行性和交互操作的庫函數(shù)(如MPI消息傳遞庫和POSIXPthreads多線程庫)引入到并行編程中；(2)新語言構(gòu)造(newlanguageconstructs)法：采用某些新的語言構(gòu)造來幫助并行編程以支持并行性和交互操作(如Fortran90中的聚集數(shù)組操作)；(3)編譯制導(dǎo)(compilerdirectives)法：編程語言保持不變，但是加進(jìn)稱之為編譯制導(dǎo)(pragma)的格式注釋。圖8.4中用一段簡單代碼來說明這些方法。所有3個并行程序均執(zhí)行相同的如圖8.4(a)所示的串行C代碼的計(jì)算。圖8.4(b)使用庫函數(shù)的方法實(shí)現(xiàn)之，其中兩個循環(huán)由p個進(jìn)程并行執(zhí)行，兩個庫函數(shù)my_process_id()和number_of_processes()開拓并行性，barrier()函數(shù)確保第一個循環(huán)執(zhí)行后所有進(jìn)程被同步，這樣第二個循環(huán)能使用第一個循環(huán)更新后的數(shù)組A的正確值；圖8.4(c)展示了使用新語言構(gòu)造執(zhí)行并行操作，F(xiàn)ortran90數(shù)組賦值結(jié)構(gòu)語句執(zhí)行N個元素相乘，然后以一個賦值語句進(jìn)行賦值，兩個數(shù)組賦值之間無需顯式同步，因?yàn)镕ortran90語句是松散同步的，即在下一語句開始執(zhí)行之前，一條賦值語句的所有操作均已完成；圖8.4(d)展示了編譯制導(dǎo)法實(shí)現(xiàn)并行操作，并行pragma指示下一語句應(yīng)并行執(zhí)行，SGI的pfor指使系統(tǒng)并行執(zhí)行下一循環(huán)，同步pragma產(chǎn)生一個路障同步。圖8.4三種并行化方法for(i=0；i<N；i++)A[i]=B[i]*B[i+1]；for(i=0；i<N；i++)C[i]=A[i]+A[i+1]；圖(a)順序化代碼段id=my_process_id()；p=number_of_processes()；for(i=id；i<N；i=i+p)A[i]=B[i]*B[i+1]；barrier()；/路障同步，解決先寫后讀的數(shù)據(jù)相關(guān)/for(i=id；i<N；i=i+p)C[i]=A[i]+A[i+1]；圖(b)使用庫函數(shù)的等效并行代碼圖8.4三種并行化方法my_process_id()，number_of_processes()，andbarrier()A(0：N-1)=B(0：N-1)*B(1：N)/采用蘊(yùn)式同步/C(0：N-1)=A(0：N-1)+A(1：N)圖(c)使用數(shù)組操作Fortran90等效代碼#pragmaparallel/以#pragma開頭的表示編譯器命令/#pragmashared(A，B，C)#pragmalocal(i){圖8.4三種并行化方法#pragmapforiterate(i=0；N；1)/此命令表示以并行方式執(zhí)行迭代操作/for(i=0；i<N；i++)A[i]=B[i]*B[i+1]；#pragmasynchronize/產(chǎn)生一個路障同步/#pragmapforiterate(i=0；N；1)for(i=0；i<N；i++)C[i]=A[i]+A[i+1]；}圖(d)SGIpowerC中使用pragma的等效代碼表8.2三種并行編程方法的優(yōu)缺點(diǎn)方法優(yōu)點(diǎn)缺點(diǎn)例子庫函數(shù)易于實(shí)現(xiàn)，不需要新的編譯器沒有編譯檢查、分析和優(yōu)化MPI、PVM、CrayCraft新語言構(gòu)造允許編譯檢查、分析和優(yōu)化難以實(shí)現(xiàn)，需要一個新的編譯器Fortran90、CrayCraft編譯制導(dǎo)是庫函數(shù)和新語言構(gòu)造兩者優(yōu)缺點(diǎn)的折衷，其顯著優(yōu)點(diǎn)是“普通串行程序+格式注釋”，可在任何串行平臺上編譯HPF、CrayCraft庫函數(shù)是目前使用最廣泛的方法。所有并行化和交互功能由附加到順序C或Fortran中的一組程序?qū)崿F(xiàn)。因此，原來的串行編譯器也能夠使用，不需要任何修改，編程者只要在原來的串行程序中加