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. https://resolver.caltech.edu/CaltechAUTHORS:ROYieeetc90
![]()
|
PDF
See Usage Policy. 1084Kb |
Use this Persistent URL to link to this item: https://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 | ||||||
---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||
ORCID: |
| ||||||
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 | ||||||
Issue or Number: | 4 | ||||||
Record Number: | CaltechAUTHORS:ROYieeetc90 | ||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:ROYieeetc90 | ||||||
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: | 22 Nov 2019 09:58 |
Repository Staff Only: item control page