Reconfigurability and Reliability of Systolic/Wavefront Arrays.
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.
Introduction
Highly parallel pipelined structures such as systolic or wavefront arrays are attractive
architectures for achieving high throughput [9]. Examples of important potential applications
include digital signal processing [11, 2], large-scale scientific computation on
arrays for solving partial differential equations [12], and simulating lattice-gas automata
[14]. As such array processors become larger, the reliability of the processing elements
(PE's) becomes a critical issue, and it becomes necessary to use fault-tolerant techniques
- both at the time of fabrication [15] and at runtime. Defective PE's must be located,
and the architecture reconfigured to substitute good PE's for bad.
In certain runtime applications like avionics and space flight, fault tolerant techniques
must be able to restore proper operation after failures as fast as possible. For this purpose,
distributed reconfiguration algorithms executed in parallel by the PE's themselves have
been studied in [13, 17]. In [5] a fault-tolerant multiprocessor is developed for space
applications that also employs a distributed reconfiguration approach for the topology
of a chordal skip-link ring. In this paper, we study the complexity of algorithms for
reconfiguring arrays after failures, and focus especially on runtime fault tolerance.
In most literature on fault tolerance, faults are confined to processing elements only
and it is assumed that all switches and connections [1, 10, 3, 18] are perfect. This is
not valid when the number of switches and connections becomes large. In this paper we
will use a graph model that takes into account failures of switches and interconnection
wires as well as PE's. PE's and switches will be represented by nodes of the graph in the
obvious way, and a connection between two elements in the computational structure will
be represented by a node inserted in the edge between the appropriate two nodes in the
graph model. Each node of the graph will have associated with it a probability of failure
".
To achieve fault tolerance, we add redundancy to the system. After a failure the original
working architecture is reconfigured by replacing some nodes that were being used
by redundant nodes. A good fault tolerant structure is one where the number of nodes
that need to be changed after failure is as small as possible. In this paper, we define a
measure of this adaptability, the degree of reconfigurability (DR), and analyze this measure
on a class of very regular graphs called dynamic graphs [16, 6, 7, 8]. We also analyze
a stricter measure, called the degree of reconfigurability with distance, DR d , which takes
into account the total distance between original nodes and replacing nodes. Our goal is
to investigate the relation between the structure of dynamic graphs, their reliability, and
their fault-tolerant capability as measured by their degree of reconfigurability.
The case when DR is independent of the size of the system is especially important
because it represents the situation when the amount of change necessary to repair the
system depends only on the number of failed nodes, but not on the size of the system. In
this case, we say the graph is finitely reconfigurable. Similarly, if DR d , the total distance
cost of changes is independent of the size of system, we say that it is locally reconfigurable.
Actually, in section 3, we show if the redundant system is a dynamic graph, it is locally
reconfigurable if and only if it is finitely reconfigurable. Given a desired working structure,
we will discuss what kinds of redundant structures are possible or impossible to maintain
at a fixed level of reliability, while at the same time being locally reconfigurable. In
particular, our main result is that if we wish to maintain both local reconfigurability, and
a fixed level of reliability, the dynamic graph must be of dimension at least one greater
than the application graph, which are shown in section 4 and section 5.
Definitions and Mathematical Framework
labelsecdef1 A VLSI/WSI array architecture can be represented as a graph E).
Each node of the graph G can be regarded as a processor, and an edge of G is a connection
between two processors. We assume that the nodes failed independently, each with
probability ffl. As mentioned above, a node in our graph model can represent a PE, a
switch, or interprocessor connection.
Real working architectures are considered to be a family of graphs, G a , called application
a ) denotes the ith application graph of G a . For example, G a
can be a family of linear arrays indexed by number of nodes, so G n
a is an n-node linear
array. We always assume each G i
a is connected and that for each value of n, there exists
a unique i. Since we need to add redundant nodes or edges to increase reliability, the
embedding structures, G r , called redundant graph, are also represented as a family of
r ) denotes the ith redundant graph of G r . Each pair of nodes in V i
r
is associated with a value, distance, defined by a function D
r \Theta V i
the set of natural numbers; D i (a; a) = 0. This distance can be regarded as the physical
distance between two nodes, or some cost, such as the communication cost.
Given two graphs G define the embedding function
be the image of V 1 .
Given an embedding function let the mapping set S(-) be the set of pairs,
represents the difference between two embedding
functions - and - 0 .
Given G a and G r , the following function will determine which graph in G r will be the
redundant graph of the ith application graph.
Definition 2.1 An Embedding Strategy for G a and G r is a function ES : G a ! G r , i.e.,
a
r , G j
r is the redundant graph for G i
a .
If ES(G i
a
r , and k nodes of G j
r have failed, the failed nodes and all the edges
incident to them will be removed and G j
r becomes a new subgraph -
r ). The
procedure of finding a new embedding function - i
r is called reconfiguration.
Definition 2.2 Given G a , G r and ES, the maximum fault-tolerance of G i
a , MFT (G i
a
is the maximum number of nodes that can be allowed to fail arbitrarily in ES(G i
a ) such
that ES(G i
a ) can still find a subgraph isomorphic to G i
a . In addition, FT (G i
a ) is given
which is some fixed number - MFT (G i
a ) for each i.
Definition 2.3 Given G a , G r , ES and Fault Tolerance FT (G i
a
a ) for each i,
the quadruple (G a called an Embedding Architecture, EA.
array
linear array

Figure

1: Example of G a and G r :
For example in figure 1, G a is a family of linear arrays, and G r is a family of triple-
modular-redundancy (TMR) arrays obtained by triplicating each node of a linear array
to be three nodes, called a module. Let G n
a ) be the n-module array, and let its
corresponding FT (G n
a ) be 2 for all n.
For simplicity, if the context is clear, we will always assume the ith application graph
maps to the ith redundant graph, i.e., ES(G i
a
r . Let - i: G i
a
r , be the initial
embedding function for the ith application graph G i
a .
Definition 2.4 Given an Embedding Architecture, define the Initial Embedding, IE, to
be a set of - i
0 for all G i
a in the family.
For the above example in figure 1, an initial embedding can be a set of - i
0 such that
each node of G i
a maps to the bottom node of each module of G i
r .
Given an embedding architecture for a G i
a , after k nodes have failed, obviously there
may be many different embedding functions - k 's. But, the difference between S(- i
should be as small as possible for the purpose of real-time fault-tolerance.
Suppose that the number of nodes in G i
a is n. Given EA, IE and that k - FT (G i
a
nodes have failed, let the cost of reconfiguration of G i
a , 4(k; n), be the minimum of
k )j over all the possible embedding functions - i
When there is no - i
k , 4(k; n) = 1. We also want to measure the total distance between
original nodes and replacing nodes after reconfiguration. The total distance cost
of reconfiguration for G i
a , 4 d (k; n) is similarly defined to be the following:
When there is no - i
1. Under a given EA and IE, let DR(k; n), the Degree
of Reconfigurability for G i
a , be the maximum of 4(k; n) over all possible k failures in
a
failures of k nodes
The Degree of Reconfigurability with distance, DR d (k; n), is defined similarly (change 4
to be 4 d in the above equation).
Return to the example in figure 1. Let the distance between two nodes in the same
module be one, and the distance between two nodes, one in module i and the other in
module j, be 1. In this case DR(k; n) and DR d (k; n) for G n
a are both k, since
for any k - FT (G n
a need only change k nodes in the same modules as
the k faulty nodes, and the distance between two nodes in the same module is one.
Definition 2.5 An Embedding Architecture, EA is finitely reconfigurable (resp. locally
reconfigurable), if there exists an Initial Embedding, IE, such that for all the G i
a 2 G a ,
DR(k; n)(resp. DR d (k; n)), can be bounded from above by a function of k but not n.
For example, the embedding architecture for linear arrays in the example above is both
LR and FR, since for each G i
a , DR(k; n) = DR d (k; n) - k.
We show in the following lemma that Hayes' h-FT (n
which is an h-fault-tolerant graph for an n-node loop application graph, is not finitely
reconfigurable.
Figure

2: Hayes' 4-FT single loop.
The nth application graph G n
a is an n-node single loop, and the embedding strategy is
to map G i
a to its so-called Hayes' h-FT (n + h)-node single loop. Thus, G n
r is defined by
the following procedure, where we assume for this example that h is even.
a single-loop graph C n+h with nodes.
Join every node x i of C n+h to all nodes at index distance j from x i , for all j
satisfying
The resulting graph G n
r is an h-FT (n Hayes [4] shows
that its MFT (G n
a Let the distance between node x i and x j be
All the computations in the proof are based on indices mod n+h, and all the indices are
in G r . The graph in Figure 2 is an example for
Lemma 2.1 The above embedding architecture with h, mapping the
n-node single loop to Hayes' h-FT (n + h)-node single-loop graph, is neither FR nor LR
if h is o(n 1
Proof: We assume there is an adversary A who always tries her best to select failures
that show that DR(k; n) is not bounded by a function of k only. No matter what the
initial - n
working nodes must be distributed among the nodes of G n
r . Define
a segment S to be a sequence of consecutively numbered working nodes
in G n
r , where x i\Gamma1 and x j+1 are non-working redundant nodes. Denote the length of the
segment S by suppose the h non-working nodes, ordered by their
indices, form the sequence
For each x i j there is a segment S j (it may
be null) starting from x i j +1 . Thus,
There must exist a segment S   such that l(S
. Without
loss of generality, assume that S   is from node x 1 to node x l(S   ) .
The adversary can choose the middle node x d of segment S   to be faulty, that is
e. Pick a reconfiguration that is optimal in the sense that the fewest possible
number of nodes in G n+h
r are changed. Let m be the number of nodes in S   which are
changed in this reconfiguration, Let C be such a sequence of m nodes,
ordered by their indices. We know x d must be replaced by one node, say x
d , and if x 0
d is
a working node, it must be replaced by another node. Thus, there is a sequence ' C of
working nodes in S   in this sequence of replacements, starting with x d and ending at a
working node that is replaced by the first node x r outside S   . First, we divide S   into
many small subsegments with length w, where
h+ 1), and represent them as a
sequence (S
d be in subsegment S
. Without loss of generality, assume
that the index of x r is larger than the largest index of a node in C; i.e., r
We claim that there must exist at least one node in C in the subsegment S
k or S
1 .
Suppose not. Let x r replace x i in C and let a and b be the two nodes connected to x i
in the initial working subgraph. Since connections must be of length at most
the distance between x i and the last node in S   (and also the first node in S   ) is ?
we know a and b must be in S   . If a or b is not in C, say a, because a is not replaced,
x r must be connected to a after the reconfiguration. But we know that i
r ? l(S   ) from the assumption, so it is impossible that x r is connected to a. Thus, we
know that a and b are in C, say that a is replaced by a 0 . Denote the sequence of original
working nodes starting from x i toward one direction in the original working subgraph by
and the sequence after reconfiguration by fx r ; a 0 ; a 0; a :g. If a 0 2 S   ,
because a 0 replaces a, a 0 must be in C. Since the index of a 0 is impossible for
a 0 to be connected to x r . Thus, a 0 is not in S   . In summary, we know that if x
x r 62 S   , then a is in C and a 0 is not in S   . Repeating the argument, using a instead of x i
and a 0 instead of x r , we can get the result that a 1 is in C and a 0
1 is not in S   . Continuing
in this way, it follows that all the nodes a; a 1 ; a are in C and nodes a 0 ; a 0
are
not in S   , but this is impossible, since there are only finite number of nodes in C. Thus,
our claim is correct.
We claim next that in each pair of the subsegments (S
l , S
there exists at least one node in C. We have proved that it is true for the first pair of sub-segments
Assume it is true for all the pairs of subsegments from
not in S
k\Gammaj , and S
g.
Since x d 2 C 0 , from the way that x r is chosen we know there must exist one node in C 0
which is replaced by a node outside of C 0 . If, in S
k\Gammaj+1 and S
j , there does not exist a node
in C 0 , the same argument as above results in the same contradiction. Thus, in each pair
of subsegments in S   , there is at least one node which has been replaced. The number of
nodes in C must therefore be at least
number of nodes
that is an unbounded function of n need to be changed. Thus, DR(k; n) is not bounded
by a function of k only, under any initial embedding function - n
therefore the Hayes'
embedding architecture is not finitely reconfigurable. It is obvious that the total distance
between original nodes and their replacing nodes is also an increasing function of n, so
it is not LR either. 2
Our next example is an embedding architecture that is finitely reconfigurable, but not
locally reconfigurable. Choose G a as in figure 1 to be a family of linear arrays, and G r as
in figure 3 to be a family of complete graphs on a row. Let ES map G n
a to G n+h
r and let
a h, for each G n
a in G a . The distance between node i and node j is defined to
be After one node has failed, say node 2, we can take any spare node to replace
it , say node shown in figure 3.
After reconfiguration
Initial embedding
n+h
n+h

Figure

3: An example that is FR but not LR.
Lemma 2.2 If h is o(n) the above embedding architecture is FR, but not LR.
Proof: It is obvious that such an EA is finitely reconfigurable, since any spare node
can replace any other node, so that only k faulty nodes need be changed after k nodes
fail. Considering G n
a and G n+h
r , under any initial embedding, there must exist a sequence
of working nodes in G n+h
r with consecutive indexes of length - n=(h 1), by the same
argument as in lemma 2.1. Choosing the middle node of such a path to be faulty, the
distance between any spare node and the faulty node must be
the distance is an increasing function of n. Thus, this EA is not locally
reconfigurable. 2
3 Degree of Reconfigurability for Dynamic Graphs
In applications we are interested in graphs which are very regular and of bounded degree.
An interesting and useful class of such graphs are called dynamic graphs [16, 6, 7, 8],
which model regular systolic and wavefront arrays in a natural way. An undirected
k-dimensional dynamic graph G defined by a finite digraph G
called the static graph, and a k-dimensional labeling of edges
The vertex set V x is a copy of V 0 at the integer lattice point x and V k is the union of all
. Let a x be the copy of node a 2 V 0 in the vertex set V x and let b y be
the copy of node b 2 V 0 in the vertex set V y . Nodes a x and b y are connected if (a; b)
and the difference between the two lattice point y and x is equal to the labeling T k (a; b).
Therefore, the dynamic graph is a locally-finite infinite graph consisting of repetitions of
the basic cell interconnected by edges determined by the labeling T k . In figure 4, we
show an example of a two-dimensional static graph G 0 and its corresponding dynamic
graph G 2 .
For g. The graph with vertex set V x and
edges with both end points only in V x is called the x-th cell of G k , C Given
a dynamic graph, we can contract all the nodes in the same cell to one node and delete
the edges totally within the cell. This contracted graph is called the cell-dynamic graph,
x6=y
We give an example in figure 5, which
is the cell-dynamic graph corresponding to G 2 in figure 4.
Given a static graph G 0 , we define F j to be the finite subgraph of G k such that
each dimension of F j has j cells, i.e., F
x
x;y
We define the family F of k-dimensional
dynamic graphs to be the set of F j , where j - 1.
There are different ways to define distance in dynamic graphs. For example, one
reasonable definition of the distance function D is to define the distance between two
nodes, one in vertex set V x , and the other in V y , to be the Euclidian distance in k-dimensional
space between point x and point y if x and y are in different cells, and
one if they are in the same cell. We say that a distance function D satisfies property
5 (triangle inequality), if the distance between nodes a and b is less than or equal to
the total distance of any path from a to b. Of course Euclidian distance satisfies 5.
The following lemma will show that when the set of redundant graphs G r is a family of
A static graph G
c
d
a
d
c
a
d c
a
d c
a
d c
a b
d c
a
d c
a
d c
a
d c
a b
(0,
c
(0,
(1,
d
a
(0,

Figure

4: An example of G 0 and the corresponding dynamic graph G 2 .

Figure

5: The cell-dynamic graph G c of G 2 .
dynamic graphs and the distance function satisfies 5, then any embedding architecture
is LR if and only if it is FR. In the rest of paper, we assume that D satisfies property 5.
Lemma 3.1 When G r is a family of dynamic graphs and its distance function satisfies 5,
the embedding architecture is locally reconfigurable if and only if it is finitely reconfigurable.
Proof: Given an EA, if this EA is LR, we know by definition that the total distance
cost of any k failures can be expressed as a function f(k), where f is a function of k
only. We know the distance between any two nodes is at least one, so the number of
nodes changed must be - f(k). Thus, this EA is also FR.
Suppose that it is FR. We know that for each G n
a 2 G a , after k nodes have failed, at
most a function of k, say f(k), nodes must be changed in the original working subgraph.
Let a 1 be the node in G n
a such that the distance in G n
r between - n
is the
maximum over all the nodes in V n
a .
Because there are at most f(k) nodes which are changed by - n
k , there exists a path in
the application graph G n
a with at most f(k) edges from a 1 to an unchanged node a 2 , i.e.
c be the maximum distance between any two nodes connected by an
edge, which is a constant independent of k and n by definition. The distance D between
node - n
is at most c \Delta f(k) by property 5, the triangle ineqality.
Similarly, the distance between node - n
is at most c \Delta f(k). Since
is at most 2c \Delta f(k). Therefore
the total distance of the f(k) changed nodes is at most 2c \Delta f(k) 2 because there are at most
pairs that are changed. EA is therefore locally reconfigurable from the definition.Finite reconfigurability is desirable in practice, especially for real-time fault tolerance,
because it shows that after k nodes have failed, at most a function of k nodes need to
be changed, independent of the size of the application graph. Lemma 3.2 will show
that the degree of reconfigurability DR provides a lower bound on the time complexity
of any distributed reconfiguration algorithm, and shows one reason this measure DR is
important. We assume in what follows that it takes one time step to send a message
through an edge.
Lemma 3.2 When G i
a is an n-node application graph and G r is a family of d-dimensional
dynamic graphs, the time complexity of any distributed reconfiguration algorithm, is
d
is the number of nodes that have failed.
Proof: After k nodes have failed, we must change at least DR nodes to reconfigure.
We can assume that a distributed reconfiguration algorithm is initiated by a neighbor
node, called a source node, of each faulty node after this neighbor node has detected
the failure. We need to inform at least DR nodes in G i
r that they are assigned different
nodes in G i
a . Thus, the time to broadcast this fault information is a lower bound on the
time complexity of any distributed reconfiguration algorithm.
Let the corresponding static graph be G its labelling be T d . The
maximum edge distance c in one dimension is the
g. Let m be equal to (jV 0 j \Theta 2c) d . We can always contract the nodes of G d into groups
of at most m nodes to obtain a d-dimensional reduced graph G 0
c ), such that
1 g. Each node of V 0
c , called a class here, represents at most m nodes of the dynamic
graph. Note that m is a constant by definition.
After t time steps, one source node can inform at most (2 \Delta t) d classes in a d-dimensional
reduced graph, so at most (2 \Delta t) d \Delta m nodes have been reached. Since there are at most
source nodes, where c 1 is the maximum degree in G r , the total number of nodes that
can be informed after t time steps is at most (2 \Delta t) d \Delta mk. There are DR nodes that need
to be informed, so t should be at
d
4 Impossibility of an LR-reliable Embedding of Dynamic
Graphs from Dimension d to d
In this section we restrict attention to dynamic graphs, and consider the relationship
between reconfigurability and reliability. In particular, we ask whether a given embedding
architecture can be finite and locally reconfigurable, and at the same time maintain
a given level of reliability. Without the constraint of being FR or LR, we can simply
construct a redundant graph to be many replications of the application graph, achieving
high reliability, but at the price of using large amounts of hardware and being difficult
to reconfigure. Our main result is Theorem 4.5: when mapping from d-dimensions to
d-dimensions, we cannot maintain both local reconfigurability and reliability simultaneously

As lemma 3.1 shows, there is no difference between local and finite reconfigurability
for dynamic graphs, and thus we consider only local reconfigurability, without the loss of
generality. We define LR-reliability in our framework as follows. Given an EA which is
LR, the probability, for each i, that G i
r contains an isomorphic image of G i
a is
a
FT
r j. The following definition replaces definition 2.5 in the statistical case.
Definition 4.1 An Embedding Architecture is LR-reliable with reliability fi, if P (G i
a
fi for all the G i
a 2 G a .
The following lemma is useful in what follows.
Lemma 4.1 Given G a , G r and ES, for each i, let MFT (G i
a ) be the maximum number
of failures that allows the corresponding EA to be LR. If this MFT is upper-bounded
by a constant as n ! 1, there exists a constant fi such that EA cannot be LR-reliable
with reliability fi.
Proof: Let the upper bound on MFT be c. By the definition of MFT in the hypothesis
of the lemma, there exist c+1 nodes in the redundant graph G i
r such that after they have
failed, for any IE, EA cannot be LR. Therefore P (G i
a
. We know
n can be chosen large enough to make c+1 ! ffln, so the term corresponding to
the largest in the summation. Thus, the probability P (G i
a
, it is obvious that when n goes
to 1, P
a ) goes to 0. Thus, for some i, we always can pick a
a ). Therefore,
such an Embedding Architecture cannot be LR-reliable with reliability fi. 2
We want to study some properties of dynamic graphs if we insist on local reconfigurability
after some nodes have failed, since local reconfigurability is desirable in practical
implementations. The following lemma tells us that one-dimensional dynamic graphs
cannot be LR-reliable when the application graphs are linear arrays.
Lemma 4.2 When G a is a family of one-dimensional linear arrays and G r is a family
of one-dimensional dynamic graphs, there exists a constant fi such that no Embedding
Architecture is LR-reliable with reliability fi.
Proof: As in the proof of lemma 3.2, we can always build a reduced graph G 0
by contracting sets of size at most m nodes in G n
r to produce a one-dimensional linear

Figure

Example of a 2-dimensional 16-node web.
array. Each node of G 0
c now represents a class of a finite number of nodes. Note that m
is a constant number, since G 0 is a finite graph by definition.
For any initial embedding, the n nodes of G n
a are distributed into at least n=m contiguous
classes in G 0
c . If the adversary chooses all the nodes in the middle class of the
above n=m classes to be faulty, the initial working subgraph is separated into two halves.
We must shift at least half of the G n
a and therefore
n) nodes to get a new
working subgraph. Thus, if an embedding architecture is locally reconfigurable, its FT
must be bounded by a constant m. From lemma 4.1, we know there exists a constant fi,
such that EA cannot be LR-reliable with reliability fi. 2
To generalize lemma 4.2, we define an n d -node d-dimensional web to be a d-dimensional
graph
g. Thus, we
connect all adjacent points in the d-dimensional Euclidian space. For example, figure 6
shows a 2-dimensional 16-node web. The family of d-dimensional webs is indexed by n.
Theorem 4.3 If G a is a family of d-dimensional webs and G r is a family of d-dimensional
dynamic graphs, there exists a constant fi such that no Embedding Architecture is LR-
reliable with reliability fi.
Proof: We can always find a d-dimensional reduced graph G 0
c ) by contracting
the dynamic graph G n
r as we did in the proof of lemma 3.2. Without loss of generality,
we consider the most general case with all possible edges present, where V 0
ae Z d and
g. Each node
2nodes

Figure

7: The n paths in the proof of theorem 4.3.
of
c represents a class of m nodes of G n
r , where m is the constant in the proof of lemma
3.2.
First, we prove that there cannot be an embedding strategy that maps a d-dimensional
web to (d \Gamma 1)-dimensional dynamic graph. Suppose first an n \Theta n two-dimensional lattice
is projected to a one-dimensional dynamic graph. Among the n 2 nodes in the web, the
vertices on the path from vertex (0; 0) to (0; must be projected to at most n
consecutive classes. Similarly, each of the n paths horizontally from (0;
and vertically to the diagonal vertices must be
projected to at most n consecutive classes. We show these n paths in figure 7. Thus, all
the nodes on the paths must be in at most 2n classes, and there must exist one class
to which at least n=4 nodes are mapped. This is impossible, since each class only has
finite number of nodes. The same argument can be generalized easily to d-dimensional
lattices. Thus, we can restrict attention to the possibility of mapping a d-dimensional
web mapping to a d-dimensional dynamic graph.
We say a class in G 0
c is empty if there is no working node in it. In the application
graph the nodes which are adjacent must be mapped to one or adjacent classes. It is not
hard to see that in the initial embedding there cannot be an empty class surrounded by
an image of a line along the y dimension in a 2-d web
an image of a line along the x dimension in a 2-d web
a line between an inner central node and the border;
there are - n
lines passing through it
inner central class
2m classes

Figure

8: The inner central class in the proof of theorem 4.3.
non-empty classes. Consider a line of - n nodes in the n d -node d-dimensional web, as in
the proof of lemma 4.2. For any initial embedding these n nodes are distributed into at
least n=m classes that are linearly connected in G 0
c . These images of lines may zig-zag in
c , but must map to at least n=m contiguous classes. Therefore, there is a well-defined
inner central class which is \Omega\Gamma n=m) classes away from the border in the image of the web,
as shown in figure 8. Note that a line between the inner central class and the border may
not be the image of a line along one dimension in the web, but the line must contains
n) nodes in the web, as figure 8 shows.
If the adversary chooses all the nodes, at most m, in the inner central class to be
faulty, the original working subgraph has a central inner hole. We must
nodes in one direction to get a new isomorphic subgraph in G n
r . Therefore, to maintain
local reconfigurability, for any embedding architecture, FT must be upper-bounded by
m. From Lemma 4.1, we then know there exists a constant fi, such that EA cannot be
LR-reliable with reliability fi 2
We next modify the application graph so that each node x
connected only to nodes We call such a d-dimensional
graph a d-dimensional orthogonal lattice. To develop intuition for the gen-
interior of the image
non-empty class
empty class

Figure

9: A pseudo hole.
eral case of d-dimensional dynamic graphs, the following lemma extends theorem 4.3 to
two-dimensional orthogonal lattices.
Lemma 4.4 If G a is a family of two-dimensional orthogonal lattices and G r is a family
of two-dimensional dynamic graphs, there exists a constant fi such that no embedding
architecture is LR-reliable with reliability fi.
Proof: As in the proof of theorem 4.3, we know that a two-dimensional orthogonal
lattice cannot be embedded in a one-dimensional dynamic graph (we made no use of
diagonal edges in that proof). Without diagonal edges, however, the rest of the proof is
a bit more complicated.
An image of an application graph can be regarded as a polygon. We say an embedding
in G 0
c has a hole of size k, if there exist k consecutive empty classes in a line along one
dimension which are inside the polygon and surrounded by non-empty classes. Thus, the
example in figure 9 is excluded from our definition of hole.
We claim that after any embedding of a two-dimensional orthogonal lattice in a two-dimensional
dynamic graph, it is impossible that there is a hole of size 2. Assume our
claim is false, and denote the empty classes in a hole of size 2 by A and B. Index the
nodes in the two-dimensional orthogonal lattice G a by x ij . For notational convenience,
choose the origin so that x 00 is a particular node which is mapped to the nonempty class
immediately above A in G 0
c . We will refer to the vertical line in G a passing through x ij
as the vertical line Lx i .
vertical line Lx 1
vertical line Lx 0
A b
a
class

Figure

10: The image of vertical lines Lx 0 and Lx 1 .
We have the following observations about the images in G 0
c of vertical lines in the
orthogonal lattice G a . First, the images of the vertical lines Lx i and Lx i+1 cannot be
more than one class apart along one dimension. Because the image of each pair of nodes
x i+1;j is in the same class or adjacent classes, this follows by induction on j.
Second, the vertical line Lx 0 and Lx 1 (resp. Lx 0 and Lx \Gamma1 ) must pass on the same side
of A and B, as in figure 10, since there is no edge passing between A and B. According
to the above two observations, by induction on i, all the vertical lines Lx i must be on the
same side of A and B (either left or right), so A and B cannot be in the interior of the
image of G a . This contradiction proves that it is impossible to have a hole of size two.
As we did in theorem 4.3, the adversary can choose the two inner central classes in one
dimension to be faulty, and as before, there is no way to reconfigure G r so that those two
faulty classes are surrounded by non-empty classes. Thus, we must
n) nodes
in one dimension to get a new working subgraph. 2
Finally, we can extend this result to d dimensions. The line containing classes A
and B will be replaced by a (d \Gamma 1)-dimensional hyperplane in a d-dimensional dynamic
graph.
Theorem 4.5 If G a and G r are families of d-dimensional dynamic graphs, there exists a
constant fi such that no embedding architecture can be LR-reliable with reliability fi.
Proof: Given an application graph G a which is a dynamic graph, a reduced graph can
be built as before. Since the application graph is connected and a class is connected
only to its neighboring classes, there exists at least one edge along each dimension from
one class to its neighboring class. Therefore, any d-dimensional reduced graph contains
a subgraph which is isomorphic to a d-dimensional orthogonal lattice. We therefore
need only prove the theorem for the case of the application graph being a family of d-dimensional
orthogonal lattices. Again, the proof of theorem 4.3 shows that d-dimensional
orthogonal lattices cannot be embedded in 1)-dimensional dynamic graphs.
We claim that it is impossible that there exist a hole of size 2 d\Gamma1 in one hyperplane
dimensions (one coordinate is fixed) in the reduced graph. Assume our
claim is false. Call the above 2 d\Gamma1 classes an obstacle O. The obstacle is composed of two
empty classes along each of the (d \Gamma 1) dimensions in H. Call the fixed dimension of H
"vertical." By the same reasoning as in lemma 4.4, no vertical lines can pass through the
obstacle O, and the images of any two adjacent vertical lines must lie on the same side of
the obstacle O in the reduced graph. Therefore, the obstacle cannot be in the interior of
the reduced graph, so our claim is correct. The adversary then chooses the inner central
in H to be faulty. There is no way to reconfigure the redundant graph such
that those faulty classes are surrounded by non-empty classes. Thus, we must change
n) nodes in one dimension to get a new isomorphic subgraph. 2
5 Possibility of an LR-reliable Embedding of Dynamic
Graphs from Dimension d to d+1
Finally, we want to show that we really can embed d-dimensional dynamic graphs in
1)-dimensional dynamic graphs, while maintaining any desired high reliability and
local reconfigurability. We begin with the one-dimensional case.
Lemma 5.1 When G a is a family of linear arrays, there exists an Embedding Architecture
G r is a family of two-dimensional dynamic graphs, which can be LR-reliable with
any given fi.

Figure

11: An LR-reliable 2-dimensional dynamic graph.
Proof: We prove this by constructing a redundant graph G n
r for an n-node linear array G n
a
as shown in figure 11. G n
r has n columns and each column has s nodes. Let FT (G n
a
The initial embedding allocates each node of G n
a to a distinct column of G n
r , i.e. let
the initial isomorphic subgraph be the sequence (0; 0), (1; 0), ., (n; 0). If one node (i;
has failed , we choose (i; 1) as the replacing node, and if nodes (i; 0) and (i; 1) have failed,
we use (i to replace nodes (i \Gamma
using the above reconfiguration procedure, we change at most 2k \Gamma 1 nodes after any
a with respect to such an EA and IE
is locally reconfigurable.
We now want to show that given fi, we can find an s and G n
r with the desired
properties. Let -
r be a square piece of G n
r , an n \Theta n dynamic graph. Let p(n) be the
probability that -
r contains G n
a . We form a vertical pile of s=n such blocks to obtain
s \Theta n such dynamic graphs as in figure 12. After we connect each two adjacent squares,
the resulting graph is the same as G n
r .
Since connections between two squares can only increase the reliability, the probability
that there does not exist a working linear array in this big graph is . For

Figure

12: A pile of -
r for the proof of lemma 5.1.
any c, if s ?
cn \Delta logn
, the above probability will be ! 1=n c . Therefore, for any
reliability fi, we can find a sufficient large s to achieve reliability fi. 2
We can now prove the main result in this section.
Theorem 5.2 When G a is a family of d-dimensional dynamic graphs, there exists an
embedding architecture where G r is a family of (d+1)-dimensional dynamic graphs, which
can be LR-reliable with any given fi.
Proof: As before, we construct a reduced graph from the given dynamic application
graph G a . The most general form of a reduced graph is a web. Thus, without loss of
generality, we need only prove the theorem for the case of the application graph being
a family of d-dimensional webs. We can use the same construction and reconfiguration
method as we did in the previous lemma. 2
From the above reconfiguration method, after k - FT (G n
a ) nodes have failed, we need
to change at most 2 \Delta k nodes. The following corollary shows that when
reduce this to exactly k nodes.
Corollary 5.3 When G a is a family of linear arrays, there exists an embedding architecture
G r is a family of two-dimensional dynamic graphs with edge degree 4m
where m is any constant - 2, such that after any k - FT (G n
a ) nodes have failed, we only
need to change k nodes.

Figure

13: Dynamic graph construction for corollary 5.3.
Proof: First construct the dynamic graph as shown in figure 13, where there are s nodes
in each column: each node (i; j) connects to (i
m).
The reconfiguration method is the same as in lemma 5.1. Let FT (G n
a
a in the family, and allocate nodes of G n
a to different columns as before. The number
of nodes which need to be changed after k nodes in one column have failed is at most
d
e \Theta 2 \Gamma 1. This is the worst case, so DR(k; n) = max(d
2. 2
Similar constructions work for d dimensions.
6 Conclusions and Open Problems
Our main result is that it is difficult for dynamic graphs to maintain both local reconfigurability
and a fixed level of reliability. More precisely, the dynamic graph must be of
dimension at least one greater than the application graph to have both properties.
The problem of considering the tradeoffs among the size of redundant graphs (the
number of edges), reconfigurability, and reliability needs to be studied further. A class
of simple layered graphs with a logarithmic number of redundant edges is proposed
in [19] which can maintain both finite reconfigurability and a fixed level of reliability
for a wide class of application graphs. By sacrificing finite reconfigurability, they also
construct highly reliable structures with the asymptotically optimal number of edges
for one-dimensional and tree-like array architectures. However, the redundant graphs
resulting from the constructions are not dynamic graphs. It would be interesting to
consider the construction of redundant graphs that are restricted to be dynamic graphs,
which are more easily implemented than less regular graphs.



--R

"Diogenes: A methodology for designing fault-tolerant VLSI processing arrays,"
"Digital signal processing applications of systolic algorithms,"
"Configuration of VLSI arrays in the presence of defects,"
" A graph model for fault-tolerant computing systems, "
"Distributed reconfiguration and recovery in the advanced architecture on-board processor,"
"Testing for cycles in infinite graphs with periodic struc- ture,"
"Planarity testing of doubly periodic infinite graphs,"
"A semiring on convex polygons and zero-sum cycle problems,"
" Why systolic architectures?"
"Fault tolerant VLSI systolic arrays and two-level pipelines,"

"Wavefront array processor: Languages, architecture, and applications,"
"Fault-tolerant array processors using single track switches,"
"A scalable architecture for lattice-gas simulation, "
"Wafer-scale integration of systolic arrays,"
"Some problems on dynamic/periodic graphs,"
"Efficient algorithms for reconfiguration in VLSI/WSI arrays,"
"Reconfiguration architecture for VLSI processing ar- rays,"
"Explicit Constructions for Reliable Reconfigurable Array Architectures"
--TR
Configuration of VLSI Arrays in the Presence of Defects
Testing for cycles in infinite graphs with periodic structure
VLSI array processors
Fault-Tolerant Array Processors Using Single-Track Switches
A scalable architecture for lattice-gas simulations
Efficient Algorithms for Reconfiguration in VLSI/WSI Arrays
A semiring on convex polygons and zero-sum cycle problems
systolic arrays;bounded-degree graphs;wavefront arrays;fault tolerant computing;reconfigurable architectures;reconfigurability;finitely reconfigurable;reliable arrays;dynamic graphs;locally reconfigurable;time complexity;lower bound;fault-tolerant redundant structures;application graph;reliability