一個基于一般通信模式的多到一全局歸約操作算法

1、一個基于一般通信模式的多到一全局歸約操作算法熊玉慶中國科學院計算技術研究所，100080 北京摘要 給出了一般邏輯拓撲結(jié)構定義，提出了一個基于一般通信模式的多到一全局歸約操作算法，該算法建立在一般邏輯拓撲結(jié)構上。邏輯拓撲結(jié)構是決定在分布并行計算中消息如何傳遞的機制。由于一般邏輯拓撲結(jié)構的抽象性，該算法實際上提供了一個多到一全局歸約操作實現(xiàn)算法框架。當給定一個具體的邏輯拓撲結(jié)構，該框架可給出基于特殊通信模式的多到一全局歸約操作算法。這為設計多到一全局歸約操作算法提供了一個新方法。關鍵詞 并行計算 多到一全局歸約操作 邏輯拓撲結(jié)構多到一全局歸約操作是將參與并行計算的多個進程中的數(shù)據(jù)進行加或求最大，

2、最小等操作，并將操作后的數(shù)據(jù)留在其中一個進程中。它在并行計算中廣泛使用1。很多關于它們的算法被提出，這些算法大部分是基于特殊的通信模式。本文首先給出通信模式的一般形式定義，即一GHIKLMNOP般邏輯拓撲結(jié)構定義。邏輯拓撲結(jié)構是決定在分布并行計算中消息如何傳遞的機制2。在此基礎上提出一個基于一般通信模式的多到一全局歸約操作算法，該算法建立在一般邏輯拓撲結(jié)構上。由于一般邏輯拓撲結(jié)構的抽象性，該算法實際上提供了一個多到一全局歸約操作實現(xiàn)算法框架。當給定一個具體的邏輯拓撲結(jié)構，根據(jù)該框架可得到基于特殊通信模式的多到一歸約操作算法。這為設計多到一全局歸約操作算法提供了一個新方法。1 一般邏輯拓撲結(jié)構定

3、義及其基本性質(zhì) 定義1 設，為進程集合，為時間步集合，其中，。是的一個劃分，其中，稱為根進程。是一棵有向加權樹，它的節(jié)點集合為，根節(jié)點為，權值集合為，方向是從葉節(jié)點到根。對任意非葉節(jié)點，設其入度為，存在一個從條進入該節(jié)點有向邊到的映射，稱為的關聯(lián)映射。有下列性質(zhì)： 最小的權為； 在每一條從葉節(jié)點到根節(jié)點的路徑上，邊的權值嚴格遞增； 進入任意非葉節(jié)點的有向邊中，權相等的邊的數(shù)目不大于； 對任意非葉節(jié)點，如果有條邊進入使得對其中任意邊，有 ，則這條邊的權值是連續(xù)的，即它們的權值可表示為 ,。其中，權最大（即）的有向邊稱作 進程的終止邊； 每個非葉節(jié)點中的所有進程的終止邊的權相等； 每個非根非葉節(jié)點

4、的射入邊的最大權值（即終止邊的權）與從該節(jié)點射出邊的權值 是連續(xù)的。即，如果射入邊的最大權值為，則射出邊的權值為,。后繼函數(shù)定義為：當且僅當，是從到的有向邊，且，的權為，否則，。定義2 設進程集合為，時間步集合為，。為后繼函數(shù)。一般邏輯拓撲結(jié)構定義為：。 例如，設進程集合為，時間步集合為，的劃分為，進程為根進程。樹如圖1所示，各節(jié)點的關聯(lián)映射為：，,。由定義1，后繼函數(shù)為, , ,，在其他情況下，的值為。由和定義2，可得下列邏輯拓撲結(jié)構： 這是2-樹邏輯拓撲結(jié)構，如圖2所示。 0 0 0 1t圖 1 樹圖 2 2-樹邏輯拓撲結(jié)構 定理1 在一般邏輯拓撲結(jié)構中，對任意的非根進程，存在唯一的進程使

5、得在某時間步有。稱作的前驅(qū)，稱作的后繼。證 設，由于是非根進程，不是樹的根。這樣，在樹中存在唯一節(jié)點使得有一條從到的有向邊。由定義1，存在唯一的使得。再由定義1，有，是樹中邊的權。從而，。由上面，可得下面推論。推論1 根進程沒有后繼。定理2 對任意的非根進程，在與之間，唯一地有進程，時間步使得，。證 設，。由于是非根進程，因而在樹中，是不根。由圖論可知，在樹中存在唯一的一條從到的路徑。設該路徑為。由定義1，在分別有進程，使得, , , ,，其中， 分別是的關聯(lián)映射。再由定義1，我們有，其中，是樹中邊的權。由定義2，可得定理成立。3 基于一般通信模式的多到一全局歸約操作算法設歸約操作運算為，滿足

6、結(jié)合律和交換律，即，和。為運算的操作數(shù)。每個操作數(shù)稱為運算結(jié)果的因子。如是的因子。設SEND和RECV是一對點到點通信原語。在SEND(msg, ), msg是要發(fā)送的消息，表示接受該消息的進程。在RECV(recv_msg, ), recv_msg表示存放要接受的消息，表示發(fā)送該消息的進程，當是any_source時，表明調(diào)用進程將接受由任意進程發(fā)來的消息。建立在一般邏輯拓撲結(jié)構上的多到一全局歸約操作算法描述如下。假設調(diào)用進程為。Reduce (msg, ) /* 進程調(diào)用該算法 */ IF 存在使得 THEN 設是最小的這樣的。 ； label: WHILE 存在使得 DO RECV(re

7、cv_msg, any_source); /* 由定理1，任意進程的后繼是唯一的，因此，使用any_source能正確接到消息。 */ msg msg recv_msg ; END-OF-WHILE; ; ; /* 由樹的性質(zhì) */ IF 存在使得 THEN goto label /* End of IF */ IF THEN SEND (msg, ); /* 由樹的性質(zhì)，可知存在，使得 */ /* End of Reduce */定理 3 上面算法不產(chǎn)生死鎖。證 如果算法產(chǎn)生死鎖，則在進程集中存在, 使得等待接受發(fā)送消息，等待接受發(fā)送消息, , and 等待接受發(fā)送消息。由算法可知，必存在時

8、間步使得, , 。因此，中的進程都有后繼，由推論1，都不是根進程。由定理2，存在一進程，在中有進程，在時間步，使得, , , 。這樣，有二個不同的后繼和 (如果)或和 (如果), 這與定理1相矛盾。定理4 算法執(zhí)行后，根進程中的數(shù)據(jù)為各進程中的數(shù)據(jù)經(jīng)運算后的結(jié)果。證 由定理2及算法可知，每個非根進程都把數(shù)據(jù)作為運算結(jié)果的一個因子傳到根進程。再由的結(jié)合律和交換律，可得到定理成立。4 基于特殊通信模式的全局多到一歸約算法設計上述算法是基于一般通信模式的多到一全局歸約操作算法，是建立在一般邏輯拓撲結(jié)構之上的。由于一般邏輯拓撲結(jié)構的抽象性，它實際上是一個框架，當給定一個具體的邏輯拓撲結(jié)構，它可實現(xiàn)基于

9、該特殊邏輯拓撲結(jié)構的多到一全局歸約操作算法。下面用二個例子說明。4.1 基于1-環(huán)邏輯拓撲結(jié)構的多到一全局歸約操作算法設計設進程集合，時間步集合，上的1-環(huán)邏輯拓撲結(jié)構為，其中，為根進程。圖2表示一個時的1-環(huán)邏輯拓撲結(jié)構。圖2 1-環(huán)邏輯拓撲結(jié)構 在1-環(huán)邏輯拓撲結(jié)構中，除外，其他進程都有唯一的前驅(qū)進程，除外，其他進程都有唯一后繼。由前面的算法，我們可得下面的基于1-環(huán)邏輯拓撲結(jié)構的多到一全局歸約操作算法。假設為調(diào)用進程。Reduc_1-ring (msg); IF THEN RECV (recv_msg, any_source); msgmsgrecv_msg; IF THEN SEND

10、(msg, ) /* 假設, */ /* end of Reduc_1-ring */4.2 基于2-樹邏輯拓撲結(jié)構的全局多到一歸約算法設計設進程集，時間步集，上的2-樹邏輯拓撲結(jié)構為，其中，是根進程，和是使，和位于到之間的整數(shù)。圖1表示時的2-樹邏輯拓撲結(jié)構。假設算法調(diào)用進程為，。當時，算法中的是使或或的最大值。當時，算法中的是使或的最大值。當，將該式變形為，由拓撲結(jié)構可知，的前驅(qū)下標為（時）和（時），后繼下標為。同理，可知當時，的前驅(qū)下標為（時）和（時），后繼下標為。當時，與3互質(zhì)，因為是使的最大值。的前驅(qū)下標為（時）和（時），如果，則為根，由推論1，它沒有后繼；如果，則或，由，它的后繼下

11、標為；如果，設，則,，由拓撲結(jié)構可知，的后繼下標為。這樣，由第4節(jié)的算法，我們有下面多到一全局歸約操作算法。Reduce_2-tree (msg); CASE OF : IF THEN FOR (;) IF THEN RECV (recv_msg, any_source); msgmsgrecv_msg; IF THEN RECV (recv_msg, any_source); msgmsgrecv_msg; /* end of FOR */ /* end of IF */ SEND (msg, ); : IF THEN FOR IF THEN RECV (recv_msg, any_sour

12、ce); msg msg recv_msg; IF THEN RECV (recv_msg, any_source); msg msg recv_msg; /* end of FOR */ /* end of IF */ SEND (msg, ); : FOR IF THEN RECV (recv_msg, any_source); msg msg recv_msg; IF THEN RECV (recv_msg, any_source); msg msg recv_msg; /* end of FOR */ IF THEN SEND (msg, ) IF THEN SEND (msg, ) /* , */ /* end of CASE */ /* end of ELSE */ /* end of Reduce_2-tree */致謝 本文工作完成于中科院軟件所并行軟件研究開發(fā)中心，并得到該中心孫家昶研究員