Modelling and algorithms for spare allocation in reconfigurable VLSI

One approach to enhancing the yield or reliability of large area VLSI structures has been by means of spare interconnect, logic and computational units. Although extensive literature exists concerning design for inclusion of spares and restructuring mechanisms in memories and processor arrays, little research has been published on general models and algorithms for broad classes of spare allocation and reconfiguration problems. The main contribution of the paper is that a novel bipartite graph theoretic approach to spare allocation is presented for structures with dedicated spares and direct replacement reconfiguration. Spare allocation for classes of reconfigurable structures is shown to be equivalent to either a graph matching or a graph dominating set problem. The complexity of optimal spare allocation for each of the problem classes is described, and reconfiguration algorithms are provided. Several detailed examples are presented, and implementation of the algorithms is discussed.