Perhaps the most common fault tolerant architecture configures a nominal t x a(.)t array using b(.)t dedicated spare rows and c t dedicated spare columns. Despite an extensive literature, two problems about row-column sparing appear unresolved: How to minimize the area of the layout. 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 a t x a.t array from a (1 + b) t x (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 greater than or equal to 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 Zarankiewicz: What is the least integer Z(t; a, b, c) such that every (1 + b) t x (a + c) t binary array with Z ones contains a t x a 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. By combining our results for layout with those for fault tolerance and redundancy, we can draw definite conclusions about the efficacy of arrays spared by rows and columns. 1) For constant redundancy, and in the presence of failures whose distribution is worst-case, i.i.d., or clustered, the fault tolerance of row-column sparing is theta (t(-1)); i.e., the number of tolerable faults is proportional to the square root of the size of the nominal array. 2) In the worst case, homogeneous sparing is asymptotically feasible, while dedicated sparing is not. 3) With a constant proportion of faulty elements, the worst-case or probabilistic area of homogeneous arrays is theta [exp(2t)], while, in the probabilistic case, that of dedicated sparing is Omega [t(.)exp(t)]. 4) Either of the architectures has worst-case wirelength theta (e t). 5) The best-case wirelength theta (1) of homogeneous sparing is less than that theta (t) of dedicated sparing. 6) At constant proportion of faulty elements, row-column sparing has wirelength Omega [exp(t)]. 7) At constant redundancy, the probabilistic wirelength theta [log(t)] of homogeneous sparing is less than that B(t) of dedicated sparing. From a practical perspective, suppose that you are designing a large-scale fault tolerant array. If you must use row-column sparing, then, contrary to industrial practices from 1980 to 1999, you are better off using homogeneous sparing than dedicated sparing. In general, however, the exponential redundancy imposed by row-column sparing becomes prohibitive. Instead of row-column sparing, you are better served by the e[log(t)l redundancy and theta[root log(t)] wirelength delivered by a straightforward implementation of local sparing. Alternatively, and at the expense of a bit more complexity in switches and configuration algorithm, you could use discretionary wiring to achieve the theoretically best possible redundancy theta (log[log(t)l), with wirelength theta[root log(t)].
