並行程式設計

為了提高計算機的運行速度和系統的處理能力，在總體設計和邏輯設計中廣泛採用並行操作技術，使各部件並行工作。要求作業系統具有並發性及資源共享，於是採用了並行程式設計，它是能夠同時執行2個以上運算或邏輯操作的程式設計技術。採用了並行程式設計技術後，可使分時和多道程式更全面地利用計算機資源，使系統效率提高，開銷減小 (所占記憶體小，花費的處理時間短)。

基本介紹

• 中文名：並行程式設計
• 外文名：Parallel programming 
• 學科：物聯網
• 現狀：並行軟體的發展落後於並行硬體

並行程式設計

能同時執行兩個以上運算或邏輯操作的程式設計方法。所謂並行性，嚴格地說，有兩種含義：一是同時性，亦即平行性，指兩個或多個事件在同一時刻發生;二是並發性，指兩個或多個事件在同一時間間隔內發生。程式並行性分為控制並行性和數據並行性。並行程式的基本計算單位是進程。並行程式有多種模型，包括： 共享存儲; 分布存儲 (訊息傳遞); 數據並行;面向對象。與並行程式設計相適應的硬體也有不同類型，如多處理機，向量機，大規模並行機和機群系統等，相應有不同的並行程式設計方法。具體解題效率還與並行算法有關。

類別

目前並行編程類型逐漸匯聚於兩類:用於PVP,SMP和DSW的共享變數的單地址空間模型和用於MPP和機群的訊息傳遞的多地址空間模型.

並行編程模型逐漸匯聚於三類標準模型:數據並行(如:HPF),訊息傳遞(如:MPI和PVM),和共享變數(如OpenMp).

現在人們希望高性能的並行機應是 具有單一系統映像的巨大的工作站,使得很多用戶都能利用增強處理能力和儲存容量來運行多個串列作業,這就是所謂的串列程式並行系統SPPS.

當我們在實際的並行機上設計並行程式時,絕大部分均是採用擴展Fortran和C語言的辦法,目前有三種擴展的辦法:一是庫函式法:除了串列語言所包含的庫函式外,一組新的支持並行性和互動操作的庫函式(如MPI訊息傳遞庫和POSIXPthreads多執行緒庫)引入到並行程式設計中。二是新語言結構法:採用某些新的語言結構來幫助並行程式設計以支持並行性和互動操作(如Fortran 90 中的聚集數組操作); 三是編譯製導法:程式設計語言保持不變,但是將稱之為編譯製導的格式注釋引入到並行程式中.

並行編程

為了對實際的或邏輯的並行性編程，必須有一 些用以建立(create)與消滅(destroy ) (即， 設立與終止)進程的一些手段和用於這些進程彼此 間通信與同步的一種方法。許多系統與語言提供了 這樣的並行程式設計設施。顯式地提供這樣一些機 構的作業系統是DEC PDP-11與DEC VAX 計算機上的UNIX(q.v)系統。並行Pascal與 Modula都運行在DEC PDP-11上，Mesa語言 是在Xerox開發的，Ada (q.v.)語言是為美 國國防部開發的，它們都是含有並行程式設計結構的現代程式設計語言的例子。

FORK與JOIN語句是一組可用於動態地建 立與消滅進程的語句。用於說明並行性的靜態設施 是cobegin/coend結構。它具有如下形式：

cobegin S₁//S₂//…//S_ncoend

它表示(可能是複合的)語句S₁、S₂、……與S_n可並行執行。

同步機構有TEST AND SET這樣的機器 語言指令，它不可分割地執行下列操作序列： 檢查 一個存儲單元為0還是1，把檢查結果存儲在一個暫存器中，使該單元置位為1; 對於實現鎖定或象 對信號量的Dijkstra P與V操作這樣的低級同步原語，TEST AND SET是方便的。在較高級是監督程式。這一設施用來說明表示一資源的共享數據 結構與定義用於獲得、釋放與存取該資源的過程; 監督程式容許封閉與調度可被若干進程使用的資源 目標。

獲得同步的另一種常用的方法是通過信息傳送原語。簡單的例子是send(p，m)與receive (p，m)。send(p.m)導致信息m傳送到進 程p，receive(p.m)等待來自進程p的信息， 把該信息插入m中。因為它並不依賴通過公用存儲器中的共享變數進行通信，信息傳遞對於分散式計算是有用的，在分散式計算中，各任務通過通信線路連線。

仍在進行精煉與測試的Ada語言具有把過程調 用與信息傳送兩者結合起來的通信與同步語句。在 兩個進程之間的通信通常進行如下。

一個進程用含有輸入與輸出參數的任務入口調 用來調用另一個進程，而被調用的進程發出一個等 待這樣一個調用的accept語句;accept語句還包 括一個任意的語句序列，該語句序列作為接受此任 務入口調用時出現的集結的一部分執行。在這個互動作用之後，調用進程與被調用進程兩者可再並行 執行。Ada還提供一個選擇等待語句，在其中有 在處於“開路”的一組accept語句之間的不確定 選擇(即，如果發出一個相應的任務入口調用，其中一個集結是可能的)。

作為並行程式設計的一個例子，我們給出對於 一個公用緩衝問題的解決方法。假設我們要為一個 二進程系統編程，其中一個進程是生產者進程，它 把一些記錄添加到一個存儲區，另一進程是消費者 進程，它把這些記錄移走。生產者進程可以是一個 與輸入設備關聯的進程，它把輸入記錄添加到存儲 緩衝器中，而消費者進程負責檢索記錄並處理它 們;另一方面，生產者進程可產生用於與一輸出設 備關聯的消費者進程的輸出記錄。

公用緩衝區有N個記錄(N≥1)的存儲。主 要問題是使緩衝器的處理同步，因而：

1.如果有空間的話，生產者進程可以只添加 一個記錄到緩衝器;如果存在一個記錄的 話，消費者進程可以只移走一個記錄。

2.一次僅一個進程可處理緩衝區。

我們假設生產者進程與消費者進程兩者均是 “永遠”循環的循環進程。採用信號量與cobegin/ coend，程式的輪廓如下：

Semaphore empty(N)，{緩衝器中空槽的 數目，初始為N}

full(0)，{緩衝器中滿記 錄的數目，初 始為0}

lock(1); {在緩衝器處理期 間，保證互斥}

Cobegin producer：

loop

begin produce Next Record;

P(empty); {只有在緩衝器中 可得到一個空槽 的情況下才進 行}

P(lock); {設定鎖定到0，避 免緩衝器被Consumer存取}

Add Record To Buffer;

V(lock); {設定鎖定到1，允 許被producer 或Consumer存 取}

V(full) {增加緩衝器中滿 記錄的數目

end consumer：

loop begin P(full); {只有在緩衝器中 有一個滿記錄時 進行}

P(lock); {對producer鎖 住緩衝器}

Take Record From Buffer;

V(lock); {緩衝器開鎖}

V(empty); {增加緩衝器中可 用槽的數目}

process Record end Coend