An efficient algorithm for constructing systolic arrays from VLSI/WSI containing faulty elements

An efficient polynomial-order algorithm for the compensation path finding problem which has been previously reduced to an NP-complete problem is given. The algorithm uses four queues of faulty processing elements (PEs) obtained by sorting faulty PEs with respect to their locations in the array, and successively finds compensation paths for the faulty PEs at the exits of the queues. A branching scheme is used to search for compensation paths depending on the relative positions of the faulty PEs at the exits of the queues. The time complexity of the algorithm is O(n³) in the worst case, where n is the number of faulty PEs. The space complexity of the algorithm is O(n)