# DPU-v2: Energy-efficient execution of irregular directed acyclic graphs

Nimish Shah1, Wannes Meert2 and Marian Verhelst1  1Department of Electrical
Engineering - MICAS, KU Leuven, Belgium  2 Department of Computer Science -
DTAI, KU Leuven, Belgium
Emails<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

A growing number of applications like probabilistic machine learning, sparse
linear algebra, robotic navigation, etc., exhibit irregular data flow
computation that can be modeled with directed acyclic graphs (DAGs). The
irregularity arises from the seemingly random connections of nodes, which
makes the DAG structure unsuitable for vectorization on CPU or GPU. Moreover,
the nodes usually represent a small number of arithmetic operations that
cannot amortize the overhead of launching tasks/kernels for each node, further
posing challenges for parallel execution.

To enable energy-efficient execution, this work proposes DAG processing unit
(DPU) version 2, a specialized processor architecture optimized for irregular
DAGs with static connectivity. It consists of a tree-structured datapath for
efficient data reuse, a customized banked register file, and interconnects
tuned to support irregular register accesses. DPU-v2 is utilized effectively
through a targeted compiler that systematically maps operations to the
datapath, minimizes register bank conflicts, and avoids pipeline hazards.
Finally, a design space exploration identifies the optimal architecture
configuration that minimizes the energy-delay product. This hardware-software
co-optimization approach results in a speedup of 1.4$\times$, 3.5$\times$, and
14$\times$ over a state-of-the-art DAG processor ASIP, a CPU, and a GPU,
respectively, while also achieving a lower energy-delay product. In this way,
this work takes an important step towards enabling an embedded execution of
emerging DAG workloads.

###### Index Terms:

Graphs, irregular computation graphs, parallel processor, hardware-software
codesign, DAG processing unit, probabilistic circuits, sparse matrix
triangular solve, spatial datapath, interconnection network, bank conflicts,
design space exploration

##  I Introduction

Emerging machine learning models like probabilistic circuits (PC, also called
sum-product networks) [4, 41] are increasingly used for energy-constrained
applications like robotic navigation [59], robust image classification [49],
human activity recognition [17], etc. PCs exhibit an irregular flow of data
that can be represented with directed acyclic graphs (DAG), as shown in fig.
1(a) for a human activity recognition model. Similarly, sparse linear algebra
operations like sparse triangular solve (SpTRSV) used for embedded
applications like robotic localization and mapping [40], wireless
communication [54], cryptography [15], etc., can also be represented with
irregular DAGs. Fig. 1(b) shows an example of a DAG for a matrix from the
SuiteSparse collection [13]. In these DAGs, nodes represent arithmetic
operations and edges represent the dependencies among these operations.

Figure 1: Example applications with irregular computation DAGs. (a)
Probabilistic circuits (PC) used in machine learning, and (b) Sparse matrix
triangular solves (SpTRSV) used in linear algebra. (c) CPU and GPU achieve
significantly lower than their peak throughput for such DAGs.

Unfortunately, these irregular unstructured DAGs pose challenges to general-
purpose computing architectures like GPUs and single-instruction-multiple-data
(SIMD) vectorization in CPUs. Fig. 1(c) shows the throughputs of an Intel Xeon
CPU and an Nvidia RTX GPU for these applications.The CPU performs much below
the peak achievable throughput (3.4 TOPS in this case), and the GPU even
underperforms compared to the CPU despite having highly parallel hardware
(especially for DAGs with fewer than 100K nodes). This underperformance is
caused by the following two reasons, preventing the platforms from utilizing
the sparsity in the workloads:

  * •

The seemingly-random edge connectivity of an unstructured DAG results in
irregular memory accesses with poor spatial locality. Hence, the large
granularity of cache-line size leads to severe under-utilization of caches and
memory bandwidth, because only 4B might get consumed out of the 32/64B of data
fetched to a cache line. Furthermore, these irregular accesses also prevent
memory coalescing, which is crucial for high GPU performance [52].

  * •

Due to the irregular structure, parallelizing different parts of DAGs across
multiple units (like CPU cores, GPU streaming multiprocessors, etc.) demands
high communication and synchronization overhead, limiting the parallelization
benefits [44].

To address these issues, this paper proposes DAG processing unit (DPU-v2), a
processing architecture111Available at
https://github.com/nimish15shah/DAG_Processor. optimised for irregular DAGs
along with a custom-designed targeted compiler. The major contributions of
this work are as follows:

  1. 1.

Processor: A parameterized architecture template is designed with a tree-
structured datapath for immediate reuse of data, a banked register file with a
novel addressing scheme, and high-bandwidth flexible interconnects. The
architecture is made programmable with a custom instruction set with long
words.

  2. 2.

Compiler: A specialized compiler is designed that schedules DAG nodes such
that the tree-based datapath is maximally utilized. The irregularity of DAGs
leads to frequent register bank conflicts, which are reduced with a conflict-
aware register allocation while taking into account the interconnect
constraints.

  3. 3.

Design-space exploration: Since there are multiple design parameters in the
architecture template (e.g. the number of register banks, computational
parallelism, etc.), a design space exploration is performed to arrive at the
architecture with the minimum energy-delay product in a 28nm CMOS technology,
and compared with state-of-the-art implementations.

This work focuses on DAGs that remain static across multiple executions, which
allow amortization of the compilation overhead, enabling highly targeted (but
relatively slow) DAG-specific compilation. This assumption of DAGs being
static is valid for our target workloads: (1) the structure of a trained PC
remains static during inference, and (2) in many applications using SpTRSV
like robotic localization and mapping [40], wireless communication [54],
cryptography [15], etc., the sparsity pattern of a matrix remains static while
the numerical values or the right-hand side vector change across executions,
which effectively only changes the inputs of the DAG. Furthermore, DAGs are
assumed to contain only arithmetic nodes (and no conditional nodes) that are
executed in a predefined order based on edge-induced dependencies. This
assumption is also valid for the target workloads in this paper, but excludes
operations like breadth-first search (even on a static DAG) from the scope of
this work.

The paper is organized as follows. §II discusses this work’s approach for
efficient parallel execution of DAGs. §III describes the processor
architecture template of DPU-v2 followed by §IV explaining the compiler. Next,
§V presents the design-space exploration to find the design with the minimum
energy-delay product, and compares it with state-of-the-art work. Finally, §VI
discusses related works and §VII concludes the paper.

##  II Concepts to tame irregularity

In this paper, a DAG encodes the computations to be performed for an
application and its data dependencies. A DAG node represents arithmetic
operations (e.g. additions, multiplications) to be performed on the node’s
inputs. This work focuses on DAGs with fine-grained nodes with low arithmetic
intensity. In other words, the nodes represent a scalar or a small-sized
vector operation but not large tensor operations, in contrast to DAGs of deep
neural networks, for example, which have compute-intensive tensor operations
as nodes. The output result of a node serves as an input to (possibly
multiple) nodes connected to the outgoing edges.

Figure 2: (a) A common approach for executing DAGs in parallel, in which the
unpredictable irregular accesses happen to scratchpad/memory. (b) In DPU-v2 by
pushing the interconnect closer to the datapath, the compiler is equipped to
predict the irregular accesses and prevent bank conflicts.

Execution order: Executing a DAG means evaluating all the nodes in a valid
order imposed by the directed edges representing data dependencies. For all
the edges, the source node should be executed before the destination node. Put
differently, a node can be executed only after all the predecessor nodes have
finished execution. Note that the DAGs targeted in this work do not contain
conditional branch nodes, and hence all the nodes are supposed to be executed.

What can be executed in parallel? At a given moment, all the nodes whose
predecessor nodes have finished execution can be executed in parallel. The
execution begins with the source nodes of the DAG, as they do not have any
incoming edges. Subsequently, different nodes become ready as the execution
progresses. DAGs from real-world applications typically have ample
parallelism, which can be utilized through a parallel processing architecture.

The rest of this section discusses the challenges for parallel processing of
irregular DAGs and the techniques introduced in this work to address them.

###  II-A Making irregular data accesses predictable

Fig. 2(a) shows a common approach for accelerating DAGs, in which a DAG is
partitioned into smaller subgraphs that can be executed on parallel cores,
e.g, in a multicore CPU. This approach is used in works like [39], [44], [46].
The cores have to synchronize occasionally for race-free communication that
happens through a shared memory structure like an L3 cache in CPUs or a shared
scratchpad in [46]. Due to the DAG irregularity, the accesses to this shared
memory structure usually happen to random addresses, inducing frequent bank
conflicts in the typically-used banked memory structures. These conflicts
could become a severe bottleneck. For instance, in [46], 43% of the load
requests result in bank conflicts. Work in [11], [43] alleviates the impact of
these conflicts through aggressive reordering of requests, but incurs the
overhead of a reordering buffer. Yet, none of these works attempt to avoid the
conflicts altogether. Given that the DAG structure is known at compile time,
it could be possible to perform the memory allocation such that the
simultaneous requests do not access the same bank. The main challenge for such
conflict avoidance is that it is not straightforward to predict which requests
happen simultaneously. The parallel cores normally execute asynchronously,
i.e. a stall in one core (eg., to wait for the next instruction) does not
stall the others, preventing a compiler from predicting conflicts.

Fig. 2(b) shows an alternative approach that makes the simultaneous irregular
accesses predictable by pushing the interconnect closer to the datapath and
forcing the PE to operate in a synchronous way. This limits the irregular
accesses to the register file, while the memory/scratchpad can be accessed in
a regular pattern. In every cycle, the compiler knows which registers are
accessed and can thereby also predict register bank conflicts. The datapath
with parallel PEs, however, cannot be programmed with SIMD-like instructions
because the PEs will gather data from different addresses in the register
banks owing to DAG irregularity. Instead, VLIW (very long instruction
word)-like instructions can be used. Yet, unlike conventional VLIW with a
partitioned register file [2], the datapath does not have to be limited to an
array of PEs, but complex dataflow patterns can be utilized.

This work hypothesizes that the architecture in fig. 2(b) can improve
throughput by avoiding bank conflicts and by using a datapath tuned for the
target workloads.

###  II-B Reducing data accesses

To ease the problem of bank conflicts further and to reduce energy
consumption, the intermediate results in the computation could be immediately
consumed in the datapath, avoiding reads/writes from a register file. A
commonly used topology for such data reuse is a systolic array of PEs [27]
(fig. 3(a)), yet it is unsuitable for sparse DAGs due to severe hardware
under-utilization as described below.

Peak utilization: To check the suitability of the systolic array, the spatial
datapath mapper from [34] is used to find the largest subgraph in our target
DAGs (described in §V-A) that can be mapped to the array. This essentially is
the peak utilization possible for the datapath. Fig. 3(c) shows that the peak
utilization of the systolic array drops rapidly with the increasing number of
inputs, and even a 4$\times$4 array with 8 inputs cannot be properly utilized.

Tree of PEs: The tree-structured datapath (fig. 3(b)) is a promising
alternative candidate, as multi-input DAG nodes can be spatially unrolled as
binary trees. As shown in fig. 3(c), the spatial mapper confirms that there
exist subgraphs in DAGs that can fully utilize the datapath.

The spatial mapper used here can quantify the peak utilization, but the
constrained-optimization-based approach used in the mapper is too slow to
fully map large DAGs with tens of thousands of nodes. For a scalable solution,
this work presents a heuristic algorithm to decompose irregular DAGs into
tree-like subgraphs (§IV-A).

Figure 3: Systolic arrays are under-utilized by irregular DAGs, while a tree-
shaped datapath is a promising alternative.

###  II-C Supporting irregular data accesses

Section §II-A alluded that DAG irregularity causes irregular register
accesses. Fig. 4 illustrates this with a concrete example. Fig. 4(a) shows a
sample DAG and a target datapath consisting of a PE tree and a banked register
file for inputs/outputs. Fig. 4(b) shows an example decomposition of the DAG
in tree-shaped structures that can be sequentially mapped to the datapath. The
outputs of some of the nodes (like node $a$) are required to be stored in the
register file for later consumption, while others (like node $d$) are fully
consumed within the datapath. Fig. 4(c) shows the temporal execution with the
evolving state of the register file. The DAG irregularity manifests in the
form of irregular accesses to register banks as explained next.

Figure 4: Example of a DAG execution on a tree of PEs, causing irregular
register accesses.  Figure 5: (a) DPU-v2 architecture template consists of
processing elements (PE) connected in a tree topology. The trees are connected
to parallel register banks with input and output interconnects. The datapath
is pipelined according to the number of PE layers. (b) Vectors are
loaded/stored from a single address in the data memory, but register banks are
addressed independently. (c) To avoid conflicts, the data are copied between
banks via the input interconnect. (d) Write address generation by tracking the
occupancy status with valid bits.

Irregular bank accesses: The inputs and outputs of the PE tree access
different banks over the cycles. For example, PE2 reads banks 2 and 3 at T0
and banks 1 and 3 at T1. The access pattern cannot be regularized by simply
remapping the variables to different banks or remapping nodes to different
PEs. Consider the input variables of node $b$, which are also consumed by $c$
and $d$. At T0, they are consumed by one PE, while at T1, by two PEs, one
each. It is not possible to map the variables among banks such that the PEs
read the same banks at T0 and T1 both. One alternative could be to execute the
nodes $c$ and $d$ in different cycles, but that would lead to idle PEs. Hence,
for high PE utilization, some form of flexibility is required in
interconnecting the inputs/outputs of PE trees to the register banks.

Irregular addresses: PEs read different addresses from different banks in a
cycle. This is caused by the fact that the input variables consumed
simultaneously can possibly be generated in different cycles. (eg., the inputs
of T3). Similarly, variables that are generated together can be consumed in
different cycles (eg., the outputs of T1). Thus, unlike SIMD execution, all
the register banks do not use the same read/write addresses, requiring
flexible addressing hardware.

Replication is not a solution: It may appear that replicating a variable in
multiple banks and multiple addresses can solve both of the above problems for
register reads. For such replications, a variable would be written as well as
read multiple times. However, there are three problems:

  * •

The register file can be severely underutilized due to replicated copies of
the same data.

  * •

The energy consumption increases due to more writes compared to fig. 4’s
approach of single writes.

  * •

The replication alleviates the irregular reads but exacerbates the
irregularity of writes. Hence, it simply shifts the problem from reads to
writes.

Hence, this work aims to use flexible interconnects and independent register
addresses to ease the gathering of data from irregular locations without
relying on data replication, enabling high-throughput execution.

##  III DPU-v2 Architecture template

This section describes the proposed processor architecture template (fig.
5(a)) designed for unstructured DAGs.

###  III-A Parallel tree of PEs

As shown in fig. 5(a), the datapath consists of many parallel processing
elements (PEs) to execute the DAG nodes.

  * •

PE: Each PE can be configured to perform a basic arithmetic operation ($+$ and
$\times$). Additionally, a PE can bypass one of its inputs to its output.

  * •

Trees of PEs: PEs are interconnected in $\mathit{T}$ parallel structures with
a tree topology containing 0pt layers, where outputs of a PE layer are
connected to the inputs of the next PE layer. This enables immediate reuse of
intermediate results, avoiding register file accesses and the associated
energy consumption.

  * •

Pipeline stages: The PE outputs are registered, resulting in 0pt pipeline
stages in the trees.

###  III-B Shared register file

The PE trees read and write data from a shared register file containing
$\mathit{B}$ parallel banks with $\mathit{R}$ registers per bank (fig. 5(a)).
The number of banks $\mathit{B}$ is chosen such that there is one register
bank for each input of the trees (i.e.,
$\mathit{B}{}=\mathit{T}{}\times\mathrm{2}^{\mathit{D}{}}$). As such, the
register file has enough bandwidth to feed the data into the trees in every
cycle. However, due to DAG irregularity, the parallel inputs needed in a clock
cycle typically do not reside at the same address in the different banks, as
discussed in §II-C. To handle this irregularity, the banks are made
independent in terms of read/write addressing. Each bank can read/write
from/to any location, independent of the other banks. This flexibility comes
at the overhead of additional instruction bits to encode these addresses.
While this overhead is present for reads, it is alleviated for writes as
discussed below.

Automatic write address generation: To reduce the instruction size, a novel
register-writing policy is used, alleviating the need of encoding write
addresses in instructions. The policy is to always write data to the empty
location with the lowest address within a register bank. Thus instructions do
not control where a write happens, but the register bank itself chooses the
appropriate location for the incoming data.

Why does the policy work? To perform correct execution with such an automatic
write policy, the compiler should be able to predict at compile time the write
addresses that will be chosen at run time. Since our target DAGs are known at
compile time and the PEs execute synchronously, the instruction execution
sequence is deterministic. This enables the compiler to predict write
addresses that will be chosen in every cycle, given that the execution begins
with a known state of the register banks (e.g, all the banks are empty).

Hardware: The policy requires that the occupancy state of every register is
tracked. This is done via a valid bit for every register, which is set to 1
when the corresponding register contains valid data. Using these valid bits,
the write address is computed with a priority encoder as shown in fig. 5(d). A
write to a register sets the respective valid bit. However, a read should not
automatically reset the bit, as a variable residing in a register can be
reused multiple times. The instructions should therefore indicate the last
read to the register to reset the valid bit and letting the register be
subsequently available to write new data. This resetting is done by a
valid_rst bit in the instruction, one for each bank. Thus, a multi-bit write
address is replaced with a single valid_rst bit, reducing the width of the
instructions. This automatic write policy results in a program size reduction
of 30% on average.

###  III-C Datapath-register banks connections

As discussed in §II-C, the connection of datapath to the register banks
requires some flexibility due to the irregularity of DAG edges. However, the
design space for interconnecting $\mathit{B}$ read ports to $\mathit{B}$
inputs and #PE outputs to $\mathit{B}$ write ports is huge. On one extreme,
full crossbars can be used for both inputs and outputs (fig. 6(a)). On the
other extreme, one-to-one connections can be done (fig. 6(d)).

Figure 6: Different interconnection topologies and their impact on bank
conflicts.

Compilation considerations: The interconnections not only have a hardware
impact but also impacts the compilation complexity. Crossbars significantly
simplify the compilation as it decouples PE mapping and bank mapping. For
example, for the design in fig. 6(a), when a DAG node is mapped to a PE, the
bank mapping options for its input data and output results do not get
restricted, as all the banks are accessible for reading and writing. In
contrast, for fig. 6(d), when a DAG node is mapped to a PE, its output result
can be stored to only one bank (or two in the case of the top PE), and the
input data should be mapped to the banks the PE can access. Thus, the PE
mapping and bank mapping get coupled. This coupling complicates the
compilation because the mapping of one node to a PE can impact the mapping of
all the rest of the nodes.

Thus, using at least one crossbar, either at the input or the output, ensures
that the mapping of one node only impacts a limited set of nodes. Furthermore,
hardware synthesis results revealed that a crossbar only consumes 4% area and
9% power of the whole design (see table II (input interconnect)). As a result,
designs with at least one crossbar are considered for exploration (fig.
6(a)-(c)) simplifying compilation without significant hardware overhead. The
mapping algorithm is explained in detail in §IV-B, which is used to minimize
the bank conflicts (fig. 6(e)) for the different design options. The bank
conflicts happen due to the following structural hazards: (1) two PEs
simultaneously access the same bank (but banks only have one read and one
write port), or (2) the input data (or the output result) is mapped to a bank
that the PE cannot access, inducing a stall for copying data across banks.

As expected, the design (a) achieves minimal conflicts. Yet, the design (b) is
selected, which has a crossbar for inputs, and each bank is connected to
outputs of one PE per layer. It induces only 1.4$\times$ higher conflicts due
to the limited output connectivity, increasing the overall latency by 1% but
reducing the overall power by 9%. As such, it achieves a better latency-power
trade-off. The design (c) results in significantly higher conflicts without
considerable area/power advantage over (b). The design (d) is not evaluated
further as it will incur even more conflicts than (c).

###  III-D Load, store, and copy of data

The register banks connect to an on-chip SRAM-based data memory with a read-
write width of $\mathit{B}$ words. The load/store from the data memory happens
in the form of vectors (with a word-level enable mask) as shown in fig. 5(b).
But, this data can be written to/read from different addresses in the register
banks. Note that the register write addresses for a load operation are
automatically generated as described in §III-B, whereas the register read
addresses for a store operation are encoded in the instructions. Furthermore,
to handle bank conflicts, a copy instruction enables an arbitrary shuffle of
data across banks using the crossbar as shown in fig. 5(c), implemented as
depicted on the left of fig. 5(a).

###  III-E Long, variable length instructions

The architecture is designed to be programmable for arbitrary DAGs, with a
custom VLIW instruction set (fig. 7(a)) that can configure the trees and
crossbar, copy data from one register bank to another, or load/store from data
memory. As different instructions encode different types of information, they
have different lengths, depending on the hardware parameters $D$, $B$, $R$.
Fig. 7(a) shows instruction lengths for a sample design configuration. For
proper utilization of the instruction memory, the instructions are packed
densely, without any bubbles (fig. 7(b)). The instruction memory can supply
_IL_ bits in every cycle, which is the same as the size of the longest
instruction. To handle varying lengths, a shifter before the instruction
decoder performs appropriate alignment, which makes sure there are no stalls
in execution, and the next instruction is always fully available for decoding.

In summary, DPU-v2 contains a datapath with parallel PE trees connected to a
banked register file with flexible interconnects. It is programmed with custom
variable-length VLIW instructions, which are packed densely in the instruction
memory. The independent parameters of the architecture template (0pt,
$\mathit{B}$ and $\mathit{R}$) are not fixed at this point and will be
selected based on a design space exploration described in §V.

Figure 7: Variable-length instructions (in (a)) are densely packed in the
memory (in (b)) and are appropriately aligned during decoding for stall-free
execution Figure 8: Steps involved in the custom compiler to generate
optimized instructions for a given DAG. Figure 9: (a) Cycles to be avoided
during block generation. (b) Avoid block dependencies like the dependence of D
on B. (c) Any subgraph with 2-input nodes, one sink node, and with the longest
path length less than the depth of a PE tree can be mapped to the PE tree by
replicating certain nodes. (d) Subgraphs that can be combined into a block
(possibly with permutations) for mapping to a datapath with one PE tree of
depth 3.

##  IV Compiler for DAG

Due to the non-conventional datapath with flexible interconnects and the VLIW
instruction set, it is difficult to modify a conventional compiler of
traditional processors to generate instructions for the proposed architecture.
Hence, a targeted compiler is developed to fully utilize the PE trees despite
the irregularity of unstructured DAGs. The compiler is designed to work for
any values of the design parameters (i.e. 0pt, $\mathit{B}$ and $\mathit{R}$),
instead of targeting a fixed configuration of the architecture template. The
compiler takes as input a DAG in any of the popular graph formats (i.e. all
formats supported by the NetworkX package [22]) and generates an execution
binary that can be directly programmed to DPU-v2. Since the structure of the
DAG remains static across multiple executions (during inference with PC and
for SpTRSV with multiple right-hand side vectors), the compilation is
performed offline and the DAG is unfolded at compile time to generate DAG-
specific instructions. The major compilation steps are shown in fig. 8 and
discussed next.

###  IV-A Block decomposition (Step 1)

Compilation begins by decomposing the input DAG, which is first converted to a
binary DAG (containing 2-input nodes only) by replacing a multi-input node
with a tree of 2-input nodes. This is to ensure that the nodes can be mapped
directly to the 2-input PEs. This binary DAG is decomposed into sets of nodes
called ‘blocks’. A block is supposed to be a monolithic unit that can be
executed with a single exec instruction (from fig. 7(a)). The constraints and
objectives for this decomposition step are as follows:

  * •

Constraint A: The resulting graph of blocks should be acyclic for functional
correctness. Fig. 9(a) shows an example of a cyclic decomposition, in which it
cannot be determined which block should be scheduled first.

  * •

Constraint B: The nodes in a block should be spatially schedulable on the PE
trees, considering the number of PEs available and their connectivity.

  * •

Objective C: The PE trees should be maximally utilized.

  * •

Objective D: The number of dependencies among blocks should be minimized to
reduce read-after-write hazards during the pipelined execution. Fig. 9(b)
shows an example where the dependency of block D on B could be avoided by an
improved combination of nodes in C, as the nodes in D are not actually
dependent on B in the DAG.

To achieve these objectives under the mentioned constraints, a greedy
iterative algorithm (see algo. 1) is designed that constructs one block in
every iteration as follows,

  1. 1.

Search all the schedulable connected subgraphs. A subgraph is schedulable if
all of its predecessor nodes (if any) are already assigned to the blocks in
previous iterations. Ensuring this schedulability property in every iteration
results in blocks that satisfy constraint A. Furthermore, a subgraph is
schedulable only if it can be completely mapped to a PE tree, which is needed
for constraint B. Subgraphs to be considered for this schedulability check are
constructed as follows: A node that is less than 0pt distance away from the
already mapped nodes (called $\mathit{curr\\_source\\_nodes}$) is considered
as a sink node, and along with its unmapped ancestors, form a subgraph. The
check that whether a subgraph satisfies constraint B or not is simplified due
to the tree topology of PEs. Any connected subgraph with only 2-input nodes,
exactly one sink node, and with the longest path length less than 0pt can be
mapped to a PE tree of depth 0pt. Fig. 9(c) shows an example of a non-tree
subgraph that satisfies these properties, and can be mapped through
replication. In this way, the find_schedulable_subg() function (line 6) finds
all the schedulable subgraphs that have a given predecessor node as an input.

The overall search for subgraphs is made efficient by keeping track of the
schedulable subgraphs across iterations (in the set
$\mathit{\mathcal{D}_{sch}}$), to avoid re-searching the same subgraphs again.
In every iteration, only the subgraphs that originate from the nodes mapped in
the previous iteration are added to the set $\mathit{\mathcal{D}_{sch}}$
(lines 5-7), by setting $\mathit{curr\\_source\\_nodes}$ appropriately (line
23).

  2. 2.

Among the schedulable subgraphs, select a set to form a block. The previous
step finds connected subgraphs that can be mapped to the datapath. As shown in
fig. 9(d), multiple such subgraphs (with possibly different longest path
lengths) can be combined into a block. To find the appropriate set of
subgraphs to combine in a block, the fitness of a block is evaluated based on
objectives C and D: (1) According to obj. C, the blocks with more nodes are
more fit. (2) Quantifying obj D is difficult. In practice, the dependencies
across blocks decrease if the subgraphs combined in a block lie closer to each
other in the DAG. Hence, a block is penalized according to the distance
between the nodes in a block. The distance is approximated by the difference
in occurrences of their nodes during a depth-first traversal of the DAG
(performed once at the beginning). These two metrics of fitness are used to
add an appropriate subgraph to a block (lines 15-16) and to compare different
valid blocks (lines 17-19).

The process repeats until all the nodes are mapped to blocks. Note that nodes
are not mapped to specific PEs yet, which is done subsequently in step 2.

Asymptotic complexity: The number of iterations scale linearly with the number
of DAG nodes for a given datapath. In each iteration, selecting a set of
subgraphs to form a block scales linearly with the number of schedulable
subgraphs (i.e. the size of $\mathit{\mathcal{D}_{sch}}$), which in turn
scales linearly with the number of DAG nodes in the worst case. As such, the
complexity is $O$($N^{2}$), where $N$ is the number of nodes.

1

$\triangleright$ Decompose into blocks (section §IV-A)

Input: $G(V,E)$: Binarized DAG where $V$ is the set of nodes and $E$ is the
set of edges. 0pt, $\mathit{T}$: The depth and number of trees in the
datapath.

Output: $\mathit{\mathcal{B}}$: Set of blocks

2

3$\mathit{\mathcal{B}}\leftarrow\varnothing$,
$\mathit{\mathcal{D}_{sch}}\leftarrow\varnothing$,
$\mathit{dfs\\_order}\leftarrow$ dfs($G$),
$\mathit{done\\_nodes}\leftarrow\varnothing$

$\mathit{combos}\leftarrow$ possible_depth_combinations($D$, $T$)
$\triangleright$ See fig. 9(d)

4

5$\mathit{curr\\_source\\_nodes}\leftarrow$ Nodes with no incoming edges

6

7while  _$\mathit{len(done\\_nodes)}\mathrm{\;\neq\;}\mathit{len(V)}$_ do

8 for  _$n\mathrm{\;in\;}\mathit{curr\\_source\\_nodes}$_ do $\triangleright$
Find sched. subgraphs

9 $\mathit{temp\\_\mathcal{D}_{sch}}\leftarrow$ find_schedulable_subg($n$)

10
$\mathit{\mathcal{D}_{sch}}\leftarrow\mathit{\mathcal{D}_{sch}}\cup\mathit{temp\\_\mathcal{D}_{sch}}$

11

12

$\triangleright$ Choose the best subgraphs to form a block

13 $\mathit{best\\_fitness}\leftarrow$ 0,
$\mathit{block}\leftarrow\varnothing$

14 for  _$\mathit{combo}\mathrm{\;in\;}\mathit{combos}$_ do

15 $\mathit{temp\\_block}\leftarrow\varnothing$

$\triangleright$ $\mathit{combo}$ is a list of subgraph depths that can be
combined in a block. For example, $\mathit{combo}$=[2, 1, 1] represents the
third combination in fig. 9(d).

16 $d_{max}\leftarrow\mathit{combo}[0]$

17 $\mathit{largest\\_subg}\leftarrow$
get_largest_subg($\mathit{\mathcal{D}_{sch}}$, $d_{max}$)

18 $\mathit{temp\\_block.add(largest\\_subg}$)

19 for  _$d\mathrm{\;in\;}\mathit{combo}[1:]$_ do

$\triangleright$ Iterate over subgraphs in $\mathit{\mathcal{D}_{sch}}$ to
find a suitable subgraph of depth $d$

20

21 $\mathit{subg\\_of\\_depth\\_d}\leftarrow$
get_fittest_subg($\mathit{\mathcal{D}_{sch}}$, $d$, $\mathit{largest\\_subg}$,
$\mathit{dfs\\_order}$)

22 $\mathit{temp\\_block.add(subg\\_of\\_depth\\_d}$)

23

24 $\mathit{temp\\_fitness}\leftarrow$ get_fitness($\mathit{temp\\_block}$)

25 if  _$\mathit{temp\\_fitness} >\mathit{best\\_fitness}$_ then

26 $\mathit{block}\leftarrow\mathit{temp\\_block}$,
$\mathit{best\\_fitness}\leftarrow\mathit{temp\\_fitness}$

27

28

29

$\triangleright$ Remove all the subgraphs from $\mathit{\mathcal{D}_{sch}}$
that contain a node allocated to $\mathit{block}$.

30 for  _$\mathit{subg}\mathrm{\;in\;}\mathit{\mathcal{D}_{sch}}$_ do

31 if
_$\mathrm{any\;node\;from\;}\mathit{block}\mathrm{\;is\;in\;}\mathit{subg}$_
then

32 $\mathit{\mathcal{D}_{sch}.remove(subg}$)

33

34

35

36 $\mathit{\mathcal{B}.add(block}$),
$\mathit{curr\\_source\\_nodes}\leftarrow$ Nodes of $\mathit{block}$

37 $\mathit{done\\_nodes}.add$(Nodes of $\mathit{block}$)

38return _$\mathit{\mathcal{B}}$_

39

Algorithm 1 Step 1 $\langle G(V,E),D,T\rangle$

###  IV-B PE and register bank mapping (Step 2)

To generate an instruction for each block, every node of the block needs to be
assigned to a hardware PE in the PE trees, and source/destination of the
inputs/outputs of a block should be mapped to register banks. The constraints
and objectives of the mappings are as follows:

  * •

Constraint E: Only one node can be mapped to one PE (note that the replication
in 9(c) is achieved by splitting nodes into multiple temporary nodes). The
mapping should be topologically consistent, which requires that if a node $n$
is mapped to a PE $p$, then the predecessors and successors of $n$ are also
mapped to, respectively, the predecessors and successors of $p$.

  * •

Constraint F: Two different inputs of a block should not be mapped to the same
register bank, to prevent bank conflicts while reading.

  * •

Constraint G: Two different outputs of a block should not be mapped to the
same register bank, to prevent bank conflicts while writing.

  * •

Constraint H: For the nodes whose results are stored as outputs of a block,
the PE mapping and the bank mapping of that node should be compatible, i.e.
the bank should be writable from that PE. This constraint arises due to the
limited connectivity of PEs and banks in the output interconnect (fig. 5(a)).
Note that such a constraint is not required for block inputs because the input
interconnect is a crossbar.

  * •

Objective I: Minimize bank conflicts, as every bank conflict will result in a
stalling cycle for data copy.

  * •

Objective J: Balance the distribution across register banks.

1

2

3

$\triangleright$ PE and register bank mapping(section §IV-B)

Input: $G(V,E)$: Binarized DAG where $V$ is the set of nodes and $E$ is the
set of edges. 0pt: The depth of PE trees in the datapath. $\mathit{B}$: The
number of register banks. $\mathit{output\\_connectivity}$: Information of
which PE’s output is connected to which banks (Note that the input
connectivity is assumed to be a crossbar). $\mathit{\mathcal{B}}$: The set of
blocks generated in step 1.

Output: $\mathit{\mathcal{M}_{p}}$: Mapping of nodes to PEs.
$\mathit{\mathcal{M}_{b}}$: Mapping of input/output nodes to banks.

4

5$\mathit{\mathcal{M}_{p}}\leftarrow\\{\\}$,
$\mathit{\mathcal{M}_{b}}\leftarrow\\{\\}$,
$\mathit{\mathcal{S}_{p}}\leftarrow\\{\\}$,
$\mathit{\mathcal{S}_{b}}\leftarrow\\{\\}$

6$\mathit{io\\_nodes}\leftarrow$ Nodes that serve as inputs/outputs of blocks

7for  _$\mathit{block}\mathrm{\;in\;}\mathit{\mathcal{B}}$ ,
$\mathit{subg}\mathrm{\;in\;}\mathit{block}$,
$\mathit{node}\mathrm{\;in\;}\mathit{subg}$_ do $\triangleright$ Initialize
the sets of compatible PEs and banks

$\triangleright$ Determine which PEs are compatible based on the position of
the node in the subgraph. For example, only the top PE is compatible for
mapping node $a$ in fig. 10.

8 $d\leftarrow$ get_max_depth_from_sources($\mathit{subg}$, $\mathit{node}$)

9 $\mathit{compatible\\_PEs}\leftarrow$ PEs at depth $d$ in the datapath

10
$\mathit{\mathcal{S}_{p}}[\mathit{node}]\leftarrow\mathit{compatible\\_PEs}$

11 if  _$\mathit{node}\mathrm{\;in\;}\mathit{io\\_nodes}$_ then

$\mathit{\mathcal{S}_{b}}[\mathit{node}]\leftarrow\mathit{output\\_connectivity}[\mathit{compatible\\_PEs}]$
$\triangleright$ Banks that are writable from the compatible PEs

12

13

14

$\triangleright$ A dictionary to find the node with the minimum number of
compatible banks in $O$($\mathit{B}$) time irrespective of the DAG size. Key:
The number of compatible banks, Value: The set of nodes.

15 $\mathit{\mathcal{M}_{nodes}}\leftarrow$ {$b$:$\varnothing$ for $b$ in
[0,1,..,$\mathit{B}$]}

16for  _$\mathit{node}\mathrm{\;in\;}\mathit{io\\_nodes}$_ do

17 $\mathit{num\\_banks}\leftarrow$
$len(\mathit{\mathcal{S}_{b}}[\mathit{node}])$

18 $\mathit{\mathcal{M}_{nodes}[\mathit{num\\_banks}]}.add(\mathit{node})$

19

$\triangleright$ Iteratively map nodes from $\mathit{io\\_nodes}$ to PEs and
banks

20

21$\mathit{done\\_nodes}\leftarrow\varnothing$

22while
_$\mathit{len(done\\_nodes)}\mathrm{\;\neq\;}\mathit{len(io\\_nodes)}$_ do

$\triangleright$ Choose a node with the minimum number of compatible banks. If
there are multiple, choose any one randomly.

23 for  _$b\mathrm{\;in\;}[0,...,B]$_ do

24 if  _$\mathit{\mathcal{M}_{nodes}[b]}\mathrm{\;\neq\;}\varnothing$_ then

25
$\mathit{chosen\\_node}\leftarrow\mathit{\mathcal{M}_{nodes}[b]}.pop(\mathit{random})$

26 break

27

28

29 $\mathit{simul\\_wr}\leftarrow$ Nodes written simultaneously with
$\mathit{chosen\\_node}$

30 $\mathit{simul\\_rd}\leftarrow$ Nodes read simultaneously with
$\mathit{chosen\\_node}$

$\triangleright$ Bank mapping

31 if
_$\mathit{\mathcal{S}_{b}}[\mathit{chosen\\_node}]\mathrm{\;\neq\;}\varnothing$_
then $\triangleright$ A compatible bank exists

$\mathit{chosen\\_bank}\leftarrow\mathit{\mathcal{S}_{b}}[\mathit{chosen\\_node}].pop(\mathit{random})$
$\triangleright$ In practice, choosing randomly achieves Objective J

32

33 else $\triangleright$ No compatible bank left

$\triangleright$ Bank conflicts will happen. Minimize the number of conflicts
by choosing a bank that is least contented.

34 $\mathit{chosen\\_bank}\leftarrow$ A bank that is allocated to the least
number of nodes in $\mathit{simul\\_wr}$ and $\mathit{simul\\_rd}$ sets

35

$\triangleright$ PE mapping

36 $\mathit{desirable\\_PEs}\leftarrow$ (PEs that can write to
$\mathit{chosen\\_bank}$) $\cap$
$\mathit{\mathcal{S}_{p}}[\mathit{chosen\\_node}]$

37 if  _$\mathit{desirable\\_PEs}\mathrm{\;\neq\;}\varnothing$_ then
$\triangleright$ No bank conflict while writing.

38
$\mathit{chosen\\_PE}\leftarrow\mathit{desirable\\_PEs}.pop(\mathit{random})$

39 else $\triangleright$ A bank conflict while writing, but the
$\mathit{chosen\\_PE}$ is according to constraint E.

40
$\mathit{chosen\\_bank}\leftarrow\mathit{\mathcal{S}_{p}}[\mathit{chosen\\_node}].pop(\mathit{random})$

41

$\triangleright$ Intra-block compatibility update

42

43 Remove $\mathit{chosen\\_bank}$ from $\mathit{\mathcal{S}_{b}}$ of
$\mathit{simul\\_wr}$ nodes, which by definition are from the same block as
$\mathit{chosen\\_node}$, and update $\mathit{\mathcal{M}_{nodes}}$
accordingly.

44 for  _$node\mathrm{\;in\;the\;block\;of\;}\mathit{chosen\\_node}$_ do

45 Update $\mathit{\mathcal{S}_{p}}[\mathit{node}]$ according to constraint
$E$

46 (If $\mathit{node}$ in $\mathit{io\\_nodes}$) Update
$\mathit{\mathcal{S}_{b}}[\mathit{node}]$ according to the updated
$\mathit{\mathcal{S}_{p}}[\mathit{node}]$ based on the
$\mathit{output\\_connectivity}$. Also, update $\mathit{\mathcal{M}_{nodes}}$
accordingly.

$\triangleright$ Inter-block compatibility update

47 Remove $\mathit{chosen\\_bank}$ from $\mathit{\mathcal{S}_{b}}$ of
$\mathit{simul\\_rd}$ nodes, and update $\mathit{\mathcal{M}_{nodes}}$
accordingly.

48

49 $\mathit{\mathcal{M}_{p}[chosen\\_node]}\leftarrow\mathit{chosen\\_PE}$,
$\mathit{\mathcal{M}_{b}[chosen\\_node]}\leftarrow\mathit{chosen\\_bank}$,
$\mathit{\mathcal{S}_{b}.remove[chosen\\_node]}$,
$\mathit{\mathcal{S}_{p}.remove[chosen\\_node]}$

50 $\mathit{done\\_nodes.add(chosen\\_node)}$

51

52

$\triangleright$ Allocate PEs to the rest of the nodes (i.e. non
$\mathit{io\\_nodes}$) just as above but without bank-mapping related steps.

53

54return _$\mathit{\mathcal{M}_{p},\mathit{\mathcal{M}_{b}}}$_

55

Algorithm 2 Step 2 $\langle
G(V,E),D,B,\mathit{output\\_connectivity},\mathit{\mathcal{B}}\rangle$

Due to constraint H, the PE mapping is performed in tandem with the register
bank mapping, since assigning a node to PE restricts the number of compatible
banks and vice versa. Specifically, a greedy iterative algorithm is used which
performs the mappings for one node in every iteration as described in
algorithm 2. The algorithm keeps track of a set of compatible PEs ($S_{p}$)
for every node and a set of compatible banks ($S_{b}$) for nodes that serve as
inputs/outputs of blocks (and hence should be stored to the register file).
These nodes involved in inputs/outputs (e.g., nodes $a$, $b$, and $d$ in fig.
10(a)) are called $\mathit{io\\_nodes}$ in the algorithm. A PE is compatible
if the topological consistency defined in constraint E can be satisfied for
all the nodes in the block after the node is mapped to the PE. A bank is
compatible, if mapping the node to that bank does not cause a bank conflict
with the already mapped nodes.

Node order for mapping: The mapping is done for $io\\_nodes$ first. In every
iteration, the node with the least number of compatible banks (to achieve
objective $I$) in $S_{b}$ is chosen for mapping, from anywhere in the DAG
ignoring the block boundaries. The runtime of the selection is made
independent of the size of the DAG using the $\mathit{\mathcal{M}_{nodes}}$
datastructure (constructed in lines 9-12 in algo. 2), and searching in it in
every iteration (lines 15-18).

Mapping: The chosen node is mapped to a compatible bank (chosen randomly to
achieve objective J) if available, otherwise to a bank that leads to the least
conflicts (lines 21-24). Subsequently, the node is mapped to a PE (lines
25-29) that can write to the chosen bank, if such a PE is compatible. If not,
a compatible PE is chosen at random from $S_{p}$. Note that at least one
compatible PE will always be left because, as explained in step 1(§IV-A), the
blocks satisfy constraint B, ensuring the schedulability of nodes. Fig. 10(a)
shows the mapping of a node $b$ to an appropriate PE and bank (in color). The
following two updates happen to the $S_{p}$ and $S_{b}$ of the nodes affected
by this mapping.

Intra-block compatibility update: The PE and bank options for the unmapped
nodes $a$, $c$ and $d$ decrease due to the mapping of $b$ in fig. 10(a),
according to the constraints E and G. $S_{p}$ and $S_{b}$ for these nodes are
updated accordingly (lines 30-33).

Inter-block compatibility update: Nodes from other blocks are also affected by
the bank assignment to $b$. The nodes $e$ and $f$ in fig. 10(a) are consumed
together with $b$ and cannot be allocated to the same bank (to satisfy
constraint F). Hence, $b$’s bank is removed from their $S_{b}$ (line 34).

After these compatibility updates, a new node is selected in the next
iteration, and the process repeats until all the $\mathit{io\\_nodes}$ are
mapped. Next, the non $\mathit{io\\_nodes}$ (node $c$ in fig. 10(a)) are
mapped to PEs in the same way as discussed earlier, but without the steps for
bank mapping.

Asymptotic complexity: The work done in the intra-block update depends only on
the size of the datapath and does not depend on the properties of the DAG,
while the work done in the inter-block update scales with the outdegree of the
node being assigned. Since the number of iterations is same as the number of
nodes, the algorithm complexity is $O$($N\times\Delta(G)$), where $N$ is the
number of DAG nodes and $\Delta(G)$ is the maximum outdegree of the DAG.

Fig. 10(b) shows that our algorithm achieves a 292$\times$ reduction in bank
conflicts compared to random bank allocation, confirming that the objective
$I$ is met. Fig. 10(c) shows the number of active registers across banks
during the execution of a workload (from table I), demonstrating a well-
balanced distribution, in-line with objective $J$. The spilling of registers
for limited bank size is discussed later in this section. The bank conflicts
are resolved with the copy instruction from fig. 7 that copies the data to an
appropriate bank, eliminating the need for handling the bank conflicts in
hardware. Finally, an instruction list is constructed with the exec and copy
instructions, along with the load instructions to fetch inputs from the data
memory for the first time.

Impact of the crossbar: Note that the input crossbar significantly simplifies
the inter-block update. It decouples the PE allocations of a block from the
bank allocations of its inputs, and limits constraint H to outputs only. This
ensures that the inter-block updates remain limited to the inputs of the
successor blocks only, and do not propagate to the whole DAG. Without a
crossbar, the inter-block update can possibly affect all the nodes in the DAG,
quickly reducing the number of compatible banks for the rest of the nodes in
every iteration.

Figure 10: (a) An example of how the mapping of node $b$ affects the
compatible PEs and banks of the other nodes. (b) Our algorithm achieves
considerably lower bank conflicts than random allocation. (c) and (d) shows
that the data allocation across register banks remains well balanced.

###  IV-C Pipeline-aware reordering (Step 3)

As the datapath has $D+1$ pipestages, the instruction list (generated in step
2) is re-ordered to ensure that the dependent instructions are at least $D+1$
instructions apart to prevent read-after-write (RAW) hazards. The reordering
involves a search for independent instructions to insert in between dependent
instructions. This search is limited to a fixed-size window of succeeding
instructions (300 in our experiments), to make the runtime scale linearly with
the size of the instruction list. Subsequently, no-operation (nop)
instructions are inserted for the unresolved hazards.

TABLE I: Statistics of the benchmarked DAGs

| Type | Workloads |  | Nodes
---
(n)
| Longest
---
path (l)
| n/l
---
| Compile
---
time (min.)
(a) | PC | tretail | 9k | 49 | 180 | 1
mnist | 10k | 26 | 400 | 2
nltcs | 14k | 27 | 504 | 3
msnbc | 48k | 28 | 1.7k | 28
msweb | 51k | 73 | 698 | 31
bnetflix | 55k | 53 | 1k | 35
(b) | SpTRSV | bp_200 | 8k | 139 | 60 | 1
west2021 | 10k | 136 | 74 | 1
sieber | 23k | 242 | 94 | 6
jagmesh4 | 44k | 215 | 203 | 12
rdb968 | 51k | 278 | 181 | 15
dw2048 | 79k | 929 | 85 | 16
(c) | Large PC | pigs | 0.6M | 90 | 6.9k | 121
andes | 0.7M | 84 | 8.6k | 145
munin | 3.1M | 337 | 9.1k | 850
mildew | 3.3M | 176 | 18.8k | 910

Figure 11: Design space exploration to identify the min-EDP design. The
optimal points are highlighted with large markers.

###  IV-D Spilling from register file (Step 4)

Data must be spilled from the register file if intermediate results do not
fit. Given the schedule of execution, a live-range analysis is performed to
determine when the spilling is required, and store instructions are
appropriately inserted. The spilled data are later loaded back by inserting
load instructions before they are supposed to be consumed, in a way that avoid
new RAW pipeline hazards. The live-range analysis and insertion of
intermediate loads/stores scale linearly with the size of the DAG. Fig. 10(c)
and (d) shows register occupancy profile for a workload without and with
register spilling, respectively, for $\mathit{R}$=64.

The final output of the compilation process is a list of instructions to be
executed on DPU-v2 for the given DAG, which can be directly translated into a
binary program for execution. The distribution of different types of
instructions is shown in fig. 13 in the next section.

###  IV-E Reduction in memory footprint

The list of instructions generated by the compiler statically encodes the
entire DAG structure, leading to a larger instruction footprint compared to a
conventional approach of a for loop iterating over the DAG stored in a
compressed sparse row (CSR)-like format and performing indirect memory
accesses. However, note that the overall memory footprint (instructions +
data) of our approach is in fact lower than the CSR datastructure because the
statically generated instructions can encode the edge connectivity information
with fewer bits, due to the following reasons.

  * •

For the DAG edges that are mapped to PE-PE connections, the addresses for the
source and destination of the edges need not be stored, in contrast to the CSR
datastructure which stores the pointers for every edge.

  * •

Due to the static mapping of variables to the register file, the address for
the source/destination of the edges that are mapped to PE-register or
register-PE connections can be specified with a register address (= 11b in our
final design configuration) instead of encoding it in a global address space
of 32/64b like in the CSR datastructure.

For the target workloads, the total memory footprint of instructions and data
is 48% smaller than the CSR datastructure, which is not required in our
approach.

##  V Design space exploration

Experiments are designed to find the most energy-efficient hardware
configuration (i.e. 0pt, $\mathit{B}$ and $\mathit{R}$) of DPU-v2 for a suite
of target workloads, and compare it with state-of-the-art implementations.

###  V-A Workloads

The performance is benchmarked with compute DAGs of varying sizes (see table
I) from two classes of workloads.

Probabilistic circuits (PC). Probabilistic circuits (also called sum-product
networks) are used in machine learning for robust inference under uncertainty,
safety-critical tasks, and neuro-symbolic reasoning [49, 59, 17, 51]. A PC is
an irregular DAG in which the nodes are either sum or product operations. The
experiments are performed on standard benchmarks of density-estimation
applications from [29] and from [48].

Sparse matrix triangular solves (SpTRSV). Solving a matrix triangular system
is a fundamental operation in linear algebra [14], used in embedded
applications like robotic navigation [40], wireless communication [54],
cryptography [15], etc. Real-world matrices usually turn out to be highly
sparse and the resulting compute DAG highly irregular. Benchmarking is done on
matrices of varying sizes from the SuiteSparse benchmark of real applications
[13].

Figure 12: Latency vs. Energy plot with a constant EDP curve passing through
the min-EDP point, colored according to $D$, $B$, and $R$ in (a), (c), and
(d).

###  V-B The most-efficient design configuration

To reliably estimate the energy impact of design choices, a parameterized
Verilog model is developed, which is used to synthesize gate-level netlists in
a CMOS 28nm technology. The design space exploration is done by varying the
parameters in the following set of values: 0pt in [1, 2, 3], $\mathit{B}$ in
[8, 16, 32, 64], and $\mathit{R}$ in [16, 32, 64, 128], leading to 48
combinations. For each of the design points, the energy is computed by mapping
actual workloads ((a) and (b) in table I) with the compiler, and annotating
the resulting switching activities of the workloads from gate-level netlist
simulations with a target frequency of 300MHz. The mean latency, energy, and
energy-delay product (EDP) per operation, averaged over the workloads, are
plotted in fig. 11 (a), (b), and (c), respectively.

TABLE II: Area and power breakdown of DPU-v2

| Area |  | Power
---|---|---|---
mm2 | % |  | mW | %
Datapath: |  |  |  |  |
PEs | 0.13 | 4 |  | 11.9 | 11
Pipelining registers | 0.04 | 1 |  | 8.0 | 7
Input interconnect | 0.14 | 4 |  | 10.0 | 9
Output interconnect | 0.01 | 0 |  | 0.5 | 1
Register file: |  |  |  |  |
Banks | 0.35 | 11 |  | 24.0 | 22
Wr addr generator | 0.03 | 1 |  | 7.8 | 7
Control: |  |  |  |  |
Instr fetch | 0.06 | 2 |  | 7.0 | 6
Decode | 0.04 | 1 |  | 2.6 | 2
Pipelining registers | 0.01 |  0 |  | 2.7 | 2
Instruction memory | 1.20 | 38 |  | 27.7 | 26
Data memory | 1.20 | 38 |  | 6.7 | 6
| 3.20 |  |  | 108.9 |

As expected, the minimum latency design point (0pt=3, $\mathit{B}$=64,
$\mathit{R}$=128) has the highest values of 0pt, $\mathit{B}$, and
$\mathit{R}$, .i.e., the one with the largest area. Note that increasing
$\mathit{R}$ beyond 32 has diminishing improvement as the active set of data
is able to fit within the register file. Unlike latency, the min. energy point
(0pt=3, $\mathit{B}$=16, $\mathit{R}$=64) uses fewer $\mathit{B}$ (and hence
also fewer PE trees) and fewer $\mathit{R}$. Notice that increasing 0pt
improves latency without consuming additional power, resulting in an energy
improvement as well. This demonstrates the effectiveness of the tree-based
spatial datapath. On the other hand, increasing $\mathit{B}$ decreases latency
but with proportionally more power consumption because the utilization of the
increasingly parallel datapath gradually decreases, shifting the minimum
energy point towards a lower value of $\mathit{B}$.

Minimum EDP: The minimum energy-delay product (EDP, fig. 11(c)) is achieved at
(0pt=3, $\mathit{B}$=64, $\mathit{R}$=32). Fig. 12 shows latency vs. energy
charts for a different perspective of the design space, along with a constant-
EDP curve passing through the min-EDP point. The slope of the curve indicates
that the latency has more variation than the energy.

Breakdown of area, power, and latency. Table II shows the distribution of area
and power across different modules for the min-EDP design. Memories consume
most of the area and 32% of the power. The datapath and the register file
consume around equal power: 28% and 29%, respectively. Fig. 13 shows the
breakdown of the different categories of instructions across the different
workloads executed on this architecture instantiation.

Compilation time The compilation times of the DAGs are reported in table I for
the min-EDP design. For the large PCs, the decomposition into blocks (step 1)
becomes too slow and the DAG is first coarsely decomposed into partitions with
20k nodes each, using the technique described in [44] (which scales linearly
with DAG size), and then each partition is decomposed independently into
blocks.

Figure 13: Breakdown of instructions.

.

Figure 14: Throughput for every workload.

.

TABLE III: Performance comparison with other platforms. †Estimated based on
the speedups over CPUSPU.

| DPU-v2 | DPU[46] | CPU[44] | GPU [30] | DPU-v2 (L) | SPU[11] | CPUSPU [11] | CPU[44] | GPU
---|---|---|---|---|---|---|---|---|---
Workloads | PC (a) and SpTRSV (b) from Table I | Large PC (c) from Table I
Technology | 28nm | 28nm | 14nm | 12nm | 28nm | 28nm | 14nm | 14nm | 12nm
Area (mm2) | 3.2 | 3.6 | NA | 754 | 40.4 | 36.6 | NA | NA | 754
Freq (GHz) | 0.3 | 0.3 | 3 | 1.35 | 0.3 | NA | 3 | 3 | 1.35
Mem BW (GB/s) | – | – | 120 | 616 | 256 | 256 | 120 | 120 | 616
Through. (GOPS) | 4.2 | 3.1 | 1.2 | 0.4 | 34.6 | 22.2† | 1.7 | 1.8 | 4.6
Speedup | 3.5$\times$ | 2.6$\times$ | 1$\times$ | 0.3$\times$ | 20.7$\times$ | 13.3$\times$ | 1$\times$ | 1.1$\times$ | 2.8$\times$
Power (W) | 0.11 | 0.07 | 55 | 98 | 1.1 | 16 | 61 | 65 | 155
EDP (pJ$\times$ns) | 6.0 | 7.1 | 38k | 1M | 1.0 | 57.4 | 36k | 27k | 9k

###  V-C State-of-the-art comparison

The proposed processor is benchmarked against two state-of-the-art ASIPs and
optimized CPU and GPU baselines.

  * •

CPU: A state-of-the-art multi-threaded implementation of DAGs [44] is
benchmarked on an Intel(R) Xeon Gold 6154 CPU with 18 cores using the open-
sourced code222https://github.com/nimish15shah/GRAPHOPT.

  * •

GPU: The SpTRSV implementation [30] from the cuSPARSE library is benchmarked
on an RTX 2080Ti GPU. In the absence of a GPU library for PC, we implemented a
layer-wise parallelization in CUDA [35] that is inspired by the cuSPARSE
SpTRSV implementation.

####  V-C1 Comparison using PC and SpTRSV

For the PC and SpTRSV workloads in tables I(a) and (b), the performance of the
obtained min-EDP configuration of our processor is compared with a SoTA
processor targeting irregular DAGs called the DAG processing unit (DPU) [46,
45], in addition to CPU and GPU.

DPU: DPU, the prior architecture generation of this line of research, has an
architectural approach similar to fig. 2(a). A configuration of DPU with a
similar area, number of registers, arithmetic format, and on-chip memory
bandwidth (112.5GB/s) as the current work is synthesized in a 28nm technology
from the open-source
RTL333https://github.com/nimish15shah/DPU_DAG_Processing_Unit.

Results: Fig. 14(a) shows the throughput of individual workloads and table III
summarizes the results. DPU-v2 outperforms DPU for all workloads except
bnetflix and sieber, with an average speedup of 1.4$\times$, 4.2$\times$, and
10.5$\times$ over DPU, CPU, and GPU, respectively, while achieving 15% better
EDP than DPU.

Analysis: Although operating at higher frequencies, the CPU and GPU
underperform specialized architectures due to severe inefficiency in the cache
hierarchies due to the irregular fine-grained accesses (as discussed in §I).
Furthermore, due to the relatively small size of the workloads, there is not
enough parallel work to amortize the synchronization and communication
overheads of multiple cores. DPU addresses these problems leading to
relatively modest gains over it. The major reasons for the speedup of DPU-v2
over DPU are as follows.

  * •

DPU does not enable the reuse of intermediate variables within the datapath,
which is achieved in this work through PE trees. Consequently, this work can
utilize more PEs than DPU for the same number of input/output ports of the
datapath and leads to fewer register file accesses.

  * •

In DPU, 43% of the load requests result in bank conflicts, severely
underutilizing the on-chip data memory bandwidth. To reduce the impact on
throughput, aggressive hardware prefetching is performed to overlap memory
requests with computations, at the cost of higher hardware complexity. In
contrast, this work simplifies the hardware by considerably eliminating the
bank conflicts altogether by limiting the irregular accesses to register banks
and through advanced bank mapping during compilation. As discussed in §II-A,
such a compile-time conflict avoidance is difficult for DPU due to
asynchronous execution of cores leading to an unpredictable timing of load
requests.

####  V-C2 Comparison using large PCs

To demonstrate the scalability of this work, a large configuration of the
proposed processor is benchmarked with large PCs with up to 3.3M nodes (table
I(c)) and compared with the sparse processing unit (SPU) [11], the CPU
baseline from the SPU work (CPUSPU), CPU, and GPU.

  * •

SPU: SPU is a coarse-grained reconfigurable array (CGRA)-like architecture
tuned for sparse workloads. Since the code is not open-sourced, we estimate
the throughput based on the speedups reported over its CPU baseline.

  * •

CPUSPU: For estimating the throughput of SPU and for a fair comparison of SPU
speedup with our work, the CPU baseline from SPU is benchmarked444The CPUSPU
baseline code is provided by the SPU authors.

  * •

DPU-v2 (L): For the large workloads, our processor is synthesized with a
larger on-chip data memory (2MB) and 256 registers per bank. Unlike previous
experiments, the instructions do not fit in the on-chip memory anymore, and
are streamed from external interface with a bandwidth of 64 GB/s. Since SPU
assumes a 256 GB/s memory interface and performs batch execution, our system
is benchmarked with 4 cores (with 64GB/s requirement per core) for a fair
comparison. The parallel cores can either perform batch execution (used for
benchmarking) or execute different DAGs. Like the SPU experiments, the power
consumption of an external memory and memory controller are not included in
the measurements.

Results: The per-workload throughput is shown in fig. 14(b) and the overall
results are summarized in table III. With a similar area and external
bandwidth consumption, the proposed processor outperforms prior work, with an
overall speedup of 1.6$\times$, 20.7$\times$, 19.2$\times$, and 7.5 $\times$
over SPU, CPUSPU, CPU, and GPU, respectively. Furthermore, the speedup is
achieved at significantly lower power (1.1W) compared to SPU (16W), greatly
improving EDP.

Analysis: The large DAGs are able to better utilize GPU, leading to higher
throughput than CPU, but also consume higher power. The CPU and GPU still
underperform compared to specialized hardware due to the reasons discussed in
§I. DPU-v2 (L) consumes significantly lower power than SPU due to the
following main architectural differences:

  * •

SPU does not have a register file leading to significantly higher memory
accesses compared to this work.

  * •

Although, in general, SPU supports the reuse within the CGRA-like datapath, it
could not be fully utilized for unstructured DAGs due to the lack of a
frequently recurring pattern for which the CGRA connectivity can be fixed.

  * •

SPU aggressively reorders memory requests in hardware to properly utilize the
on-chip memory bandwidth in the presence of irregular requests, at the expense
of higher hardware complexity. On the other hand, this work considerably
eliminates the bank conflicts altogether by limiting the irregular accesses to
register banks and through advanced bank mapping during compilation.

This way, the hardware-software co-optimization presented for DPU-v2 results
in efficient parallel execution of irregular DAGs for emerging embedded
applications.

##  VI Additional related works

Specialized dataflow: MAERI [28], an architecture with flexible dataflow for
neural networks, is the most similar to this work, as it also uses a tree-
based datapath of PEs. But, the controller and the interconnection networks
are designed specifically for neural networks, and do not natively support
arbitrary DAGs. Due to the regularity in NNs, the mapping of operations and
routing of operands get significantly simplified compared to arbitrary DAGs.
The regularity also limits bank conflicts, which get exacerbated due to
irregularity.

Clark et al. proposed approaches related to this work, in which frequent
recurring subgraphs are identified in a DAG [7], [6] to determine the most
promising datapath structure. However, the number of ports of the datapath (4
inputs, 2 outputs) are severely limited due to the use of a monolithic
register file, limiting hardware parallelism. This work addresses that by
using a banked register file and appropriate interconnections, allowing a
highly parallel datapath with up to 64 read/write ports.

Chainsaw [47] decomposes DAGs into chains instead of trees, which is also a
promising alternative as multi-input nodes can also be unfolded as chains.
However, the inter-chain communication, which is frequent for irregular DAGs,
happens via a central register file accessed with a bus. This would become a
major bottleneck as fig. 6 shows that a multi-ported register file and high-
bandwidth interconnection used in this work are critical for good performance.

SEED[33] combines a dataflow architecture with a general-purpose processor. It
focuses on small DAGs within nested loops, which typically contain a high
proportion of conditional nodes, while our work focuses on large
DAGs,requiring a different approach based on high-bandwidth interconnects and
a banked register file.

Operand networks: The input/output interconnects of our work can be classified
as scalar operand networks as discussed in [50], however we closely couple
operand networks with a spatial tree-based datapath, which significantly
complicates the spatial and temporal mapping. The conflict-avoiding bank
mapping given the networking constraints is also novel.

FPGA: The work in [36] targets PCs through fully-spatial mapping on FPGA.
However, since large PCs cannot be completely spatially mapped, their approach
is limited to only small DAGs with fewer than 500 nodes.

CGRA: Coarse-grained reconfigurable array (CGRA) architectures like HRL [18],
Plasticine [42], DySER [20], CGRA Express [38] can execute DAGs with a spatial
datapath. However, existing CGRAs suffer from several problems.

  * •

Most CGRAs either have a local register file within a PE or do not have a
register file at all. Eg., DySER does not have a register file in the PEs and
the inputs/outputs are sequentially accessed from a global register file,
which would severely limit the throughput. CGRA Express [38] uses a local
register file per PE and also has register bypass networks to dynamically fuse
operations with the same goal as the PE trees in this work. An advantage of
using PE trees is that $X$ PEs can operate with $X+1$ register read ports,
while in CGRA Express, $X$ PEs would require $2X$ ports. Furthermore,
experiments in §III-C shows that a one-to-one connection of PE and banks would
lead to frequent conflicts, revealing that local register files (similar to a
one-to-one connection) would be insufficient and more complex connectivity
between the PEs and register banks is essential for good performance.

  * •

The spatial connectivity of CGRAs is not reconfigured every cycle typically,
but is fixed for the entire execution. Given that a large DAG cannot be
entirely mapped spatially, it has to be decomposed into one recurring pattern,
which is difficult to find due to irregularity.

  * •

CGRAs normally use a 2D mesh. But, as described in §II-B, unstructured DAGs
cannot fully utilize a 2D array.

Graph analytics: In recent years, several accelerators like Fifer [31],
PolyGraph [10], Graphicionado [23], [21], with hardware support for
irregularity have been proposed for graph kernels like traversal, node
ranking, clustering, etc. In graph analytics, the ordering of nodes/edges
cannot be determined at compile time, limiting the scope of compile-time
optimizations. On the other hand, the node ordering in our target computation
DAGs is fixed based on the dependencies, which are known at compile time. This
fact is utilized extensively in this work to perform mapping of nodes to PEs,
conflict-aware bank allocation, pipeline-aware reordering, etc. This way, the
hardware is simplified by assigning several responsibilities to the compiler,
but excludes general graph analytic operations from the scope of this work.

Spare linear algebra: A growing number of hardware solutions are being
designed for sparse linear algebra, like Sparse-TPU [25], SpArch [58], SparseP
[19], etc. Some specifically target sparsity in deep learning algebra, e.g,
SNAP [57], Sticker [56], [12]. These works mainly focus on sparse matrix-
matrix or matrix-vector multiplications (SpMM and SpMV). But SpTRSV has a
different kind of parallelism compared to SpMM and SpMV due to its inductive
nature, which is discussed in detail in REVEL [55]. Put simply, in SpMV and
SpMM, outputs only depend on inputs, while in SpTRSV, outputs can depend on
the previous outputs, creating possibly long chains of producer-consumer
dependencies. REVEL [55] provides a solution for dense matrices. Sparsity
exacerbates the parallelization difficulties by introducing irregularity,
which is addressed in this work. There still remains scope for a more general
solution that does not utilize a DAG-specific (in other words, sparsity-
pattern specific) compilation developed in this work, allowing the sparsity
pattern to change with every execution.

Compilers: The greedy block generation in step 1 (§IV-A) is highly related to
the work in [5], and their advanced algorithm that can achieve optimal mapping
for a general spatial datapath. However, their experiments reported a modest
speedup of 10% over greedy heuristics, suggesting a limited opportunity for
further improvement over this work. CGRA mappers like [1], [24], [53], [3],
[32], [34], can map a DAG to generic spatial datapaths, including trees.
However, they can handle relatively small DAGs with up to 500 nodes, which are
supposed to be fully mapped to the datapath. In contrast, this work can handle
more than 100k nodes by limiting the focus to trees. Moreover, these works
usually considered a local/no register file, making them unsuitable for a
global, banked file.

Like this work, [9] also developed a DAG mapping algorithm for an architecture
with a tree of accelerator blocks (instead of PEs) [8], but the similarity
ends there. Since the targetwas a larger hardware granularity, i.e,
accelerator blocks instead of PEs, they did not have to consider the
constraints of a banked register file connected with a custom interconnection
topology, like this work.

VLIW compilers that consider partitioned register files like [16], [26], and
[37], share several similarities with the compiler of this work. Specifically,
the bottom-up greedy (BUG) algorithm [16] can compile for independent register
banks and arbitrary interconnection between the banks and PEs. Yet, it
enforces a limitation that the output of a PE cannot be connected to another
PE but can only connect to a register bank. This limits the design space to
only an array of PEs (i.e. our template with $D$=1) and excludes the PE trees
used in this work. As noted in [16], the algorithm cannot be easily modified
to ease this constraint. Our compiler, on the other hand, targets PE trees but
limits the interconnection design space to have at least one crossbar.

##  VII Conclusion

This paper presents DPU-v2, a specialized processor template designed for
energy-efficient parallel execution of irregular DAGs. The architecture is
equipped with a tree-based datapath of processing elements enabling immediate
data reuse. Instead of a multi-ported global register file, parallel register
banks with independent addressing provide the required bandwidth. The
instruction overhead of independent register addresses is eased with an
automatic writing scheme. The optimized interconnect networks between the
datapath and the register banks enable flexible routing of data required for
irregular data accesses. The architecture is made programmable with a
variable-length VLIW-like instruction set.

A targeted compiler is developed to map DAGs to DPU-v2, which maximizes the
datapath utilization, while minimizing stalls due to bank conflicts and
pipeline hazards. This way, a cohesive hardware-software co-optimization
approach is developed to address the complexities arising from irregularity
and simplify the hardware for energy efficiency.

Finally, a design space exploration is performed to identify the configuration
with minimal EDP. The optimal design achieved speedup over prior works while
consuming lower EDP. Thus, this paper demonstrates the effectiveness of
hardware-software co-optimization for irregular DAG execution, enabling
emerging energy-constrained applications.

## Acknowledgment

This work has been supported by the European Union’s European Research Council
(ERC) project Re-SENSE under grant agreement ERC-2016-STG-715037, and received
funding from the Flemish Government (AI Research Program) and KU Leuven. We
would like to thank Laura I. Galindez Olascoaga (UC Berkley) for the
insightful discussions of probabilistic circuits and benchmarks; Vidushi Dadu
and Tony Nowatzki (UC Los Angeles) for providing CPUSPU baseline
implementation; and Yitao Liang and Guy Van den Broeck (UC Los Angeles) for
providing probabilistic circuit workloads.

##  Appendix A Artifact Appendix

###  A-A Abstract

To reproduce the performance results of our processor, the following items are
open-sourced:

  * •

SystemVerilog-based microarchitectural register transfer level (RTL) model of
DPU-v2 and a testbench.

  * •

The custom compiler implemented in Python

  * •

The input DAGs used in the experiments

Workflow summary: The python-based compiler takes the DAG benchmarks as inputs
and generates binary programs for each benchmark. The SystemVerilog testbench
reads the binary programs and the data input files, and executes the RTL
simulation (with the proprietary Synopsys VCS simulator) to evaluate the
processor’s throughput. Finally, charts are plotted according to the obtained
results. All these steps are automated with a python script.

Expected results: The experiments report the breakdown of the different types
of instruction (fig. 13) and the throughput achieved by the processor (fig.
14(a)).

###  A-B Artifact check-list (meta-information)

  * •

Algorithm: A compilation algorithm is presented to map a DAG to the proposed
processor.

  * •

Compilation: The custom compiler is included with the codebase.

  * •

Data set: The target DAG workloads are included with the codebase.

  * •

Run-time environment: The code is tested on two Linux distributions (CentOS
and Ubuntu).

  * •

Hardware: The processor microarchitecture is modeled at register transfer
level (RTL) with SystemVerilog. Ths Synopsys VCS simulator is used to perform
the RTL simulation.

  * •

Execution: The execution runs for approximately 3-4 hours.

  * •

Metrics: The latency reported by the cycle accurate RTL simulation is used to
compute the throughput of the processor.

  * •

Output: The outputs of the experiments are:

    1. 1.

A plot showing the breakdown of the instruction categories as reported in fig.
13.

    2. 2.

A plot showing the throughput of the processor as reported in fig. 14(a). The
plot also shows throughput of other platforms for comparison, but they are NOT
evaluated in this codebase.

Note that the large DAGs (”Large PC”) from table I are not evaluated due to
long runtime ($>$24hours).

  * •

Experiments:  The experiments are run through a bash script.

  * •

How much disk space required (approximately)?: Less than 200MB.

  * •

How much time is needed to prepare workflow (approximately)?: 10 minutes, if
the software dependencies are already installed.

  * •

How much time is needed to complete experiments (approximately)?: 7 hours.

  * •

Publicly available?: Yes, at https://github.com/nimish15shah/DAG_Processor.

  * •

Code licenses (if publicly available)?: MIT license.

  * •

Data licenses (if publicly available)?: The input workloads (provided with the
codebase for quick experimentation) are publicly available in the UCLA StarAI
circuit model zoo (https://github.com/UCLA-StarAI/Circuit-Model-
Zoo/tree/master/psdds) and the SuiteSparse matrix collection
(https://sparse.tamu.edu/).

  * •

Archived (provide DOI)?: Yes, available on Zenodo.
https://doi.org/10.5281/zenodo.7020493

###  A-C Description

####  A-C1 How to access

The artifact is made available at
https://github.com/nimish15shah/DAG_Processor and archived on Zenodo at
https://doi.org/10.5281/zenodo.7020493. The disk space requirement is less
than 200MB.

####  A-C2 Hardware dependencies

No special hardware is required other than a general purpose CPU running a
Linux OS.

####  A-C3 Software dependencies

The following softwares are required:

  * •

The proprietary Synopsys VCS simulator for SystemVerilog simulation. More
information at https://www.synopsys.com/verification/simulation/vcs.html.

  * •

bash version 4 (or zsh).

  * •

(Optional) Anaconda. Please find the Linux installation guide at
https://docs.anaconda.com/anaconda/install/linux/#installation.

The experiments are tested on Linux distributions (CentOS and Ubuntu).

####  A-C4 Data sets

The input workloads are provided with the codebase for quick experimentation.
They are publicly available in the UCLA StarAI circuit model zoo
(https://github.com/UCLA-StarAI/Circuit-Model-Zoo/tree/master/psdds) and the
SuiteSparse matrix collection (https://sparse.tamu.edu/).

###  A-D Installation

Please run the following commands for setting up the project.

With Anaconda:

⬇

git clone git@github.com:nimish15shah/DAG_Processor.git

cd DAG_Processor

conda create –name DAGprocessor –file conda-linux-64.yml

Without Anaconda:

⬇

\pargit clone git@github.com:nimish15shah/DAG_Processor.git

cd DAG_Processor

python3 -m venv venv_DAGprocessor

./venv_DAGprocessor/bin/activate

pip install –upgrade pip

pip install -r requirements.txt

\par

###  A-E Experiment workflow

The experiments are launched with the following script.

With Anaconda (recommended):

⬇

conda activate DAGprocessor

./run.sh

Without Anaconda:

⬇

./run.sh noconda

The script performs the following steps:

  * •

The python-based compiler takes the DAG benchmarks as input and generates
binary programs for each benchmark.

  * •

The SystemVerilog testbench reads the binary programs and the data input files
generated by the compiler, and executes the RTL simulation (with the
proprietary Synopsys VCS simulator) and generates the latency log.

  * •

Finally the charts are plotted according to the data collected during the
compilation and RTL simulations.

###  A-F Evaluation and expected results

The expected results of the experiments are:

  1. 1.

A plot at
./out/plots/instruction_breakdown.pdf showing the breakdown of the instruction
categories as reported in fig. 13.

  2. 2.

A plot at ./out/plots/throughput.pdf showing the throughput of the processor
as reported in fig. 14(a). The plot also shows throughput of other platforms
for comparison, but they are NOT evaluated in this artifact.

Note 1: The large DAGs (”Large PC”) from table I are not evaluated due to
large experimental runtime ($>$24hours).

Note 2: There could be slight variations in the results in every run due to
some randomizations in the compiler.

## References

  * [1] M. Canesche, M. Menezes, W. Carvalho, F. S. Torres, P. Jamieson, J. A. Nacif, and R. Ferreira, “Traversal: A fast and adaptive graph-based placement and routing for CGRAs,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , vol. 40, no. 8, pp. 1600–1612, 2020.
  * [2] A. Capitanio, N. Dutt, and A. Nicolau, “Partitioned register files for VLIWs: A preliminary analysis of tradeoffs,” _ACM SIGMICRO Newsletter_ , vol. 23, no. 1-2, pp. 292–300, 1992.
  * [3] L. Chen and T. Mitra, “Graph minor approach for application mapping on cgras,” _ACM Transactions on Reconfigurable Technology and Systems (TRETS)_ , vol. 7, no. 3, pp. 1–25, 2014.
  * [4] Y. Choi, A. Vergari, and G. Van den Broeck, “Probabilistic circuits: A unifying framework for tractable probabilistic models,” Technical report, Tech. Rep., 2020.
  * [5] N. Clark, A. Hormati, S. Mahlke, and S. Yehia, “Scalable subgraph mapping for acyclic computation accelerators,” in _Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems_ , 2006, pp. 147–157.
  * [6] N. Clark, M. Kudlur, H. Park, S. Mahlke, and K. Flautner, “Application-specific processing on a general-purpose core via transparent instruction set customization,” in _37th international symposium on microarchitecture (MICRO-37’04)_. IEEE, 2004, pp. 30–40.
  * [7] N. T. Clark, H. Zhong, and S. A. Mahlke, “Automated custom instruction generation for domain-specific processor acceleration,” _IEEE Transactions on Computers_ , vol. 54, no. 10, pp. 1258–1270, 2005.
  * [8] J. Cong, M. A. Ghodrat, M. Gill, B. Grigorian, and G. Reinman, “Charm: A composable heterogeneous accelerator-rich microprocessor,” in _Proceedings of the 2012 ACM/IEEE international symposium on Low power electronics and design_ , 2012, pp. 379–384.
  * [9] J. Cong, H. Huang, and M. A. Ghodrat, “A scalable communication-aware compilation flow for programmable accelerators,” in _2016 21st Asia and South Pacific Design Automation Conference (ASP-DAC)_. IEEE, 2016, pp. 503–510.
  * [10] V. Dadu, S. Liu, and T. Nowatzki, “PolyGraph: exposing the value of flexibility for graph processing accelerators,” in _2021 ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA)_. IEEE, 2021, pp. 595–608.
  * [11] V. Dadu, J. Weng, S. Liu, and T. Nowatzki, “Towards general purpose acceleration by exploiting common data-dependence forms,” in _Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture_ , 2019, pp. 924–939.
  * [12] S. Dave, R. Baghdadi, T. Nowatzki, S. Avancha, A. Shrivastava, and B. Li, “Hardware acceleration of sparse and irregular tensor computations of ML models: A survey and insights,” _Proceedings of the IEEE_ , vol. 109, no. 10, pp. 1706–1752, 2021.
  * [13] T. A. Davis and Y. Hu, “The university of florida sparse matrix collection,” _ACM Transactions on Mathematical Software (TOMS)_ , vol. 38, no. 1, pp. 1:1–1:25, 2011.
  * [14] T. A. Davis, S. Rajamanickam, and W. M. Sid-Lakhdar, “A survey of direct methods for sparse linear systems,” _Acta Numerica_ , vol. 25, pp. 383–566, 2016.
  * [15] C. Delaplace, “Linear algebra algorithms for cryptography,” Ph.D. dissertation, Université Rennes 1, 2018.
  * [16] J. R. Ellis, _Bulldog: a compiler for VLSI architectures_. Mit Press, 1986.
  * [17] L. I. Galindez Olascoaga, W. Meert, N. Shah, M. Verhelst, and G. Van den Broeck, “Towards hardware-aware tractable learning of probabilistic models,” _Advances in Neural Information Processing Systems 32 (NeurIPS)_ , vol. 32, 2019.
  * [18] M. Gao and C. Kozyrakis, “HRL: Efficient and flexible reconfigurable logic for near-data processing,” in _2016 IEEE International Symposium on High Performance Computer Architecture (HPCA)_ , 2016, pp. 126–137.
  * [19] C. Giannoula, I. Fernandez, J. Gómez-Luna, N. Koziris, G. Goumas, and O. Mutlu, “SparseP: Towards efficient sparse matrix vector multiplication on real processing-in-memory systems,” _arXiv preprint arXiv:2201.05072_ , 2022.
  * [20] V. Govindaraju, C.-H. Ho, T. Nowatzki, J. Chhugani, N. Satish, K. Sankaralingam, and C. Kim, “DySER: Unifying functionality and parallelism specialization for energy-efficient computing,” _IEEE Micro_ , vol. 32, no. 5, pp. 38–51, 2012.
  * [21] C.-Y. Gui, L. Zheng, B. He, C. Liu, X.-Y. Chen, X.-F. Liao, and H. Jin, “A survey on graph processing accelerators: Challenges and opportunities,” _Journal of Computer Science and Technology_ , vol. 34, no. 2, pp. 339–371, 2019.
  * [22] A. Hagberg, P. Swart, and D. S Chult, “Exploring network structure, dynamics, and function using networkx,” Los Alamos National Lab.(LANL), Los Alamos, NM (United States), Tech. Rep., 2008.
  * [23] T. J. Ham, L. Wu, N. Sundaram, N. Satish, and M. Martonosi, “Graphicionado: A high-performance and energy-efficient accelerator for graph analytics,” in _2016 49th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)_. IEEE, 2016, pp. 1–13.
  * [24] M. Hamzeh, A. Shrivastava, and S. Vrudhula, “REGIMap: Register-aware application mapping on coarse-grained reconfigurable architectures (CGRAs),” in _Proceedings of the 50th Annual Design Automation Conference_ , 2013, pp. 1–10.
  * [25] X. He, S. Pal, A. Amarnath, S. Feng, D.-H. Park, A. Rovinski, H. Ye, Y. Chen, R. Dreslinski, and T. Mudge, “Sparse-TPU: Adapting systolic arrays for sparse matrices,” in _Proceedings of the 34th ACM International Conference on Supercomputing_ , 2020, pp. 1–12.
  * [26] S. Jang, S. Carr, P. Sweany, and D. Kuras, “A code generation framework for VLIW architectures with partitioned register banks,” in _Procs. of 3rd. Int. Conf. on Massively Parallel Computing Systems_ , vol. 4. Citeseer, 1998.
  * [27] H. Kung and C. E. Leiserson, “Systolic arrays (for vlsi),” in _Sparse Matrix Proceedings 1978_ , vol. 1. Society for industrial and applied mathematics, 1979, pp. 256–282.
  * [28] H. Kwon, A. Samajdar, and T. Krishna, “MAERI: Enabling flexible dataflow mapping over dnn accelerators via reconfigurable interconnects,” in _Proceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems_ , 2018, pp. 461–475.
  * [29] Y. Liang, J. Bekker, and G. V. den Broeck, “Learning the structure of probabilistic sentential decision diagrams,” in _Proceedings of the Thirty-Third Conference on Uncertainty in Artificial Intelligence UAI_ , 2017\.
  * [30] M. Naumov, “Parallel solution of sparse triangular linear systems in the preconditioned iterative methods on the GPU,” _NVIDIA Corp., Westford, MA, USA, Tech. Rep. NVR-2011_ , vol. 1, 2011.
  * [31] Q. M. Nguyen and D. Sanchez, “Fifer: Practical acceleration of irregular applications on reconfigurable architectures,” in _MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture_ , 2021, pp. 1064–1077.
  * [32] T. Nowatzki, N. Ardalani, K. Sankaralingam, and J. Weng, “Hybrid optimization/heuristic instruction scheduling for programmable accelerator codesign,” in _Proceedings of the 27th International Conference on Parallel Architectures and Compilation Techniques_ , 2018, pp. 1–15.
  * [33] T. Nowatzki, V. Gangadhar, and K. Sankaralingam, “Exploring the potential of heterogeneous von neumann/dataflow execution models,” in _Proceedings of the 42nd Annual International Symposium on Computer Architecture_ , 2015, pp. 298–310.
  * [34] T. Nowatzki, M. Sartin-Tarm, L. De Carli, K. Sankaralingam, C. Estan, and B. Robatmili, “A scheduling framework for spatial architectures across multiple constraint-solving theories,” _ACM Transactions on Programming Languages and Systems (TOPLAS)_ , vol. 37, no. 1, pp. 1–30, 2014.
  * [35] NVIDIA Corporation, “NVIDIA CUDA C programming guide,” 2019, version 10.1.
  * [36] M. Ober, J. Hofmann, L. Sommer, L. Weber, and A. Koch, “High-throughput multi-threaded sum-product network inference in the reconfigurable cloud,” in _2019 IEEE/ACM International Workshop on Heterogeneous High-performance Reconfigurable Computing (H2RC)_ , 2019, pp. 26–33.
  * [37] E. Ozer, S. Banerjia, and T. M. Conte, “Unified assign and schedule: A new approach to scheduling for clustered register file microarchitectures,” in _Proceedings. 31st Annual ACM/IEEE International Symposium on Microarchitecture_. IEEE, 1998, pp. 308–315.
  * [38] Y. Park, H. Park, and S. Mahlke, “CGRA express: accelerating execution using dynamic operation fusion,” in _Proceedings of the 2009 international conference on Compilers, architecture, and synthesis for embedded systems_ , 2009, pp. 271–280.
  * [39] A. Picciau, G. E. Inggs, J. Wickerson, E. C. Kerrigan, and G. A. Constantinides, “Balancing locality and concurrency: Solving sparse triangular systems on GPUs,” in _2016 IEEE 23rd International Conference on High Performance Computing (HiPC)_. IEEE, 2016, pp. 183–192.
  * [40] L. Polok, “Accelerated sparse matrix operations in nonlinear least squares solvers,” Ph.D. dissertation, Ph. D. Thesis at Faculty of Information Technology, Brno University of …, 2016.
  * [41] H. Poon and P. Domingos, “Sum-product networks: A new deep architecture,” in _2011 IEEE International Conference on Computer Vision Workshops (ICCV Workshops)_. IEEE, 2011, pp. 689–690.
  * [42] R. Prabhakar, Y. Zhang, D. Koeplinger, M. Feldman, T. Zhao, S. Hadjis, A. Pedram, C. Kozyrakis, and K. Olukotun, “Plasticine: A reconfigurable architecture for parallel patterns,” in _2017 ACM/IEEE 44th Annual International Symposium on Computer Architecture (ISCA)_ , 2017, pp. 389–402.
  * [43] A. Rucker, M. Vilim, T. Zhao, Y. Zhang, R. Prabhakar, and K. Olukotun, “Capstan: A vector RDA for sparsity,” in _MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture_ , 2021, pp. 1022–1035.
  * [44] N. Shah, W. Meert, and M. Verhelst, “Graphopt: constrained optimization-based parallelization of irregular graphs,” _arXiv preprint arXiv:2105.01976_ , 2021.
  * [45] N. Shah, L. I. G. Olascoaga, S. Zhao, W. Meert, and M. Verhelst, “9.4 PIU: A 248gops/w stream-based processor for irregular probabilistic inference networks using precision-scalable posit arithmetic in 28nm,” in _2021 IEEE International Solid-State Circuits Conference (ISSCC)_ , vol. 64. IEEE, 2021, pp. 150–152.
  * [46] ——, “DPU: Dag processing unit for irregular graphs with precision-scalable posit arithmetic in 28 nm,” _IEEE Journal of Solid-State Circuits_ , 2021.
  * [47] A. Sharifian, S. Kumar, A. Guha, and A. Shriraman, “Chainsaw: Von-neumann accelerators to leverage fused instruction chains,” in _2016 49th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)_. IEEE, 2016, pp. 1–14.
  * [48] Y. Shen, A. Choi, and A. Darwiche, “Tractable operations for arithmetic circuits of probabilistic models,” _Advances in Neural Information Processing Systems_ , vol. 29, 2016.
  * [49] K. Stelzner, R. Peharz, and K. Kersting, “Faster attend-infer-repeat with tractable probabilistic models,” in _Proceedings of the 36th International Conference on Machine Learning, ICML_ , vol. 97, 2019, pp. 5966–5975.
  * [50] M. B. Taylor, W. Lee, S. Amarasinghe, and A. Agarwal, “Scalar operand networks: On-chip interconnect for ILP in partitioned architectures,” in _The Ninth International Symposium on High-Performance Computer Architecture, 2003. HPCA-9 2003. Proceedings._ IEEE, 2003, pp. 341–353.
  * [51] N. Thoma, Z. Yu, F. Ventola, and K. Kersting, “Recowns: Probabilistic circuits for trustworthy time series forecasting,” _arXiv preprint arXiv:2106.04148_ , 2021.
  * [52] G. van den Braak, “Improving GPU performance: reducing memory conflicts and latency,” Ph.D. dissertation, Technische Universiteit Eindhoven, 2015.
  * [53] M. J. Walker and J. H. Anderson, “Generic connectivity-based CGRA mapping via integer linear programming,” in _2019 IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)_. IEEE, 2019, pp. 65–73.
  * [54] X. Wang and E. Serpedin, “An overview on the applications of matrix theory in wireless communications and signal processing,” _Algorithms_ , vol. 9, no. 4, p. 68, 2016.
  * [55] J. Weng, S. Liu, Z. Wang, V. Dadu, and T. Nowatzki, “A hybrid systolic-dataflow architecture for inductive matrix algorithms,” in _2020 IEEE International Symposium on High Performance Computer Architecture (HPCA)_. IEEE, 2020, pp. 703–716.
  * [56] Z. Yuan, Y. Liu, J. Yue, Y. Yang, J. Wang, X. Feng, J. Zhao, X. Li, and H. Yang, “STICKER: An energy-efficient multi-sparsity compatible accelerator for convolutional neural networks in 65-nm cmos,” _IEEE Journal of Solid-State Circuits_ , vol. 55, no. 2, pp. 465–477, 2020.
  * [57] J.-F. Zhang, C.-E. Lee, C. Liu, Y. S. Shao, S. W. Keckler, and Z. Zhang, “Snap: An efficient sparse neural acceleration processor for unstructured sparse deep neural network inference,” _IEEE Journal of Solid-State Circuits_ , vol. 56, no. 2, pp. 636–647, 2021.
  * [58] Z. Zhang, H. Wang, S. Han, and W. J. Dally, “Sparch: Efficient architecture for sparse matrix multiplication,” in _2020 IEEE International Symposium on High Performance Computer Architecture (HPCA)_. IEEE, 2020, pp. 261–274.
  * [59] K. Zheng and A. Pronobis, “From pixels to buildings: End-to-end probabilistic deep networks for large-scale semantic mapping,” in _2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2019, pp. 3511–3518.