Ehm. Sha et K. Steiglitz, RECONFIGURABILITY AND RELIABILITY OF SYSTOLIC WAVE-FRONT ARRAYS, I.E.E.E. transactions on computers, 42(7), 1993, pp. 854-862
In this paper, we study fault-tolerant redundant structures for mainta
ining reliable arrays. In particular, we assume the desired array (app
lication graph) is embedded in a certain class of regular, bounded-deg
ree graphs called dynamic graphs. We define the degree of reconfigurab
ility DR, and DR with distance Dr(d), of a redundant graph. When DR (r
espectively, DR(d)) is independent of the size of the application grap
h, we say the graph is finitely reconfigurable, FR (respectively, loca
lly reconfigurable, LR). We show that DR provides a natural lower boun
d on the time complexity of any distributed reconfiguration algorithm
and that there is no difference between being FR and LR on dynamic gra
phs. We then show that if we wish to maintain both local reconfigurabi
lity and a fixed level of reliability, a dynamic graph must be of dime
nsion at least one greater than the application graph. Thus, for examp
le, a one-dimensional systolic array cannot be embedded in a one-dimen
sional dynamic graph without sacrificing either reliability or localit
y of reconfiguration.