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

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

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

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

例8.2并行程序中的數據相關性分析假設有如下并行程序段：parfor(i=1；i<=n；i++){A[i]=B[i]/10；A[i-1]=B[i]+C[i]；}解：在上述并行程序段的循環體部分，下標只出現了i和i-1，即下標的變化范圍為2，因此，只需將上述并行循環展開2層，即可分析出2條語句在并行執行時可能會發生的數據相關性。假設i=1對應的指令序列在處理機P1上實現，i=2對應的指令序列在處理機P2上執行，如下所示：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]，為保證程序運行的正確性，即在順序程序中語句“A[1]=B[2]+C[2]；”應在語句“A[1]=B[1]/10；”之后執行，因此并行程序段中存在寫寫相關。值得注意的是，并不是循環體中兩條語句的輸出變量只要是數組A的分量，就一定發生寫寫相關，例如，將本例中的步長改為2，程序如下：parfor(i=1；i<=n；i=i+2){A[i]=B[i]/10；A[i-1]=B[i]+C[i]；}例8.3并行程序中的數據相關性分析假設有如下并行程序段：parfor(i=2；i<=n；i++)A[i]=A[i-2]/B[i]；解：在上述并行程序段的循環體部分只有一條語句，下標只出現了i和i-2，即下標的變化范圍為3，因此，只需將上述并行循環展開3層，即可分析出此條語句在并行執行時可能會出現的數據相關性。假設i=2、3、4對應的指令分別在處理機P2、P3、P4上執行，如下所示：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]進行讀寫操作，為保證程序運行的正確性，即在順序程序中語句“A[4]=A[2]/B[4]；”應在語句“A[2]=A[0]/B[2]；”之后執行，因此并行程序段中存在先寫后讀相關。

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

解：假定滿足上述條件的雙重循環如下:parfor(i=1；i<n；i++){for(j=1；j<n；j++){A[i,j]=A[i+1,j-1]；}}若直接使之對變量j的操作集中，而對i的操作分布到相互獨立的處理器上，來完成并行處理，將會出現先讀后寫數據相關。將上述循環展開后如下：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]…在上述加框語句、加下劃線語句、斜體表示的語句對之間均出現了先讀后寫數據相關。因此，需對并行循環體中的順序程序部分進行修改，修改后的循環控制程序如下：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并行編程概況對于所希望的應用，很多現存的并行代碼似乎是不存在的，即使有，也常不能用于用戶的并行機上，因為并行代碼原來都是為不同的并行結構(如SMP、MPP等)而寫的。并行編程的問題是：(1)并行算法范例至今尚不能被很好地理解和廣泛地接受；(2)并行編程是建立在不同的計算模型（PRAM模型、異步PRAM模型、BSP模型、logP模型、C3模型）上的，而它們沒有誰能象馮·諾依曼模型那樣被普遍的接受和認可；(3)絕大部分被使用的并行編程語言都是Fortran和C的推廣，它們都不能充分地表達不同并行結構的特點，既不成熟也不通用；(4)并行編程工具依賴于具體的并行機結構和計算機代的更迭，既不通用也不穩定，在某個平臺上開發的并行程序，很難移植到別的或將來的并行機上。盡管并行編程問題很多，但也有不少進展：(1)已經開發了很多并行算法，雖然它們大多基于理想的PRAM(ParallelRandom-AccessMachine)模型，但有些已被實際采用；(2)少量的并行算法范例已出現，并且正逐漸被接受；(3)編程類型漸趨匯聚于兩類：用于PVP、SMP和DSM的共享變量的單地址空間模型和用于MPP和機群的消息傳遞的多地址空間模型，SIMD模型已退出主流，但對專用領域(如信號、圖像處理，多媒體處理等)仍是有用的；(4)并行編程模型漸趨匯聚于三類標準模型：數據并行(如HPF)，消息傳遞(如PVM和MPI)和共享變量(如ANSI和X3H5)。在表8.1中，將并行編程所獲得的進展在五個方面與串行編程進行了比較。表8.1串行編程和并行編程比較一覽表

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