What designers of bus and network architectures should know about hypercubes

We quantify why, as designers, we should prefer clique-based hypercubes (K-cubes) over traditional hypercubes based on cycles (C-cubes). Reaping fresh analytic results, we find that K-cubes minimize the wirecount and, simultaneously, the latency of hypercube architectures that tolerate failure of an...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 2003-04, Vol.52 (4), p.525-544
Main Authors: LaForge, L.E., Korver, K.F., Sami Fadali, M.
Format: Article
Language:English
Subjects:
Asymptotic properties
Buses (vehicles)
Computer architecture
Costs
Deep space
Delay
Failure
Failure analysis
Fault tolerance
Graphs
Hamming distance
Hypercubes
Joining processes
Kirk field collapse effect
Optimization
Probes
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We quantify why, as designers, we should prefer clique-based hypercubes (K-cubes) over traditional hypercubes based on cycles (C-cubes). Reaping fresh analytic results, we find that K-cubes minimize the wirecount and, simultaneously, the latency of hypercube architectures that tolerate failure of any f nodes. Refining the graph model of Hayes (1976), we pose the feasibility of configuration as a problem in multivariate optimization: What (f+1)-connected n-vertex graphs with fewest edges [n(f+1)/2] minimize the maximum a) radius or b) diameter of subgraphs (i.e., quorums) induced by deleting up to f vertices? We solve (1) for f that is superlogarithmic but sublinear in n and, in the process, prove: 1) the fault tolerance of K-cubes is proportionally greater than that of C-cubes; 2) quorums formed from K-cubes have a diameter that is asymptotically convergent to the Moore Bound on radius; 3) under any conditions of scaling, by contrast, C-cubes diverge from the Moore Bound. Thus, K-cubes are optimal, while C-cubes are suboptimal. Our exposition furthermore: 4) counterexamples, corrects, and generalizes a mistaken claim by Armstrong and Gray (1981) concerning binary cubes; 5) proves that K-cubes and certain of their quorums are the only graphs which can be labeled such that the edge distance between any two vertices equals the Hamming distance between their labels; and 6) extends our results to K-cube-connected cycles and edges. We illustrate and motivate our work with applications to the synthesis of multicomputer architectures for deep space missions.
ISSN:0018-9340
1557-9956
DOI:10.1109/TC.2003.1190592