Reconfiguration Strategies in VLSI (Very Large Scale Integration) Arrays and Trees

摘要

Reconfiguration strategies in VLSI processor arrays have been advocated in the recent literature as a means of achieving higher production yield and higher reliability. In the thesis, the authors present new reconfiguration techniques for rectangular arrays and trees that are generalizations of the Diogenes approach. They present two schemes for reconfiguring rectangular arrays and a scheme for reconfiguring trees. For the analysis of the different schemes presented in the paper, they assume that a processor has a square layout. The first scheme for reconfiguring an N x N rectangular array uses r additional rows and c additional columns. The scheme guarantees reconfiguration as long as there are at most c columns that have more than r faulty processors. The second scheme uses S spare processors. Here k is a parameter of the design. It guarantees reconfiguration as long as there are enough spare processors, and in any window of N processors in a particular linearization there are at most k faulty processors. The scheme for reconfiguring a tree can tolerate as many faults as the number of spare processors S. Generalizations of the above scheme for trees, that improve on the number of switches an edge has to traverse, are also presented.