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.