Narasimhan, JagannathanNakajima, KazuoRim, Chong S.Dahbura, Anton T.In an approach recently proposed for the yield enhancement of programmable gate arrays (PGAs), an initial placement of a circuit is first obtained using a standard technique such as simulated annealing on a defect-free PGA. In the next step this placement is reconfigured so that the circuit is mapped onto the defect-free portion of a defective PGA chip with the same architecture. We first provide a graph theoretical formulation of the reconfiguration aspect of this approach. Based upon this formulation, we present three efficient algorithms. The first one optimally reconfigures the I/O buffers located on the periphery of a programmable array. The remaining algorithms are used as heuristics to reconfigure the gates located within a PGA and the processors within wafer scale integrated processor array. We evaluate the heuristic algorithms using the measure of routability and total wire length of the reconfigured placement of the circuit. Based on this evaluation, we establish good reconfiguration strategies.en-USalgorithmscombinatoricscomputational complexitygraph theoryVLSI architecturesreconfigurationCAD for VLSIprogrammable arraysSystems IntegrationTechnical Report