R3-1

SASIMI 2016 Proceedings

Extending Distributed Control for High-Level Synthesis
beyond Borders of Basic Blocks
Miho SHIMIZU

Nagisa ISHIURA

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

Abstract— This paper proposes an extension of
distributed control, which enables eﬃcient run-timescheduling of variable latency operations, to multiple dataﬂow graphs. Conventional high-level synthesis
methods determine the execution schedule of operations statically assuming that their latencies are ﬁxed.
However, actual circuits contain so-called variable latency units whose execution cycles may vary depending on various run-time factors. Although Del Barrio,
Pilato, and Yamashita have proposed distributed control methods which can eﬃciently control circuits withsuch units, they only handles a single dataﬂow graphs.
Our method extends the Del Barrio’s distributed control to handle multiple dataﬂow graphs. It enables
dynamic scheduling of operations beyond the boundaries of basic blocks which results in fewer execution
cycles than those by conventional centralized control
with loop scheduling and trace scheduling.

I.

Introduction

Recent progress in semiconductor technology has enabled development of larger and more sophisticated systems on VLSI chips. While such systems needs enormous
design eﬀorts, there is a strong demand to reduce time
to market. High-level synthesis is one of the promisingmeasures to expedite hardware design on which many researches have been conducted [1].
In conventional high-level synthesis methods, operations are scheduled assuming that functional units takesame latencies for the same operations. Namely, thescheduling is determined ahead of the time and does notchange during run time. However, in actual datapaths,
some functional units exhibit diﬀerent latencies for thesame operation depending on operands or their environment. Although the traditional scheduling is still valid if
the maximum latencies are assumed for such units, wasteful waiting cycles arise when the units take less latencies
than those of the worst case.
To address this issue, [2] proposed a adaptable controller which adjusts scheduling of operations at run-time
based on the completion signals from the variable latency
units. Although it enables eﬃcient execution without
wasteful waits, the number of its states increased explosively with the size of dataﬂow graphs (DFGs). As apromising alternative, distributed control has been recently developed in which a datapath is controlled bymultiple ﬁnite state machines. Some diﬀerent schemes for
distributed controllers have been proposed by Del Barrio[3], Pilato [4], and Yamashita [5].
However, all these methods deal with a simple casewhere computation is expressed with a single DFG. In
order to apply the distributed control in control centric
high-level synthesis, control data ﬂow graphs (CDFGs)
consisting of multiple DFGs must be handled.
This paper, therefore, proposes a method of extending the distributed controller to rein the variable latency
units to handle multiple DFGs. It is an extension of Del
Barrio’s method. Rather than simply patchworking thestate transition graphs for the DFGs, it enables dynamic
operation motion across multiple DFGs, which achieveseﬃcient execution like loop scheduling and trace scheduling. An experiment on two benchmarks has proved thatthe total execution cycles were drastically reduced by the
proposed method with about 24% increase in the circuit
size.
II.
A.

Variable latency units and distributed
control

Variable latency units

Functional units in datapaths may exhibit diﬀerent latencies for the same operation, depending on operand values, states of the units, and environment factors. For example, shift/add-based multipliers and dividers can omit
part of the computation when some part of multiplicand
or intermediate remainder becomes zero. Memory accesses may take diﬀerent cycles depending on address histories. NBTI may cause long term change on delays andlatencies of the functional units.
Let us consider executing a DFG in Fig. 1 (a) with anadder A which takes 1 cycle and a multiplier M whichtakes either 1 or 2 cycles. In the conventional high-level
synthesis based on ﬁxed scheduling, the operations arescheduled as (b) assuming operations 2 and 4 may take2 cycles. Even when operation 2 completes in 1 cycle,
scheduling is unchanged as shown in (c), where the second
cycle is wasteful.
Toda [2] proposed dynamic scheduling based on thecompletion signals from functional units which enables- 172 -

A
a

b c

+1 ∗2
+3

M

+1

d

A

M

A

+1 ∗2

∗
2

+3

u

∗4

+3
∗

FSMA
enA
endA

∗
4

(b)

(c)

endA
endA

4

∗
4

t

(a)

M

+1 ∗2
+3

start1
S1
endA
start3
S3
endA

FSMM
endM
endM

start2
S2
endM
start4
S4
endM

en M
end M

Fig. 3. Distributed control of Del Barrio

(d)

C.

Del Barrio’s distributed control

Fig. 1. Execution ﬂow with variable latency units.

A

+1

M

FSM

∗

S0
2

+3

S1
S2
S3

∗
4

S4

(a) Centralized control

A

M

FSMA FSMM

+1 ∗2

S1

S2

+3 ∗4

S3

S4

(b) Distributed control of Del Barrio

Fig. 2. Centralized and distributed control

scheduling as shown in Fig. 1 (d). However, the controller for this dynamic scheduling needed huge amountof states, so the resulting circuit would be impracticallylarge.

B. Distributed control
As an approach to realizing dynamic scheduling without increasing circuit size, distributed control has recently
been proposed which controls functional units using multiple ﬁnite state machines (FSMs).
In the Del Barrio’s method [3], an FSM is assigned toeach function unit in a datapath. The function unit toexecute each operation is determined beforehand. The
order of the operations executed by each unit is also ﬁxed
and the controller dynamically decides the timings to execute the operations. The Pilato’s method [4] controls
the datapath by assigning a state variable to each operation. As Del Barrio’s method, the function unit to execute
each operation is determined beforehand but the order aswell as the timing of execution of the operations is determined dynamically. The Yamashita’s method [5] allows
hardware to dynamically decide functional unit to execute
each operation as well as the order and the timing.
However, these methods only discusses the case where
computation is expressed by a single DFG. They have notaddressed the issue of handling a CDFG consisting of multiple DFGs, which is essential in synthesizing hardware
from speciﬁcation expressed in programming languages
like C.

In the conventional centralized control method, a whole
datapath is controlled by a single FSM (ﬁnite state machine), as shown in Fig. 2 (a). On the other hand, in Del
Barrio’s distributed control, separate FSMA and FSMM
control function units A and M , respectively, as in (b).
This allows each unit to choose execution timing separately.
Fig. 3 is the details of the FSMs in Fig. 2 (b). The formulation in this paper is slightly diﬀerent from the original one in [3], but substantially the same. One state Si is
assigned to an operation i in the DFG, where Si controls
the execution of i. At Si , the FSM waits for starti = 1
where starti becomes 1 if all the operations on which i
depends are ﬁnished. In the case of Fig. 3,
start1 = 1,start2 = 1,start3 = (s2 ∧ endM ) ∨ Done2 ,start4 = (s3 ∧ endA ) ∨ Done3 ,where si means that the FSM is in state Si , and endu
is the completion signal from unit u. Donei stands forcompletion of operation i, whose initial value is 0 and is
updated as follows.
if (s1 ∧ endA ) {Done1 <= 1},
if (s2 ∧ endM ) {Done2 <= 1},
if (s3 ∧ endA ) {Done3 <= 1},
if (s4 ∧ endM ) {Done4 <= 1}.
When state is Si and starti = 1, FSMu sets the enable
signal enu of unit u.
enA = ((s1 ∧ start1 ) ∨ (s3 ∧ start3 )) ∧ ExecA ,enM = ((s2 ∧ start2 ) ∨ (s4 ∧ start4 )) ∧ ExecM ,where Execu means that unit u is in operation, which isdeﬁned as follows.
if (endA ) {ExecA <= 0}
else if (enA ) {ExecA <= 1},
if (endM ) {ExecM <= 0}
else if (enM ) {ExecM <= 1}.
Del Barrio’s distributed controller exhibits less freedom
than Pilato’s and Yamashita’s, because it can not change
the order of the operations nor the function units to execute the operations at run time. However, it is the simplest of the three, and the size and the delay of implemented hardware will be the smallest.

- 173 -

DFG1

DFG1

main

S0

S2

S0

S2

S1

S3

S1

S3

DFG2

DFG3

DFG2

DFG3

executed next DFG a frontier DFG. In Fig. 4 (b), DFG1
is the main DFG and DFG3 is the frontier DFG. A selfloop is eliminated by duplicating the DFG, as shown in
Fig. 5.
frontier

S5

S7

S9

S11

S5

S7

S9

S11

S6

S8

S10

S12

S6

S8

S10

S12

(a)

B.

(b)

S0

S2

S0

S2

S0

S2

S1

S3

S1

S3

S1

S3

S7

S5

S7

S6

S8

S6

S8

Fig. 5. Eliminating a self loop.

Del Barrio’s method in [3] covers a loop with a single DFG, where operations in the next iteration may be
executed without waiting for the completion of a certain
iteration. However, it does not handle a CDFG consistingof multiple DFGs; it does not cover conditional jumps, forexample.
III.

Formulation

Let U be the set of units in the given datapath. Foru ∈ U , ou and eu are the output and the completion signalof u at the current cycle, respectively. Let D be the set of
DFGs. An FSM to control unit u ∈ U and DFG d ∈ D isdenoted as Fd,u . Let Sd,u and fd,u be the set of states andthe last sate of Fd,u , respectively, and σd,u be the current
state of Fd,u .

Fig. 4. Distributed control beyond the borders of DFGs.

S5

For design convenience, each FSM of a unit must haveat least one state per DFG; if there is no state for a DFG, adummy state in which no operation is executed is inserted.

Distributed Control beyond the Bordersof Dataflow Graphs

A. Overview
This paper extends the Del Barrio’s distributed control
to handle multiple DFGs, where dynamic scheduling ofoperations is achieved across multiple DFGs.
In the case of the centralized FSM, the control is transferred to one of the next DFGs after all the operationsin the current DFG are ﬁnished. By applying the same
policy, the distributed control may be extended to multiple DFGs. However, in the presence of variable latency
operations, not all the units ﬁnish their task in an DFG simultaneously but they must wait for each other at the endof the DFG. To reduce the ineﬃciency, in our method,
operations in the next DFG can start execution before
concluding the current DFG. For example, in Fig. 4 where
two units are controlled by two controllers, the operations
corresponding to S0 and S3 are ﬁnished (as in (a)), then,the control of the second FSM can be transferred from
S3 to S11, without waiting for the completion of S1, if
DFG3 is known to be the next DFG of DFG1.
In this paper, we assume that only one DFG ahead of
the current DFG may be executed. The current DFG
is hereafter referred to as a main DFG and the partially

For d ∈ D and s ∈ Sd,u , Γ(s), γ(s), and e(d) are deﬁned
as follows. Intuitively, Γ(s) means that execution of theoperation at state s has been ﬁnished before the current
cycle, γ(s) means that execution of the operation at states is ﬁnished at the current cycle, and e(d) means that
execution of DFG d completes at the current cycle. Γ0 (s)and Γ (s) are the initial value and the next value (thevalue at the next cycle) of Γ(s), respectively.
γ(s) = Γ(s) ∨ ((σd,u = s) ∧ eu )e(d) =

γ(fd,u )u∈UΓ0 (s) = 0Γ (s) = if e(d) then 0 else γ(s)When e(d) becomes 1, the next state of Fd,u is the initialstate for every u ∈ U .
For e ∈ D and d ∈ D, Δ(e, d) means that transition
from e to d has been ﬁxed before the current cycle, andδ(e, d) means that transition from e to d is ﬁxed at thecurrent cycle. If d is the unique successor of e, thenΔ(e, d) = δ(e, d) = 1. Otherwise, δ(e, d) and Δ(e, d) aredeﬁned as follows assuming that the transition from e tod is determined by the output of unit u at state s.
δ(e, d) = Δ(e, d) ∨ ((σe,d = s) ∧ eu ∧ ou )Δ0 (e, d) = 0
Δ (e, d) = if e(e) then 0 else δ(e, d)M(d) means that d ∈ D is executed as the main DFG,
whose initial value M0 (d) and next value M (d) is deﬁned
as follows, where Pd is the set of DFGs preceding d.
M0 (d) = if d is the starting DFG then 1 else 0M (d) = if e(d) then 0
else M(d) ∨(e(e) ∧ δ(e, d))e∈PdF(d) means that DFG d ∈ D is executed as the frontier
DFG, whose initial value F0 (d) and next value F  (d) is
deﬁned as follows.

- 174 -F0 (d) = 0

TABLE I
Experimental result (#cycle)
centralized
diﬀeq
iprod64

770
710

u
y

distributed (proposed)
r = 1.0
r = 0.5
r = 0.0
770
632
513
740
541
422

dx 3

y x

x 3

∗1

∗2

+5

∗6

y’

−8

dx

∗3
dx

∗7

+4

a

x’

< 10

u

Loop iteration: 128, multiplication: 1゚ 2 cycles,
r: probability where multiplication took 2 cycles,c−9F  (d) = if M (d) then0 else F(d) ∨(M (e) ∧ δ(e, d))u’(a) Dataﬂow graph.

e∈Pd

A1

The operations in DFG d are executed only if M(d) ∨F(d). All the other conditions are same as the Del Barrio’s control in subsection II-C.
IV.

DFG0

A2

M1

M2

+4

∗3 ∗2

< 10 − 8

∗1

+5

∗7

−9

∗6

Experimental Result

RTL circuits based on the proposed distributed control
were designed in Verilog HDL for two benchmark CDFGs and compared with ones based on the conventional
centralized control. Throughout the experiments, it was
assumed that multiplication took either 1 or 2 cycles andthe other operations took 1 cycle.

DFG0

+4

∗3 ∗2

< 10 − 8

∗1

+5

∗7

−9

(b) Distributed control.

+4 −8

A. Benchmark CDFG

< 10 − 9(1) diﬀeq
A DFG in Fig. 6(a) is executed with two adders A1 andA2, and two multipliers M1 and M2. Fig. 6(b) is an example of binding and scheduling for distributed control. The
DFG is duplicated to remove the self loop. For comparison, the same DFG is scheduled for centralized control,as shown in Fig. 6(c).
(2) iprod64
The DFG in Fig. 7(a) computes the inner product of
64-bit data, where 64-bit multiplication is implemented byfour 32-bit multiplications and three additions. However,some of the computation may be skipped, if the higher orthe lower half of the multiplier is 0. The DFG is computedwith an ALU (A), an ALU+shifter (AS), a multiplier (M),a load/store unit (L), a comparator (E). C in the DFG
represents data transfer without operation.
Fig. 7(b) shows an example of scheduling/biding forour distributed control. The self loops are eliminatedby duplicating DFG0. Since our method requires that
the FSM for each unit must have at least one state foreach DFG, dummy states (depicted by the broken lines),
which do not issue any operation and just transfer to thenext state, are inserted for such DFGs. For comparison,
the same computation is scheduled for centralized control with the same numbers of the units. Fig. 7(c) is the
CDFG obtained by trace scheduling.
B. Performance (cycle count)
Table I compares the cycle counts on the two benchmarks. The loop was iterated 128 times on the both

∗6

∗

∗
3

2

∗
1

+5

∗

∗
7

6

(c) Centralized control (loop scheduling).
Fig. 6. Benchmark “diﬀeq.”

benchmarks. The column “centralized” shows the result for the conventional ﬁxed centralized control with thescheduling in Fig. 6(c) and Fig. 7(c), where the latency of
all the multiplications were ﬁxed at two cycles. The column “distributed” shows the cycle counts for our variableand distributed control. The parameter r is the probability where multiplication took 2 cycles; r = 1.0 means all
the multiplications took two cycles, while r = 0.5 means
half of the multiplications took two cycles and the others
one cycle. In the iprod benchmark, the each of the upper
32-bit and the lower 32-bit became 0 with a probabilityof 50%.
On the diﬀeq benchmark, the proposed method
achieved the same cycle count as the loop scheduling on
r = 1.0. Furthermore, our distributed control is mucheﬃcient than the centralized scheduling on r = 0.5 andr = 0.0.
On the iprod benchmark, however, our method resulted
in an increase in the cycle count. This is due to insertionof the dummy state and its root cause is that our method
allows operation execution in the DFG only one transition
ahead of the current active DFG. Nevertheless, the pro-- 175 -TABLE II
Experimental result (circuit size)

diﬀeq
iprod64

centralized
slices (FFs)delay [ns]567 (331)
15.044724 (464)
14.492

distributed (proposed)
slices (FFs)delay [ns]702 (441)
14.878890 (556)
15.871

posed variable scheduling reduced the cycle count whenr = 0.5 and r = 0.0.
Fig. 8 shows examples of execution traces of the diffeq benchmark by our method. (a) is the case where all
the multiplications take two cycles. Units A1, M1, andM2 can start the second iteration (highlighted by red) before A2 ﬁnishes the ﬁrst iteration, so cycle per iterationis reduced to 6. This is equivalent to the loop scheduling (determined ahead of the execution). (b) shows thecase where 6 out of 12 multiplications ﬁnish in 1 cycle.
Scheduling is dynamically adjusted beyond the border ofthe DFGs which contributes to the drastic reduction in
the total cycle count.
An execution trace example for iprod64 is also shownin Fig. 9 with r = 1.0. The result is almost equivalent tothe conventional trace scheduling, except that the dummy
state, indicated by (1), increases the cycle count by one.
Note that this occurs only when all the multiplications
take 2 cycles; if one of them ﬁnishes in 1 cycle, the dummy
state is not on the critical path and does not cause theincrease in the cycle count.
C. Circuit size
TABLE II summarizes the result of logic synthesis by
Xilinx ISE (14.7) targeting FPGA (Spartan–3E). The
columns slices, FFs, delay show the circuit size in termsof slices and ﬂip-ﬂops, and the critical path delay. The
circuits in our control method is about 24% larger thanthose by the conventional implementation. This is due tothe increase in the number of registers (and consequently
increase in the total multiplexer cost) because the lifetimes of the values overlap more frequently in variable
latency scheduling. The critical path delay is almost thesame. Thus we may conclude that the proposed controller
can be implemented in hardware of a feasible size.
V.

Discussion

Like the loop scheduling and trace scheduling methods, the proposed method yields eﬃcient computation
scheduling by moving operations across DFGs. In addition, our distributed control allows run-time adjustmentof the scheduling in response to varying latency of operations. On the other hand, our method may be less eﬃcientthan the conventional (ﬁxed) scheduling because it allows
operations to move only to the adjacent DFGs.
It is possible to apply Del Barrio’s distributed control toa DFG obtained by loop scheduling and trace scheduling,which enables both operation motion across DFGs andrun-time scheduling. This combination may outperform

our method on the presumed execution trace on which
the scheduling is determined, because operations can be
moved by more than one DFGs. However, our distributed
control may work better when the prediction fails, because
it can handle both the predicted/unpredicted branches
equally.
In our method, as well as in trace and loop scheduling, operation motion does not work when branchtaken/untaken is determined at the ﬁnal step of a DFG.
This issue may be addressed by introducing branch prediction and speculative execution.
VI.

Conclusion

This paper has presented a distributed control methodthat allows dynamic operation motion across DFGs foreﬃcient scheduling under the existence of variable latency operations. Experiment on two benchmarks demonstrated drastic reduction in execution cycles with about
24% increase in hardware size.
We are now working on adapting our method to other
distributed control methods such as [4] and [5], and on
introducing branch prediction and speculative execution
to further enhance performance.
Acknowledgements
Authors would like to express their appreciation to Dr. Hiroyuki Kanbara of ASTEM/RI, Prof. Hiroyuki Tomiyama of
Ritsumeikan University, and Mr. Takayuki Nakatani (formerly
with Ritsumeikan University) for their valuable comments. We
would also like to thank to the members of Ishiura Lab. ofKwansei Gakuin University for their cooperation and discussion. This work was partly supported by JSPS KAKENHI
Grant Number 16K00088.

References[1] Daniel D. Gajski, Nikil D. Dutt, Allen C-H Wu, andSteve Y-L Lin: High-Level Synthesis: Introduction to
Chip and System Design, Kluwer Academic (1992).
[2] Yuki Toda, Nagisa Ishiura, and Kousuke Sone: “Static
scheduling of dynamic execution for high-level synthesis,” in Proc. SASIMI 2009, pp. 107–112 (Mar. 2009).
[3] Alberto A. Del Barrio, Seda Ogrenci Memik, Marı́aC. Molina, José M. Mendı́as, and Román Hermida: “A
distributed controller for managing speculative functional units in high-level synthesis,” IEEE Trans. CAD,
pp. 350–363 (Mar. 2011).
[4] Christian Pilato, Vito Giovanni Castellana, Silvia
Lovergine, and Fabrizio Ferrandi: “A runtime adaptive controller for supporting hardware components
with variable latency,” in Proc. NASA/ESA AHS-2011,
pp. 153–160 (June 2011).
[5] Shinji Yamashita and Nagisa Ishiura: “Dynamic operation binding in distributed controller for supporting
functional units with variable latency” (in Japanese), in
Technical Report of IEICE, VLD2013–128 (Jan. 2014).

- 176 -

a

a

b

b

+ 3 +4 L1 L 2
a’

b’

La

A1

ch*cl

0

Lb

== 5
ch

cl

+7

bl

32

−
−

<< 13

<< 9
ch

+
<

+
∗ 12 32 11

ah

ch

+

<< 11s
bh

s

+ 13

s’

s’

+

E

+

(a) Dataﬂow graph.

DFG0
ch*cl

AS

M

+3

<<
+

∗

C

L
L 1

+4

cpy

A1

∗

L 2

∗

∗

∗

∗

== 5

−
−

∗

∗

∗

∗

A2

M1

+
<
+

∗
∗

+
<

−
−

+3

<<
+

∗

+
+
<

∗

∗

∗

∗

−
−

(a)

∗

(b)

+4

cpy

L 2

== 5

L

==

ch*cl

cl

cl
DFG1

Fig. 8. Example execution ﬂow of diﬀeq.

L 1

+7

∗6
<<
+9

cpy

∗8

ch
ch

DFG2

+

<<
+ 11
<<
+ 13

∗ 10 cpy

L

==

∗ 12

(b) Distributed scheduling.
A

+3
ch*cl

+4

+3

L 1
L 2

+3

∗

L 1

<<
+9

+
+
+

+7

∗

<<
+9

∗
10
L 1

+4

L 2

== 5

12
<<
+ 13

∗
cl

∗

+
+
+

ch*cl
ch*cl

6

L

<<
+

L

Fig. 7. Benchmark “iprod64.”- 177 -

==

L
cpy

L

==

cpy
(1)

∗

L
cpy

L

cpy

<<
+

Fig. 9. Example execution ﬂow of iprod64.

(c) Centralized scheduling (trace scheduling).

E

cpy

∗

<<
+ 13
10

<<
+ 11

∗

∗

ch

8

+3

cpy

∗

10

C

L

<<
+ 13

∗
6

M

+
+

== 5
ch*cl

cl

L 1

AS

∗

∗

ch*cl

DFG0

M2

∗

∗

+9

A

M2

∗

∗ 10 32

∗6
∗8

∗

bh

al

bl

ah

M1

ch*cl

cl
al

A2

+
<

==

∗
∗