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.

Perhaps the most common fault tolerant architecture configures a nominal t/spl times/a/spl middot/t array using b/spl middot/t dedicated spare rows and c/spl middot/t dedicated spare columns. Despite an extensive literature, two problems about row-column sparing appear unresolved: how to minimize the area of the layout and how to minimize the maximum wirelength. This paper answers these questions, consolidates results, and describes the implications for the designer. An outstanding conjecture is counterexampled by using a graph-theoretic procedure to lay out arrays spared by dedicated rows and columns, in area proportional to the number of array elements. However, dedicated sparing is somewhat more costly than homogeneous extraction of at/spl times/a/spl middot/t array from a (1+b)/spl middot/t/spl times/(a+c). T array. Complementing our results for layout, we quantify the worst-case and probabilistic fault tolerance for both dedicated and homogeneous sparing, as a function of the nominal aspect ratio a/spl ges/1, the redundancy parameters b, c, and the scale parameter t. In the process, we contribute to the solution to an open question in extremal graph theory, the problem of Zarnnkiewicz: what is the least integer Z(t; a, b, c) such that every (1+b)/spl middot/t/spl times/(a+c)/spl middot/t binary array with Z ones contains a t/spl times/a/spl middot/t subarray having no zeros? Whereas the mathematical literature traditionally focuses on subarrays possessing a constant number of rows or columns, we are interested in scalable constructions for microelectronics. Reflecting this priority, we derive exact formulae for Z(t; a, b, c) when the extracted subarray, grows in proportion to embedding array.

The bulk of results for the performance of configuration architectures treat the case of failed processors, but neglect switches that are stuck open or closed. By contrast, the present work characterizes this multivariate problem in the presence of either iid or clustered faults. Suppose that the designer wishes to assure, with high probability, a fault free s/spl times/t array. If local sparing is used then, as we prove, the area of the redundant array is 1) /spl theta/(st log st) in the presence of faulty elements or faulty elements and switches stuck open; 2) /spl theta/(st log/sup 2/ st) in the presence of faulty elements and switches stuck closed; 3) /spl theta/([st]/sup 2/ log st) in the presence of faulty elements and switches that may be either stuck open or stuck closed. We also furnish bounds on maximum wirelength and an optimal configuration algorithm.

A simple diagnosis algorithm is presented for constant degree systems such as rectangular grids connected as tori. The algorithm determines the status of a unit according to the size of its faction, a cluster of units that call each other fault-free but outsiders faulty. Almost all units are correctly identified with this algorithm under a binomial failure distribution even when the probability of failure is rather high. The complexity of the algorithm is O(n), where n is the number of units in a constant degree system. The application of the algorithm to production testing of VLSI chips is also considered. With a test board that houses a large number of chips to be tested, all the chips can be tested in parallel in a way that they test each other and the test outcomes, not necessarily correct, are reported to a host system for analysis. The actual status of each chip is determined by using this new diagnosis algorithm. The above chip screening process can be repeated for higher accuracy. It is shown that no more than two steps are needed in most real situations. Compared with testing by test equipment that usually tests only one chip at a time, the saving of test time and the test equipment cost could be significant with our approach.>

We demonstrate a structure for mutual test among N processing elements. We indicate how this structure might be used to identify the good dice on a semiconductor wafer at a cost below that of current techniques. Under either a digraph or a comparison model, our proposed test structure has the following properties: 1) It is nearly regular. 2) It can be laid out in area O(/spl ominus/(n). 3) In time /spl ominus/(N) and with high probability, all but at most an arbitrarily small fraction of the good elements can be identified. 4) The number of tests or comparisons per element is bounded by a constant. We approximate this constant analytically. The result is a substantial savings over the /spl ominus/(log N) tests per element in regular structures whose purpose is to identify, with high probability, every good element. In contrast with the majority of previous work, our results apply even when less than half of the elements are good.>