A Caltech Library Service

Efficient algorithms for reconfiguration in VLSI/WSI arrays

Roychowdhury, Vwani P. and Bruck, Jehoshua and Kailath, Thomas (1990) Efficient algorithms for reconfiguration in VLSI/WSI arrays. IEEE Transactions on Computers, 39 (4). pp. 480-489. ISSN 0018-9340.

See Usage Policy.


Use this Persistent URL to link to this item:


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

Item Type:Article
Additional Information:© Copyright 1990 IEEE. Reprinted with permission. Manuscript received June 30, 1989; revised November 27, 1989. V. P. Roychowdhury and T. Kailath are supported in part by the Department of the Navy, Office of Naval Research under Contract N00014-86-K-0726, the SDIO/IST, managed by the Army Research Office under Contract DAAL03-87-K-0033, and the U.S. Army Research Office under Contract DAAL03-86-K-0045.
Subject Keywords:Efficient polynomial time algorithm, fault-tolerant architecture, reconfigurable processor arrays, single-track and multiple-track models, wafer scale integration (WSI) technology
Record Number:CaltechAUTHORS:ROYieeetc90
Persistent URL:
Alternative URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:5764
Deposited By: Archive Administrator
Deposited On:01 Nov 2006
Last Modified:26 Dec 2012 09:15

Repository Staff Only: item control page