Incorporating speculative execution into scheduling of control-flow intensive behavioral descriptions.
Speculative execution refers to the execution of parts of a computation before the execution of the conditional operations that decide whether it needs to be executed. It has been shown to be a promising technique for eliminating performance bottlenecks imposed by control flow in hardware and software implementations alike. In this paper, we present techniques to incorporate speculative execution in a fine-grained manner into scheduling of control-flow intensive behavioral descriptions. We demonstrate that failing to take into account information such as resource constraints and branch probabilities can lead to significantly sub-optimal performance. We also demonstrate that it may be necessary to speculate simultaneously along multiple paths, subject to resource constraints, in order to minimize the delay overheads incurred when prediction errors occur. Experimental results on several benchmarks show that our speculative scheduling algorithm can result in significant (upto seven-fold) improvements in performance (measured in terms of the average number of clock cycles) as compared to scheduling without speculative execution. Also, the best and worst case execution times for the speculatively performed schedules are the same as or better than the corresponding values for the schedules obtained without speculative execution.
Introduction
Speculative execution refers to the execution of a part of a computation
before it is known if the control path to which it belongs
will be executed (for example, execution of the code after a branch
statement before the branch condition itself is evaluated). It has
been used to overcome, to some extent, the scheduling bottlenecks
imposed by control-flow. There has been previous work on speculative
execution in the areas of high-level synthesis [1, 2, 3] as well
as high-performance compilation [4, 5].
Previous work [1, 2, 3] in high-level synthesis has attempted
to locate single or multiple paths for speculation prior to schedul-
ing. This paper presents techniques to integrate speculative execution
into scheduling during high-level synthesis of control-flow
intensive designs. In that context, we demonstrate that not using
information such as resource constraints and branch probabil-
* This work was supported in part by NSF under Grant No. 9319269 and
in part by Alternative System Concepts, Inc. under an SBIR contract from
Air Force Rome Laboratories.
Permissions to make digital/hard copy of all or part of this work for personal
or classroom use is granted without fee provided that copies are not made
or distributed for profit or commercial advantage, the copyright notice, the
title of the publication and its date appear, and notice is given that copying
is by permission of ACM, Inc. To copy otherwise, to republish, to post on
servers or to redistribute to lists, requires prior specific permission and/or a
fee.
DAC 98, San Francisco, California
ities while deciding when to speculate can lead to significantly sub-optimal
performance. We also demonstrate that it is necessary to
perform speculative execution along multiple paths at a fine-grain
level during the course of scheduling, in order to obtain maximal
benefits. In addition, we present techniques to automatically manage
the additional speculative results that are generated by speculatively
executed operations. We show how to incorporate speculative
execution into a generic scheduling methodology, and in particular
present the results of its integration into an efficient scheduler
Wavesched [6]. Experimental results for various benchmarks
and examples are presented that indicate upto seven-fold improvement
in performance (average number of clock cycles required to
perform the computation).
Background and Motivation
Scheduling tools typically work using one or more intermediate
representations of the behavioral description, such as a data flow
graph (DFG), control flow graph (CFG), or control-data flow graph
(CDFG). In this paper, we use the CDFG as the intermediate representation
of a behavioral description, and state transition graphs
(STGs) to represent the scheduled behavioral description, as explained
in later sections. In addition to the behavioral description,
our scheduler also accepts the following information:
ffl A constraint on the number of resources of each type available
(resource allocation constraints).
ffl The target clock period for the implementation, or constraints
that limit the extent of data and control chaining allowed.
ffl Profiling information that indicates the branch probabilities
for the various conditional constructs present in the behavioral
description.
We now present some motivational examples to illustrate the use
of speculative execution during scheduling.
Consider a part of a behavioral description and the
corresponding CDFG fragment shown in Figure 1, that contains a
while loop. The CDFG contains vertices corresponding to operations
of the behavioral description, where solid lines indicate data
dependencies, and dotted lines indicate control dependencies. Control
edges in the CDFG are annotated with a variable that represents
the result of the conditional operation that generates them. For ex-
ample, the control edges fed by operation > 1 are marked c in Figure
1. The initial values of variables i and t 4 used in the loop body
are indicated in parentheses beside the corresponding CDFG data
edges.
Let us now consider the task of scheduling the CDFG shown
in

Figure

1. Suppose we have the following constraints to be used
during scheduling.
while (k > t4) {
c
c

Figure

1: A CDFG to illustrate speculative execution
S5
S5
++1_5, M1_4, *1_2, *1_3,
*2_1, *2_2, +1_0
*2_2, *2_3, +1_1, M2_0
*2_3, *2_4, +1_2, M2_1
M1_1/c_1, *1_0
(a) (b)

Figure

2: (a) Non-speculative schedule for the CDFG of Figure 1,
and (b) schedule incorporating speculative execution
ffl The target clock period allows the execution of +, ++, >, and
memory access operations in one clock cycle, while the * operation
requires two clock cycles. In addition, we assume that
the * operation will be implemented using a 2-stage pipelined
multiplier.
chaining is allowed, since it leads to a violation
of the target clock period constraint (in general, however, our
algorithm can handle chaining).
ffl The aim is to optimize the performance of the design as much
as possible. Hence, no resource constraints are specified for
the purposes of illustration for this example. This is not a
limitation of our scheduling algorithm, which does handle resource
constraints as described in later sections.
A schedule for the CDFG that does not incorporate speculative
execution is shown in Figure 2(a). This schedule can be obtained
by applying either the loop-directed scheduling [7] technique or the
Wavesched [6] technique to the CDFG. Vertices in the STG represent
schedule states, that directly correspond to states in the controller
of the RTL implementation. Each state is annotated with
the names of the CDFG operations that are performed in that state,
including a suffix that represents a symbolic iteration index of the
CDFG loop that the operation belongs to. For example, consider
operation > 1 of the CDFG. When > 1 is encountered the first time
during scheduling, it is assigned a subscript 0, resulting in operation
in the STG of Figure 2(a). In general, multiple copies of
an operation may be generated during scheduling, corresponding to
different conditional paths, or different iterations of a loop. For ex-
ample, operation > 1 1 in the STG of Figure 2(a) corresponds to
the execution of the first unrolled instance of CDFG operation > 1.
An edge in the STG represents a controller state transition, and is
annotated with the conditions that activate the transition.
Each iteration of the loop in the scheduled CDFG requires eight
clock cycles. For this example, the data dependencies among the
operations within the loop require them to be performed serially.
In addition, the control dependencies between the comparison operation
together with the inter-iteration
data dependency 1 from +1 to > 1, prevent the parallel
computation of multiple loop iterations, even when loop unrolling
is employed.
A schedule for the CDFG of Figure 1 that incorporates speculative
execution is shown in the STG of Figure 2(b). This schedule
was derived by techniques we present in later sections. Speculatively
executed operations are annotated with the conditional operations
whose results they depend upon, using the following
tion. op/cond represents an operation op that is executed assuming
that the speculation condition cond will evaluate to t rue. The
speculation condition cond could, in general, be an expression that
is a conjunction of the results of various conditional operations in
the STG. For example, consider operation ++1 1/c 1 in state S1 of

Figure

2(b). This is a speculatively executed operation, that corresponds
to the second instance of CDFG operation in the
schedule, and assumes that the result of conditional operation > 1 1,
which is executed only in state S7, is going to be true. States S7 and
S8 represent the steady state of the schedule. Note that, when in the
steady state, a new iteration is initiated every cycle, as opposed to
once in eight cycles.
The following example illustrates the impact of branch probabilities
and resource constraints on the performance of speculatively
derived schedules and makes a case for the integration of
speculation into the scheduling process.
Consider the example CDFG shown in Figure 3. The
select operation Sel1 selects the data operand at its l (r) port if
the value at its s port is 1 (0). Figure 4 shows three different
schedules that use speculative execution, that were generated using
different resource constraints and branch probabilities. The STG
of

Figure

4(a) was generated assuming the following information.
Available resources consist of one incrementer (++), one adder(+),
An intra-iteration data or control dependency is between operations that
correspond to the same iteration of a loop, while an inter-iteration dependency
is between operations in different (e.g., consecutive) iterations. We
refer to intra-iteration data and control dependencies simply as data and
control dependencies.
a
out
>>1c d
e
s
l r

Figure

3: CDFG demonstrating the effect of resource constraints
and branch probabilities on speculative execution



(a) (b) (c)

Figure

4: Three speculative schedules derived using different resource
constraints or branch probabilities
one comparator (>), one shifter (>>), and one multiplier (*), all of
which require one cycle. Also, the probability of comparison > 1
evaluating to f alse is higher than it evaluating to true. Since the
result of > 1 evaluates to f alse more often, the schedule of Figure
4(a) gives preference to executing operations from the corresponding
control path (e.g., +2). As a result, +2 is scheduled to
be performed on the sole adder in state S0, as opposed to +1, even
though the data operands for both operations are available. The average
number of clock cycles, CC a , required for the STG in Figure
4(a) can be calculated as follows.
In the above equation, P(c1) represents the probability that the result
of comparison > 1 evaluates to true.
The STG of Figure 4(b) was derived with the same information
above, except that it was assumed that comparison > 1 evaluates
to true more often than it evaluates to f alse. Hence, operation +1
is given preference over operation +2 and is scheduled in S0. The
average number of clock cycles, CC b , required for the STG in Figure
4(b) is given by the following expression
Suppose the resource constraints were relaxed to allow two adders.
The speculative schedule that results is shown in Figure 4(c). The
average number of clock cycles, CC c , required for the STG in Figure
4(c) is given by the following expression.
Expected
Number
of
Cycles
CC a

Figure

5: Comparison of the speculative schedules
The values of CC a , CC b , and CC c for various values of P ranging
from 0 to 1 are plotted in Figure 5. As expected, the schedule
of

Figure

4(a) outperforms the schedule of Figure 4(b) when
P(c1) < 0.5, and the schedule of Figure 4(b) performs better when
0.5. Moreover, the schedule of Figure 4(c), which was derived
using one extra adder, outperforms the other two schedules
for all values of P(c1). Thus, we can conclude that branch probabilities
and resource constraints do influence the trade-offs involved
in deciding which conditional paths to speculate upon, making the
case for the integration of speculative execution into the scheduling
step where such information is available.
The following example illustrates that it is necessary to perform
speculative execution along multiple paths, in a fine-grained man-
ner, in order to obtain maximal performance improvements.
schedules shown in Figure 4 were all generated
S5

Figure

Speculation along a single path
by speculatively executing operations from both the conditional
paths of the CDFG in a fine-grained manner, as allowed by the resource
constraints. For the purpose of comparison, we scheduled
the CDFG shown in Figure 3, assuming the same scheduling information
that was assumed to derive the schedule of Figure 4(b).
However, in this case, we restricted the scheduler to allow speculative
execution along only one path. The resulting schedule is shown
in

Figure

6. The average number of clock cycles, CC d , required for
the STG in Figure 6 is given by the following expression.
Comparing the expression for CC d to the expression for CC b from
the previous example indicates that CC d CC b for all feasible values
of P(c1). Thus, in this example, simultaneously speculating
along multiple paths according to resource availability results in
a schedule that is provably better than one derived by speculating
along only the most probable path. Our scheduling algorithm automatically
decides the best paths to speculate upon for the given
resource constraints and branch probabilities.
3 The Algorithm
In this section, we present the changes that need to be made to a
generic scheduling algorithm to support speculative execution.
3.1 A generic scheduling algorithm

Figure

7 shows the pseudocode for a generic scheduling algo-
rithm. The inputs to the scheduler are a CDFG, G, to be sched-
Generic scheduler (CDFG G, ALLOCATION CONSTRAINT K,
MODULE SELECTION INFO M inf , CLOCK PERIOD clk) f
SET  Unscheduled operations;
SET  Schedulable operations;
while (jUnscheduled operationsj >
schedulable operation
(Schedulable operations, K, M inf , clk);
//Select an operation for scheduling. The selected
// operation must honor allocation and clock cycle constraints
Unscheduled operations.remove operation(op);
5 Schedulable operations.remove operation(op);
6 SET  schedulable successors = Compute-
schedulable successors(op);//Find the set of operations
// in op's fanout which become schedulable when op is scheduled
7 Schedulable operations.append(schedulable successors);
//Augment Schedulable operations by addition of
//operations in schedulable successors
gg

Figure

7: Pseudocode for a generic scheduling algorithm
uled, the target clock period of the design, allocation constraints,
which specify the numbers and types of functional units available,
and module selection information, which gives the type of functional
unit an operation is mapped to. The output of the scheduler
is an STG which describes the schedule. At any point, a
generic scheduler maintains (a) the set of unscheduled operations
whose data and control dependencies have been satisfied, and can
therefore be scheduled (Schedulable operations), and (b) the set
of operations which are unscheduled (Unscheduled operations).
The scheduling process proceeds as follows: an operation from
Schedulable operations is selected for scheduling in a given state
(statement 2). The selection should honor allocation and clock cycle
constraints. The manner in which the selection is done varies
from one scheduling algorithm to another. The selected operation,
op, is scheduled in the state. Since op no longer belongs to either
Schedulable operations or Unscheduled operations, it is removed
from these sets (statements 4 and 5). Also, the scheduling
of op might render some of the operations in its fanout schedu-
lable. The routine Compute schedulable successors (statement
identifies such operations, and these operations are subsequently included
in the set Schedulable operations (statement 7).
3.2 Incorporating speculative execution into a
generic scheduler: An overview
We now provide an overview of the changes that need to be
made to incorporate speculative execution into the framework of
the generic scheduler shown in Figure 7.
To support speculative execution, the generic scheduler shown
in

Figure

7 needs to be modified as follows (the details of these
steps are provided in Section 3.3).
1. When an operation is scheduled, one needs to recognize all
its schedulable successors, including the ones which can be
s
r

Figure

8: A CDFG fragment illustrating speculative execution
speculatively scheduled. In addition, speculatively executed
operations and their successors need to be specially marked.
Clearly, procedure Compute schedulable successors needs to
be augmented to consider such cases. Note that, at any stage,
every speculatively schedulable operation is added to the list
of schedulable operations. However, few of them are actually
scheduled. Operations which are not worth being speculated
on are ignored, and eventually removed from the list
of schedulable operations, using procedures described later in
this section.
Example 4: Consider the CDFG fragment shown in Figure
8. We assume that operation op0 is scheduled, operation
op2 has just been scheduled, and operations op1, op3,
Sel1, and op4 are unscheduled. The output of the routine
Compute schedulable successors(op2) must include operation
op4, which can now be speculatively executed, i.e., its
operands can be assumed to be the results of operations op2
and op0.
2. When operations are scheduled, control and data dependencies
of speculatively executed operations are resolved. This
would potentially validate or invalidate speculatively performed
operations. Operations which are validated should
be considered "normal", i.e., they need not be specially
marked any longer. Operations in Unscheduled operations
and Schedulable operations which are invalidated need no
longer be considered for scheduling. They can, therefore, be
removed from these sets. In general, the resolution of the control
or data dependencies of a speculatively performed operation
creates two separate threads of execution, which correspond
to the success and failure of the speculation.
Example 5: Consider again, the CDFG fragment shown in

Figure

8. Suppose operations op0, op2 and op4 have been
scheduled, and operation op3 is unscheduled. Operation op4
uses as its operands, the results of operations op2 and op0.
Assume that operation op1 has just been scheduled. If op1
evaluates to true, then the execution of op4 can be considered
fruitful, because the operands chosen for its computation
are correct. Therefore, op4, and its scheduled and schedulable
successors need not be considered conditional on the result of
op1 anymore, and the data structures can be modified to reflect
this fact. If, however, op1 evaluates to false, then op4
should use as its operands, the results of operations op3 and
op0, thus invalidating the result of our speculation. There-
fore, schedulable operations, whose computations are influenced
by the result computed by op4 are invalid, and can be
removed from the set Schedulable operations.
3. The set, Schedulable operations, from which an operation
is selected for scheduling, contains operations whose execution
is speculative, i.e., whose results are not always use-
ful. The selection procedure, represented by the routine Select
schedulable operation() (statement 2), needs to be modified
to account for this fact. For example, operations, whose
execution is extremely improbable, would make poor selection
candidates, as the resources consumed by them might be
better utilized by operations whose execution is more proba-
ble. Also, operations, which fall on critical paths, would be
better candidates for selection than those on off-critical paths.
3.3 Incorporating speculative execution into a
generic scheduler: A closer look
In this section, we fill in the details of the changes outlined in
Section 3.2. This is preceded by a formal treatment of concepts
related to speculative execution.
A scheduler which supports speculative execution works with
conditioned operations as its atomic schedulable units, just as a
normal scheduler uses operations. Therefore, the fanin-fanout relationships
between operations, captured by the CDFG, need to
be defined for conditioned operations. Since all speculatively performed
operations are conditioned on some event, the adjective
"speculatively performed" when applied to an operation, implies
that it is conditioned on some event or combination of events.
As mentioned in Section 3.2, when an operation is scheduled,
its schedulable successors need to be computed.
s
r
l
s
r

Figure

9: Illustrating the scheduling of successors of speculatively
performed operations
Consider the CDFG fragment shown in Figure 9. Assume
that operations op5 and op6 have been scheduled, operations
op1, op3, and op4 are unscheduled, and op2 has just been sched-
uled. It is now possible to schedule two versions of operation op7,
with the first version, op7 0 , using op2 and op5 as its operands,
and the second, op7 00 using op2 and op6. op7 0 is conditioned on
c(op1)  c(op4), and op7 00 is conditioned on c(op1)  c(op4). The
following analysis presents a structured means of identifying such
relationships.
We now present a result which helps derive fanin-fanout relationships
among speculatively performed operations.
Lemma 1: Consider an operation, op, whose fanins are op1, op2,
., opn. If the fanins of op have been speculatively scheduled, so
can op. In particular, if the ith fanin, opi, is conditioned on C i , then
op would be conditioned on V n
We now present details of Steps 1, 2, and 3, outlined in Section
3.2.
Step 1: This step addresses the issue of deriving all schedulable
successors of a scheduled operation, op0. The result of Lemma 1 is
used for this procedure.
scheduled op-
erations, which satisfies the following condition sources a schedulable
operation.
Condition: There exits an operation, fanout, in the CDFG, all of
whose fanins are reachable from the outputs of the operations in S
through paths which consist exclusively (if at all) of select opera-
tions. The path connecting the output of an operation opj in S to
an input of fanout is denoted by Pj, and the operations on Pj are
. Note that aj can equal represents the
condition that path Pj is selected, i.e., the result of operation op j is
propagated through path Pj to the appropriate input of fanout. Operation
fanout is conditioned on V
represents the expression opk is conditioned on.
Observation 1 can be used to infer the schedulable successors
of an operation. The procedure Compute schedulable successors,
which is called in statement 6 of the pseudocodeshown in Figure 7,
is appropriately augmented.
So far, we have described the technique used to identify all
schedulable successors of an operation. This was accomplished
by tagging operations with the conditions under which their results
would be valid. Note that our procedure allows us to speculate
on all possible outcomes of a branch, and arbitrarily deeply
into nested branches. If integrated with a scheduler which supports
loop unrolling, the speculation could also cross loop boundaries.
We now present the technique used to validate or invalidate speculatively
performed operations whose dependencies have just been
resolved.
Step 2: Suppose operation op s , which resolves a condition c, has
just been scheduled. The resolution of c results in the creation of
two different threads of execution, where (i) true, and (ii)
false. The following procedure is carried out for every operation,
which belongs either to the set, Schedulable operations, or the
set of scheduled operations. Let op be conditioned on
In the true (false) branch, C is evaluated assuming a value of 1 (0)
for c, and the resultant expression is the new expression that op is
conditioned on.
Step 3: We now describe the procedure employed by the scheduler
to select an operation to schedule, from a pool of schedulable oper-
ations, Schedulable operations. Schedulable operations can contain
operations which are conditioned on different sets of events,
i.e., we can choose different paths to speculate upon. We need to
decide the "best" candidate to map to a given resource, where, by
best, we mean the operation whose mapping on the given resource
would minimize the expected number of cycles for the schedule.
Formally, the problem can be stated as follows: given (i) a partial
schedule, (ii) a functional unit, fu, (iii) a set of operations, S (some
of which may be speculative), which can execute on the functional
unit, and (iv) typical input traces, select the operation, which, if
mapped to fu, would minimize the expected number of cycles.
The above problem has been proven to be NP-complete, even
for conditional- and loop-free behavioral descriptions [8]. We,
therefore, use the following heuristic, whose guiding principle has
been successfully employed by several scheduling algorithms [9].
The heuristic is based on the following premise: operations in the
CDFG which feed primary outputs through long paths are more
critical than operations which feed primary outputs through short
paths and, therefore, need to be scheduled earlier. The rationale behind
this heuristic is that operations which belong to short paths are
more mobile than those on long paths, i.e., the total schedule length
is less sensitive to variations in their schedules. The length of a path
is measured as the sum of the delays of its constituent operations.
In data-dominated descriptions, with no loops and conditional
operations, the longest path between any pair of operations is fixed.
In control-flow intensive descriptions, some paths could be input-
dependent. Therefore, the longest path between a pair of operations
must be defined with respect to a given input. For example, for the
CDFG shown in Figure 3, the longest path connecting primary input
c with output out depends upon the value taken by operation
> 1. Since our scheduling algorithm is geared towards minimizing
the average execution time, we use the expected length of the
longest path from an operation to a primary output as a metric to
rank different operations. We use the notation l(op) to denote this
quantity for operation op.
Speculation adds a new dimension to this problem: the result
computed by an operation is not guaranteed to be useful. For an

Table

1: Expected number of cycles, number of states, best-
and worst-case number of cycles results
Circuit E.N.C. #states bc wc
WS SP WS SP WS SP WS SP
Barcode
GCD 95
Findmin 522 265 4

Table

2: Allocation constraints for the examples in Table 2
Circuit add1 sub1 mult1 comp1 eqc1 inc1
Findmin
operation, op, we account for this effect by multiplying the probability
that an operation's output is utilized with l(op) to derive a
metric of an operation's criticality. This is expressed by means of
the following equation:
where criticality(op) measures the desirability of scheduling op,
is the product of the probabilities of the events that op is
conditioned on, and l(op) is as defined above.
4 Experimental Results
The techniques described in this paper were implemented in a
program called Wavesched-spec, written in C++. We evaluated this
program by using it to produce schedules for several commonly
available benchmarks. These schedules were compared against
those produced by the scheduling algorithm, Wavesched [6], without
the use of speculative execution, with respect to the following
metrics: (a) expected number of cycles, (b) number of states in
the STG produced, (c) the smallest number of cycles taken to execute
the behavioral description, and (d) the largest number of cycles
taken to execute the behavioral description. In general, finding
the largest number of cycles taken to execute a behavioral description
is a hard problem. However, for the examples considered in
this paper, static analysis of the description was sufficient to find
the number.

Table

1 summarizes the results obtained. The columns labeled
#states, bc, and wc represent, respectively, the expected
number of cycles, the number of states in the STG produced, smallest
number of cycles taken to execute the STG, and the largest number
of cycles taken to execute the STG. Minor columns WS and
produced by Wavesched and Wavesched-
spec, respectively. We used a library of functional units which
consisted of (a) an adder, add1, (b) a subtracter, sub1, (c) a mul-
tiplier, mult1, (d) a less-than comparator, comp1, (e) an equality
comparator, eqc1, and (f) an incrementer, inc1. Unlimited numbers
of single-input logic gates (OR, AND, and NOT) were assumed to
be available. All functional units except mult1, which executes in
two cycles, take one cycle to execute. The allocation constraints for
an example can be found by looking up the entry corresponding to
the example in Table 2. For example, the allocation constraints for
GCD are two sub1, one comp1, and two eqc1.
The expected number of cycles for the final design was measured
by simulating a VHDL description of the schedule using the
SynopsysVSS simulator. The input traces used for simulation were
obtained as zero-mean Gaussian sequences.
Of our examples, Barcode, GCD, TLC, and Findmin are borrowed
from the literature. Test1 is the example shown in Figure 1.
Barcode represents a barcode reader, GCD computes the greatest
common divisor of its inputs, TLC represents a traffic light con-
troller, and Findmin returns the index of the minimum element in
an array.
The results obtained indicate that Wavesched-spec produced an
average expected schedule length speedup of 2.8 over schedules
obtained using Wavesched. Note that Wavesched [6] was reported
to have achieved an average speedup of 2 over schedules produced
by existing scheduling algorithms, such as path-based scheduling
[10], and loop-directed scheduling [7]. To get an idea of the
area overhead of this technique, we obtained a 16-bit RTL implementation
for the GCD example using an in-house high-level synthesis
system, for the schedules produced by Wavesched-spec and
Wavesched. These RTL circuits were technology-mapped using the
MSU library, and the area of the gate-level circuits were obtained.
The area overhead for the circuit produced from Wavesched-spec
was found to be only 3.1%. We also note that for Wavesched-spec,
the number of cycles in the shortest and longest paths is smaller
than or equal to the corresponding number for Wavesched.
Conclusions
In this paper, we presented a technique for incorporating speculative
execution into scheduling of control-flow intensive designs.
We demonstrated that in order to fully exploit the power of speculative
execution, one needs to integrate it with scheduling. We introduced
a node-tagging scheme for the identification of operations
which can be speculatively scheduled in a given state, and a heuristic
to select the "best" operation to schedule. Our techniques were
fully integrated into an existing scheduling algorithm which can
support implicit unrolling of loops, functional pipelining of control-flow
intensive behaviors, and can parallelize the execution of independent
loops whose bodies share resources. Experimental results
demonstrate that the presented techniques can improve the performance
of the generated schedule significantly. Schedules produced
using speculative execution were, on an average, 2.8 times faster
than schedules produced without its benefit.



--R

"Experiments with low-level speculative computation based on multiple branch prediction,"
"Global scheduling independent of control dependenciesbased on condition vectors,"
"Combining MBP-speculative computation and loop pipelining in high-level synthesis,"
"Trace scheduling: A technique for global microcode compaction,"
"Sentinel scheduling: A model for compiler-controlled speculative execution,"
"Wavesched: A novel scheduling technique for control-flow intensive behavioral de- scriptions,"
"Performance analysis and optimization of schedules for conditional and loop-intensive specifica- tions,"
Computers and Intractibility.
"Empirical evaluation of some high-level synthesis scheduling heuristics,"
"Path-based scheduling for synthesis,"
--TR
Global scheduling independent of control dependencies based on condition vectors
Empirical evaluation of some high-level synthesis scheduling heuristics
Sentinel scheduling
Performance analysis and optimization of schedules for conditional and loop-intensive specifications
<italic>Wavesched</italic>
Computers and Intractability
Combining MBP-speculative computation and loop pipelining in high-level synthesis

--CTR
Sumit Gupta , Nick Savoiu , Sunwoo Kim , Nikil Dutt , Rajesh Gupta , Alex Nicolau, Speculation techniques for high level synthesis of control intensive designs, Proceedings of the 38th conference on Design automation, p.269-272, June 2001, Las Vegas, Nevada, United States
Sumit Gupta , Nikil Dutt , Rajesh Gupta , Alex Nicolau, Dynamic Conditional Branch Balancing during the High-Level Synthesis of Control-Intensive Designs, Proceedings of the conference on Design, Automation and Test in Europe, p.10270, March 03-07,
Sumit Gupta , Nick Savoiu , Nikil Dutt , Rajesh Gupta , Alex Nicolau , Timothy Kam , Michael Kishinevsky , Shai Rotem, Coordinated transformations for high-level synthesis of high performance microprocessor blocks, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA
Satish Pillai , Margarida F. Jacome, Compiler-Directed ILP Extraction for Clustered VLIW/EPIC Machines: Predication, Speculation and Modulo Scheduling, Proceedings of the conference on Design, Automation and Test in Europe, p.10422, March 03-07,
Sumit Gupta , Nick Savoiu , Nikil Dutt , Rajesh Gupta , Alex Nicolau, Conditional speculation and its effects on performance and area for high-level snthesis, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montral, P.Q., Canada
Soha Hassoun, Fine grain incremental rescheduling via architectural retiming, Proceedings of the 11th international symposium on System synthesis, p.158-163, December 02-04, 1998, Hsinchu, Taiwan, China
Luiz C. V. dos Santos , Jochen A. G. Jess, Exploiting state equivalence on the fly while applying code motion and speculation, Proceedings of the conference on Design, automation and test in Europe, p.120-es, January 1999, Munich, Germany
Darko Kirovski , Miodrag Potkonjak, Engineering change: methodology and applications to behavioral and system synthesis, Proceedings of the 36th ACM/IEEE conference on Design automation, p.604-609, June 21-25, 1999, New Orleans, Louisiana, United States
Srivaths Ravi , Ganesh Lakshminarayana , Niraj K. Jha, Removal of memory access bottlenecks for scheduling control-flow intensive behavioral descriptions, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.577-584, November 08-12, 1998, San Jose, California, United States
Sumit Gupta , Nikil Dutt , Rajesh Gupta , Alexandru Nicolau, Loop Shifting and Compaction for the High-Level Synthesis of Designs with Complex Control Flow, Proceedings of the conference on Design, automation and test in Europe, p.10114, February 16-20, 2004
high-level synthesis;telecommunication