Optimizing computations for effective block-processing.
Block-processing can decrease the time and power required to perform any given computation by simultaneously processing multiple samples of input data. The effectiveness of block-processing can be severely limited, however, if the delays in the dataflow graph of the computation are placed suboptimally. In this paper we investigate the application of retiming for improving the effectiveness of block-processing in computations. In particular, we consider the k-delay problem: Given a computation dataflow graph and a positive integer k, we wish to compute a retimed computation graph in which the original delays have been relocated so that k data samples can be processed simultaneously and fully regularly. We give an exact integer linear  programming formulation for the k-delay problem. We also describe an algorithm that solves the k-delay problem fast in practice by relying on a set of necessary conditions to prune the search space. Experimental results with synthetic and random benchmarks demonstrate the performance improvements achievable by block-processing and the efficiency of our algorithm.
Introduction
In many application domains, computations are defined on semi-infinite or very long streams
of data. The rate of the incoming data is dictated by the nature of the application and often
cannot be satisfied by a straightforward implementation of the specification. Although the
speed of hardware components has been increasing steadily, the throughput requirements
of new applications have been increasing at an even faster pace. Recent studies show that
while computational requirements per sample of state-of-the-art communication have been
A preliminary version of this work was presented at the 33rd ACM/IEEE Design Automation Conference,
June 1996.
(a) (b)

Figure

1: Improving the effectiveness of block-processing by retiming. The block-processing
factor of the original computation dataflow graph in Part (a) is 1. The block-processing
factor of the retimed graph in Part (b) is 3.
doubling every year, the processing power of hardware is doubling only every three years
[5]. Furthermore, new applications requirements such as low power dissipation impose
additional design constraints which often further add to the gap between the speed of
hardware primitives and the rate of incoming data.
In order to meet the increasing computational demands of today's communication ap-
plications, it is required to compute simultaneously on multiple samples of the incoming
data stream. This approach, known as block-processing or vectorization, is widely used
to satisfy throughput requirements through the use of parallelism and pipelining. Block-
processing enhances both regularity and locality in computations, thus greatly facilitating
their efficient implementation on many hardware platforms [6, 9]. Enhanced regularity
reduces the effort in software switching and address calculation, and improved locality improves
the effectiveness of code-size reduction methods [13]. Moreover, block-processing
enables the efficient utilization of pipelines and efficient implementations of vector-based
algorithms such as FFT-based filtering and error-correction codes [2]. In general, block-
processing is beneficial in all cases where the net cost of processing n samples individually
is higher than the net cost of processing n samples simultaneously. Typical cost measures
include processing time, memory requirements, and energy dissipation per sample.
There are several ways to increase the block-processing factor of a computation, that
is, the number of data samples that can be processed simultaneously. For example, one can
unfold the basic iteration of a computation and schedule computational blocks from different
iterations to execute successively. However, this technique may not uniformly increase the
block-processing factor for all computational blocks.
Another transformation that can be used for increasing the block-processing factor is
retiming. Contrary to other architectural transformation techniques that have targeted
high-level synthesis [8, 17], retiming has been used traditionally for clock period minimization
[7, 10, 12] and for logic synthesis [14, 15].

Figure

1 illustrates the use of retiming for improving block-processing. The computation
dataflow graph (CDFG) in this figure has three computation blocks A, B, and C, and three
delays. An input stream is coming into block A, and an output stream is generated by A.
Assuming that the computation is implemented by a uniprocessor system, the expression
above each block gives the initiation time x and the computation time y per
block input. The initiation time includes context-switching overhead for fetching data and
instructions from the background memory and the cost for reconfiguring pipelines. A single
iteration of the computation in Figure 1(a) completes in (7+5)+(7+6)+(6+3)=34 cycles by
executing the blocks in the order A . For three iterations, the computational blocks
can be executed in the order A . In this case, a new input
is consumed every 34 cycles, and the entire computation needs 3 \Theta cycles. On
the other hand, the functionally equivalent CDFG in Figure 1(b) is obtained by retiming
the original CDFG and can complete all three iterations in a single "block iteration" that
requires only (7 cycles. By grouping
all three delays on one edge, the computations of the three iterations can be executed in
the order A 1 thus amortizing the initiation time of each block
over three inputs.
Recently, retiming has been studied in the context of optimum vectorization for a class
of DSP programs [16, 18]. Specifically, a technique for linear vectorization of DSP programs
using retiming has been presented in [18]. This technique involves the redistribution
of delays in the CDFG representation of a DSP program in a way that maximizes the concentration
of delays on the edges. However, fully regular vectorization cannot be achieved
using the linear vectorization approach in that paper. Moreover, the retiming problem
for computing linear vectorizations is formulated as a non-linear program which can be
computationally very expensive to solve.
In this paper, we consider the problem of retiming computation dataflow graphs to
achieve any given block-processing factor k. We call this the k-delay problem. We first
present an integer linear programming (ILP) formulation of the k-delay problem. We then
formulate a set of necessary conditions which we use to develop an efficient branch-and-
bound algorithm for the k-delay problem. Given a CDFG and a positive integer k, our
algorithm computes a retimed CDFG that achieves a block-processing factor of k or determines
that such a retiming does not exist. An important feature of our approach is that
all blocks in the retimed CDFG achieve the same block-processing factor k and the same
execution order across iterations. As a result, our retimed CDFGs can operate faster and
are less expensive to implement than generic block-processed CDFGs. We provide extensive
experimental results which demonstrate the effectiveness of our optimization and the
efficiency of our algorithms.
The remainder of this paper is organized as follows. In Section 2 we describe the
representation of computations as dataflow graphs and give background material on block-
processing and retiming. We also give a precise mathematical formulation of the k-delay
problem. In Section 3, we present an integer linear programming formulation of the k-delay
problem. In Section 4, we describe a set of effective necessary conditions. Using these
necessary conditions, we develop a branch-and-bound algorithm in Section 5 for solving
the k-delay problem which is efficient in practice. We present our experimental results in
Section 6 and conclude with directions for future work in Section 7.
Preliminaries
In this section, we first describe the dataflow graph representation of computations. We
subsequently provide some background on block-processing and give the conditions that
must be satisfied for effective block-processing. We also provide background material on
retiming and give a mathematical formulation of the k-delay problem.
2.1 Graph representation
The CDFG of a computation structure is an edge-weighted directed graph
The nodes v 2 V model the computation blocks (subroutines, arithmetic or boolean oper-
ators), and the directed edges e 2 E model the interconnection (data and control depen-
dencies) between the computation blocks. Each edge e 2 E is associated with a weight
w(e) that denotes the number of delays or registers associated with that interconnection.

Figure

3(a) gives the graph representation of a sample CDFG.
A delay (state) in behavioral synthesis corresponds to an iteration boundary in software
compilation and a register in gate-level description. All results in this paper can be translated
from one domain to the other two in a straightforward manner. Translation of results
from behavioral to logic synthesis involves only semantic interpretation.
2.2 Block-Processing
Block-processing strives to maximize the throughput of a computation by simultaneously
processing multiple samples of the incoming data. The maximum number of samples that
can be processed simultaneously or immediately after each other by a block v is called the
block-processing factor k v of that block. A block-processing is linear if all blocks have the
A
(a) (b)
A

Figure

2: Types of linear block-processing. (a) Regular and linear block-processing with a
factor 2. (b) Irregular but linear block-processing with a factor 2.
same block-processing factor k. Given a linear block-processing with factor k, the k \Delta jV j
computational block evaluations that generate k iterations of the computation constitute
a block iteration. A linear block-processing with factor k is regular if the k data samples
processed simultaneously by every computational block are accessed during the same
block iteration. The retimed CDFG in Figure 2(a), for example, can be block-processed
linearly and regularly with a block-processing factor of 2. The computation blocks for this
CDFG execute in the order A 1 two input samples are consumed
in each block-iteration. Regular block-processing leads to more efficient implementations
of CDFGs, because it reduces the costs of address calculation and software switching. As
the CDFG in Figure 2(a) illustrates, the indices 1 and 2 computed for block A can be
used for block B as well in the first block-iteration. A linear block-processing need not be
regular, as is illustrated for the CDFG in Figure 2(b) which can be block-processed with a
block-processing factor of 2. The computation blocks for this CDFG execute in the order
\Delta. The block-processing is irregular, however, because the computation
blocks process different samples in a given block iteration. In the first block iteration,
for example, block B processes samples 1 and 2 while block A processes samples 2 and 3.
The following lemma gives the necessary and sufficient conditions for achieving linear
and regular block-processing.
be a CDFG. We can achieve a linear and regular block-
processing of G with factor k if and only if for every edge e 2 E, we have
Proof. ()) If Relation (1) is not satisfied for some CDFG that can be block-processed
linearly and regularly with a factor k, then there exists an edge u e
v such that 1 -
can process at most w(e) samples per iteration. Since w(e) ! k,
the remaining k \Gamma w(e) samples must be accessed from the previous block iteration, which
contradicts regularity.
2.3 Retiming
A retiming of a CDFG is an integer valued vertex-labeling r
This integer value denotes the assignment of a lag to each vertex which transforms G into
r i, where for each edge u e
defined by the equation
The retimed CDFG G r is well-formed if and only if for all edges
Several important properties of the retiming transformation stem directly from Relation
(2). One such property that we use repeatedly in the proofs of this paper is that for
any given vertex pair u; v in V , a retiming r changes the original delay count of every path
from u to v by the same amount. To verify this property, we express the post-retiming
delay count w r (p) along any such path p as the sum of the delay counts of its constituent
edges:
since the sum in Equation (4) telescopes. Thus, the change in the delay count of any path
depends only on the endpoints of the path.
A corollary that follows immediately from Equation (4) for is that retiming does
not change the delay count around the directed cycles of a CDFG. Based on this property,
it is straightforward to show that for any given edge e 2 E, the maximum number of delays
that any retiming can place on e cannot exceed
where W (v;
2.4 The k-delay problem
According to Lemma 1, a linear and regular block-processing with factor k can be achieved
only for CDFGs that have exactly 0 or at least k delays on each edge. If a given CDFG does
not satisfy the condition in Relation (1), we can redistribute its delays by retiming so that
all nodes achieve the desired block-processing factor k. We call the problem of computing
such a retiming the k-delay problem:
Problem KDP (The k-delay problem) Given a CDFG and a positive integer
k, compute a retiming function r Z such that for every edge u e
in E, we have
or determine that no such retiming exists.
Problem KDP cannot be expressed directly in a linear programming form because of the
disjunction (or requirement) in Relation (6). In this section we rely on the notion of the
"companion graph" that was described in [10] to express Problem KDP as an Integer Linear
Program (ILP).
The companion graph G of a CDFG G is constructed by segmenting
every edge u e
into two edges
v, where x uv is a dummy vertex.
Thus, we have
and for each edge u e

Figure

3 illustrates the construction of the companion graph.
The following lemma gives the necessary and sufficient conditions that hold for any
retiming that solves Problem KDP.
be a CDFG, and let G its companion graph.
Then there exists a retiming function r that solves Problem KDP on G if and only
if there exists a retiming function r Z such that for every edge u e i
we have
and for every edge u e
in E, we have
F
(a)
(b)
F

Figure

3: Constructing a companion graph. (a) Original CDFG Companion
graph generated by segmenting every edge in E into two edges and
introducing a dummy vertex such that the first edge has a delay count of at most 1. Edge
in G has been segmented to generate edges C w=1 ! XCD and XCD w=2 ! D in G 0 .
Proof. Inequality (7) ensures that the retimed circuit is well-formed. Inequalities (8) and
ensure that the delay counts in G 0
r 0 satisfy the definition of a companion graph. Inequality
ensures that for every edge u e
x uv has one delay after retiming,
then edge x uv
v has at least k \Gamma 1 delays. Thus, if edge u e
in E has any delays, then
it has at least k delays after retiming. By construction, a solution r for Problem KDP on
G can be derived from r 0 by simply setting
The following theorem expresses Problem KDP as a set of O(E) integer linear programming
constraints.
Theorem 3 Let computation flow graph and let G
be its companion graph. Then there exists a retiming function r solves
Problem KDP if and only if there exists a retiming function r Z such that for every
edge
and for every edge u e
in E, we have
Proof. Follows directly from the linearity of Relation (2) and the form of the inequalities
in Lemma 2.
Necessary conditions
The main challenge in solving Problem KDP is to determine which edges should have delays
and which should not. In the ILP formulation of Problem KDP, we determine these edges
explicitly, and the resulting constraints in the formulation do not appear to have any special
structure. We thus need to resort to general integer linear programming solvers to compute
a solution, which can be computationally expensive for large CDFGs. In this section, we
give a set of necessary conditions which determine implicitly which edges should or should
not have delays. In the next section, we develop a branch-and-bound technique based on
these necessary conditions, which is considerably more efficient in practice than the ILP
formulation.
In the following four subsections, we derive necessary conditions for the feasibility of
Problem KDP on any given CDFG. We first derive conditions to ensure that all cycles
have enough delays around them. We then identify paths which must necessarily contain
delays and paths which must necessarily be free of delays. Based on these paths, we derive
necessary conditions for the feasibility of Problem KDP. We finally describe the construction
of a constraints graph which captures explicitly the necessary conditions for the feasibility
of Problem KDP.
4.1 Delays around cycles
Retiming leaves the delay count around cycles unchanged and, therefore, for any given
CDFG G and a block-processing factor k, Problem KDP is feasible only if the delay count
around all cycles in G is greater than k. The following lemma gives a mathematical characterization
of this result for the feasibility of Problem KDP.
be a CDFG. Problem KDP is feasible on G only if for every
vertex
Proof. By contradiction. Let Problem KDP be feasible on G, and let there exist a vertex
pair u; v for which Inequality (15) does not hold. Since W (u; v) the
minimum delay count for any simple cycle through u and v, there exists a directed cycle c
in G that has a delay count less than k. Since retiming does not change the delay count
around cycles, we conclude that c has an edge with delay count between 1 and
every retiming, which contradicts our assumption that Problem KDP is feasible.
For every vertex pair u; v 2 V , W (u; v) can be computed efficiently by an all-pairs
shortest-paths computation in O(V steps. We thus assume for the remainder
of this paper that any given CDFG G already satisfies Inequality (15).
4.2 Paths with delays
Using the property that retiming changes the delay count of paths between a given vertex
pair by the same amount, we determine vertex pairs between which all paths must necessarily
contain delays in any solution to Problem KDP. The following lemma gives a necessary
condition for such vertex pairs.
be a CDFG, and let r Z be a solution to Problem KDP
on G. Then for every vertex pair u; v 2 V such that there exists a path u p
in G with
Proof. By contradiction. Suppose that r solves Problem KDP and that W r (u; v) -
for some vertex pair u; v 2 V which satisfies the condition in the lemma. We will show that
there exists an edge e 2 E for which Relation (6) does not hold.
then the path u q
with minimum delay W r (u; v) has a nonzero delay
count that does not exceed k \Gamma 1. Thus, some edge on this path violates Relation (6).
then for the path u q
in the statement of the lemma, we have
Furthermore, we have
(c)
(b)
(a)

Figure

4: Illustration of explicit and implicit delay-essential (DE) vertex pairs. The CDFG
in Part (a) has been transformed by Algorithm AddEdges to generate the CDFG in Part
(b) and then finally the CDFG in Part (c). The bold edges in Part (b) are between explicit
DE pairs. The weights on these edges indicate the excess delay associated with the corresponding
vertex pairs. The bold edges in Part (c) denote both explicit and implicit DE
pairs. For example, the pair B; D is implicitly DE and becomes apparent only after the DE
vertex pairs B; C and C; D are made explicit.
Thus, p has a nonzero delay count that does not exceed k \Gamma 1, and consequently, some edge
on p violates Relation (6).
The following lemma casts the necessary conditions of Lemma 5 as a retiming problem
on an appropriately constructed constraints graph.
be a given CDFG and let G  be the constraints
graph that is generated from G as follows: For every vertex pair u; v 2 V such that there
exists a path u p
in G with delay count w(p) and W (u; v) ! w(p) ! k, add a new edge
Problem KDP on G, then
for every edge u e
Proof. From Relation (2) and the definition of well-formedness, we have that Inequality (17)
holds for every edge e 2 E.
It remains to show that Inequality (17) holds for the edges in the set E   \Gamma E. Consider
a vertex pair u; v 2 V that is connected by an edge e For the purpose of
contradiction, suppose that Problem KDP is feasible and that r(v) \Gamma r(u)
the construction of G   , we have
Since r solves Problem KDP, Lemma 5 implies that W r (u; v) - k, which contradicts Inequality
(19).
We call a vertex pair u; v 2 V delay-essential (DE) if the shortest path u q
every retimed CDFG that satisfies Relation (6) must contain delays. For example, every
vertex for which there exists a path u p
v such that W (u;
delay-essential, since it satisfies the condition in Lemma 5. It can be shown that it suffices
to compare the delay count of the two shortest paths between a vertex pair to check for the
existence of a path u p
v such that W (u;
Algorithm AddEdges-1 in Figure 5 transforms the given graph G into G   . This algorithm
determines delay-essential vertex pairs by checking if the delay counts of the shortest
and the strictly-second shortest path between every vertex pair differ by less than k. For
every delay-essential vertex pair u; v, an edge u e
introduced to ensure that W r (u; v) - k.
It is important to note that in order to determine whether a given vertex pair is delay-
essential, one needs to compare the delay counts of the shortest path and the strictly-second
shortest simple path (that is, a path whose weight is strictly greater than the shortest-path
weight). Although the problem of computing the strictly-second shortest simple path between
a given vertex pair is NP-complete, the corresponding problem without the simple
path requirement can be solved in polynomial time [11]. For graphs that satisfy Inequality
in Lemma 4, it is straightforward to show that if the strictly-second shortest path is
non-simple, then its delay count exceeds that of the shortest path by at least k. Conversely,
if the delay counts of the shortest and the strictly-second shortest paths differ by less than
k, then the strictly-second shortest path is guaranteed to be simple.
The following lemma shows that Algorithm AddEdges-1 runs in polynomial time.
AddEdges-1(G;
1 for every vertex pair u;
do m[u][v] / FALSE
4 Run an all-pairs strictly-second-shortest paths algorithm on G.
5 for every vertex pair u; v 2 V with u p1
being the two shortest paths between u; v
6 do if
7 then m[u][v] / TRUE
8 Introduce u e
return G

Figure

5: Algorithm AddEdges-1 transforms
Lemma 7 In O(V 2 E) steps, Algorithm AddEdges-1 transforms a given CDFG
hV; E;wi into G   .
Proof. Steps 1-2 take O(V 2 ) time. Since the all-pairs second-shortest paths can be computed
in O(V E+V E) time [11], Step 4 takes O(V 2 E) time. Steps 5-10 take O(V 2 )
time to complete. Thus, Algorithm AddEdges-1 terminates in O(V 2 E) steps.
Lemma 5 captures only explicit delay requirements and not implicit or hidden require-
ments. Let us assume, for example, that we wish to solve Problem KDP for the CDFG in

Figure

4(a) with 2. Since the shortest and the second-shortest paths between vertices B
and D have 1 and 4 delays, respectively, the condition in Lemma 5 does not apply, and the
does not appear to be delay-essential. We can verify, however, that the shortest
path between B and D must necessarily contain delays in any solution of Problem KDP,
since it is impossible to retime the given CDFG and zero out the delay count of B ! D.
Since the vertex pairs B; C and C; D must satisfy the condition in Lemma 5, they need at
least 2 delays on their shortest paths D. Thus, no delay along the path
can be moved outside B ; D. Since retiming changes the delay along paths
between the same vertex pair in an identical manner, the delay on edge cannot be
moved out of B ; D.
In order to expose implicit delay requirements, we construct a new graph G
all delay-essential vertex pairs are explicit. Algorithm AddEdges-2 in Figure 6
transforms the graph G   (generated from a given CDFG G by Algorithm AddEdges-1)
into G T and determines implicit delay-essential vertex pairs. Delay-essential vertex pairs
are determined by comparing, for every vertex pair, the delay counts of the shortest path in
3 repeat
4 for every delay-essential vertex pair u; v 2 Q
5 do m[u][v] / TRUE
6 Introduce edge u e
8 for every delay-free vertex pair u;
9 do m[v][u] / TRUE
Run an all-pairs shortest paths algorithm on G T to compute W T (u; v)
for every vertex pair u;
do if
20 then delete edge u e
! v from G T
22 Q
23 for every pair u;
do if
26 elseif w
then delete edge v e
! u from G T
28 m[v][u] / FALSE

Figure

Algorithm AddEdges-2 transforms G
steps. In the new graph G T , all delay-essential and all delay-free vertex pairs
of G are explicit.
the transformed graph of the current iteration and the shortest path in the original graph.
If for a vertex pair u; v the delay counts of these two paths differ, then an edge u e
weight is introduced to ensure that W r (u; v) - k. (It can be shown
that is is sufficient to place the additional edge only if the delay counts for the two shortest
paths differ by less than k. If their difference exceeds k, then the condition W r (u; v) - k is
implicitly taken care of.) Intuitively, W (u; the excess delay of the pair u;
and gives an upper bound on the number of delays that can be "contributed" by that pair
to the rest of the graph. As new edges are introduced, new vertex pairs can become delay-
essential, as shown in Figure 4. For example, the pair B; D becomes delay-essential only
after the delay requirements of the pairs B; C and C; D become explicit.
The following lemma proves that the constraints introduced for the delay-essential vertex
pairs in each iteration of Algorithm AddEdges-2 are necessary for Problem KDP.
be a CDFG, and let G be the transformed graph
generated by the repeat loop of Algorithm AddEdges-2 after i iterations. Let G
be the graph generated after iterations by augmenting E i as follows:
For every vertex pair u; v), an edge u e
is introduced in E i . Let r Z be a solution for Problem KDP
on G. If for every edge u e
then for every edge u e
Proof. Let u e
. In this case, we have w Inequality (20)
follows immediately from Inequality (19).
Let u e
By construction, we have W (u; v) ? W i (u; v). Therefore
r
Adding up the left and right-hand side parts of Inequality (19) along the edges of the shortest
path from u to v in G i , we obtain W i
r (u; v) - 0. Inequality (22) implies that W r (u; v) ? 0,
and since r is a solution to Problem KDP, we infer that
(Otherwise some edge along the shortest path in G r would contain fewer than k delays.)
Therefore, for the edge u e
Thus, r satisfies Inequality (20).
4.3 Paths without delays
In contrast to delay-essential paths, we have paths which must contain no delays in any
solution. We call a vertex pair u; v 2 V delay-free (DF) if the shortest path u q
in every retimed CDFG that satisfies Relation (6) must contain no delays. For example,
if G T is the constraints graph constructed from G, then any vertex pair u; v with
is delay-free, since retiming does not change the delay count
around cycles and cannot result in W r (u; v) - k. As a result, for every such vertex pair,
the condition W r (u; must hold, otherwise Relation (6) will be violated for some edge
along the shortest path u p
During the construction of graph G T by Algorithm AddEdges-2, delay-free vertex pairs
are determined by checking for every vertex pair u; v whether
If so, an edge v e
is introduced to ensure that W r (u;
This process is repeated until every delay-free vertex pair is made explicit by these additional
edges. For example, in Figure 7(a), the pair A; B is delay-essential, and we introduce a bold
edge This new edge introduces the cycle
which has fewer than k delays, and thus the vertex pair B; A must be delay-free. To enforce
this constraint, the weight on the bold edge A ! B is changed to \GammaW (B;
The following lemma proves that each iteration of Algorithm AddEdges-2 introduces
constraints that are necessary for Problem KDP to be feasible.
Lemma 9 Let be a given CDFG, and let G be the transformed
graph generated by the repeat loop of Algorithm AddEdges after i iterations. Let G
be the graph generated after iterations by augmenting E i as follows:
For every vertex pair u; k, an edge v e
C(a) (b)

Figure

7: Delay-free path for a given CDFG with 2. The cycle formed by
in (a) has less than k delays. Therefore B; A must be delay-free and the weight on
the bold edge is changed to \GammaW (B; in (b) to achieve this.
is introduced in E i . Let r Z be a solution for Problem KDP on
G. If for every edge u e
then for every edge u e
Proof. If u e
Inequality (23) follows
immediately from Inequality (22).
Now, consider an edge v e
. For the vertex pair u; v 2 V , we have
by the construction of E i+1 . Adding up the parts of Inequality (22)
along the edges of the shortest path from v to u in E i , we obtain W i
r (v; u) - 0. Therefore
r (v; u)
Since r solves Problem KDP, the last inequality implies that W r (u;
then some edge along the shortest path from u to v in E contains fewer than k delays.)
Thus, for the edge v e
and r satisfies Inequality (20).
4.4 Constraints graph generation
The necessary conditions in Lemmas 5, 8, and 9 are encoded by the edges and edge-weights
of the constraints graph G generated by Algorithm AddEdges-2. For each
DE vertex pair u; v 2 G, this algorithm introduces an edge u e
k. Moreover, for each DF vertex pair u; introduces an edge v e
weight w T v). The following lemma summarizes the necessary conditions for
the feasibility of Problem KDP on a given CDFG G in terms of the transformed graph G T .
be a CDFG, and let G be the transformed
graph generated by Algorithm AddEdges-2. Let r Z be a solution for Problem KDP
on G. Then for every edge u e
Proof. Follows directly from Lemmas 8 and 9.
The following lemma gives the running time of Algorithm AddEdges-2.
Lemma 11 In O(V 3 E+V 4 lg V ) steps, Algorithm AddEdges-2 transforms a given CDFG
into G T or determines that such a transformation is not possible.
Proof. The repeat loop in Step 3 can execute O(V 2 ) times in the worst case when in
each iteration only one additional edge between a DE or a DF vertex pair gets added
or modified to the graph. (It can be shown that the delay count of an additional edge
gets modified at most once). All for loops in Algorithm AddEdges-2 execute in O(V 2 )
steps since we have at most O(V 2 ) vertex pairs. Step 15 takes O(V
using Johnson's algorithm for computing the all-pairs shortest paths [4]. Thus the body
of the repeat loop completes in O(V
5 A practical branch-and-bound algorithm
In this section, we describe an efficient branch-and-bound scheme for solving Problem KDP.
Our scheme relies on the necessary conditions derived in Section 4 to effectively prune the
search space while computing a solution.
(G;
1 for every vertex
do r[u] / 0
6 then return r
7 else return INFEASIBLE

Figure

8: Algorithm SolveKDP for solving Problem KDP.

Figure

8 describes our Algorithm SolveKDP for Problem KDP. After generating the
constraints graph G T , our algorithm initializes r and searches for a solution using the
procedure Branch-and-Bound that is described in Figure 9. The recursive procedure
Branch-and-Bound computes a retiming r that satisfies the constraints in G T . If there
exists a violating edge e in the retimed graph G r (that is, an edge with a delay count
between 1 and k \Gamma 1), Algorithm Branch-and-Bound adds constraints in G T that force e
to have at least k delays. It subsequently computes a retiming that satisfies the augmented
constraints set. This step is repeated until a solution is found or until we obtain a set
of necessary conditions that cannot be satisfied by any retiming, in which case Algorithm
Branch-and-Bound backtracks. In each backtracking step, the state of the constraints
graph is restored, and a new constraint is added that forces the violating edge e to take a
delay count of zero.
For a given CDFG G, the optimal block-processing factor kmax is the largest number of
samples which can be processed successively by all the computation blocks of G. This number
equals the maximum number of delays that can be placed on any edge and is bounded
from above by F . Thus, kmax can be determined by a binary search over the integers in
the range [1; F ]. The feasibility of each value is checked using Algorithm SolveKDP.
6 Experimental Results
We have developed three programs for computing the optimal block-processing factor kmax .
In all three programs kmax is determined by a binary search. In this section, we present
results from the application of our programs on real and synthetic DSP computations. The
purpose of our experiments was to determine by how much block-processing speeds up
computations, to compare the efficiency of our different implementations, and to evaluate
the effectiveness of our necessary conditions.
The first program (ILP) solves the integer linear programming formulation of Problem
Branch-and-Bound
that satisfies Inequality (24)
exists
3 then return FAIL
with
6 do Save G T
and r
8 Introduce edge u e
12 then return SUCCESS
else Restore G T
and r
19 then return SUCCESS
else Restore G T
and r
22 return FAIL
return SUCCESS

Figure

9: Algorithm Branch-and-Bound which is called by Algorithm SolveKDP for
solving Problem KDP.
KDP that we described in Section 3. It first generates the ILP constraints and then solves
the integer program separately using lp solve, a public-domain mixed-integer linear programming
solver [1]. Our second program (NC-ILP) first checks the necessary conditions
given in Section 4 to screen out infeasible problems. The problems that satisfy the necessary
conditions are then solved by an ILP formulation which is fed to lp solve. Our third
program (BB) is an implementation of Algorithm SolveKDP given in Section 5. This
branch-and-bound scheme relies on the necessary conditions from Section 4 to effectively
prune the search space.
In order to explore the computational speedup possible with block-processing, we applied
our k-delay optimization to the computation dataflow graphs of four real DSP programs.
Our test suite comprised an adaptive voice echo canceler, an adaptive video coder, and two
examples from [18]. The size of the CDFGs of these DSP programs ranged from 10 to 25
nodes.
The results of our speedup experiments are given in the table of Figure 10. These data
have been obtained for uniprocessor implementations. For each CDFG, the improvement is
Design # cycles with kmax # cycles with Improvement (%)
original CDFG optimized CDFG
Echo Canceler 1215 3 840 31

Figure

10: Experimental results for uniprocessor implementations.
given by the fraction
# cycles with optimized CDFG
# cycles with original CDFG :
After k-delay retiming, the reduction S achieved in execution time is given by the fraction
where O is the sum of the context-switching overheads of all nodes, and C is the sum of
all computation times. In our experiments, initiation and computation times were obtained
using measurements on typical DSP general purpose processors, such as TMS32020 and
Motorola 56000.
In order to evaluate the efficiency of our implementations, we experimented with large
synthetic graphs in addition to the real DSP programs. The synthetic graphs in our test
suite were generated using the sprand function of the random graph generator described
in [3]. All the graphs generated using sprand were connected and had integer edge weights
chosen uniformly in the range [0, 5]. Given the number of vertices and edges desired,
sprand generates graphs by randomly placing edges between vertices and by randomly
assigning weights from the specified range. The size of these computation dataflow graphs
was between 10 to 300 vertices and 20 to 750 edges.
The results from the application of our three programs on our synthetic test suite are
summarized in Figure 11. Our experiments were conducted on a SPARC10 with 64MB of
main memory. The CPU times for the three programs are for computing kmax . Our results
show that ILP is very inefficient and its running time becomes impractical for graphs with
more than vertices and 70 edges. ILP searches the entire solution space before detecting
infeasible solutions. During the binary search, solutions to feasible problems are computed
relatively fast, but not as fast as in the other two programs. Furthermore, the detection of
infeasible problems is extremely time-consuming.
NC-ILP is more efficient than ILP, primarily due to the quick screening of infeasible
problems based on the necessary conditions from Section 4. However, NC-ILP cannot
name ILP NC-ILP BB

Figure

11: Comparison of running times (in CPU seconds) taken by ILP, NC-ILP, and
BB to compute kmax for random graphs. Entries marked with "-" indicate running times
exceeding 30,000 cpu seconds.
handle efficiently any CDFG that has more than 50 nodes.
BB is the most efficient of our three programs and is orders of magnitude faster than
ILP or NC-ILP. Moreover, it can handle graphs that are at least one order of magnitude
larger than the graphs handled by ILP or NC-ILP. We thus conclude that our necessary
conditions are very effective in pruning the search space.
7 Conclusion and future work
Block-processing speeds up the execution of computations by amortizing context switching
overheads over several data samples. In this paper, we investigated the problem of improving
the block-processing factor of DSP programs using the retiming transformation. We
formulated the problem of computing a retiming that achieves a given block-processing factor
k as an integer linear program. We then presented a set of necessary conditions for this
problem that can be computed in polynomial time. Based on these conditions, we designed
a branch-and-bound scheme for computing regular and linear block-processings. In our experiments
with real and synthetic computation graphs, our branch-and-bound scheme was
orders of magnitude more efficient than the general integer linear programming approaches.
Thus, our necessary conditions proved to be particularly powerful in pruning the search
tree of our branch-and-bound scheme.
An important question that remains open is whether our necessary conditions are also
sufficient. So far, we have not been able to prove sufficiency. On the other hand, we have
not discovered a situation in which our necessary conditions are feasible yet the k-delay
problem is infeasible. We nevertheless conjecture that our necessary conditions are not
sufficient.
An interesting direction for further investigation is the reduction of critical path length
in conjunction with the maximization of the block-processing factor. Our preliminary work
in the area shows that it is possible to express critical path requirements in the form of
constraint edges in the transformed graph G T .
Future work in this area could explore the applicability of our techniques for compiling
code on Very Long Instruction Word (VLIW) architectures. The main challenge with VLIW
machines is to issue as many instructions as possible in the same clock cycle. By viewing
the instructions in a given program as delay elements in a computation graph, one could
model the compilation problem for VLIW architectures as a block-processing problem on a
CDFG.



--R

lp solve: A mixed-integer linear programming solver
Fast Algorithms for Digital Signal Processing.
Shortest paths algorithms: theory and experimental evaluation.
Introduction to Algorithms.
Software's chronic crisis.

Optimizing two-phase
Relative scheduling under timing constraints: Algorithms for high-level synthesis of digital circuits
VLSI Array Processors.
DelaY: An efficient tool for retiming with realistic delay modeling.
Computing strictly-second shortest paths
Retiming synchronous circuitry.
Storage assignment to decrease code size.
Retiming and resynthesis: Optimizing sequential networks with combinational techniques.
Synchronous logic synthesis: Algorithms for cycle-time minimization
Optimum vectorization of scalable synchronous dataflow graphs.
Behavioral transformations for algorithmic level IC design.
Retiming of DSP programs for optimum vec- torization
--TR
VLSI array processors
Introduction to algorithms
Storage assignment to decrease code size
The practical application of retiming to the design of high-performance systems
Computing strictly-second shortest paths
Fast Algorithms for Digital Signal Processing

--CTR
Dong-Ik Ko , Shuvra S. Bhattacharyya, Modeling of Block-Based DSP Systems, Journal of VLSI Signal Processing Systems, v.40 n.3, p.289-299, July      2005
Ming-Yung Ko , Chung-Ching Shen , Shuvra S. Bhattachryya, Memory-constrained block processing for DSP software optimization, Journal of Signal Processing Systems, v.50 n.2, p.163-177, February 2008
Ming-Yung Ko , Praveen K. Murthy , Shuvra S. Bhattacharyya, Beyond single-appearance schedules: Efficient DSP software synthesis using nested procedure calls, ACM Transactions on Embedded Computing Systems (TECS), v.6 n.2, p.14-es, May 2007
retiming;combinatorial optimization;computation dataflow graphs;embedded systems;integer linear programming;scheduling;high-level synthesis;vectorization