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

点击翻译按钮获取中文摘要

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.