What designers of microelectronic systems should know about arrays spared by rows and columns

Perhaps the most common fault tolerant architecture configures a nominal t×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 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×a·t array from a (1+b)·t×(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⩾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)·t×(a+c)·t binary array with Z ones contains a t×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