An array grid model based on single-track switches is proposed. A reconfigurability theorem is developed to provide the theoretical footing for novel reconfiguration algorithms for the fabrication-time and run-time processing. For fabrication-time yield enhancement, the problem of finding a feasible reconfiguration using global control can be reformulated as a maximum independent set problem. An existing algorithm in graph theory is adopted to solve this problem. The simulations conducted indicate that the algorithm is computationally very efficient; therefore, it may also be applicable to certain run-time fault tolerance. In real-time fault tolerance, the propagation time of data/control signals between the host computer incurred in the global control is often prohibitively long; therefore, only distributed processing is feasible. Based on the same reconfigurability theorem, a distributive reconfiguration algorithm is developed for (asynchronous) array processors.>

The authors present a systematic methodology for mapping commonly used digital signal processing algorithms to VLSI array processors, such as the systolic array and the wavefront array. A concise description of the proposed methodology is presented to show the flexibility and usefulness of the method. The advantages of this methodology include: (1) algorithms in different expressions, such as sequential programs, signal flow graphs, or dataflow graphs can be mapped to array processors easily; (2) the mapping procedure is systematic and optimal designs can be efficiently searched; and (3) the methodology can be automated as software tools to assist the array processor designers.>