网格中基于最小连接块的启发式容错路由算法

陈贵海; 杜 鹏; 王大进; 谢 立

您当前的位置：

首页 >

文章列表页 >

网格中基于最小连接块的启发式容错路由算法

论文 | 更新时间：2025-07-16

- 网格中基于最小连接块的启发式容错路由算法
- Heuristic Fault-Tolerant Routing in Mesh Using Minimal-Connected-Component Fault Blocks
- 电子学报 2004年32卷第2期页码：318-322
- 作者机构：
  
  1. 南京大学计算机软件新技术国家重点实验室,江苏,南京,210093
  2. 美国蒙特克莱州立大学计算机科学系,美国
  3. 南京大学计算机软件新技术国家重点实验室江苏南京,210093
  4. 美国蒙特克莱州立大学计算机科学系美国
- 作者简介：
- 基金信息：
  
  国家自然科学基金项目 (No.60073029);国家973项目 (No.2002CB312002);教育部高校青年教师奖资助计划
- DOI：
  中图分类号： TP393
- 纸质出版：2004
- 稿件说明：
移动端阅览
陈贵海, 杜鹏, 王大进, 等. 网格中基于最小连接块的启发式容错路由算法[J]. 电子学报, 2004,32(2):318-322.

CHEN Gui-hai, DU Peng, WANG Da-jin, et al. Heuristic Fault-Tolerant Routing in Mesh Using Minimal-Connected-Component Fault Blocks[J]. Acta Electronica Sinica, 2004, 32(2): 318-322.
陈贵海, 杜鹏, 王大进, 等. 网格中基于最小连接块的启发式容错路由算法[J]. 电子学报, 2004,32(2):318-322. DOI：

CHEN Gui-hai, DU Peng, WANG Da-jin, et al. Heuristic Fault-Tolerant Routing in Mesh Using Minimal-Connected-Component Fault Blocks[J]. Acta Electronica Sinica, 2004, 32(2): 318-322. DOI：

摘要

矩形无效块模型可以用来解决网格下的容错路由问题

最小连接块(MCC)模型是它的一个改良模型.本文在MCC基础上

建立MCC 重叠图

当发现不存在曼哈顿路径的时候

给出一套算法

来计算出一条避免无效块的尽可能短的路径.模拟试验表明

通过这种算法找到的路径

与最短路径相差很小.比起花费更多的时间去找寻最短路径

这种启发式容错算法无疑是更好的选择.

Abstract

Rectangular fault block model is designated to solve the problem of fault-tolerant route in mesh and was improved as Minimal-Connected-Component (MCC) model.Based on MCC

we construct an overlapping graph and give a set of algorithm according to the graph to work out the route as short as possible to avoid the appearance of fault block when Manhattan route does not exist.The simulated test shows that the route found by the algorithm mentioned above is nearly the shortest one.Hence compared to other methods costing much more time

this new heuristic fault-tolerant algorithm is of no doubt a better method in finding the shortest route.

关键词

Keywords

references

浏览量

836

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于流形学习的三维空间数据网格剖分方法

Torus网络中基于中心距离的完全自适应路由算法

同步McCulloch－Pitts型神经网络分析