数学执本与率用
k元n立方并行容错路由
张涌逸
(太原师范学院计算机系山西晋中030619)
通信技术
摘要：本文讨论了k元n立方并行容错路由问题给出了k元n立方并行容错路由并行条数的一个下界，电给出每条路径步长的一个下界，证明过程同时电可转化为求并行路径的算法。
关键词k元n立方体m子立方体k元n立方的m子主方体连通图并行路由
中图分类号:TP302.8 1引言
文献标识码：A
文章编号:1007-9416(2014)08-0035-01
中，则存在u到v经过W路径。如果u的正确的邻接点在W中而v的正
针对并行处理器拓扑结构，人们已经提出了很多模型，k元n立方是其中一种并行模型。从1997年被提之后，因其具有很多优良特性，受到很多人的注意，对它进行了大量研究。k元n立方体已经应用在几个系统中，比如已被用于Ametek2020J-Machine，Mosaic. iwarp等系统中。随着数字技术的发展，处理器在并行系统中越来越多，出错可能性随之增大，容错成为一个重要的研究课题。并行容错既可提高系统的效率，也能提高系统的可靠性。因此讨论在k元n立
方体中的并行容错路由问题具有重要意义， 2k元n立方体中的并行容错路由
k元n立方体：结点集V=x,x,"x」x,为0到k-1之间的整数(i=1,2，",n)),两个结点有边相连当且仅当n个位中只有一位不同且不同的位之差的绝对值模为1。
m子立方体：在k元n立方中，前n-m+1元确定，其余的m个元可任意选取，构成的k元m立方体，称为k元n立方的m子立方体，记为 X,X,"-X.+**称x,XX+为x,X,X.+**的标签。
两个m子立方体Lee距离：设k元n立方的两个m子立方体为 X,X,""X-+**和y,Y""yn-n+**，此两m子立方体的Lee距离等于 ≥la],其中a,为,-→)模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子立方体为 X,X,XX+**,称xX,(x+1)X.m+**为x,XX*Xm+**i 位增邻接m子立方体。简称增邻接m子立方体。
定理：在k元n立方的m子立方体连通图H中，任给一对结点u. V，至少存在条从u到v的并行容错路径，每条路径长度不超过(d(U， U,)+k+1)m*步。其中1=min(D[U,],D[U,D,D[U,J表示除u所在的m子立方体U,外其余的u的邻接点所在的U,的位增邻接m子立方体的个数，D[U表示除v所在的m子立方体U,外其余的v的邻接点所在的U 的位增邻接m子立方体的个数，d(U_，U)是指U和U之间Lee距离
证明：
(1)当d(UU,)=0时，也即u,v在同一个m子立方体中U设u,v 所在的m子立方体为x,X,""X.-m+**，取Us邻接的m子立方体W,=(x,+1)x,*X.m+)**, W,=X,(x,+1).X.#+)**, **, W.m+)=X,X,*.(x,-+,+1)**。如果u的正确的邻接点和v的正确的邻接点在某个W
收稿日期：20140716
确的邻接点不在W中且v的正确的邻接点在某个W,中而u的正确的邻接点不在W.中，此时有W.和W共同增邻接的W，则存在u到W.，经 W，再到W，到v的路径。如果u,v在W中没有正确的邻接点，抛弃掉 W(1≤i≤n-m+1)。此时至少有1条从u到v的并行容错路径。又在任何一个m子立方体中一对正确结点之间寻找一条路径最多需m*步，故从u到v最多3m步。
(2)当d(U,U,)≥1时,设x,(x,+1)xm+**U,为=x,XXm+**, 取U,邻接的m子立方体W,x,+1)xX**,W,x,(x)X-**，，W+=Xx,(x.++1)*+分别为并行序列M,M,，"，M.+的首个m子立方体。W(1≤i≤Ⅱ-m+1)到U,的Lee距离最多增1,对每个 M,，选好首个立方体后，从x,x""x.-m的第i+1位开始到第n-m+1 位，再从第1位在循环回第位，依次找出和U,标签不同的位，设这些位的值为A,A,."",A(d-1).A,,在从A,,A,"",A(d-1)的第—位A, 起，增1或减1，得到新的m子立方体x,X,"(x+1)X.-m+**或 x,X(x-1)X.-+**使到U,的Lee距离减1,此过程在第A,位继续，直到到Ut的Lee距离不能减少，转到A。对A,上述过程一样进行，直到A(d-1)。对Ad,每次减1,直到和U,邻接。显然，各个序列没有共同的m子立方体，且最后一个m子立方体为U,的增邻接m子立方体。如果u的正确的邻接点和v的正确的邻接点在某个M,序列首个和最后一个m子立方体中，则存在u到v经过序列M路径。如果u的正确的邻接点在序列M首个m子立方体中面v的正确的邻接点不在序列M 的最后一个m子立方体中且v的正确的邻接点在序列M的最后一个m 子立方体中面u的正确的邻接点不在M首个m子立方体中，此时有序列M和序列M共同的第一个增邻接的m子立方体W.，则存在u到M，经W，再到M，到v的路径，如果u,V在序列Mi中没有正确的邻接点，抛弃掉序列M,(1≤i≤n-m+1)。故u,v之间至少存在min(D[U,],D[U, 条并行路径。同样，在任何一个子立方体中一对正确结点之间寻找
-条路径最多需m*步，知从u到v最多(d(U，U,)+(k-2)+3)m*步。(3)当d(U，U,)=1时，和(2)类似。
根据上面的证明过程可以写出并行容错路由算法。 3结语
以上我们讨论了k元n立方体的并行容错路由，得到并行路径条数至少为min(D[UJ],D[U]),步长不超过(d(U,,U,)+k+1)m*步,容错不止适合结点错误，还适合链路错误，且结点容错能力超过一半以上。但所得结论和增邻接m子立方体有关，事实上，还应该和减邻接
m子立方体有关，也即结果也许还有可改进的地方。参考文献
[1]王国军，陈松乔,陈建二.具有大量错误结点的超立方体网络中并行路由算法[J].计算机工程与料学,2001(05):5-12.
[2]张涌速.k元n立方体网络的容错路由[J]数字技术与应用,2012(09):24,
作者简介：张涌逸(1968一)，男，山西河曲人,硕士，制教投，主要研究方向为网络容错、网络路由和分布式测试等。
35