Reliable Reconfigurable Structures for Array Architectures

Abstract:

This paper describes some explicit constructions for reconfigurable
array architectures. Given a working architecture (application graph),
we add redundant hardware to increase reliability. The degree of
reconfigurability, D R, of a redundant graph is a measure of the cost
of reconfiguration after failures. When DR is independent of the
size of the application graph, we say the graph is finitely
reconfigurable, F R. We present a class of simple layered graphs with
a logarithmic number of redundant edges, which can maintain both finite
reconfigurability and a fixed level of reliability for a wide class of
application graphs. By sacrificing finite reconfigurability, we show
that by using expanders we can construct highly reliable structures
with the asymptotically optimal number of edges for one-dimensional and
tree-like array architectures.