WILDCARD DIMENSIONS, CODING THEORY AND FAULT-TOLERANT MESHES AND HYPERCUBES

Hypercubes, meshes and tori are well known interconnection networks fo r parallel computers. The sets of edges in those graphs can be partiti oned to dimensions. It is wen known that the hypercube can be extended by adding a wildcard dimension resulting in a folded hypercube that h as better fault-tolerant and communication capabilities. First we prov e 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 to ri. Using techniques from error correcting codes we construct d-dimens ional meshes and tori with wildcard dimensions. Finally, we show how t hese constructions can be used to tolerate edge and node faults in mes h and torus networks.