[2]footnote

# A variant of Baer’s theorem

Pasha Zusmanovich  University of Ostrava, Czech Republic
<EMAIL_ADDRESS>
(Date: First written September 15, 2022; last minor revision March 26, 2023)

###### Abstract.

We provide a variant of Baer’s theorem about isomorphism of endomorphism rings
of vector spaces over division rings, where the full endomorphism rings are
replaced by some subrings of finitary maps.

###### Key words and phrases:

Baer’s theorem; endomorphism ring; finitary linear map

###### 2020 Mathematics Subject Classification:

16S50

Rocky Mountain J. Math., to appear

Under Baer’s theorem we mean the following result, formulated for the first
time as Theorem 1 in [Baer, Chapter V, §4]: if $V$ and $W$ are two (say,
right) vector spaces over division rings $D$ and $F$ respectively, then the
isomorphism of their endomorphism rings $\operatorname{End}_{D}(V)$ and
$\operatorname{End}_{F}(W)$ implies a semilinear isomorphism of $V$ and $W$.
Baer’s original proof uses properties of idempotents in the endomorphism ring;
for a streamlined and modern exposition see [KTT, Theorem 4.1]. Another proof
offered in [W, Theorem 8.1] (Ph.D. thesis under Baer) uses Jacobson’s density
theorem. In [R] and [Bal] Baer’s theorem is extended to the cases of super
vector spaces and graded vector spaces over super or graded division rings,
respectively. Later on Baer’s theorem was also extended to modules over large
classes of abelian groups (the so-called Baer–Kaplansky theorem), see [KTT]
and references therein for a survey.

If $V$ is infinite-dimensional over $D$, the ring $\operatorname{End}_{D}(V)$
is huge, and one may wonder whether in the formulation of Baer’s theorem it
can be replaced by something smaller. Somewhat anachronistically, this was
done, with small variations, already before Baer, in 1940s, in the works of
Dieudonné, Jacobson, and others, see [J2, Chapter IV, §11] or [J1, Chapter IX,
§11, Theorem 7]: the condition involves isomorphism of rings of _finitary_
linear maps, and the proof uses again Jacobson’s density theorem. The origin
of these works seems to be in similar results established earlier in the
analytic setting, for rings of bounded operators on Banach or Hilbert spaces,
or rings of continuous operators on normed spaces, by Eidelheit, Mackey, and
others; see historical references at [J2, p. 94].

Here we offer another variation on this topic. We retain a relatively narrow
context of vector spaces over division rings, and – similarly to Jacobson and
others – instead the full endomorphism ring, consider its subrings of finitary
linear maps. However, the rings we consider are, in the infinite-dimensional
case, rather “small”, significantly “smaller” even than the ring of all
finitary maps, so this can be viewed as a substantial extension of the
original Baer theorem. Moreover, our rings are, generally, not dense, thus all
the previous methods of proofs of Baer’s theorem and its variants, based on
consideration of idempotents or other structural gadgets from ring theory, or
on Jacobson’s density theorem, do not work. Instead, we use an elementary
linear-algebraic technique of “decomposing” conditions imposed on linear maps
on tensor products, and consideration of traces.

All rings in this note are assumed to be associative. For the standard linear
algebra over a (noncommutative) division ring, we refer to [Baer] or [J1].
Some notation and terminology is also borrowed from [CO] (where things are
treated in the Lie-algebraic context).

Let $D$ be a division ring with unit $1$, and $V$ a right vector space over
$D$; then the dual $V^{*}$ is a left vector space over $D$. A linear map is
called _finitary_ if its kernel has finite codimension (or, what is
equivalent, its image has finite dimension). Finitary maps have traces,
defined in the usual manner. The set of all finitary linear maps forms a
subring $\operatorname{FEnd}_{D}(V)$ of the endomorphism ring
$\operatorname{End}_{D}(V)$, and is linearly spanned by _infinitesimal
transvections_ $t_{v,f}:V\to V$, defined as $t_{v,f}(u)=vf(u)$, where $v,u\in
V$ and $f\in V^{*}$ (infinitesimal transvections are exactly linear maps whose
image is one-dimensional). The trace of an infinitesimal transvection is
determined by the formula $\operatorname{Tr}(t_{v,f})=f(v)$.

The ring $\operatorname{FEnd}_{D}(V)$ is isomorphic to the ring
$V\otimes_{D}V^{*}$, with multiplication given by

(1) $(v\otimes f)\cdot(u\otimes g)=vf(u)\otimes g,$

where $v,u\in V$, $f,g\in V^{*}$. The isomorphism is given by sending the
infinitesimal transvection $t_{v,f}$ to the decomposable tensor $v\otimes f$.

Now let $\Pi$ be a $D$-subspace of $V^{*}$. Then $V\otimes_{D}\Pi$ is still
closed with respect to the multiplication (1), and hence forms a subring of
$V\otimes_{D}V^{*}$. Going back to $\operatorname{End}_{D}(V)$ and its
subrings, the ring $V\otimes_{D}\Pi$ is isomorphic to the subring
$\operatorname{FEnd}_{D}(V,\Pi)$ of $\operatorname{FEnd}_{D}(V)$ generated by
all infinitesimal transvections $t_{v,f}$ with $v\in V$ and $f\in\Pi$.

Note that all the just mentioned rings, $\operatorname{End}_{D}(V)$,
$\operatorname{FEnd}_{D}(V)$, and $\operatorname{FEnd}_{D}(V,\Pi)$, are also
right vector spaces over $D$, and hence have a structure of a right
$D$-algebra.

######  Theorem.

Let $V,W$ be right vector spaces over a division ring $D$, $\Pi$ a nonzero
finite-dimensional subspace of $V^{*}$, $\Gamma$ a finite-dimensional subspace
of $W^{*}$, and
$\Phi:\operatorname{FEnd}_{D}(V,\Pi)\to\operatorname{FEnd}_{D}(W,\Gamma)$ an
isomorphism of $D$-algebras. Then there is an isomorphism of $D$-vector spaces
$\alpha:V\to W$ such that

(2) $\Phi(f)=\alpha\circ f\circ\alpha^{-1}$

for any $f\in\operatorname{FEnd}_{D}(V,\Pi)$.

###### Proof.

Write the rings $\operatorname{FEnd}_{D}(V,\Pi)$ and
$\operatorname{FEnd}_{D}(W,\Gamma)$ in the isomorphic form as the tensor
products $V\otimes_{D}\Pi$ and $W\otimes_{D}\Gamma$ as above, and, by abuse of
notation, denote by the same symbol $\Phi$ the isomorphism of $D$-algebras
$\Phi:V\otimes_{D}\Pi\to W\otimes_{D}\Gamma$. Due to finite-dimensionality of
$\Pi$, we have isomorphism of vector spaces over $D$:

$\operatorname{Hom}_{D}(V\otimes_{D}\Pi,W\otimes_{D}\Gamma)\simeq\operatorname{Hom}_{D}(V,W)\otimes_{D}\operatorname{Hom}_{D}(\Pi,\Gamma),$

and hence we can write $\Phi$ in the form

(3) $\Phi(v\otimes f)=\sum_{i\in I}\alpha_{i}(v)\otimes\beta_{i}(f),$

where $\alpha_{i}:V\to W$ and $\beta_{i}:\Pi\to\Gamma$ are two linearly
independent families of $D$-linear maps, indexed by a finite set $I$. The
condition that $\Phi$ is a homomorphism, written for a pair of decomposable
tensors $v\otimes f$ and $u\otimes g$, where $v,u\in V,f,g\in\Pi$, is
equivalent to

$\sum_{i\in I}\Big{(}\alpha_{i}(v)f(u)-\sum_{j\in
I}\alpha_{j}(v)\beta_{j}(f)(\alpha_{i}(u))\Big{)}\otimes\beta_{i}(g)=0.$

Since the family $\\{\beta_{i}\\}_{i\in I}$ is linearly independent over $D$,
each first tensor factor in the external sum vanishes, i.e.,

$\alpha_{i}(v)f(u)-\sum_{j\in I}\alpha_{j}(v)\beta_{j}(f)(\alpha_{i}(u))=0$

for any $i\in I$, $v,u\in V$, and $f\in\Pi$. This can be rewritten as

$\alpha_{i}(v)\Big{(}f(u)-\beta_{i}(f)(\alpha_{i}(u))\Big{)}-\sum_{\begin{subarray}{c}j\in
I\\\ j\neq i\end{subarray}}\alpha_{j}(v)\beta_{j}(f)(\alpha_{i}(u))=0.$

Since the family $\\{\alpha_{i}\\}_{i\in I}$ is linearly independent over $D$,
each coefficient from $D$ in the last sum vanishes; in particular,

(4) $\beta_{i}(f)(\alpha_{i}(u))=f(u)$

for any $u\in V,f\in\Pi$, and $i\in I$.

This implies

$\operatorname{Tr}\Big{(}\Phi(u\otimes
f)\Big{)}=\operatorname{Tr}\Big{(}\sum_{i\in
I}\alpha_{i}(u)\otimes\beta_{i}(f)\Big{)}=\sum_{i\in
I}\operatorname{Tr}\Big{(}\alpha_{i}(u)\otimes\beta_{i}(f)\Big{)}\\\
=\sum_{i\in I}\beta_{i}(f)(\alpha_{i}(u))=\sum_{i\in
I}f(u)=|I|f(u)=|I|\operatorname{Tr}(u\otimes f).$

As the ring $V\otimes_{D}\Pi$ is linearly spanned by decomposable tensors, we
have

(5) $\operatorname{Tr}(\Phi(\xi))=|I|\operatorname{Tr}(\xi)$

for any $\xi\in V\otimes_{D}\Pi$.

Now consider the inverse isomorphism $\Phi^{-1}:W\otimes_{D}\Gamma\to
V\otimes_{D}\Pi$, with decomposition similar to (3) with the index set $J$. By
the same reasoning as in the case of $\Phi$, we have

(6) $\operatorname{Tr}(\Phi^{-1}(\eta))=|J|\operatorname{Tr}(\eta)$

for any $\eta\in W\otimes_{D}\Gamma$. Combining (5) and (6), we have

(7) $\operatorname{Tr}(\xi)=|I||J|\operatorname{Tr}(\xi)$

for any $\xi\in V\otimes_{D}\Pi$.

Since for any nonzero $f\in V^{*}$ there is $v\in V$ such that $f(v)\neq 0$
(actually, we can choose $f(v)$ to be equal to $1$),
$\operatorname{FEnd}_{D}(V,\Pi)$ always contains elements of nonzero trace***
This is a trivial, albeit a crucial point in our reasoning. Compare with the
condition of so-called totality in [J1, Chapter IX, §11, Theorem 7], which, in
our notation, amounts to saying, in a sense, a dual thing: for any nonzero
$v\in V$ there is $f\in\Pi$ such that $f(v)\neq 0$. The latter condition is
equivalent to the density of rings under consideration, and allows to use
Jacobson’s density theorem.  . Picking such an element $\xi$ in (7), we have
$|I|=|J|=1$, i.e., $\Phi$ preserves traces and can be represented as a
decomposable linear map: $\Phi=\alpha\otimes\beta$ for some $\alpha:V\to W$
and $\beta:\Pi\to\Gamma$. The system of equalities (4) reduces to the single
equality

(8) $\beta(f)\circ\alpha=f$

for any $f\in\Pi$. As $\Phi$ is invertible, $\alpha$ and $\beta$ are
invertible with $\Phi^{-1}=\alpha^{-1}\otimes\beta^{-1}$, so (8) can be
rewritten as $\beta(f)=f\circ\alpha^{-1}$, and hence $\Phi(v\otimes
f)=\alpha(v)\otimes(f\circ\alpha^{-1})$. Rewriting the last equality in terms
of $\operatorname{FEnd}_{D}(V,\Pi)$ for an infinitesimal transvection
$t_{v,f}$, and expanding by linearity, we get (2). ∎

A couple of final remarks concerning possible extensions of the theorem:

  1. (i)

We require the base ring $D$ to be a division ring in order to ensure that all
$D$-modules are free. We can merely require that all the modules appearing in
the formulation of the theorem, i.e., $V$, $W$, $\Pi$, $\Gamma$, as well as
all the modules appearing in the course of the proof, are free, without
imposing any conditions on $D$, but this will just lead to a cumbersome
formulation without changing the essence of the things.

  2. (ii)

The theorem can be easily extended to the graded case (thus providing a
“finitary” analog of results from [R] and [Bal]), with essentially the same
proof which will keep track of the maps on each graded component separately.
This is left as an exercise to the reader.

Thanks are due to the anonymous referee for indicating an erroneous remark in
the previous version of the manuscript.

## References

  * [Baer] R. Baer, _Linear Algebra and Projective Geometry_ , Acad. Press, 1952.
  * [Bal] I.N. Balaba, _Isomorphisms of graded rings of linear transformations of graded vector spaces_ , Chebyshevskii Sbornik 6 (2005), no.4, 7–24 (in Russian).
  * [CO] H. Cuypers, M. Oostendorp, _A geometric characterization of the finitary special linear and unitary Lie algebras_ , arXiv:2105.11967.
  * [J1] N. Jacobson, _Lectures in Abstract Algebra. II. Linear Algebra_ , Von Nostrand, 1953; reprinted by Springer-Verlag, 1975.
  * [J2] by same author, _Structure of Rings_ , 2nd ed., AMS, 1964.
  * [KTT] P.A. Krylov, A.A. Tuganbaev, A.V. Tsarev, _Around the Baer–Kaplansky theorem_ , J. Math. Sci. 256 (2021), no.3, 278–298.
  * [R] M.L. Racine, _Primitive superalgebras with superinvolution_ , J. Algebra 206 (1998), no.2, 588–614.
  * [W] K.G. Wolfson, _An ideal-theoretic characterization of the ring of all linear transformations_ , Amer. J. Math. 75 (1953), no.2, 358–386.


# Massive Data-Centric Parallelism in the Chiplet Era

Marcelo Orenes-Vera, Esin Tureci, David Wentzlaff and Margaret Martonosi
Princeton University, New Jersey, USA
{movera, esin.tureci, wentzlaf<EMAIL_ADDRESS>
###### Abstract

Traditionally, massively parallel applications have been executed on
distributed systems, where computing nodes are distant enough that the
parallelization schemes must minimize data communication and synchronization
to achieve scalability. Mapping communication-intensive workloads to
distributed systems require complicated problem partitioning and dataset pre-
processing. With the current AI-driven trend of having thousands of
interconnected processors per chip, there is an opportunity to re-think these
communication-bottlenecked workloads. This bottleneck often arises from the
data structure traversals, which cause irregular memory access patterns and
poor cache locality.

Recent works have introduced task-based parallelization schemes to accelerate
graph traversal and other sparse workloads. Data structure traversals are
split into tasks, which are then pipelined across processing units (PUs).
Dalorex demonstrated the highest scalability (up to thousands of PUs on a
single chip) by having the entire dataset on-chip, scattered across PUs, and
executing the tasks at the PU where the data is local. However, it also raised
many questions on how to scale to larger datasets when all the memory is on-
chip, and at what cost.

To address these challenges, we propose a scalable architecture composed of a
grid of Data-Centric Reconfigurable Array (DCRA) chiplets. Package-time
reconfiguration enables creating chip products that optimize for different
target metrics, such as time-to-solution, energy, or cost, while software
reconfigurations avoid network saturation when scaling to millions of PUs
across many chip packages. We evaluate six applications and four datasets,
with several configurations and memory technologies to provide a detailed
analysis of the performance, power and cost of data-local execution at scale.
Our parallelization of Breadth-First-Search with RMAT-26 across a million
PUs—the largest of the literature—reaches 3323 GTEPS.

##  I Introduction

Figure 1:  Two configurations of the DCRA architecture: (top) two packages on
a board, each featuring only DCRA chiplet dies, which optimizes for time-to-
solution as it aims to parallelize a dataset much as possible (lower data
footprint per die); and (bottom) a single package with DCRA dies and stacked
DRAM for extended memory capacity, optimizes for performance-per-watt/$.
(Insights based on evaluation results.)

In the last decade, we have seen AI workloads to scale linearly on massive
manycore systems [12, 26, 82, 34, 14] via dataflow computation. However, due
to the ever increasing size of AI models, computationally-intensive
applications such as Neural Networks are moving towards sparse data structures
like graphs, which present communication challenges [71].

Recently, several works have proposed task-based parallelization schemes that
accelerate graph and sparse data structure traversal by splitting the program
at irregular memory access [56, 17, 60], offering a promising path for
parallelizing these communication- and data-intensive applications. Dalorex
[60] proposes a data-local execution model that minimizes data movement by
operating data where it resides, which shows scaling up to thousands of PUs on
a single chip.

In Dalorex, data arrays are scattered across the processing tiles as equal-
sized chunks. A tile comprises a PU, a router, and SRAM. Each PU can only
access its fraction of the dataset, i.e., there is a single data owner.
Because of that, a program must be split at each indirect memory access to
create a tasks executed at the tiles containing the data to be operated on.

While Dalorex introduced a promising new execution model for parallelizing
sparse applications, it has several limitations: (1) Due to the irregular
nature of the sparse data structure, the destination tile may be anywhere on
the tile grid. As a result, as the number of tiles in the system increases, so
does the average distance of communication for task invocations, adding
network contention. (2) Because the data footprint per tile shrinks when
parallelizing across more tiles, the likelihood that a tile will own much
hotter data than others increases. The fact that an operation must be done by
the data owner leads to a growing work imbalance when scaling out. (3) Dalorex
assumes a homogeneous, arbitrarily large grid of processing tiles. It does not
address how to fabricate such large tile grid in a cost-effective manner, nor
how to communicate fine-grain task messages efficiently across multiple chips.

Our work overcomes the above limitations by: (a) introducing proxy regions of
tiles with copies of data to reduce task invocation distance and work
imbalance; (b) designing a scalable system where chip packages are composed of
an arbitrary number of Data-Centric Reconfigurable Array (DRCA) chiplets; and
(c) providing a detailed study of tradeoffs in cost, performance and energy-
efficiency of packaging-time design decisions. We evaluate strong scaling
performance when parallelizing sparse applications with up to one million
processors without resorting to dataset preprocessing or partitioning.

_Proxy Regions:_ To reduce long-distance communication, DCRA divides the tile
grid (configured to run a program) into subgrids. In each subgrid, proxy tiles
are assigned to data that resides outside the subgrid. Tasks requiring long-
distance communication are first sent to a regional proxy tile. This results
in filtering out unnecessary requests to the data owner and significantly
reduces the average communication distance of task invocations (see Section
V). This approach also improves work balance as a tile that owns very hot data
does not need to process all the tasks that access it. We demonstrate the
benefits of this for the task responsible for vertex-update in graph
applications and the reduction phase of sparse linear algebra and histogram.

_Reconfigurable Architecture:_ While Dalorex studied that performance and
energy efficiency of task-based execution with different granularity of SRAM
per tile, a specific size is decided for tapeout. When we factor in the
fabrication cost of such data-local architecture, we found that this
granularity also affects key metrics of throughput or energy efficiency per
dollar. Because fabricating different silicon masks for different target
metrics is prohibitively expensive, we propose composable architecture where
crucial decisions like on-chip memory capacity or off-chip bandwidth are taken
post-silicon (during chip packaging). Figure 1 depicts two packaging
alternatives where the same DCRA dies (also referred to as chiplets) are
integrated to create different chip products, each optimized for a different
metric. A DCRA die may be attached at packaging time to a DRAM device. This
effectively increases the capacity of a tile’s local memory since the DRAM
storage is logically partitioned across the tiles of the adjacent DCRA die.

The technical contributions of this paper are:

  * •

Software-reconfigurable proxy regions that removes the limitation of data-
local architectures that a data operation can only be done by data owner. This
reduces distant communication of tasks and improves work balance.

  * •

A scalable architecture where chip design decisions such as on-chip memory,
number of PUs, network topology and off-chip bandwidth are taken post-silicon.

  * •

A practical path for manufacturing chip packages by composing DCRA dies. The
first design that proposes interleaving any number of compute and DRAM
chiplets.

  * •

A detailed study of tradeoffs in cost, performance and energy-efficiency of
several package designs.

We evaluate DCRA and demonstrate that:

  * •

The proposed proxy regions reduces network traffic by 1.8$\times$ over a prior
data-local architecture [60].

  * •

Optimized task scheduling and buffering can improve the overall system’s
throughput up to $5\times$.

  * •

Different packaging options of DCRA leads to different optimal design points
for key metrics in HPC, such as energy-efficiency/cost or throughput.

  * •

It is possible to construct a data-centric execution model exhibiting strong
scaling performance upto a million PUs.

  * •

Our BFS parallelization is 3.8$\times$ faster than the most performant entry
of the Graph500 list for RMAT-26.

##  II Background and Motivation

Graph and sparse linear algebra applications do not exhibit spatial nor
temporal locality, resulting in poor cache behavior and intense traffic in the
memory hierarchy [48].

Prior work aiming to accelerate these workloads mitigate memory latency via
decoupling, prefetching, and hardware pipelining techniques [81, 59, 27, 70,
62, 1, 55, 56, 17]. Fifer [56] and Polygraph [17] also increase utilization
through spatiotemporal parallelization. However, all of these works store the
dataset on off-chip DRAM; thus, their scalability is limited by the network
and memory bandwidth. Tesseract [3] and GraphQ [96] tackle this problem via
processing-in-memory. However, their proposed integration of PUs on the logic
layer of a memory cube [67] is less scalable than the manycore integration
proposed by Dalorex [60].

Section II-A reviews the latest manycore architectures with a focus on chip
manufacturing. Section II-B details the data-local execution model of Dalorex,
since this paper builds on top of it to improve work balance and network
contention, as well as to design a more practical system integration.

TABLE I: Post-silicon decidable memory capacity, # of processing elements, network topology per chip package, and whether the processing elements can execute Instructions. Reconfigurable | Memory | #Processing | Configurable | Software ISA
---|---|---|---|---
Aspects / | Capacity | Elements | Network | Programmable
Prior Work | on package | on package | Topology | Processors
Tesseract [3] | ✓ | ✗ | ✗ | ✓
GraphQ [96] | ✓ | ✗ | ✗ | ✓
Fifer [21] | ✓ | ✗ | ✗ | ✗
Dalorex [60] | ✗ | ✗ | ✗ | ✓
PolyGraph [17] | ✓ | ✗ | ✗ | ✗
Piton+Maple [7, 59] | ✗ | ✗ | ✗ | ✓
ESP [11, 24] | ✗ | ✗ | ✗ | ✓
Manticore [92] | ✓ | ✗ | ✗ | ✓
Graphcore [37] | ✗ | ✗ | ✓ | ✓
Sambanova [20] | ✓ | ✓ | ✓ | ✗
Cerebras [12] | ✗ | ✗ | ✓ | ✓
Groq [26] | ✗ | ✗ | ✗ | ✓
Tesla Dojo [26] | ✓ | ✓ | ✗ | ✓
Esperanto [21] | ✗ | ✗ | ✗ | ✓
Google TPU [34] | ✓ | ✗ | ✓ | ✗
Nvidia A100 [14] | ✓ | ✗ | ✗ | ✓
DCRA | ✓ | ✓ | ✓ | ✓

###  II-A Modern Manycore Systems and Chip Fabrication Cost

In recent years, the widespread demand for large deep-learning models has
accelerated the development of manycore and dataflow systems that can
massively parallelize compute-intensive workloads. Although the demand for
graph and sparse linear algebra workloads is growing, we have not seen systems
exhibiting as high strong scaling performance as dense systems. This is due to
the irregularity of the data-access patterns and the high memory-footprint-to-
compute ratio.

Table I shows a selection of the manycore systems published over the last five
years, where the upper ones focus on sparse workloads and the rest focus on
AI. While some of these large manycores have good attributes for sparse data
processing (large on-chip SRAM capacity [60, 12, 26, 37, 82] or on-package
DRAM [14, 20, 34, 92, 3]), the ratio of memory capacity and PUs is optimized
for dense computation, and the interconnect is designed for dataflow
communication. For our work, instead of designing a manycore architecture with
a memory-to-PU ratio and network optimized for sparse data, we propose a
chiplet architecture where these can be configured at the packaging time.

Big players in the semiconductor industry have moved towards having multiple
dies in a chip package [44, 54, 25, 4, 80] to reduce fabrication cost and
enable reusing components across different products. From the silicon
manufacturing perspective, the Non-Recurring-Engineering cost (NRE) of a wafer
mask is so high with respect to the silicon wafer itself that the cost per
wafer is 18$\times$ larger when manufacturing 100 wafers, instead of 100,000
[33]. Since the volume of silicon production of each chip architecture
generation is not as high in the HPC market than in the consumer electronic
market, we argue that mass fabrication of a chiplet that can serve as a
building block for scalable architectures is a valuable proposition. That is
why we design a unique chiplet, which can be fabricated in high volume to
amortize NRE costs, and then integrated into a Multi-Chip Module (MCM) package
with a smaller or larger grid of dies. As depicted in Figure 1, our design
optionally integrates DRAM dies between columns of DCRA dies (and not just on
the borders as current designs).

###  II-B The Data-Local Execution Model

In our task-based model, the original program is split into tasks that are
executed at the tile co-located with the memory region that the task operates
on. A task with dependent tasks can spawn them by injecting inputs for each
task in the output queue (OQ), which drains into a logical network channel
(one per task type). The entire program is executed as a sequence of tasks,
with no concept of execution threads (no main task). The parallelization level
is determined by the number of tiles with tasks ready to execute, i.e.,
waiting on an input queue (IQ). There is one IQ per task type. An IQ is
populated with invocation parameters created by either a prior task executed
in the local tile or by incoming task messages at the network channels. While
some spawned tasks are likely to be in the nearby tiles due to data placement
policy, for others, the destination may be anywhere at random in the tile
grid. As the size of the grid increases, so would the average number of router
hops of a task invocation.

_Tile Grid and Network Routing:_ The grid’s size, hence the number of tiles a
program is to run on, is determined by the user at compilation time. The
logical tile ID is set by the microcode when a workload is selected to run on
a grid, and it is used for XY routing. Since the dataset is statically
partitioned across the tiles on the grid, and the first parameter of a task
message is a global index to a data array, this index is used to route the
message, avoiding message headers altogether. Based on the size of the array
associated with each logical NoC for routing purposes, the router selects the
bits that indicate destination tile ID.

_Task Prioritization:_ In Dalorex, work efficiency and PU utilization highly
depend on the order of task executions. In order to make task invocations non-
blocking and non-interrupting, the inputs for tasks arrive at a tile’s task-
specific queues through a unit called Task Scheduling Unit (TSU). TSU’s main
role is to determine the order of execution of tasks based on occupancy of
queues. Priority is given to tasks whose IQ is highly populated, or OQ is
empty. This allows the tile to sense the network pressure and execute tasks
that will relieve pressure when it is high (IQs are full) or increase when it
is low (OQs are rarely pushing).

DCRA has reconfigurable queue sizes, and we analyze the impact of queue sizes
on performance for different applications in Section V-A. Section V-B also
shows how our proxy regions reduce the excessive traffic that appears with
large tile grids.

##  III DCRA: A Reconfigurable Tiled Architecture

In this section, we describe how DCRA overcomes the network scalability
challenges through its _software reconfigurable_ mechanism, such as proxy
regions, queues, scheduling, and caches. We also introduce our _package-time
reconfigurable_ design and provide a thorough analysis of cost versus
performance of various manufacturing options.

###  III-A Reducing Network Contention by using Proxy Regions

In DCRA, dataset arrays are scattered as equal-sized chunks to tiles, where
each tile _owns_ a chunk of each data array, similar to Dalorex. In addition,
DCRA introduces proxy ownership for tiles other than the owner by temporarily
storing some remote data. We first define _proxy regions_ by subdividing the
tile grid. We distribute the proxy ownership for a select data array across
the tiles of each proxy region such that the most recent updates coming from
within region can be stored inside the local proxy tile before being sent to
the true owner. The purpose of proxy regions is twofold: it reduces network
contention by reducing the average number of hops between task invocations and
smooths out workload imbalance by allowing tiles other than the data owner to
execute tasks. Figure 2 explains how proxy regions are configured in software
and depicts how regional tiles executing proxy tasks reduce long-distance
communication.

Applicability: Each proxy region is responsible for the entirety of a dataset
array. Any task in the data-local execution model can have a proxy task.
However, it is more beneficial to have proxy for tasks whose owner tile can be
anywhere in the tile grid. This is the case of the vertex update in graph
applications and the reduction phase of sparse linear algebra and histogram,
which we evaluate in Section V. Proxy tasks could be applied to read-only
data, as well as for modifiable arrays. For the latter, the proxy updates need
to be propagated to the owner at some moment.

Proxy Coherence: Parallel applications often require atomic updates to array
elements because any interleaving of parallel executions can occur, including
those operating on stale data. This is the case for the Bulk-Synchronous
Parallel (BSP) model for graph applications, where the updates must only be
made visible at the end of each epoch (ending with a barrier). Moreover, in
BSP and most parallel formulations, the atomic updates are commutative, so the
order of updates does not matter. We leverage these properties to reduce the
number of tasks executed on the owner tile. The reduction is twofold: updates
are not always successful (e.g., minimization in SSSP example), and several
updates can be merged before being sent to the owner. In our design, proxy
updates are propagated to the owner as either write-through (every time the
value changes) or write-back (when proxy data gets invalidated). These
policies are independent of the fact that proxy data can be cached (Section
III-C), although caching influences how often the data gets invalidated.

Application-specific Proxy configuration: In this paper, we evaluate one
application (Pagerank) following the BSP model, for which updates are
propagated to the owner at the end of each epoch. This is done by invalidating
the write-back proxy and giving all elements a default value. A similar
strategy is used for Histogram and SPMV, whose additive updates only need to
be accumulated at the end of the execution. For the SSSP example shown in
Figure 2 and the other applications described in Section IV, the code
explicitly performs write-through updates. This is because our SSSP
implementation does not use barriers between epochs; thus, updates should
propagate quickly to avoid stale data.

Figure 2:  Software configuration of proxy regions and flow of tasks for
single-source shortest path (SSSP). Based on the number of configured proxy
regions $P$, the grid is divided into $P$ subgrids, where each region is
responsible for a copy of a data array. Each tile _is a proxy for_ a $P$
chunks of the data array (P_DIST). Contrary to Dalorex, T2 does not invoke T3
directly, but instead, its output queue (OQ2) is configured to route to the
corresponding proxy tile within the same subgrid. The data owner tile is
calculated as neigh_id $/$ vertices_per_chunk, which is tile 53 (y=6,x=5) in
the code example. When a channel is configured as proxy, the proxy tile is
calculated doing modulo with the dimensions of the proxy. The red arrow shows
an invocation of T3’ (the proxy task) for which proxy value was smaller than
the received one (new_dist); thus, no message is sent to the owner. The blue
arrows show a path for which the proxy value was not minimal, so a T3
invocation is sent to the owner to determine the new minimal value.

###  III-B Software Configurable Queues to Optimize Throughput

DCRA offers more software-reconfigurable features that are tuned for different
applications and tasks (Table II). This section describes configurations for
task scheduling, queue sizes, NoCs, SRAM, and prefetching, and summarizes the
rest.

Task Scheduling and Queue Sizes: To mitigate back-pressure from end-point
routers, input queues must have a sufficient size to buffer message bursts.
These bursts naturally happen in sparse linear algebra when a column of a
sparse matrix is much denser than the rest or in graph traversal when a vertex
has many more neighbors. However, making queues too large has unwanted side
effects, such as message waiting very long on average to be processed (leading
to data staleness). Moreover, in data-local execution, there is no global
orchestration of tasks, so task scheduling depends solely on information that
is local to each tile. Thus, queue occupancy and back-pressure help signal
tiles to adapt their task scheduling to prioritize tasks that would lead to
higher overall utilization, effectively resulting in a Goldilocks effect. We
study the size ratio between IQs and OQs on performance in Section V-A. For
the rest of the evaluation, we choose a ratio between IQ and OQ size
proportional to the expected average number of hops in that channel because in
a 2D network, the more hops, the more contention under irregular
communication, and so more input buffering is needed to maintain throughput.
For _proxy tasks_ we set the ratio to width of proxy subgrid, while for _main
tasks_ , we set this ratio proportional to the width of the tile grid.
However, as we observe later from the queue characterization of Section V-A,
different applications behave different with regard to buffering, which is
related to application sensitivity to data staleness. Since this sensitivity
depends on the synchronization point (barriers or epochs), we envision that
queue size could be set differently based on the workloads by a compiler via
static analysis. Based on this and the communication distance between tasks,
the compiler can more adequately set the queue sizes for different tasks. This
can also help utilize the storage better and give more SRAM to the caches.

NoC Reconfigurability: In a DCRA system, there are $P$ physical NoCs and $C$
logical channels. These channels can be assigned to different physical NoCs,
or to the same one. If they are in separate NoCs, these messages are routed
uncontested. If they are in the same NoC, they are routed in a round-robin
fashion. If the application is not using all of the available NoCs, a task can
use more than one channel increase the communication bandwidth with the task
being invoked. The allocation of physical to logical resources is fully
reconfigurable, a NoC can be used by multiple tasks, and a task can use
multiple NoCs.

TABLE II: Reconfigurable Parameters of DCRA Tapeout-time Design Decisions
---
# of Tiles per die
SRAM per-tile (MiB)
#Physical NoCs and Width of each one (in bytes)
Max.# of Router Buffer Entries per Physical NoC
Max.# of Logical NoC Channels per Physical NoC
Max.# of Memory Controller Channels per DCRA die
Packaging-time Design Decisions
# of DCRA dies per package
# of DRAM dies per package and capacity of each (GiB)
Ratio of DCRA-DRAM dictates Mem. BW and Capacity per DCRA
# of I/O dies per package (Off-Package BW)
Compile Time Configurations
Size and Place of the grid that the workload uses (grid of dies)
Whether the dataset uses SRAM as a scratchpad or D$
Size of the D$ (in data elements)
Mapping of Tasks to Logical NoC Channels
Mapping of NoC Channels to Physical NoCs
Number of Router Buffer Entries of each NoC Channel (shared pool)
Arbitration ratio between Channels sharing a Physical NoC
Per Task
Whether a Task has a Proxy and the size of the Proxy region
Whether the Proxy array is cached or kept in full
Whether Proxy updates are propagated write-through or write-back
Whether a Task uses data prefetching during execution (if dataset is cached)
Size of the Input Queue (IQ)
Size of the Output Queue (OQ) if the Task produces into a NoC Channel

###  III-C Software Configurable Caches using the local SRAM

In a DCRA system, the SRAM in each tile can be used either as a scratchpad or
as a cache [38, 15, 16]. The cache mode stores cacheline tags in SRAM,
including a valid bit. To minimize the hardware and energy overhead of using
the SRAM as a cache, we make the caches directly mapped.

This cache mode is used to configure the _proxy cache_ (P$), which holds proxy
data, and the _data cache_ (D$), which caches the dataset arrays when the
package has integrated HBM. When scaling out the parallelization of a dataset,
if the memory footprint per tile is so low that everything fits in the local
SRAM, the D$ would not be configured, and the PUs would access the data arrays
as a scratchpad. (Both the memory controller and the HBM would be switched
off).

The D$ and the P$ have reconfigurable sizes. Only one D$ can be configured,
and its line width equals the bitline width of the DRAM memory controller (512
bits in our experiments with HBM). Every proxy task would configure its own
logical P$, although they all use the same hardware comparison logic. This is
necessary because writing back proxy data requires knowing which task to send
it to.

D$ misses and evictions: Upon a miss, the D$ fetches the full cacheline from
DRAM without checking for coherence because the data is not shared across
tiles. This fetch uses a physical address since each DRAM module is private to
each DCRA die with 1-1 exclusive mapping between each tile and DRAM vault.
Therefore, each tile’s local SRAM is backed up by a DRAM storage of size
$DRAM\\_capacity/tiles\\_per\\_die$. The details of the DRAM assumed for the
evaluation are described in Table III. The D$ has a write-back policy and a
dirty bit per line, so when modified data get evicted, it is written back to
DRAM. Since the D$ of each tile only contains the part of the dataset that the
tile is responsible for, there is no coherence issues for modified data.

P$ misses and evictions: A miss in the P$ returns a default pre-configured
value such as 0 for Histogram or infinite for SSSP. A P$ is either write-
through or write-back, depending on how the proxy region is configured for
that task. On eviction, the data is simply replaced with write-through, while
with write-back, an update task is sent to the owner. Since the intention of
the P$ is to coalesce updates, all lines are considered dirty in the write-
back mode. By the end of a kernel, the write-back mode should evict all P$
lines to merge the updates before outputting the result. To overlap the data
merge, we include a heuristic in the TSU to flush the P$ when all queues and
network buffers are empty. In our experiments, a P$ line contains a single
data element to avoid sending multi-update messages in the write-back mode.
However, multiple elements per cacheline would increase effective P$ size, as
less SRAM storage is used for tags.

Prefetching The PU has a very simple in-order pipeline, which stalls waiting
for data on a D$ miss. Since the first parameter of every task message
contains an array index, and the TSU knows to which array it corresponds (as
it is necessary for network routing), we use this information to prefetch the
data. A task may access more than one array using the same index. Thus, we add
another pointer to the TSU’s task configuration table so that the TSU
prefetches both, if needed. The task entries in that table also have an extra
bit saying whether the PU prefetch data during the execution of the task.
Tasks can only access data within their dataset chunk, and when a task
accesses more than one array element, it often does so with a streaming
pattern. To prefetch those accesses, we enable the PU’s next-line prefetcher
(stride=1) for tasks that access more than one element.

Figure 3:  Top view of an example chip package with 32x32 tiles. The number of
DCRA dies would determine the compute capacity, while including HBM dies would
determine the compute-to-memory ratio of the chip architecture. The number and
sizes of the I/O dies would determine the provisioned off-chip bandwidth.
Figure 4:  Links between horizontal tiles within a DCRA die and across dies.
The red links show the network that connects every tile (tile network), while
the blue links represent a network that only connects to one tile per die (die
network). Because of the die network, the tiles at the edges of a die have
radix-9 routers, while the rest have radix-5 routers. The ports shadowed in
blue are reconfigurable, i.e., we can select which link to use at runtime.
These enable re-configuring any subgrid within the system to become Torus. The
die placed at the end of a package will interface with the I/O die. All four
links at the edge can be connected to the I/O die when loading the program and
the dataset to maximize the I/O bandwidth. During the program execution, both
networks can become torus, or we can have the tile network as a torus and the
die network as a mesh, to keep streaming data coming from outside the package.
Moreover, if the grid in which a program runs spans several packages, the
ports can be connected to conform a torus across packages as well.

###  III-D Package reconfigurability

Whether to integrate HBM on the chip is a package-time decision based on the
target metrics of the final product. Figure 3 exemplifies how the DCRA dies
could be packaged to provide high memory capacity per processor.

Extensible Memory Capacity: HBM capacity can be increased by either stacking
more DRAM layers or having larger layers. In our evaluation, we assumed a
10x11mm 4-layer HBM die (up to 16 layers has been demonstrated [65]). DCRA
could also integrate larger HBM dies, provided that the distance between DCRA
dies remain within 25mm (limit of common PHYs for MCM [73, 58, 5]). Selecting
the amount of DRAM attached to a DCRA die depends on what level of parallelism
is expected on a final product. If the chip is always expected to parallelize
a dataset to the limit of strong scaling, HBM might not be necessary. In
contrast, with target metrics like performance-per-watt, larger on-package
memory capacity is essential. We evaluate both options in Section 9 and
discuss the tradeoffs.

Integrating the HBM dies: Figure 1 depicts the connection between the DCRA and
the HBM die via a silicon interposer. Although we think that a silicon bridge
[47] or substrate integration (given enough layers) [39, 4] might be possible,
we assume the interposer integration in our evaluation because it has been
demonstrated to work in real products [14, 54]. Another alternative is 3D
integration, where the HBM die is placed on top DCRA. We evaluate this in
Section IV-C to understand whether the advantages are worth the power, thermal
and integration challenge [9, 29].

Designing the network: When dealing with irregular network traffic in
dimension-ordered routing (DOR), a 2D-torus provides a more uniform
utilization than a 2D-mesh [60]. DOR keeps the router logic simple, and
deadlocks are avoided using bubble routing [69]. To make implementation
practical on 2D silicon, the 2D-torus is folded: a set of links connects the
even-numbered tiles, and the other set of links connects the odd-numbered
ones. The torus can be arbitrarily large, i.e., be confined within a die or
span multiple dies, packages, or boards. Table III presents the interconnect
energy and latency assumed for our evaluation at each level. Figure 4 shows
that the routers at the edges of each die can be configured to connect to a
router on the next die or wrap around by connecting to the adjacent tile
(Tiles 0 and 63).

Reconfigurable topology: We can reconfigure a 2D-torus interconnect to become
two 2D-mesh networks by not connecting the wrap-around links on the routers at
the edges. Utilizing two 2D-meshes may be the right choice when running a
workload with near-neighbor communication [6]. As Figure 4 shows, DCRA has two
hierarchical networks that route per tile and per die. Each network topology
is individually configured. While bringing the data inside the package from
disk, they both would be configured as a mesh to enable data streaming from
the I/O dies. During the execution, both may become torus, or the per-die
network can remain open to I/O data.

Off-Chip Bandwidth: DCRA delegates the design of the interconnect between
packages to the I/O chiplets. This allows DCRA dies to remain agnostic to the
specific protocol (e.g., PCIe 6.0 [72]). It also delays choices like off-chip
bandwidth to packaging time, which are taken based on the requirements of the
final product. The off-chip bandwidth could be up to the bandwidth of the
I/O-DCRA interface. Figure 4 shows a configuration where two 32-bit
bidirectional Torus networks interface each border tile on a die (16 tiles per
side). Considering that only one side of the die interfaces with the I/O
chiplet, the border die can deliver up to 512GB/s. Multiplying that for the
number of bordering dies on a package would determine the maximum off-chip
bandwidth.

What decides the package size? A package is as big as the size of its
substrate. A silicon substrate typically scales 2-3x the reticle size, but
this could technically scale up to a wafer-scale interposer [64]. On a Multi-
chip Module (MCM) integration, server-class chip packages typically span over
$4500mm^{2}$ [53, 4, 54]. However, MCM substrates have been fabricated to
nearly $100,000mm^{2}$ [82, 22]. So the choice of the package size may be
determined by the unit of sale rather than a constraint in the substrate size.
Regarding the number of dies on a package, although we see chip packages with
tens of them [25], bonding may set feasibility bound. The package yield is
determined by the bonding yield of each die. [83]. When using DCRA dies of
16x16 tiles, the practical limit may be 128x128 tiles per package (64 dies).
In our evaluation, we set the package size to 64x64 tiles, i.e., $4780mm^{2}$,
which is in line with the size of server-class chips.

Scaling beyond a package: Off-chip network topology and bandwidth are
determined by the I/O chiplets selected. The I/O links across packages could
also be electrical or optical[50, 19]. If a system featuring DCRA chiplets is
expected to have near-neighbor communication, several packages are connected
on a board using a 2D network with electrical links. However, when irregular
or all-to-all traffic is expected, it would be beneficial to connect packages
directly with optical links on a high-dimensional network [8, 2]. For
simplicity, we assume electrical links between packages DCRA in our
evaluation.

Graph Partitioning is commonly used in distributed graph processing [84] to
reduce communication. In addition to using proxies, graph partitioning can
also be used during data placement in DCRA so that each subgrid would store a
graph partition with fewer cross-partition connections.

##  IV Evaluation

Applications: We evaluate the performance of DCRA on four graph workloads, one
sparse linear algebra, and a histogram benchmark [79] to demonstrate the
generality of our approach for memory-intensive applications.

Breadth-First Search (BFS) determines the number of hops from a root vertex to
all vertices reachable from it; Single-Source Shortest Path (SSSP) finds the
shortest path from the root to each reachable vertex; PageRank ranks websites
based on the potential flow of users to each page [40]; Weakly Connected
Components (WCC) finds and labels each set of vertices reachable from one to
all others in at least one direction (using graph coloring [75]); Sparse
Matrix-Vector Multiplication (SPMV) multiplies a sparse matrix with a dense
vector. Histogram (Histo) counts the number of values that fall within a
series of intervals. We perform the evaluation using real-world networks and
synthetic datasets. We use several different sizes of synthetic RMAT graphs
[43] of up to 67M vertices (V) and 1.3B edges (E), with up to 12GB of memory
footprint, as well as real-world graphs Wikipedia (V=4.2M, E=101M). For
Histogram we use the same datasets and have $E$ elements to be filtered into
$V$/8 bins (as values, we use the edge array index plus its value, modulo the
#bins)

Methodology: We build upon the cycle-level simulator of Dalorex [60] and
extend it to support data and proxy caches, an HBM model, and three levels of
network interconnect (between tiles, dies, and packages). Table III summarizes
our additions to the energy, latency and area model for network links and
memory technology. In addition to the latency of the links shown in Table III,
the simulator models cycle-accurate network congestion (it evaluates the
routers every clock cycle). We use the existing model on the simulator for the
power and area of the cores and routers. This is modeled based on
characterizations of manycore architectures [49, 61, 18, 93, 91, 90], and
transistor scaling to a 7nm process [77, 88]. We assume a 1GHz frequency for
the die logic.

###  IV-A Characterizations

We have experimented with the DCRA configuration knobs listed in Table II.
Section V-A characterizes several sizes of task queues and proxy grids, as
well as four network options. Section V-C studies the cost-effectiveness of
integrating HBM dies in performance and energy efficiency. Due to space
considerations, for the rest of the experiments, we verbally present our
insights here.

SRAM size: We experimented with SRAM sizes ranging from 128KiB to 4MiB and
found 1.5MiB of SRAM per tile to be enough to hold the program code, the task
queues, and a well-performing size of D$ and P$. The P$ saves on-die traffic
on the task for which it is enabled, reducing the average number of router
hops for that task. The ideal size of the P$ depends on the ratio between the
program grid and the proxy grid. The D$ saves traffic to the HBM device,
reducing memory-controller contention and energy. An appropiate size of D$
yields a hit rate that is high enough not to saturate the memory channels when
the processing units are fully utilized. These sizes are compile-time
configurable, as mentioned in Section III-B. At 1.5MiB, the tile area
dedicated to SRAM is 7$\times$ larger than the area of the router, PU and TSU
together. Since DCRA is focused on Data-Centric computing, this size is a good
tradeoff.

Die size: All our results use dies with 16x16 tiles. This size is practical
for several reasons: (a) it matches common sizes of HBM chiplets [42, 65, 57];
(b) it allows for larger configurations per package, as the packaging yield
depends on the number of dies; (c) the lower yield of a 32x32-tile (27x25mm)
die results in getting 62% less good dies per wafer [31]. Larger dies would
achieve a high yield with the overhead of adding tile redundancy [45, 37].
However, we find it appealing to have a unit die that is small enough to add
flexibility at packaging time.

Network interconnect: We use one die network and two torus networks for all
results but the characterization Figure 6. Both torus networks use 32-bit
links across dies, but one them uses 64-bit links inside the die. We used this
configuration due to its good performance-to-cost ratio. The interconnect
bandwidth between DCRA dies is sufficiently low ($\sim$800Gbit/s/mm) to avoid
an expensive silicon interposer (which can reach up to 5Tbit/s/mm [87, 58,
73]). For the die-to-die substrate wires, we assume a BoW-128 PHY with 130µm
bumps [58, 5]. To connect DCRA and HBM, we assume a 65nm CMOS passive
interposer [68, 13] with 55µm bumps [58].

###  IV-B Cost Model

Die Cost: For silicon, we assume that a 300mm diameter wafer featuring 7nm
transistors costs $6,047 [33]. We obtain the cost per die by dividing the
wafer cost by the number of good dies per wafer. This was obtained with a die
yield calculator using Murphy’s model [31], using 0.2mm scribes, 4mm edge
loss, and 0.07 defects per mm2. When comparing cost-effectiveness in Figure 9,
we do not include the Non-Recurring Engineering (NRE) cost of the DCRA dies
since all the alternatives use the same chiplets.

Packaging Cost: All our results featuring grid sizes over 64x64 use multiple
chip packages (of 64x64 tiles each, based on our rationale from Section
III-D). Although costs of packaging and die bonding are not disclosed, there
is public information on the cost overhead with respect to the cost of the
die. We assume the cost of the 65nm silicon interposer connecting a DCRA die
with HBM (including bonding) to be 20% of the price of a DCRA die [83]. We
assume the cost of an organic substrate to be 10% of the price of an equal-
sized DCRA die, and the bonding adds an additional 5% overhead [78, 41].

HBM Cost: We assume an 8GB HBM2E device with eight 64GB/s memory channels.
While this cost is not disclosed, we made an educated guess using public
sources [33, 66] and other technical blogs. We assume a 7.5$/GB of HBM. This
is much more affordable than when HBM was released in 2017, and we expect this
price to decrease over time as more vendors fabricate HBM [51, 42, 57].

TABLE III: Energy, bandwidth and latency assumed for the evaluation Memory Model Parameters | Values
---|---
SRAM Density | 3.5 MiB/mm2 [89]
SRAM R/W Latency & Energy | 0.82ns & 0.18 / 0.28 pJ/bit [89]
Cache Tag Read & Compare Energy | 6.3 pJ [89, 90]
HBM2E 4-high Density | 8GiB/110mm2 (74.5 MiB/mm2) [42]
Mem.Channels & Bandwidth | 8 x 64 GB/s [42]
Mem.Ctrl-to-HBM RW Lat. & Energy | 50ns & 3.7pJ/bit [63, 35]
Bitline Refresh Period & Energy | 32ms & 0.22pJ/bit [76, 23]
Wire & Link Model Parameters | Values
MCM PHY Areal Density | 690 Gbits/mm2 [5]
MCM PHY Beachfront Density | 880 Gbits/mm [5]
Si. Interposer PHY Areal Density | 1070 Gbits/mm2 [5]
Si. Interposer PHY Beachfront Density | 1780 Gbits/mm [5]
Die-to-Die Link Lat. & Energy | 4ns & 0.55pJ/bit ($<$25mm) [58]
NoC Wire Latency & Energy | 50 ps/mm & 0.15pJ/bit/mm [36]
NoC Router Latency & Energy | 500ps & 0.1pJ/bit
I/O Die RX-TX Latency | 20ns [72]
Off-Package Link Energy | 1.17pJ/bit (80mm) [87]
Figure 5:  Alternative packaging of an HBM device on top of a DCRA die. The
design of the DCRA die would need to be different; it would behave as a very
active interposer. This would require making the DCRA die larger to
accommodate the links and power supply pads below the HBM device.

###  IV-C 3D Integrations

Prior work [3, 94, 96, 36] has assumed 3D integrations where processing cores
are on the base plane of the 3D-stacked memory, accessing the TSVs directly.
However, we believe this may be impractical. The are very few foundries that
can fabricate HBM technology, and the design seems to only change with every
generation of JEDEC specification [32](e.g., HBM2, HBM2e, HBM3) which vendors
conform to. So it would be expensive (if possible) to get a foundry to
fabricate an HBM die with a custom base layer. Moreover, the base layer of the
HBM stacks is filled with MBIST logic and PHY [42, 65, 28, 57]. Vertical
stacking would reduce HBM latency, but more importantly, it would
significantly reduce wire energy [36]. Having HBM on top of a compute die is
challenging for bonding, power delivery, and thermal dissipation [95]. It
seems more practical to use an off-the-shelf HBM die and integrate it via an
interposer. We observe two alternatives: (a) having the HBM die adjacent to a
compute die and connecting them via a passive interposer, or (b) having the
HBM die on top of the compute die, which would behave as a beefy, active
interposer [85, 78]. The most common integrations of HBM with compute dies are
horizontal [53, 4, 47, 30, 54, 92, 87], where we have only found one vertical
integration of memory but using SRAM [80]. Since the power-density of the DCRA
die is very low due the large area dedicated to SRAM, we think that
integration like the one depicted in Figure 5 is not out of the question which
we consider in Section V-C.

###  IV-D Comparison with the State-of-the-Art

Since we want to understand where our system stands with respect to the Graph
500 list [52], we adhere to their guidelines. Graph500 requires timing
separately the reading, preparing, and loading of the graph onto the system
and the graph traversal itself. In our case, we do not perform any dataset
pre-processing and directly read the CSR structure from disk. The time for
loading the dataset depends on how many disks the data is spread across, the
speed of these disks, and the off-chip bandwidth. Assuming latter to be the
limiting factor, we provide a lower bound by dividing the dataset size by the
off-chip I/O.

Since our goal is to evaluate the performance of our architecture, we
concentrate on graph traversal. Based on the Graph 500 benchmark guidelines,
we begin counting cycles when the search key is loaded onto the system, and we
stop counting when the last vertex is visited. We report traversed edges per
second as $TEPS=m/time$ where $m$ is the number of edges connected to the
vertices in the graph traversal starting from the search key. Due to runtime
limitations of our simulator, we only perform one search from the root node
and report the TEPS for that search. Because we also evaluate other
applications than graph traversal, when we report for SPMV and Histogram, we
consider # input elements to process.

##  V Results

In this section, we first present the characterization of a crucial pre-
silicon choice: the number of physical networks and their width. Second, we
characterize software-time configurations, such as the size of the input
queues for tasks concerning the output queues. Third, we explore packaging
choices, including two with SRAM-only and another two with different
integrations of HBM. Later, we show the performance gains over the prior work
Dalorex, characterizing the impact of _proxies_ on network traffic. Finally,
we study strong scaling, performance-per-watt, and performance-per-dollar by
parallelizing RMAT-26 for increasing grid sizes, ranging from 256 tiles to
1,048,576 tiles. We compare our fastest results versus entries of the Graph500
ranking [52] and other works [10] for same datasets sizes.

###  V-A Characterizations

Network: We evaluate four different network options to characterize how the
intra-die (ID) out-of-die (OD) network bandwidth affects runtime, including:
(a) two 32-bit networks whose flow gets throttled to a shared 32-bit when
crossing die boundaries; (b) a 32-bit and a 64-bit networks whose flow gets
throttled to a shared 32-bit when crossing die boundaries; (c) same as $b$ but
with two 32-bit links across dies; (d) same as $b$ but maintaining the
bandwidth across dies.

All runs are performed on a single chip package with a 64$\times$64 tile grid
across 16 dies. We assign the 64-bit network to the channel used by the proxy
task, while the other tasks use the 32-bit network. The proxy subgrids are of
size 16x16, matching the die size. Thus, overall there are 16 subgrids.

Figure 6 (top) shows that the increase in network bandwidth is beneficial for
four applications. Figure 6 (bottom) shows the average percent of the runtime
that the PUs were executing tasks. One can observe that Histogram and WCC
start with higher utilization than other workloads with the lowest bandwidth
setting, which may explain why their performance does not improve
significantly more with increased bandwidth.

Across the board, the geomean improvement of option (c), with two 32-bit links
between dies, is 1.72$\times$ geomean faster than option (a). Since this is a
tapeout-time parameter, it is essential to understand the cost impact of this
choice. The total die area grows by 4.5%, but the performance improvement
renders it worth it. For the rest of this section, the results are evaluated
using option (c).

Returning to the utilization of Figure 6 (bottom), note that RMAT-22 has
$2^{22}$ vertices, and we are executing it on $2^{12}$ tiles (a 64$\times$64
grid). This level of parallelization (with little work per PU) makes it
challenging to achieve a 100% utilization since the ramp-up time (to get
enough tasks in the network) and the cool-down phase (where the last tasks are
executed) represent a significant part of the total runtime.

---
---

Figure 6: Performance improvement (top) and PU utilization in % of total
runtime (bottom) of three network options with different intra-die (ID) and
out-of-die (OD) link widths over a baseline of two 32-bit networks whose flow
gets throttled to a shared 32-bit when crossing die boundaries. The legend
represents the link widths and whether there is more than one link. The X-axis
shows the datasets used for each of the applications evaluated. All runs are
performed on a 64$\times$64 tile grid using the RMAT-22 and Wikipedia
datasets.

Queue sizes: Figure 7 shows the performance improvement resulting from
increasing the size of the input queues (IQs), while keeping the size of the
output queues (OQs) fixed. Note that the legend does not indicate the queue
size but how many times bigger the IQ is compared to the OQ. We observe that
increasing the IQ size has a significant impact on performance. In the case of
SSSP, BFS, and WCC, we observe a Goldilocks effect. Increasing IQ size
improves performance while there exists network contention; once that is
removed, larger IQ sizes only increases data staleness. The lack of
improvement on WCC and Histogram is attributed to the already high core
utilization observed in Figure 6. It is noteworthy that SPMV drastically
increases performance due to increased IQ size. Figure 6 used our default IQ-
OQ ratio of 8. Figure 7 demonstrates that performance can improve even
further, for the case of SPMV, by increasing the IQ ratio. Insufficient IQ
size causes end-point contention when bursts of messages arrive, and the PU
cannot process them fast enough. A smarter Task scheduler could also help
alleviate this problem by dynamically adjusting the IQ sizes among tasks to
use the SRAM space more effectively than with static allocation.

Figure 7: Performance improvement of growing the input queue (IQ) size while
keeping the same output queue (OQ) size, normalized to the baseline of same
size IQ and OQ. The legend indicates how many times bigger is the IQ of each
task compared to its OQ. The X-axis shows the datasets used for each of the
applications evaluated. All runs are performed on a 64$\times$64 tile grid
using the RMAT-22 and Wikipedia datasets.

###  V-B Comparison with prior work

In order to measure the impact of proxy tasks and re-configurable queue sizes,
we reproduce the same configuration as that in Orenes-Vera et al. [60], and
compare the performance of DCRA with that of Dalorex.

The advantages of proxy tasks: Figure 8 (top) shows the average number of
router hops of a the vertex update message in Dalorex and for DCRA’s proxy
task. For smaller configurations, the DCRA proxy region is defined as a
quarter or the size of the tile grid. For the 128x128 configuration, we use 16
subgrids of size 32x32 for all applications except Pagerank, which uses 64x64
subgrids. These vaying sizes help show the impact of the subgrid size on the
average number of hops. We can observe from Figure 8 (top) that the proxy
region significantly reduces communication, which translates to achieving
higher throughput (bottom).

Scalability: Figure 8 (bottom) also shows that DCRA is not limited when
scaling to large grid sizes, unlike Dalorex, which starts to plateau after
64x64 due to high network contention. Dalorex gets higher throughput on the
16x16 configuration, since they assume that data footprint per tile always
fits on the local SRAM, while DCRA uses a limited 1.5MB SRAM with a backup on
HBM.

---
---

Figure 8:  The top plot shows the average number of router hops per message
(lower is better) for the vertex update task. Since DCRA uses a proxy on this
task, the average number of hops is smaller. The bottom plot shows the
throughput improvement over the baseline Dalorex 16x16 (Y-axis is
logarithmic). All the datapoints use the RMAT-26 dataset.

###  V-C Package Integration Options

Figure 9 evaluates throughput and energy efficiency per unit of cost of three
DCRA integrations over Dalorex. We evaluate DCRA without HBM dies (only SRAM)
and integrating HBM with two packaging options: placing the HBM device
vertically on top of the DCRA die (See Figure 5), or horizontally, via a
passive interposer (See Figure 1). Since the silicon area of a 64x64
configuration of Dalorex [60] is beyond the reticle limit of 880mm2, we assume
the same chiplet-based integration of DCRA for Dalorex. This makes their cost
very similar (only affected by the interconnect area). Thus, throughput-per-
cost differences mostly come from total runtime. We evaluate all integrations
on their smallest configuration that fits the dataset. This makes HBM
integrations to use a grid size with 16 times less tiles.

Although Figure 9 does not show total throughput, we can observe from Figure
11 (also using RMAT-26) that throughput scales very well. Since DCRA-SRAM does
not cost 16$\times$ more than DCRA-HBM, it wins across the board on
throughput-per-dollar. Despite that DCRA-SRAM runs 16$\times$ faster, it does
not consume 16$\times$ less energy, so DCRA-HBM wins on energy-efficiency-per-
dollar.

Note that these results assume a 60$ 8GB HBM2 die (3$\times$ more expensive
than the base DCRA die in 7nm). This throughput-per-dollar results could
change significantly if either HBM becomes cheaper or other DRAM or 3D-stacked
SRAM [74] technology (using the same HBM memory controller) becomes cheaper.
Considering the two HBM options, our cost model estimated that (should it be
practical) the HBM-Vertical integration would cost 5% more than the horizontal
one. Therefor, the reason why DCRA-HBM-Vertical wins over the horizontal
alternative is because of savings in wire energy.

---
---

Figure 9:  Improvements in throughput/$ and energy efficiency/$, normalized to
Dalorex. Dalorex and SRAM-only DCRA use a 64x64 configuration for RMAT-25 and
128x128 for RMAT-26. The HBM configurations use a 16x16 configuration for
RMAT-25 and 32x32 for RMAT-26.

Figure 10:  Breakdown of the energy consumed by computing logic, memory, and
network communication (including routing and wire energy). The plots break
down the energy used by DCRA-SRAM (top) and DCRA-Horiz (bottom) with the same
configurations of Figure 9. The Y-axis shows the percentage of the total
energy spent on each component. The X-axis indicates the dataset.

Figure 10 breaks down the energy consumed by the PU logic, memory and network
for both DCRA-SRAM and DCRA-HBM-Horiz. The SRAM-only integration scales out to
use 16$\times$ more tiles than the version including HBM; thus, it spends much
more energy on wires. Although not shown here, we observed that the HBM
integration saturates the memory controller bandwidth. This makes the
breakdown to be dominated by DRAM energy. PUs represent a small fraction on
the energy consumption on both cases. Note that PUs are powered off by the TSU
when idle, so they only consume energy while processing tasks.

###  V-D Strong Scaling Up to a Million Tiles

Figure 11:  Throughput in operations, traversed edges per second (TEPS), and
the average on-chip memory bandwidth needed to achieve that. Note that the
couple of datapoints without TEPS are partial run that the simulator could
finish. Partial runs may show higher throughput as they have not reached the
cool-down ending phase. The X-axis is the size of the DCRA grid used when
analyzing strong scaling RMAT-26, ranging from 256 to over a million tiles.
The Y-axis is logarithmic for both plots. The bottom plot shows throughput as
a function of power and cost. Higher is better.

Throughput-per-watt likes small grids: From Figure 11 (bottom), we observe
that when throughput-per-watt is the critical metric, staying within the
smallest configuration that fits the dataset is the correct choice. The
RMAT-26 dataset fits entirely on a 16x16 die with 8GB HBM. Throughput-per-watt
drops significantly after using $2^{12}$ tiles, i.e., a chip package of 64x64
tiles. The inter-package links are more power-hungry than the links inside the
package, hence, the drop in efficiency.

Throughput-per-dollar increases during superlinear performance scaling:
Optimal throughput-per-dollar peaks at a 128x128 configuration (4 chip
packages). This is because while the cost grows linearly with the number of
chips, the performance grew super-linearly until that scaling step, where the
decrease in footprint-per-tile also decreased the pressure in the memory
controller of the HBM. At 128x128, RMAT-26 fits in SRAM. Beyond that, the
gradually smaller footprint-per-tile reduces PU utilization since there are
less parallel tasks to be executed. This leads to a less than linear scaling
that makes the throughput-per-dollar to decrease.

Strong scaling for faster time-to-solution: For purposes of this experiment we
take the extreme approach of parallelizing a dataset with $2^{26}$ vertices
(and $\sim$$2^{28}$ edges) across $2^{20}$ tiles. This shows that DCRA is
suited for strong scaling, although it is not the most efficient way to use
it.

Work Efficiency: The goal in graph applications is high TEPS, and not
necessarily operations per second. TEPS is a measurement for how long it takes
to process a certain dataset. The order in which vertices are processed
matters for work efficiency, so throughput alone does not determine runtime.
From Figure 11 (top), we can observe that for very large parallelizations of
SSSP, BFS and WCC, the increase in throughput does not translate into an equal
increase in TEPS. (We can expect a similar trend for the datapoints that the
simulator could not finish). Better work efficiency could by achieved by
enforcing order with a barrier at the end of each epoch, but this would reduce
the throughput. Pagerank does have that barrier, and we observe a more steady
increase in throughput and TEPS. For Histogram and SPMV, TEPS indicate total
array elements divided by runtime, which correlates with throughput. This is
because data updates are only relevant for the final result, what allows proxy
updates not to get propagated to the owners until the last part of the
execution (when proxy regions are invalidated). Histogram is a simpler kernel
than SPMV, and so the reason for the trend is simply lack of work to be
parallelized. SPMV achieves a remarkable scaling all the way to the million-
tile configuration. The spike in throughput at the last datapoints is that we
could dedicate more SRAM resources to task queues due to having a smaller data
footprint-per-tile. We saw in Figure 7 that larger IQs had a big impact on
SPMV performance.

Petabyte/s of memory bandwidth: We mentioned in the beginning of the paper
that data-structure traversal have a high memory to compute ratio. We can
observed in this plot how much memory bandwidth is required to maintain a high
target throughput. Figure 11 (top) shows that for the 1-million-tile
configuration, SPMV reads, on average, half a PB/s from their local memories.
At peak, SPMV is reading 1.7 PB/s to perform 450 Teraops/s, of which 43
Teraops/s are dedicated to multiplication of non-zero matrix elements. It
achieves that by drawing 37KW across 256 chip packages (power density stays in
the tens of mW/mm2, air cooling).

Comparing with the state-of-the-art: From the Graph500 list, the current best
performance for BFS on RMAT-26 is 884 GTEPS, which is achieved at the Tianhe
Exa-node (Prototype@GraphV) [52]. The next entry features an undisclosed High
Throughput Computer with four NVidia V100-SXM2, which delivers 392 GTEPS. For
RMAT-26, our work performs 3161 GTEPS on a 512x512 grid (256 chips) and 3323
GTEPS on a 1024x1024 grid (256 chips). Given the assumed chip I/O and the
number of chips, bringing the dataset on chip would take $<0.1$ms.

For smaller datasets like RMAT-22, although Graph500’s best entry is at 1
GTEPS, we found other works showing up to 70 GTEPS [10] running the Enterprise
[46] and Gunrock codes [86] on a 32GB NVIDIA Tesla V100-SXM3. For RMAT-22, the
64x64 configuration (single-chip) evaluated in Figure 6 would achieve 362
GTEPS. Note that this GPU runs at 1.6 GHz, while we assume 1 Ghz for our
system.

##  VI Conclusion

In this work we demonstrate that our data-centric architecture scales
performance for sparse data applications even when processing datasets of
$2^{26}$ vertices across $2^{20}$ PUs. This is 100$\times$ larger than the
prior largest parallelization of a problem of this size. We achieve this by
leveraging the benefits of data-local execution while introducing a
reconfigurable tile fabric that removes prior work’s limitations. Our work
introduces techniques for better work balance, scalable network communication,
and reconfigurable memory hierarchy. DCRA allows integrating extra DRAM on
chip, drastically reducing the need to scale out when processing large
datasets. Through our reconfigurable design, one can balance cost, performance
and energy efficiency tradeoffs and tailor compile-time optimizations such as
proxy, cache, and queue sizes.

## References

  * [1] M. Abeydeera and D. Sanchez, “Chronos: Efficient speculative parallelism for accelerators,” in _Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems_ , 2020, pp. 1247–1262.
  * [2] N. R. Adiga, G. Almási, G. S. Almasi, Y. Aridor, R. Barik, D. Beece, R. Bellofatto, G. Bhanot, R. Bickford, M. Blumrich _et al._ , “An overview of the bluegene/l supercomputer,” in _SC’02: Proceedings of the 2002 ACM/IEEE Conference on Supercomputing_. IEEE, 2002, pp. 60–60.
  * [3] J. Ahn, S. Hong, S. Yoo, O. Mutlu, and K. Choi, “A scalable processing-in-memory accelerator for parallel graph processing,” in _Proceedings of the 42nd Annual International Symposium on Computer Architecture_ , 2015, pp. 105–117.
  * [4] AMD, “Amd rome,” 2018, https://en.wikichip.org/wiki/amd/cores/rome.
  * [5] S. Ardalan, B. Vinnikota, T. Arabi, and E. Alon, “What is the right die-to-die interface? a comparison study,” 2022, https://www.opencompute.org/events/past-events/hipchips-chiplet-workshop-isca-conference.
  * [6] K. Asanovic, R. Bodik, B. C. Catanzaro, J. J. Gebis, P. Husbands, K. Keutzer, D. A. Patterson, W. L. Plishker, J. Shalf, S. W. Williams _et al._ , “The landscape of parallel computing research: A view from berkeley,” _eScholarship, University of California_ , 2006.
  * [7] J. Balkind, K. Lim, F. Gao, J. Tu, D. Wentzlaff, M. Schaffner, F. Zaruba, and L. Benini, “OpenPiton+Ariane: The first open-source, SMP Linux-booting RISC-V system scaling from one to many cores,” in _Third Workshop on Computer Architecture Research with RISC-V, CARRV_ , vol. 19, 2019.
  * [8] A. Benner, “Optical interconnect opportunities in supercomputers and high end computing,” in _OFC/NFOEC_. IEEE, 2012, pp. 1–60.
  * [9] B. Black, “Die stacking is happening,” in _Intl. Symp. on Microarchitecture, Davis, CA_ , 2013.
  * [10] L. Burchard, J. Moe, D. T. Schroeder, K. Pogorelov, and J. Langguth, “ipug: Accelerating breadth-first graph traversals using manycore graphcore ipus,” in _International Conference on High Performance Computing_. Springer, 2021, pp. 291–309.
  * [11] L. P. Carloni, “The case for embedded scalable platforms,” in _2016 53nd ACM/EDAC/IEEE Design Automation Conference (DAC)_. IEEE, 2016, pp. 1–6.
  * [12] Cerebras Systems Inc., “The second generation wafer scale engine,” https://cerebras.net/wp-content/uploads/2021/04/Cerebras-CS-2-Whitepaper.pdf.
  * [13] R. Chaware, K. Nagarajan, and S. Ramalingam, “Assembly and reliability challenges in 3d integration of 28nm fpga die on a large high density 65nm passive interposer,” in _2012 IEEE 62nd Electronic Components and Technology Conference_ , 2012, pp. 279–283.
  * [14] J. Choquette and W. Gandhi, “Nvidia A100 GPU: Performance & innovation for GPU computing,” in _2020 IEEE Hot Chips 32 Symposium (HCS)_. IEEE Computer Society, 2020, pp. 1–43.
  * [15] C. C. Chou, A. Jaleel, and M. K. Qureshi, “Cameo: A two-level memory organization with capacity of main memory and flexibility of hardware-managed cache,” in _2014 47th Annual IEEE/ACM International Symposium on Microarchitecture_. IEEE, 2014, pp. 1–12.
  * [16] E. G. Cota, P. Mantovani, and L. P. Carloni, “Exploiting private local memories to reduce the opportunity cost of accelerator integration,” in _Proceedings of the 2016 International Conference on Supercomputing_ , 2016, pp. 1–12.
  * [17] 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.
  * [18] S. Davidson, S. Xie, C. Torng, K. Al-Hawai, A. Rovinski, T. Ajayi, L. Vega, C. Zhao, R. Zhao, S. Dai, A. Amarnath, B. Veluri, P. Gao, A. Rao, G. Liu, R. K. Gupta, Z. Zhang, R. Dreslinski, C. Batten, and M. B. Taylor, “The celerity open-source 511-core risc-v tiered accelerator fabric: Fast architectures and design methodologies for fast chips,” _IEEE Micro_ , vol. 38, no. 2, pp. 30–41, 2018.
  * [19] Y. Demir, Y. Pan, S. Song, N. Hardavellas, J. Kim, and G. Memik, “Galaxy: A high-performance energy-efficient multi-chip architecture using photonic interconnects,” in _Proceedings of the 28th ACM international conference on Supercomputing_ , 2014, pp. 303–312.
  * [20] M. Emani, V. Vishwanath, C. Adams, M. E. Papka, R. Stevens, L. Florescu, S. Jairath, W. Liu, T. Nama, and A. Sujeeth, “Accelerating scientific applications with sambanova reconfigurable dataflow architecture,” _Computing in Science & Engineering_, vol. 23, no. 2, pp. 114–119, 2021\.
  * [21] Esperanto Technologies, “Esperanto’s et-minion on-chip risc-v cores,” https://www.esperanto.ai/technology/.
  * [22] J. Frazelle, “Chip measuring contest: The benefits of purpose-built chips,” _Queue_ , vol. 19, no. 5, pp. 5–21, 2021.
  * [23] S. Ghose, A. G. Yaglikçi, R. Gupta, D. Lee, K. Kudrolli, W. X. Liu, H. Hassan, K. K. Chang, N. Chatterjee, A. Agrawal _et al._ , “What your dram power models are not telling you: Lessons from a detailed experimental study,” _Proceedings of the ACM on Measurement and Analysis of Computing Systems_ , vol. 2, no. 3, pp. 1–41, 2018.
  * [24] D. Giri, K.-L. Chiu, G. Di Guglielmo, P. Mantovani, and L. P. Carloni, “ESP4ML: Platform-based design of systems-on-chip for embedded machine learning,” in _DATE_. IEEE Press, 2020.
  * [25] W. Gomes, A. Koker, P. Stover, D. Ingerly, S. Siers, S. Venkataraman, C. Pelto, T. Shah, A. Rao, F. O’Mahony _et al._ , “Ponte vecchio: A multi-tile 3d stacked processor for exascale computing,” in _2022 IEEE International Solid-State Circuits Conference (ISSCC)_ , vol. 65. IEEE, 2022, pp. 42–44.
  * [26] L. Gwennap, “Groq rocks neural networks,” _Microprocessor Report, Tech. Rep., jan_ , 2020.
  * [27] T. J. Ham, L. Wu, N. Sundaram, N. Satish, and M. Martonosi, “Graphicionado: A high-performance and energy-efficient accelerator for graph analytics,” in _Proceedings of the 49th Annual International Symposium on Microarchitecture_ , ser. MICRO, 2016. [Online]. Available: https://doi.org/10.1109/MICRO.2016.7783759
  * [28] “High-Bandwidth Memory (HBM),” 2015, https://www.amd.com/Documents/High-Bandwidth-Memory-HBM.pdf.
  * [29] X. Hu, D. Stow, and Y. Xie, “Die stacking is happening,” _IEEE micro_ , vol. 38, no. 1, pp. 22–28, 2018.
  * [30] Intel, “Intel kaby lake g,” 2018, https://en.wikichip.org/wiki/intel/cores/kaby_lake_g.
  * [31] Isine, “Die yield calculator,” https://isine.com/resources/die-yield-calculator/.
  * [32] JEDEC, “Standard high bandwidth memory specification jesd235a,” 2015.
  * [33] S. W. Jones, “Lithovision: Economics in the 3d era,” https://semiwiki.com/wp-content/uploads/2020/03/Lithovision-2020.pdf.
  * [34] N. P. Jouppi, C. Young, N. Patil, D. Patterson, G. Agrawal, R. Bajwa, S. Bates, S. Bhatia, N. Boden, A. Borchers _et al._ , “In-datacenter performance analysis of a tensor processing unit,” in _Proceedings of the 44th annual international symposium on computer architecture_ , 2017, pp. 1–12.
  * [35] D.-H. Kim, B. Song, H.-a. Ahn, W. Ko, S. Do, S. Cho, K. Kim, S.-H. Oh, H.-Y. Joo, G. Park, J.-H. Jang, Y.-H. Kim, D. Lee, J. Jung, Y. Kwon, Y. Kim, J. Jung, S. O, S. Lee, J. Lim, J. Son, J. Min, H. Do, J. Yoon, I. Hwang, J. Park, H. Shim, S. Yoon, D. Choi, J. Lee, S. Woo, E. Hong, J. Choi, J.-S. Kim, S. Han, J. Bang, B. Park, J. Kim, S.-K. Choi, G.-H. Han, Y.-C. Sung, W.-I. Bae, J.-D. Lim, S. Lee, C. Yoo, S. J. Hwang, and J. Lee, “A 16gb 9.5gb/s/pin lpddr5x sdram with low-power schemes exploiting dynamic voltage-frequency scaling and offset-calibrated readout sense amplifiers in a fourth generation 10nm dram process,” in _2022 IEEE International Solid- State Circuits Conference (ISSCC)_ , vol. 65, 2022, pp. 448–450.
  * [36] S. Kim, S. Kim, K. Cho, T. Shin, H. Park, D. Lho, S. Park, K. Son, G. Park, and J. Kim, “Processing-in-memory in high bandwidth memory (pim-hbm) architecture with energy-efficient and low latency channels for high bandwidth system,” in _2019 IEEE 28th Conference on Electrical Performance of Electronic Packaging and Systems (EPEPS)_ , 2019, pp. 1–3.
  * [37] S. Knowles, “Graphcore,” in _2021 IEEE Hot Chips 33 Symposium (HCS)_. IEEE, 2021, pp. 1–25.
  * [38] S. Kumar, H. Zhao, A. Shriraman, E. Matthews, S. Dwarkadas, and L. Shannon, “Amoeba-cache: Adaptive blocks for eliminating waste in the memory hierarchy,” in _2012 45th Annual IEEE/ACM International Symposium on Microarchitecture_. IEEE, 2012, pp. 376–388.
  * [39] J. H. Lau, “Status and outlooks of flip chip technology,” _IPC EXPO Proceedings, February 2017_ , pp. 1–20, 2017.
  * [40] P. Lawrence, B. Sergey, R. Motwani, and T. Winograd, “The pagerank citation ranking: Bringing order to the web,” Stanford University, Technical Report, 1998\.
  * [41] C.-C. Lee, C. Hung, C. Cheung, P.-F. Yang, C.-L. Kao, D.-L. Chen, M.-K. Shih, C.-L. C. Chien, Y.-H. Hsiao, L.-C. Chen, M. Su, M. Alfano, J. Siegel, J. Din, and B. Black, “An overview of the development of a gpu with integrated hbm on silicon interposer,” in _2016 IEEE 66th Electronic Components and Technology Conference (ECTC)_ , 2016, pp. 1439–1444.
  * [42] D. U. Lee, H. S. Cho, J. Kim, Y. J. Ku, S. Oh, C. D. Kim, H. W. Kim, W. Y. Lee, T. K. Kim, T. S. Yun _et al._ , “22.3 a 128gb 8-high 512gb/s hbm2e dram with a pseudo quarter bank structure, power dispersion and an instruction-based at-speed pmbist,” in _2020 IEEE International Solid-State Circuits Conference-(ISSCC)_. IEEE, 2020, pp. 334–336.
  * [43] J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos, and Z. Ghahramani, “Kronecker graphs: An approach to modeling networks,” _Journal of Machine Learning Reseach (JMLR)_ , vol. 11, pp. 985–1042, Mar. 2010.
  * [44] C. Lichtenau, A. Buyuktosunoglu, R. Bertran, P. Figuli, C. Jacobi, N. Papandreou, H. Pozidis, A. Saporito, A. Sica, and E. Tzortzatos, “Ai accelerator on ibm telum processor: industrial product,” in _Proceedings of the 49th Annual International Symposium on Computer Architecture_ , 2022, pp. 1012–1028.
  * [45] S. Lie, “Multi-million core, multi-wafer ai cluster,” in _2021 IEEE Hot Chips 33 Symposium (HCS)_. IEEE Computer Society, 2021, pp. 1–41.
  * [46] H. Liu and H. H. Huang, “Enterprise: breadth-first graph traversal on gpus,” in _Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis_ , 2015, pp. 1–12.
  * [47] R. Mahajan, R. Sankman, N. Patel, D.-W. Kim, K. Aygun, Z. Qian, Y. Mekonnen, I. Salama, S. Sharan, D. Iyengar _et al._ , “Embedded multi-die interconnect bridge (emib)–a high density, high bandwidth packaging interconnect,” in _2016 IEEE 66th Electronic Components and Technology Conference (ECTC)_. IEEE, 2016, pp. 557–565.
  * [48] A. Manocha, T. Sorensen, E. Tureci, O. Matthews, J. L. Aragón, and M. Martonosi, “Graphattack: Optimizing data supply for graph applications on in-order multicore architectures,” _ACM Transactions on Architecture and Code Optimization (TACO)_ , vol. 18, no. 4, pp. 1–26, 2021.
  * [49] M. McKeown, A. Lavrov, M. Shahrad, P. J. Jackson, Y. Fu, J. Balkind, T. M. Nguyen, K. Lim, Y. Zhou, and D. Wentzlaff, “Power and energy characterization of an open source 25-core manycore processor.” in _HPCA_ , 2018, pp. 762–775.
  * [50] R. Meade, S. Ardalan, M. Davenport, J. Fini, C. Sun, M. Wade, A. Wright-Gladstein, and C. Zhang, “Teraphy: a high-density electronic-photonic chiplet for optical i/o from a multi-chip module,” in _2019 Optical Fiber Communications Conference and Exhibition (OFC)_. IEEE, 2019, pp. 1–3.
  * [51] Micron, “High Bandwidth Memory with ECC,” 2018, https://media-www.micron.com/-/media/client/global/documents/products/data-sheet/dram/hbm2e/8gb_and_16gb_hbm2e_dram.pdf.
  * [52] R. C. Murphy, K. B. Wheeler, B. W. Barrett, and J. A. Ang, “Introducing the Graph 500,” http://www.graph500.org/specifications, Cray User’s Group (CUG), 2010.
  * [53] S. Naffziger, N. Beck, T. Burd, K. Lepak, G. H. Loh, M. Subramony, and S. White, “Pioneering chiplet technology and design for the amd epyc™ and ryzen™ processor families,” in _Proceedings of the 48th Annual International Symposium on Computer Architecture_ , ser. ISCA ’21. IEEE Press, 2021, p. 57–70.
  * [54] N. Nassif, A. O. Munch, C. L. Molnar, G. Pasdast, S. V. Lyer, Z. Yang, O. Mendoza, M. Huddart, S. Venkataraman, S. Kandula _et al._ , “Sapphire rapids: The next-generation intel xeon scalable processor,” in _2022 IEEE International Solid-State Circuits Conference (ISSCC)_ , vol. 65. IEEE, 2022, pp. 44–46.
  * [55] Q. M. Nguyen and D. Sanchez, “Pipette: Improving core utilization on irregular applications through intra-core pipeline parallelism,” in _2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)_. IEEE, 2020, pp. 596–608.
  * [56] 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_ , ser. MICRO ’21. New York, NY, USA: Association for Computing Machinery, 2021, p. 1064–1077. [Online]. Available: https://doi.org/10.1145/3466752.3480048
  * [57] C.-S. Oh, K. C. Chun, Y.-Y. Byun, Y.-K. Kim, S.-Y. Kim, Y. Ryu, J. Park, S. Kim, S. Cha, D. Shin _et al._ , “22.1 a 1.1 v 16gb 640gb/s hbm2e dram with a data-bus window-extension technique and a synergetic on-die ecc scheme,” in _2020 IEEE International Solid-State Circuits Conference-(ISSCC)_. IEEE, 2020, pp. 330–332.
  * [58] Open Compute Group, “Bunch of wires phy specification,” https://opencomputeproject.github.io/ODSA-BoW/bow_specification.html.
  * [59] M. Orenes-Vera, A. Manocha, J. Balkind, F. Gao, J. L. Aragón, D. Wentzlaff, and M. Martonosi, “Tiny but mighty: designing and realizing scalable latency tolerance for manycore socs.” in _ISCA_ , 2022, pp. 817–830.
  * [60] M. Orenes-Vera, E. Tureci, D. Wentzlaff, and M. Martonosi, “Dalorex: A data-local program execution and architecture for memory-bound applications,” _arXiv:2207.13219. To appear at the 29th IEEE International Symposium on High-Performance Computer Architecture (HPCA)_ , 2022\.
  * [61] Y. Ou, S. Agwa, and C. Batten, “Implementing low-diameter on-chip networks for manycore processors using a tiled physical design methodology,” in _2020 14th IEEE/ACM International Symposium on Networks-on-Chip (NOCS)_. IEEE, 2020, pp. 1–8.
  * [62] M. M. Ozdal, S. Yesil, T. Kim, A. Ayupov, J. Greth, S. Burns, and O. Ozturk, “Energy efficient architecture for graph analytics accelerators,” _ACM SIGARCH Computer Architecture News_ , vol. 44, no. 3, pp. 166–177, 2016.
  * [63] M. O’Connor, N. Chatterjee, D. Lee, J. Wilson, A. Agrawal, S. W. Keckler, and W. J. Dally, “Fine-grained dram: Energy-efficient dram for extreme bandwidth systems,” in _2017 50th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)_. IEEE, 2017, pp. 41–54.
  * [64] S. Pal, D. Petrisko, M. Tomei, P. Gupta, S. S. Iyer, and R. Kumar, “Architecting waferscale processors-a gpu case study,” in _2019 IEEE International Symposium on High Performance Computer Architecture (HPCA)_. IEEE, 2019, pp. 250–263.
  * [65] M.-J. Park, H. S. Cho, T.-S. Yun, S. Byeon, Y. J. Koo, S. Yoon, D. U. Lee, S. Choi, J. Park, J. Lee _et al._ , “A 192-gb 12-high 896-gb/s hbm3 dram with a tsv auto-calibration scheme and machine-learning-based layout optimization,” in _2022 IEEE International Solid-State Circuits Conference (ISSCC)_ , vol. 65. IEEE, 2022, pp. 444–446.
  * [66] A. Patrizio, “High-bandwidth memory (hbm) delivers impressive performance gains,” https://semiengineering.com/whats-next-for-high-bandwidth-memory/.
  * [67] J. T. Pawlowski, “Hybrid memory cube (hmc),” in _2011 IEEE Hot Chips 23 Symposium (HCS)_. IEEE, 2011, pp. 1–24.
  * [68] C. Premachandran, T. Tran-Quinn, L. Burrell, and P. Justison, “A comprehensive wafer level reliability study on 65nm silicon interposer,” in _2019 IEEE International Reliability Physics Symposium (IRPS)_ , 2019, pp. 1–8.
  * [69] V. Puente, R. Beivide, J. A. Gregorio, J. Prellezo, J. Duato, and C. Izu, “Adaptive bubble router: a design to improve performance in torus networks,” in _Proceedings of the 1999 International Conference on Parallel Processing_. IEEE, 1999, pp. 58–67.
  * [70] S. Rahman, N. Abu-Ghazaleh, and R. Gupta, “Graphpulse: An event-driven hardware accelerator for asynchronous graph processing,” in _2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)_. IEEE, 2020, pp. 908–921.
  * [71] A. Shah, “Chipmakers Looking at New Architecture to Drive Computing Ahead,” 2022, https://www.hpcwire.com/2022/11/23/chipmakers-looking-at-new-architecture-to-drive-computing-ahead/.
  * [72] D. D. Sharma, “Pci express 6.0 specification: A low-latency, high-bandwidth, high-reliability, and cost-effective interconnect with 64.0 gt/s pam-4 signaling,” _IEEE Micro_ , vol. 41, no. 1, pp. 23–29, 2020.
  * [73] D. D. Sharma, G. Pasdast, Z. Qian, and K. Aygun, “Universal chiplet interconnect express (ucie): An open industry standard for innovations with chiplets at package level,” _IEEE Transactions on Components, Packaging and Manufacturing Technology_ , vol. 12, no. 9, pp. 1423–1431, 2022.
  * [74] K. Shiba, T. Omori, K. Ueyoshi, S. Takamaeda-Yamazaki, M. Motomura, M. Hamada, and T. Kuroda, “A 96-mb 3d-stacked sram using inductive coupling with 0.4-v transmitter, termination scheme and 12: 1 serdes in 40-nm cmos,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , vol. 68, no. 2, pp. 692–703, 2020.
  * [75] G. M. Slota, S. Rajamanickam, and K. Madduri, “BFS and coloring-based parallel algorithms for strongly connected components and related problems,” in _2014 IEEE 28th International Parallel and Distributed Processing Symposium, Phoenix, AZ, USA, May 19-23, 2014_. IEEE Computer Society, 2014, pp. 550–559. [Online]. Available: https://doi.org/10.1109/IPDPS.2014.64
  * [76] K. Sohn, W.-J. Yun, R. Oh, C.-S. Oh, S.-Y. Seo, M.-S. Park, D.-H. Shin, W.-C. Jung, S.-H. Shin, J.-M. Ryu, H.-S. Yu, J.-H. Jung, H. Lee, S.-Y. Kang, Y.-S. Sohn, J.-H. Choi, Y.-C. Bae, S.-J. Jang, and G. Jin, “A 1.2 v 20 nm 307 gb/s hbm dram with at-speed wafer-level io test scheme and adaptive refresh considering temperature distribution,” _IEEE Journal of Solid-State Circuits_ , vol. 52, no. 1, pp. 250–260, 2017.
  * [77] A. Stillmaker and B. Baas, “Scaling equations for the accurate prediction of cmos device performance from 180 nm to 7 nm,” _Integration_ , vol. 58, pp. 74–81, 2017.
  * [78] D. Stow, Y. Xie, T. Siddiqua, and G. H. Loh, “Cost-effective design of scalable high-performance systems using active and passive interposers,” in _2017 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)_ , 2017, pp. 728–735.
  * [79] J. A. Stratton, C. Rodrigues, I.-J. Sung, N. Obeid, L.-W. Chang, N. Anssari, G. D. Liu, and W.-m. Hwu, “Parboil: A revised benchmark suite for scientific and commercial throughput computing,” University of Illinois at Urbana-Champaign, Tech. Rep. IMPACT-12-01, 2012.
  * [80] R. Swaminathan and J. Wuu, “Chiplet’s march to amd 3d v-cache and beyond,” 2022, https://www.opencompute.org/events/past-events/hipchips-chiplet-workshop-isca-conference.
  * [81] N. Talati, K. May, A. Behroozi, Y. Yang, K. Kaszyk, C. Vasiladiotis, T. Verma, L. Li, B. Nguyen, J. Sun, J. M. Morton, A. Ahmadi, T. Austin, M. O’Boyle, S. Mahlke, T. Mudge, and R. Dreslinski, “Prodigy: Improving the memory latency of data-indirect irregular workloads using hardware-software co-design,” in _2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA)_. IEEE, 2021, pp. 654–667.
  * [82] E. Talpes, D. Williams, and D. D. Sarma, “Dojo: The microarchitecture of tesla exa-scale computer,” in _2022 IEEE Hot Chips 34 Symposium (HCS)_. IEEE Computer Society, 2022, pp. 1–28.
  * [83] T. Tang and Y. Xie, “Cost-aware exploration for chiplet-based architecture with advanced packaging technologies,” _arXiv preprint arXiv:2206.07308_ , 2022.
  * [84] Y. Tian, A. Balmin, S. A. Corsten, S. Tatikonda, and J. McPherson, “From” think like a vertex” to” think like a graph”,” _Proceedings of the VLDB Endowment_ , vol. 7, no. 3, pp. 193–204, 2013.
  * [85] P. Vivet, E. Guthmuller, Y. Thonnart, G. Pillonnet, C. Fuguet, I. Miro-Panades, G. Moritz, J. Durupt, C. Bernard, D. Varreau, J. Pontes, S. Thuries, D. Coriat, M. Harrand, D. Dutoit, D. Lattard, L. Arnaud, J. Charbonnier, P. Coudrain, A. Garnier, F. Berger, A. Gueugnot, A. Greiner, Q. L. Meunier, A. Farcy, A. Arriordaz, S. Chéramy, and F. Clermidy, “Intact: A 96-core processor with six chiplets 3d-stacked on an active interposer with distributed interconnects and integrated power management,” _IEEE Journal of Solid-State Circuits_ , vol. 56, no. 1, pp. 79–97, 2021.
  * [86] Y. Wang, A. Davidson, Y. Pan, Y. Wu, A. Riffel, and J. D. Owens, “Gunrock: A high-performance graph processing library on the gpu,” in _Proceedings of the 21st ACM SIGPLAN symposium on principles and practice of parallel programming_ , 2016, pp. 1–12.
  * [87] J. Wilson, “High-bandwidth density, energy-efficient, short-reach signaling that enables massively scalable parallelism,” 2022, https://www.opencompute.org/events/past-events/hipchips-chiplet-workshop-isca-conference.
  * [88] Q. Xie, X. Lin, Y. Wang, S. Chen, M. J. Dousti, and M. Pedram, “Performance comparisons between 7-nm finfet and conventional bulk cmos standard cell libraries,” _IEEE Transactions on Circuits and Systems II: Express Briefs_ , vol. 62, no. 8, pp. 761–765, 2015.
  * [89] Y. Yokoyama, M. Tanaka, K. Tanaka, M. Morimoto, M. Yabuuchi, Y. Ishii, and S. Tanaka, “A 29.2 mb/mm2 ultra high density sram macro using 7nm finfet technology with dual-edge driven wordline/bitline and write/read-assist circuit,” in _2020 IEEE Symposium on VLSI Circuits_ , 2020, pp. 1–2.
  * [90] F. Zaruba and L. Benini, “The cost of application-class processing: Energy and performance analysis of a linux-ready 1.7-ghz 64-bit risc-v core in 22-nm fdsoi technology,” _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ , vol. 27, no. 11, pp. 2629–2640, Nov 2019, https://github.com/openhwgroup/cva6.
  * [91] F. Zaruba and L. Benini, “Ariane: An open-source 64-bit RISC-V application class processor and latest improvements,” 2018, technical talk at the RISC-V Workshop https://www.youtube.com/watch?v=8HpvRNh0ux4.
  * [92] F. Zaruba, F. Schuiki, and L. Benini, “Manticore: A 4096-core risc-v chiplet architecture for ultraefficient floating-point computing,” _IEEE Micro_ , vol. 41, no. 2, pp. 36–42, 2020.
  * [93] F. Zaruba, F. Schuiki, T. Hoefler, and L. Benini, “Snitch: A tiny pseudo dual-issue processor for area and energy efficient execution of floating-point intensive workloads,” _IEEE Transactions on Computers_ , 2020\.
  * [94] M. Zhang, Y. Zhuo, C. Wang, M. Gao, Y. Wu, K. Chen, C. Kozyrakis, and X. Qian, “Graphp: Reducing communication for pim-based graph processing with efficient data partition,” in _2018 IEEE International Symposium on High Performance Computer Architecture (HPCA)_. IEEE, 2018, pp. 544–557.
  * [95] Y. Zhu, B. Wang, D. Li, and J. Zhao, “Integrated thermal analysis for processing in die-stacking memory,” in _Proceedings of the Second International Symposium on Memory Systems_ , 2016, pp. 402–414.
  * [96] Y. Zhuo, C. Wang, M. Zhang, R. Wang, D. Niu, Y. Wang, and X. Qian, “Graphq: Scalable pim-based graph processing,” in _Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture_ , 2019, pp. 712–725.