IEEE Circuits and Systems Magazine - Q2 2021 - 106

that the inputs are accepted in order of program execution.
To this end, we generate an in-order control path
that follows the control flow of the program through the
BBs-essentially, a data-less variable which is a live-in
and live-out of each and every BB. The tokens on this
path are used to trigger operations without inputs as
many times as their BB becomes active. This path enters
each BB through a cmerge, which connects to the
muxes of the same BB and indicates the ordering of the
inputs from which they will receive data, as illustrated in
Figure 8. Whenever a mux is guaranteed to receive its inputs
in order (e.g., when there is a single value propagating
through the CFG and a token can only enter a BB from
its single active predecessor), it may be disconnected
from the cmerge and replaced with a simpler merge unit.
Constructing the Datapath
Once the control flow is correctly handled, the BB internals
are straightforward to design-each instruction is
literally converted into its dataflow unit (i.e., a functional
unit with inputs and outputs accompanied by handshake
signals). As every data exchange must be represented
with an explicit token transfer (i.e., handshake
exchange), units with multiple successors require a fork
to replicate the output token into a token for each of the
successors. Unused unit outputs (e.g., branch outputs
without successors) connect to sinks which discard the
unused tokens.
VI. Bringing HLS Optimizations to Dataflow Circuits
In this section, we present techniques that make the circuits
produced with our HLS approach competitive to
standard HLS solutions: we first describe how to pipeline
dataflow circuits and then discuss how to save resources
through time-multiplexing of functional units.
A. Pipelining
Dataflow circuits are naturally capable of pipelining, as
the fine-grain handshake mechanism allows certain operations
to run ahead and, consequently, enables executions
of different operations to overlap. Yet, pipelining
is not always possible due to backpressure: some paths
take a longer time to consume a token and prevent potentially
quick and independent paths from processing
tokens at a high rate. This issue is illustrated on the left
of Figure 9(a), showing the dataflow circuit implementing
the code in the bottom of the figure: the fork could,
in principle, issue tokens to the load on every cycle,
but the path to the store stalls the first token until the
multiplication completes, hence preventing new tokens
from issuing to the load and limiting loop pipelining;
the achieved schedule will, essentially, correspond to a
nonpipelined schedule of a static HLS tool. Classic pipelining
algorithms that standard tools exploit are not applicable
in the absence of a static schedule; the solution
here is to systematically identify and resolve backpressure
to achieve the same pipelining effect.
Just like standard synchronous circuits, dataflow
BB Live-Ins
CMerge
Mux
...
Mux
BB Cond
Fork
Branch
Branch
...
Branch
BB Live-Outs
Figure 8. Basic block organization. Every live-in enters a
BB through a mux and every live-out exits the BB through a
branch. A control-only network (left of the figure) regulates
the ordering of tokens at the mux inputs.
106 IEEE CIRCUITS AND SYSTEMS MAGAZINE
BB Datapath
circuits require buffers, i.e., registers, which break combinational
paths and, possibly, reduce the critical path
of the circuit. Yet, in contrast to standard circuits, buffers
can be placed on any channel (i.e., between any
two dataflow units) without compromising the circuit
functionality. This property can be exploited to mitigate
backpressure by inserting buffers into the paths that
create stalls and lower system throughput, as illustrated
on the right of Figure 9(a). Buffers used for regulating
throughput typically have a larger capacity (i.e., they
are implemented as FIFOs with multiple data slots) to
hold all tokens issued by the predecessor before the
successor is ready to accept them-in this example, the
buffer requires 3 slots to constantly consume tokens
from the fork; without the backpressure on the fork, the
iterator loop can issue a new token on every cycle and
achieve a perfect pipeline with an II equal to 1.
To optimize the performance of dataflow circuits by
strategically placing and sizing buffers, we have developed
a mixed-integer linear programming model [43]
based on Petri net theory [50]. This model allows for
resource-optimal buffer placement and sizing, with the
purpose of maximizing throughput of the performancecritical
loops at the desired clock frequency.
B. Resource Sharing
Standard HLS tools perform scheduling in conjunction
with resource allocation and sharing [70]; depending
SECOND QUARTER 2021
Control-Only Path
Basic Block
Fork
IEEE Circuits and Systems Magazine - Q2 2021

Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q2 2021
