Explicit construction for reliable reconfigurable array architectures

This paper describes some explicit constructions for reconfigurable array architectures. Given a working architecture (application graph), the authors add redundant hardware to increase reliability. The degree of reconfigurability, DR, 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, the authors say the graph is finitely reconfigurable, FR. They 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, they show that by using expanders they can construct highly reliable structures with the asymptotically optimal number of edges for one-dimensional and tree-like array architectures.