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. doi:10.1109/12.54841. https://resolver.caltech.edu/CaltechAUTHORS:ROYieeetc90
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
PDF
See Usage Policy. 1MB |
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 | ||||||
| DOI: | 10.1109/12.54841 | ||||||
| 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: | 08 Nov 2021 20:28 |
Repository Staff Only: item control page
