Name
Abstract | ||
|---|---|---|
The authors study fault-tolerant redundant structures for maintaining reliable arrays. In particular, they assume that the desired array (application graph) is embedded in a certain class of regular, bounded-degree graphs called dynamic graphs. The degree of reconfigurability (DR) and DR with distance (DR/sup d/) of a redundant graph are defined. When DR and DR/sup d/ are independent of the size of the application graph, the graph is finitely reconfigurable (FR) and locally reconfigurable (LR), respectively. It is shown that DR provides a natural lower bound on the time complexity of any distributed reconfiguration algorithm and that there is no difference between being FR and LR on dynamic graphs. It is also shown that if both local reconfigurability and a fixed level of reliability are to be maintained, a dynamic graph must be of a dimension at least one greater than the application graph. Thus, for example, a one-dimensional systolic array cannot be embedded in a one-dimensional dynamic graph without sacrificing either reliability or locality of reconfiguration. |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1109/12.237725 | Computers, IEEE Transactions |
Keywords | Field | DocType |
dynamic graphs,systolic/wavefront arrays,distributed reconfiguration algorithm,time complexity,reliable arrays,wavefront arrays,fault tolerant computing,reconfigurable architectures,bounded-degree graphs,locally reconfigurable,array reliability,redundant graph,computational complexity,natural lower bound,systolic arrays,application graph,reliability,graph theory,lower bound,reconfigurability degree,fault-tolerant redundant structures,reconfigurability,finitely reconfigurable,switches,indexing terms,throughput,computer architecture,computer science,fault tolerant,systolic array,fault tolerance | Locality,Reconfigurability,Upper and lower bounds,Computer science,Parallel computing,Systolic array,Real-time computing,Fault tolerance,Graph bandwidth,Time complexity,Control reconfiguration | Journal |
Volume | Issue | ISSN |
42 | 7 | 0018-9340 |
ISBN | Citations | PageRank |
0-7803-0003-3 | 1 | 0.38 |
References | Authors | |
9 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Edwin H.-M. Sha | 1 | 1318 | 97.35 |
| Kenneth Steiglitz | 2 | 1128 | 660.13 |