摘要：本文討論了k元n立方并行容錯(cuò)路由問(wèn)題，給出了k元n立方并行容錯(cuò)路由并行條數(shù)的一個(gè)下界，也給出每條路徑步長(zhǎng)的一個(gè)下界，證明過(guò)程同時(shí)也可轉(zhuǎn)化為求并行路徑的算法。

關(guān)鍵詞：k元n立方體 m子立方體 k元n立方的m子立方體連通圖 并行路由

中圖分類(lèi)號(hào)：TP302.8 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2014）08-0035-01

1 引言

針對(duì)并行處理器拓?fù)浣Y(jié)構(gòu)，人們已經(jīng)提出了很多模型，k元n立方是其中一種并行模型。從1997年被提之后，因其具有很多優(yōu)良特性，受到很多人的注意，對(duì)它進(jìn)行了大量研究。k元n立方體已經(jīng)應(yīng)用在幾個(gè)系統(tǒng)中，比如已被用于Ametek2020、J-Machine、Mosaic、iWarp等系統(tǒng)中。隨著數(shù)字技術(shù)的發(fā)展，處理器在并行系統(tǒng)中越來(lái)越多，出錯(cuò)可能性隨之增大，容錯(cuò)成為一個(gè)重要的研究課題。并行容錯(cuò)既可提高系統(tǒng)的效率，也能提高系統(tǒng)的可靠性。因此討論在k元n立方體中的并行容錯(cuò)路由問(wèn)題具有重要意義。

2 k元n立方體中的并行容錯(cuò)路由

k元n立方體：結(jié)點(diǎn)集V={x1x2…xn| xi為0到k-1之間的整數(shù)（i=1，2，…，n）}，兩個(gè)結(jié)點(diǎn)有邊相連當(dāng)且僅當(dāng)n個(gè)位中只有一位不同且不同的位之差的絕對(duì)值模k為1。

m子立方體：在k元n立方中，前n-m+1元確定，其余的m個(gè)元可任意選取，構(gòu)成的k元m立方體，稱為k元n立方的m子立方體，記為x1x2…xn-m+1**。稱x1x2…xn-m+1為x1x2…xn-m+1**的標(biāo)簽。

兩個(gè)m子立方體Lee距離：設(shè)k元n立方的兩個(gè)m子立方體為x1x2…xn-m+1**和y1y2…yn-m+1**，此兩m子立方體的Lee距離等于，其中為xi-yi模k后的值。為敘述方便常把模k省略。兩個(gè)m子立方體是鄰接的當(dāng)且僅當(dāng)它們的Lee距離為1。

k元n立方的m子立方體連通圖：在k元n立方中，如果所有的m子立方體中正確結(jié)點(diǎn)構(gòu)成連通圖，且任兩個(gè)鄰接的m子立方體有一對(duì)正確結(jié)點(diǎn)相鄰接。

從k元n立方的m子立方體連通圖定義可以看出，k元n立方的m子立方體連通圖是連通圖；不需要在每個(gè)m子立方體正確結(jié)點(diǎn)個(gè)數(shù)大于錯(cuò)誤結(jié)點(diǎn)個(gè)數(shù)，也即錯(cuò)誤結(jié)點(diǎn)個(gè)數(shù)可多余一半以上。

m子立方體的i位增鄰接m子立方體：設(shè)k元n立方m子立方體為x1…x2…xi…xn-m+1**，稱x1x2（xi+1）…xn-m+1**為x1x…2xi…xn-m+1**i位增鄰接m子立方體。簡(jiǎn)稱增鄰接m子立方體。

定理：在k元n立方的m子立方體連通圖H中，任給一對(duì)結(jié)點(diǎn)u、v，至少存在l條從u到v的并行容錯(cuò)路徑，每條路徑長(zhǎng)度不超過(guò)（d（Us，Ut）+k+1）mk步。其中l(wèi)=min（D[Us]，D[Ut]），D[Us]表示除u所在的m子立方體Us外其余的u的鄰接點(diǎn)所在的Us的i位增鄰接m子立方體的個(gè)數(shù)，D[Ut]表示除v所在的m子立方體Ut外其余的v的鄰接點(diǎn)所在的Ut的i位增鄰接m子立方體的個(gè)數(shù)，d（Us，Ut）是指Us和Ut之間Lee距離。

證明：

（1）當(dāng)d（Us，Ut）=0時(shí)，也即u，v在同一個(gè)m子立方體中Us，設(shè)u，v所在的m子立方體為x1x2…xn-m+1**，取Us鄰接的m子立方體W1=（x1+1）x2…xn-m+1**，W2=x1（x2+1）…xn-m+1**，…，Wn-m+1=x1x2…（xn-m+1+1）**。如果u的正確的鄰接點(diǎn)和v的正確的鄰接點(diǎn)在某個(gè)Wi中，則存在u到v經(jīng)過(guò)Wi路徑。如果u的正確的鄰接點(diǎn)在Wi中而v的正確的鄰接點(diǎn)不在Wi中且v的正確的鄰接點(diǎn)在某個(gè)Wj中而u的正確的鄰接點(diǎn)不在Wj中，此時(shí)有Wi和Wj共同增鄰接的W，則存在u到Wi，經(jīng)W，再到Wj，到v的路徑。如果u、v在Wi中沒(méi)有正確的鄰接點(diǎn)，拋棄掉Wi（1in-m+1）。此時(shí)至少有l(wèi)條從u到v的并行容錯(cuò)路徑。又在任何一個(gè)m子立方體中一對(duì)正確結(jié)點(diǎn)之間尋找一條路徑最多需mk步，故從u到v最多3mk步。

（2）當(dāng)d（Us，Ut）1時(shí)，設(shè)x1（x2+1）…xn-m+1**Us為=x1x2…xn-m+1**，取Us鄰接的m子立方體W1=（x1+1）x2…xn-m+1**，W2=x1（x2+1）…xn-m+1**， …，Wn-m+1=x1x2（xn-m+1+1）**分別為并行序列M1，M2，…，Mn-m+1的首個(gè)m子立方體。Wi（1in-m+1）到Ut的Lee距離最多增1。對(duì)每個(gè)Mi，選好首個(gè)立方體后，從x1x2…xn-m+1的第i+1位開(kāi)始到第n-m+1位，再?gòu)牡?位在循環(huán)回第i位，依次找出和Ut標(biāo)簽不同的位，設(shè)這些位的值為A1、A2、…、A（d-1）、Ad，在從A1、A2、…、A（d-1）的第一位A1起，增1或減1，得到新的m子立方體x1x2…（xA1+1）…xn-m+1**或x1x2…（xA1-1）…xn-m+1**使到Ut的Lee距離減1，此過(guò)程在第A1位繼續(xù)，直到到Ut的Lee距離不能減少，轉(zhuǎn)到A2。對(duì)A2上述過(guò)程一樣進(jìn)行，直到A（d-1）。對(duì)Ad，每次減1，直到和Ut鄰接。顯然，各個(gè)序列沒(méi)有共同的m子立方體，且最后一個(gè)m子立方體為Ut的增鄰接m子立方體。如果u的正確的鄰接點(diǎn)和v的正確的鄰接點(diǎn)在某個(gè)Mi序列首個(gè)和最后一個(gè)m子立方體中，則存在u到v經(jīng)過(guò)序列Mi路徑。如果u的正確的鄰接點(diǎn)在序列Mi首個(gè)m子立方體中而v的正確的鄰接點(diǎn)不在序列Mi的最后一個(gè)m子立方體中且v的正確的鄰接點(diǎn)在序列Mj的最后一個(gè)m子立方體中而u的正確的鄰接點(diǎn)不在Mj首個(gè)m子立方體中，此時(shí)有序列Mi和序列Mj共同的第一個(gè)增鄰接的m子立方體Wij，則存在u到Mi，經(jīng)Wij，再到Mj，到v的路徑。如果u、v在序列Mi中沒(méi)有正確的鄰接點(diǎn)，拋棄掉序列Mi（1in-m+1）。故u、v之間至少存在min（D[Us]，D[Ut]）條并行路徑。同樣，在任何一個(gè)m子立方體中一對(duì)正確結(jié)點(diǎn)之間尋找一條路徑最多需mk步，知從u到v最多（d（Us，Ut）+（k-2）+3）mk步。

（3）當(dāng)d（Us，Ut）=1時(shí)，和（2）類(lèi)似。

根據(jù)上面的證明過(guò)程可以寫(xiě)出并行容錯(cuò)路由算法。

3 結(jié)語(yǔ)

以上我們討論了k元n立方體的并行容錯(cuò)路由，得到并行路徑條數(shù)至少為min（D[Us]，D[Ut]），步長(zhǎng)不超過(guò)（d（Us，Ut）+k+1）mk步，容錯(cuò)不止適合結(jié)點(diǎn)錯(cuò)誤，還適合鏈路錯(cuò)誤，且結(jié)點(diǎn)容錯(cuò)能力超過(guò)一半以上。但所得結(jié)論和增鄰接m子立方體有關(guān)，事實(shí)上，還應(yīng)該和減鄰接m子立方體有關(guān)，也即結(jié)果也許還有可改進(jìn)的地方。

參考文獻(xiàn)

[1]王國(guó)軍，陳松喬，陳建二.具有大量錯(cuò)誤結(jié)點(diǎn)的超立方體網(wǎng)絡(luò)中并行路由算法[J].計(jì)算機(jī)工程與科學(xué)，2001（05）：5-12.

[2]張涌逸.k元n立方體網(wǎng)絡(luò)的容錯(cuò)路由[J].數(shù)字技術(shù)與應(yīng)用，2012（09）：24.

摘要：本文討論了k元n立方并行容錯(cuò)路由問(wèn)題，給出了k元n立方并行容錯(cuò)路由并行條數(shù)的一個(gè)下界，也給出每條路徑步長(zhǎng)的一個(gè)下界，證明過(guò)程同時(shí)也可轉(zhuǎn)化為求并行路徑的算法。

關(guān)鍵詞：k元n立方體 m子立方體 k元n立方的m子立方體連通圖 并行路由

中圖分類(lèi)號(hào)：TP302.8 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2014）08-0035-01

1 引言

針對(duì)并行處理器拓?fù)浣Y(jié)構(gòu)，人們已經(jīng)提出了很多模型，k元n立方是其中一種并行模型。從1997年被提之后，因其具有很多優(yōu)良特性，受到很多人的注意，對(duì)它進(jìn)行了大量研究。k元n立方體已經(jīng)應(yīng)用在幾個(gè)系統(tǒng)中，比如已被用于Ametek2020、J-Machine、Mosaic、iWarp等系統(tǒng)中。隨著數(shù)字技術(shù)的發(fā)展，處理器在并行系統(tǒng)中越來(lái)越多，出錯(cuò)可能性隨之增大，容錯(cuò)成為一個(gè)重要的研究課題。并行容錯(cuò)既可提高系統(tǒng)的效率，也能提高系統(tǒng)的可靠性。因此討論在k元n立方體中的并行容錯(cuò)路由問(wèn)題具有重要意義。

2 k元n立方體中的并行容錯(cuò)路由

k元n立方體：結(jié)點(diǎn)集V={x1x2…xn| xi為0到k-1之間的整數(shù)（i=1，2，…，n）}，兩個(gè)結(jié)點(diǎn)有邊相連當(dāng)且僅當(dāng)n個(gè)位中只有一位不同且不同的位之差的絕對(duì)值模k為1。

m子立方體：在k元n立方中，前n-m+1元確定，其余的m個(gè)元可任意選取，構(gòu)成的k元m立方體，稱為k元n立方的m子立方體，記為x1x2…xn-m+1**。稱x1x2…xn-m+1為x1x2…xn-m+1**的標(biāo)簽。

兩個(gè)m子立方體Lee距離：設(shè)k元n立方的兩個(gè)m子立方體為x1x2…xn-m+1**和y1y2…yn-m+1**，此兩m子立方體的Lee距離等于，其中為xi-yi模k后的值。為敘述方便常把模k省略。兩個(gè)m子立方體是鄰接的當(dāng)且僅當(dāng)它們的Lee距離為1。

k元n立方的m子立方體連通圖：在k元n立方中，如果所有的m子立方體中正確結(jié)點(diǎn)構(gòu)成連通圖，且任兩個(gè)鄰接的m子立方體有一對(duì)正確結(jié)點(diǎn)相鄰接。

從k元n立方的m子立方體連通圖定義可以看出，k元n立方的m子立方體連通圖是連通圖；不需要在每個(gè)m子立方體正確結(jié)點(diǎn)個(gè)數(shù)大于錯(cuò)誤結(jié)點(diǎn)個(gè)數(shù)，也即錯(cuò)誤結(jié)點(diǎn)個(gè)數(shù)可多余一半以上。

m子立方體的i位增鄰接m子立方體：設(shè)k元n立方m子立方體為x1…x2…xi…xn-m+1**，稱x1x2（xi+1）…xn-m+1**為x1x…2xi…xn-m+1**i位增鄰接m子立方體。簡(jiǎn)稱增鄰接m子立方體。

定理：在k元n立方的m子立方體連通圖H中，任給一對(duì)結(jié)點(diǎn)u、v，至少存在l條從u到v的并行容錯(cuò)路徑，每條路徑長(zhǎng)度不超過(guò)（d（Us，Ut）+k+1）mk步。其中l(wèi)=min（D[Us]，D[Ut]），D[Us]表示除u所在的m子立方體Us外其余的u的鄰接點(diǎn)所在的Us的i位增鄰接m子立方體的個(gè)數(shù)，D[Ut]表示除v所在的m子立方體Ut外其余的v的鄰接點(diǎn)所在的Ut的i位增鄰接m子立方體的個(gè)數(shù)，d（Us，Ut）是指Us和Ut之間Lee距離。

證明：

（1）當(dāng)d（Us，Ut）=0時(shí)，也即u，v在同一個(gè)m子立方體中Us，設(shè)u，v所在的m子立方體為x1x2…xn-m+1**，取Us鄰接的m子立方體W1=（x1+1）x2…xn-m+1**，W2=x1（x2+1）…xn-m+1**，…，Wn-m+1=x1x2…（xn-m+1+1）**。如果u的正確的鄰接點(diǎn)和v的正確的鄰接點(diǎn)在某個(gè)Wi中，則存在u到v經(jīng)過(guò)Wi路徑。如果u的正確的鄰接點(diǎn)在Wi中而v的正確的鄰接點(diǎn)不在Wi中且v的正確的鄰接點(diǎn)在某個(gè)Wj中而u的正確的鄰接點(diǎn)不在Wj中，此時(shí)有Wi和Wj共同增鄰接的W，則存在u到Wi，經(jīng)W，再到Wj，到v的路徑。如果u、v在Wi中沒(méi)有正確的鄰接點(diǎn)，拋棄掉Wi（1in-m+1）。此時(shí)至少有l(wèi)條從u到v的并行容錯(cuò)路徑。又在任何一個(gè)m子立方體中一對(duì)正確結(jié)點(diǎn)之間尋找一條路徑最多需mk步，故從u到v最多3mk步。

（2）當(dāng)d（Us，Ut）1時(shí)，設(shè)x1（x2+1）…xn-m+1**Us為=x1x2…xn-m+1**，取Us鄰接的m子立方體W1=（x1+1）x2…xn-m+1**，W2=x1（x2+1）…xn-m+1**， …，Wn-m+1=x1x2（xn-m+1+1）**分別為并行序列M1，M2，…，Mn-m+1的首個(gè)m子立方體。Wi（1in-m+1）到Ut的Lee距離最多增1。對(duì)每個(gè)Mi，選好首個(gè)立方體后，從x1x2…xn-m+1的第i+1位開(kāi)始到第n-m+1位，再?gòu)牡?位在循環(huán)回第i位，依次找出和Ut標(biāo)簽不同的位，設(shè)這些位的值為A1、A2、…、A（d-1）、Ad，在從A1、A2、…、A（d-1）的第一位A1起，增1或減1，得到新的m子立方體x1x2…（xA1+1）…xn-m+1**或x1x2…（xA1-1）…xn-m+1**使到Ut的Lee距離減1，此過(guò)程在第A1位繼續(xù)，直到到Ut的Lee距離不能減少，轉(zhuǎn)到A2。對(duì)A2上述過(guò)程一樣進(jìn)行，直到A（d-1）。對(duì)Ad，每次減1，直到和Ut鄰接。顯然，各個(gè)序列沒(méi)有共同的m子立方體，且最后一個(gè)m子立方體為Ut的增鄰接m子立方體。如果u的正確的鄰接點(diǎn)和v的正確的鄰接點(diǎn)在某個(gè)Mi序列首個(gè)和最后一個(gè)m子立方體中，則存在u到v經(jīng)過(guò)序列Mi路徑。如果u的正確的鄰接點(diǎn)在序列Mi首個(gè)m子立方體中而v的正確的鄰接點(diǎn)不在序列Mi的最后一個(gè)m子立方體中且v的正確的鄰接點(diǎn)在序列Mj的最后一個(gè)m子立方體中而u的正確的鄰接點(diǎn)不在Mj首個(gè)m子立方體中，此時(shí)有序列Mi和序列Mj共同的第一個(gè)增鄰接的m子立方體Wij，則存在u到Mi，經(jīng)Wij，再到Mj，到v的路徑。如果u、v在序列Mi中沒(méi)有正確的鄰接點(diǎn)，拋棄掉序列Mi（1in-m+1）。故u、v之間至少存在min（D[Us]，D[Ut]）條并行路徑。同樣，在任何一個(gè)m子立方體中一對(duì)正確結(jié)點(diǎn)之間尋找一條路徑最多需mk步，知從u到v最多（d（Us，Ut）+（k-2）+3）mk步。

（3）當(dāng)d（Us，Ut）=1時(shí)，和（2）類(lèi)似。

根據(jù)上面的證明過(guò)程可以寫(xiě)出并行容錯(cuò)路由算法。

3 結(jié)語(yǔ)

以上我們討論了k元n立方體的并行容錯(cuò)路由，得到并行路徑條數(shù)至少為min（D[Us]，D[Ut]），步長(zhǎng)不超過(guò)（d（Us，Ut）+k+1）mk步，容錯(cuò)不止適合結(jié)點(diǎn)錯(cuò)誤，還適合鏈路錯(cuò)誤，且結(jié)點(diǎn)容錯(cuò)能力超過(guò)一半以上。但所得結(jié)論和增鄰接m子立方體有關(guān)，事實(shí)上，還應(yīng)該和減鄰接m子立方體有關(guān)，也即結(jié)果也許還有可改進(jìn)的地方。

參考文獻(xiàn)

[1]王國(guó)軍，陳松喬，陳建二.具有大量錯(cuò)誤結(jié)點(diǎn)的超立方體網(wǎng)絡(luò)中并行路由算法[J].計(jì)算機(jī)工程與科學(xué)，2001（05）：5-12.

[2]張涌逸.k元n立方體網(wǎng)絡(luò)的容錯(cuò)路由[J].數(shù)字技術(shù)與應(yīng)用，2012（09）：24.

摘要：本文討論了k元n立方并行容錯(cuò)路由問(wèn)題，給出了k元n立方并行容錯(cuò)路由并行條數(shù)的一個(gè)下界，也給出每條路徑步長(zhǎng)的一個(gè)下界，證明過(guò)程同時(shí)也可轉(zhuǎn)化為求并行路徑的算法。

關(guān)鍵詞：k元n立方體 m子立方體 k元n立方的m子立方體連通圖 并行路由

中圖分類(lèi)號(hào)：TP302.8 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2014）08-0035-01

1 引言

針對(duì)并行處理器拓?fù)浣Y(jié)構(gòu)，人們已經(jīng)提出了很多模型，k元n立方是其中一種并行模型。從1997年被提之后，因其具有很多優(yōu)良特性，受到很多人的注意，對(duì)它進(jìn)行了大量研究。k元n立方體已經(jīng)應(yīng)用在幾個(gè)系統(tǒng)中，比如已被用于Ametek2020、J-Machine、Mosaic、iWarp等系統(tǒng)中。隨著數(shù)字技術(shù)的發(fā)展，處理器在并行系統(tǒng)中越來(lái)越多，出錯(cuò)可能性隨之增大，容錯(cuò)成為一個(gè)重要的研究課題。并行容錯(cuò)既可提高系統(tǒng)的效率，也能提高系統(tǒng)的可靠性。因此討論在k元n立方體中的并行容錯(cuò)路由問(wèn)題具有重要意義。

2 k元n立方體中的并行容錯(cuò)路由

k元n立方體：結(jié)點(diǎn)集V={x1x2…xn| xi為0到k-1之間的整數(shù)（i=1，2，…，n）}，兩個(gè)結(jié)點(diǎn)有邊相連當(dāng)且僅當(dāng)n個(gè)位中只有一位不同且不同的位之差的絕對(duì)值模k為1。

m子立方體：在k元n立方中，前n-m+1元確定，其余的m個(gè)元可任意選取，構(gòu)成的k元m立方體，稱為k元n立方的m子立方體，記為x1x2…xn-m+1**。稱x1x2…xn-m+1為x1x2…xn-m+1**的標(biāo)簽。

兩個(gè)m子立方體Lee距離：設(shè)k元n立方的兩個(gè)m子立方體為x1x2…xn-m+1**和y1y2…yn-m+1**，此兩m子立方體的Lee距離等于，其中為xi-yi模k后的值。為敘述方便常把模k省略。兩個(gè)m子立方體是鄰接的當(dāng)且僅當(dāng)它們的Lee距離為1。

k元n立方的m子立方體連通圖：在k元n立方中，如果所有的m子立方體中正確結(jié)點(diǎn)構(gòu)成連通圖，且任兩個(gè)鄰接的m子立方體有一對(duì)正確結(jié)點(diǎn)相鄰接。

從k元n立方的m子立方體連通圖定義可以看出，k元n立方的m子立方體連通圖是連通圖；不需要在每個(gè)m子立方體正確結(jié)點(diǎn)個(gè)數(shù)大于錯(cuò)誤結(jié)點(diǎn)個(gè)數(shù)，也即錯(cuò)誤結(jié)點(diǎn)個(gè)數(shù)可多余一半以上。

m子立方體的i位增鄰接m子立方體：設(shè)k元n立方m子立方體為x1…x2…xi…xn-m+1**，稱x1x2（xi+1）…xn-m+1**為x1x…2xi…xn-m+1**i位增鄰接m子立方體。簡(jiǎn)稱增鄰接m子立方體。

定理：在k元n立方的m子立方體連通圖H中，任給一對(duì)結(jié)點(diǎn)u、v，至少存在l條從u到v的并行容錯(cuò)路徑，每條路徑長(zhǎng)度不超過(guò)（d（Us，Ut）+k+1）mk步。其中l(wèi)=min（D[Us]，D[Ut]），D[Us]表示除u所在的m子立方體Us外其余的u的鄰接點(diǎn)所在的Us的i位增鄰接m子立方體的個(gè)數(shù)，D[Ut]表示除v所在的m子立方體Ut外其余的v的鄰接點(diǎn)所在的Ut的i位增鄰接m子立方體的個(gè)數(shù)，d（Us，Ut）是指Us和Ut之間Lee距離。

證明：

（1）當(dāng)d（Us，Ut）=0時(shí)，也即u，v在同一個(gè)m子立方體中Us，設(shè)u，v所在的m子立方體為x1x2…xn-m+1**，取Us鄰接的m子立方體W1=（x1+1）x2…xn-m+1**，W2=x1（x2+1）…xn-m+1**，…，Wn-m+1=x1x2…（xn-m+1+1）**。如果u的正確的鄰接點(diǎn)和v的正確的鄰接點(diǎn)在某個(gè)Wi中，則存在u到v經(jīng)過(guò)Wi路徑。如果u的正確的鄰接點(diǎn)在Wi中而v的正確的鄰接點(diǎn)不在Wi中且v的正確的鄰接點(diǎn)在某個(gè)Wj中而u的正確的鄰接點(diǎn)不在Wj中，此時(shí)有Wi和Wj共同增鄰接的W，則存在u到Wi，經(jīng)W，再到Wj，到v的路徑。如果u、v在Wi中沒(méi)有正確的鄰接點(diǎn)，拋棄掉Wi（1in-m+1）。此時(shí)至少有l(wèi)條從u到v的并行容錯(cuò)路徑。又在任何一個(gè)m子立方體中一對(duì)正確結(jié)點(diǎn)之間尋找一條路徑最多需mk步，故從u到v最多3mk步。

（2）當(dāng)d（Us，Ut）1時(shí)，設(shè)x1（x2+1）…xn-m+1**Us為=x1x2…xn-m+1**，取Us鄰接的m子立方體W1=（x1+1）x2…xn-m+1**，W2=x1（x2+1）…xn-m+1**， …，Wn-m+1=x1x2（xn-m+1+1）**分別為并行序列M1，M2，…，Mn-m+1的首個(gè)m子立方體。Wi（1in-m+1）到Ut的Lee距離最多增1。對(duì)每個(gè)Mi，選好首個(gè)立方體后，從x1x2…xn-m+1的第i+1位開(kāi)始到第n-m+1位，再?gòu)牡?位在循環(huán)回第i位，依次找出和Ut標(biāo)簽不同的位，設(shè)這些位的值為A1、A2、…、A（d-1）、Ad，在從A1、A2、…、A（d-1）的第一位A1起，增1或減1，得到新的m子立方體x1x2…（xA1+1）…xn-m+1**或x1x2…（xA1-1）…xn-m+1**使到Ut的Lee距離減1，此過(guò)程在第A1位繼續(xù)，直到到Ut的Lee距離不能減少，轉(zhuǎn)到A2。對(duì)A2上述過(guò)程一樣進(jìn)行，直到A（d-1）。對(duì)Ad，每次減1，直到和Ut鄰接。顯然，各個(gè)序列沒(méi)有共同的m子立方體，且最后一個(gè)m子立方體為Ut的增鄰接m子立方體。如果u的正確的鄰接點(diǎn)和v的正確的鄰接點(diǎn)在某個(gè)Mi序列首個(gè)和最后一個(gè)m子立方體中，則存在u到v經(jīng)過(guò)序列Mi路徑。如果u的正確的鄰接點(diǎn)在序列Mi首個(gè)m子立方體中而v的正確的鄰接點(diǎn)不在序列Mi的最后一個(gè)m子立方體中且v的正確的鄰接點(diǎn)在序列Mj的最后一個(gè)m子立方體中而u的正確的鄰接點(diǎn)不在Mj首個(gè)m子立方體中，此時(shí)有序列Mi和序列Mj共同的第一個(gè)增鄰接的m子立方體Wij，則存在u到Mi，經(jīng)Wij，再到Mj，到v的路徑。如果u、v在序列Mi中沒(méi)有正確的鄰接點(diǎn)，拋棄掉序列Mi（1in-m+1）。故u、v之間至少存在min（D[Us]，D[Ut]）條并行路徑。同樣，在任何一個(gè)m子立方體中一對(duì)正確結(jié)點(diǎn)之間尋找一條路徑最多需mk步，知從u到v最多（d（Us，Ut）+（k-2）+3）mk步。

（3）當(dāng)d（Us，Ut）=1時(shí)，和（2）類(lèi)似。

根據(jù)上面的證明過(guò)程可以寫(xiě)出并行容錯(cuò)路由算法。

3 結(jié)語(yǔ)

以上我們討論了k元n立方體的并行容錯(cuò)路由，得到并行路徑條數(shù)至少為min（D[Us]，D[Ut]），步長(zhǎng)不超過(guò)（d（Us，Ut）+k+1）mk步，容錯(cuò)不止適合結(jié)點(diǎn)錯(cuò)誤，還適合鏈路錯(cuò)誤，且結(jié)點(diǎn)容錯(cuò)能力超過(guò)一半以上。但所得結(jié)論和增鄰接m子立方體有關(guān)，事實(shí)上，還應(yīng)該和減鄰接m子立方體有關(guān)，也即結(jié)果也許還有可改進(jìn)的地方。

參考文獻(xiàn)

[1]王國(guó)軍，陳松喬，陳建二.具有大量錯(cuò)誤結(jié)點(diǎn)的超立方體網(wǎng)絡(luò)中并行路由算法[J].計(jì)算機(jī)工程與科學(xué)，2001（05）：5-12.

[2]張涌逸.k元n立方體網(wǎng)絡(luò)的容錯(cuò)路由[J].數(shù)字技術(shù)與應(yīng)用，2012（09）：24.