SASIMI 2018 Proceedings

R1-7

Extended Distributed Control for Dynamic Scheduling across Dataflow Graphs
Wakako NAKANO

Nagisa ISHIURA

School of Science and Technology, Kwansei Gakuin University
2-1 Gakuen, Sanda, Hyogo, 669–1337, Japan
Abstract—This paper extends distributed control for run-timescheduling of variable latency operations so that it can execute
operations in more than two DFGs in parallel. In contrast to theconventional high-level synthesis methods which determine thescheduling of operations statically and control a datapath witha single finite state machine, the distributed control enables dynamic adjustment of execution timing of variable latency operations by reining functional units with multiple finite state machines. Although Shimizu extended the Del Barrio’s distributed
controller to handle control dataflow graphs (CDFGs) consistingof multiple dataflow graphs (DFGs), in which dynamic operation
motion across DFGs were possible, its formulation allowed parallel execution of operations in at most two DFGs. This paper proposes a new formulation where operations in more than two DFGs
may be executed in parallel. A preliminary experiment shows that
our new method reduces execution cycles when data dependency
does not prohibit parallel execution of multiple DFGs.

I. Introduction
While the scale and the complexity of the hardware implemented in a chip are growing rapidly, there is a strong demand
to reduce time to market. High-level synthesis is considered to
be one of the effective means to expedites hardware design.
In traditional high-level synthesis methods, operations arescheduled statically assuming that functional units take thesame number of clock cycles for the same operations. However, in actual datapaths, functional units may exhibit different latencies for the same operations. There had been someattempts to adjust operation scheduling in runtime [1], a finite state machine (FSM) to control the datapath would end
up with enormous amount of states. On the other hand, a
distributed control scheme, where the datapath is controlled
by multiple FSMs, enables run-time adjustment of operation
scheduling with reasonable hardware cost. Different schemes
for distributed controllers have been proposed by Del Barrio[2], Pilato [3], etc.
While these methods originally dealt with a case where computation is expressed with a single DFG, Shimizu extended theDel Barrio’s distributed control to handle multiple DFGs [4].
This enables dynamic operation motion across dataflow graphs(DFGs) which brought about the same effect as trace/loop
scheduling. However, it posed a restriction that only two DFGs
may be executed in parallel.
To address this issue, we propose an improved formulationof the distributed control where more than two DFGs can beexecuted in parallel. A preliminary experiment demonstrates
that execution cycles can be reduced by this extension.
II. Variable latency units and distributed control
Functional units in datapaths may exhibit different latencies for the same operation, depending on operand values,states of the units, etc. Memories and iteration-based multipli-- 35 -A+1M

FSMA

∗

S0+1 ∗2

A+3S2S3∗

∗
∗

S4

4

44(a) static scheduling(b) early completion(c) dynamic scheduling

FSMA

M+1 ∗2+3 ∗4

M+1 ∗2+3S12+3A

M

enA
endA

endA
endA

start1
A1
endA
start3
A3
endA

FSMM
endM
endM

start2
M2
endM
start4
M4
endM

en M
end M(d) Del Barrio’s distributed control [2]Fig. 1. Handling of variable latency operations.

ers/dividers are such examples. In traditional high-level synthesis where operations are scheduled statically (Fig. 1 (a)),
operation 3 can not start early even when operation 2 finishes
in a cycle (Fig. 1 (b)).
In the Del Barrio’s method [2], dynamic adjustment ofscheduling (Fig. 1 (c)) is realized by controlling units with separate FSMs. For example, in Fig. 1 (d), FSMA and FSM M
control units A and M, respectively. Unit u start execution
when FSMu sets enu = 0, and notifies the completion by setting endU = 1. Each operation i is assigned a state S i . At
S i , the FSM waits for starti = 1, which means that all theoperations i depends on are finished. For example, at S 3 ,start3 = (S 2 ∧end M )∨ Done2 , where Donei expresses the completion of operation i. After setting enu = 1, FSMu waits forthe completion signal endu , and then moves to the next state.
Shimizu extended the Del Barrio’s method to handle multiple DFGs connected with conditional and unconditional transitions [4], which enables dynamic operation motion across
DFGs. For example, in the benchmark in Fig. 2 (a), A2 canexecute operations 1 in DFG0 of the next iteration, while operations 12, 11, and d2 in DFG2 are still under execution.
However, the formulation in [4] posed a restriction that only
one DFG ahead of the current DFG may be executed, i.e. atmost two DFGs may be executed at the same time. A self loop
is eliminated by duplicating the DFG (DFG0’ in Fig. 2 (a) isa copy of DFG0). It also imposed that at least one state must
exist per unit per DFG. States d0, d0’, d1, and d2 are dummy
states inserted to satisfy this condition.
III. Extended distributed control

A. Overview
There are cases where the “2 DFG restriction” in [4] limits
the performance of resulting circuits. For example, in a exe-

A1
DFG0A2+ d0 + 1M1M2∗ d0 ∗ d0A1

DFG0’+ d0’ + 1’

3&4−2<3< 3’−9+ 10< 4’3&43’&4’DFG1DFG2+ d2 ∗ 11 ∗ d2+ 12+1A2

DFG1− 2’3’&4’<43&4∗ d0’ ∗ d0’DFG23’&4’+ d1 ∗ 5∗7∗6∗8−9DFG0DFG1+ 10M1M2+ d1 ∗ 5+ d2 ∗ 7∗6∗XXA1DFG1−9+ 108∗ d2∗ 11 ∗ d0∗ d0+1+ 12 − 2+ d0 < 3<4+ d1 ∗ 5DFG2

DFG0+ 12+ d0A2

M1M2+ d1 ∗ 5 ∗ 6+ d2 ∗ 7∗+18−2∗ d2< 3 ∗ 11 ∗ d0< 4 ∗ d0+ d1 ∗ 5 ∗ 6DFG1

DFG 0main
DFG 1DFG 2frontier DFG 3DFG 4(d) main-frontier scheme [4]activeactive
DFG 0& head
DFG 1
DFG 2
DFG 3

∗6active DFG 4(a) CDFG of benchmark bicubic [4](b) trace (previous)(c) trace (proposed)(e) active-head scheme

Fig. 2. Extended distributed control on bicubic benchmark.

cution trace in Fig. 2 (b), A2 could execute operations 1 and 2
just after d2, but A2 must wait for the completion of operation
10 to start operation 1, due to the 2 DFG restriction.
In this paper, the formulation is updated so that operations
in more than 2 DFGs can be executed at the same time. With
this formulation, the trace in Fig. 2 (b) will be improved to (c).

B. Formulation
In the previous formulation, state transition was controlled
by defining a main DFG (currently being executed) and a frontier DFG (one DFG ahead of the main DFG) as illustrated inFig. 2 (d). Transition into a state is allowed only if it is in themain or frontier DFGs.
In this paper, new predicates active and head are introduced.
Intuitively, as illustrated in Fig. 2 (e), active(d) means thatsome operation in DFG d is being executed, and head(d) meansthat DFG d is the forefront of the active DFGs. Let last(d)means that all the operations in the DFG d finishes in the current cycle. Then, transition from a state in DFG d to a state in
DFG d′ is allowed only if transition from d to d′ is fixed, andhead(d) or active(d′ )′or last(d ).

This allows execution of DFGs as long as the head DFG does
not overrun the “tail” of the active DFGs.
Predicates active(d) and head(d) are defined operationally.
Initially, active(d) = head(d) = 0 for all DFGs d and active(d0)= head(d0) = 1 for the start DFG d0 . active(d) is set when
there is a transition from a state in some DFG d p to a state ind. When last(d) =1, active(d) is reset in the next cycle. When
there is a transition from a state in some DFG d p to a state in dwhere head(d p)=1, head(d) is set and head(d p) is reset.
IV.

Experimental Results

Preliminary experiment has been conducted by manually designing RTL circuits in Verilog HDL for the same benchmarks
as in [4], and synthesizing them by Xilinx Vivado (2016.4)
targeting Artrix-7 (xc7a100tcsg324-3). It is assumed that multiplication takes 1 or 2 cycles depending on operands, and all
the other operations take 1 cycle. TABLE I summarizes theresults. Rows “DC” and “XDC” are for the previous [4] andthe proposed methods, respectively. “#cycle” are the numberof execution cycles for 128 iteration, where r is the probability that the multiplication takes two cycles. We can observe
substantial reduction of execution cycles on bicubic. On theother hand, there is no change on m-lerp in which there is nochance of executing more than 3 DFGs, bacause of loop car-- 36 -TABLE I Experimental result.
controlbicubicm-lerp

DC [4]XDC
DC [4]
XDC#cycler = 1.0 r = 0.5 r = 0.0
1,138 1,039
933
1,037
893
731
933
860
819
933
860
819

#LUT
586
588
743
737

delay
[ns]
7.86
8.00
7.61
7.60

ried data dependence across DFGs. “#LUT” (LUT count) and“delay” (critical path delay) are almost the same as the previous method.
V. Conclusion
This paper has proposed a new formulation of the distributed
control in which operations in more than two DFGs may be executed in parallel. A preliminary experiment shows that ournew method can reduce execution cycles when data dependency does not prohibit parallel execution of multiple DFGs.
We are now working on automatic RTL generation from CDFG
and scheduling/binding based on this formulation.
Acknowledgements—Authors would like to express their appreciation
to Dr. H. Kanbara (ASTEM/RI), Prof. H. Tomiyama (RitsumeikanUniv.), and Mr. T. Nakatani (formerly with Ritsumeikan Univ.) for
their valuable comments. We would also like to thank to the membersof Ishiura Lab. of Kwansei Gakuin Univ. for their cooperation. Thiswork was partly supported by JSPS KAKENHI Grant #16K00088.

References[1] Y. Toda, N. Ishiura, and K. Sone: “Static scheduling of dynamic execution for high-level synthesis,” in Proc. SASIMI
2009, pp. 107–112 (Mar. 2009).
[2] A. A. Del Barrio, et al.: “A distributed controller for managing speculative functional units in high-level synthesis,”IEEE Trans. CAD, vol. 30, no. 3, pp. 350–363 (Mar. 2011).
[3] C. Pilato, et al.: “A runtime adaptive controller for supporting hardware components with variable latency,” in Proc.
NASA/ESA AHS 2011, pp. 153–160 (June 2011).
[4] M. Shimizu and N. Ishiura: “Extending distributed controlfor high-level synthesis beyond borders of basic blocks,”
in Proc. SASIMI 2016, pp. 172–177 (Oct. 2016).
[5] M. Shimizu, N. Ishiura, S. Ota, and W. Nakamo: “Speculative execution in distributed controllers for high-level
synthesis,” in Proc. RSP 2017, pp. 99–105 (Oct. 2017).