Circuit Retiming Applied to Decomposed Software Pipelining.
AbstractThis paper elaborates on a new view on software pipelining, called decomposed software pipelining, and introduced by Gasperoni and Schwiegelshohn, and by Wang, Eisenbeis, Jourdan, and Su. The approach is to decouple the problem into resource constraints and dependence constraints. Resource constraints management amounts to scheduling an acyclic graph subject to resource constraints for which an efficiency bound is known, resulting in a bound for loop scheduling. The acyclic graph is obtained by cutting some particular edges of the (cyclic) dependence graph. In this paper, we cut edges in a different way, using circuit retiming algorithms, so as to minimize both the longest dependence path in the acyclic graph, and the number of edges in the acyclic graph. With this technique, we improve the efficiency bound given for Gasperoni and Schwiegelshohn algorithm, and we reduce the constraints that remain for the acyclic problem. We believe this framework to be of interest because it brings a new insight into the software problem by establishing its deep link with the circuit retiming problem.
Introduction
OFTWARE PIPELINING is an instruction-level loop
scheduling technique for achieving high performance on
processors such as superscalar or VLIW (Very Long Instruction
Word) architectures. The main problem is to
cope with both data dependences and resource constraints
which make the problem NP-complete in general. The software
pipelining problem has motivated a great amount of
research. Since the pioneering work of Rau and Glaeser [1],
several authors have proposed various heuristics [2], [3], [4],
[5], [6] in various frameworks. An extended survey on software
pipelining is provided in [7].
Recently, a novel approach for software pipelining, called
decomposed software pipelining, has been proposed simultaneously
by Gasperoni and Schwiegelshohn [8], and by
Wang, Eisenbeis, Jourdan, and Su [9]. The idea is to decompose
the NP-complete software pipelining problem into
two subproblems: a loop scheduling problem ignoring resource
constraints, and an acyclic graph scheduling prob-
lem, for which efficient techniques (such as list scheduling
for example) are well known. Although splitting the problem
in two subproblems is clearly not an optimal strat-
egy, Wang, Eisenbeis, Jourdan and Su have demonstrated,
through an experimental evaluation on a few loops from
the Livermore Benchmark Kernels, that such an approach
P.-Y. Calland is supported by a grant of R'egion Rh"one-Alpes. A.
Darte and Y. Robert are supported by the CNRS-ENS Lyon-INRIA
project ReMaP.
The authors are with Laboratoire LIP, URA CNRS 1398, Ecole
Normale Sup'erieure de Lyon, F-69364 LYON Cedex 07, e-mail:
[Pierre-Yves.Calland,Alain.Darte,Yves.Robert]@ens-lyon.fr
is very promising with respect to time efficiency and space
efficiency.
In both approaches, the technique is to pre-process the
loop data dependence graph (which may include cycles) by
cutting some dependence edges. After the pre-processing,
the modified graph becomes acyclic and classical scheduling
techniques can be applied on it to generate the "pattern"
(or "kernel") of a software pipelining loop. However, the
way edges are cut is ad-hoc in both cases, and no general
framework is given that explains which edges could and/or
should be cut. The main contribution of this paper is to
establish that this pre-processing of the data dependence
graph has a deep link with the circuit retiming problem.
The paper is organized as follows: in Section II, we described
more precisely our software pipelining model. In
Section III, we recall the main idea of decomposed software
pipelining: we illustrate this novel technique through
Gasperoni and Schwiegelshohn algorithm, and we show
that decomposed software pipelining can be re-formulated
in terms of retiming algorithms that are exactly the tools
needed to perform the desired edges cut. Then, we demonstrate
the interest of our framework by addressing two optimization
problems:
ffl In Section IV, we show how to cut edges so that the
length of the longest path in the acyclic graph is minimized.
With this technique, we improve the performance bound
given for Gasperoni and Schwiegelshohn algorithm.
ffl In Section V, we show how to cut the maximal number
of edges, so as to minimize the number of constraints
remaining when processing the acyclic graph. This criteria
is not taken into account, neither in Gasperoni and
Schwiegelshohn algorithm, nor in Wang, Eisenbeis, Jourdan
and Su algorithm.
Finally, we discuss some extensions in Section VI. We
summarize our results and give some perspectives in Section
VII.
II. A simplified model for the software
pipelining problem
We first present our assumptions before discussing their
motivations.
A. Problem formulation
In this paper, we consider a loop composed of several
operations that are to be executed a large number of times
on a fine-grain architecture. We assume both resource
constraints and dependence constraints, but, compared to
more general frameworks, we make the following simplifying
hypotheses:
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. XX, NO. Y, MONTH 1996
Resources. The architecture consists in p identical, non
pipelined, resources. The constraint is that, in each cy-
cle, the same resource cannot be used more than once.
Dependences. Dependences between operations are captured
by a doubly weighted graph ffi). V is the
set of vertices of G, one vertex per operation in the loop.
E is the set of edges in G. For each edge e in E, d(e) is
a nonnegative integer, called the dependence distance. For
each vertex u in V , ffi(u) is a nonnegative integer, called the
delay. ffi and d model the fact that for each edge
the operation v at iteration i has to be issued at least ffi(u)
cycles after the start of the operation u at iteration
We assume that the sum of dependence distances along any
cycle is positive.
These hypotheses are those given by Gasperoni and
Schwiegelshohn in the non pipelined case. Before discussing
the limitations of this simplified model, let us illustrate
the notion of operations, iterations, delays, and
dependence distance, with the following example. We will
work on this example throughout the paper.
ENDDO
The loop has 6 operations (A, B, C, D, E, and F ) and
N iterations, each operation is executed N times. N is
a parameter, of unknown value, possibly very large. The
associated graph G is given in Figure 1. Delays are depicted
in square boxes, for example the delay of operation F is 10
times greater than the delay of operation A. Dependence
distances express the fact that some computations must be
executed in a specified order so as to preserve the semantics
of the loop. For example, operation A at iteration k writes
a(k), hence it must precede computation B at iteration
which reads this value. This constraint is captured
by the label equal to 2 associated to the edge (A; B) in the
dependence graph of Figure 1.
A
F
121414Fig. 1. An example of dependence graph G
The software pipelining problem is to find a schedule oe
that assigns an issue time oe(u; for each operation instance
operation u at iteration k). Each edge in
the graph gives rise to a constraint for scheduling:
Valid schedules are those schedules satisfying both dependence
constraints (expressed by Equation 1) and resource
constraints. Because of the regular structure of the software
pipelining problem, we usually search for a cyclic (or
modulo) scheduling oe: we aim at finding a nonnegative integer
(called the initiation interval of oe) and constants
c u such that oe(u;
Because the input loop is supposed to execute many iterations
(N is large), we focus on the asymptotic behavior
of oe. The initiation interval  is a natural performance estimator
of oe, as 1= measures oe's throughput. Note that if
the reduced dependence graph G is acyclic and if the target
machine has enough processors, then  can be zero (this
type of schedule has infinite throughput).
A variant consists in searching for a nonnegative rational
a=b and to let oe(u; (with rational
constants c u ). This amounts to unroll the input loop by a
factor b. We come back on this variant in Section VI. Note
also that rational cyclic schedules are dominant in the case
of unlimited resources [4].
B. Limitations of the model
Compared to more sophisticated models, where more
general programs may be handled (such as programs with
conditionals) and where more accurate architecture description
can be given, our framework is very simple and
may seem unrealistic. We (partly) agree but we would like
to raise the following arguments:
Delays. In many frameworks, the delay is defined on edges
and not on vertices as in our model. We chose the latter for
two reasons. First, we want to compare our technique to
Gasperoni and Schwiegelshohn algorithm which uses delays
on vertices. Second, we use graph retiming techniques that
are also commonly defined with delays on vertices. How-
ever, we point out that retiming in a more general model
is possible, but technically more complex. See for example
[10, Section 9].
Resources. Our architecture model, with non pipelined and
identical resources, is very simple. The main reason for
this restricted hypothesis is that we want to demonstrate,
from a theoretical point of view, that our technique allows
to derive an efficiency bound, as for Gasperoni and
Schwiegelshohn algorithm.
From a practical point of view, our technique can still be
used, even for more sophisticated resource models. Indeed,
the retiming technique that we use is independent of the
architecture model, and can be seen as a pre-loop transfor-
mation. Resource constraints are taken into account only
in the second phase of the algorithm: additional features
on the architecture can then be considered when scheduling
the acyclic graph obtained after retiming. In particular,
such a technique can be easily integrated, regardless of the
architecture details, in a compiler that has an instruction
scheduler.
Extensions of the model. Decomposed software pipelining
is still a recent approach for software pipelining. It has thus
been studied first from a theoretical point of view, and only
on restricted models. This is also the case in this paper.
The whole problem is (not yet) well understood enough
P.-Y. CALLAND, A. DARTE AND Y. ROBERT: CIRCUIT RETIMING APPLIED TO DECOMPOSED SOFTWARE PIPELINING 3
to allow more general architecture features be taken into
account. However, we believe that our new view on the
problem, in particular the use of retiming for controlling
the structure of the acyclic graph, will lead in the future to
more accurate heuristics on more sophisticated architecture
models.
III. Going from cyclic scheduling to acyclic
scheduling
Before going into the details of Gasperoni and
Schwiegelshohn heuristic (GS for short), we recall some
properties of cyclic schedules, and the main idea of decomposed
software pipelining, so as to make the rest of the
presentation clearer.
A. Some properties of cyclic scheduling
Consider a dependence graph d) and a
cyclic schedule oe, oe(u; that satisfies both
dependence constraints and resource constraints. Such a
cyclic schedule is periodic, with period : the computation
scheme is reproduced every  units of time. More pre-
cisely, if instance (u; is assigned to begin at time t, then
instance will begin at time t + . Therefore, we
only need to study a slice of  clock cycles to know the
behavior of the whole cyclic schedule in steady state.
Let us observe such a slice, e.g. the slice SK from clock
cycle K up to clock cycle (K
enough so that the steady state is reached. Figure 2 depicts
the steady state of a schedule, for the graph of Figure 1,
with initiation interval
time
resources
A,k
F,k
initiation interval
Fig. 2. Successive slices of a schedule for graph G. Boxes in grey
represent the operation initiated in the same slice SK .
Now, for each perform the Euclidean division of
c u by : c
This means that one and only one instance of operation u
is initiated within the slice SK : it is instance
issued r u clock cycles after the beginning of the slice. The
quantities r u and q u are similar to the row and column
numbers introduced in [9].
If the schedule is valid, both resource constraints and dependence
constraints are satisfied. Dependence constraints
can be separated in two types depending on how they are
either two dependent operation instances are initiated
in the same slice SK (type 1) or they are initiated
in two different slices (type 2). Of course, the partial dependence
graph induced by type 1 constraints is acyclic,
because type 1 dependences impose a partial order on the
operations, according to the order in which they appear
within the slice. In Figure 2, arrows represent
pendences. All other dependences (not depicted in the fig-
are type 2 dependences.
The main idea of Gasperoni and Schwiegelshohn algorithm
(GS), and more generally of decomposed software
pipelining, is the following. Assume that we have a valid
cyclic schedule of period  0 for a given number p 0 of pro-
cessors, and that we want to deduce a valid schedule for
a smaller number p of processors. A way of building the
new schedule is to keep the same slice structure, i.e. to
keep the same operation instances within a given slice. Of
course we might need to increase the slice length to cope
with the reduction of resources. In other words, we have
to stretch the rectangle of size  0 \Theta p 0 to build a rectangle
of size  \Theta p. Using this idea, type 2 dependences will
still be satisfied if we choose  large enough. Only type 1
dependences have to be taken into account for the internal
reorganization of the slice (see Figure 3). But since the
corresponding partial dependence graph is acyclic, we are
brought back to a standard acyclic scheduling problem for
which many theoretical results are known. In particular,
a simple list scheduling technique provides a performance
bound (and the shorter the longest path in the graph, the
more accurate the performance bound).
time
resources
A,k
F,k
time
A,k
Fig. 3. Two different allocations of a slice of graph G (p
Once this main principle is settled, there remain several
open questions:
1. How to choose the initial scheduling? For which  0 ?
2. How to choose the reference slice? There is no reason a
priori to choose a slice beginning at a clock cycle congruent
to 0 modulus  0 .
3. How to decide that an edge is of type 1, hence to be
considered in the acyclic problem?
These three questions are of course linked together. Intu-
itively, it seems important to (try to) minimize both
ffl the length of the longest path in the acyclic graph, which
should be as small as possible as it is tightly linked to the
performance bound obtained for list scheduling, and
ffl the number of edges in the acyclic graph, so as to reduce
the dependence constraints for the acyclic scheduling
problem.
4 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. XX, NO. Y, MONTH 1996
We will give a precise formulation to these questions and
give a solution. Beforehand, we review the choices of GS.
B. The heuristic of Gasperoni and Schwiegelshohn
In this section we explain with full details the GS heuristic
[8]. The main idea is as outlined in the previous section.
The choice of GS for the initial scheduling is to consider
the optimal cyclic scheduling for an infinite number of processors
constraints.
B.1 Optimal schedule for unlimited resources
Consider the cyclic scheduling problem d)
without resource constraints
Let  be a nonnegative integer. Define from G an edge-weighted
graph G 0
ffl Vertices of G 0
to V a new vertex s:
ffl Edges of G 0
an edge from s to all other ver-
tices:
ffl Weight of edges of G 0
We have the following well-known result:
Lemma 1:  is a valid initiation interval , G 0
has no
cycle of positive weight. Furthermore, if G 0
has no cycle
of positive weight, and if t(s; u) denotes the length of the
longest path, in G 0
, from s to u, then oe(u;
is a valid cyclic schedule.
Lemma 1 has two important consequences:
ffl First, given an integer , it is easy to determine if  is a
valid initiation interval and if yes, to build a corresponding
cyclic schedule by applying Bellman-Ford algorithm [11] on
.
ffl The optimal initiation interval 1 is the smallest non-negative
integer  such that G 0
has no positive cy-
cle. Therefore,
maxfd
C cycle of Gg otherwise. Furthermore, a binary
search combined with Bellman-Ford algorithm computes
1 in polynomial time.
B.2 Algorithm GS for p resources
As said before, in the case of p identical processors,
the algorithm consists in the conversion of the dependence
graph G into an acyclic graph G a . G a is obtained by deleting
some edges of G. As initial scheduling, GS takes the
optimal scheduling with unlimited resources
As reference slice, GS takes a slice starting at a clock cycle
congruent to 0 modulus 1 , i.e. a slice from clock cycle
K1 up to clock cycle (K This amounts to
decomposing t(s; u) into
In other words r Consider an edge
In the reference slice, the operation instance
, the
operation instance of v which is performed within the reference
slice, namely (v; started before the end
of the operation (u; K \Gamma q u ). Hence this operation instance
not the one that depends upon completion
of In other words, K \Gamma q
The two operations in dependence through edge e are not
initiated in the same slice. Edge e can be safely considered
as a type 2 edge, and thus can be deleted from G. This is
the way edges are cut in GS heuristic 1 . We are led to the
following algorithm:
Algorithm 1: (Algorithm GS)
1. Compute the optimal cyclic schedule oe 1 for unlimited
resources.
2. Let be an edge of G. Then e will be deleted
from G if and only if
This provides the acyclic graph G a .
3. (a) Consider the acyclic graph G a where vertices are
weighted by ffi and edges represent task dependences, and
perform a list scheduling oe a on the p processors.
(b) Let be the makespan (i.e.
the total execution time) of the schedule for G a .
4. For all
t(s; u)
is a valid cyclic schedule.
The correctness of Algorithm GS can be found in [8]. It can
also be deduced from the correctness of Algorithm CDR
(see Section IV-B.1).
B.3 Performances of Algorithm GS
GS gives an upper bound to the initiation interval  obtained
by Algorithm 1. Let  opt be the optimal (smallest)
initiation interval with p processors. The following inequality
is established:
where \Phi is the length of the longest path in G a . Moreover,
owing to the strategy for cutting edges, \Phi
where in [8]). This
implies which leads to
opt
opt
GS is the first guaranteed algorithm. We see from equation
(2) that the bound directly depends upon \Phi, the length
of the longest path in G a .
Example. We go back to our example. Assume
processors. The graph G is the graph of Figure 1. We
have In Figure 4(a), we depict the graph G 0 12 .
The different values t(s; u) for all are given in circles
on the figure. The schedule oe 1 (u;
already represented in Figure 2: 4 processors are needed.
1 However, this is not the best way to determine type 2 edges. See
Section III-C.
P.-Y. CALLAND, A. DARTE AND Y. ROBERT: CIRCUIT RETIMING APPLIED TO DECOMPOSED SOFTWARE PIPELINING 5

Figure

4(b) shows the acyclic graph G a obtained by cutting
edges
r Finally, Figure 4(c) shows a possible
schedule of operations provided by a list scheduling.
The initiation interval of this solution is
A
F
A
A,k
time
resources
(a)
(b)
(c)
Fig. 4. (a): The graph G 0(b): The acyclic graph Ga
corresponding list scheduling allocation:
C. Cutting edges by retiming
Let us summarize Algorithm GS as follows: first compute
the values t(s; u) in G 0
1 to provide the optimal scheduling
without resource constraints oe 1 . Then take a reference
slice starting at clock cycle 0
Finally, delete from G some edges that necessarily correspond
to dependences between different slices: only those
edges are removed by
algorithm GS.
However, edges that correspond to dependences between
different slices are those such that q u
within the reference slice, the scheduled computation instances
are
Therefore, the computation (v; depends
upon performed in the same slice iff
wise, it is performed in a subsequent slice, and in this case
Let us check this mathematically, for an arbitrary slice.
Consider a valid cyclic scheduling oe(u; (with
6= 0), and let c
where t 0 is given. For each edge the dependence
constraint is satisfied, thus r u
r
Finally, dividing by , we get
Furthermore, if q v then the dependence
constraints directly writes r u . We thus have:
ae
Therefore, the condition for cutting edges corresponding to
dependences between different slices (i.e. those we called
Furthermore, if an edge is cut by GS, then
it is also cut by our new rule. We are led to a modified
version of GS which we call mGS. Since we cut more edges
in mGS than in GS, the acyclic graph mG a obtained by
mGS contains a subset of the edges of the acyclic graph
G a . See

Figure

5 to illustrate this fact.
A
A,k
time
resources
(a) (b)
Fig. 5. (a): The acyclic graph provided by Algorithm mGS
(b): A corresponding list scheduling allocation:
Actually, we need neither an initial ordering nor a reference
slice any longer. What we only need is to determine
a function
Then, we define the acyclic graph mG a as follows: an edge
in mG a iff q(v)
Clearly, mG a is acyclic (assume there is a cycle, and sum
up the quantities q(v) q(u) on this cycle to get a
contradiction). Finally, given mG a , we list schedule it as a
DAG whose vertices are weighted by the initial ffi function.
Such a function q is called a retiming in the context
of synchronous VLSI circuits [10]. Given a graph
d), q performs a transformation of G into a new
graph G d q ) where d q is defined as follows: if
is an edge of E then
d q
This transformation can be interpreted as follows: if d(e)
represents the number of "registers" on edge e, a retiming
q amounts to suppress q(u) registers to each edge leaving
u, and to add q(v) registers to each edge entering v. A
retiming is said valid if for each edge e of E, d q (e)  0 (at
least one register per edge in G q , see Equation 3). Edges
such that d q are edges "with no register". Note that
we assumed that the sum of the d(e) on any cycle of G is
positive: using VLSI terminology, we say G is synchronous.
We are now ready to formulate the problem. Recall that
our goal was to answer the following two questions:
ffl How to cut edges so as to obtain an acyclic graph G a
whose longest path has minimal length?
ffl How to cut as many edges as possible so that the number
of dependence constraints to be satisfied by the list-
scheduling of G a is minimized?
6 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. XX, NO. Y, MONTH 1996
using our new formulation, we can state our objectives
more precisely in terms of retiming:
Objective 1 Find a retiming q that minimizes the longest
path in mG a , i.e. in terms of retiming, that minimizes the
clock period \Phi of the retimed graph.
Objective 2 Find a retiming q so that the number of edges
in mG a is minimal, i.e. distribute registers so as to leave
as few edges with no register as possible.
In Section IV, we show how to achieve the first objective.
There are several possible solutions, and in Section V, we
show how to select the best one with respect to the second
objective, and we state our final algorithm. We improve
upon GS for two reasons: first we have a better bound,
and second we cut more edges, hence more freedom for the
list scheduling.
IV. Minimizing the longest path of the acyclic
graph
There are well-known retiming algorithms that can be
used to minimize the clock period of a VLSI circuit, i.e.
the maximal weight (in terms of delay) of a path with no
register. We first recall these algorithms, due to Leiserson
and Saxe [10], then we show how they can be applied to
decomposed software pipelining.
A. Retiming algorithms
We first need some definitions. We denote by u P
a path P of G from u to v, by d(P
e2P d(e) the
sum of the dependences of the edges of P , and by ffi(P
v2P ffi(v) the sum of the delays of the vertices of P . We
define D and \Delta as follows:
D and \Delta are computed by solving an all-pairs shortest-path
algorithm on G where edge u e
weighted with
the pair (d(e); \Gammaffi(u)). Finally, let
path of G; d(P
\Phi(G) is the length of the longest path of null weight in G
(and is called the clock period of G in VLSI terminology).
Theorem 1: (Theorem 7 in [10]) Let d) be
a synchronous circuit, let  be an arbitrary positive real
number, and let q be a function from V to the integers.
Then q is a legal retiming of G such that \Phi(G q )   if and
only if
1. for every edge u e
2.
that \Delta(u; v) ? .
Theorem 1 provides the basic tool to establish the following
algorithm (Algorithm 2) that determines a retiming
such that the clock period of the retimed graph is minimized

Algorithm 2: (Algorithm OPT1 in [10])
1. Compute D and \Delta (see Algorithm WD in [10]).
2. Sort the elements in the range of \Delta.
3. Binary search among the elements \Delta(u; v) for the minimum
achievable clock period. To test whether each potential
clock period  is feasible, apply the Bellman-Ford
algorithm to determine whether the conditions in Theorem
1 can be satisfied.
4. For the minimum achievable clock period found in step
3, use the values for the q(v) found by the Bellman-Ford
algorithm as the optimal retiming.
This algorithm runs in O(jV j 3 log jV j), but there
is a more efficient algorithm whose complexity is
O(jV jjEj log jV j), which is a significant improvement for
sparse graphs. It runs as the previous algorithm except in
step 3 where the Bellman-Ford algorithm is replaced by the
following algorithm:
Algorithm 3: (Algorithm FEAS in [10]) Given a synchronous
d) and a desired clock period
, this algorithm produces a retiming q of G such that G q
is a synchronous circuit with clock period \Phi  , if such a
retiming exists.
1. For each vertex set q(v) to 0.
2. Repeat the following
(a) Compute graph G q with the existing values for q.
(b) for any vertex v 2 V compute \Delta 0 (v) the maximum
sum ffi(P ) of vertex delays along any zero-weight directed
path P in G leading to v. This can be done in O(jEj).
(c) For each vertex v such that \Delta 0 (v) ? , set q(v) to
3. Run the same algorithm used for step 2(b) to compute
\Phi. If \Phi ?  then no feasible retiming exists. Otherwise, q
is the desired retiming.
B. A new scheduling algorithm: Algorithm CDR
We can now give our new algorithm and prove that both
resource and dependence constraints are met.
Algorithm 4: (Algorithm CDR) Let d) be a
dependence graph.
1. Find a retiming q that minimizes the length \Phi of the
longest path of null weight in G q (use Algorithm 2 with
the improved algorithm for step 3).
2. Delete edges of positive weight, or equivalently keep
edges
edges with no register). By this way, we obtain an acyclic
graph G a .
3. Perform a list scheduling oe a on G a and compute
4. Define the cyclic schedule oe by:
Note that the complexity of Algorithm CDR is determined
by Step 1 whose complexity is O(jV jjEj log(jV j)).
In comparison, the complexity of Algorithm GS is
O(jV jjEj log(jV jffi max )). The difference comes from the fact
that \Phi opt can be searched among the jV j 2 values \Delta(u; v)
whereas 1 is searched among all values between 0 and
algorithms have similar
complexities.
P.-Y. CALLAND, A. DARTE AND Y. ROBERT: CIRCUIT RETIMING APPLIED TO DECOMPOSED SOFTWARE PIPELINING 7
B.1 Correctness of Algorithm CDR
Theorem 2: The schedule oe obtained with Algorithm
CDR meets both dependence and resource constraints.
Proof: Resource constraints are obviously met because
of the list scheduling and the definition of , which
ensures that slices do not overlap. To show that dependence
constraints are satisfied for each of E, we
need to verify
, oe a (u)
, oe a
On one hand, suppose that e is not deleted, i.e. e 2 G a .
It is equivalent to say that the weight of e after the retiming
is equal to zero: q(v) since oe a is a
schedule for G a :
oe a (u)
Thus, inequality (4) is satisfied.
On the other hand, if e is deleted, then
. But, by
definition of  we have
oe a (u)
Thus, inequality (4) is satisfied.
B.2 Performances of Algorithm CDR
Now, we use the same technique as in [8] in order to show
that our algorithm is also guaranteed and we give an upper
bound for the initiation interval  that is smaller than the
bound given for Algorithm GS.
Theorem 3: Let G be a dependence graph, \Phi opt the minimum
achievable clock period for G,  the initiation interval
of the schedule generated by Algorithm CDR when p processors
are available, and  opt the best possible initiation
interval for this case. Then
opt
'' \Phi opt
opt
Proof: By construction, \Phi opt is the length of the
longest path in G a , thus with the same proof technique as
in [8], i.e a list scheduling technique, we can prove that
which leads to the desired inequality.
Now we show that the bound obtained for Algorithm
CDR (Theorem 3) is always better than the bound for Algorithm
GS (see Equation 2). This is a consequence of the
following lemma:
Lemma 2: 1  \Phi opt
Proof: Let us apply Algorithm CDR with unlimited
resources. For that, we define a retiming q such that
and we define the graph G a by deleting from
G all edges e such that d q (e) ? 0. Then, we define a schedule
for G a with unlimited resources by oe a
P path of G a leading to ug. The makespan of oe a is \Phi opt by
construction. Finally, we get a schedule for G by defining
tion, the smallest initiation interval for
Now, consider an optimal cyclic schedule oe for unlimited
resources, oe(u; as defined in Section III-
B.1. Let
As
proved in Section III-C, q defines a valid retiming for G, i.e.
for all edges
G a by deleting from G all edges e such that d q (e) ? 0
(as in Algorithm mGS). Let P be any path in G a ,
Summing up these
By construction, \Phi(G q ) is the length of the longest path
in G a , thus \Phi(G q Finally, we have
\Phi opt  \Phi(G q ), hence the result.
Theorem 4: The performance upper bound given for Algorithm
CDR is better than the performance upper bound
given for Algorithm GS.
Proof: This is easily derived from the fact that \Phi opt
shown by Lemma 2.
Note: this bound is a worst case upper bound for the initiation
interval. It does not prove however that CDR is
always better than GS.
Example. We can now apply Algorithm CDR to our key
example (assume again available processors). \Phi
14 and the retiming q that achieves this clock period is
obtained in two steps by Algorithm 3: q
Figures 6(a), 6(b) and 6(c)
show the successive retimed graphs. Figure 6(d) shows
the corresponding acyclic graph G a and finally, Figure 6(e)
shows a possible schedule of operations provided by a list
scheduling technique, whose initiation interval is
This is better than what we found with Algorithm mGS
(see

Figure

5(b)), and with Algorithm GS (see Figure 4(c)).
B.3 Link between 1 and \Phi opt
As shown in Lemma 2, 1 and \Phi opt are very close. How-
ever, the retiming that can be derived from the schedule
with initiation interval 1 does not permit to define an
acyclic graph with longest path \Phi opt . In other words, looking
for 1 is not the right approach to minimizing the
period of the graph. In this section, we investigate more
deeply this fact, by recalling another formulation of the
retiming problem given by Leiserson and Saxe [10].
Lemma 3: (Lemma 9 in [10]) Let d) be a
synchronous circuit, and let c be a positive real number.
8 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. XX, NO. Y, MONTH 1996
A
F
F
F
(b)
(c)
A
A,k
B,k C,k
time
resources
(d) (e)
Fig. 6. (a): Initial dependence graph G
(b) and (c): Successive steps of retiming used in CDR
Corresponding acyclic graph
corresponding list scheduling allocation:
Then there exists a retiming q of G such that \Phi(G q )   if
and only if there exists an assignment of a real value s(v)
and an integer value q(v) to each vertex v 2 V such that
the following conditions are satisfied:
\Gammas(v)  \Gammaffi(v) for every vertex
s(v)   for every vertex
such that q(u) \Gamma
By letting every vertex u, inequalities
5 are equivalent to:
such that q(u) \Gamma
This last system permits to better understand all the techniques
that we developed previously:
Optimal schedule for unlimited resources. As seen in
Lemma 2, the schedule oe(u;
System 6 with
except the second inequality. We do have r(v)
but not necessarily r(v)
and in this case,
proof).
Algorithm CDR for unlimited resources. By construc-
tion, with the retiming such that \Phi(G q
and System 6 is satisfied with the smallest value
for . Therefore, this technique leads to the better cyclic
schedule with unlimited resources for which the slices do
not overlap (because of the second inequality). It is not
always possible to find 1 this way.
Algorithms CDR and GS for p resources. The schedule
obtained satisfies System 6 with the makespan of
oe a . For CDR, q is the retiming that achieves the optimal
period, whereas for GS, q is the retiming defined from 1
1 c). For CDR, the fourth inequality is satisfied
exactly for all edges
However, for GS, oe is required to satisfy the fourth inequality
for more edges than necessary (actually for all edges
such that r(u)+ ffi(u)  r(v)). Note that for both
algorithms, there are additional conditions imposed by the
resource constraints that do not appear in System 6.
V. Minimizing the number of edges of the
acyclic graph
Our purpose in this section is to find a retimed graph
with the minimum number of null weight edges among all
retimed graphs whose longest path has the best possible
length \Phi opt . Removing edges of non null weight will give
an acyclic graph that matches both objectives stated at the
end of Section III-C.
Example. Consider step 1 of Algorithm CDR in which we
use the retiming algorithm of Leiserson and Saxe [10]. The
final retiming does minimize the length \Phi of the longest
path of null weight, but it does not necessarily minimize the
number of null weight edges. See again our key example,

Figure

6 (c), for which 14. We can apply yet another
retiming to obtain the graph of Figure 7(a):
0, and
A
F
(c)
A
B,k
time
resources
Fig. 7. (a): The final retimed graph
(b): The corresponding acyclic graph
corresponding list scheduling allocation:
The length of the longest path of null weight is still
14, but the total number of null weight edges is smaller.
This implies that the corresponding acyclic graph G a (see

Figure

contains fewer edges than the acyclic graph
of

Figure

6(d) and therefore, is likely to produce a smaller
initiation interval 2 . That is the case in our example: we
find an initiation interval equal to 19 (see Figure 7(c)). It
turns out that  = 19 is the best possible integer initiation
List scheduling a graph which is a subset of another graph will not
always produce a smaller execution time. But intuition shows that it
will in most practical cases (the fewer constraints, the more freedom).
P.-Y. CALLAND, A. DARTE AND Y. ROBERT: CIRCUIT RETIMING APPLIED TO DECOMPOSED SOFTWARE PIPELINING 9
interval with processors: the sum of all operation
delays is 37, and d 37
Recall that a retiming q such that \Phi(G q
integral solution to the following system (see formulation
of Theorem 1):
such that \Delta(u; v) ? \Phi opt
Among these retimings, we want to select one particular
retiming q for which the number of null weight edges in G q
is minimized. This can be done as follows:
Lemma 4: Let d) be a synchronous circuit.
A retiming q such that \Phi(G q and such that the
number of null weight edges in G q is minimized can be
found in polynomial time by solving the following integer
linear program:
min
such that \Delta(u; v) ? \Phi opt
Proof: Consider an optimal integer solution (q; v) to
System 8. q defines a retiming for G with \Phi(G q
since system 7 is satisfied: indeed q(v) \Gamma q(u)+d(e)+v(e)
Note that each v(e) is constrained by only one equation:
1. There are two cases:
ffl The weight of e in G q is null, i.e.
is the only possibility.
ffl The weight of e in G q is positive, i.e. q(v)\Gammaq(u)+d(e)  1
(recall that q and d are integers). In this case, the minimal
value for v is 0.
Therefore, given a retiming q,
e2E v(e) is minimal when
it is equal to the number of null weight edges in G q .
it remains to show that such an optimal integer
solution can be found in polynomial time. For that, we
System 8 in matrix form as minfcx j Ax  bg:
I d
C I d
where C is the transpose of the jV j\ThetajEj-incidence matrix of
G, C 0 is the transpose of the incidence matrix of the graph
whose edges are the pairs (u; v) such that \Delta(u; v) ? \Phi opt
and I d is the jEj \Theta jEj identity matrix.
An incidence matrix (such as C) is totally unimodular
(see [12, page 274]). Then, it is easy to see that A is also
totally unimodular. Therefore, solving the ILP Problem 8
is not NP-complete: System 8 considered as an LP problem
has an integral optimum solution (Corollary 19.1a in [12])
and such an integral solution can be found in polynomial
time (Theorem 16.2 in [12]).
Let us summarize how this refinement can be incorporated
into our software pipelining heuristic: first, we compute
\Phi opt the minimum achievable clock period for G, then
we solve System 8 and we obtain a retiming q. We define
G a as the acyclic graph whose edges have null weight in
the longest path in G a is minimized and the number
of edges in G a is minimized. Finally, we schedule G a as in
Algorithm CDR. We call this heuristic the modified CDR
(or simply mCDR).
Remark: Solving System 8 can be expensive although
polynomial. An optimization that permits reducing the
complexity is to pre-compute the strongly connected components
G i of G and to solve the problem separately for
each component G i . Then, a retiming that minimizes the
number of null weight edges in G q is built by adding suitable
constants to each retiming q i so that all edges that
link different components have positive weights. Future
work will try to find a pure graph-theoretic approach to
the resolution of System 8, so that the practical complexity
of our software pipelining heuristic is decreased.
VI. Load balancing
We have restricted so far initiation intervals to integer
values. As mentioned in Section II, searching for rational
initiation intervals might give better results, but at the
price of an increase in complexity: searching for
b can
be achieved by unrolling the original loop nest by a factor of
b, thereby processing an extended dependence graph with
many more vertices and edges.
In this section, we propose a simple heuristic to alleviate
potential load imbalance between processors, and for which
there is no need to unroll the graph.
Remember the principle of the four previously described
heuristics (GS, mGS, CDR and mCDR). First, an acyclic
graph G a is built from G. Then, G a is scheduled by a
list scheduling technique. This defines the schedule oe a inside
each slice of length  (the initiation interval). Finally,
slices are concatenated, a slice being initiated just after the
completion of the previous one.
The main weakness of this principle is that slices do not
overlap. Since the schedule in each slice has been defined
by an As-Soon-As-Possible (ASAP) list scheduling, what
usually happens is that many processors are idle during the
last time steps of the slice. The idea to remedy this problem
is to try to fill these "holes" in the schedule with the tasks of
the next slice. For that, instead of scheduling the next slice
with the same schedule oe a , we schedule it with an As-Late-
As-Possible (ALAP) so that "holes" may appear in the first
time steps of the slice. Then, between two successive slices,
processors are permuted so that the computational load is
(nearly) equally balanced when concatenating both slices.
Of course dependences between both slices must now be
taken into account.
A precise formulation of this heuristic can be found
in [13]. Here, we only illustrate it on our key example.
Example. Figure 7(c) shows a possible allocation of an instance
of G a provided by an ASAP list scheduling. Figure
8(a) shows an allocation provided by an ALAP list
scheduling and Figure 8(b) the concatenation of these two
instances. The initiation interval  that we obtain is equal
to 37 for two instances. i.e. which is better
than the initiation interval obtained with Algorithm

Figure

7(c)). This cannot be improved further: the
two processors are always busy, as
2.
(a)
time
resources
B,k
(b)
B,k
A,k
D,k
C,k
F,k
Fig. 8. (a): ALAP scheduling
(b): Concatenation of two instances
Another possibility is to schedule, in an acyclic manner,
two (or more) slices instead of one, after the retiming as
been chosen. This is equivalent to unroll the loop after the
retiming has been performed. In this case, once the first
slice has been processed, the second slice can be allocated
the same way, taking into account dependence constraints
coming from the acyclic graph, plus dependences between
the two slices. In other words, the retiming can be seen
as a pre-loop transformation, that consists in changing the
structure of the sub-graph induced by loop independent
edges. Once this retiming has been done, any software
pipelining algorithm can still be applied.
VII. Conclusion
In this paper, we have presented a new heuristic for the
software pipelining problem. We have built upon results
of Gasperoni and Schwiegelshohn, and we have made clear
the link between software pipelining and retiming.
In the case of identical, non pipelined, resources, our
new heuristic is guaranteed, with a better bound than that
of [8]. Unfortunately, we cannot extend the guarantee to
the case of many different resources, because list scheduling
itself is not guaranteed in this case.
We point out that our CDR heuristic has a reasonable
complexity, similar to classical software pipelining algo-
rithms. As for mCDR, further work will be aimed at deriving
an algorithmic implementation that will not require the
use of Integer Linear Programming (even though the particular
instance of ILP invoked in mCDR is polynomial).
Finally, note that all edge-cutting heuristics lead to cyclic
schedules where slices do not overlap (by construction).
Our final load-balancing technique is a first step to overcome
this limitation. It would be very interesting to derive
methods (more sophisticated than loop unrolling) to
synthesize resource-constrained schedules where slices can
overlap.

Acknowledgments

The authors would like to thank the anonymous referees
for their careful reading and fruitful comments.



--R

"Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing,"
"Software pipelining; an effective scheduling technique for VLIW machines,"
"Perfect pipelining; a new loop optimization technique,"
"Cyclic scheduling on parallel proces- sors: an overview,"
"Fine-grain scheduling under resource con- straints,"
"A frame-work for resource-constrained, rate-optimal software pipelining,"
"Software pipelining,"
"Generating close to optimum loop schedules on parallel processors,"
"Decomposed software pipelining,"
"Retiming synchronous circuitry,"
Introduction to Algorithms
Theory of Linear and Integer Program- ming
"A new guaranteed heuristic for the software pipelining problem,"
--TR

--CTR
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
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
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
Alain Darte , Guillaume Huard, Loop Shifting for Loop Compaction, International Journal of Parallel Programming, v.28 n.5, p.499-534, Oct. 2000
Greg Snider, Performance-constrained pipelining of software loops onto reconfigurable hardware, Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays, February 24-26, 2002, Monterey, California, USA
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
R. Govindarajan , Guang R. Gao , Palash Desai, Minimizing Buffer Requirements under Rate-Optimal Schedule in Regular Dataflow Networks, Journal of VLSI Signal Processing Systems, v.31 n.3, p.207-229, July 2002
software pipelining;circuit retiming;list scheduling;cyclic scheduling;modulo scheduling