Extended minimal routing in 2-D meshes with faulty blocks
by Jie Wu, Zhen Jiang
International Journal of High Performance Computing and Networking (IJHPCN), Vol. 1, No. 1/2/3, 2004

Abstract: In this paper, several enhanced sufficient conditions are given for minimal routing in 2-dimensional (2-D) meshes with faulty nodes contained in a set of disjoint faulty blocks. It is based on an early work of Wu's minimal routing in 2-D meshes with faulty blocks. Unlike many traditional models that assume all the nodes know global fault distribution, our approach is based on the notion of limited global fault information. First, a fault model called faulty block is reviewed in which all faulty nodes in the system are contained in a set of disjoint faulty blocks. Fault information is coded in a 4-tuple called extended safety level associated with each node of a 2-D mesh to determine the feasibility of minimal routing. Specifically, we study the existence of minimal route at a given source node based on the associated extended safety level, limited distribution of faulty block information, and minimal routing. An analytical model for the number of rows and columns that receive faulty block information is also given. Extensions to Wang's minimal-connected-components (MCCs) are also considered. MCCs are rectilinear-monotone polygonal shaped fault blocks and are refinement of faulty blocks. Our simulation results show substantial improvement in terms of higher percentage of minimal routing in 2-D meshes under both fault models.

Online publication date: Fri, 05-Aug-2005

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of High Performance Computing and Networking (IJHPCN):
Login with your Inderscience username and password:

Username:        Password:          Forgotten your password?

Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com