RECONFIGURABILITY AND RELIABILITY OF SYSTOLIC WAVE-FRONT ARRAYS

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.