首页 | 本学科首页   官方微博 | 高级检索  
     

超立方体中基于极大安全通路矩阵的容错路由
引用本文:王雷,林亚平,陈治平,文学.超立方体中基于极大安全通路矩阵的容错路由[J].软件学报,2004,15(7):994-1004.
作者姓名:王雷  林亚平  陈治平  文学
作者单位:湖南大学,计算机与通信学院,湖南,长沙,410082
基金项目:Supported bythe Natural Science Foundation of Hu'nan Province of China under Grant No.01JJY1007(湖南省自然科学基金)
摘    要:n维超立方体结构的多处理机系统在并行与分布式处理中具有良好的性能,随着多处理机系统规模的增大,系统出现链路与节点故障的概率也随之增大,因此设计容错性更强的路由算法对n维超立方体结构的多处理机系统具有重要意义.针对超立方体结构的多处理机系统中存在链路故障的情况,提出了用于最优通路记录的极大安全通路矩阵(maximum safety path matrices,简称MSPMs)这一概念,给出了一种建立MSPMs及其容错路由算法.证明了MSPMs通过n-1轮邻节点之间的信息交换,能以矩阵的形式记录最多的最优通路

关 键 词:容错路由  最优通路  极大安全通路矩阵  超立方体  多处理机系统
文章编号:1000-9825/2004/15(07)0994
收稿时间:2003/3/13 0:00:00
修稿时间:9/5/2003 12:00:00 AM

Fault-Tolerant Routing for Hypercube Multi-Computers Based on Maximum Safety-Path Matrices
WANG Lei,LIN Ya-Ping,CHEN Zhi-Ping and WEN Xue.Fault-Tolerant Routing for Hypercube Multi-Computers Based on Maximum Safety-Path Matrices[J].Journal of Software,2004,15(7):994-1004.
Authors:WANG Lei  LIN Ya-Ping  CHEN Zhi-Ping and WEN Xue
Abstract:Hypercube multi-computers system is of good performance in parallel and distributed computation. With the increasing size of a multi-computers system, the fault possibility of computers and their links increases. It is very important to seek for better fault-tolerant routing strategies to realize an effective fault-tolerant routing. A novel fault-tolerant routing algorithm in hypercube multi-computers system is proposed, in which each node uses a maximum safety path matrices (MSPMs) to record the optimal paths to the other nodes. It proves that MSPMs can record most of the optimal paths by n-1 rounds of information exchanges between neighboring nodes. Furthermore, it proves that MSPMs is the final extension of the Optimal Path Matrices (OPMs) and the Extended Optimal Path Matrices (EOPMs) which also use the matrices to record the optimal paths in hypercube multi-computers system, so the problem of how to record the most of optimal paths in the n dimensional hypercube multi-computers system by using matrices is solved finally.
Keywords:fault-tolerant routing  optimal path  maximum safety path matrices  hypercube  multi-computers system
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《软件学报》浏览原始摘要信息
点击此处可从《软件学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号