|
Published Articles >> Table of Contents >> Abstract
18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Papers
p. 12a
On Constructing the Minimum Orthogonal Convex Polygon in 2-D Faulty Meshes
Jie Wu, Florida Atlantic University
Zhen Jiang, West Chester University
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IPDPS.2004.1302915
Send link to a friend
| Abstract |
|
The rectangular faulty block model is the most commonly used fault model for designing fault-tolerant and deadlock-free routing algorithms in mesh-connected multicomputers. The convexity of a rectangle facilitates simple and efficient ways to route messages around fault regions using relatively few or no virtual channels to avoid deadlock. However, such a faulty block may include many non-faulty nodes which are disabled, i.e., they are not involved in the routing process. Therefore, it is important to de.ne a fault region that is convex and, at the same time, to include a minimum number of non-faulty nodes. In this paper, we propose an optimal solution that can quickly construct a set of minimum faulty polygons, called orthogonal convex polygons, from a given set of faulty blocks in a 2-D mesh (or 2-D torus). The formation of orthogonal convex polygons is implemented using either a centralized or distributed solution. Both solutions are based on the formation of faulty components each of which consists of adjacent faulty nodes only, followed by the addition of a minimum number of non-faulty nodes to make each component a convex polygon. This provides a solution to an open problem raised in [15]. Extensive simulation has been done to determine the number of non-faulty nodes included in the polygon, and the result obtained is compared with the best existing known result. Results show that the proposed approach can not only find a set of minimum faulty polygons but also does so quickly in terms of the number of rounds of information exchanges and updates between neighbors in the distributed solution.
|
 Additional Information
|
Citation:
Jie Wu, Zhen Jiang,
"On Constructing the Minimum Orthogonal Convex Polygon in 2-D Faulty Meshes,"
ipdps,
p. 12a,
18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Papers,
2004
|
|
