Rolf Clauberg
IBM J. Res. Dev
This paper presents constructions for fault-tolerant, two-dimensional mesh architectures. The constructions are designed to tolerate k faults while maintaining a healthy n by n mesh as a subgraph. They utilize several novel techniques for obtaining trade-offs between the number of spare nodes and the degree of the fault-tolerant network. We consider both worst-case and random fault distributions. In terms of worst-case faults, we give a construction that has constant degree and O(k3) spare nodes. This is the first construction known in which the degree is constant and the number of spare nodes is independent of n. In terms of random faults, we present several new degree-6 and degree-8 constructions and show (both analytically and through simulations) that these constructions can tolerate large numbers of randomly placed faults.
Rolf Clauberg
IBM J. Res. Dev
Lerong Cheng, Jinjun Xiong, et al.
ASP-DAC 2008
Elliot Linzer, M. Vetterli
Computing
Beomseok Nam, Henrique Andrade, et al.
ACM/IEEE SC 2006