交错立方体上限制容错单播算法的研究

王喜<sup>1,2</sup>,何福男<sup>1</sup>,张书奎<sup>2</sup>

doi:10.13718/j.cnki.xsxb.2018.09.009

西南师范大学学报(自然科学版)

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
	姓名不能为空！
邮箱
	邮箱不能为空！非法的邮箱地址。
手机号码
	电话不能为空！请输入有效手机号!
标题
	标题不能为空！
留言内容
	内容不能为空！
验证码
	验证码不能为空！验证码错误！

交错立方体上限制容错单播算法的研究

王喜1,2,何福男1,张书奎2. 交错立方体上限制容错单播算法的研究[J]. 西南师范大学学报(自然科学版), 2018, 43(9): 51-59. doi: 10.13718/j.cnki.xsxb.2018.09.009

引用本文:

王喜^1,2,何福男¹,张书奎². 交错立方体上限制容错单播算法的研究[J]. 西南师范大学学报(自然科学版), 2018, 43(9): 51-59. doi: 10.13718/j.cnki.xsxb.2018.09.009

WANG Xi1,2, HE Fu-nan1, ZHANG Shu-kui2. A Restricted Fault-Free Unicast Algorithm in Cross-Cubes[J]. Journal of Southwest China Normal University(Natural Science Edition), 2018, 43(9): 51-59. doi: 10.13718/j.cnki.xsxb.2018.09.009

Citation:

WANG Xi^1,2, HE Fu-nan¹, ZHANG Shu-kui². A Restricted Fault-Free Unicast Algorithm in Cross-Cubes[J]. Journal of Southwest China Normal University(Natural Science Edition), 2018, 43(9): 51-59. doi: 10.13718/j.cnki.xsxb.2018.09.009

交错立方体上限制容错单播算法的研究

王喜^1,2,何福男¹,张书奎²

1. 苏州工业职业技术学院软件与服务外包学院, 江苏苏州 215004;
2. 苏州大学计算机科学与技术学院, 江苏苏州 215006

A Restricted Fault-Free Unicast Algorithm in Cross-Cubes

WANG Xi^1,2, HE Fu-nan¹, ZHANG Shu-kui²

1. Suzhou Institute of Industrial Technology, Suzhou Jiangsu, 215004, China;
2. School of Computer Science and Technology, Soochow University, Suzhou Jiangsu, 215006, China

摘要: 在交错立方体中引入限制故障顶点集的概念，证明了当n ≥ 3时，交错立方体中基于限制故障顶点集的限制连通度为2n-2，这一结果几乎是交错立方体上传统连通度的两倍；然后提出了基于该情形下的时间复杂度为O（「log|F|」n3）的容错单播算法，并证明了在最坏情形下，该算法构造出的无故障路径的最长路径长度的上界为5m+n-1，其中m=「log|F|」；进一步利用上述算法进行仿真.
- 交错立方体 /
- 并行系统 /
- 连通度 /
- 限制连通度
Abstract: Supercomputers based on parallel systems have always been the hot research topic in industry and academia. The interconnection network, which is the basis of the parallel system, its properties determine the performance of the parallel system directly. The n-dimensional Cross-cube, denoted by Cn, is a variant of the hypercube, which has some features superior to the hypercube, for example:the diameter of the cross-cube is less than that of the hypercube. In this paper, we first introduce the concept of the set of restricted faulty nodes into cross-cubes. We further prove that under the condition that each node of the Cn has at least one fault-free neighbor its restricted connectivity is 2n-2, which is almost as twice as that of Cn under the condition of arbitrary faulty nodes. Moreover, we give an O(「log|F|」n3) fault-free unicast algorithm, and the maximal length of the path constructed by the algorithm is no more than 5m+n-1, where m=「log|F|」. Finally, we give the simulation result of the expected length of the fault-free path gotten by our algorithm.
- cross-cube /
- parallel systems /
- connectivity /
- restricted connectivity .

[1]	海蓝.神威·太湖之光继续"称霸"超级计算机排行榜, 美国无缘前三[EB/OL].(2017-06-19)[2018-03-13].http://www.techweb.com.cn/world/2017-06-19/2536748.shtml.
[2]	HARARY F.Conditional Connectivity[J].Networks,1983,13(3):347-357.
[3]	ESFAHANIAN A.Generalized Measures of Fault Tolerance with Application to n-Cube Networks[J].IEEE Transactions on Computers,1989,38(11):1586-1591.
[4]	OH A,CHOI H.Generalized Measures of Fault Tolerance in n-cube Networks[J].IEEE Transactions on Parallel and Distributed Systems,2002,4(6):702-703.
[5]	LIN R,ZHANG H.The Restricted Edge-Connectivity and Restricted Connectivity of a Ugmented k-ary n-Cubes[J].International Journal of Computer Mathematics,2015,93(8):1281-1298.
[6]	WANG X,FAN J,ZHOU J,et al.The Restricted h-Connectivity of the Data Center Network D Cell[J].Discrete Applied Mathematics,2016,203:144-157.
[7]	HSIEH S,HUANG H,LEE C.{2,3}-Restricted Connectivity of Locally Twisted Cubes[J].Theoretical Computer Science,2016,615:78-90.
[8]	LIN L,XU L,ZHOU S,et al.The Extra,Restricted Connectivity and Conditional Diagnosability of Split-Star Networks[J].IEEE Transactions on Parallel and Distributed Systems,2016,27(2):533-545.
[9]	HAQ E.Cross-Cube:A New Fault Tolerant Hypercube-based Network[C]//Processing of the 5th International Parallel Processing Symposium,New Work:IEEE Computer Society,1991:471-474.
[10]	闫少华,樊建席.Cross-cube在PMC诊断模型下的诊断性[J].计算机工程与应用,2011,47(17):83-86.

计量

文章访问数: 588
HTML全文浏览数: 418
PDF下载数: 26
施引文献: 0

交错立方体上限制容错单播算法的研究

王喜^1,2,何福男¹,张书奎²

1. 苏州工业职业技术学院软件与服务外包学院, 江苏苏州 215004;
2. 苏州大学计算机科学与技术学院, 江苏苏州 215006

收稿日期: 2017-09-30

关键词:

摘要: 在交错立方体中引入限制故障顶点集的概念，证明了当n ≥ 3时，交错立方体中基于限制故障顶点集的限制连通度为2n-2，这一结果几乎是交错立方体上传统连通度的两倍；然后提出了基于该情形下的时间复杂度为O（「log|F|」n3）的容错单播算法，并证明了在最坏情形下，该算法构造出的无故障路径的最长路径长度的上界为5m+n-1，其中m=「log|F|」；进一步利用上述算法进行仿真.

English Abstract

A Restricted Fault-Free Unicast Algorithm in Cross-Cubes

1. 苏州工业职业技术学院软件与服务外包学院, 江苏苏州 215004;
2. 苏州大学计算机科学与技术学院, 江苏苏州 215006

Received Date: 2017-09-30

Keywords:

Abstract: Supercomputers based on parallel systems have always been the hot research topic in industry and academia. The interconnection network, which is the basis of the parallel system, its properties determine the performance of the parallel system directly. The n-dimensional Cross-cube, denoted by Cn, is a variant of the hypercube, which has some features superior to the hypercube, for example:the diameter of the cross-cube is less than that of the hypercube. In this paper, we first introduce the concept of the set of restricted faulty nodes into cross-cubes. We further prove that under the condition that each node of the Cn has at least one fault-free neighbor its restricted connectivity is 2n-2, which is almost as twice as that of Cn under the condition of arbitrary faulty nodes. Moreover, we give an O(「log|F|」n3) fault-free unicast algorithm, and the maximal length of the path constructed by the algorithm is no more than 5m+n-1, where m=「log|F|」. Finally, we give the simulation result of the expected length of the fault-free path gotten by our algorithm.