# HIDA: A Hierarchical Dataflow Compiler for High-Level Synthesis

Hanchen Ye  0000-0002-6646-8146 University of Illinois Urbana-ChampaignUnited
States<EMAIL_ADDRESS>,  Hyegang Jun  0000-0002-7879-6884 University of
Illinois Urbana-ChampaignUnited States<EMAIL_ADDRESS>and  Deming Chen
0000-0002-3016-0270 University of Illinois Urbana-ChampaignUnited States
<EMAIL_ADDRESS>
###### Abstract.

Dataflow architectures are growing in popularity due to their potential to
mitigate the challenges posed by the memory wall inherent to the Von Neumann
architecture. At the same time, high-level synthesis (HLS) has demonstrated
its efficacy as a design methodology for generating efficient dataflow
architectures within a short development cycle. However, existing HLS tools
rely on developers to explore the vast dataflow design space, ultimately
leading to suboptimal designs. This phenomenon is especially concerning as the
size of the HLS design grows. To tackle these challenges, we introduce _HIDA_
111https://github.com/UIUC-ChenLab/ScaleHLS-HIDA, a new scalable and
hierarchical HLS framework that can systematically convert an algorithmic
description into a dataflow implementation on hardware. We first propose a
collection of efficient and versatile dataflow representations for modeling
the hierarchical dataflow structure. Capitalizing on these representations, we
develop an automated optimizer that decomposes the dataflow optimization
problem into multiple levels based on the inherent dataflow hierarchy. Using
FPGAs as an evaluation platform, working with a set of neural networks modeled
in PyTorch, HIDA achieves up to 8.54$\times$ higher throughput compared to the
state-of-the-art (SOTA) HLS optimization tool. Furthermore, despite being
fully automated and able to handle various applications, HIDA achieves
1.29$\times$ higher throughput over the SOTA RTL-based neural network
accelerators on an FPGA.

##  1\. Introduction

With the decline of Moore’s law, it is no longer possible to expect the price
of computation to decrease year over year. As a result, _customized_ and
_domain-specific_ accelerators are becoming well accepted in combating the
physical limitations of silicon, including those implemented on ASICs (Du et
al., 2015; Jouppi et al., 2017; Genc et al., 2021) and reconfigurable
platforms, such as FPGAs (Zhang et al., 2021; Zhou et al., 2021; Ye et al.,
2020). Historically, the cost of developing hardware accelerators has always
remained astronomically high. In this context, high-level synthesis (HLS) is a
promising solution that can synthesize high-level algorithmic description to a
hardware description language (HDL) implementation (Cong et al., 2011).

Dataflow Architecture. An important computation architecture for customized
hardware accelerators is _dataflow_ , which enables the parallel temporal
execution of multiple coarse-grained tasks (Moreau et al., 2018; Prabhakar et
al., 2017; Zhang et al., 2020). Unlike the Von Neumann architecture that
constantly grapples with the memory wall, dataflow architecture can exploit
the on-chip communication between tasks to avoid frequent external memory
access. As long as an application is dataflow feasible, a well-designed
dataflow architecture can efficiently execute the application with reduced
power and bandwidth utilization (Umuroglu et al., 2017; Wei et al., 2018;
Fahim et al., 2021).

Existing Dataflow Approaches. Commercial HLS tools typically provide
programming interfaces for users to implement dataflow structures, such as the
AMD Vitis HLS dataflow directive (Inc, 2022a), Intel HLS _system of tasks_
(Inc, 2022b), and LegUp thread APIs (Inc, 2021). However, it is still
difficult to implement a dataflow-oriented HLS design with sequential
languages, such as C/C++. Therefore, academic HLS tools have pushed for
approaches that decouple algorithm specification from hardware customizations
in compute, data types, and memory (Ben-Nun et al., 2019; Lai et al., 2019;
Xiang et al., 2022; Ikarashi et al., 2022), or introduce specialized HLS
primitives (Margerm et al., 2018; Koeplinger et al., 2018; Chi et al., 2021;
Guo et al., 2022). These approaches have effectively improved productivity and
quality compared to industrial HLS tools. Note that there also exist recent
frameworks (Ye et al., 2022a; Ejjeh et al., 2022) that can automatically
generate dataflow design without manual code rewriting. However, these
automated tools cannot systematically model dataflow architectures, limiting
them to the generation of suboptimal simple designs.

Unexplored Opportunities. Although existing HLS tools can enable dataflow
designs, they still heavily rely on the user to make the hard design
decisions, including but not limited to parallelization strategy, tiling
strategy, memory hierarchy, data layout, etc. More importantly, the design
spaces of different tasks in the dataflow are tightly coupled with each other
due to two reasons: (1) an efficient dataflow architecture demands the latency
to be balanced across different tasks as the critical task determines the
overall achievable performance; (2) the inter-task communications are often
established through streaming channels or on-chip buffers instead of
hierarchical shared memory. Meanwhile, large-scale dataflow often gravitates
towards a _hierarchical_ structure, as dataflow tasks are naturally
represented by nested graphs, further complicating the design space.

As a result, the vast design space can prohibit programmers from reasoning
about various design choices and finding the optimized design point. This can
eventually lead to non-ideal performance and efficiency, thereby thwarting the
promise of existing dataflow approaches. We observed that many HLS-
augmentation tools have proposed DSE engines using different algorithms,
including polyhedral techniques (Zuo et al., 2015, 2017; Agostini et al.,
2022; Zhao et al., 2022), graph analysis (Zhong et al., 2016; Zhao et al.,
2017; Huang et al., 2021; Ye et al., 2022b), and machine learning
(Sohrabizadeh et al., 2022; Yu et al., 2021; Ejjeh et al., 2022; Jun et al.,
2023). These tools can effectively explore the local design space of a single
task or kernel. However, they cannot handle the dataflow-oriented exploration
of multiple tasks due to the inter-task coupling and the complicated dataflow
hierarchy.

HIDA Approach. With the discussion above, we concluded that the challenges
presented in the design and optimization of dataflow architecture cannot be
fully addressed by existing HLS approaches, which rely on programmers to
explore the vast design space manually. We argue that compilers will and
should play an important role in the design process - the hierarchical
characteristics of dataflow architecture should be systematically represented
and modeled, on which an optimization pipeline should be built to handle the
inter- and intra-task optimizations comprehensively.

Under this mantra, we propose _HIDA_ , an HLS framework with hierarchical
dataflow intermediate representations (IR) and optimizations, enabling the
automated transformation of algorithmic hardware descriptions to efficient
dataflow architectures. The main contributions of HIDA are as follows:

  * •

We propose a new dataflow IR called HIDA-IR that models dataflow at two
different levels of abstraction, Functional and Structural, to capture the
dataflow characteristics and multi-level hierarchy, enabling effective
optimizations.

  * •

We propose a new dataflow optimizer called HIDA-OPT, featuring a pattern-
driven task fusion algorithm and an intensity- and connection-aware dataflow
parallelization algorithm geared toward maximum efficiency.

  * •

We enable an end-to-end and extensible compilation stack supporting PyTorch
and C++ inputs, empowering the user to rapidly experiment with various design
parameters and prototype new dataflow architectures.

  * •

We perform comprehensive FPGA evaluations of HIDA. On a set of neural
networks, HIDA achieves 8.54$\times$ and 1.29$\times$ higher throughputs over
the SOTA HLS optimization framework and RTL-based neural network accelerator.

Table 1. LeNet accelerator design. _CPF_ and _KPF_ denote the channel and
kernel parallel factor.

Layer | Task | Factor | Range
---|---|---|---
(All Layers) | - | $BATCH$ | {1, 5, 10, 15, 20}
Conv+ReLU | Task1 | $KPF_{task1}$ | {1, 2, 3, 6}
Pool
Conv+ReLU | Task2 |  $KPF_{task2}$ $CPF_{task2}$ |  {1, 2, 4, 8, 16} {1, 2, 3, 6}
Pool
Conv+ReLU | Task3 |  | $KPF_{task3}$
---
$CPF_{task3}$
| {1, 2, 3, 4, 6, 8}
---
{1, 2, 4, 8, 16}
Linear | Task4 | - | -

Table 2. Evaluation results of LeNet.

| Expert | Exhaustive | HIDA
---|---|---|---
Resource Util. | 95.5% | 99.2% | 95.0%
Throu. (Imgs/s) | 41.6k | 49.9k | 53.2k
Develop Cycle | 40 hours | 210 hours | 9.9 mins

Figure 1. Exhaustive design space search of the LeNet accelerator. _w/ df_ and
_w/o df_ indicate whether dataflow is enabled. _Worst w/ df_ is the dataflow
design with the worst quality. _Expert design_ is hand-tuned by HLS experts.
_HIDA design_ is automatically generated from HIDA.

##  2\. Motivation

Due to the inherent disjoint between the Von Neumann-centric programming model
and the dataflow programming model, it is easy for HLS designs to leave a
large portion of the achievable performance on the table. To better understand
the challenges presented in existing HLS tools, we implemented an HLS-based
LeNet (LeCun et al., 1998) accelerator on an AMD PYNQ-Z2 FPGA as a case study.

Design Process. Table 1 shows the structure of the LeNet model, which consists
of 6 layers in total. We followed the steps below to design the HLS-based
accelerator:

  1. (1)

We rewrote the LeNet model in C++ as the baseline design, which is also used
for the testbench and simulation in all subsequent steps. (2 hours)

  2. (2)

We applied _layer fusion_ and _parallelization_ to the baseline design
following the strategy summarized in Table 1. The listed parallel factors are
selected with heuristics (Zhang et al., 2015) and implemented with manual loop
tiling and loop unroll directive insertion. (10 hours)

  3. (3)

We rewrote the design to enable coarse-grained _dataflow_ and loop _pipeline_.
Specifically, we outlined all tasks, implemented off-chip memory interfaces,
and partitioned inter-task on-chip buffers with heuristics (Wang et al.,
2013). (8 hours)

  4. (4)

We iterated on different settings of parallel factors and directive
configurations by rewriting and evaluating the design in AMD Vitis HLS until
we were satisfied with the quality of the results. (20 hours)

Overall, we spent around 40 hours designing and fine-tuning the HLS-based
LeNet accelerator. Then, we parameterized all six parallel factors listed in
Table 1 and developed a TCL script exhaustively traversing each configuration
under both dataflow and non-dataflow settings. This took another 170 hours.
Finally, as a comparison, we automatically generated an HIDA-based design,
which took 0.4 minutes to compile and 9.5 minutes for AMD Vitis HLS to
generate RTL.

Results and Analysis. Figure 1 shows the exhaustive search results of the
LeNet accelerator in the throughput-resource space. Table 2 summarizes the
evaluation results and development cycles of the expert design, the best
design from the exhaustive search, and the HIDA design. The key observations
are summarized as follows:

  * •

_Dataflow designs are Pareto-dominating._ We can clearly observe a large
throughput/resource gap between the Pareto frontiers with and without
dataflow. The best dataflow design achieves 3.13$\times$ higher throughput
than the non-dataflow counterpart under the same resource constraints.

  * •

_Dataflow cannot guarantee a good trade-off._ We can observe tons of dataflow
designs dominated by non-dataflow designs. Under the same resource
constraints, the best non-dataflow design achieves 3.83$\times$ higher
throughput than the dataflow design with the worst quality.

  * •

_Dataflow design space is vast._ In the layer fusion, spatial parallelization,
and array partition steps, we have pruned a large amount of design points
based on heuristics. However, the resulting design space still contains more
than $2.4\times 10^{4}$ points and costs hundreds of CPU hours to search
exhaustively, owing to the fact that each design point takes 2-10 minutes for
Vitis HLS to evaluate.

  * •

_Dataflow design space is difficult to comprehend._ In Table 2, we can observe
that the _exhaustive_ design achieves 1.20$\times$ higher throughput than the
hand-tuned _expert_ design. We attribute this to the inter-task design space
coupling. The complicated dataflow design space makes it substantially
difficult to find the optimized design point by reasoning about the trade-off
empirically.

  * •

_Automated tool outperforms exhaustive search._ HIDA further improves the
throughput of the _exhaustive_ design by 1.06$\times$. After comparing the two
designs, we found HIDA to have automatically explored additional
parallelizable dimensions apart from the six in the _Factor_ column of Table
1, such as the feature map width and height dimensions, presenting a path that
can increase the design efficiency further. This indicates that using
heuristics suitable for single-task or non-dataflow designs may accidentally
prune away valuable design points for dataflow designs.

Need for Scalable Automation Tools. For the LeNet case study, while the expert
design took tens of hours to develop and ended up with a sub-optimal design,
HIDA only took minutes to generate the design and achieved the best quality of
results. One should expect that as the complexity and size of the target
design increase, the development time will grow dramatically, while the manual
design quality will decrease due to the vast and complicated dataflow design
space. In summary, _productivity_ , _performance_ , and _scalability_ problems
of dataflow architecture are the three strong motivators for a scalable HLS
optimization tool.

Figure 2. An IR example. affine and scf dialect are structured control flow
IRs that can be lowered to unstructured IR. All types are omitted for
simplicity.

Figure 3. HIDA framework overview.

Table 3. HIDA-IR key operations. _Region_ is a sequential list of operations
to be executed.

Operation | Description
---|---
Functional Dataflow
task |  Own a transparent region, can contain nested dispatch operations with sub-tasks.
dispatch |  Launch multiple tasks in its region.
Structural Dataflow
node |  Own an isolated region, can contain nested schedule operations with sub-nodes. Carry explicit I/O memory effect information.
schedule |  An isolated region with multiple nodes. Carry explicit scheduling information.
buffer |  A buffer with variadic stages and ports and automatic ping-pong buffering semantics. Carry explicit partition and layout information.
stream |  A stream channel with variadic entries.
Module Interface
port |  A memory or stream port with explicit type.
bundle |  A named bundle of ports.
pack |  Pack an external memory block into a port.

##  3\. Background

###  3.1. MLIR Framework

MLIR (Lattner et al., 2020; Contributors, 2023g) is a compilation framework
supporting multiple levels of functional and representational hierarchy. In
the remainder of this paper, we use _MLIR_ to refer to the MLIR framework and
_IR_ for the intermediate representation of programs in MLIR. MLIR includes a
single static assignment (SSA) style IR (Cytron et al., 1991) where an
_Operation_ is the minimal unit of code. Each operation accepts a set of typed
_Operand_ s and produces a set of typed _Result_ s. Connections between the
results of one operation and the operands of another operation describe the
SSA-style flow of data. For instance, %3 = addi %0, %c1 in Figure 2(iii) is an
operation with operands %0 and %c1 and result %3. Each operation can also be
parameterized by a set of _Attribute_ s indicating important characteristics
of the operation. Unlike operands, which typically model values produced by
other operations when a program is executed, attributes have values that are
known and fixed at compile time. A sequential list of operations without
control flow is defined as a _Block_ and a control flow graph (CFG) of blocks
is organized into a _Region_ in MLIR. Regions are, in turn, contained by
operations, enabling the description of arbitrary design hierarchy. In MLIR,
_Function_ is defined as a built-in callable operation always owning one
region. For instance, function @foo in Figure 2(iii) owns one region
containing four blocks, bb0 to bb3.

A _Dialect_ in MLIR defines a namespace for a group of related operations,
attributes, and types. MLIR not only provides multiple built-in dialects to
represent common functionalities, but also features an open infrastructure
allowing to define new dialects at different abstraction levels. _Pass_ is a
key component of compiler which traverses the IR for the purpose of
optimization or analysis. Similar to LLVM (Lattner and Adve, 2004), users can
design _Transform_ and _Analysis_ passes in MLIR to perform the IR
transformation and analysis. However, in the context of MLIR, _Transform_
typically refers to the transformation within a dialect. The transformation
between different dialects is typically referred as _Conversion_ , while the
transformation between MLIR and external representation is referred as
_Translation_. _Lowering_ is a terminology referring to the process of
lowering the abstraction level of IR.

###  3.2. Relevant MLIR Dialects

Many dialects in MLIR are immediately applicable for representing nested loop
programs commonly used in HLS. The linalg dialect provides a structured
representation of linear algebra operations. The affine dialect provides a
powerful abstraction for affine operations in order to make dependence
analysis and loop transformations efficient and reliable. The affine dialect
defines _Affine Map_ as a mathematical function that transforms a list of
affine values into a list of results. Affine operations (e.g., affine.for and
if) must take affine values as input operands, therefore the loop bounds of
affine.for operation and conditions of affine.if operation must be the
expression of affine values. The scf (structured control flow) dialect defines
control flow operations (e.g., scf.for and if) whose loop bounds or conditions
can be any SSA values. Therefore, scf operations are not constrained by the
affine requirements and can represent a wider range of programs. MLIR also
provides several fundamental built-in dialects to represent basic arithmetic
operations (e.g., addf), unstructured control flow operations (e.g., br and
cond_br), and memory-related operations (e.g., load and store). Taking Figure
2 as an example, the structured control flows in Figure 2(i) and (ii)
represented with affine and scf operations are flattened to the unstructured
br and cond_br operations in Figure 2(iii).

Figure 4. buffer, stream, and node operation syntax in _Structural_ dataflow.
_RO_ and _RW_ denote read-only and read-write.

##  4\. HIDA Overview

Figure 3 shows the overall architecture of HIDA. HIDA is built on top of the
MLIR infrastructure (Lattner et al., 2021; Contributors, 2023g) and can take
deep learning models written in PyTorch (Paszke et al., 2019) or generic HLS
C++ code as design entries and produce optimized HLS C++ code. For the PyTorch
and C++ inputs, we use Torch-MLIR (Contributors, 2023i) and Polygeist (Moses
et al., 2021) as front-ends to parse source codes. After the optimizations are
completed in HIDA, we use an HLS C++ emitter (Ye et al., 2022a) to generate
synthesizable HLS C++ code, which can then be mapped to RTL designs with
downstream HLS tools (Inc, 2022a, b, 2021). HIDA proposes two new techniques
to handle the _representation_ and _optimization_ of dataflow compilation,
which are the key enablers to tackle the challenges discussed in Section 2:

  * •

_Hierarchical Dataflow IR (HIDA-IR)._ As shown in Figure 3, HIDA consists of
_Functional_ and _Structural_ dataflow IR carved for different purposes. Table
3 summarizes the key operations of HIDA-IR. Details can be found in Section 5.

  * •

_Hierarchical Dataflow Optimizer (HIDA-OPT)._ HIDA decouples the HLS
optimization problems of _Functional_ and _Structural_ dataflow to handle HLS
designs at scale. Details can be found in Section 6.

##  5\. HIDA-IR

Currently, HLS tools (Zhao et al., 2017; Ye et al., 2022a; Zhao et al., 2022)
employ call graphs to represent HLS structures using sequential IRs. However,
due to the lack of expressiveness for the parallel characteristics and micro-
architecture of dataflow, these IRs have limited capability when used in
scalable dataflow optimization flows. To address this problem, we propose a
holistic HIDA-IR with two levels of representation, which we refer to as
_Functional_ and _Structural_ dataflow. The _Functional_ dataflow is designed
to capture the high-level characteristics and hierarchy of HLS designs,
driving the algorithmic optimizations and task fusion. In contrast, the
_Structural_ dataflow is a low-level abstraction that captures the micro-
architectural details and is optimized to handle the scheduling and
parallelization.

###  5.1. Functional Dataflow

Hierarchical Structure. In the _Functional_ dataflow, we introduce a dispatch
operation that contains the computation graph to be dispatched. Within the
dispatch operation, all graph nodes are partitioned into multiple task
operations to represent the dispatch strategy. As accelerators often have
multiple levels of dataflow to achieve higher parallelism, HIDA-IR supports a
hierarchical structure by allowing the recursive nesting of task and dispatch
operations. Figure 3 visualizes a hierarchical _Functional_ dataflow, where
_Task6_ contains three sub-tasks that can be executed in a dataflow manner to
hide the latency of loads and stores, allowing us to utilize the computational
capability to a greater extent.

Transparent from Above. At the _Functional_ level, tasks often need to be
manipulated as different dispatch strategies can lead to different trade-offs.
Based on this observation, the dispatch and task operations are designed to be
transparent and share the global context, simplifying the process of the
fusing and splitting of tasks. As a result, we can efficiently explore various
dispatch strategies at the _Functional_ level. Meanwhile, thanks to the
transparency, buffers and tensors defined in the global context can be
accessed by tasks at all hierarchies without indirection. Therefore, the
_Functional_ dataflow can enable effective algorithmic optimizations for both
PyTorch and C++ programs, which model the computations at tensor and memory
levels, respectively.

###  5.2. Structural Dataflow

Memory-Mapped and Stream Buffer. In order to precisely capture the on-chip and
off-chip memory accessing behaviors, we introduce two types of buffers at the
_Structural_ dataflow level, the memory-mapped buffer and the stream buffer,
which are represented with the buffer and stream operations, respectively.
Figure 4 shows their syntax, where % denotes a single static assignment (SSA)
value (Cytron et al., 1991). The embedded partition and data layout attributes
of the buffer operation are designed to be converted to semi-affine maps
(Contributors, 2023e), enabling polyhedral-based dependency analysis and
transformation (Benabderrahmane et al., 2010) in HIDA-OPT. Notably, to
facilitate dataflow optimizations, buffer operations inherently carry ping-
pong buffering semantics, allowing buffer instances to interleave the accesses
from producers and consumers to improve the communication efficiency. Figure 3
visualizes the combined usage of the two types of buffers, where the red boxes
and blue arrows represent the memory-mapped buffer and stream buffers. Dashed
blue arrows denote single-bit stream buffers. In addition to the buffers, we
introduce the port operation to represent memory-mapped or stream interfaces,
capturing the interface characteristics, such as latency, that can have a
considerable impact on the dataflow efficiency. For instance, in Figure 3,
_Node0_ , _Node1_ , and _Node2_ are scheduled to communicate through external
memory, where the AXI interfaces are modeled with port operations.

Isolated from Above. In the _Structural_ dataflow, we introduce schedule and
node operation as the counterparts of dispatch and task operation. While
_Structural_ dataflow has a hierarchical structure similar to _Functional_
dataflow, an important distinction between the two is that the schedule and
node operations are isolated from the external context. Therefore, external
values must be passed into schedule and node as arguments. In addition, the
node operation carries explicit memory effect information for each argument to
avoid unnecessary inter-node effect analysis. Figure 4 shows the syntax of
node operation, where %buffer and %stream are passed in as read-only arguments
in this specific example. For simplicity, we omit the read-write arguments and
constant parameters in Figure 4. The rationale behind this design decision is
driven by how the _Structural_ dataflow carries the architecture optimization.
By isolating the context of schedule and node, the dataflow optimization
problem can be cleanly partitioned into multiple local intra-node
optimizations and global inter-node optimization, leading to a decoupled
scalable solution. Details of the optimization process is elaborated in
Section 6.

Figure 5. Integration with MLIR dialects.

###  5.3. Integration with MLIR Dialects

HIDA reuses a set of MLIR built-in dialects to represent the common program
components in PyTorch or C/C++. Figure 5 illustrates the integration of HIDA
with the built-in MLIR dialects. The vertical axis of Figure 5 represents the
various abstraction levels of the dialects. Horizontally, all dialects are
categorized into four different types: _structure_ , _data_ , _payload_ , and
_control-flow_. At every abstraction level, the corresponding four types of
dialects are combined with each other to represent the complete functionality
of a program. The _Functional_ dataflow is first combined with tensor, arith,
and linalg dialects to represent the tensor-level programs compiled from
PyTorch. Then, the tensor and linalg dialects are lowered to memref and affine
dialects, respectively, while the lowered IRs are still combined with the
_Functional_ dataflow due to its adaptability with both tensor and memory
semantics. Once the optimizations at the _Functional_ dataflow level are
completed, the _Functional_ dataflow is lowered to the _Structural_ dataflow,
while the memref operations are lowered to the _Structural_ buffer and stream
operations. Note that the affine dialect is used in both the _Functional_ and
_Structural_ dataflows for loop analyses and transformations. HIDA reuses the
_Primitive_ and _Directive_ IRs from ScaleHLS (Ye et al., 2022a) to represent
the HLS-specific structures, such as the loop pipelining directive. By
integrating with the existing dialects, HIDA can carry out loop and directive-
level HLS optimizations in a hierarchical manner.

##  6\. HIDA-OPT

Although previous works (Ye et al., 2022a; Ejjeh et al., 2022) have enabled
inter-task parallelization through dataflow, they could not conduct dataflow-
oriented optimizations. Specifically, ScaleHLS (Ye et al., 2022a) could
automatically legalize a computation graph into a dataflow model and enable
code generation but ignored the inter-task design space coupling (Jun et al.,
2023), resulting in suboptimal dataflow designs. HPVM2FPGA (Ejjeh et al.,
2022) used an ML-driven algorithm (Nardi et al., 2019) for DSE, but it only
introduced a boolean parameter to enable/disable global dataflow, again,
leading to the restricted search of the design space. In this section, we
propose a HIDA-OPT solution consisting of five steps to tackle the dataflow
optimization problem.

Algorithm 1 Functional dataflow construction

1:$m$, top module of the initial computation graph

2:Updated $m$, top module of the _Functional_ dataflow

3:for $n$ in postorder_walk($m$, has_region()) do

4: if is_dispatchable(get_region($n$)) then

5: $d\leftarrow$ wrap_ops(get_ops($n$), new(dispatch))

6: for $op$ in get_ops($d$) do

7: wrap_ops({$op$}, new(task))

###  6.1. Functional Dataflow Construction

We leverage the transformations available in MLIR (Lattner et al., 2021;
Contributors, 2023g) to generate a _hierarchical_ computation graph at the
level of linear algebra (Contributors, 2023f) or loop (Contributors, 2023e).
Algorithm 1 shows the pseudo-code of converting the initial computation graph
to the _Functional_ dataflow. From line 1 to 3, we wrap each _dispatchable_
region with a dispatch operation in a bottom-up manner, where a region is
defined as _dispatchable_ if it is owned by an iterative operation, such as
loop and func, while containing at least two iterative operations. For
instance, a loop region containing two child loops is considered to be
_dispatchable_ as the two child loops can be dataflowed. Then, from line 4 to
5, each operation is wrapped with a separate task operation to construct a
legal dataflow model.

Algorithm 2 Functional dataflow task fusion

1:$m$, top module of the _Functional_ dataflow

2:$patterns$, set of profitable task fusion patterns

3:Updated $m$, top module of the partitioned dataflow

4:for $d$ in preorder_walk($m$, is_instance(dispatch)) do

5: $worklist\leftarrow$ queue(get_tasks($d$))

6: while not is_empty($worklist$) do

7: $t\leftarrow$ pop($worklist$)

8: if $t^{\prime}\leftarrow$ get_matched_task($t$, $patterns$) then

9: push($worklist$, wrap_ops({$t$, $t^{\prime}$}, new(task)))

10: repeat $t_{0},t_{1}\leftarrow$ get_least_critical_tasks($d$, 2)

11: wrap_ops({$t_{0}$, $t_{1}$}, new(task))

12: until not is_fusion_profitable($t_{0},t_{1}$)

13: simplify_dispatch_hierarchy($d$)

###  6.2. Functional Dataflow Optimization

Once the initial _Functional_ dataflow is constructed, we can optionally fuse
dataflow tasks to balance the task workloads while reducing the communication
cost. Algorithm 2 shows the task fusion process, where the inputs are the
initial dataflow and a set of pre-defined profitable fusion patterns, such as
element-wise operations fusion. From line 1 to 10, we recursively partition
each dispatch operation in a top-down manner. Specifically, we first fuse
adjacent tasks into new tasks through a pattern-driven worklist algorithm
(lines 2 to 6). The pre-defined task fusion patterns are recursively applied
to the dataflow until no pattern can be matched. Then, we continuously fuse
the least critical two adjacent tasks to re-balance the dataflow until the
fusion begins to generate a new critical task (lines 7 to 9). Finally, in line
10, we simplify the hierarchy by canonicalizing the dispatch and task
operations. For instance, a task containing only one sub-task should be
canonicalized to a single task. Notably, HIDA-IR’s systematic dataflow
representation allows the task fusion process to be expanded with different
heuristics or algorithms under varying scenarios.

Figure 6. _Functional_ to _Structural_ dataflow lowering.

###  6.3. Structural Dataflow Construction

The _Functional_ dataflow can be lowered to _Structural_ dataflow for low-
level optimizations and code generation. The dataflow lowering is composed of
three procedures: (1) buffer operation generation; (2) dispatch to schedule
operation mapping; (3) task to node operation mapping. Figure 6 shows a
simplified example of the _Functional_ to _Structural_ dataflow lowering,
where the two task operations in Figure 6(a) are mapped to node operations in
Figure 6(b) correspondingly. The distinction between tensor and memory
semantics draws a line between the _Functional_ and _Structural_ dataflow:
tensors are immutable objects passed between producers and consumers directly;
buffers are mutable objects that can be instantiated in hardware and modified
multiple times. Therefore, in Figure 6(a), the %tensor object is produced by
the first task operation and directly consumed inside of the second task
operation. In contrast, we can observe that the original %tensor object is
lowered to a buffer operation in Figure 6(b). Correspondingly, the first node
operation becomes a user of the %buffer object with read-write effect, while
the second node operation uses the %buffer object with read-only effect, given
the syntax defined in Figure 4.

Automation. For procedure (1) above, each tensor result of each task operation
is converted to a buffer operation with default partition fashions, tiling,
vectorization factors, and placement annotations. For procedures (2) and (3)
above, because the _Functional_ operations are transparent while the
_Structural_ operations are isolated from above context, the live-ins and
memory effects are analyzed during the mapping. As shown in Figure 4, the
arguments of the node operations are explicitly grouped based on their memory
effects. Notably, procedure (1) to (3) can generate a legal _Structural_
dataflow, and the node and buffer operations will be optimized later in the
dataflow balancing and parallelization.

Figure 7. Eliminate multiple producers. Double arrows indicate both read and
write on a buffer. For instance, in (a), _Node1_ may first read from _Buf2_
and then write results to it.

###  6.4. Structural Dataflow Optimization

At the _Structural_ dataflow level, we propose two optimizations that are
crucial for dataflow efficiency but have not been thoroughly studied in
existing tools: _(1) Multi-producer elimination_ , which can eliminate
multiple nodes writing to the same buffer and improve the dataflow
parallelism; _(2) Data path balancing_ , which can balance different data
paths by inserting on-chip or external buffers, balancing the pipeline
execution rate to achieve the best throughput.

####  6.4.1. Eliminate Multiple Producers

Dataflow architectures often contain buffers written to by multiple producers,
leading to inefficient dataflow execution. For example, in Figure 7(a),
correctly managing the memory access of _Buf2_ is challenging as _Node1_ and
_Node2_ simultaneously write to it. As a result, to preserve correctness, the
dataflow structure must be executed sequentially.

Algorithm 3 Multiple producers elimination

1:$s$, dataflow schedule

2:Updated $s$, transformed dataflow schedule

3:for $b$ in get_internal_buffers($s$) do

4: $p\\_list\leftarrow$ topo_sort(get_producers($b$))

5: for $p$ in drop_front($p\\_list$) do $\triangleright$ exclude the 1st
producer

6: $b^{\prime}\leftarrow$ clone($b$)

7: if read_effect($p$, $b$) then

8: $copy\leftarrow$ new(copy, $b$, $b^{\prime}$)

9: insert_to_front($copy$, get_region($p$))

10: for $u$ in get_users($b$) do

11: if dominate($p$, $u$) then $\triangleright$ include $p$ itself

12: replace_use_with($b$, $b^{\prime}$, $u$)

13:for $b$ in get_external_buffers($s$) do

14: $p\\_list\leftarrow$ get_producers($b$)

15: wrap_ops($p\\_list$, new(node)) $\triangleright$ merge producers

Solution. HIDA-OPT resolves this problem considering two cases: _(1) Buffer
duplication._ In the case of Figure 7(a), we eliminate the multiple producers
by duplicating _Buf2_ into the _Buf2’_ as shown in Figure 7(b). As a result,
_Node1_ and _Node2_ no longer write to _Buf2_ simultaneously, allowing the
structure to be scheduled in a pipelined manner. This duplication is possible
due to the semantics of the _Structural_ IR, where _Buf2_ is allocated inside
the context of its parent schedule, ensuring that no external side-effect
operation can access _Buf2_. _(2) Node fusion._ For Figure 7(c), _Node1_ and
_Node2_ write to _Buf2_ allocated outside of its parent schedule. In this
case, we cannot apply the same transformation as case (1) because there may
exist an external node having write-effect on _Buf2_. Specifically, if we
duplicate _Buf2_ into _Buf2’_ , only the original _Buf2_ can be updated by the
external write-effect nodes, leaving outdated data in _Buf2’_. Therefore, in
the next iteration, _Buf2’_ may hold incorrect data and eventually lead to
incorrect functionality. Thus, to eliminate the multi-producer violation, we
fuse _Node1_ and _Node2_ into a new node and sequentially execute them as
shown in Figure 7(d).

Automation. Lines 1 to 10 of Algorithm 3 show the pseudo-code of case (1)
above. For each internal buffer, we first collect all its _producer_ s and
sort them based on SSA dominance to maintain the predetermined memory access
order in the subsequent transformations. Then, for each producer except the
first one, we duplicate a new buffer _b’_ for it (line 4) and create an
explicit memory copy from the original buffer _b_ to _b’_ (lines 5 to 7) if
the current producer _p_ reads from _b_. Finally, we replace uses of _b_ with
_b’_ if the user is dominated by the _p_ (lines 8 to 10), leaving exactly one
producer for the original buffer _b_. Lines 11 to 13 of Algorithm 3 shows the
pseudo-code of case (2) that merges all producers of each external buffer into
a single node to avoid data racing.

Complexity. One can observe that case (2) employs a more conservative
transformation and enables the dataflow execution of the whole design by only
enforcing the sequential execution of _Node1_ and _Node2_. One may argue for a
more comprehensive inter-node analysis of _Buf2_ to determine whether the
external write-effect nodes will intervene if we were to duplicate _Buf2_ \-
this could work on small dataflow architectures, but it does not scale well.
Many dataflow nodes at different hierarchies can access shared buffers; as a
result, an inter-node analysis has a complexity of $O(mn^{2})$, where $m$
denotes the number of shared buffers and $n$ is the number of nodes accessing
the same buffer.

Figure 8. Balance data paths. Dash line block represents a 1-bit token buffer.
Soft FIFO is allocated in external memory and interfaced with dataflow through
AXI interconnect.

####  6.4.2. Balance Data Path

A complicated dataflow structure often has multiple data paths; some paths may
have more dataflow nodes to execute. If left unoptimized, the unbalanced paths
can significantly degrade the overall performance of the final design. For
instance, in Figure 8(a), the _Node0-Node1-Node2_ path is longer than the
_Node0-Node2_ path. As a result, _Node0_ must wait until the longer path
completes before it can process the next data frame. This situation is very
common in real-world applications, such as ResNet (He et al., 2016), which has
shortcut paths in the residual blocks. Note that there are two levels of
balancing in HIDA: one is the _data path_ balancing we discuss in this
section; the other is _node delay_ balancing that will be handled separately
during the dataflow parallelization.

Solution. HIDA-OPT resolves this issue using two methods: _(1) On-chip buffer
duplication._ We can duplicate buffers on the shorter data paths to balance
the execution speed. For instance, in Figure 8(b), _Buf3_ is duplicated to
_Buf3’_ , followed by an automatic insertion of a copy node between _Buf3_ and
_Buf3’_. Through this approach, the _Node0-Copy-Node2_ data path can execute
in a pipelined manner at the same rate as another data path, such that _Node0_
no longer needs to wait. _(2) Soft FIFO in external memory._ As shown in
Figure 8(c), a soft FIFO is allocated in the external memory to substitute
_Buf3_. The FIFO is _soft_ because data is not really shifted in the FIFO.
Instead, the memory access addresses of dataflow nodes are rotated to access
the correct data. For instance, in Figure 8(c), _Node0_ is writing to _Buf3_ ,
while _Node1_ and _Node2_ are reading from _Buf3’_ and _Buf3”_ , respectively.
Then in the next dataflow iteration, _Node0_ will write to _Buf3”_ , and
_Node1_ and _Node2_ will read from _Buf3_ and _Buf3’_ , respectively.

⬇

1float A[32][16];

2NODE0_I: for (int i=0; i<32; i++)

3 NODE0_K: for (int k=0; k<16; k++)

4 A[i][k] = ...; // Load array A.

5

6float B[16][16];

7NODE1_K: for (int k=0; k<16; k++)

8 NODE1_J: for (int j=0; j<16; j++)

9 B[k][j] = ...; // Load array B.

10

11float C[16][16];

12NODE2_I: for (int i=0; i<16; i++)

13 NODE2_J: for (int j=0; j<16; j++)

14 NODE2_K: for (int k=0; k<16; k++)

15 C[i][j] = A[i*2][k] * B[k][j];

Table 4. Node connections appearing in Listing 5. _S_ and _T_ denote the
source and target nodes of the connection. $\emptyset$ denotes empty.

Source | Target | Buffer | Permutation Map | Scaling Map
---|---|---|---|---
S-to-T | T-to-S | S-to-T | T-to-S
Node0 | Node2 | A |  [0, $\emptyset$, 1] | [0, 2] | [0.5, 1] |  [2, $\emptyset$, 1]
Node1 | Node2 | B |  [$\emptyset$, 1, 0] | [2, 1] | [1, 1] |  [$\emptyset$, 1, 1]

Table 5. Node parallelization results of Listing 5 assuming a maximum parallel
factor of 32.

Node | Intensity | Parallel Factor | Loop Unroll Factors
---|---|---|---
w/o IA | w/ IA | IA+CA | IA | CA | Naive
Node0 | 512 | 32 | 4 | [4, 1] | [2, 2] | [8, 4] | [4, 8]
Node1 | 256 | 32 | 2 | [1, 2] | [1, 2] | [4, 8] | [4, 8]
Node2 | 4,096 | 32 | 32 | [4, 8, 1] | [4, 8, 1] | [4, 8, 1] | [4, 8, 1]

Elastic Node Execution. For method (2) above, after the soft FIFO is
generated, the original _Buf3_ is substituted with external memory interfaces,
such as memory-mapped AXI interfaces. Therefore, the dependencies between
dataflow nodes associated with _Buf3_ are no longer explicit - they access
external memories through assigned addresses instead of sharing _Buf3_. To
maintain the correct execution order, HIDA can automatically construct a token
flow between these dataflow nodes. For instance, in Figure 8(c), once _Node0_
completes its computation, it will send a _Token_ , and _Node1_ and _Node2_
will not start until they receive the _Token_ and _Token’_ respectively. This
way, the token flows elastically maintain the execution order, and no static
logic in the form of an FSM is needed to control the execution.

###  6.5. Structural Dataflow Parallelization

After dataflow optimization, HIDA will parallelize each node to improve the
overall throughput and latency. However, automatic parallelization is often
very challenging for several reasons: _(1) Memory data layout._ Degradation of
dataflow performance may occur without proper alignment between the
computation pattern and memory layouts. _(2) Connectedness of nodes._ We
define two nodes as having a _connection_ if they communicate through shared
buffers. Due to reason (1), when two nodes are connected, the parallelism of
each node should be aware of the shared memory layout. _(3) Computation
intensity of nodes._ We define the number of operations contained by a node as
its _intensity_. To maximize the overall throughput while minimizing resource
utilization, the optimal parallel factors should be proportional to the
intensity of dataflow nodes. Due to the coupling of local design spaces, the
local optimality of the scheduling of each node can no longer automatically
lead to the global optimal solution for dataflow architectures.

####  6.5.1. Intensity and Connection-Aware Approach

The challenges discussed above are tightly coupled and need to be handled
holistically. In HIDA, we propose an intensity-aware (IA) and connection-aware
(CA) approach to determine the best parallelization strategies:

Step (1) Intensity and Connection Analysis. We first construct two maps to
record the intensity and connections of each dataflow node. For each
connection, we record the source and target node, associated buffer,
permutation maps holding the loop level alignment, and scaling maps holding
the stride alignment. For instance, in Listing 5, _Node0_ and _Node2_ are
connected through array _A_. Because _Node0_ writes to array _A_ with the
first and second loops, while _Node2_ reads with the first and third loops,
the _Node0-to-Node2_ permutation map is [0, $\emptyset$, 1], where $\emptyset$
denotes empty. Meanwhile, the _Node0-to-Node2_ scaling map is [0.5, 1] as
_Node2_ reads array _A_ with a stride of 2. Table 5 shows the two connections
in Listing 5. The permutation maps and scaling maps will be used to align the
loop unroll factors of connected nodes in step (4) below.

Step (2) Node Sorting. We then sort all dataflow nodes into a worklist in
descending order of the number of connections with the computation intensity
as tie-breaker. This determines the order in which we parallelize each node.
Intuitively, the parallelization strategy of a node with more connections will
affect more nodes, while higher-intensity nodes, being more computationally
complex, are more sensitive to optimization. Therefore, following the results
of step (1), the order of nodes in Listing 5 in terms of criticality is
_Node2_ , _Node0_ , and then _Node1_.

Step (3) Parallel Factor Generation. Guided by resource constraints, HIDA-OPT
determines the maximum parallel factor that can be applied to a dataflow node.
Then, the parallel factor of each node will be set proportionally to its
intensity. In Listing 5, assuming the maximum parallel factor is 32, the
parallel factor of each node is listed in Table 5.

Algorithm 4 Node parallelization

1:$n$, dataflow node

2:Updated $n$, transformed dataflow node

3:$constraints\\_list\leftarrow$ new([][]) $\triangleright$ list of
constraints

4:$c\\_list\leftarrow$ get_connected_nodes($n$)

5:for $c$ in $c\\_list$ do

6: $unroll\\_factors\leftarrow$ get_unroll_factors($c$)

7: $s\\_map\leftarrow$ get_scaling_map($c$) $\triangleright$ from step (1)

8: $p\\_map\leftarrow$ get_permutation_map($c$) $\triangleright$ from step (1)

9: $constraints\leftarrow$ permute($unroll\\_factors\odot s\\_map$, $p\\_map$)

10: append($constraints\\_list$, $constraints$)

11:$parallel\\_factor\leftarrow$ get_parallel_factor($n$) $\triangleright$
from step (3)

12:$dse\leftarrow$ init_dse($n$) $\triangleright$ initialize DSE engine

13:repeat $unroll\\_factors\leftarrow$ propose_unroll_factors($dse$)

14: $is\\_valid\leftarrow$ true

15: for $constraints$ in $constraints\\_list$ do

16: for $constr$, $uf$ in zip($constraints$, $unroll\\_factors$) do

17: if $constr$ % $uf$ != 0 and $uf$ % $constr$ != 0 then

18: $is\\_valid\leftarrow$ false

19: if product($unroll\\_factors$) ¿= $parallel\\_factor$ then

20: $is\\_valid\leftarrow$ false

21: if $is\\_valid$ then

22: evaluate_and_evolve_dse($unroll\\_factors$, $dse$)

23: else

24: evolve_dse($unroll\\_factors$, $dse$)

25:until is_converged($dse$) or is_early_terminated($dse$)

26:apply_unrolling($n$, get_final_unroll_factors($dse$))

Step (4) Node Parallelization. Dataflow nodes are parallelized in the order
determined by step (2). Algorithm 4 shows the pseudo-code of node
parallelization. For each node _n_ , we first query whether any nodes
connected with it have been parallelized (line 2). If so, each connected
node’s unroll factors are multiplied with the scaling map and then permutated
with the permutation map generated in step (1) (lines 3 to 8). The processed
unroll factors are recorded in a _constraints_list_ to constrain the intra-
node DSE. Meanwhile, in line 9, we also get the parallel factor of node _n_
generated in step (3) to constrain the overall parallelism of _n_.

With all the constraints generated, lines 10 to 23 of Algorithm 4 illustrate a
simplified intra-node DSE for node _n_. In each iteration of exploration, the
DSE engine will propose new unroll factors for evaluation. However, the
proposed factors could fail to meet the constraints in two cases: (1) If any
of the unroll factors are mutually indivisible with the corresponding
constraint (lines 13 to 16); or (2) the overall parallelism exceeds the pre-
calculated parallel factor (lines 17 to 18). Case (1) can cause unaligned
inter-node memory access behavior, while case (2) can cause imbalanced
dataflow execution, both leading to sub-optimal dataflow efficiency. If all
the constraints are fulfilled, HIDA employs a quality of results (QoR)
estimator from (Ye et al., 2022a) to evaluate the performance and resource
utilization of the proposed factors (line 20). Then, the evaluation results or
failure message are passed to the DSE and evolve the exploration. Finally, in
line 23, we terminate the DSE if the results have converged or met the early
termination criteria. The proposed algorithm can identify the Pareto frontier
in the local design space and selects the best design point under the imposed
constraints.

Table 6. Array partition results of Listing 5. Array | Array Partition Factors | Bank Number
---|---|---
IA+CA | IA | CA | Naive | IA+CA | IA | CA | Naive
A | [8, 1] | [8, 2] | [8, 4] | [8, 8] | 8 | 16 | 32 | 64
B | [1, 8] | [2, 8] | [4, 8] | [8, 8] | 8 | 16 | 32 | 64
C | [4, 8] | [4, 8] | [4, 8] | [4, 8] | 32 | 32 | 32 | 32

####  6.5.2. Discussion

We summarize the results of IA+CA, IA-only, CA-only, and naive parallelization
in Table 5, where the naive solution applies the maximum parallel factor 32 to
all dataflow nodes. One can observe our IA+CA approach achieves the best
unroll factors, eventually leading to the least computation resource
utilization. Meanwhile, IA and CA can also reduce memory resource utilization.
Table 6 shows the array partition results. Array partitioning is an HLS
technique that divides a large array into smaller sub-arrays to enable
parallel access. One can observe that our IA+CA approach achieves the lowest
number of banks for arrays appearing in Listing 5, resulting in the lowest
memory utilization. For this small example, the margin can already reach
8$\times$ on arrays _A_ and _B_ compared to the naive solution. For large-
scale dataflow applications, the parallelization solution can determine
whether the overall solution is scalable; an ablation study is conducted in
Section 7.3.

##  7\. Evaluation

To evaluate HIDA, we use FPGAs as the target platform and perform two sets of
experiments using C++ and PyTorch inputs and an ablation study on a ResNet-18
model. As depicted in Figure 3, AMD Vitis HLS 2022.1 (Inc, 2022a) is used for
generating RTL code. All reported performances and resource utilization are
collected from the synthesis results of Vitis HLS.

Table 7. Evaluation results for C++ kernels. _ScaleHLS_ designs are automatically generated by (Ye et al., 2022a). _SOFF_ results are ported from their paper (Jo et al., 2020), which compared with SDAccel (previous name of Vitis). _Vitis_ designs are solely optimized by Vitis HLS. Kernel |  HIDA Compile Time (s) |  LUT Number |  FF Number |  DSP Number | Throughput (Samples/s)*
---|---|---|---|---|---
HIDA |  | ScaleHLS (Ye et al., 2022a)
---
| SOFF (Jo et al., 2020)
---
| Vitis (Inc, 2022a)
---
2mm | 0.65 | 38.8k | 27.4k | 269 | 239.22 |  122.39 (1.95$\times$) |  30.67 (7.80$\times$) |  1.23 (194.88$\times$)
3mm | 0.79 | 38.7k | 27.8k | 243 | 175.43 |  92.33 (1.90$\times$) | - |  1.04 (167.99$\times$)
atax | 2.06 | 44.6k | 34.6k | 260 | 1,021.39 |  932.26 (1.10$\times$) |  2,173.17 (0.47$\times$) |  103.18 (9.90$\times$)
bicg | 0.72 | 16.0k | 15.1k | 61 | 2,869.69 |  2,869.61 (1.00$\times$) |  2,295.75 (1.25$\times$) |  104.19 (27.54$\times$)
correlation | 0.91 | 14.5k | 12.3k | 66 | 67.33 |  59.77 (1.13$\times$) |  3.96 (16.99$\times$) |  1.32 (50.97$\times$)
gesummv | 0.60 | 34.2k | 22.8k | 232 | 31,685.68 |  31,685.68 (1.00$\times$) |  3,466.70 (9.14$\times$) |  266.65 (118.83$\times$)
jacobi-2d | 1.98 | 91.4k | 56.6k | 352 | 257.27 |  128.63 (2.00$\times$) | - |  2.71 (94.95$\times$)
mvt | 0.42 | 23.8k | 16.5k | 162 | 9,979.04 |  4,989.02 (2.00$\times$) |  870.01 (11.47$\times$) |  62.13 (160.62$\times$)
seidel-2d | 3.59 | 5.5k | 2.5k | 4 | 0.14 |  0.14 (1.00$\times$) | - |  0.11 (1.28$\times$)
symm | 1.05 | 14.9k | 9.5k | 74 | 2.62 |  2.62 (1.00$\times$) | - |  2.02 (1.29$\times$)
syr2k | 0.69 | 14.3k | 12.8k | 78 | 27.68 |  27.67 (1.00$\times$) | - |  1.44 (19.23$\times$)
Geo. Mean | 0.99 |  |  |  |  | 1.29$\times$ | 4.49$\times$ | 31.08$\times$
* Numbers in () show throughput improvements of HIDA over others.

###  7.1. C++ Kernels Evaluation

Experiment Settings. We evaluate HIDA with a set of C++ benchmarks from
PolyBench (Pouchet et al., 2012). The benchmarks cover multiple categories,
including blas routines (gesummv, symm, and syr2k), linear algebra kernels
(2mm, 3mm, atax, bicg, and mvt), data mining (correlation), and stencils
(jacobi-2d and seidel-2d). The target platform is AMD-Xilinx ZU3EG FPGA. Table
7 shows the evaluation results. Although Vitis HLS can automatically apply
optimizations such as loop pipeline, it cannot conduct complex dataflow
analysis and optimizations. As a result, HIDA achieves 31.08$\times$ higher
throughput on average over Vitis HLS.

Comparison with Previous Works. Compared with the state-of-the-art (SOTA) HLS
optimization framework ScaleHLS (Ye et al., 2022a), and another HLS framework
SOFF (Jo et al., 2020), HIDA achieved 1.29$\times$ and 4.49$\times$ higher
throughput, respectively. We observed that for single-loop kernels (bicg,
gesummv, seidel-2d, symm, and syr2k), the performance of HIDA was on par with
ScaleHLS due to these kernels not presenting any dataflow optimization
opportunities. For the multi-loop kernels, HIDA outperforms ScaleHLS due to
dataflow optimizations. When only considering multi-loop kernels, HIDA
achieves 1.57$\times$ higher throughput than ScaleHLS. We concluded that the
dataflow scheduling and parallelization problems are pervasive based on the
evaluation results. Thus, HIDA-OPT can better optimize these kernels,
ultimately leading to an increased performance.

Table 8. Evaluation results for PyTorch models. _DNNBuilder_ results are directly from their paper (Zhang et al., 2018). To make fair comparison, we constrained the FPGA resources to the same with DNNBuilder. _ScaleHLS_ designs are automatically generated by (Ye et al., 2022a). Model |  HIDA Compile Time (s) |  LUT Number |  DSP Number |  | Throughput (Samples/s)*
---
| DSP Efficiency*
---
HIDA |  | DNNBuilder
---
(Zhang et al., 2018)
| ScaleHLS
---
(Ye et al., 2022a)
HIDA |  | DNNBuilder
---
(Zhang et al., 2018)
| ScaleHLS
---
(Ye et al., 2022a)
ResNet-18 | 83.1 | 142.1k | 667 | 45.4 | - |  3.3 (13.88$\times$) | 73.8% | - |  5.2% (14.24$\times$)
MobileNet | 110.8 | 132.9k | 518 | 137.4 | - |  15.4 (8.90$\times$) | 75.5% | - |  9.6% (7.88$\times$)
ZFNet | 116.2 | 103.8k | 639 | 90.4 |  112.2 (0.81$\times$) | - | 82.8% |  79.7% (1.04$\times$) | -
VGG-16 | 199.9 | 266.2k | 1118 | 48.3 |  27.7 (1.74$\times$) |  6.9 (6.99$\times$) | 102.1% |  96.2% (1.06$\times$) |  18.6% (5.49$\times$)
YOLO | 188.2 | 202.8k | 904 | 33.7 |  22.1 (1.52$\times$) | - | 94.3% |  86.0% (1.10$\times$) | -
MLP | 40.9 | 21.0k | 164 | 938.9 | - |  152.6 (6.15$\times$) | 90.0% | - |  17.6% (5.10$\times$)
Geo. Mean | 108.7 |  |  |  | 1.29$\times$ | 8.54$\times$ |  | 1.07$\times$ | 7.49$\times$
* Numbers in () show throughput/DSP efficiency improvements of HIDA over others.

###  7.2. PyTorch Models Evaluation

Experiment Settings. We evaluate HIDA with a set of deep neural network (DNN)
benchmarks written in PyTorch to understand its performance on large-scale
dataflow applications. The benchmarks cover multiple categories of DNN models,
including image classification (ResNet-18 (He et al., 2016), MobileNet (Howard
et al., 2017), ZFNet (Zeiler and Fergus, 2014), and VGG-16 (Simonyan and
Zisserman, 2014)), object detection (YOLO (Redmon et al., 2016)), and fully-
connected networks (MLP). The optimization for these models exhibit
significant variations under dataflow setting, owing to the distinct layer
types and interconnections. The targeted platform is one super logic region
(SLR) of an AMD-Xilinx VU9P FPGA. Table 8 shows the evaluation results. Even
for these complicated DNN models, HIDA only takes 108.7 seconds on average to
compile them into dataflow implementations.

Figure 9. Memory utilization compared with ScaleHLS (Ye et al., 2022a).

Comparison with Previous Works. Again, we compare HIDA with ScaleHLS (Ye et
al., 2022a), where we observe an 8.54$\times$ higher throughput. The
throughput gains are much more significant than the C++ kernels due to large
DNN models exposing more opportunities for HIDA to optimize the dataflow
architecture. For ZFNet and YOLO, ScaleHLS cannot produce results due to the
DNNs having irregular convolution sizes and high-resolution inputs,
respectively, demonstrating the superior flexibility and scalability of HIDA.
For the four benchmarks supported by ScaleHLS, we use DSP efficiency to
compare the two frameworks, calculated as:

(1) $Efficiency_{DSP}=\frac{Throughput\times OPs}{Number_{DSP}\times
Frequency},$

where $OPs$ denotes the number of multiply-accumulate (MAC) operations per
sample of the DNN, _Throughput_ is samples per second, and $Frequency$ denotes
the clock frequency constant at 200MHz for both ScaleHLS and HIDA. DSP
efficiency is a common metric for comparing the efficiency of DNN accelerators
across different platforms or frameworks. A 100% of DSP efficiency indicates
all instantiated DSPs in the accelerator continuously operating without
stalling. HIDA achieves 7.49$\times$ higher DSP efficiency than ScaleHLS on
average and 14.24$\times$ for ResNet-18. We attribute the much higher
efficiency for ResNet-18 to HIDA’s ability to optimize shortcut data paths.
For VGG-16, we observe an over 100% DSP efficiency, attributing the excess
percentage to the back-end RTL generator where MAC operations can be
instantiated with LUTs when resources are abundant.

Apart from the throughput and efficiency improvements, we also observe
substantial on-chip memory reduction by HIDA compared to ScaleHLS. As Figure 9
shows, HIDA can reduce memory utilization by 41.5$\times$ to 75.6$\times$ due
to several factors: (1) HIDA can leverage loop tiling and local buffer
creation to only cache small tiles of intermediate results while enabling the
dataflow execution. In comparison, ScaleHLS must keep all intermediate results
on-chip due to the lack of external memory access support. (2) The IA+CA
parallelization can drastically reduce the buffer sizes. In summary, HIDA can
utilize computation and memory resources more efficiently and achieve
substantial throughput improvements on DNN models compared to SOTA frameworks.

Comparison with Dedicated DNN Accelerator. In addition to the comparison with
HLS optimization frameworks, we further compare HIDA with a dedicated DNN
acceleration framework, DNNBuilder (Zhang et al., 2018). DNNBuilder has RTL-
based and human-designed DNN IPs and can enable the dataflow execution of all
the instantiated IPs to achieve SOTA throughput and efficiency on FPGAs. As
shown in Table 8, HIDA achieves 1.29$\times$ and 1.07$\times$ higher
throughput and DSP efficiency compared to DNNBuilder, which already has an
extremely high DSP efficiency. Note that DNNBuilder doesn’t support ResNet-18
and MobileNet due to its lack of support for shortcut paths and depthwise
convolutions. Through this comparison, we demonstrate the productivity and
performance of HIDA outperforming a dedicated DNN acceleration framework.
Additionally, we demonstrate the flexibility of HIDA, which can automatically
adapt to a wide range of computational patterns.

###  7.3. Ablation Study on ResNet-18

Figure 10. Parallel factor and tile size ablation on ResNet-18.

Parallel Factor and Tile Size Ablation. To understand the scalability of HIDA,
we perform an ablation study on ResNet-18 by sweeping the maximum parallel
factor from 1 to 256 and tile size from 2 to 32. Three metrics (DSP
utilization, memory utilization, and throughput) are measured for each
combination of parallel factor and tile size. Figure 10 shows the ablation
study results. Overall, as the parallel factor increases, all three metrics
increase as expected, showing promising _scalability_ of HIDA. Meanwhile, the
overall trend predictably showed more memory instances being utilized as we
increased the tile size. However, we also observed some interesting findings
summarized as follows:

  * •

_Small tile can drastically increase DSP utilization._ Counter-intuitively,
the number of DSPs increases when the tile size decreases, highlighted by the
data point with a parallel factor of 1 and a tile size of 2, instantiating 518
DSPs. Analysis shows that due to small tiles needing fine-grained control of
memory accesses, a large number of DSPs are used for address calculations
instead of actual computations.

  * •

_Smaller tile may not reduce memory utilization._ For small parallel factors
(1 to 8) and small tile sizes (2 to 8), the memory utilization does not change
noticeably within the range. Analysis shows that as the minimum memory
instance is BRAM (block RAM) for FPGAs, increasing parallel factor or tile
size may not demand more BRAM instances as long as the current BRAMs are large
enough to hold the data tiles and can provide enough bandwidth.

  * •

_Throughput and tile size may positively correlate._ Ideally, different tile
sizes should not affect the throughput. However, experimental results
disagree: throughput increases with tile size being larger, especially for
large parallel factors (32 to 256). Analysis shows two main reasons for the
observed behavior: (1) Small tile sizes cannot provide sufficient bandwidth,
resulting in a degradation of the level of parallelism.(2) Small tile sizes
cannot provide sufficient burst length for consecutive external memory access,
leading to poor external memory efficiency.

Figure 11. Intensity-aware (IA) and connection-aware (CA) dataflow
parallelization ablation on ResNet-18.

Node Parallelization Ablation. Section 6 introduces IA and CA approaches to
drive the dataflow parallelization. To better understand the performance of
the two methods on large-scale applications, we conduct an ablation study on
ResNet-18. In this study, we set four groups of experiments (IA+CA, IA-only,
CA-only, and Naive) for comparison, and for each group, we sweep the maximum
parallel factor from 1 to 256. As expected, the four groups show a similar
trend in DSP numbers - they increase proportionally with the parallel factor.
However, the IA+CA group shows a drastically different trend in memory and
throughput compared with the other groups - only IA+CA scales well when we
increase the parallel factor. For instance, for the data samples with a
parallel factor of 64, compared with the other groups, IA+CA utilizes
3.7$\times$ less DSP and 1.2$\times$ less memory, yet achieves 44.3$\times$
better throughput. After studying the generated accelerators, we found for all
the other groups except IC+CA, the compiler generates overly-complicated
control logics due to the mismatch between node unroll factors and memory
layouts, ultimately falling back to flawed designs. Meanwhile, even when all
groups can be scaled well, IA+CA shows substantially better resource
utilization efficiency than other groups. For instance, for the data samples
with a parallel factor of 32, compared with the other groups, IA+CA performs
on par in throughput but utilizes 4.5$\times$ less DSP and 4.7$\times$ less
memory. Through these comparisons, we demonstrate the superior scalability and
efficiency of our proposed IA+CA dataflow parallelization approach.

##  8\. Related Works

###  8.1. MLIR Infrastructure

MLIR (Lattner et al., 2021; Contributors, 2023g) is a compiler infrastructure
with multiple levels of representation, allowing users to tailor domain-
specific compilers. MLIR also provides commonly used IRs and optimizations for
different domains, including tensor (Contributors, 2023h), linear algebra
(Contributors, 2023f), and loop (Contributors, 2023e). As MLIR is an
infrastructure for compilers, it does not natively support hardware-oriented
compilation; however, many related compilers have been developed on top of
MLIR. IREE (Contributors, 2023d) provides compilation and runtime support for
hardware accelerators like GPU. CIRCT (Contributors, 2023c) is a toolchain for
circuit design and optimization, supporting HLS, HDL-generation languages
(Bachrach et al., 2012), and HDL.

###  8.2. HLS Languages

Different domain-specific languages (DSL) have been proposed to improve the
productivity and performance of commercial HLS tools. TAPA (Chi et al., 2021;
Guo et al., 2022) introduced specialized interfaces to enable dataflow and
efficient external memory access, but didn’t provide solution for dataflow
DSE. As a result, TAPA requires users to make many design decisions, such as
task parallelization and buffer implementation. Spatial (Koeplinger et al.,
2018) abstracted interfaces for describing the control, memory, and I/O
structures, enabling auto-tuning-based DSE. Dahlia (Nigam et al., 2020)
proposed an affine-based approach to improve the predictability of HLS
designs. Aetherling (Durst et al., 2020) proposed a strong type system to
tackle the fine-grained scheduling and DSE of hardware design. Another cluster
of works extends existing language syntax, such as Python, to further raise
the abstraction level of HLS designs, including DaCe (Ben-Nun et al., 2019)
and PyLog (Huang et al., 2021). These languages are orthogonal to HIDA, which
attempts to address the dataflow optimization problem with compiler
techniques. As future works, they can be integrated as front-ends to further
improve the productivity of HIDA.

HeteroCL. HeteroCL (Lai et al., 2019) and HeteroFlow (Xiang et al., 2022)
decoupled the algorithmic description and optimization of HLS designs by
providing a versatile set of computation, data type, and data movement
customization primitives. HeteroCL incorporated third-party frameworks for
automated HLS optimization, including PolySA (Cong and Wang, 2018) for
systolic arrays and SODA (Chi et al., 2018) for stencil applications. However,
these automated optimizations are intra-task and domain-specific. For inter-
task optimizations and computation patterns that are not covered by third-
party frameworks, designers must make every design decision empirically.
Meanwhile, HeteroCL cannot directly take PyTorch as an input - designers must
rewrite the PyTorch model in HeteroCL DSL.

###  8.3. HLS Compilers

Existing works have explored different approaches for the fine-grained
scheduling problem in HLS, including static scheduling (Spatial (Koeplinger et
al., 2018), SOFF (Jo et al., 2020), and Calyx (Nigam et al., 2021)), dynamic
scheduling (Dynamatic (Josipović et al., 2018) and TAPAS (Margerm et al.,
2018)), and static-dynamic hybrid scheduling (DASS (Cheng et al., 2020) and
Hector (Xu et al., 2022)). Fine-grained scheduling deals with operator-level
parallelism, such as multipliers, instead of task-level and thus is very
different from the problems we addressed in HIDA. For instance, fine-grained
scheduling does not consider the intra-task parallelization. We have seen a
large amount of HLS optimization tools, including LLVM-based (Merlin (Cong et
al., 2016), COMBA (Zhao et al., 2017), and HPVM2FPGA (Ejjeh et al., 2022)) and
MLIR-based (ScaleHLS (Ye et al., 2022a), POLSCA (Zhao et al., 2022), and SODA-
Opt (Agostini et al., 2022)). However, as discussed in Section 1, these tools
either did not consider dataflow during the compilation or are limited in
dataflow-oriented optimizations. Another alternative solution is leveraging
existing multi-core CPU or CGRA compilers, such as PolyMage (Mullapudi et al.,
2015), Tapir (Schardl et al., 2017), Unified Buffer (Liu et al., 2023), and
Revet (Rucker et al., 2023), for the purpose of HLS. However, the dataflow
optimizations are not compatible with these compilers due to the fundamentally
different programming model and memory hierarchy of HLS-based dataflow
accelerators.

CIRCT. Handshake dialect (Contributors, 2023b) is a CIRCT dialect implementing
the elastic circuit components and dynamic scheduling algorithms proposed in
Dynamatic (Josipović et al., 2018). Coarse-grained tasks are abstracted as
_function_ s in the handshake dialect, where scalar intermediate results are
passed between different functions through handshaking FIFOs. However, for
tensor intermediate results, the handshake dialect adopts a load-store queue-
based (Josipovic et al., 2017) shared memory model instead of the dataflow
model for inter-function communication, drawing a line between the two.
Elastic silicon interconnect (ESI) dialect (Contributors, 2023a) is another
CIRCT dialect aiming to provide type-safe and latency-insensitive interface
abstraction for FPGA/ASIC design. In contrast, HIDA aims to tackle the DSE
problem of fine-grained and coarse-grained scheduling, which is orthogonal to
the mission of the ESI dialect.

###  8.4. DNN Compilers

DNN layer fusion algorithms have been studied in recent years (Alwani et al.,
2016; Zhao et al., 2018) to reduce the layer-wise communication cost of DNN
training or inference. In contrast, HIDA’s task fusion is a general-purpose
algorithm for dataflow applications in different domains. The patterns
proposed by (Alwani et al., 2016; Zhao et al., 2018) can be implemented and
plugged into HIDA. The scheduling problem of cache-based or scratchpad-based
DNN accelerators has also been thoroughly studied, such as in Eyeriss (Chen et
al., 2016), Diannao (Chen et al., 2014), and Timeloop (Parashar et al., 2019),
either from an architecture or compiler perspective. However, the scheduling
of dataflow-based DNN accelerators is still under intensive study (Zhuang et
al., 2023; Rucker et al., 2023; Zhao et al., 2023). The intention to balance
the dataflow pipeline while enabling buffer sharing or streaming between layer
instances (either a single DNN layer, a fused layer, or a decomposed layer)
significantly complicates the scheduling problem. The reason is, as we
mentioned in Section 6.5, the local optimality of each layer cannot lead to
the global optimal dataflow architecture. Although existing works, such as
FINN (Umuroglu et al., 2017) and DNNBuilder (Zhang et al., 2018), explored the
problem to some extent, their framework can only target a subset of DNNs; for
instance, DNNBuilder only supports CNNs.

##  9\. Conclusion

In this paper, we propose HIDA, an HLS framework that can systematically
transform an algorithmic description into an efficient dataflow
implementation. We propose a two-level dataflow representation, HIDA-IR, and a
hierarchical dataflow optimizer, HIDA-OPT, significantly improving the
productivity, performance, and scalability of HLS dataflow accelerators. To
demonstrate the performance of HIDA, we evaluate a set of DNN models and C++
kernels, where HIDA outperforms the existing SOTA hand-tuned RTL-based DNN
accelerator and compilation-based HLS frameworks. We hope that the HIDA
framework will serve as a new open infrastructure for future dataflow
architectural research, allowing researchers to explore the vast design space
effectively.

###### Acknowledgements.

We thank all anonymous reviewers and Adrian Sampson of Cornell University for
their valuable feedback and suggestions. This work is supported in part by AMD
Center of Excellence at UIUC, AMD Heterogeneous Adaptive Compute Cluster
(HACC) initiative, NSF 2117997 grant through the A3D3 institute, and
Semiconductor Research Corporation (SRC) 2023-CT-3175 grant.

## References

  * (1)
  * Agostini et al. (2022) Nicolas Bohm Agostini, Serena Curzel, Vinay Amatya, Cheng Tan, Marco Minutoli, Vito Giovanni Castellana, Joseph Manzano, David Kaeli, and Antonino Tumeo. 2022.  An MLIR-based Compiler Flow for System-Level Design and Hardware Acceleration. In _Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design_. 1–9.
  * Alwani et al. (2016) Manoj Alwani, Han Chen, Michael Ferdman, and Peter Milder. 2016.  Fused-layer CNN accelerators. In _2016 49th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)_. IEEE, 1–12.
  * Bachrach et al. (2012) Jonathan Bachrach, Huy Vo, Brian Richards, Yunsup Lee, Andrew Waterman, Rimas Avižienis, John Wawrzynek, and Krste Asanović. 2012.  Chisel: constructing hardware in a scala embedded language. In _Proceedings of the 49th Annual Design Automation Conference_. 1216–1225.
  * Ben-Nun et al. (2019) Tal Ben-Nun, Johannes de Fine Licht, Alexandros N Ziogas, Timo Schneider, and Torsten Hoefler. 2019.  Stateful dataflow multigraphs: A data-centric model for performance portability on heterogeneous architectures. In _Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis_. 1–14.
  * Benabderrahmane et al. (2010) Mohamed-Walid Benabderrahmane, Louis-Noël Pouchet, Albert Cohen, and Cédric Bastoul. 2010.  The polyhedral model is more widely applicable than you think. In _Compiler Construction: 19th International Conference, CC 2010, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2010, Paphos, Cyprus, March 20-28, 2010. Proceedings 19_. Springer, 283–303.
  * Chen et al. (2014) Tianshi Chen, Zidong Du, Ninghui Sun, Jia Wang, Chengyong Wu, Yunji Chen, and Olivier Temam. 2014.  Diannao: A small-footprint high-throughput accelerator for ubiquitous machine-learning.  _ACM SIGARCH Computer Architecture News_ 42, 1 (2014), 269–284.
  * Chen et al. (2016) Yu-Hsin Chen, Tushar Krishna, Joel S Emer, and Vivienne Sze. 2016.  Eyeriss: An energy-efficient reconfigurable accelerator for deep convolutional neural networks.  _IEEE journal of solid-state circuits_ 52, 1 (2016), 127–138.
  * Cheng et al. (2020) Jianyi Cheng, Lana Josipovic, George A Constantinides, Paolo Ienne, and John Wickerson. 2020.  Combining dynamic & static scheduling in high-level synthesis. In _Proceedings of the 2020 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays_. 288–298.
  * Chi et al. (2018) Yuze Chi, Jason Cong, Peng Wei, and Peipei Zhou. 2018.  SODA: Stencil with optimized dataflow architecture. In _2018 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)_. IEEE, 1–8.
  * Chi et al. (2021) Yuze Chi, Licheng Guo, Jason Lau, Young-kyu Choi, Jie Wang, and Jason Cong. 2021.  Extending high-level synthesis for task-parallel programs. In _2021 IEEE 29th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)_. IEEE, 204–213.
  * Cong et al. (2016) Jason Cong, Muhuan Huang, Peichen Pan, Yuxin Wang, and Peng Zhang. 2016.  Source-to-source optimization for HLS.  _FPGAs for Software Programmers_ (2016), 137–163.
  * Cong et al. (2011) Jason Cong, Bin Liu, Stephen Neuendorffer, Juanjo Noguera, Kees Vissers, and Zhiru Zhang. 2011.  High-level synthesis for FPGAs: From prototyping to deployment.  _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ 30, 4 (2011), 473–491.
  * Cong and Wang (2018) Jason Cong and Jie Wang. 2018.  PolySA: Polyhedral-based systolic array auto-compilation. In _2018 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)_. IEEE, 1–8.
  * Contributors (2023a) CIRCT Contributors. 2023a.  _CIRCT ESI Dialect_.  https://circt.llvm.org/docs/Dialects/ESI/
  * Contributors (2023b) CIRCT Contributors. 2023b.  _CIRCT Handshake Dialect_.  https://circt.llvm.org/docs/Dialects/Handshake/
  * Contributors (2023c) CIRCT Contributors. 2023c.  _The CIRCT Project_.  https://github.com/llvm/circt
  * Contributors (2023d) IREE Contributors. 2023d.  _The IREE Project_.  https://github.com/openxla/iree
  * Contributors (2023e) MLIR Contributors. 2023e.  _MLIR Affine Dialect_.  https://mlir.llvm.org/docs/Dialects/Affine/
  * Contributors (2023f) MLIR Contributors. 2023f.  _MLIR LinAlg Dialect_.  https://mlir.llvm.org/docs/Dialects/Linalg/
  * Contributors (2023g) MLIR Contributors. 2023g.  _MLIR Project_.  https://github.com/llvm/llvm-project/tree/main/mlir
  * Contributors (2023h) MLIR Contributors. 2023h.  _MLIR Tensor Dialect_.  https://mlir.llvm.org/docs/Dialects/TensorOps/
  * Contributors (2023i) Torch-MLIR Contributors. 2023i.  _Torch-MLIR Project_.  https://github.com/llvm/torch-mlir/
  * Cytron et al. (1991) Ron Cytron, Jeanne Ferrante, Barry K Rosen, Mark N Wegman, and F Kenneth Zadeck. 1991.  Efficiently computing static single assignment form and the control dependence graph.  _ACM Transactions on Programming Languages and Systems (TOPLAS)_ 13, 4 (1991), 451–490.
  * Du et al. (2015) Zidong Du, Robert Fasthuber, Tianshi Chen, Paolo Ienne, Ling Li, Tao Luo, Xiaobing Feng, Yunji Chen, and Olivier Temam. 2015.  ShiDianNao: Shifting vision processing closer to the sensor. In _Proceedings of the 42nd Annual International Symposium on Computer Architecture_. 92–104.
  * Durst et al. (2020) David Durst, Matthew Feldman, Dillon Huff, David Akeley, Ross Daly, Gilbert Louis Bernstein, Marco Patrignani, Kayvon Fatahalian, and Pat Hanrahan. 2020.  Type-directed scheduling of streaming accelerators. In _Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation_. 408–422.
  * Ejjeh et al. (2022) Adel Ejjeh, Leon Medvinsky, Aaron Councilman, Hemang Nehra, Suraj Sharma, Vikram Adve, Luigi Nardi, Eriko Nurvitadhi, and Rob A Rutenbar. 2022.  HPVM2FPGA: Enabling true hardware-agnostic FPGA programming. In _2022 IEEE 33rd International Conference on Application-specific Systems, Architectures and Processors (ASAP)_. IEEE, 1–10.
  * Fahim et al. (2021) Farah Fahim, Benjamin Hawks, Christian Herwig, James Hirschauer, Sergo Jindariani, Nhan Tran, Luca P Carloni, Giuseppe Di Guglielmo, Philip Harris, Jeffrey Krupa, et al. 2021\.  hls4ml: An open-source codesign workflow to empower scientific low-power machine learning devices.  _arXiv preprint arXiv:2103.05579_ (2021).
  * Genc et al. (2021) Hasan Genc, Seah Kim, Alon Amid, Ameer Haj-Ali, Vighnesh Iyer, Pranav Prakash, Jerry Zhao, Daniel Grubb, Harrison Liew, Howard Mao, et al. 2021\.  Gemmini: Enabling systematic deep-learning architecture evaluation via full-stack integration. In _2021 58th ACM/IEEE Design Automation Conference (DAC)_. IEEE, 769–774.
  * Guo et al. (2022) Licheng Guo, Yuze Chi, Jason Lau, Linghao Song, Xingyu Tian, Moazin Khatti, Weikang Qiao, Jie Wang, Ecenur Ustun, Zhenman Fang, et al. 2022\.  TAPA: A Scalable Task-Parallel Dataflow Programming Framework for Modern FPGAs with Co-Optimization of HLS and Physical Design.  _arXiv preprint arXiv:2209.02663_ (2022).
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016.  Deep residual learning for image recognition. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 770–778.
  * Howard et al. (2017) Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. 2017.  Mobilenets: Efficient convolutional neural networks for mobile vision applications.  _arXiv preprint arXiv:1704.04861_ (2017).
  * Huang et al. (2021) Sitao Huang, Kun Wu, Hyunmin Jeong, Chengyue Wang, Deming Chen, and Wen-mei Hwu. 2021.  Pylog: An algorithm-centric python-based FPGA programming and synthesis flow.  _IEEE Trans. Comput._ 70, 12 (2021), 2015–2028.
  * Ikarashi et al. (2022) Yuka Ikarashi, Gilbert Louis Bernstein, Alex Reinking, Hasan Genc, and Jonathan Ragan-Kelley. 2022.  Exocompilation for productive programming of hardware accelerators. In _Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation_. 703–718.
  * Inc (2022a) Advanced Micro Devices Inc. 2022a.  _Vitis High-Level Synthesis User Guide UG1399 (v2022.2)_.
  * Inc (2022b) Intel Inc. 2022b.  _Intel High Level Synthesis Compiler Pro Edition Reference Manual (22.4)_.
  * Inc (2021) Microchip Technology Inc. 2021.  _LegUp 2021.1 Documentation_.
  * Jo et al. (2020) Gangwon Jo, Heehoon Kim, Jeesoo Lee, and Jaejin Lee. 2020.  SOFF: An OpenCL high-level synthesis framework for FPGAs. In _2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA)_. IEEE, 295–308.
  * Josipovic et al. (2017) Lana Josipovic, Philip Brisk, and Paolo Ienne. 2017.  An out-of-order load-store queue for spatial computing.  _ACM Transactions on Embedded Computing Systems (TECS)_ 16, 5s (2017), 1–19.
  * Josipović et al. (2018) Lana Josipović, Radhika Ghosal, and Paolo Ienne. 2018.  Dynamically scheduled high-level synthesis. In _Proceedings of the 2018 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays_. 127–136.
  * Jouppi et al. (2017) Norman P Jouppi, Cliff Young, Nishant Patil, David Patterson, Gaurav Agrawal, Raminder Bajwa, Sarah Bates, Suresh Bhatia, Nan Boden, Al Borchers, et al. 2017\.  In-datacenter performance analysis of a tensor processing unit. In _Proceedings of the 44th annual international symposium on computer architecture_. 1–12.
  * Jun et al. (2023) HyeGang Jun, Hanchen Ye, Hyunmin Jeong, and Deming Chen. 2023.  AutoScaleDSE: A Scalable Design Space Exploration Engine for High-Level Synthesis.  _ACM Trans. Reconfigurable Technol. Syst._ (2023).
  * Koeplinger et al. (2018) David Koeplinger, Matthew Feldman, Raghu Prabhakar, Yaqi Zhang, Stefan Hadjis, Ruben Fiszel, Tian Zhao, Luigi Nardi, Ardavan Pedram, Christos Kozyrakis, et al. 2018\.  Spatial: A language and compiler for application accelerators. In _Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation_. 296–311.
  * Lai et al. (2019) Yi-Hsiang Lai, Yuze Chi, Yuwei Hu, Jie Wang, Cody Hao Yu, Yuan Zhou, Jason Cong, and Zhiru Zhang. 2019.  HeteroCL: A multi-paradigm programming infrastructure for software-defined reconfigurable computing. In _Proceedings of the 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays_. 242–251.
  * Lattner and Adve (2004) Chris Lattner and Vikram Adve. 2004.  LLVM: A compilation framework for lifelong program analysis & transformation. In _International symposium on code generation and optimization, 2004. CGO 2004._ IEEE, 75–86.
  * Lattner et al. (2021) Chris Lattner, Mehdi Amini, Uday Bondhugula, Albert Cohen, Andy Davis, Jacques Pienaar, River Riddle, Tatiana Shpeisman, Nicolas Vasilache, and Oleksandr Zinenko. 2021.  MLIR: Scaling compiler infrastructure for domain specific computation. In _2021 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)_. IEEE, 2–14.
  * Lattner et al. (2020) Chris Lattner, Jacques Pienaar, Mehdi Amini, Uday Bondhugula, River Riddle, Albert Cohen, Tatiana Shpeisman, Andy Davis, Nicolas Vasilache, and Oleksandr Zinenko. 2020.  MLIR: A Compiler Infrastructure for the End of Moore’s Law.  _arXiv preprint arXiv:2002.11054_ (2020).
  * LeCun et al. (1998) Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. 1998.  Gradient-based learning applied to document recognition.  _Proc. IEEE_ 86, 11 (1998), 2278–2324.
  * Liu et al. (2023) Qiaoyi Liu, Jeff Setter, Dillon Huff, Maxwell Strange, Kathleen Feng, Mark Horowitz, Priyanka Raina, and Fredrik Kjolstad. 2023.  Unified Buffer: Compiling Image Processing and Machine Learning Applications to Push-Memory Accelerators.  _ACM Transactions on Architecture and Code Optimization_ 20, 2 (2023), 1–26.
  * Margerm et al. (2018) Steven Margerm, Amirali Sharifian, Apala Guha, Arrvindh Shriraman, and Gilles Pokam. 2018.  TAPAS: Generating parallel accelerators from parallel programs. In _2018 51st Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)_. IEEE, 245–257.
  * Moreau et al. (2018) Thierry Moreau, Tianqi Chen, Ziheng Jiang, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. 2018.  VTA: an open hardware-software stack for deep learning.  _arXiv preprint arXiv:1807.04188_ (2018).
  * Moses et al. (2021) William S Moses, Lorenzo Chelini, Ruizhe Zhao, and Oleksandr Zinenko. 2021.  Polygeist: Raising C to polyhedral MLIR. In _2021 30th International Conference on Parallel Architectures and Compilation Techniques (PACT)_. IEEE, 45–59.
  * Mullapudi et al. (2015) Ravi Teja Mullapudi, Vinay Vasista, and Uday Bondhugula. 2015.  Polymage: Automatic optimization for image processing pipelines.  _ACM SIGARCH Computer Architecture News_ 43, 1 (2015), 429–443.
  * Nardi et al. (2019) Luigi Nardi, David Koeplinger, and Kunle Olukotun. 2019.  Practical design space exploration. In _2019 IEEE 27th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS)_. IEEE, 347–358.
  * Nigam et al. (2020) Rachit Nigam, Sachille Atapattu, Samuel Thomas, Zhijing Li, Theodore Bauer, Yuwei Ye, Apurva Koti, Adrian Sampson, and Zhiru Zhang. 2020.  Predictable accelerator design with time-sensitive affine types. In _Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation_. 393–407.
  * Nigam et al. (2021) Rachit Nigam, Samuel Thomas, Zhijing Li, and Adrian Sampson. 2021.  A compiler infrastructure for accelerator generators. In _Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems_. 804–817.
  * Parashar et al. (2019) Angshuman Parashar, Priyanka Raina, Yakun Sophia Shao, Yu-Hsin Chen, Victor A Ying, Anurag Mukkara, Rangharajan Venkatesan, Brucek Khailany, Stephen W Keckler, and Joel Emer. 2019.  Timeloop: A systematic approach to dnn accelerator evaluation. In _2019 IEEE international symposium on performance analysis of systems and software (ISPASS)_. IEEE, 304–315.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019\.  Pytorch: An imperative style, high-performance deep learning library.  _Advances in neural information processing systems_ 32 (2019).
  * Pouchet et al. (2012) Louis-Noël Pouchet et al. 2012\.  Polybench: The polyhedral benchmark suite.  _URL: http://www. cs. ucla. edu/pouchet/software/polybench_ 437 (2012), 1–1.
  * Prabhakar et al. (2017) Raghu Prabhakar, Yaqi Zhang, David Koeplinger, Matt Feldman, Tian Zhao, Stefan Hadjis, Ardavan Pedram, Christos Kozyrakis, and Kunle Olukotun. 2017.  Plasticine: A reconfigurable architecture for parallel paterns.  _ACM SIGARCH Computer Architecture News_ 45, 2 (2017), 389–402.
  * Redmon et al. (2016) Joseph Redmon, Santosh Divvala, Ross Girshick, and Ali Farhadi. 2016.  You only look once: Unified, real-time object detection. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 779–788.
  * Rucker et al. (2023) Alexander Rucker, Shiv Sundram, Coleman Smith, Matthew Vilim, Raghu Prabhakar, Fredrik Kjolstad, and Kunle Olukotun. 2023.  Revet: A Language and Compiler for Dataflow Threads.  _arXiv preprint arXiv:2302.06124_ (2023).
  * Schardl et al. (2017) Tao B Schardl, William S Moses, and Charles E Leiserson. 2017.  Tapir: Embedding fork-join parallelism into LLVM’s intermediate representation. In _Proceedings of the 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming_. 249–265.
  * Simonyan and Zisserman (2014) Karen Simonyan and Andrew Zisserman. 2014.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_ (2014).
  * Sohrabizadeh et al. (2022) Atefeh Sohrabizadeh, Cody Hao Yu, Min Gao, and Jason Cong. 2022.  AutoDSE: Enabling software programmers to design efficient FPGA accelerators.  _ACM Transactions on Design Automation of Electronic Systems (TODAES)_ 27, 4 (2022), 1–27.
  * Umuroglu et al. (2017) Yaman Umuroglu, Nicholas J Fraser, Giulio Gambardella, Michaela Blott, Philip Leong, Magnus Jahre, and Kees Vissers. 2017.  Finn: A framework for fast, scalable binarized neural network inference. In _Proceedings of the 2017 ACM/SIGDA international symposium on field-programmable gate arrays_. 65–74.
  * Wang et al. (2013) Yuxin Wang, Peng Li, Peng Zhang, Chen Zhang, and Jason Cong. 2013.  Memory partitioning for multidimensional arrays in high-level synthesis. In _Proceedings of the 50th Annual Design Automation Conference_. 1–8.
  * Wei et al. (2018) Xuechao Wei, Yun Liang, Xiuhong Li, Cody Hao Yu, Peng Zhang, and Jason Cong. 2018.  TGPA: Tile-grained pipeline architecture for low latency CNN inference. In _2018 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)_. ACM, 1–8.
  * Xiang et al. (2022) Shaojie Xiang, Yi-Hsiang Lai, Yuan Zhou, Hongzheng Chen, Niansong Zhang, Debjit Pal, and Zhiru Zhang. 2022.  Heteroflow: An accelerator programming model with decoupled data placement for software-defined fpgas. In _Proceedings of the 2022 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays_. 78–88.
  * Xu et al. (2022) Ruifan Xu, Youwei Xiao, Jin Luo, and Yun Liang. 2022.  HECTOR: A Multi-Level Intermediate Representation for Hardware Synthesis Methodologies. In _Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design_. 1–9.
  * Ye et al. (2022a) Hanchen Ye, Cong Hao, Jianyi Cheng, Hyunmin Jeong, Jack Huang, Stephen Neuendorffer, and Deming Chen. 2022a.  Scalehls: A new scalable high-level synthesis framework on multi-level intermediate representation. In _2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA)_. IEEE, 741–755.
  * Ye et al. (2022b) Hanchen Ye, HyeGang Jun, Hyunmin Jeong, Stephen Neuendorffer, and Deming Chen. 2022b.  ScaleHLS: a scalable high-level synthesis framework with multi-level transformations and optimizations. In _Proceedings of the 59th ACM/IEEE Design Automation Conference_. 1355–1358.
  * Ye et al. (2020) Hanchen Ye, Xiaofan Zhang, Zhize Huang, Gengsheng Chen, and Deming Chen. 2020.  HybridDNN: A framework for high-performance hybrid DNN accelerator design and implementation. In _2020 57th ACM/IEEE Design Automation Conference (DAC)_. IEEE, 1–6.
  * Yu et al. (2021) Mang Yu, Sitao Huang, and Deming Chen. 2021.  Chimera: A hybrid machine learning-driven multi-objective design space exploration tool for fpga high-level synthesis. In _Intelligent Data Engineering and Automated Learning–IDEAL 2021: 22nd International Conference, IDEAL 2021, Manchester, UK, November 25–27, 2021, Proceedings 22_. Springer, 524–536.
  * Zeiler and Fergus (2014) Matthew D Zeiler and Rob Fergus. 2014.  Visualizing and understanding convolutional networks. In _Computer Vision–ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part I 13_. Springer, 818–833.
  * Zhang et al. (2021) Bingyi Zhang, Rajgopal Kannan, and Viktor Prasanna. 2021.  Boostgcn: A framework for optimizing gcn inference on fpga. In _2021 IEEE 29th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)_. IEEE, 29–39.
  * Zhang et al. (2015) Chen Zhang, Peng Li, Guangyu Sun, Yijin Guan, Bingjun Xiao, and Jason Cong. 2015.  Optimizing FPGA-based accelerator design for deep convolutional neural networks. In _Proceedings of the 2015 ACM/SIGDA international symposium on field-programmable gate arrays_. 161–170.
  * Zhang et al. (2018) Xiaofan Zhang, Junsong Wang, Chao Zhu, Yonghua Lin, Jinjun Xiong, Wen-mei Hwu, and Deming Chen. 2018.  DNNBuilder: An automated tool for building high-performance DNN hardware accelerators for FPGAs. In _2018 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)_. ACM, 1–8.
  * Zhang et al. (2020) Xiaofan Zhang, Hanchen Ye, Junsong Wang, Yonghua Lin, Jinjun Xiong, Wen-mei Hwu, and Deming Chen. 2020.  DNNExplorer: a framework for modeling and exploring a novel paradigm of FPGA-based DNN accelerator. In _Proceedings of the 39th International Conference on Computer-Aided Design_. 1–9.
  * Zhao et al. (2017) Jieru Zhao, Liang Feng, Sharad Sinha, Wei Zhang, Yun Liang, and Bingsheng He. 2017.  COMBA: A comprehensive model-based analysis framework for high level synthesis of real applications. In _2017 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)_. IEEE, 430–437.
  * Zhao et al. (2022) Ruizhe Zhao, Jianyi Cheng, Wayne Luk, and George A Constantinides. 2022.  POLSCA: Polyhedral High-Level Synthesis with Compiler Transformations. In _32nd International Conference on Field Programmable Logic and Applications (FPL’22)_.
  * Zhao et al. (2023) Tian Zhao, Alexander Rucker, and Kunle Olukotun. 2023.  Sigma: Compiling Einstein Summations to Locality-Aware Dataflow. In _Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2_. 718–732.
  * Zhao et al. (2018) Zhuoran Zhao, Kamyar Mirzazad Barijough, and Andreas Gerstlauer. 2018.  Deepthings: Distributed adaptive deep learning inference on resource-constrained iot edge clusters.  _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ 37, 11 (2018), 2348–2359.
  * Zhong et al. (2016) Guanwen Zhong, Alok Prakash, Yun Liang, Tulika Mitra, and Smail Niar. 2016.  Lin-analyzer: A high-level performance analysis tool for FPGA-based accelerators. In _Proceedings of the 53rd Annual Design Automation Conference_. 1–6.
  * Zhou et al. (2021) Peipei Zhou, Jiayi Sheng, Cody Hao Yu, Peng Wei, Jie Wang, Di Wu, and Jason Cong. 2021.  Mocha: Multinode cost optimization in heterogeneous clouds with accelerators. In _The 2021 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays_. 273–279.
  * Zhuang et al. (2023) Jinming Zhuang, Jason Lau, Hanchen Ye, Zhuoping Yang, Yubo Du, Jack Lo, Kristof Denolf, Stephen Neuendorffer, Alex Jones, Jingtong Hu, et al. 2023\.  CHARM: Composing Heterogeneous AcceleRators for Matrix Multiply on Versal ACAP Architecture.  _arXiv preprint arXiv:2301.02359_ (2023).
  * Zuo et al. (2015) Wei Zuo, Warren Kemmerer, Jong Bin Lim, Louis-Noël Pouchet, Andrey Ayupov, Taemin Kim, Kyungtae Han, and Deming Chen. 2015.  A polyhedral-based systemc modeling and generation framework for effective low-power design space exploration. In _2015 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)_. IEEE, 357–364.
  * Zuo et al. (2017) Wei Zuo, Louis-Noel Pouchet, Andrey Ayupov, Taemin Kim, Chung-Wei Lin, Shinichi Shiraishi, and Deming Chen. 2017.  Accurate high-level modeling and automated hardware/software co-design for effective SoC design space exploration. In _Proceedings of the 54th Annual Design Automation Conference 2017_. 1–6.