Efficient algorithms for reconfiguration in VLSI/WSI arrays
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
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.Files
| Name | Size | Download all |
|---|---|---|
|
md5:9084589532255718e589446234412142
|
1.1 MB | Preview Download |
Additional details
- Eprint ID
- 5764
- Resolver ID
- CaltechAUTHORS:ROYieeetc90
- Created
-
2006-11-01Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field