並列編程模型
来自维基百科,自由的百科全书
在電腦科學中,並列編程模型(Parallel programming model)是平行計算機架構的抽象化,通過它可方便的表達演算法和它們在程式中的合成。判別編程模型的價值可以通過它的通用性:在各種不同架構上能表達多大範圍的不同問題,和它的效能:編譯的程式在執行時有多高的效率[1]。並列編程模型的實現形式可以是從「順序編程」語言中呼叫的函數庫,作為現存語言的擴充,或作為全新的語言。
圍繞特定編程模型的共識是很重要的,這可導致建造不同的平行計算機來支援這個模型,從而促進軟件的可移植性。在這個意義上,編程模型被稱為在硬件和軟件之間的橋接[2]。
並列編程模型的分類
行程互動有關於並列行程能夠籍此相互通訊的機制。最常見的互動形式是共用主記憶體和訊息傳遞。
共用主記憶體是在行程間傳遞數據的高效方式。在共用主記憶體模型中,並列行程共用它們可以非同步讀與寫的全域地址空間。非同步並行訪問可能導致競爭條件,和用來避免它們的機制如:鎖、訊號量和監視器。常規的多核處理器直接支援共用主記憶體,很多並列程式語言和庫在設計上利用了它,比如採用分叉會合模型的:Cilk、OpenMP和線程建造塊[6]。
在訊息傳遞模型中,並列行程通過訊息傳遞相互交換數據。這種通訊可以是非同步的,就是說訊息可以在接收者準備好之前發出;或是同步的,就是說訊息發出前接收者必須準備好。交談循序程式(CSP)形式化了使用同步通訊通道來連接行程的訊息傳遞,並引出了重要的語言如:Occam、Limbo和Go。與之相對,演員模型使用非同步訊息傳遞,並被採用於如下語言的設計中:D、Scala和SALSA[7]。
分散式主記憶體指稱一類多處理器電腦系統,其中每個處理器都有自己私有的主記憶體,計算任務只能在本地數據上運算,如果需要遠端數據,計算任務必須與一個或多個遠端處理器通訊。在分散式主記憶體系統編程中的關鍵要點是如何把數據分佈到各個主記憶體上;依賴於所解決的問題,數據可以靜態分佈,也可以在節點間移動;數據可以在需要時移動,也可以事先推入新的節點。
MPI規定了用於分散式主記憶體系統的通訊協定,支援點到點通訊和集體通訊(collective communication)二者。MPI還是訊息傳遞API,帶有對其特徵在任何實現中必須如何表現的協定和語意規定[8]。MPI的目標是高效能、可伸縮性和可移植性,目前仍是高效能計算領域中統治性的模型[9]。此外還有支援單邊通訊(one-sided communication)的分區全域地址空間模型。
數據並列模型關注進行運算所在的數據集,典型的是正規結構的陣列。一組任務將在這些數據上運算,但是單獨的處於在不相交的分區中。數據並列通常對應SPMD編程模型[12],相應執行模型對應費林分類法中的SIMD(例如AVX擴充)或MIMD(例如Xeon Phi)[13],還有GPGPU採用的SIMT[14](例如NVIDIA Tesla)。
任務並列模型關注行程或線程的執行。這些行程通常表現出獨特性,並強調對通訊的需求。任務並列是表達訊息傳遞通訊的自然方式。任務並列通常對應MPMD編程模型,與SPMD的區別在於適合解決的問題而非執行模型[15]。
與上述顯式並列相反,隱式並列不向編程者透露任何編譯器、執行時系統或硬件負責的事情。例如,在編譯器中自動並列化是把順序代碼轉變程並列代碼的過程;而在電腦架構中,超純量執行是採用指令級並列來進行並列運算的機制,因自身限制而被實際利用為同時多線程/超線程。
在隱式並列中,行程互動對編程者均不可見,轉而由編譯器和/或執行時系統負責進行互動。函數式程式設計語言不存在副作用,允許無依賴的函數並列執行,人們已經進行了很多有關的研究實驗[16]。以SISAL和SAC為代表的一類數據流程編程語言,是可以高效隱式並列的函數式程式設計語言,其關鍵特徵是單賦值和面向陣列。
術語
平行計算模型是計算模型的一大範疇,包括:細胞自動機、PRAM機、LogP機、佩特里網、行程網和互動網等。計算模型是用來分析計算行程代價的一種抽象化,利用它分析並列演算法效能,可以不取決於特定實現和技術所特有的各種變化,並列演算法一般而言是針對特定計算模型而編寫的,為PRAM機編寫的偽碼通常會採用某種For循環形式的並行編程構造[17]。
編程模型指稱一種編程樣式,即通過看起來像庫呼叫的方式引發執行。例子包括POSIX的Pthreads庫和Apache Hadoop中的MapReduce。在這二者情況下,執行模型都符合這個庫所用語言的語法卻不能按照其語意來理解。不同於計算模型,編程模型特別暗含着對硬件或軟件實現的實際考慮[18]。
在平行計算中,執行模型經常必須暴露硬件特徵來達成高效能。並列硬件有大量的變種導致了同時需要類似數量的並列執行模型。對每個執行模型都建立一門新語言是不實際的,因此常見的實踐都是通過某個API來引發並列執行模型的行為。並列程式語言可以基於一種或一個組合的編程模型。例如,高效能Fortran基於共用主記憶體互動和數據並列問題分解,而Go提供共用主記憶體互動和訊息傳遞互動。
並列編程模型
這裏列出的編程模型是可稱為橋接模型的電腦的抽象模型[2],它提供了在一個機器的物理實現和編程者可獲得的這個機器的抽象概念之間的橋樑;換句話說,它意圖在硬件和軟件工程師之間提供共同的理解層面。成功的編程模型可以在現實中有效的實現並被編程者有效的作為目標;特別是應當有可能用典型的高階語言編譯器生成良好的代碼。從編程者的角度來看,這種橋接並列編程模型一般典型的位於Pthreads、IPC、MPI等之上,而在OpenMP、OpenACC等之下。
名稱 | 互動類別 | 分解類別 | 實現及用例 |
---|---|---|---|
分叉會合模型 | 共用主記憶體 | 數據 | Cilk,OpenMP,線程建造塊[6] |
整體同步並列模型 | 共用主記憶體 | 數據[19] | BSPlib[20]:MulticoreBSP[21]、BSPonMPI[22],Apache Giraph[23],Apache Hama[24] |
分區全域地址空間模型 | 分散式主記憶體 | 數據 | SHMEM[25],Coarray Fortran,Chapel,X10 |
交談循序程式模式 | 同步訊息傳遞 | 任務 | Occam,Ada,Go |
演員模型 | 非同步訊息傳遞 | 任務 | Erlang[26],D,Scala,很多的框架和庫實現 |
異構計算框架 | 共用主記憶體 | 數據 | OpenCL,CUDA[27],SYCL,Pocl[28] |
串流處理/數據流程範式 | 管道 | 數據[1] | Brook[29],Apache Flink,RaftLib,TensorFlow,Lustre |
進階綜合電子設計自動化 | 通道 | 任務 | C轉HDL:Handel-C、SystemC |
OpenCL將計算系統視為組成自一組「計算裝置」,它們可以是CPU或是附加的「加速器」比如GPU。它定義了一種類C語言用來寫程式。在OpenCL裝置上執行的函數叫做「內核」[30]:17。一個單一的計算裝置典型的組成自一些「計算單元」,它們依次又包含很多「處理元素」(PE)。一個單一的內核執行可以在所有或多個PE上並列執行。OpenCL定義了API,允許執行於主機上的程式,啟動在計算裝置上的內核,並管理裝置主記憶體,它至少在概念上分離於主機主記憶體。用OpenCL語言寫的程式預期會被即時編譯,所以使用OpenCL的應用程式在針對各種裝置的實現之間是可移植的[31]。
FPGA可以被用來解決任何可計算的問題,這通過用FPGA能實現軟微處理器的事實就可輕易的證明。它們的好處在於對某些應用它們明顯的要更快速,因為它們有着並列本質和在對用在特定處理上的邏輯門的數目方面的最佳化[32]。近年來開始興起使用OpenCL編程來利用FPGA提供的效能和能耗效率。OpenCL允許編程者用C語言編碼並把FPGA組合函數作為使用OpenCL構造的OpenCL計算內核的目標[33]。
MapReduce是通過並列、分散式演算法在叢集上處理和生成鍵/值對形式的大數據集的編程模型和有關實現[34],Apache Hadoop中將它與HDFS分立實現[35]。MapReduce受到了在函數式程式設計範式中常用的map和reduce函數的啟發[36],但是它們在MapReduce框架中的用途不同於它們在起初形式中那樣[37]。
並列編程模型還有很多,比如:馬里蘭大學學院市分校依據PRAM計算模型,建立了指令級並列顯式多線程的多處理器電腦和程式語言XMTC[38],實現了Spawn-Join範式[39]。
參見
參照
擴充閱讀
Wikiwand - on
Seamless Wikipedia browsing. On steroids.