k元n立方并行容錯路由

摘要：本文討論了k元n立方并行容錯路由問題，給出了k元n立方并行容錯路由并行條數的一個下界，也給出每條路徑步長的一個下界，證明過程同時也可轉化為求并行路徑的算法。

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

中圖分類號：TP302.8 文獻標識碼：A 文章編號：1007-9416（2014）08-0035-01

1 引言

針對并行處理器拓撲結構，人們已經提出了很多模型，k元n立方是其中一種并行模型。從1997年被提之后，因其具有很多優良特性，受到很多人的注意，對它進行了大量研究。k元n立方體已經應用在幾個系統中，比如已被用于Ametek2020、J-Machine、Mosaic、iWarp等系統中。隨著數字技術的發展，處理器在并行系統中越來越多，出錯可能性隨之增大，容錯成為一個重要的研究課題。并行容錯既可提高系統的效率，也能提高系統的可靠性。因此討論在k元n立方體中的并行容錯路由問題具有重要意義。

2 k元n立方體中的并行容錯路由

k元n立方體：結點集V={x1x2…xn| xi為0到k-1之間的整數（i=1，2，…，n）}，兩個結點有邊相連當且僅當n個位中只有一位不同且不同的位之差的絕對值模k為1。

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

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

k元n立方的m子立方體連通圖：在k元n立方中，如果所有的m子立方體中正確結點構成連通圖，且任兩個鄰接的m子立方體有一對正確結點相鄰接。

從k元n立方的m子立方體連通圖定義可以看出，k元n立方的m子立方體連通圖是連通圖；不需要在每個m子立方體正確結點個數大于錯誤結點個數，也即錯誤結點個數可多余一半以上。

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

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

證明：

（1）當d（Us，Ut）=0時，也即u，v在同一個m子立方體中Us，設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的正確的鄰接點和v的正確的鄰接點在某個Wi中，則存在u到v經過Wi路徑。如果u的正確的鄰接點在Wi中而v的正確的鄰接點不在Wi中且v的正確的鄰接點在某個Wj中而u的正確的鄰接點不在Wj中，此時有Wi和Wj共同增鄰接的W，則存在u到Wi，經W，再到Wj，到v的路徑。如果u、v在Wi中沒有正確的鄰接點，拋棄掉Wi（1in-m+1）。此時至少有l條從u到v的并行容錯路徑。又在任何一個m子立方體中一對正確結點之間尋找一條路徑最多需mk步，故從u到v最多3mk步。

（2）當d（Us，Ut）1時，設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的首個m子立方體。Wi（1in-m+1）到Ut的Lee距離最多增1。對每個Mi，選好首個立方體后，從x1x2…xn-m+1的第i+1位開始到第n-m+1位，再從第1位在循環回第i位，依次找出和Ut標簽不同的位，設這些位的值為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，此過程在第A1位繼續，直到到Ut的Lee距離不能減少，轉到A2。對A2上述過程一樣進行，直到A（d-1）。對Ad，每次減1，直到和Ut鄰接。顯然，各個序列沒有共同的m子立方體，且最后一個m子立方體為Ut的增鄰接m子立方體。如果u的正確的鄰接點和v的正確的鄰接點在某個Mi序列首個和最后一個m子立方體中，則存在u到v經過序列Mi路徑。如果u的正確的鄰接點在序列Mi首個m子立方體中而v的正確的鄰接點不在序列Mi的最后一個m子立方體中且v的正確的鄰接點在序列Mj的最后一個m子立方體中而u的正確的鄰接點不在Mj首個m子立方體中，此時有序列Mi和序列Mj共同的第一個增鄰接的m子立方體Wij，則存在u到Mi，經Wij，再到Mj，到v的路徑。如果u、v在序列Mi中沒有正確的鄰接點，拋棄掉序列Mi（1in-m+1）。故u、v之間至少存在min（D[Us]，D[Ut]）條并行路徑。同樣，在任何一個m子立方體中一對正確結點之間尋找一條路徑最多需mk步，知從u到v最多（d（Us，Ut）+（k-2）+3）mk步。

（3）當d（Us，Ut）=1時，和（2）類似。

根據上面的證明過程可以寫出并行容錯路由算法。

3 結語

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

參考文獻

[1]王國軍，陳松喬，陳建二.具有大量錯誤結點的超立方體網絡中并行路由算法[J].計算機工程與科學，2001（05）：5-12.

[2]張涌逸.k元n立方體網絡的容錯路由[J].數字技術與應用，2012（09）：24.

摘要：本文討論了k元n立方并行容錯路由問題，給出了k元n立方并行容錯路由并行條數的一個下界，也給出每條路徑步長的一個下界，證明過程同時也可轉化為求并行路徑的算法。

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

中圖分類號：TP302.8 文獻標識碼：A 文章編號：1007-9416（2014）08-0035-01

1 引言

針對并行處理器拓撲結構，人們已經提出了很多模型，k元n立方是其中一種并行模型。從1997年被提之后，因其具有很多優良特性，受到很多人的注意，對它進行了大量研究。k元n立方體已經應用在幾個系統中，比如已被用于Ametek2020、J-Machine、Mosaic、iWarp等系統中。隨著數字技術的發展，處理器在并行系統中越來越多，出錯可能性隨之增大，容錯成為一個重要的研究課題。并行容錯既可提高系統的效率，也能提高系統的可靠性。因此討論在k元n立方體中的并行容錯路由問題具有重要意義。

2 k元n立方體中的并行容錯路由

k元n立方體：結點集V={x1x2…xn| xi為0到k-1之間的整數（i=1，2，…，n）}，兩個結點有邊相連當且僅當n個位中只有一位不同且不同的位之差的絕對值模k為1。

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

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

k元n立方的m子立方體連通圖：在k元n立方中，如果所有的m子立方體中正確結點構成連通圖，且任兩個鄰接的m子立方體有一對正確結點相鄰接。

從k元n立方的m子立方體連通圖定義可以看出，k元n立方的m子立方體連通圖是連通圖；不需要在每個m子立方體正確結點個數大于錯誤結點個數，也即錯誤結點個數可多余一半以上。

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

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

證明：

（1）當d（Us，Ut）=0時，也即u，v在同一個m子立方體中Us，設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的正確的鄰接點和v的正確的鄰接點在某個Wi中，則存在u到v經過Wi路徑。如果u的正確的鄰接點在Wi中而v的正確的鄰接點不在Wi中且v的正確的鄰接點在某個Wj中而u的正確的鄰接點不在Wj中，此時有Wi和Wj共同增鄰接的W，則存在u到Wi，經W，再到Wj，到v的路徑。如果u、v在Wi中沒有正確的鄰接點，拋棄掉Wi（1in-m+1）。此時至少有l條從u到v的并行容錯路徑。又在任何一個m子立方體中一對正確結點之間尋找一條路徑最多需mk步，故從u到v最多3mk步。

（2）當d（Us，Ut）1時，設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的首個m子立方體。Wi（1in-m+1）到Ut的Lee距離最多增1。對每個Mi，選好首個立方體后，從x1x2…xn-m+1的第i+1位開始到第n-m+1位，再從第1位在循環回第i位，依次找出和Ut標簽不同的位，設這些位的值為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，此過程在第A1位繼續，直到到Ut的Lee距離不能減少，轉到A2。對A2上述過程一樣進行，直到A（d-1）。對Ad，每次減1，直到和Ut鄰接。顯然，各個序列沒有共同的m子立方體，且最后一個m子立方體為Ut的增鄰接m子立方體。如果u的正確的鄰接點和v的正確的鄰接點在某個Mi序列首個和最后一個m子立方體中，則存在u到v經過序列Mi路徑。如果u的正確的鄰接點在序列Mi首個m子立方體中而v的正確的鄰接點不在序列Mi的最后一個m子立方體中且v的正確的鄰接點在序列Mj的最后一個m子立方體中而u的正確的鄰接點不在Mj首個m子立方體中，此時有序列Mi和序列Mj共同的第一個增鄰接的m子立方體Wij，則存在u到Mi，經Wij，再到Mj，到v的路徑。如果u、v在序列Mi中沒有正確的鄰接點，拋棄掉序列Mi（1in-m+1）。故u、v之間至少存在min（D[Us]，D[Ut]）條并行路徑。同樣，在任何一個m子立方體中一對正確結點之間尋找一條路徑最多需mk步，知從u到v最多（d（Us，Ut）+（k-2）+3）mk步。

（3）當d（Us，Ut）=1時，和（2）類似。

根據上面的證明過程可以寫出并行容錯路由算法。

3 結語

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

參考文獻

[1]王國軍，陳松喬，陳建二.具有大量錯誤結點的超立方體網絡中并行路由算法[J].計算機工程與科學，2001（05）：5-12.

[2]張涌逸.k元n立方體網絡的容錯路由[J].數字技術與應用，2012（09）：24.

摘要：本文討論了k元n立方并行容錯路由問題，給出了k元n立方并行容錯路由并行條數的一個下界，也給出每條路徑步長的一個下界，證明過程同時也可轉化為求并行路徑的算法。

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

中圖分類號：TP302.8 文獻標識碼：A 文章編號：1007-9416（2014）08-0035-01

1 引言

針對并行處理器拓撲結構，人們已經提出了很多模型，k元n立方是其中一種并行模型。從1997年被提之后，因其具有很多優良特性，受到很多人的注意，對它進行了大量研究。k元n立方體已經應用在幾個系統中，比如已被用于Ametek2020、J-Machine、Mosaic、iWarp等系統中。隨著數字技術的發展，處理器在并行系統中越來越多，出錯可能性隨之增大，容錯成為一個重要的研究課題。并行容錯既可提高系統的效率，也能提高系統的可靠性。因此討論在k元n立方體中的并行容錯路由問題具有重要意義。

2 k元n立方體中的并行容錯路由

k元n立方體：結點集V={x1x2…xn| xi為0到k-1之間的整數（i=1，2，…，n）}，兩個結點有邊相連當且僅當n個位中只有一位不同且不同的位之差的絕對值模k為1。

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

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

k元n立方的m子立方體連通圖：在k元n立方中，如果所有的m子立方體中正確結點構成連通圖，且任兩個鄰接的m子立方體有一對正確結點相鄰接。

從k元n立方的m子立方體連通圖定義可以看出，k元n立方的m子立方體連通圖是連通圖；不需要在每個m子立方體正確結點個數大于錯誤結點個數，也即錯誤結點個數可多余一半以上。

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

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

證明：

（1）當d（Us，Ut）=0時，也即u，v在同一個m子立方體中Us，設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的正確的鄰接點和v的正確的鄰接點在某個Wi中，則存在u到v經過Wi路徑。如果u的正確的鄰接點在Wi中而v的正確的鄰接點不在Wi中且v的正確的鄰接點在某個Wj中而u的正確的鄰接點不在Wj中，此時有Wi和Wj共同增鄰接的W，則存在u到Wi，經W，再到Wj，到v的路徑。如果u、v在Wi中沒有正確的鄰接點，拋棄掉Wi（1in-m+1）。此時至少有l條從u到v的并行容錯路徑。又在任何一個m子立方體中一對正確結點之間尋找一條路徑最多需mk步，故從u到v最多3mk步。

（2）當d（Us，Ut）1時，設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的首個m子立方體。Wi（1in-m+1）到Ut的Lee距離最多增1。對每個Mi，選好首個立方體后，從x1x2…xn-m+1的第i+1位開始到第n-m+1位，再從第1位在循環回第i位，依次找出和Ut標簽不同的位，設這些位的值為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，此過程在第A1位繼續，直到到Ut的Lee距離不能減少，轉到A2。對A2上述過程一樣進行，直到A（d-1）。對Ad，每次減1，直到和Ut鄰接。顯然，各個序列沒有共同的m子立方體，且最后一個m子立方體為Ut的增鄰接m子立方體。如果u的正確的鄰接點和v的正確的鄰接點在某個Mi序列首個和最后一個m子立方體中，則存在u到v經過序列Mi路徑。如果u的正確的鄰接點在序列Mi首個m子立方體中而v的正確的鄰接點不在序列Mi的最后一個m子立方體中且v的正確的鄰接點在序列Mj的最后一個m子立方體中而u的正確的鄰接點不在Mj首個m子立方體中，此時有序列Mi和序列Mj共同的第一個增鄰接的m子立方體Wij，則存在u到Mi，經Wij，再到Mj，到v的路徑。如果u、v在序列Mi中沒有正確的鄰接點，拋棄掉序列Mi（1in-m+1）。故u、v之間至少存在min（D[Us]，D[Ut]）條并行路徑。同樣，在任何一個m子立方體中一對正確結點之間尋找一條路徑最多需mk步，知從u到v最多（d（Us，Ut）+（k-2）+3）mk步。

（3）當d（Us，Ut）=1時，和（2）類似。

根據上面的證明過程可以寫出并行容錯路由算法。

3 結語

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

參考文獻

[1]王國軍，陳松喬，陳建二.具有大量錯誤結點的超立方體網絡中并行路由算法[J].計算機工程與科學，2001（05）：5-12.

[2]張涌逸.k元n立方體網絡的容錯路由[J].數字技術與應用，2012（09）：24.