A Built-in Self-repair Circuit for Restructuring Mesh-Connected Processor Arrays by Direct Spare Replacement

We present a digital circuit for restructuring a mesh-connected processor array with faulty processing elements which are directly replaced by spare processing elements located at two orthogonal sides of the array. First, the spare assignment problem is formalized as a matching problem in graph theory. Using the result, we present an algorithm for restructuring the array in a convenient form for finding a matching by a digital circuit. Second, the digital circuit which exactly realizes the algorithm is given. The circuit can be embedded in a target processor array to restructure very quickly the array with faulty processing elements without the aid of a host computer. This implies that the proposed system is effective in not only enhancing the run-time reliability of a processor array but also such an environment that the repair by hand is difficult or a processor array is embedded within a VLSI chip where faulty processor elements cannot be monitored externally through the boundary pins of the chip, and so on. Third, the data about the array reliability considering not only faults in processors but also in that digital circuit are given, and then the effectiveness of our scheme is shown.