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

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

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

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

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

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

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

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

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

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

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

11、發(fā)送緩沖區(qū)不能被使用。非阻塞通信可獲得相當大的性能改善。然而，非阻塞通信的使用容易帶來錯誤，導致代碼過于復雜，這與并行數(shù)值計算通信庫易于使用的目的不符。為了利用非阻塞通信帶來的益處，同時避免它產(chǎn)生的缺陷。在并行數(shù)值計算通信庫設計時，在其內部使用非阻塞通信，將非阻塞通信的復雜性對用戶屏蔽。設在并行數(shù)值計算通信庫中滿足上述要求的點到點發(fā)送子程序是_SEND。為實現(xiàn)這兩個子程序，首先在中設置一個公共緩沖池。_SEND的實現(xiàn)算法如下：_SEND（BUFF，DEST，） 從系統(tǒng)中申請一塊內存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ū)相關的非阻塞通信的request對象隊列。為及時釋放公共緩沖池中的可重用的緩沖區(qū)，在的所有通信操作結束前，都執(zhí)行如下程序段： MPI_ISEND (buff, count, datatype, dest, tag, comm, re

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