权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

A Theory of Fault-Tolerant Adaptive and Minimal Routing in Mesh-Connected Multicomputers

网状连接多机容错自适应最小路由理论

基本信息

批准号：
9900646
负责人：
Jie Wu
金额：
$ 13.41万
依托单位：
Florida Atlantic University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
1999
资助国家：
美国
起止时间：
1999-06-15 至 2003-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=9900646&HistoricalAwards=false
关键词：
Theory Fault Tolerant Adaptive Minimal

项目摘要

This project aims to develop a general theory of fault-tolerant adaptive and minimal routing in k-ary n-dimensional meshes. This theory can be extended to k-ary n-dimensional hypercubes, which are meshes with wraparounds. The theory is based on a new fault model and an information model. Unlike many existing fault models, the proposed fault model can handle boundary faulty nodes easily without disabling too many non-faulty nodes. As opposed to some existing fault-tolerant routing approaches where fault information is carried by the header of the routing message, the proposed approach is based on coded neighborhood information maintained at each processor. Each node in a mesh-connected multicomputer collects and distributes fault information concurrently but in a decentralized way. This collection and distribution process exhibits desirable properties of self-stabilizing, self-optimizing, and self-healing. Unlike many existing information models that require each node to have knowledge of the entire system, the coded fault information associated with each node represents limited-global information by exploring locality of disturbances in the system. Locality of fault information also ensures the scalability of the proposed approach. Insights gained in this project will shed new light on constructing new fault-tolerant, adaptive, minimal, and deadlock-free routing in mesh-connected multicomputers.

本计画的目的是发展一个通用的容错适应性理论，以及在k元n维网格上的最小路由。这个理论可以扩展到k元n维超立方体，这是一种带有环绕的网格。该理论基于一种新的故障模型和信息模型。与许多现有的故障模型，该故障模型可以很容易地处理边界故障节点，而不会禁用太多的非故障节点。相对于一些现有的容错路由方法，其中故障信息是由路由消息的头部进行，所提出的方法是基于在每个处理器保持编码的邻域信息。网状连接的多计算机中的每个节点并发地但以分散的方式收集和分发故障信息。这种收集和分配过程表现出自稳定、自优化和自修复的理想特性。与许多现有的信息模型，需要每个节点有整个系统的知识，与每个节点相关联的编码故障信息表示有限的全球信息，通过探索系统中的干扰的局部性。故障信息的局部性也保证了所提出的方法的可扩展性。在这个项目中获得的见解将揭示新的光构建新的容错，自适应，最小，无死锁的网状连接的多计算机路由。