分布存儲并行數(shù)值計算通信庫界面設(shè)計

1、分布存儲并行數(shù)值計算通信庫界面設(shè)計熊玉慶中科院計算所摘要 指出了應(yīng)用程序界面是分布存儲并行數(shù)值計算通信庫設(shè)計中的一個主要方面。分析了從進(jìn)程抽象命名，基于源的消息選擇和非阻塞點到點通信三個方面提高通信庫的應(yīng)用程序界面。關(guān)鍵詞： 并行數(shù)值計算 通信庫 應(yīng)用程序界面分布存儲并行計算系統(tǒng)是目前高性能計算機的主流。通信庫是分布存儲并行計算系統(tǒng)的關(guān)鍵部分之一。目前，較常見的通信庫有MPI1，PVM2等。它們是面向一般應(yīng)用的，通用的消息傳遞界面。對于面向某一特殊領(lǐng)域的大型數(shù)值計算，這些庫的界面較低，不適合大型數(shù)值程序的開發(fā)34。為快速方便地開發(fā)高性能，高可靠的大型數(shù)值軟件，研制直接面向某一計算領(lǐng)域的通信庫是

2、十分必要和有價值的。這樣，通信庫界面設(shè)計就成為通信庫設(shè)計的一個重要方面。這樣的通信庫界面應(yīng)該是自然，簡潔，方便，使程序編寫更方便，編制的程序易于維護。本文從進(jìn)程抽象命名，基于源的消息選擇和非阻塞點到點通信三個方面討論如何提高通信庫的界面。并舉例說明它們的實現(xiàn)方法。1. 進(jìn)程抽象命名在MPI，PVM等通信庫中，一個進(jìn)程組中的進(jìn)程標(biāo)記（在MPI中進(jìn)程標(biāo)記的英文為rank）是線性的。但在許多數(shù)值計算中線性的進(jìn)程標(biāo)記不能充分反映進(jìn)程的邏輯通信模式。如在線性代數(shù)和油藏模擬計算中，二維的進(jìn)程網(wǎng)格常常是方便的。而在有的FFT計算中蝶型的進(jìn)程拓?fù)浣Y(jié)構(gòu)則更方便。由于進(jìn)程的拓?fù)浣Y(jié)構(gòu)反映了進(jìn)程的邏輯關(guān)系，因而，它對

3、程序的編寫及閱讀帶來極大方便。這里舉例說明進(jìn)程抽象命名的實現(xiàn)。一般地，設(shè)進(jìn)程的拓?fù)浣Y(jié)構(gòu)為。假設(shè)所要設(shè)計的數(shù)值計算通信庫是建立在MPI上。由于一個進(jìn)程組中的通信總是在一定的通信上下文中進(jìn)行，因此，必須將嵌入通信上下文中。在MPI中可實現(xiàn)如下：MPI_COMM_GROUP (comm, grp); /* 找出初始進(jìn)程組，進(jìn)程的拓?fù)浣Y(jié)構(gòu)為線性 */MPI_GROUP_INCL (grp, Ng, , tgrp) /* 形成新的進(jìn)程組，進(jìn)程的拓?fù)浣Y(jié)構(gòu)為 */MPI_COMM_CREATE (comm, tgrp, &tcomm); /* 建立新的通信上下文*/2. 基于源的消息選擇5在通信過程

4、中，接受進(jìn)程對消息的選擇一般是根據(jù)消息源和消息標(biāo)志。但使用標(biāo)志會帶來一些問題。例如，在一個循環(huán)體中，通信使用一個固定的消息標(biāo)志，那么，如果一個進(jìn)程花比其他進(jìn)程更多的時間完成一次循環(huán)，則該進(jìn)程可能接受下一個循環(huán)的數(shù)據(jù)作為本次循環(huán)的數(shù)據(jù)。此外，并行程序往往很大，要多個人或多個小組共同完成。這就要求在所有子程序和所有程序員之間進(jìn)行協(xié)調(diào)，使得各子程序中的通信消息標(biāo)志不發(fā)生沖突。當(dāng)以后要加入一個子程序時，必須保證新的子程序中的通信消息標(biāo)志與其他子程序不發(fā)生沖突。這使得程序設(shè)計變得困難而復(fù)雜。下面舉例說明基于源的消息選擇的實現(xiàn)。再次假設(shè)所設(shè)計的數(shù)值計算通信庫建立在MPI上。為了實現(xiàn)基于源的消息選擇，在通信

5、上下文中，對每個通信上下文，定義一個一一映射表示自該通信上下文建立以來，在該通信上下文中所進(jìn)行的群通信次數(shù)，的初值為1。為此，須另外定義通信上下文數(shù)據(jù)結(jié)構(gòu)如下：Struct CoNtExT MPI_Comm comm; int msgid, maxid, minid; comm是MPI的通信域，maxid, minid表示消息標(biāo)志的范圍，Context是指向該數(shù)據(jù)結(jié)構(gòu)的一個指針。在Context建立時maxid和minid 被賦初值。msgid是當(dāng)前消息標(biāo)志，初值為minid。定義如下：顯然，在區(qū)間1+(k-1)(maxid-minid), k(maxid-minid)上是個一一映射，其中，k

6、=1,2,。maxid和minid的值相差足夠大，使得在任意時刻在同一通信域中未完成的群通信操作數(shù)不超過maxid - minid個。因而，在任意時刻不同群通信所傳遞的消息的消息標(biāo)志不同，而同一次群通信中，各進(jìn)程發(fā)送或接收的消息標(biāo)志相同。對于中的點到點通信子程序，它們調(diào)用MPI的MPI_SEND和MPI_RECV來實現(xiàn)的。MPI_SEND和MPI_RECV在通信時，所傳遞的消息都帶有消息標(biāo)志，內(nèi)部把這些消息標(biāo)志都置為某個常量。該常量的值在maxid和minid之外。在同一通信域中，當(dāng)MPI的兩個進(jìn)程之間通信所傳遞消息的消息標(biāo)志相同，而且接收操作是MPI_RECV時，點到點通信操作的順序與程序執(zhí)

7、行的順序是一致，因而，接收進(jìn)程只需知道發(fā)送進(jìn)程標(biāo)記，就可對接收的消息進(jìn)行區(qū)別。這樣，在中就實現(xiàn)了點到點無消息標(biāo)志通信，從而通信對消息的選擇是基于源的。對于中的群通信(collective communications)，如果它們直接調(diào)用MPI的群通信子程序，則由于MPI的群通信子程序自身是無消息標(biāo)志通信，因而，自然實現(xiàn)了通信對消息的選擇是基于源的。假設(shè)它們是由MPI的MPI_SEND和MPI_RECV來實現(xiàn)的。MPI_SEND和MPI_RECV都以消息標(biāo)志及接收進(jìn)程或發(fā)送進(jìn)程標(biāo)記作為參數(shù)來區(qū)別消息。通信路經(jīng)是由邏輯拓?fù)銽OPO來決定的?，F(xiàn)以廣播通信為例來說明。設(shè)該通信子程序為_BCAST設(shè)某一

8、進(jìn)程調(diào)用廣播通信子程序，如果它是消息源進(jìn)程，則根據(jù)TOPO，_BCAST調(diào)用MPI_SEND將消息發(fā)給其他進(jìn)程。這里把消息發(fā)給哪個進(jìn)程是由TOPO來決定的。MPI_SEND所需消息標(biāo)志是如果調(diào)用廣播通信子程序的進(jìn)程不是消息源進(jìn)程，則_BCAST首先調(diào)用MPI_RECV，MPI_RECV的消息標(biāo)志也為，因而，在同一次廣播通信中的各進(jìn)程發(fā)送或接收的消息的標(biāo)志相同。由于同一次廣播通信中各進(jìn)程的TOPO參數(shù)一致，因此，MPI_RECV接到的消息與發(fā)給它的消息一致。MPI_RECV是全局阻塞的，在未接到消息之前，不會前進(jìn)到下一步。MPI_RECV接到消息后，_BCAST根據(jù)TOPO決定是否將消息發(fā)給其他

9、進(jìn)程及發(fā)給哪個進(jìn)程，如果要發(fā)送，消息的標(biāo)志仍然為。3.非阻塞點到點發(fā)送操作1為了提高并行計算的性能，讓通信與計算重疊是一種有效途徑，多線程是達(dá)到這種根的一個方法。當(dāng)一個線程阻塞等待通信時，同一個處理器上的另一個線程可被調(diào)用執(zhí)行。在單線程環(huán)境中，非阻塞通信方式是達(dá)到通信與計算重疊的一個重要方法。非阻塞點到點通信由兩部分組成，一部分是啟動操作，它啟動非阻塞通信。另一部分是完成操作，它完成一次非阻塞通信。在MPI中，非阻塞點到點發(fā)送操作子程序可描述如下：MPI_ISEND（buff, count, datatype, dest, tag, comm, request），它返回一個值id。buff是一

10、個緩沖區(qū)，含有要發(fā)送的消息。destination是消息要到達(dá)的進(jìn)程號。MPI_ISEND啟動一個通信，但不完成它。這個調(diào)用在消息從buff拷貝出來之前返回。MPI_WAIT（request, status），當(dāng)request標(biāo)識的操作完成時，也就是當(dāng)消息從發(fā)送緩沖區(qū)拷貝出來時，MPI_WAIT返回，否則，它阻塞。MPI_TEST（request, flag, status），如果request標(biāo)識的操作完成，它返回，并置flag=true，否則，flag=false。對于完成操作，MPI還提供幾個子程序，它們是MPI_WAIT和MPI_TEST的延伸。在非阻塞點到點發(fā)送操作中，操作未完成前，

11、發(fā)送緩沖區(qū)不能被使用。非阻塞通信可獲得相當(dāng)大的性能改善。然而，非阻塞通信的使用容易帶來錯誤，導(dǎo)致代碼過于復(fù)雜，這與并行數(shù)值計算通信庫易于使用的目的不符。為了利用非阻塞通信帶來的益處，同時避免它產(chǎn)生的缺陷。在并行數(shù)值計算通信庫設(shè)計時，在其內(nèi)部使用非阻塞通信，將非阻塞通信的復(fù)雜性對用戶屏蔽。設(shè)在并行數(shù)值計算通信庫中滿足上述要求的點到點發(fā)送子程序是_SEND。為實現(xiàn)這兩個子程序，首先在中設(shè)置一個公共緩沖池。_SEND的實現(xiàn)算法如下：_SEND（BUFF，DEST，） 從系統(tǒng)中申請一塊內(nèi)存buff； buff BUFF； 將buff放到公共緩沖池中； MPI_ISEND (buff, count, d

12、atatype, dest, tag, comm, request); MPI_TESTALL (count, array_of_request, flag, array_of_status); 將可重用的緩沖區(qū)從公共緩沖池中釋放；在MPI_TESTALL的參數(shù)表中，count 是公共緩沖池中緩沖區(qū)的個數(shù)，array_of_request表示與公共緩沖池中所有緩沖區(qū)相關(guān)的非阻塞通信的request對象隊列。為及時釋放公共緩沖池中的可重用的緩沖區(qū)，在的所有通信操作結(jié)束前，都執(zhí)行如下程序段： MPI_ISEND (buff, count, datatype, dest, tag, comm, re

13、quest); 將可重用的緩沖區(qū)從公共緩沖池中釋放；從上面算法，可知_SEND內(nèi)部執(zhí)行了非阻塞發(fā)送，但從用戶角度，避免了使用啟動與完成兩個操作。從而實現(xiàn)了上述目標(biāo)。4. 總結(jié)提高應(yīng)用程序界面是分布存儲并行數(shù)值計算通信庫設(shè)計中的一個重要方面。本文分析了從進(jìn)程抽象命名，基于源的消息選擇和非阻塞點到點發(fā)送操作三個方面提高通信庫的應(yīng)用界面。但提高通信庫界面并不僅限于這幾方面。有關(guān)的工作還有待于進(jìn)一步研究。致謝 本文工作完成于中科院軟件所并行軟件研究開發(fā)中心，并得到該中心孫家昶研究員，李玉成高工和中科院計算所張祥研究員的悉心指導(dǎo)。在此，向他們表示誠摯的謝意。參考文獻(xiàn)1 M. P. I. Forum, M

14、PI: A message passing interface standard, International Journal of Supercomputer applications and High Performance Computing, 8(3/4), 1994. Special issue on MPI.2 A. Geist, A. Beguelin, J. Dongarra, W. C. Jiang, R. Manchek, and V. Sunderam, PVM: Parallel Virtual Machine, The MIT Press, 1994.3 About mpC Parallel Programming Environment, Available via world wide web from URL=http:/www.ispras.ru/mpc.4 J. J. Dongarra, R. C. Whaley, “A U