Asymptotically tight bounds for computing with faulty arrays of processors
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 285-296 vol.1
- https://doi.org/10.1109/fscs.1990.89547
Abstract
The computational power of 2-D and 3-D processor arrays that contain a potentially large number of faults is analyzed. Both a random and a worst-case fault model are considered, and it is proved that in either scenario low-dimensional arrays are surprisingly fault tolerant. It is also shown how to route, sort, and perform systolic algorithms for problems such as matrix multiplication in optimal time on faulty arrays. In many cases, the running time is the same as if there were no faults in the array (up to constant factors). On the negative side, it is shown that any constant congestion embedding of an n*n fault-free array on an n*n array with Theta (n/sup 2/) random faults (or Theta (log n) worst-case faults) requires dilation Theta (log n). For 3-D arrays, knot theory is used to prove that the required dilation is Omega ( square root log n).<>Keywords
This publication has 7 references indexed in Scilit:
- A unified approach to off-line permutation routing on parallel networksPublished by Association for Computing Machinery (ACM) ,1990
- Robust algorithms for packet routing in a meshPublished by Association for Computing Machinery (ACM) ,1989
- Expanders might be practical: fast algorithms for routing around faults on multibutterfliesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Reconfiguring a hypercube in the presence of faultsPublished by Association for Computing Machinery (ACM) ,1987
- Wafer-Scale Integration of Systolic ArraysIEEE Transactions on Computers, 1985
- Tight Bounds on the Complexity of Parallel SortingIEEE Transactions on Computers, 1985
- Configuration of VLSI Arrays in the Presence of DefectsJournal of the ACM, 1984