并行計(jì)算系統(tǒng)的系統(tǒng)軟件的發(fā)展（僅供參考）

1、窗體頂端并行計(jì)算系統(tǒng)的系統(tǒng)軟件的發(fā)展（僅供參考）摘要:近年來,基于適當(dāng)數(shù)量(大概在16到1024范圍內(nèi))且相對(duì)高效處理器(比如用于科學(xué)工作站)的并行計(jì)算系統(tǒng)已經(jīng)在商業(yè)上可行.目前這些計(jì)算系統(tǒng)的系統(tǒng)軟件還需要程序員使用特殊技巧,利用系統(tǒng)帶來的高的計(jì)算速度.當(dāng)一個(gè)運(yùn)行于傳統(tǒng)的串行或向量系統(tǒng)的程序轉(zhuǎn)換到新的并行系統(tǒng)時(shí),程序員必須清楚新系統(tǒng)的并行計(jì)算模式和原始的操作.本文通過對(duì)并行計(jì)算的兩種模式數(shù)據(jù)并行和消息傳遞的描述,為舊的串行代碼向并行代碼轉(zhuǎn)換提供了基礎(chǔ).而這兩種模式的一些原始操作我們將通過例子(用已存在語言編寫)來描述和解釋,其中一些數(shù)據(jù)并行模式例子給出了代碼.一個(gè)并行計(jì)算系統(tǒng)的模型在本文中我們

2、假定一個(gè)并行計(jì)算系統(tǒng)帶有能控制整個(gè)系統(tǒng)的前置處理器(FE)和許多處理部件(PE).處理部件的數(shù)量是2的指數(shù),通常在16和1024之間.前置處理器和所有處理部件都有各自的內(nèi)存,并只對(duì)本處理器可見.本文所陳列的模型是幾個(gè)已用于商業(yè)的并行系統(tǒng)的簡(jiǎn)單化,包括思維機(jī)CM-5.這個(gè)模型區(qū)別于理論上經(jīng)常學(xué)習(xí),并行隨機(jī)存取的并行計(jì)算模型,因?yàn)樗鼪]有共享的內(nèi)存.因而,關(guān)于并行計(jì)算的書中的許多運(yùn)算法則沒有經(jīng)過重要更改時(shí),不能有效地在諸如上面討論的系統(tǒng)上執(zhí)行.在這樣的系統(tǒng)中有兩種重要的并行計(jì)算模式,它們是數(shù)據(jù)并行和消息傳遞.這兩種模式主要區(qū)別在于并行的間隔尺寸.數(shù)據(jù)并行模式的運(yùn)算規(guī)則假定有細(xì)密的并行性(在陳述和表達(dá)

3、層面上),而消息傳遞模式則假定有粗糙的并行性(處理器之間有相對(duì)較少的同步).接下來的兩節(jié)描述了這兩種模式.2、數(shù)據(jù)并行計(jì)算數(shù)據(jù)并行模式與上世紀(jì)60和70年代用于Illiac系統(tǒng)的相似.這種模式假定向量映射到很多虛擬的PE,而向量的每個(gè)元素儲(chǔ)存在不同的虛擬PE的本地內(nèi)存中.每個(gè)物理PE的內(nèi)存用于模擬許多實(shí)際的PE.(在CM-5上,虛擬的PE數(shù)應(yīng)至少是物理PE數(shù)的32倍.)在任何時(shí)候,一個(gè)關(guān)于數(shù)組元素操作的指令都是由每個(gè)PE在其本地內(nèi)存中執(zhí)行的.每個(gè)PE可以選擇是否忽略一個(gè)特定的指示.一種舊的數(shù)據(jù)并行模式的術(shù)語是SIMD,按Flynn關(guān)于計(jì)算系統(tǒng)的分類法稱為單指令多數(shù)據(jù).例如,假定X,Y,Z為64

4、*128*16維的整數(shù)數(shù)組,數(shù)據(jù)并行模式假定存在131072個(gè)虛擬處理器(即使物理PE比這少的多)為X(I,J,K),Y(I,J,K), Z(I,J,K)在同樣的虛擬PE的各自內(nèi)存中分配存儲(chǔ)空間.指令Z=X+Y將會(huì)使X(I,J,K)+Y(I,J,K)的值賦到Z(I,J,K),對(duì)所有對(duì)應(yīng)的I,J,K值.2.1.一些數(shù)據(jù)并行語言商業(yè)上用的兩種數(shù)據(jù)并行語言是CM Fortran和,及它們的各種版本.這些語言都支持代碼中使用大量的虛擬PE.高性能Fortran語言是Fortran的另一個(gè)版本,目的是用于并行計(jì)算系統(tǒng)和意圖作為執(zhí)行平臺(tái).因?yàn)檫@些語言(及那些簡(jiǎn)單的用于其它并行硬件的語言)主要是Fortra

5、n和C的擴(kuò)展,所以在傳統(tǒng)的串行或向量系統(tǒng)上運(yùn)行的用Fortran或C寫的程序,通常能夠正確地在并行系統(tǒng)上編譯(由CM Fortran或的編譯器)和運(yùn)行.然而,由于這些程序沒有清楚地運(yùn)用任何潛在的并行系統(tǒng),且導(dǎo)致了額外的用于支持并行的代碼,因此它們?cè)诓⑿邢到y(tǒng)上運(yùn)行時(shí)常常明顯地慢于傳統(tǒng)的串行系統(tǒng).因而修改這些程序以利用PE提供的并行是必須的.將一個(gè)程序從傳統(tǒng)的串行或向量系統(tǒng)修改到數(shù)據(jù)并行模式的系統(tǒng),需要懂得并行系統(tǒng)的原始操作和數(shù)據(jù)存儲(chǔ)問題.2.1.1.CM FortranCM Fortran包括Fortran 77 和Fortran 90 的向量處理特征2.1.2. 往C中加進(jìn)了形態(tài)的概念,及已存

6、在算子的額外的附加意義和新的庫函數(shù).2.2.語言原型本節(jié)介紹了數(shù)據(jù)并行語言的一些原始操作,并提供了具體的用CM Fortran和寫的具體例子.2.2.1.聲明一些編譯器能自動(dòng)將向量的各個(gè)元素分配到不同的虛擬PE中.另外一些需要程序員去指定一個(gè)在中稱為并行變量的特定數(shù)組,存儲(chǔ)在這些PE的內(nèi)存中.CM Fortran編譯器根據(jù)是否任意的并行操作都適用于數(shù)組決定是否將數(shù)組元素存儲(chǔ)在FE的內(nèi)存中.程序員可以不考慮編譯器指令性文件的任務(wù).例如,聲明和編譯器指令:導(dǎo)致數(shù)組A的元素分配到唯一一個(gè)虛擬處理器的內(nèi)存中,且B的所以元素都被分配到FE的本地內(nèi)存中.需要用戶去定義形態(tài),接著要聲明它的并行變量.這些并行

7、變量存儲(chǔ)在PE的本地內(nèi)存中,而數(shù)組存儲(chǔ)在FE的內(nèi)存中.接下來的命令定義了一個(gè)并行變量A和一個(gè)數(shù)組B.A將被存儲(chǔ)在PE內(nèi)存中,而B存儲(chǔ)在FE內(nèi)存中.同樣地,程序中的每步并行操作必須發(fā)生在一個(gè)特定的形態(tài)里.下面的內(nèi)容(在下一段樣本代碼中出現(xiàn))說明了現(xiàn)在的形態(tài).因?yàn)閺囊粋€(gè)PE內(nèi)存中復(fù)制數(shù)值到另一個(gè)PE內(nèi)存中或者到另一FE內(nèi)存中需要的時(shí)間比一步計(jì)算時(shí)間要多得多,因此應(yīng)盡量減少內(nèi)存之間數(shù)據(jù)的轉(zhuǎn)移.一般來說,所有數(shù)組(或的并行變量)應(yīng)該是一樣的形態(tài)和大小,而且應(yīng)存儲(chǔ)在PE內(nèi)存中.小的頻繁使用的數(shù)組應(yīng)當(dāng)被復(fù)制到每一個(gè)PE內(nèi)存中(這通常對(duì)庫子程序也適用).2.2.2.操作數(shù)據(jù)并行語言大都提供了許多新操作,基本

8、涵蓋了內(nèi)存之間數(shù)據(jù)的所有操作.我們可以將之規(guī)為多對(duì)多(這些操作返回和操作數(shù)一樣維數(shù)和大小的結(jié)果),少對(duì)多(這些操作將移動(dòng)一個(gè)數(shù)值到所有虛擬PE的內(nèi)存中或返回一個(gè)比操作數(shù)更高維數(shù)或至少更多元素的結(jié)果)和多對(duì)少(這些操作將返回一個(gè)數(shù)值或比原操作數(shù)低維或元素要少的結(jié)果).2.2.2.1.多對(duì)多:一些多對(duì)多操作提供了對(duì)數(shù)組(或并行變量)元素進(jìn)行逐個(gè)操作,例如本文前面的例子Z=X+Y.其它操作允許將變量的值從一個(gè)虛擬PE內(nèi)存?zhèn)鬟f到其它內(nèi)存.在CM Fortran中,這些功能由CShift和EOShift函數(shù)提供,它們分別支持循環(huán)和不停移動(dòng).每個(gè)函數(shù)的第一個(gè)參數(shù)是要移動(dòng)的數(shù)組,第二個(gè)是數(shù)組的維數(shù),第三個(gè)是

9、每次移動(dòng)的數(shù)量,第四個(gè)(對(duì)EOShift而言)指明要插入在左邊空位的數(shù)值.用pcoord函數(shù)來支持移動(dòng)操作.pcoord函數(shù)在當(dāng)前的形態(tài)中生成一個(gè)臨時(shí)并行變量,并對(duì)它的每一個(gè)元素按參數(shù)初始化.下面例子的代碼將相同的值賦予A、B、C和D.2.2.2.2.少對(duì)多:散發(fā)和廣播是少對(duì)多操作的例子.將一個(gè)數(shù)值廣播給數(shù)組的所有分量或并行變量在CM Fortran和中是簡(jiǎn)單的.如A=3或a=3;CM Fortran提供了一個(gè)函數(shù)可將一個(gè)低維的數(shù)組復(fù)制轉(zhuǎn)化成一個(gè)較高維的數(shù)組.復(fù)制了N個(gè)d維數(shù)組A并將之賦給d+1維數(shù)組ACube.2.2.2.3.多對(duì)少:收集操作是多對(duì)少操作的一類.我們的例子代碼都提供了將CM

10、Fortran中的數(shù)組或中的并行變量的多個(gè)值組合成一個(gè)單獨(dú)的值,下面的表顯示了一些典型的減少操作.2.2.3.控制結(jié)構(gòu)基本上,當(dāng)代碼從串行系統(tǒng)或向量系統(tǒng)修改到支持?jǐn)?shù)據(jù)并行模式的系統(tǒng)時(shí),只要可能,用并行控制結(jié)構(gòu)來修改循環(huán)是不錯(cuò)的.CM Fortran提供的新的控制結(jié)構(gòu)是ForAll和Where語句.ForAll允許計(jì)算中的數(shù)組元素下標(biāo)是一個(gè)操作數(shù)的并行操作表達(dá).例如:PrefixSumofA(J)中存儲(chǔ)著求和A(1)+ A(2)+ A(J).Where語句允許一些虛擬PE忽略某個(gè)特定的表達(dá).如:數(shù)值變量Minimum存儲(chǔ)著數(shù)組A分量中的最小值(A可以是任意維),對(duì)每個(gè)J,Count(J)=1,從

11、而對(duì)其它的J,A(J)=Minimum且Count(J)=0,數(shù)值變量Kount中存儲(chǔ)著Count元素的和,即A的最小值出現(xiàn)的個(gè)數(shù).提供了一個(gè)相似的表達(dá)方式,見前面的例子.Pcoord函數(shù)能用于ForAll語句達(dá)到相似的目的.3.消息傳遞計(jì)算(MPI)消息傳遞模式適用于粗紋理運(yùn)算法則系統(tǒng),在這里每個(gè)PE都能在需要的信息從別的PE或FE內(nèi)存里傳過來之前計(jì)算一段時(shí)間(粗略的經(jīng)驗(yàn)估計(jì)是至少100步計(jì)算操作).一個(gè)消息傳遞模式的舊術(shù)語是MIMD,即多指令多數(shù)據(jù).3.1.一些消息傳遞問題3.1.1.處理器的個(gè)數(shù)許多賣主庫需要用戶代碼寫在具體數(shù)量的PE上.由于這些庫大都提供了一個(gè)函數(shù)返回正在執(zhí)行的任務(wù)所用

12、的PE數(shù),程序本身必須合理地利用這些信息去區(qū)分PE中的工作量和數(shù)據(jù).3.1.2.PE代碼與FE+PE代碼的比較一些系統(tǒng)允許用戶為一個(gè)程序啟用多個(gè)不同的PE,并為這些PE具體分配任務(wù),每個(gè)PE在工作過程中能運(yùn)行一個(gè)不同的程序.其它一些系統(tǒng)只允許啟用一個(gè)PE程序,并保證這個(gè)程序被所有的PE執(zhí)行.在這樣的情況下,多PE程序當(dāng)然能被大段陳述表達(dá),假定有足夠的PE內(nèi)存來存儲(chǔ)這個(gè)程序(所有的PE內(nèi)存中都you代碼的復(fù)制).當(dāng)然,一些系統(tǒng)需要寫FE程序去控制整個(gè)用戶程序或多PE程序的邏輯流.另外一些或者推薦不要寫這樣一個(gè)FE程序,或者阻止這樣做.3.2.語言或庫原型不論消息傳遞是被語言支持還是被庫支持,其原

13、型是簡(jiǎn)單的.3.2.1.發(fā)送和接收一個(gè)語句或庫函數(shù)必須能使發(fā)送消息(字節(jié)流)到.同樣,一個(gè)語句或函數(shù)必須能使接收消息.一些庫提供了這樣一種原始操作,在允許發(fā)送消息到的同時(shí),接收來自的消息.3.2.2.阻塞和非阻塞大部分支持消息傳遞的語言和庫允許發(fā)送和接收操作阻塞和非阻塞.在阻塞發(fā)送中,發(fā)送消息的PE等待直到消息被其它的PE接收.在非阻塞發(fā)送中,發(fā)送消息的PE在消息發(fā)出之后可以自由地繼續(xù)計(jì)算,而不考慮消息什么時(shí)候(或是否)被收到.阻塞和非阻塞接收的定義是一樣的.3.2.3.匿名基本上發(fā)送PE知道接收PE的標(biāo)識(shí).然而,在有些語言或庫中,接收PE不知道發(fā)送PE的標(biāo)識(shí)而接收來自任何發(fā)送PE的消息.通常

14、一個(gè)庫會(huì)提供某種方法使發(fā)送者標(biāo)識(shí)一個(gè)消息,以便接收者能選擇是否接收當(dāng)前的消息.3.2.4.消息的長(zhǎng)度一些賣主的庫需要知道消息的字節(jié)長(zhǎng)度作為一個(gè)參數(shù),以便聲明發(fā)送和接收.3.3.一些消息傳遞的執(zhí)行通常消息傳遞程序用慣常的語言編寫,要向庫提交消息傳遞操作.一些語言包含了消息傳遞范例.3.3.1.AdaAda語言的任務(wù)設(shè)施是建立在消息傳遞范例的基礎(chǔ)上.一個(gè)任務(wù)訪問另一任務(wù)的連接點(diǎn).為了允許庫的可重用任務(wù)的建立,接收任務(wù)不必知道訪問者的身份.阻塞和非阻塞的發(fā)送和接收形式都允許.3.3.2.CMMD庫CM-5的消息傳遞庫稱為CMMD.這個(gè)庫里的子程序和函數(shù)能被Fortran,C,CM Fortran和程

15、序調(diào)用.(CM-5的PE每個(gè)有4個(gè)向量單元.CM Fortran或程序能在數(shù)據(jù)并行模式下在各自的物理PE里運(yùn)行,但交換信息必須在消息傳遞模式下由其余的PE執(zhí)行.)其它賣主的并行系統(tǒng)提供了相似的庫到CMMD.4.修改程序的總的建議由于數(shù)據(jù)并行和消息傳遞模式有不同的原始操作,通常寫一個(gè)新的建立在新數(shù)據(jù)并行或消息傳遞上的程序要比在并行系統(tǒng)上修改一個(gè)已經(jīng)存在的串行或向量程序更好.然而有時(shí)這是不現(xiàn)實(shí)的.在本節(jié)中我們提供了怎樣去修改一個(gè)已經(jīng)存在程序的建議.用軟件工具去決定哪段代碼需要大量的計(jì)算時(shí)間一般來說是十分有用的.大多轉(zhuǎn)換工作能被擴(kuò)展在這些段上.很多具體步驟取決于被轉(zhuǎn)換的程序是運(yùn)行在數(shù)據(jù)并行還是消息傳

16、遞模式上.4.1.修改到數(shù)據(jù)并行系統(tǒng)上當(dāng)修改已存在代碼到并行系統(tǒng)上時(shí)我們有兩種方法.仔細(xì)分配數(shù)組到內(nèi)存,大數(shù)組分到PE內(nèi)存,小的頻繁使用的復(fù)制到每個(gè)PE內(nèi)存中,不常使用的放在FE內(nèi)存中(如果PE的內(nèi)存很少).將循環(huán)操作改為并行操作或控制結(jié)構(gòu).這些策略在應(yīng)用中并不瑣碎.例如,如果一個(gè)大的用于計(jì)算密集的子程序的數(shù)組存儲(chǔ)在PE內(nèi)存里,那么其它子程序要用那個(gè)數(shù)組時(shí),必須修改為對(duì)數(shù)組進(jìn)行數(shù)據(jù)并行操作,而不是傳統(tǒng)的對(duì)每個(gè)數(shù)組元素進(jìn)行操作.4.2.修改到消息傳遞系統(tǒng)上我們的經(jīng)驗(yàn)是,分開調(diào)試運(yùn)算法則和庫使用細(xì)節(jié)會(huì)更容易些.我們特別地用Ada任務(wù)首先執(zhí)行一個(gè)新的或已被修改的傳遞運(yùn)算法則的消息.然后我們?cè)诰幾g時(shí)間

17、和運(yùn)行時(shí)間檢查的幫助下調(diào)試運(yùn)算法則,這由Ada提供并在處理大部分消息傳遞庫的復(fù)雜性后執(zhí)行.如果期望程序常常運(yùn)行在不同數(shù)量的物理PE上,那么將程序假定的PE數(shù)目參數(shù)化是非常重要的.5.一些數(shù)據(jù)并行程序的例子5.1.Cannon的運(yùn)算法則矩陣A與矩陣B相乘的Cannon運(yùn)算法則需要移動(dòng)A的列和B的行,以使A(I,K)和B(K,J)最初的值在相同的相對(duì)位置,也就存儲(chǔ)在相同的虛擬PE內(nèi)存中.數(shù)據(jù)并行相乘運(yùn)算法則的第一步是對(duì)A(I,K)和B(K,J)相乘.然后在一個(gè)循環(huán)中對(duì)A的每行和B的每列重復(fù)N-1次循環(huán)移動(dòng)到一個(gè)位置,并且對(duì)相乘被計(jì)算,它們的計(jì)算結(jié)果存在結(jié)果矩陣的元素中.5.1.1.CM Fortran5.1.2. 這個(gè)例子用.作為pcoord(當(dāng)前的維數(shù))的縮寫,本身提供.5.2.三維例子接下來的兩個(gè)例子顯示了兩個(gè)N*N的矩陣相乘的不同算法.算法用三個(gè)N