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

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

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

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

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

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

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

7、cv_msg, any_source); /* 由定理1，任意進(jìn)程的后繼是唯一的，因此，使用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)生死鎖，則在進(jìn)程集中存在, 使得等待接受發(fā)送消息，等待接受發(fā)送消息, , and 等待接受發(fā)送消息。由算法可知，必存在時(shí)

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

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

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

11、標(biāo)為；如果，設(shè)，則,，由拓?fù)浣Y(jié)構(gòu)可知，的后繼下標(biāo)為。這樣，由第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ā)中心，并得到該中心孫家昶研究員