CaltechAUTHORS
  A Caltech Library Service

Wildcard dimensions, coding theory and fault-tolerant meshes and hypercubes

Bruck, Jehoshua and Cypher, Robert and Ho, Ching-Tien (1995) Wildcard dimensions, coding theory and fault-tolerant meshes and hypercubes. IEEE Transactions on Computers, 44 (1). pp. 150-155. ISSN 0018-9340. http://resolver.caltech.edu/CaltechAUTHORS:BRUieeetc95

[img]
Preview
PDF - Published Version
See Usage Policy.

767Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:BRUieeetc95

Abstract

Hypercubes, meshes and tori are well known interconnection networks for parallel computers. The sets of edges in those graphs can be partitioned to dimensions. It is well known that the hypercube can be extended by adding a wildcard dimension resulting in a folded hypercube that has better fault-tolerant and communication capabilities. First we prove that the folded hypercube is optimal in the sense that only a single wildcard dimension can be added to the hypercube. We then investigate the idea of adding wildcard dimensions to d-dimensional meshes and tori. Using techniques from error correcting codes we construct d-dimensional meshes and tori with wildcard dimensions. Finally, we show how these constructions can be used to tolerate edge and node faults in mesh and torus networks.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/12.367998DOIUNSPECIFIED
http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=8421&arnumber=367998PublisherUNSPECIFIED
Additional Information:© Copyright 1995 IEEE. Reprinted with permission. Manuscript received May 10, 1993.
Subject Keywords:error correction codes; fault tolerant computing; hypercube networks; reliability; coding theory; communication capabilities; edge faults; error correcting codes; fault-tolerant meshes; folded hypercube; interconnection networks; node faults; parallel computers; wildcard dimensions
Record Number:CaltechAUTHORS:BRUieeetc95
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:BRUieeetc95
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:12333
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:12 Nov 2008 23:03
Last Modified:26 Dec 2012 10:30

Repository Staff Only: item control page