Estimation of lower bounds in scheduling algorithms for high-level synthesis.
To produce efficient design, a high-level synthesis system should be able to analyze a variety of cost-performance tradeoffs. The system can use lower-bound performance estimated methods to identify and puune inferior designs without producint complete designs. We present a lower-bound performance estimate method that is not only faster than existing methods, but also produces better lower bounds. In most cases, the lower bound produced by our algorithm is tight.Scheduling algorithms such as branch-and-bound need fast and effective lower-bound estimate methods, often for a large number of partially scheduled dataflow graphs, to reduce the search space. We extend our method to efficiently estimate completion time of partial schedules. This problem is not addressed by existing methods in the literature. Our lower-bound estimate is shown to by very effective in reducing the size of the search space when used in a branch-and-bound scheduling algorithm.Our methods can handle multicycle operations, pipelined functional units, and chaining of operations. We also present an extension to handle conditional branches. A salient feature of the extended method is its applicability to speculative execution as well as C-select implementation of conditional branches.
Introduction
High-level synthesis takes an abstract behavioral specification of a digital system and finds a
register-transfer level structure that realizes the given behavior. Usually, there are many different
structures that can be used to realize a given behavior. One of the main goals of a synthesis
system is to find the structure that best meets the constraints, such as limitations on the number
of functional units, registers, power, while minimizing some other parameters like the number of
time steps. Operation scheduling and datapath construction are the core of high-level synthesis in
obtaining efficient designs in terms of area and speed. Scheduling datapath operations into the best
time steps is a task whose importance has been recognized in many systems [12, 14, 15, 16]. Since
scheduling is an intractable problem, most high-level synthesis systems use heuristics to find a good
schedule. In the absence of good lower-bound estimates, it is difficult to evaluate the performance
of heuristics.
For a synthesis system to produce efficient designs, it should have the capability to analyze
different cost-performance trade-offs. So, a scheduler has to explore the design space with a variety
of resource constraints. Instead of producing schedules with each and every resource constraint,
a scheduler can use estimation to identify and prune inferior designs. Furthermore, estimation of
lower bounds can be used to evaluate a heuristic solution. For an estimation tool to be useful, it has
to be much faster than the actual scheduler and the lower bounds it produces should be as tight as
possible. We have proposed an efficient estimation technique for the lower-bound performance. We
tested our estimation method on a number of benchmarks and compared our results with those of
some other known methods in the literature [17, 20]. Our method faster than the methods in [17]
and [20]. Our method produces better lower bounds than both of them in many cases. In most
cases, the lower bound is tight.
Many scheduling algorithms such as the branch and bound methods [3] and multi-schedule
methods [2] search through the design space by constructively scheduling operations, one step
at a time. During the search process, schedules for a subset of operations in the DFG will be
produced and evaluated to check if they can lead to a complete schedule with a target upper-bound
performance. Such scheduling methods need a method to estimate lower bounds on the completion
time of partial schedules. Since the number of partial schedules is generally very high in a design
space search process, this estimation should be faster than the estimation for the entire DFG.
In this paper, we have proposed a fast and effective lower-bound estimation method for partially
scheduled DFGs. It is an extension of our method for the lower-bound estimation of the entire
DFGs. In our approach we defined some very useful data structures that need to be computed only
once for a given DFG before the exploration. Using those data structures, our method can compute
a lower bound for a partial schedule in O(k) time where k is the number of ready and unfinished
operations (defined later in this paper) at the partial schedule. The methods in [5, 17, 20, 21]
are originally proposed for estimation for the entire DFG and do not address the estimation from
partial schedules. They are too slow to be used for partial schedules. For example, if the methods
in [17], [20] are used for partial schedules, they take O(c 2 respectively to compute
lower bound for a partial schedule where n is the number of operations to be scheduled and c is
the critical path length.
We implemented our method and the method in [17] separately into a branch and bound
scheduling algorithm and tested on a number of benchmarks. The results show that our method is
at least 20 times faster and equally effective in reducing the size of the search space. Our method
can be used in any scheduling algorithm that schedules one step at a time. We used this method in
an optimal dynamic programming scheduling algorithm [1] we developed, and it drastically reduced
the size of the search space. We could obtain optimal schedules in very short computational times.
Our methods can handle multi-cycle operations, pipelined functional units and chaining of
operations. We extended our methods to handle conditional branches. The extended method is
applicable to speculative execution as well as C-select execution of operations in the conditional
branches. To our knowledge, no other estimation method in the literature can support speculative
execution. In the next section, a brief overview of previous works for lower bound estimation is
presented. In section 3, our model and terminology is defined. The method for the estimation of
lower bounds for the entire DFG is presented in section 4. The computational complexity of our
method as compared to Sharma's method [20] is analyzed in the same section. Our lower-bound
estimation method for partial schedules is presented in section 5. Extensions to handle conditional
branches and chaining are explained in section 6. Experimental results are presented in section 7
and conclusions are in section 8 .
Previous Work
There are several methods proposed in the literature for the lower-bound estimation of cost as
well as performance. Jain et al [7] proposed a mathematical model for predicting the area-delay
curve. Their lower-bound method is very fast, but is too trivial and does not consider precedence
constraints at all. The technique proposed by Fernandez and Bussell [4] computes the minimum
number of operations which must be scheduled in each sub-interval of time steps. It then derives
maximum increase in total execution time over all intervals for not having enough processors to
accommodate all the operations in that interval. Their method considers only homogeneous resources
and can be applied only to multiprocessor schedules. Their method has been extended to
high-level synthesis by Sharma et al [20]. They compute the increase in the length of each interval
due to concentration of each type of operations in that interval. They also address lower bounds
on area cost including interconnect cost. Their method has a computational complexity of O(nc 2 )
where n is the number of nodes in the DFG and c is the critical path length. The method proposed
by Ohm et al [10] estimates lower bounds on functional units as well as registers. Their technique
for functional unit estimation is a refinement of the basic technique of [20]. It is not applicable to
lower-bound performance estimation. The complexity of their method is O( n(c 2 +n+ e) ) where e
is the number of edges in the DFG. The method proposed in [17] uses a relaxation technique of the
ILP formulation of the scheduling problem for the lower-bound estimation of performance under
resource constraints. It has a computational complexity of O(n is the number of
time steps and produced lower bounds as good as [20] on many benchmarks. The method in [21]
is similar to [17] in that it relaxes the precedence constraints and solves the relaxed problem using
a slack driven list scheduling algorithm. Hu et al [5] proposed a method to estimate lower bounds
on iteration time and functional unit cost for functional pipelined DFGs. The complexity of their
method is O(nck 2 ) where k is the initiation latency. A recursive technique is proposed in [8] for
lower-bound performance estimation and it has a complexity of O(n The complexity of
our method for the lower-bound performance estimation of the entire DFGs has a complexity of
3 Model and Definitions
A DFG (Data Flow Graph) E) is a (directed acyclic) graph representation of a behavioral
description where the set of nodes V represents the set of operations and the set of edges E denotes
the set of dependencies (precedence constraints) between the operations. For any two operations
should be finished before operation y can start. A node x
is called a predecessor of y (and y, a successor of x) if there is a directed path from x to y in G
using the arcs in E. An operation without any predecessors is called an input operation and an
operation without any successors is called an output operation. Associated with each operation x
in V , there is a single type indicating that a functional unit of that type should be used to execute
that operation. Resource   constraints are given by a set of ordered tuples ! t;
D(t) is the delay (number of time steps or clock cycles) an operation of type t takes to complete and
N(t) is the number of available resources of type t. If a resource type t is pipelined, one instance
of that resource type can be assigned to more than one operation in an overlapping fashion. The
latency with which they can overlap is denoted by ffi t . Clearly,
Let d x denote the delay of an operation x, which is equal to the delay of the type of resource
that executes x. For all (as soon as possible) is the earliest time-step that
v can be scheduled to start execution, assuming unlimited resources. For all
MSAT (v) (Minimum Steps After This operation) as the minimum number of time steps that any
schedule of G is going to take after the completion of operation v, assuming unlimited resources.
The critical path length is the minimum number of time-steps that any schedule of G is going to
take, assuming unlimited resources. It can be computed as with the
maximum taken over all output operations v.
4 Lower-bound estimation for performance
The intuitive idea behind our lower-bound estimation is as follows. For each resource type t, we
group the operations of that type into three non-overlapping intervals and compute a lower-bound
as the sum of the lengths of those intervals. The final lower bound is the maximum among all
resource types and all possible groupings of operations of each type.
Let P t be the number of operations of type t in the DFG. If there are oe A (i; t) operations of type
t with an ASAP value less than or equal to i, then there are at least P operations
that cannot be scheduled in the first i time steps. Similarly, if there are oe M (j; t) type t operations
with a MSAT value less than j, then there are at least P operations that cannot
In this paper, resources refer to single-function functional units only
be scheduled to execute in the last j time steps. Thus, there are at least P
t operations that cannot either be scheduled in the first i time steps or be scheduled to execute in
the last j steps of any schedule. The three intervals considered are : first i steps (interval I 1 ), last
steps (interval I 3 ) and an interval between the two (interval I 2 ) that does not overlap with the
other two. The lengths of intervals I 1 and I 3 are i and j respectively. The length of I 2 depends
on the minimum number of type t operations in that interval as well as the number of available
resources of type t. The number of operations in I 2 depends on the ASAP and MSAT values of
operations which are determined by data dependencies. Thus, the lower-bound estimation takes
into account both precedence constraints and resource constraints.
Note that it takes at least i time steps before any of the operations in I 2 can start execution
and at least j steps after the last operation has finished execution. The lengths of I 1 and I 3 are
independent of the set of operations scheduled in those intervals. Thus, for the purposes of lower-bound
estimation, the three intervals are non-overlapping. We denote the minimum number of
type t operations in interval I 2 by q(i; j; t) and the minimum length of I 2 due to type t operations
by h(i; j; t). As explained above, q(i; j; and the value of h(i; j; t) can be
computed from q(i; j; t) as follows.
operations can be scheduled into dk=re stages. If type
t resources are not pipelined, each stage takes D(t) time steps where D(t) is the delay of a type t
resource. If they can be pipelined with a latency ffi t , each stage except the last takes ffi t steps. The
last stage in either case takes D(t) steps. Hence,
pipelined
r e   D(t) otherwise.
lower bound on the the completion time of any schedule of the given DFG, - is
oe A (1;
oe A (2;
oe A (3;
oe A (4;
oe A (5;
oe A (6;
The ordered pair next to each node shows its ASAP and MSAT values

Figure

1. An example for the lower-bound estimation for the entire DFG
given by max (t;i+j-c) fh(i; c is the critical path length.
Proof : The above discussion implies that i is a lower bound for a given i, j and
type t. The expression for - is the best lower bound among all i, j and t. The condition
makes sure that the intervals are non-overlapping. 2

Figure

1 shows an example for lower-bound computation. The ordered pair next to each node
indicates its ASAP and MSAT values respectively. It is assumed that addition takes one time step
and multiplication takes two. There are one adder and one non-pipelined multiplier. All values of
oe A and oe M for multiplication and addition are shown in the figure. For example, the multiplication
operations 1 and 2 each has ASAP value less than or equal to 2. Hence, oe A (2;  ) is 2. Similarly,
the addition operations 6; 7; 8 and 9 each has MSAT value less than 2. Hence, oe M (2; +) is 4. For
the example DFG, the maximum value for - is obtained when i=0 and j=2.
Complexity analysis :
The ASAP values can be computed in a top-down fashion starting from the input
operations as follows. If v is an input operation, ASAP (v) = 1. Otherwise,
g. The MSAT values are similarly computed in a
bottom-up fashion starting from the output operations as follows. If v is an output operation,
g. Let n be the number
of operations in the DFG. The number of edges in a DFG will grow linearly in n since the number
of inputs of each operation is generally bounded by small number such as two. Hence, the ASAP
and MSAT values can be found in O(n) time. The number of resource types is generally bounded
by a small number. For any i and t, oe A (i; t) and oe M (i; t) can be found recursively as follows.
oe A (i; is the number of type t operations with ASAP value i.
Similarly, oe M (i; is the number of type t operations
with MSAT value 1. The values for A and M can be found during the computation of ASAP
and MSAT values without affecting its complexity. Hence, computing oe A and oe M takes O(c) time
where c is the critical path length. Finally, computing lower bound using these values takes O(c 2 )
time because there are O(c 2 ) intervals. Thus, the complexity of our algorithm to estimate lower
bound of the entire DFG is O(n
The method in [20] is similar to our method in that it estimates the length of each interval
of time steps. It computes the required computation cycles of each type as the sum of minimum
overlaps of all operations of that type in each interval. Then the difference in the required and
available computation cycles of each type is divided by the number of available functional units of
that type to get any increase in the length of that interval. In their method, for each interval the
minimum overlap of each operation has to be determined. Hence, it has a complexity of O(nc 2 ).
Our method computes only the number of operations in each interval in constant time using the
precomputed data structures oe A and oe M , thus having a complexity of only O(n
5 Estimating a lower bound for a partially scheduled DFG
Scheduling algorithms such as branch and bound methods need to compute lower bounds on the
completion times from a large number of partially scheduled DFGs. The methods in [20] or [17]
are proposed for the purpose of estimating the lower bound for the entire graph. If those methods
are used for estimating lower bounds for partial schedules, the time spent in estimation itself may
be so high that the advantage of estimation is nullified. They take O(nc 2
to compute lower bound for each partial schedule. Our method in the previous section also takes
time. In this section, we present an extension to that method such that the lower-bound from
a partial schedule can be computed more efficiently. Our method takes O(k) time, where k is the
number of ready and unfinished operations (defined later in this section) at the partial schedule.
In the rest of the paper, we call a partial schedule a configuration. If a configuration R is
the result of scheduling r time steps, any unscheduled operation at R can only be scheduled at a
time step greater than r. We call r the depth of R denoted by depth(R). Let f(v) denote the
time step at which the operation v is scheduled to start execution. An operation x is said to be
ready at R if it is not scheduled yet and if all its predecessors are scheduled and finished at R i.e.
y such that y is a predecessor of x. Note that d y is the delay of
y. The set of ready operations at R is denoted by ready(R). A multi-cycle operation x is said to
be unfinished at R if it is scheduled to start execution at a time step less than or equal to depth(R),
but not finished at depth(R) i.e. f(x) - depth(R) 1. The set of unfinished
operations at R is denoted by unfinished(R). The number of unscheduled operations of type t at
configuration R is denoted by unsch(R; t).
The basic idea behind the estimation for the partial schedules is as follows. At a partial schedule,
a subset of operations is already scheduled so as to satisfy precedence constraints as well as resource
constraints. So, instead of considering all possible values for i and j (to divide operations into
intervals), we can consider the following special case for each resource type t. For the unscheduled
portion of the DFG, we find I = maxfijoe A (i; 0g. Intuitively,
I is the number of time steps after the current step before any type t unscheduled operation can
start execution. And, J is the number of time steps that any complete schedule from the current
configuration takes after the last type t operation has finished executing. The steps in computing
a lower bound from a configuration R for a resource type t are as follows.
1. Compute I and J .
2. q(I; J; t) / unsch(R; t). (Since oe A (I;
3. Compute h(I; J; t) from q(I; J; t). (As explained in the previous section)
a lower bound on the number of time steps to schedule the
remaining operations of type t, the quantity depth(R) J is a lower bound
on the completion time of any schedule from R. The maximum of these lower bounds over all
resource types t (only if there are any unscheduled operations of type t) gives a lower bound on the
completion time of any schedule that configuration R can lead to.
The only non-trivial step in computing the lower bound is the computation of I and J (Step
1). The most important merit of our algorithm is that it computes I and J in a very efficient way
as described in Figure 2. For each node u and each operation type t, ff(u; t) is defined as the
minimum number of time steps that any type t successor of u can start after the starting time of
u. The value of ff(u; t) is set to infinity if u has no successors of type t. For each node u and each
The value for I is 0 if there is a type t operation in ready(R).
Otherwise, it is given by min(a; b) where
ff(u; t) and
is the number of time steps u finished at R.
The value for J is given by min(a; b), where
fi(u; t) and
is the set of operations in unfinished(R) with a type t successor.

Figure

2. Computing the values for I and J
operation type t, fi(u; t) is defined as the minimum number of time steps that any schedule of the
given DFG is going to take after the completion of all type t successors of u. The value for fi(u; t)
can be computed as min v fMSAT (v)g such that v is a type t successor of u. If u has no successors
of type t, then : if u is a type t operation, fi(u; otherwise, it is set to infinity. Note
that a lower bound for a type t is computed only when there are some unscheduled operations of
that type. Therefore, the values of I and J will never be infinity.
The formulas for the computation of I and J are based on the following lemma.
unscheduled operation x at configuration R, x is either a member of ready(R)
or there exists a y in (ready(R) [ unfinished(R)) such that y is a predecessor of x.
x be an unscheduled operation. If x is not in ready(R), then there is a predecessor p
of x that is not scheduled or scheduled but not finished executing. Among all such p, let q be the
farthest from x i.e. the length of the longest path from q to x is maximum among all p.
(i) If q is scheduled but not finished executing, q is in unfinished(R).
q is not in ready(R), then there is a predecessor q 1 of q that is not scheduled
or is in unfinished(R). Note that q 1 is a predecessor of x also. And, q 1 is farther than q from x,
which is a contradiction. Hence, q is in ready(R). 2
F or type +;?
completion
operation in ready(R)
completion

Figure

3. An example for the estimation of lower-bound completion time of partial schedules

Figure

3 shows an example for the estimation of lower-bound completion time of a partially
scheduled DFG. It is assumed that the scheduling of the first step is finished. There is one adder
and one multiplier both with a delay of one time-step. The lower-bound completion time is 7
time-steps. If the target performance is 6 time-steps, the lower-bound estimation suggests that the
selection of operations 2 and 3 in the first time-step is wrong.
The method in this section is especially useful for a class of scheduling algorithms that compute
the lower bound for a large number of configurations during the design space exploration. The
matrices ff and fi for all the operations in the DFG and all resource types are computed only once
before the design space exploration. This can be done by computing the transitive closure. For a
directed graph, the transitive closure can be computed using depth-first search in O(n(e+n)) where
e is the number of edges in the graph [18]. As already explained, e grows linearly in n in a DFG
since the number of inputs of each operation is generally bounded by a small number such as two.
Thus, ff and fi can be computed in O(n 2 ) time. Note that these values for only the operations in
ready(R) and unfinished(R) are used in computing the values of I and J . Hence, a lower-bound
for any configuration R can be computed in O(k) time where k is the number of operations in
Another major advantage of our method is that it introduces very little memory overhead. The
only overhead is to store the matrices ff and fi. When there are a large number of partial schedules
the memory requirement is dominated by the amount of information stored at each configuration.
Any scheduling algorithm taking full advantage of our lower-bound estimation needs to store very
little information at each configuration.
6 Extensions
6.1 Conditional Branches
We use the same approach of dividing each type of operations into three non-overlapping intervals.
As explained in section 4, the lengths of the first and the third intervals are independent of resource
constraints. The length of the second interval is a function of the total resource requirement of
the operations that should be scheduled in that interval. If there are no conditional branches, the
resource requirement is equal to the number of operations. In the presence of conditional branches,
however, more than one operation can share one resource in the same time-step. Effectively, an
operation requires only a fraction of the resource. If an operation can share resources with at most
/* Computes weights of all operations in the CDFG */
f
Partition all the operations into conditional blocks
For each operation x in the CDFG f
b /\Gamma block of x
number of blocks that have a type t operation and
mutually exclusive with the block b

Figure

4. Outline of the procedure to compute the weights of operations
other operations in the same time-step, its minimum resource requirement is 1=(n 1). We refer
to this quantity as the weight of that operation. For any given resource type t, the minimum total
resource requirement in an interval can be computed as the sum of weights of all type t operations
in that interval. Given the weights of individual operations, the computation of the sum of weights
of operations in each interval is similar to the computation of the number of operations with no
impact on the complexity. For partial schedules, we use the sum of weights of the unscheduled
operations of each type t in place of unsch(R; t) at each configuration R. Thus, the only increase
in complexity with our extension to conditional branches is due to the computation of the weights
of operations.

Figure

4 shows an outline of the procedure to compute the weights of individual operations.
We partition all the operations into blocks such that all the operations with the same conditional
behavior are placed into the same block. Since all the operations in a block have the same control
behavior, the concept of mutual exclusiveness between operations can be easily extended to blocks.
If x is a type t operation in the block b, then at any given control step x can share a resource with
at most one other type t operation from any other block that is mutually exclusive with b. Hence,
if there are n blocks that are mutually exclusive with b and that have a type t operation, then the
weight of x is 1=(n 1).
The method in [19] to handle conditional branches is extension of [20]. In their approach, for
each interval the operations from only one conditional path are considered so as to maximize the
minimum resource requirement in that interval. Since the conditional path analysis is performed for
each interval, their method is very slow. When used in scheduling algorithms for partial schedules,
the actual time spent in estimation itself can outweigh the advantage of the resultant pruning. In
comparison, our method computes the weights of operations only once and the complexity of the
remaining steps remains unchanged. Their method is based on distribute-join representation of
CDFGs which is a C-select implementation. In C-select implementation, the operations in conditional
branches cannot be executed until the corresponding condition is resolved. Many scheduling
algorithms in the recent literature allow execution of branch operations before the corresponding
conditional [24, 23, 26, 27]. This is known as speculative execution and is shown to produce faster
schedules on many benchmarks [27]. Our estimation method can support both C-select implementation
and speculative execution. In C-select implementation, the control precedences are treated
the same way as data dependencies are considered in computing ASAP and MSAT values of op-
erations. In speculative execution, control dependencies are ignored while computing ASAP and
MSAT values.
6.2 Chaining
Chaining of operations is handled by dividing time steps into time-units and extending the definitions
of MSAT and ASAP values in terms of time-units. Let the length of each time-step be T
time-units. Let - v denote the delay of an operation v in terms of time-units. If two operations u and
are chained, the functional unit executing u cannot be freed until v is finished [19]. Therefore, if
spans across time-steps, this may result in under-utilization of resources. To avoid this, we follow
the same assumption as in [19] that an operation v can be chained at the end of operation u only if
there is a enough time for v to be finished in the same time step in which u has finished execution.
This condition is imposed by the checking that - u mod T 6= 0 and
Let A(v) and M(v) be the ASAP and MSAT values of an operation in terms of time-units. The
A and M values can be recursively computed similar to the computation of ASAP and MSAT . For
any (u; v) 2 E, the earliest time-unit that the execution result of u is available for v is A(u)
However, if v cannot be chained to u, v can start execution only at the beginning of the next time
step. Hence, A(v) is given by:
can be chained to u
cannot be chained to u.
Similarly, M(v) is given by:
ae(v;
can be chained to v
cannot be chained to v.
From the A and M values, the corresponding ASAP and MSAT values are derived. The lower-bound
is then computed using the ASAP and MSAT values as explained in section 4.
7 Experimental Results
We implemented our methods in C language on a SUN Sparc-2 workstation. We tested them using
a number of benchmarks in the literature. The benchmarks we used are the AR Filter [6], the fifth-order
elliptic Wave Filter [13], twice unfolded Wave Filter, the complex Biquad recursive digital
Filter [13], the sixth-order elliptic Bandpass Filter [13], Discrete Cosine Transform [11], and Fast
Discrete Cosine Transform [9]. For the Biquad Filter example, we used three time steps for the
multiplier and one for adder (we used the same resource type adder to do addition, subtraction
and comparison). For all the other examples, we used two time steps for multiplication and one for
adder.
7.1 Lower bound estimation of partial schedules in branch and bound methods
As mentioned in section 1 , branch and bound scheduling methods rely on estimating lower bounds
for partial schedules to keep the design space from exploding. Generally, lower bounds need to
be estimated for a large number of partial schedules (configurations). If the time spent in lower-bound
estimation itself is too high, it will have a big negative impact on the over-all time taken
by the scheduling algorithm. We implemented a branch and bound scheduling algorithm [3] and
tested on the benchmarks. We first find a schedule using a list scheduling algorithm. We use that
performance as an upper bound in the branch and bound algorithm and search the design space
exhaustively for an optimum schedule. From each partial schedule, we estimate a lower bound for
the schedule completion time. If it exceeds the upper-bound, the partial schedule cannot lead to a
complete schedule with the target performance and it is not explored further.
We separately measured the time spent in lower-bound estimation using our method of section 5
and Rim's method [17]. The results are reported in table 1. Our method is at least 20 times faster
in all cases. As a measure of the effectiveness of the lower-bound estimation in reducing the size
of the search space, we also measured the number of configurations visited using each method
separately. These results are also reported in table 1. Both the methods are equally effective. Since
their estimation is very slow, the CPU time taken using their method is more than the time taken
without using any lower-bound estimation in a few cases. However, in a majority of the cases, the
search space exploded without lower-bound estimation, thus showing the necessity of estimation in
Resources Configurations
Our method Rim [17] Our method Rim
AR Filter 2 3 0.35 8.2 1769 3497
Once unrolled 2 3 0.13 2.9 770 723
Twice unrolled
Filter 2 3 4.0 81.2 33182 27767
Filter
Fast Discrete 1 1 0.14 3.1 688 892

Table

1. CPU time and number of configurations in branch and bound algorithm
branch and bound scheduling algorithms. Our method is more suitable than the existing methods
to be used in such scheduling algorithms. We incorporated this method in a dynamic programming
scheduling (DPS) algorithm [1] that we developed and obtained excellent results.
7.2 Lower-bound estimation for the entire DFGs
We tested all the benchmarks with different resource constraints for pipelined multiplier (latency
is 1) and non-pipelined multiplier. For all the cases, our lower bound is compared with an optimal
solution we obtained using our DPS algorithm [1]. In tables 2 and 3, we present the lower bounds
for some of the cases as obtained by our method of section 4 . The column DPS in the tables shows
the number of steps in an optimal solution. The lower bound is tight in 156 out of 198 cases. In 22
more cases, the difference is only one step. We also implemented the algorithms by Rim [17] and
Sharma [20], and compared the results with ours. Our method gives better lower bound than [17]
in nine cases. In five cases, our lower bounds are better than [20]. In [17], the lower bounds by one
more method, Jain [7] are also reported. Those are copied into the second last column (Jain) of our
our lower bound and an
Resources optimum solution other lower bounds
lower bound difference Rim [17] Jain [7] Sharma [20]
AR Filter 1 3
Twice unrolled
Wave Filter 3 2 50 50 0 50
Fast
(*) Complex multiplication takes 3 time steps
(y) Our lower bound for this case is better than Rim's
(z) Our lower bound for this case is better than Sharma's

Table

2. Lower bounds with non-pipelined multiplier
tables. For the benchmarks and cases not reported in our tables, our lower bounds are identical to
Rims' [17]. The average CPU times are 21 ms, 25 ms and 270 ms for our method, Rim's method
and Sharma's method respectively. Thus, our method is faster than the fastest non-trivial method
in the literature [17] and produces better lower bounds in more cases. Our method is one order
faster than the method in [20] and still produces better results in some cases. The lower bounds
of [7] are far inferior to ours.
our lower bound and an
Resources optimum solution other lower bounds
lower bound difference Rim [17] Jain [7] Sharma [20]
Fast 1 1 26 26 0 26 - 26
Transform
(*) Complex multiplication takes 3 time steps

Table

3. Lower bounds with pipelined multiplier
7.3 Results for CDFGs

Table

4 shows the results for examples with conditional behavior - Maha from [14], Parker from
High Level Synthesis Benchmark Suite, Kim from [25], Waka from [22] and MulT from [23]. The
resources column lists the number of adders, subtracters and comparators used in each case. All
additions, subtractions and comparisons are single-cycle. We presented the number of time steps in
the schedules obtained by our DPS algorithm. The lower bounds in all but a few cases are tight. We
obtained schedules both with C-select implementation and by allowing speculative execution. In
C-select implementation, operations from mutually exclusive branches can always share resources.
However, since control precedences are strict precedences, critical path length may increase. In
table 4, Maha and Parker are two examples with a high degree of branching. In the C-select imple-
mentation, the advantage of conditional resource sharing is nullified by the increase in the critical
path length. The length of the schedules could not be reduced even by adding more resources. In
comparison, speculative execution gives much superior results and adding more resources reduces
schedules lengths.
Benchmark Resources # Time Steps
C-select Spec. Exec.
Maha 1,1,1 11 y7
Maha 2,1,1 11 y6
Maha 2,2,2 11 5
Parker 1,1,1 11 y6
Parker 2,2,1 11 5
Parker 2,2,2 11 5
y For these cases, lower bound is one step less. All other lower bounds are tight.

Table

4. C-select and Speculative execution in Conditional Branch benchmarks
8 Conclusions and future research
We have presented simple and efficient techniques for estimating lower-bound completion time for
the scheduling problem. The proposed techniques can handle multi-cycle operations, pipelined
functional units, conditional branches and chaining of operations. Our method for the entire DFGs
is faster and produces better lower bounds than [17] and [20].
We have also presented an extension to our technique that is especially suitable for finding lower-bound
for partially scheduled DFGs. The extended method is very useful to keep the search space
from exploding in scheduling algorithms such as branch and bound method. Exising methods in the
literature do not give any special consideration for computing the lower bounds for partial schedules.
We conducted extensive experiment using our method and the fastest non-trivial method known
in the literature [17] for the estimation of partial schedules in a branch and bound algorithm. Our
method is found to be at least 20 times fatser than theirs while being equally effective in reducing
the size of the search space.
We are currently investigating estimation of lower bounds in the presence of loops and when
multi-function functional units are used. We are also investigating estimation of lower bounds with
additional constraints such as interconnect and storage.



--R

"Optimum Dynamic Programming Scheduling under Resource Constraints"
"A Multi-Schedule Approach to High-Level Synthesis"
"Some Experiments in Local Microcode Compaction for Horizontal Machines"
"Bounds on the Number of processors and Time for Multi-processor Optimal Schedules"
"Lower Bounds on the Iteration Time and the Number of Resources for Functional Pipelined Data Flow Graphs"
"Experience with the ADAM Synthesis System"
"Predicting system-level area and delay for pipelined and non-pipelined designs"
"A Recursive Technique for Computing Lower-Bound Performance of Schedules"
"A new approach to pipeline optimization"
"Comprehensive Lower Bound Estimation from Behavioral Descriptions"
"Personal Communication"
"Slicer: A State Synthesizer for Intelligent Silicon Compiler"
"A High Level Synthesis Technique Based on Linear Pro- gramming"
"MAHA: A Program for Datapath Synthesis"
"SEHWA: A Software Package for Synthesis of Pipelines for Synthesis of Pipelines from Behavioral Specifications"

"Lower-Bound Performance Estimation for the High-Level Synthesis Scheduling Problem"
"Algorithms in C"
"Estimation and Design Algorithms for the Behavioral Synthesis of ASICS"
"Estimating Architectural Resources and Performance for High-Level Synthesis Applications"
"Estimating Implementation Bounds for Real Time DSP Application Specific Circuits"
"A resource sharing and control synthesis method for conditional branches"
"Global Scheduling Independent of Control Dependencies Based on Condition Vectors"
"A Tree-Based Scheduling Algorithm For Control-Dominated Circuits"
"A Scheduling Algorithm For Conditional Resource Sharing"
"Global Scheduling For High-Level Synthesis Applications"
"A New Symbolic Technique for Control-Dependent Scheduling"
--TR
Experience with ADAM synthesis system
Algorithms in C
Global scheduling independent of control dependencies based on condition vectors
A tree-based scheduling algorithm for control-dominated circuits
Comprehensive lower bound estimation from behavioral descriptions
Global scheduling for high-level synthesis applications
MAHA
A Multi-Schedule Approach to High-Level Synthesis
Estimation and design algorithms for the behavioral synthesis of asics
A new approach to pipeline optimisation

--CTR
Shen Zhaoxuan , Jong Ching Chuen, Lower bound estimation of hardware resources for scheduling in high-level synthesis, Journal of Computer Science and Technology, v.17 n.6, p.718-730, November 2002
Helvio P. Peixoto , Margarida F. Jacome, A new technique for estimating lower bounds on latency for high level synthesis, Proceedings of the 10th Great Lakes symposium on VLSI, p.129-132, March 02-04, 2000, Chicago, Illinois, United States
Margarida F. Jacome , Gustavo de Veciana, Lower bound on latency for VLIW ASIP datapaths, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.261-269, November 07-11, 1999, San Jose, California, United States
Margarida F. Jacome , Gustavo de Veciana, Lower bound on latency for VLIW ASIP datapaths, Readings in hardware/software co-design, Kluwer Academic Publishers, Norwell, MA, 2001
Margarida F. Jacome , Gustavo de Veciana , Viktor Lapinskii, Exploring performance tradeoffs for clustered VLIW ASIPs, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
high-level synthesis;lower-bound estimated;dynamic programming;scheduling