Fault detection and location in reconfigurable VLSI arrays

A systematic and efficient fault diagnosis methodology in reconfigurable VLSI array architectures is presented. This methodology utilizes the output data path independence of subsets of processing elements (PEs) based on the topology of the arrays. The 'divide and conquer' technique is applied to reduce testing complexity and enhances the controllability and observability of arrays. An array under test is divided into several nonoverlapping parallel partitions. Those PEs in the same partition can be diagnosed simultaneously. The problem to find parallel partitions is shown equivalent to a generalized Eight Queens problem. Three types of easily testable PEs are designed to illustrate this approach. The main contribution of this paper is a novel PE fault diagnosis approach which speeds up the testing by at least O(|V|^1/2) for the arrays considered, where |V| is the number of PEs. This approach requires little or no hardware overhead depending on the types of architectures and can diagnose multiple PE faults.