Title: Extended minimal routing in 2-D meshes with faulty blocks

Authors: Jie Wu, Zhen Jiang

Addresses: Department of Computer Science and Engineering, Florida Atlantic University, Boca Raton, FL 33431, USA. ' Department of Computer Science, Information Assurance Center, West Chester University, West Chester, PA 19383, USA

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.

Keywords: fault models; fault tolerance; high assurance; minimal routing; 2D meshes; two-dimensional meshes; faulty blocks; simulation; high performance computing; multicomputer systems; multiprocessors; high performance networking.

DOI: 10.1504/IJHPCN.2004.007573

International Journal of High Performance Computing and Networking, 2004 Vol.1 No.1/2/3, pp.140 - 152

Published online: 05 Aug 2005 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article