Efficient algorithms for reconfiguration in VLSI/WSI arrays

Vwani Roychowdhury, Jehoshua Bruck, T. KailathIEEE Trans. Computers 1990 · DOI

Abstract

The issue of developing efficient algorithms for reconfiguring processor arrays in the presence of faulty processors and fixed hardware resources is discussed. The models discussed consist of a set of identical processors embedded in a flexible interconnection structure that is configured in the form of a rectangular grid. An array grid model based on single-track switches is considered. An efficient polynomial time algorithm is proposed for determining feasible reconfigurations for an array with a given distribution of faulty processors. In the process, it is shown that the set of conditions in the reconfigurability theorem is not necessary. A polynomial time algorithm is developed for finding feasible reconfigurations in an augmented single-track model and in array grid models with multiple-track switches.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>
BibTeX
@article{roychowdhury1990efficient,
  author = {Vwani Roychowdhury and Jehoshua Bruck and T. Kailath},
  title = {{Efficient algorithms for reconfiguration in VLSI/WSI arrays}},
  journal = {IEEE Transactions on Computers},
  year = {1990},
  doi = {10.1109/12.54841},
}

Loading related content...

Figure