IEEE Circuits and Systems Magazine - Q2 2021 - 102

and postpones the read until the previous, possibly dependent
write has been completed.
III. A Completely Different Way to Do HLS
The key to avoiding the limitations of static scheduling is
to refrain from triggering the operations through a centralized
pre-planned controller (as shown in Figure 4(a) and
the examples in Figure 1), but to make scheduling decisions
locally in the circuit as it runs: as soon as all conditions
for execution are satisfied (e.g., the operands are
available or critical control decisions are resolved), an operation
starts. Dataflow circuits [18] are a natural method
to realize such behavior. Such circuits are built out of units
that implement latency-insensitivity by communicating
with their predecessors and successors through point-topoint
pairs of handshake control signals, as indicated in
Figure 4(b). The data is propagated from unit to unit as
soon as memory and control dependences allow it-otherwise,
the handshaking mechanism stalls the data on-thefly.
This distributed control mechanism effectively implements
a dynamic schedule, such as the bottom schedule
in Figure 3: when a dependence exists (in the example, between
the second and the third iteration) the dynamically
scheduled circuit will stall the pipeline to prevent hazards.
Otherwise, in the absence of an address collision, it will
start a new iteration on every cycle and gain, in this case,
up to a factor 6 in performance. Such dynamic behavior
is beyond what classic static techniques can achieve [37].
In the rest of this article, after a brief digression on
how the same issues have influenced computer architecture,
we will describe our HLS methodology which produces
dynamically scheduled dataflow circuits out of
high-level code. We discuss our methodology to implement
high-throughput pipelines and to identify resource
sharing opportunities in the circuits we generate. We
then detail the construction of a memory interface (i.e.,
a load-store queue) for dataflow circuits that can correctly
handle memory accesses arriving out-of-order
and show how to automatically customize this interface
to a particular application. Further, we present a generic
framework for handling speculative execution. All these
features introduce to dataflow circuits characteristics
similar to those of modern superscalar processors; we
believe that such behavior is key for HLS to be successful
in new contexts and broader application domains.
IV. Computer Architects Have Been There Already
The contrast between static and dynamic scheduling
in HLS is in line with the experience in computer
architecture.
Practically all high-end application processors in our
computing devices and data centers are superscalar outof-order
processors [33]. Their architecture is usually
similar to the one shown in Figure 5(a). The key idea is
that reservation stations enable out-of-order execution:
they hold back fetched and decoded instructions until
Start: i = 0
i
1
ld x[i]
ld weight[i]
N
ld hist[x[i]]
+
+
Branch
st hist[x[i]]
(a)
st hist[x[i]]
Exit: i = N
(b)
Figure 4. A statically (Figure 4(a)) and a dynamically (Figure 4(b)) scheduled circuit. The static circuit has a pre-planned controller
which determines the time when each operation will execute. In contrast, the dynamically scheduled circuit contains a distributed
control system which enables decision-making at runtime and offers greater flexibility and performance. The circuits in the figure
correspond to the code from Figure 3.
102 IEEE CIRCUITS AND SYSTEMS MAGAZINE
SECOND QUARTER 2021
<
+
ld x[i]
Static
Controller
N
FIFO
ld hist[x[i]]
<
Fork
FIFO
ld weight[i]
+
Fork
Buff
Merge
Buff
Fork
1
Merge
Data
Valid Ready
IEEE Circuits and Systems Magazine - Q2 2021

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