CaltechAUTHORS
  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. http://resolver.caltech.edu/CaltechAUTHORS:ROYieeetc90

[img]
Preview
PDF
See Usage Policy.

1084Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:ROYieeetc90

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


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:http://resolver.caltech.edu/CaltechAUTHORS:ROYieeetc90
Alternative URL:http://dx.doi.org/10.1109/12.54841
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:5764
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:01 Nov 2006
Last Modified:26 Dec 2012 09:15

Repository Staff Only: item control page