一個基于一般通信模式的多到一全局歸約操作算法(編輯修改稿)
2025-07-23 18:36 本頁面
【文章內(nèi)容簡介】 ource)。 /* 由定理1，任意進程的后繼是唯一的，因此，使用any_source能正確接到消息。 */ msg msg recv_msg 。 ENDOFWHILE。 。 。 /* 由樹的性質(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ā)送消息。由算法可知，必存在時間步使得, ,…, 。因此，中的進程都有后繼，由推論1，都不是根進程。由定理2，存在一進程，在中有進程，在時間步，使得, , …, 。這樣，有二個不同的后繼和 (如果)或和 (如果), 這與定理1相矛盾。定理4 算法執(zhí)行后，根進程中的數(shù)據(jù)為各進程中的數(shù)據(jù)經(jīng)運算后的結(jié)果。證 由定理2及算法可知，每個非根進程都把數(shù)據(jù)作為運算結(jié)果的一個因子傳到根進程。再由的結(jié)合律和交換律，可得到定理成立。4 基于特殊通信模式的全局多到一歸約算法設(shè)計上述算法是基于一般通信模式的多到一全局歸約操作算法，是建立在一般邏輯拓撲結(jié)構(gòu)之上的。由于一般邏輯拓撲結(jié)構(gòu)的抽象性，它實際上是一個框架，當給定一個具體的邏輯拓撲結(jié)構(gòu)，它可實現(xiàn)基于該特殊邏輯拓撲結(jié)構(gòu)的多到一全局歸約操作算法。下面用二個例子說明。 基于1環(huán)邏輯拓撲結(jié)構(gòu)的多到一全局歸約操作算法設(shè)計設(shè)進程集合，時間步集合，上的1環(huán)邏輯拓撲結(jié)構(gòu)為，其中，為根進程。圖2表示一個時的1環(huán)邏輯拓撲結(jié)構(gòu)。圖2 1環(huán)邏輯拓撲結(jié)構(gòu) 在1環(huán)邏輯拓撲結(jié)構(gòu)中，除外，其他進程都有唯一的前驅(qū)進程，除外，其他進程都有唯一后繼。由前面的算法，我們可得下面的基于1環(huán)邏輯拓撲結(jié)構(gòu)的多到一全局歸約操作算法。假設(shè)為調(diào)用進程。Reduc_1ring (msg)。{ IF THEN { RECV (recv_msg, any_source)。 msgmsgrecv_msg。 } IF THEN SEND (m
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1