Static Scheduling of Dynamic Execution for High-Level Synthesis
Yuki Toda

Nagisa Ishiura

Kousuke Sone

School of Science and Technology
Kwansei Gakuin University
2-1 Gakuen, Sanda, Hyogo, 669-1337, Japan

Abstract— This paper presents a concept of variable
scheduling for high-level synthesis. While the existingschedulers assume ﬁxed delays for all the operations,the latency of memory accesses and serial multiplication/division, for example, may vary depending on
operand values. The new scheduling scheme attempts
to exploit the dynamic delay variations; the control
step to start each operation’s execution is dynamicallyadjusted depending on the completion signals fromthe preceding operations. Note that the schedulingis adaptive but static, or precomputed during synthesis, thus the hardware would be simpler than that ofsuperscalar microarchitecture. Experimental results
show that the number of the execution cycles are reduced by about 4 to 18%, although the sizes of the
ﬁnite state machines becomes much larger than thatof the conventional ﬁxed scheduling.

I.

Introduction

High-level synthesis [1], a technology to auto-generate
register transfer level circuit design from behavioral speciﬁcation in programming language such as C, is now becoming one of the essential tools to expedite large scale
VLSI system design.
Scheduling is one of the core processes in high-level synthesis in which the operations in a given program (or adata-ﬂow graph) are assigned to the control steps (execution cycles) so that maximum performance per cost isachieved.
Due to the static nature of the scheduling in high-level
synthesis, conventional schedulers decide the execution
timing of the operations assuming that their delay, or thenumber of cycles they need to complete their tasks, areﬁxed. However, there are some operations whose delays
may vary dynamically. Memory access operations andserial multiplication/division are such examples. Especially, changes on the number of cycles for memory accesses due to cache hit/misshit (or line/row hit/misshit,in the case of embedded systems) are signiﬁcantly large.
Dynamic scheduling by hardware, as implemented in superscalar microarchitecture, may be a solution for highend and middle-end computing systems, but not for embedded systems where cost and power consumption for
hardware schedulers would be prohibitive.

This paper presents a novel idea of static scheduling ofdynamic execution of such indeﬁnite latency operations.
We assume that completion signals are available fromfunctional units executing indeﬁnite delay operations andwe try to synthesize circuits which adaptively adjust theexecution timing of operations depending on the completion signals from the other operations.
Our approach is diﬀerent from high-level synthesis ofasynchronous circuits [3, 4] in that circuits synthesizedby our method are fully synchronous and the adjustmentof timing is carried out by state based controllers.
We formulate the representation of such scheduling interms of a state transition graph and give a list-basedscheduling and binding algorithms for synthesizing register transfer level circuits. Experiments on some DFGs
show that the numbers of execution cycles are reduced byabout 4 to 18%, though the sizes of the ﬁnite state machines to control the datapath have grown by more than
10 times.
In the rest of this paper, we ﬁrst describes examples
of indeﬁnite cycles operations and how such operations
are handled in the conventional scheduling algorithms in
Section 2. We then present the concept of the variable
scheduling and an algorithm for it in Section 3, and show
a binding algorithm in Section 4. After describing theexperimental result obtained so far in Section 5, we giveconcluding remarks and future work in Section 6.

II.

A.

Indefinite cycle operations and theirschedulingIndeﬁnite cycle operations

Memory accesses (load and store) are typical examples
of indeﬁnite cycle operations. The number of cycles tocomplete a load might be one on cache hit but ten on
cache misshit, for example. RAMs with a burst mode
allows faster access to the data within the same row,where the initial access takes four cycles but the successive read/write to the same row takes one cycle per each
word, for example. Other examples are serial multipliers
and shift-and-subtract dividors whose latency may varydepending on the values of the operands.

B. Handling of indeﬁnite cycle operations in conventional scheduling
Figure 1 (a) is a simple example of resource constrainedscheduling. We assume that “L,” a load operation, takes
either one or two cycles while addition always takes one
cycle. We assume that we have two memory access units
and one adder.
One way of handling indeﬁnite latency operation in theconventional scheduler is to assume the worst case delays:
Two cycles for every load operation, as in Figure 1 (a). In
this case, execution of this DFG always takes ﬁve cycles.
Even if f4 ﬁnishes its task in a single cycle, f5 must wait
for one cycle to start its execution.
The other extreme is to expect the best case delays, one
cycle for every load operation, as shown in Figure 1 (b).
In case loads do not ﬁnish in one cycle, the controller stalls
the entire datapath to avoid data hazards, as in Figure 1(c).
The latter strategy, however, also fails to give the bestscheduling. If we knew the delays for f1 , f2 , and f4 are
1, 2, and 2, respectively, as in Figure 1 (c), we could start
f4 one step earlier, as in Figure 1 (d), to reduce the total
cycles to four.
Even though we may assume typical delays or any combination of delays instead of the best/worst case, we canalways ﬁnd an example where scheduling based on theﬁxed delay model is not powerful enough to give the bestscheduling under the existence of indeﬁnite cycle operations.
  



 
 




 
 
 

 






We generalize the conventional high-level synthesis settings so that the delay (in terms of cycles, in this paper) of
each operation is given in the form of a list of non-negative
integers. For example, delay < 2, 4, 6 > indicates the execution of the operation takes either 2, 4, or 6 cycles. A
single element list such as < 1 > implies the delay is ﬁxed.
We also assume that each functional unit that executes indeﬁnite cycle operations has a dedicated output port toinform the completion of the operations, which we call acompletion signal.
In our scheme, the controller adaptively changes the execution timing of the operations depending on the completion signals of the other operations. However, our scheduling is static in the sense that the execution is adaptive but
the scheduling is precomputed.
The key idea is to represent the adaptive control in theform of a state transition graph (STG). The result of theconventional scheduling, Figure 1 (a) for example, may
be regarded as a sequence of states as shown in Figure 2
where each state corresponds to a control step. Sink statesF is a virtual state, which is introduced for notational
convenience. It stands for “the end of this DFG” andcorresponds to the initial states of the next DFGs.
An instance of adaptive scheduling is expressed by augumenting the transition edges in the STG with the completion signals: Figure 3 shows an example. It is a variable
scheduling for the same setting as in Figure 1, where ci isthe completion signal for fi .
The initial state s1 corresponds to the ﬁrst cycle inthe conventional scheduling, which starts execution of f1
and f2 . If both f1 and f2 complete in a single cycle,
the next state s2 is reached by following the edge labeledby c1 c2 , where execution of f3 and f4 starts. If f4 also
ﬁnishes in a cycle, s9 and then sF are reached. This
path corresponds to the best case scheduling depicted in
Figure 1 (b). If c1 c2 edge and c4 edge are followed froms1 , then it is the worst case (Figure 1 (a)). The more
tricky sequence in Figure 1 (d) is represented by pathc c(a) Assuming the worst case delay (b) Assuming the best case delay

.- #
 !""
,+ $
 !""

98 /

*)

#

#

('

76 0

/

45
/

43

0 21

c

1 2
4
s3 →
s8 → s9 → sF .
s1 →;: K J I G
J
H
L
N
P
O
?> M
O
YX S W Q F D
E
=<

V UT

(d) Ideal scheduling for (c)

A@

S RQ

Figure 1: Conventional scheduling with indeﬁnite cycle operations.

CB

$ &%
(c) Adjustment by stall

Figure 2: State transition graph of Fig. 1 (a)’s scheduling.

III.
A.

Variable scheduling

Variable scheduling and its expression

As a new approach to get more eﬃcient scheduling under the existence of indeﬁnite cycle operations, this paper
presents a concept of variable scheduling.

B. Formulation of variable scheduling
Let F be a set of operations in a given program ora DFG. Let M be a set of the types of the available

xw

 
r p
q o
v

u

|{

g

l

f

k

e

j


~}

i

_

h

^







h

z

y

]





d

c

c

b

n 
m 





\

a

[

2. x and A must be consistently deﬁned for s, s1 , ands2 where s = δ(s1 , Z1 ) = δ(s2 , Z2 ). That is:

`
 ts



Z



































£









¢







• If x(s, f ) is deﬁned, then x(s1 , f ) = x(s2 , f ).
• A(s1 ) ∪ Z1 = A(s2 ) ∪ Z2
3. If δ(s, Z) is deﬁned, then x(s, f ) ∈ D(f ) for all f ∈ Z.

¡

A valid variable scheduling must satisfy the following
constraints:
1. Dependency constraint

Figure 3: Variable scheduling.

functional units and n(m) be the number of m ∈ M . For
operation f ∈ F , P (f ) ⊆ F is the set of the operations on
which f depends, D(f ) ⊆ Z + is the set of the delays (thenumber of the possible cycles) for f , and M (f ) ∈ M is theset of the types of the functional units that can executef.
Given the above settings, variable scheduling computes< S, δ, I, m > as deﬁned below:• S is a set of the states, which must contain the initialstate s0 and the ﬁnal state sF .
• δ(s, Z) ∈ S, where s ∈ S and Z ⊆ F , is the statetransitioned from s when the set of the operations
that complete their execution by the end of s is exactly euqals to Z.
• I(f ) ⊆ S, where f ∈ F , is the set of states at which
the execution of f starts.
• m(s, f ) ∈ M (f ), where s ∈ S and f ∈ F , is the typeof functional unit that executes f at s.
We deﬁne x and A in order to describe constraints posedon valid state transition graphs.
• x(s, f ) ∈ Z + ∪ {⊥}, where s ∈ S and f ∈ F , indicates that x(s, f )-th cycle of f is executed at s, wherex(s, f ) = ⊥ means f is not executed at s.
– x(s, f ) = 1 if s ∈ I(f ).
– x(δ(s, Z), f ) = x(s, f ) + 1 if f ∈/ Z.
– x(s, f ) = ⊥ otherwise.
• A(s) ∈ F , where s ∈ S, is the set of operations whichhave completed their execution before s:– A(s0 ) = φ.
– A(δ(s, Z)) = A(s) ∪ Z.
A valid state transition graph must satisfy the following
conditions:
1. δ(sF , Z) is undeﬁned for any Z, but δ(s, Z) must be
deﬁned for all the other s ∈ S for some Z. x(sF , f ) =⊥ for all f ∈ F . δ(s, Z) must not be s0 for any
combinations of s and Z.

∀f ∈ F, ∀s ∈ I(f ) : P (f ) ⊆ A(s).
All the operations on which f depends must havebeen computed before f starts.
2. Resource constraint
Let F (s, m) = {f ∈ F | x(s, f ) = ⊥, m(s, f ) = m}.
Then,∀s ∈ S, ∀m ∈ M : |F (s, m)| ≤ n(m).
The number of the operations which use the unit oftype m at state s is limited.
3. Completion constraint
A(sF ) = F .
All the operations must be computed by this statetransition graph.
The scheduling we search for is the one that minimizes the average, or the total number of the cycles. Let
Q<S,δ,I,m> be the set of all the paths (sequences of thestates) from the initial state to the ﬁnal state for scheduling < S, δ, I, m >. Then, our scheduling problem is formulated as to ﬁnd < S, δ, I, m > minimizing|q|q∈Q<S,δ,I,m>under the above constraints.
C. Algorithm for variable scheduling
We have developed an algorithm for variable schedulingwhich is based on the list-scheduling method [1]. Figure
4 shows its outline.
Function main (lines 01–08) calls recursive function
schedule after initialization. X, Q, C are sets of operations which are being executed, ready, and completed,
respectively. x[f ] and m[f ] indicate which cycle and on
which type of functional unit f is being executed (forf ∈ X).
Function schedule builds a state transition graph for
given X, Q, C, x, m and returns its initial state. Scheduling is computed until both X and Q become empty (line11). A functional unit to execute each f ∈ Q is searched,and if it is available, it is scheduled to start execution
at this state (lines 12–19). A new state is created for
updated status, but no two equivalent states will be instanciated so as to avoid state explosion (lines 20–22).
Function schedule is recursively called for every possible
Z with updated status to ﬁnd the next state δ(s, Z).

01: void main () {02: X = φ; /* set of executing ops */04: C = φ; /* set of completed ops */03: Q = {f | P (f ) = φ}; /* set of ready ops */05: for (f ∈ F ) x[f ] = ⊥; /* f is executing x[f]-th cycle */06: for (f ∈ F ) m[f ] = ⊥; /* unit type to execute f */07: s0 = schedule(X, C, Q, x, m);
08: }
09:
10: State schedule (X, C, Q, x, m) {11: if (X==φ && Q== φ) return sF ;12: for (f ∈ Q) {13:
if (some u ∈ M (f ) is available) {14:
x[f ] = 0;15:m[f ] = u;17:
X = X ∪ {f };16:
Q = Q − {f };
18:
}
19: }
20: for (f ∈ X) x[f ]++;
21: if (there exists t with t =< X, Q, C, x, m >) return t;
22: s = new State with s =< X, Q, C, x, m >;23: for (Z ∈ all possible combinations of ops
24:
which can complete execution) {25:
X  = X − Z;26:
C  = C ∪ Z;
27:
Q = Q ∪ {f | P (f ) ⊆ C  } − X  − C  ;28:x = x;29:m = m;30:s = schedule(X  , C  , Q , x , m );31:
let δ(s, Z) = s
32:
}
33:
return s;
34: }Figure 4: Algorithm of variable scheduling.

IV.
A.

Binding for variable schedulingDiﬀerence from conventional binding

In the conventional scheduling, a single functional unit
is assigned to each operation in the binding process. However, in the case of variable scheduling, an operation may
be executed on diﬀerent functional units depending onstates.
Figure 5 illustrates such an example. Suppose a fractionof a state transition graph in Figure 5 (a) is generated byvariable scheduling, and we have two units M1 and M2
that can execute f1 , f2 , and f3 . Figure 5 (b) is an exampleof binding for Figure 5 (a). Let f1 and f2 be executedby M1 and M2 , respectively, at state s1 . At state s2 ,operation f3 must be executed on M1 since M2 is still
executing the second cycle of f1 . On the other hand, at
s3 , the same operation f3 must be executed on M2 whichis the only available functional unit. Thus, f2 should beexecuted on diﬀerent units depending on the states 1 .
similar situation occurs on register binding. Figure 5(c) is an example of register binding for Figure 5(b). Suppose only four registers R1 through R4 are available. At
state s1 , operation f1 reads R1 and R2 , and operation f2
reads R3 and R4 . At state s2 , registers R1 and R2 must
be assigned to the operands of f3 , since R3 and R4 are
1 If another unit M

3 were available, the operation binding could

be made state-independent by assigning M3 to f3 .

still read by f2 . In contrast, in state s3 , the operands off3 must be held in registers R3 and R4 , instead. Thus,
register binding also depends on the states 2 .
Note that in our formulation we only determine an input register for each operation, because this automaticallydetermines the output registers. Thus, the output register for each operation depends on the next state, which isdetermined by combination of the present state and thecompletion signals.
The circuits synthesized by variable scheduling andbinding are basically the same as those generated by theconventional methods. The controller of a circuit delivers control signals to select appropriate operations andinput/output registers for each functional unit and to indicate writes to each registers. The only diﬀerence is thatthe completion signals are fed into the controller.
B. State splitting
There are bad news about binding for variable scheduling: The number of the states of STG may increase during the binding due to the need for state splitting. This iscaused both by operation binding and by register binding.
(1) State splitting by operation binding
Let us consider the STG in Figure 6 (a) which are obtained by adding s4 to that in Figure 5 (a). Operation
f3 is executed on diﬀerent units M1 and M2 at states s2
and s3 , respectively, which incurs a contradiction on reconvergence state s4 . To reconcile this situation, the states4 must be split as shown in Figure 6 (b).
(2) State splitting by register binding
The same thing happens during register binding. In
Figure 7 (a), f3 is reading R1 and R2 in state s2 andR3 and R4 in state s3 . In order to avoid conﬂict on thereconvergence, state s4 must be split as shown in Figure
7 (b).
Note that some of such state splitting are inevitable,
but others may be avoidable by appropriate operation andregister binding. For example, splitting in Figure 7 would
be avoided if R3 and R4 are used instead of R1 and R2 instate s2 . Thus, it is an important goal to ﬁnd a bindingthat curve the state increase due to state splitting.

C. Formulation of binding
Let V be the set of all the input and output values(operands) of the operations in F , R be a set of available registers, and P I (P O) be the set of the input (output) ports of the functional units. For operation typem ∈ M , U (m) is the set of the functional units of typem. Let pi(u, k) (po(u, k)) be the k-th input (ouput) port.
Let vi(f, k) (vo(f, k)) be the k-th input (output) operandvalue to operation f , and nvi(f ) (nvo(f )) be the numberof input (output) operands. Let u(s, f ) be the functional
2 If there were suﬃcient number of registers, the register binding
could be made state-independent by using R5 and R6 for input
operands of f3 .

¥¤
¸ ·º¹

¾½ Õ

« ª
°

äãâá

¸ ·¼»

¯®©
¯®©
² ± ¨ ­¬ ¨² ±
±
¶

µ ³
´

§¦

« ª
ª

(a) result of scheduling












ó ñ
ò



÷ ö
ö



ýü

ÿ

äãàß
Ò Ð ×
Ö
Ñ

(b) operation binding





ê è
é



Figure 5: variable binding.


9


;

:

8 


$  &%('
# 

- ,
0 .
, =<
/

ED

*)
"
!

9

7

I

?
 
>
+

6

5

8

1

C A
B @
,

4

*)

2
3

}|{z
?

>

GF

K
Jo

n

k

H

\
_ ]
[
^

ut
f d
S o
e
R
n

(a) before splitting

[

jO N
N

q
O N
p
Z

yxwv
UTM
WVM
[
L Q
L \
a
s
q
Pk
` c
r
p
j
b

YX

ml
i g
h

ut
f d s
e
r

(b) after splitting

Figure 6: State splitting by operation binding.

unit to execute f at s, and r(s, v) be the register to store
value v at s. Then biding is to ﬁnd u(s, f ) and r(s, v)
for s ∈ s, f ∈ F , and v ∈ V which satisﬁes the following
constraints:• ∀s ∈ S, ∀f1 , f2 ∈ V : u(s, f1 ) = u(s, f2 ).
• ∀s ∈ S, ∀v1 , v2 ∈ V : r(s, v1 ) = r(s, v2 ).
• Let s = δ(s, Z) and x(s, f ) = ⊥ ∧ x(s , f ) = ⊥holds. Then,– u(s, f ) = u(s , f ), and– r(s, vi(f, k)) = r(s , vi(f, k)) for 1 ≤ k ≤nvi(f ).
The third constraint is for multicycle operations where thefunctional units nor the input registers must not change
during their execution.
There are various cost functions to minimize, among
which we try to curve the number of the interconnections
between the registers and the input/output ports of thefunctional units.
minimize |C|, whereC = {(r(s, vi(f, k)), pi(u(s, f ), k)),(po(u(s, f ), l), r(s, vo(f, l))) |1 ≤ k ≤ nvi(f ), 1 ≤ l ≤ nvo(f )}
D.












 ~






 




©














(a) before splitting

®
­

µ

´

®
­

µ

´

°


°
¨ ¦
§



°
¡

 ¹



¸

®¯
¢

¬« ª

²±

®³
¥ £
¤

¡
²±
¹

º

·¶

®³
¨ ¦
§

(b) after splitting

Figure 7: State splitting by register binding.

(c) register binding

C A
B @





  
 



þ
÷ ö 
øîíúù ìëìû



 ð
ï

ô
õ ô   ç å
æ

ô

ô



ÈÇÂ
ÊÉÌË
À¿ Ú
ÁÆ
Ò Ð Ï Î ÜÛ Å Þ Ý Ï Î
Ó
Î
Ù Ñ

µ ³
´



Õ
Ô Ä ÃÃ Ä ÍÃØ

Algorithm of binding

Figure 8 shows the outline of the binding algorithm wehave developed so far. As is described in main function(lines 01–04), operation binding and register binding aredone seperately. This is because we found in our earlier
experiment that simultaneous register binding with operation biding would cause tremendous state increase due
to state splitting to avoid register conﬂicts. In function
fu bind, the recursion continues until the ﬁnal state sF
is reached (line 07). An avaialbe functional unit is assigned to each operation f whose execution starts at thisstate s (lines 08–09). Then, every possible next state s
is tested if it has been already visited. If not, recursion
continues on s with constraints regarding multicycle operation passed to s (lines 12–15). Otherwise, since therecursion has reached a reconvergence, it checkes for theconsistency. If contradictions are found, then the states
are split (lines 16–23). On the other hand, in registerbinding, we use a simpler strategy. We ﬁrst build for eachvalue v the list of states where v is alive, and then try
to ﬁnd a conﬂict-free mapping from the set of the values
to a set of registers by solving a convering problem by agreedy method.
01: void main () {02: fu bind(s0 ); /* operation binding */03: reg bind(s0 ); /* register binding */
04: }
05:
06: void fu bind (State s) {07: if (s == sF ) return;
08: for s (such that s ∈ I(f )) {09:
let u(s, f ) be some available unit;
10: }11: for s (such that s = δ(s, Z) for some Z) {12:
if (binding of s is not yet done) {13:
copy multicycle info from s to s ;14:
fu bind(s );
15:
}
16:
else if (binding of s is contradictory) {17:/* state splitting */18:s = new State;19:s = s ;20:
overwrite s with multicycle info from s;
21:
fu bind(s );22:
let δ(s, Z) = s
23:
}
24:
else { ; }
25: }
26: }
27:
28: void reg bind (State s) {29:
build ALIVE(v); /* list of the states where v is alive */30:
solve the covering probem by greedy algorithm;
31: }Figure 8: Algorithm of binding.

Table I: Result of variable scheduling and binding.

DFG

#op

GSM:Auto
GSM:RC
GSM:TLAR
GSM:QCellip.c

740
225
70
413
48

matrix3.c

114

V.

#unit
(+, *, M)(2, 2, 1)(2, 2, 1)(2, 2, 1)(2, 2, 1)(1, 1, 1)(2, 2, 1)(3, 3, 1)

ﬁxed (max)ﬁxed (min)variable scheduling & binding#st #cy #st
#cy
#st
#cy
CPU (sec)
847
847 421 518.16 943 496.11
48.375247
247 106 155.01 263 143.00
0.180
54
54
33
48.00
54
45.00
0.997
561
561 243 294.00 561 270.00
0.514
45
45
28
38.94 134
33.42
0.505
35
35
20
29.76 611
25.58
2.919
306
306
93 122.84 585 106.00
3.275
the number of cycles: +<1>, ∗<2, 3, 4>, M<1, 4>

Experiments

A program to compute variable scheduling and biding
has been implemented based on the algorithm describedso far on Unix (Mac OS X) by Perl (5.8.6). Table I summarizes the results of the experiments. DFGs “ellip.c”
and “matrix3.c” are an eliptic ﬁlter and 3 × 3 matrix multiplication. “GSM:Auto,” “GSM:RC,” “GSM:TLAR,”
and “GSM:QC” are functions Autocorrelations, Reﬂection coeﬃcients, Transformation to Log Area Rations,and Quantization and coding, respectively, taken fromthe GSM benchmark of CHStone [5].

VI.

Conclusion

We have presented a concept of variable scheduling, or
precomputed dynamic scheduling, and described its formulation and scheduling/biding algorithms.
There are deﬁnitely many things that have to be done
to see if this concept would be practical. The STG size interms of the number of states must be reduced throughout scheduling and biding. The impacts and trade-oﬀs
between the performance and the cost of synthesized circuits should be evaluated, and many factors should betaken into account for biding algorithms.
Acknowledgements#op is the number of operations in the DFG, #unit
is the list of the numbers of functional units (adders(+), multipliers (∗), and memory access units (M)). The
numbers of the cycles are < 1 > (ﬁxed) for addition,< 2, 3, 4 > for multiplication, and < 1, 4 > for memory accesses. We assume the three possibilities of delays
for multiplication have equal probability (1/3). On theother hand, we assume a memory access takes one cycle if the address is within the same 256 word row asin the previous access, but four cycles otherwise. The
columns “ﬁxed (max)” and “ﬁxed (min)” are results (thenumber of states, or control steps, and average execution
cycles) by the conventional ﬁxed delay scheduling, where
the maximum and minimum delays, respectively, are assumed for multiplication and memory accesses. The columuns under “variable scheduling & binding” lists the thenumber of the states (after binding) and the average execution cycles, and the CPU time for the computation(scheduling and binding).
Across all the benchmarks we tried, ﬁxed (min) gave
better results than ﬁxed (max). Variable scheduling reduced the execution cycles over ﬁxed (min) by 13 to 18%
on ellip.c and matrix3.c. However, the increase in the
STG size is prohibitively large. On GSM benchmarks,
where parallelism is not very high, the execution cycles
are reduced by 4 to 8% while the STG sizes are almost
the same as ﬁxed (max).
The CPU time is reasonable for the benchmarks in thetable, but there were cases where the CPU time grewprohibitively with the STG size especially during binding.

Authors would like to express their appreciattion to
Dr. Hiroyuki Kanbara of ASTEM/RI, Prof. Hiroyuki
Tomiyama of Nagoya University, and Mr. Takayuki
Nakatani (formerly with Ritsumeikan University) for their
discussion and valuable comments. We would also like tothank to Mr. Yoshitaka Iritani and the other members of
Ishiura Lab. of Kwansei Gakuin University.
References[1] Daniel D. Gajski, Nikil D. Dutt, Allen C-H Wu, and Steve Y-L
Lin: High-Level Synthesis: Introduction to Chip and System
Design, Kluwer Academic Publishers (1992).
[2] Yuki Toda: Dynamic Scheduling for High-Level Synthesis Considering Indeﬁnite Cycle Operations (in Japanese), Bachelor
Thesis, Department of Informatics, Kwansei Gakuin University(Mar. 2008).
[3] T. Yoneda, A. Matsumoto, M. Kato, and C. Myers: “High level
synthesis of timed asynchronous circuits,” in Proc. IEEE International Symposium on Asynchronous Circuits and Systems,
pp. 178–189 (Mar. 2005).
[4] A. Prihozhy: “Asynchronous scheduling and allocation,” inProc. DATE 1998, pp. 963–964 (Feb. 1998).
[5] Y. Hara, H. Tomiyama, S. Honda, H. Takada, and K. Ishii:“CHStone : A benchmark program suite for practical C-based
high-level synthesis,” in Proc. ISCAS 2008 (May 2008).