Scheduling Data-Flow Graphs via Retiming and Unfolding.
AbstractLoop scheduling is an important problem in parallel processing. The retiming technique reorganizes an iteration; the unfolding technique schedules several iterations together. We combine these two techniques to obtain a static schedule with a reduced average computation time per iteration. We first prove that the order of retiming and unfolding is immaterial for scheduling a data-flow graph (DFG). From this nice property, we present a polynomial-time algorithm on the original DFG, before unfolding, to find the minimum-rate static schedule for a given unfolding factor. For the case of a unit-time DFG, efficient checking and retiming algorithms are presented.
INTRODUCTION
OW to efficiently and optimally schedule iterative or
recursive algorithms is an important problem in VLSI
high level synthesis and compilers for parallel machines
like VLIW or Data-Flow machines. For example, given a
signal flow graph of any filter (it may have many cycles),
we would like to know how to obtain a schedule such that a
resultant synthesized hardware can achieve the highest
pipeline rate. We combine two techniques, retiming and
unfolding, to maximize the execution rate of static sched-
ules. This combination technique turns out to be very simple
and efficient, and has great potential to be generalized
to other applications. In this paper, we study some fundamental
theorems of this combination, and provide efficient
algorithms.
The input algorithm is described as a data-flow graph
(DFG), which is widely used in many fields; for example, in
circuitry [1], in program descriptions [2], [3], [4], etc. In a
DFG, nodes represent operations and edges represent
precedence relationships. The graph G in Fig. 2a is an example
of DFG, where the number attaches to a node is its
computation time. A DFG is called a unit-time DFG if the
computation time of every node is one unit. A certain delay
count is associated with each edge to represent inter-iteration
precedences.
Although our results are quite general to many applications
which use the model of DFGs, in this paper, we specifically
consider the problem of multiprocessor scheduling
for a recursive or iterative algorithm, as being studied in
[5], [4], which is particularly useful in DSP applications
(DFGs are usually called signal-flow graphs in DSP). Fig. 1
shows an innermost body of a loop program, and the DFG
in Fig. 2a is its corresponding DFG. A schedule 1 for G is
shown in Fig. 2b, which takes three time units (equals the
cycle period of G) to complete an iteration. Since we can use
this schedule repeatedly for each iteration, we call such a
schedule a static schedule.
to n do
Fig. 1. A loop program.
The retiming technique has been effectively used to improve
static schedules by rearranging the delays [1], [6].
The retimed DFG, denoted by G r , in Fig. 3a corresponds to
a faster static schedule in Fig. 3b. Static schedules can be
further improved by using the common unfolding tech-
nique. The unfolding technique is studied in [4], [6], and
generalized to handle switches in [7]. The original DFG is
unfolded f times, so the unfolded graph, denoted by G f ,
consists of f copies of the node set and the edge set. Each
instance of a static schedule contains f iterations, and its
computation time is called the cycle period. Therefore, the
iteration period, which is the average computation time per
iteration (cycle period/f) can be reduced. This f is called an
unfolding factor.
A static schedule can be obtained from an unfolded
graph, and executed repeatedly for every f iterations. The
amount of memory needed to store a static schedule is proportional
to the unfolding factor. For general DFGs, Parhi
and Messerschmitt [4] show that, if the unfolding factor is
the least common multiple of all the loop delay counts in
DFG, a rate-optimal schedule can be achieved. An iterative
algorithm is designed in [6] to find the minimum unfolding
factor to achieve a given iteration period.
1. Under the assumption that there are enough resources available, each
node is scheduled as early as possible.
. L.-F. Chao is with the Dept. of Electrical and Computer Engineering, Iowa
State University, Ames, IA 50011. E-mail: lfc@iastate.edu.
. E. H.-M. Sha is with the Department of Computer Science and Engineer-
ing, University of Notre Dame, Notre Dame, IN 46556.
E-mail: hms@cse.nd.edu.
Manuscript received 14 Oct. 1992; revised 17 Oct. 1994.
For information on obtaining reprints of this article, please send e-mail to:
tpds@computer.org, and reference IEEECS Log Number 100505.
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 8, NO. 12, DECEMBER 1997
F:\LIBRARY\TRANS\PRODUCTION\TPDS\2-INPROD\100505\100505_1.DOC regularpaper97.dot AB 19,968 10/22/97 9:37 AM 2 / 9
Like most previous works [4], [6], we assume that the
scheduler can only operate on integral grids, i.e., each operation
starts at an integral instant of time. The rate-optimal
scheduling and unfolding factors for a fractional-time
scheduler, which can start an operation at any fractional
time instant, are discussed in [8]. The size of program code
or control unit is proportional to the unfolding factor. A
synthesis system should provide many alternatives, such as
the pairs of unfolding factors and their corresponding
minimum iteration periods under retimings.
The designer can choose the most suitable pair among
them. For a given maximum unfolding factor F from the
design requirement, we present efficient algorithms to find
these pairs on the original DFG. One obvious way is to unfold
the original DFG first, and then do retiming to find the
minimum iteration period. Instead, we show that we can
perform retiming directly on the original DFG, and obtain
the same minimum iteration period without working on a
large unfolded DFG. This nice and counter-intuitive property
is shown in Section 3 by proving that the order of
retiming and unfolding does not matter for obtaining the
minimum iteration period.
The results for unit-time DFGs are obtained in Section 4.
A simple inequality is derived as a necessary and sufficient
condition for the existence of a retiming to produce a
schedule with unfolding factor f and cycle period c. The
minimum iteration period for a given unfolding factor can
be evaluated from this inequality. And, there is an efficient
algorithm which runs in time O(|V| -
|E|) for finding such
a retiming, where V is the node set and E is the edge set.
As for a general-time DFG, the necessary and sufficient
condition can not be characterized in a simple formula as that
for unit-time DFGs. For getting the pair of an unfolding factor f
and its corresponding minimum iteration period, we present
our retiming algorithm in Section 5 which runs in time
and the preprocessing algo-
rithm, which runs in time O(f
When we want to obtain all the pairs of unfolding factors
which are less than F, and the corresponding minimum iteration
periods, the nice thing for the preprocessing algorithm is
that it only needs to be performed once for the maximum unfolding
factor F, instead of F times. Note that all the algorithms
in the paper are easily implemented, since they are mainly
variations of general shortest path algorithms.
We first describe definitions and properties of retiming
and unfolding. Then, we prove the order of retiming and
unfolding is immaterial in Section 3. The algorithms and
results for unit-time DFG are presented in Section 4 and, for
general-time DFG, in Section 5. Finally, we make some concluding
remarks in the last section. Since detailed proofs are
sketched or omitted due to space limitations, interested
readers are referred to [9], [10].
DEFINITION 1. A data-flow graph (DFG) d, t) is a
node-weighted and edge-weighted directed graph, where V
is the set of nodes,
V is the set of edges, d is a
function from E to the nonnegative integers, and t is a
function from V to the positive integers.
(a) (b)
Fig. 2. The corresponding data-flow graph G: (a) a DFG G, (b) a static schedule.
(a) (b)
Fig. 3. A retimed DFG: (a) a retimed DFG G r , (b) a static schedule.
CHAO AND SHA: SCHEDULING DATA-FLOW GRAPHS VIA RETIMING AND UNFOLDING 3
F:\LIBRARY\TRANS\PRODUCTION\TPDS\2-INPROD\100505\100505_1.DOC regularpaper97.dot AB 19,968 10/22/97 9:37 AM 3 / 9
Interiteration data dependencies are represented by
weighted edges. An edge e from u to v with delay count d(e)
means that the computation of node v at iteration j depends
on the computation of node u at iteration j # d(e). The set of
edges without delay composes a directed acyclic graph, which
represents data dependencies within the same iteration. 2
We define one iteration to be an execution of each node in
exactly once. The computation time of the longest path
without delay is called the cycle period. For example, the cycle
period of the DFG in Fig. 2a is three from the longest path,
which is from node B to C. An edge e from u to v with delay
count d(e) means that the computation of node v at iteration j
depends on the computation of node u at iteration j # d(e).
For the sake of convenience, we use the following notation.
The notation u v
e
# means that e is an edge from node u to
node v. The notation u v
means that p is a path from node u
to v. The delay count of a path p v v v v
# is
1 . The total computation time of a path p is
2.1 The Retiming Technique and Retimed Graphs
The retiming technique [1] moves delays around in the following
way: A delay is drawn from each of the incoming
edges of v, and then, a delay is pushed to each of the out-going
edges of v, or vice versa. A retiming r of a DFG G is a
function from V to the integers. The value r(v) is the number
of delays drawn from each of the incoming edges of node
v and pushed to each of the outgoing edges. 3 (See Fig. 3.)
be the DFG retimed by a retiming r
from G. For any edge u v
e
# , we have d r
a similar property applies for any path. A retiming is legal if
the retimed delay count d r is nonnegative for every edge in E.
A legal retiming preserves the data dependencies of the
original DFG, although a prologue is needed to set up the
initial assignments.
Compare Fig. 2 and Fig. 3. The technique of retiming regroups
operations in a loop into new iterations, in which
each operation is executed once. The operation v in the
original iteration i is shifted to the new iteration i # r(v). In
general, if r(v) . 0, r(v) instances of node v appear in the
prologue; if r(v) . 0, #r(v) instances appear in the epilogue.
The edges without delay in G r give the precedence relations
of the new loop body. Although the prologue and epilogue
are introduced by retiming, the size of prologue and epilogue
can be controlled by adding simple constraints to the
proposed retiming algorithms [9].
Under the definition of retiming [1], there is no distinction
between recursive (cyclic) and nonrecursive (acyclic)
parts in the DFG. If the input/output behavior needs to be
preserved, a host can be introduced in the DFG so that there is
an edge from the host to every input node and an edge from
every output node to the host. After this transformation, our
2. For the graph to be a meaningful data-flow graph, the delay count of
any loop should be nonzero.
3. Note that r(v) is positive if delays are pushed along the direction of
edges.
algorithms can be applied to the DFG without special considerations
for the nonrecursive part.
2.2 The Unfolding Technique and Unfolded Graphs
Let f be a positive integer. An unfolded graph with unfolding
factor f, denoted G f , consists of f copies of node set V
and represents the same precedence relations in G by delay
counts on edges. We say the unfolded DFG G
is a DFG obtained by unfolding G f times. Set V f is the union
of
# . Let u i be the node u in V i and the computation
t(u). For example, the DFG in Fig. 4a is the
unfolded graph with factor two for the DFG G r in Fig. 3a.
The unfolded graph gives a more global view to the data
dependencies with a manageable graph size.
We use the subscript f to represent the correspondences
between G and G . For a node v (resp. edge e) in G, v f (resp. e )
represents any copy of v (resp. e) in G f . For a path p f in G f ,
there is a unique path p in G corresponding to p f . Let Z be the
set of integers and [0, f) the set of integers 0, 1, 2, #, f # 1. For
a, b - Z, the notation a - f b means that there exists n - Z such
that a # f. The operation a % f produces a congruent
integer within [0, f).
One cycle in G f consists of all computation nodes in V f .
The period during which all computations in a cycle are
executed is called cycle period. The cycle period &(G ) of G
for every path p f in G f }. During
a cycle period of G f , f iterations of G are executed. Thus, the
iteration period of G f is equal to &(G f ) /f, in other words, the
average computation time for each iteration in G. For the
original DFG G, the iteration period is equal to &(G). An
algorithm can find &(G) for a DFG in time O(|E|) [1].
Some properties of the unfolded graph have been studied
in [4]. A procedure has been proposed to generate the
unfolded graph. However, the relationship between d(e)
and d f (e F ) is not clear. We characterize some properties of
the unfolded graph in the following, which will be used in
the proofs of this paper. Though Property 1d has been
(a) (b)
Fig. 4. An unfolded retimed DFG G r,f and a globally-static schedule:
(a) G r,f with 2.
4 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 8, NO. 12, DECEMBER 1997
F:\LIBRARY\TRANS\PRODUCTION\TPDS\2-INPROD\100505\100505_1.DOC regularpaper97.dot AB 19,968 10/22/97 9:37 AM 4 / 9
pointed out in [4], we restate it with our notation. From
these properties, a simpler procedure of constructing the
unfolded graph is shown in Fig. 5.
PROPERTY 1. Let u and v be nodes in G and u v
e
# .
a) For any 0 . i < f and 0 . j < f, there is an edge u v
e
f
in G f if and only if
b) The f copies of edge e in G f are the set of edges
c) The total number of delays of the f copies of edge e is d(e),
i.e., d e d e
f
f
0These properties can be easily extended to paths by substituting
for e and each path in G has exactly f copies in G .
From the definition of &(G), Leiserson and Saxe [1] derived
the following characterization for cycle period.
LEMMA 2.1 [1]. Let G be a DFG and c a cycle period. &(G) . c if
and only if for every path p in G if
We prove a similar property for the unfolded graphs in
the following lemma. The value of &(G f ) is obtained from
the original DFG G, and we show that the cycle period in
the unfolded graph G is the maximum total computation
time among all paths where the total delay count is less
than f in the original graph G.
LEMMA 2.2. Let G be a DFG, c a cycle period, and f an unfolding
factor.
a) &(G f ) is equal to max {t(p) | d(p) < f for every path p in G.
only if for every path p in G if t (p) > c
then d(p) . f.
2.3 The Combination
For a DFG G, let G r,f be the DFG obtained by unfolding G r with
factor f, and G f r be the DFG obtained by retiming G f with
function r f , which is a retiming from V f to Z. We define the
minimum cycle period, denoted by MCP(f), under an unfolding
factor f as min ( )
G
& , which is the minimum cycle period
achieved by unfolding G with factor f. In the next section,
we show that MCP f G G
f
the approach of retiming first, then unfolding, can achieve the
same minimum cycle period, we say that the order of retiming
and unfolding is immaterial. With this approach, one does not
need to compute retiming functions on a large unfolded
graph. Hence, it is computationally more efficient.
Although the retimed graph in Fig. 3 achieves the minimum
cycle period with unfolding Factor 1, MCP(1), the
graph G r,f where has a cycle period 4, which is not
MCP(2). In this paper, retiming algorithms are designed to
find a retiming achieving MCP(f) without unfolding a DFG
first. For the above example, our algorithm will find another
retiming r " shown in Fig. 6, which is optimal with both unfolding
Factors 1 and 2. The cycle period of G r equals MCP(1).
From Lemma 2.2, we know the cycle period of G r, f with
is three, which is the minimum.
In this section, the relationship between G f r and G r, f for a
fixed unfolding factor is explored. Intuitively, it seems that the
, provides finer retimings on the unfolded node set
and gives better flexibility on retiming. However, we show
that the order of retiming and unfolding is not essential. More
precisely, we prove MCP f G G
Therefore, in the next two sections, we focus on finding a
retiming r to achieve MCP(f) for a given unfolding factor f on
for every edge do begin
Add edge e u v
f
G to
Add edge e u v
f
G to
Fig. 5. The procedure for constructing E f and d .
(a) (b)
Fig. 6. A DFG retimed by another retiming r ": (a) DFG G r retimed by r ", (b) iteration period = 2.
CHAO AND SHA: SCHEDULING DATA-FLOW GRAPHS VIA RETIMING AND UNFOLDING 5
F:\LIBRARY\TRANS\PRODUCTION\TPDS\2-INPROD\100505\100505_1.DOC regularpaper97.dot AB 19,968 10/22/97 9:37 AM 5 / 9
The following lemma says that any cycle period which is
obtained by retiming the unfolded graph G f can be
achieved by retiming on the original graph G directly, while
Lemma 3.3 proves the converse.
LEMMA 3.1. Let G be a DFG, c a cycle period and f an unfolding
factor. For any legal retiming r f on the unfolded graph G f ,
such that & ( )
G c
. , there exists a legal retiming r on the
original graph G such that &(G r,f ) . c.
PROOF. Assume that r f is a legal retiming from V f to Z, such
that
G c
f r . Let r be a retiming from V to Z and
we choose r u r u
f
f
1 for every u - V, where u i
is the ith copy of node u in V f . We show that r is a legal
retiming and &(G r, ) . c.
Since r f is a legal retiming, it is easy to show that r
is also a legal retiming. Then, we prove that &(G r, f ) .
G c
. , from Lemma 2.1, we know for
every
# for u v
f
V , we know
f
V be a
path such that t f (p f ) > c and u v
in G is the corresponding
path of p . Since t f (p i for the ith copy of
# , we know r f (v (i+d(p))%f
for every 0 . i < f. By summing up these f inequalities,
we have r V r u d p f d p f
f
f
1 . There-
fore, we know for every path p in G, if t(p) > c, then r(v) #
r(u) . d(p) # f. Thus, from Lemma 2.2, r is a legal retiming
of G such that &(G r, f ) . c.
The following lemma proves that G f and G r,f are struc-
turely isomorphic, which means that there is a one-to-one
correspondence among edges and nodes of the two
graphs, and the mapping is to circularly shift every copy
of node v in V by the amount r(v). Actually, this lemma
gives a way of constructing DFG G r,f directly from G with
given r and f, instead of constructing G r first and then unfolding
it. We consider that G f and G r,f have the same node
set, denoted V f , but different edge sets, denoted E f and E r,f
respectively, and different delay functions, denoted d f and
d r,f respectively.
Lemma 3.2. Let d, t) be a DFG, r a retiming on G,
and f an unfolding factor. The unfolded graph
and the unfolded retimed graph G
have the following relation: There is an edge from u i to v j in
G f iff there is an edge from u i r u
# to v j r v f
# in G r,f .
PROOF. Consider an edge e r,f from u i r u f
# to v j r v f
# in
G r,f . From Property 1, this edge corresponds to edge
e
# in G r , iff d r
r(v), the modular equation is
equivalent to that d(e) - f j # i, which means that there
is an edge from u i to v j . Thus, the lemma is proved.
The above lemma also holds for the corresponding paths in
G f and G r,f . For the structurally equivalent graphs G f r
, and
G r,f , we show that there is certain correspondence between
the two retimings r and r.
Lemma 3.3. For any legal retiming r on the original graph G
such that &(G r,f ) . c, there exists a legal retiming r f on the
unfolded graph G f such that & ( )
G c
f r .
PROOF. Let r be a retiming from V to Z such that &(G r,f ) . c.
From Lemma 3.2, we know that G f and G r,f are struc-
turely equivalent, and there is an edge from u i to v j in G
iff there is an edge from u i r u f
# to v j r v f
# in G r,f .
We want to prove that there exists a retiming r f such
that G f r f
, is equivalent to G r,f , that is, each pair of corresponding
edges have the same delay count. Let e f and
e r,f be a pair of corresponding edges for u v
e
# and
e
# . We want to find a retiming r to
satisfy the equations d e d e
G f . Since d e d e r u r v
# , we derive
r Thus, if the following linear
system has an integer solution, a retiming r f is found. For
every u v
e
# in G f and u v
e
# in G r,f ,
are unknown variables and
are constants. We show that the linear
system is consistent and has an integer solution r f .
is equivalent to G r,f , the retiming r f is certainly
a legal retiming. The lemma is proved.
The following theorem is derived from Lemma 3.1 and
Lemma 3.3.
THEOREM 1. Let G be a DFG and f a fixed unfolding factor.
a) There is a legal retiming r on the original graph G such
that &(G r,f ) . c if and only if there is a legal retiming
r on the unfolded graph G such that & ( )
G c
f r .
It seems that retiming on the unfolded graph tends to have
better iteration period, because finer retiming functions can
be found. However, this theorem tells us that, for a fixed
unfolding factor, the minimum iteration period can be
found no matter which unfolding or retiming is performed
first. Obviously, a retiming on the original graph saves time
and space, which is the focus of the rest of the paper.
6 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 8, NO. 12, DECEMBER 1997
F:\LIBRARY\TRANS\PRODUCTION\TPDS\2-INPROD\100505\100505_1.DOC regularpaper97.dot AB 19,968 10/22/97 9:37 AM 6 / 9
It is well known that any DFG which involves loops, feedbacks
or recursions has a lower bound on the iteration period
[11]. This iteration bound %(G) for a DFG G is given by
G
D l
loop in G
where T(l) is the sum of computation time in loop l, and D(l) is
the sum of delay counts in loop l. For a unit-time DFG, it takes
O(|V||E|) to compute the bound %(G). The loop which gives
the iteration bound is called critical loop, l cr . For example, the
in Fig. 2a is 4/3. A schedule is rate-optimal if the iteration
period of this schedule equals to the iteration bound.
In this section, we show that c/f . %(G) is a necessary and
sufficient condition for the existence of a retiming to produce
a schedule with unfolding factor f and cycle period c. The
minimum cycle period for a given unfolding factor is derived
as
- % . An efficient O(|V||E|)-time algorithm
is design to find such a retiming.
be the graph modified from
every edge e in E. Note
that G # x may have nonintegral, even negative, delay
counts if x is not an integer. The next lemma shows the relation
of G # f/c and the lower bound %(G).
LEMMA 4.1. Let G be a unit-time DFG and f and c positive inte-
gers. The graph G # f/c contains no loops having negative
delay counts if and only if c/f . %(G).
PROOF. Assume that G # f/c contains no loops having negative
delay counts. Let D-(l) be the delay count of a
loop l in G # f/c. Since the number of edges in loop l
equals T(l) in unit-time DFG, we know
(f/c) - T(l) . 0. Therefore, we have c/f . T(l)/D(l) for
every loop l in G. The if part can be proved similarly.
Similar to the characterization of cycle period for unit-time
DFGs under retiming in [1], we give a characterization
of cycle period under both retiming and unfolding.
LEMMA 4.2. Let E) be a unit-time DFG, c a positive in-
teger, and f an unfolding factor. There is a legal retiming r
on G f such that &(G r,f ) . c if and only if G # f/c contains
no loops having negative delay counts.
PROOF. The only if part can be easily proved by contradic-
tion. If there is a loop with negative delay, from
Lemma 4.1, we know c/f is smaller than the lower
bound %(G). Thus, no retiming r exists such that
For the if part, we assume that there is no loop
with negative delay count. We construct a retiming
for the DFG as follows: We first add a new node v 0 in
the graph G # f/c, where v 0 is connected to all the
nodes with delay 0, and compute all the shortest
paths from v 0 to other nodes. Let Sh(v) be the length
of the shortest path from v to v 0 . We choose the
retiming r of node v equals the ceiling of Sh(v) for every
v in V. It is easy to prove that r is a legal retiming and
which is similar to the proof in [1].
From this lemma, we have a retiming algorithm to find a
retiming r such that &(G r,f ) . c, as shown in Fig. 7. We adopt
the single-source shortest path algorithm introduced in [12]
to find the shortest paths Sh(v) for all nodes v. If there is a
negative loop, the algorithm will report it, and if not, we return
the retiming function r(v) to be the ceiling of Sh(v). The
time complexity of this retiming algorithm is O(|V| - |E|).
The static schedule with cycle period c can be easily obtained
by unfolding the retimed graph G r in time O(f |E|).
The following theorem provides us a simple existence
criterion, c/f . %(G), to check whether a given cycle period
c can be achieved.
THEOREM 2. Let G be a unit-time DFG and f and c positive inte-
gers. The following statements are equivalent:
does not contain any cycle having negative delay
count.
There exists a legal retiming r on G such that, after G
is retimed by r and unfolded by f, the cycle period
PROOF. From Lemma 4.1, the first and the second statements
are equivalent. The equivalence of the second
and the third statement is proved from Lemma 4.2.
For a pair of given integers f and c, if there exists a legal
retiming r such that &(G r,f ) . c, we say the pair is feasible.
From Theorem 2, the designer only needs to check the inequality
c/f . %(G) in order to decide the feasibility of a pair
of f and c. For an unfolding factor f, the minimum feasible c
from the inequality is MCP f f G
- % . Thus, all the
pairs of f and MCP(f) are easily generated, and the designer
may choose the suitable pair according to its requirement.
A legal retiming r for such a chosen pair can be found
merely in time O(|V| |E|). The corresponding schedule
can be generated from the graph G r,f . The maximum difference
between the iteration period of the chosen pair and the
iteration bound %(G) is less than 1/f.
Retiming Algorithm
Input: a DFG G, an unfolding factor f and a cycle period c.
Output: A retiming r such that &(G r,f
begin /* pass is used
to prevent the algorithm being trapped in negative
loops. */
for every node v - V do begin
to Q; end;
pass - 0;
last - the last element in Q;
while Q is not empty and pass < |V| do begin
Pop v from Q;
for every edge
if w is not in Q then PUSH w to Q; end;
last then begin
last - the last element in Q;
pass
if Q is empty then
for every v - V do r v Sh v
else "There is a negative loop in the graph G # f/c."
Fig. 7. Retiming Algorithm for unit-time DFGs.
CHAO AND SHA: SCHEDULING DATA-FLOW GRAPHS VIA RETIMING AND UNFOLDING 7
F:\LIBRARY\TRANS\PRODUCTION\TPDS\2-INPROD\100505\100505_1.DOC regularpaper97.dot AB 19,968 10/22/97 9:37 AM 7 / 9
As a consequence of Theorem 2, the minimum rate-optimal
unfolding factor, which produces a rate-optimal schedule,
can be derived as D(l cr ) / gcd(T(l cr ), D(l cr And, the
corresponding rate-optimal schedule can be easily derived
from our algorithm.
We first design an algorithm to find a retiming r such that
possible, for a given unfolding factor f and a
given cycle period c. A preprocessing algorithm is performed
first in order to find a set of critical paths, which is
presented in the second subsection. In the first subsection,
some properties about these critical paths are derived in
order to represent the above problem in a simple Linear
Programming (LP) form, which can be solved in time
O(|V| 3 ) by a general shortest path algorithm. Then, by binary
search on all the O(f|V| 2 ) possible cycle periods, we
can find a legal retiming r which achieves the minimum
cycle period on DFG G r,f for a given unfolding factor f in
time
5.1 Retiming Algorithm
Since the delay count of every path from u to v is changed
by the same amount r(u) - r(v) after the DFG is retimed by
r, the quantities defined below specify a set of critical paths
for all paths from u to v such that we only need to look at
these quantities in order to decide whether &(G f ) . c.
Definition 2. Let u and v be nodes in G and s an integer where
a) Define '(u, min{d(p)|for every path u v
V in G.
s
in
G such that
For an integer s, the value '(u, v) is the minimum delay
count of all the paths from u to v. The value 7
s
is the
maximum computation time among all these paths from u to
v, where the delay counts are equal to '(u ,v) s. The paths
V such that
s
7 are
called critical paths. The preprocessing algorithm described
in Subsection 5.2 computes '(u, v) and 7 # !
s
u and v in V and every 0 . s < f.
THEOREM 3. Let t, d) be a DFG, c a cycle period, and f
an unfolding factor. Then, &(G f ) . c if and only if, for all
nodes u and v in V and for all s where
s
PROOF. To prove the only if part by contradiction, we assume
and that there exist u, v - V and s -
[0, f) such that '(u, v)
s
p be a critical path u v
V with
s
7 . Thus, there exists a path p in G such
that d(p) < f and t(p) > c. From Lemma 2.2, we know
&(Gf) > c. This is a contradiction.
Now, we prove the if part. Assume that for all u, v -
V and for all s where
s
. Under this assumption, we claim that,
for every path p in G, if d(p) < f, then t(p) . c, which implies
V be a path in G. If p is a critical
path, the claim is true. Otherwise, we want to show
that d(p) . f or t(p) . c. In case that d(p) . '(u, v) + f, we
know d(p) . f since '(u, v) . 0. Otherwise,
is not a critical path,
we have t p u v
s
7 . From the assumption, we
know that either d(p) . f or t(p) . c. Therefore, the claim
is proved.
The next theorem gives us the necessary and sufficient
conditions for a retiming r with &(G r,f ) . c in terms of ' and
s . From this theorem, we are able to construct a simple
LP form for retiming and unfolding.
THEOREM 4. Let t, d) be a DFG, c a cycle period and f
an unfolding factor. The following two statements are
equivalent:
a) r is a retiming on G such that &(G r,f ) . c.
b) for all nodes u and v in V and for all s where
s
PROOF.
s
similarly defined on G r .
First, we prove that the effect of retiming on the functions
'(u, v) and 7 # !
s
similar to that on the
functions d and t, i.e., ' r (u,
r
theorem is easily
derived from Theorem 3 on the retimed graph G r .
THEOREM 5. Let t, d) be a DFG, c a cycle period, and f
an unfolding factor. Then, r is a legal retiming on G such
that &(G r,f ) . c if and only if
e
# of G, and
s
PROOF. The function r is a legal retiming if and only if d r (e) . 0
for every e in G. Since d r r is a legal
retiming if and only if r(v) # r(u) . d(e) for every
e
# . The second inequality comes from Theorem 4.+
For a particular cycle period c and an unfolding factor f,
this theorem gives a simple LP form to find a legal retiming
r, if it exists, such that &(G r,f ) . c. This LP form can be easily
solved by single-source shortest path algorithms. Assume
that the preprocessing of computing ' and 7 # !
s for a
given unfolding factor f is done. The number of values
s
In time O(f |V| 2 ), we can generate
an LP form for a given cycle period c by scanning the values
of
s
the inequalities which have the
same left-hand side are covered by the one which has the
8 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 8, NO. 12, DECEMBER 1997
F:\LIBRARY\TRANS\PRODUCTION\TPDS\2-INPROD\100505\100505_1.DOC regularpaper97.dot AB 19,968 10/22/97 9:37 AM 8 / 9
smallest value on the right-hand side, we obtain an LP form
which has at most |V| 2 inequalities. Thus, the legal retiming
can be found in time O(|V| 3 ) by Bellman-Ford algorithm
for shortest-path problems.
It is easy to observe that the cycle period of G r,f is a value
of
s
v, and s. We can sort the set of
values
s
every u and v - G and s - [0, f)}, and
perform binary search on this set of values in order to find
the minimum cycle period of G r,f over all retiming r. There-
fore, the legal retiming such that &(G r,f ) is the minimum
that can be found in time O((f|V|
From the definitions, the functions ' and 7 # !
s are independent
of the unfolding factor. Let F be the maximum
value of unfolding factors under resource consideration.
After we perform the preprocessing step for the maximum
unfolding factor F once in time O(F
|V|)), the values of MCP(f) for any f, f . F, can be found
by using our retiming algorithm without further preprocessing
for each f.
Although the minimum cycle period MCP(f) is an increasing
function, the behavior of the minimum iteration
period MIP(f), which is MCP(f)/f, is hard to characterize. In
order to find the minimum iteration period MIP(f) for every
f . F, we need to compute the minimum cycle period
MCP(f) for every f and then find the one such that MCP(f)/f
is minimized. Thus, the minimum of the minimum iteration
period MIP(f) for all f, where f . F, can be found in time
5.2 Preprocessing Algorithm
The function ' can be easily computed by all-pair shortest
path algorithms in time O(|V| 3 ). We first compute the following
two functions, D f and T f , defined on the unfolded
graph G , and then show how to compute the function 7 # !
s
from ', D , and T f .
DEFINITION 3. Let be an unfolded graph, u i and
nodes in G , and s an integer where 0 . s < f. The function
D is a function from V f - V to nonnegative integers,
and T f is a function from V f - V f to positive integers.
a) Define D f
)|for every path u v
in G f }.
f
)|for every path u v
in G f such that d f (p f
(When there is no path u v
undefined and
With length measure (d f (p f path, the functions
D f and T can be computed in time O(|V| 3 f 3 ) by the Floyd-Warshall
algorithm for all-pairs shortest path problems [13].
The following lemma shows the relation between functions
' and D f .
LEMMA 5.1. Let u and v be two nodes in V, f an unfolding factor,
and s an integer where 0 . s < f. If there exists a path
V such that
f
PROOF. First, we show the following property of D :
# . (The detailed
proof appears in [9], [10].) Assume that there exists a
path
V such that
1b, we know the corresponding path u v
f
in G f has delay d p
f
' . Thus,
f
From the above property of D f , we have
# .
Thus, the lemma is proved.
The following theorem shows us how to generate
s
, ) from '(u, v), D f (u, v), and T (u, v).
THEOREM 6. Consider two nodes u and v in G. For every s where
s
f
f
otherwise
We rewrite the definition of 7
s
in terms of
the paths in the unfolded graph as
s
in G such that d p u v s f
' }. The theorem
follows. (The detailed proof appears in [9], [10].)
The function ' can be easily computed by all-pair shortest
path algorithms in time O(|V| 3 ). In time O(|V| 2 f), we
can construct 7 # !
s
every u and v from T f by using
the above theorem.
6 CONCLUDING REMARKS
In this paper, we study some fundamental theorems about
the combination of two useful techniques: retiming and
unfolding. This understanding gives us more insight for
many problems in which retiming and unfolding can both
be applied, such as multiprocessor scheduling and data-path
design in VLSI computer-aided design. We believe
that these results can also be applied to other applications.
CHAO AND SHA: SCHEDULING DATA-FLOW GRAPHS VIA RETIMING AND UNFOLDING 9
F:\LIBRARY\TRANS\PRODUCTION\TPDS\2-INPROD\100505\100505_1.DOC regularpaper97.dot AB 19,968 10/22/97 9:37 AM 9 / 9
One interesting result shows that unfolding before retiming
or after retiming has no effect on the iteration period.
Therefore, we do not need to unfold DFG first to obtain re-
sults; instead, we can do operations directly on the original
DFG. We present an efficient algorithm for finding the minimum
iteration period from an unfolding factor f which runs
in time O((f|V| retiming.
When we consider the unit-time DFG, which is applicable
to RISC multiprocessors, software pipelining, unit-time parallel
pipelines, etc., more surprising results are obtained. For any
pair of cycle period c and unfolding factor f, as long as c/f is no
less than the iteration bound %(G), there exists such a sched-
ule, i.e., there exists a retiming r to derive this schedule. The
retiming algorithm runs in time O(|V||E|) The result in
Theorem 2 is generalized in [8] to obtain rate-optimal schedules
for general-time DFGs under various models.
After we understood the fundamental properties in this
paper, we successfully applied these results to a scheduling
problem with resource constraints in [14]. One important
open question is to measure the minimum iteration period
under resource constraints for an unfolding factor from the
results without resource constraints. These fundamental
properties and best schedules can be used to derive approximation
algorithms.

ACKNOWLEDGMENTS

This work was supported in part by U.S. National Science
Foundation Grant MIP-8912100, U.S. Army Research Of-
fice-Durham Grant DAAL03-89-K-0074, and DARPA/ONR
contract N00014-88-K-0459.



--R

"Retiming Synchronous Circuitry,"
"Retiming and Unfolding Data-Flow Graphs,"
"Data Flow Program Graphs,"
"Static Rate-Optimal Scheduling of Iterative Data-Flow Programs Via Optimum Unfolding,"
"Unfolding and Retiming Data-Flow DSP Programs for RISC Multiprocessor Scheduling,"
"Unfolding and Retiming for High-Level DSP Synthesis,"
"A Systematic Approach for Design of Digital-Serial Signal Processing Architectures,"
"Static Scheduling for Synthesis of DSP Algorithms on Various Models,"
"Scheduling Data-Flow Graphs Via Retiming and Unfolding,"
"Scheduling and Behavioral Transformations for Parallel Systems,"
"The Maximum Sampling Rate of Digital Filters under Hardware Speed Constraints,"
Data Structures and Network Algorithms.
Networks and Matroids.
"Rotation Scheduling: A Loop Pipelining Algorithm,"
--TR

--CTR
Timothy W. O'Neil , Edwin H.-M. Sha, Combining extended retiming and unfolding for rate-optimal graph transformation, Journal of VLSI Signal Processing Systems, v.39 n.3, p.273-293, March 2005
Timothy W. O'Neil , Edwin H.-M. Sha, Combining Extended Retiming and Unfolding for Rate-Optimal Graph Transformation, Journal of VLSI Signal Processing Systems, v.39 n.3, p.273-293, March     2005
Qingfeng Zhuge , Bin Xiao , Zili Shao , Edwin H.-M. Sha , Chantana Chantrapornchai, Optimal code size reduction for software-pipelined and unfolded loops, Proceedings of the 15th international symposium on System Synthesis, October 02-04, 2002, Kyoto, Japan
M. Jacome , G. de Veciana , C. Akturan, Resource constrained dataflow retiming heuristics for VLIW ASIPs, Proceedings of the seventh international workshop on Hardware/software codesign, p.12-16, March 1999, Rome, Italy
Qingfeng Zhuge , Zili Shao , Bin Xiao , Edwin H.-M. Sha, Design space minimization with timing and code size optimization for embedded DSP, Proceedings of the 1st IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, October 01-03, 2003, Newport Beach, CA, USA
Qingfeng Zhuge , Bin Xiao , Edwin H.-M. Sha, Code size reduction technique and implementation for software-pipelined DSP applications, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.4, p.590-613, November
Han-Saem Yun , Jihong Kim, Power-aware modulo scheduling for high-performance VLIW processors, Proceedings of the 2001 international symposium on Low power electronics and design, p.40-45, August 2001, Huntington Beach, California, United States
Meikang Qiu , Zhiping Jia , Chun Xue , Zili Shao , Edwin H.-M. Sha, Voltage Assignment with Guaranteed Probability Satisfying Timing Constraint for Real-time Multiproceesor DSP, Journal of VLSI Signal Processing Systems, v.46 n.1, p.55-73, January   2007
Dongming Peng , Mi Lu, On exploring inter-iteration parallelism within rate-balanced multirate multidimensional DSP algorithms, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.13 n.1, p.106-125, January 2005
Michael I. Gordon , William Thies , Saman Amarasinghe, Exploiting coarse-grained task, data, and pipeline parallelism in stream programs, ACM SIGOPS Operating Systems Review, v.40 n.5, December 2006
Han-Saem Yun , Jihong Kim , Soo-Mook Moon, Time optimal software pipelining of loops with control flows, International Journal of Parallel Programming, v.31 n.5, p.339-391, October
Chiang , Lan-Rong Dung, Verification method of dataflow algorithms in high-level synthesis, Journal of Systems and Software, v.80 n.8, p.1256-1270, August, 2007
Karam S. Chatha , Ranga Vemuri, Hardware-Software partitioning and pipelined scheduling of transformative applications, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.10 n.3, p.193-208, June 2002
retiming;loop parallelization;data-flow graphs;parallel processing;scheduling;unfolding