A graph theoretical approach for the yield enhancement of reconfigurable VLSI/WSI arrays

In this paper, we consider the yield enhancement of programmable structures by logical restructuring of the circuit placement. In this approach, an initial placement of a circuit on the array is first obtained by simulated annealing on a defect-free array. To implement the circuit on a defective array, the initial placement is reconfigured so that only the defect-free portion of the array is used. Customizing a given initial placement for each defective chip by logical restructuring, if done very fast, would be a cost effective method for yield enhancement. We describe a formulation of the circuit reconfiguration problem in terms of graphs and pebbles, wherein each processing element (PE) of the array is represented by a vertex which is classified as either defective or nondefective, depending upon whether the PE that it represents is defective or nondefective. Vertices representing PEs that are physically adjacent are connected by an edge, whose length is a measure of the proximity of the PEs. The logic elements of a circuit are represented by weighted pebbles. The initial placement of the circuit on the array corresponds to an initial placement of the pebbles on the vertices of the graph, with at most one pebble per vertex. The problem is to successively shift these pebbles along paths in the graph, such that after reconfiguration no pebble is located on a defective vertex, and an associated cost function is minimized. We describe four cost measures using weighted displacement and weighted shift of the pebbles. After presenting exact algorithms for some special cases of the problem, we prove the NP-completeness of the general cases of the corresponding decision problems.