一個(gè)基于一般通信模式的多到一全局歸約操作算法(編輯修改稿)
2025-07-23 18:36 本頁面
【文章內(nèi)容簡介】 ource)。 /* 由定理1，任意進(jìn)程的后繼是唯一的，因此，使用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)生死鎖，則在進(jìn)程集中存在, 使得等待接受發(fā)送消息，等待接受發(fā)送消息, …, and 等待接受發(fā)送消息。由算法可知，必存在時(shí)間步使得, ,…, 。因此，中的進(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)基于該特殊邏輯拓?fù)浣Y(jié)構(gòu)的多到一全局歸約操作算法。下面用二個(gè)例子說明。 基于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_1ring (msg)。{ IF THEN { RECV (recv_msg, any_source)。 msgmsgrecv_msg。 } IF THEN SEND (m
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號-1