* (152) D. Zhang, N. Jayasena, A. Lyashevsky, J. L. Greathouse, L. Xu, and M. Ignatowski, “TOP-PIM: Throughput-Oriented Programmable Processing in Memory,” in _HPDC_ , 2014.
  * (153) Q. Zhu, T. Graf, H. E. Sumbul, L. Pileggi, and F. Franchetti, “Accelerating Sparse Matrix-Matrix Multiplication with 3D-Stacked Logic-in-Memory Hardware,” in _HPEC_ , 2013.
  * (154) W. Zuravleff and T. Robinson, “Controller for a Synchronous DRAM That Maximizes Throughput by Allowing Memory Requests and Commands to Be Issued Out of Order,” U.S. Patent No. 5,630,096, 1997.

Figure 16. Synthesizing SIMDRAM circuit for a full addition.

APPENDIX

##  Appendix A AIG-to-MIG Conversion

The conversion from AND/OR/NOT representation of an operation to its MAJ/NOT
representation relies on a set of transformation rules that are derived from
the characteristics of the MAJ operation. Table 4 lists the set of
transformation rules that we use to synthesize a circuit for a desired
operation with MAJ and NOT gates. We use full addition as a running example to
describe the process of synthesizing a MAJ/NOT-based circuit, starting from an
AND/OR/NOT representation of the circuit and using the transformation rules.
We obtain MAJ/NOT-based circuits for other SIMDRAM operations following the
same method. In a later step (section 4.2), we translate a MAJ/NOT-based
circuit to sequences of AAPs/APs operations.

Table 4. MAJ/NOT transformation Rules (epflmaj, ).

Commutativity (C) | $M(x,y,z)=M(y,x,z)=M(z,y,x)$
---|---
Majority (M) |  if$(x=y):M(x,y,z)=x=y$
if$(x=\overline{y}):M(x,y,z)=z$
Associativity (A) | $M(x,u,M(y,u,z))=M(z,u,M(y,u,x))$
Distributivity (D) | $M(x,y,M(u,v,z))=M(M(x,y,u),M(x,y,v),z)$
Inverter Propagation (I) | $\overline{M}(x,y,z)=M(\overline{x},\overline{y},\overline{z})$
Relevance (R) | $M(x,y,z)=M(x,y,\mathbf{z}_{x/\overline{y}})$
Complementary Associativity (CA) | $M(x,u,M(y,\overline{u},z))=M(x,u,M(y,x,z))$

Fig. 16a shows the optimized AND/OR/Inverter (i.e., AND/OR/NOT) Graph (AOIG)
representation of a full addition (i.e., F = A + B + Cin). As shown in Fig.
16b, the naive way to transform the AOIG to a Majority/Inverter (i.e.,
MAJ/NOT) Graph (MIG) representation, is to replace every AND and OR primitive
with a three-input MAJ primitive where the third input is 0 or 1,
respectively. The resulting MIG is in fact Ambit’s (seshadri2017ambit, )
representation of the full addition. While the AOIG in Fig. 16a is optimized
for AND/OR/NOT operations, the resulting MIG in Fig. 16b can be further
optimized by exploiting the transformation rules of the MAJ primitive (Table
4, replicated from (epflmaj, )). The MIG optimization is performed in two key
steps: (1) node reduction, and (2) MIG reshaping.

Node reduction. In order to optimize the MIG in Fig. 16b, the first step is to
reduce the number of MAJ nodes in the MIG. As shown in Table 1, rules M and D
reduce the number of nodes in a MIG if applied from left to right (i.e.,
$\mathbf{M}_{L\rightarrow{R}}$) and from right to left (i.e.,
$\mathbf{D}_{R\rightarrow{L}}$), respectively. $\mathbf{M}_{L\rightarrow{R}}$
replaces a MAJ node with a single value, and $\mathbf{D}_{R\rightarrow{L}}$
replaces three MAJ nodes with two MAJ nodes in the MIG. The node reduction
step applies $\mathbf{M}_{L\rightarrow{R}}$ and $\mathbf{D}_{R\rightarrow{L}}$
as many times as possible to reduce the the number of MAJ operations in the
MIG. We can see in Fig. 16b that none of the two rules are applicable in the
particular case of the full addition MIG. Therefore, Fig 16b remains unchanged
after applying node reduction.

MIG reshaping. When no further node reduction is possible, we _reshape_ the
MIG in an effort to enable more node reduction opportunities by repeatedly
using two sets of rules: (1) rules $\mathbf{M}_{R\rightarrow{L}}$,
$\mathbf{D}_{L\rightarrow{R}}$, and R to temporarily inflate the MIG and
create more node reduction opportunities with the help of the new nodes, and
(2) rules A and CA, to exchange variables between adjacent nodes. Note that in
this step, rules M and D are applied in the reverse direction compared to the
previous step (i.e., node reduction step) which results in increasing the
number of nodes in the MIG. We now describe the MIG reshaping process for the
full addition example (Fig. 16b). For simplicity, we first assume that the
entire MIG is represented as function F that computes the full addition of the
input operands A and B. Then, we apply rule $\mathbf{M}_{R\rightarrow{L}}$
while introducing variable X to the MIG (as $F=M(F,x,\overline{x})$) without
impacting the functionality of the MIG (Fig. 16c). We then apply the same rule
again, and replace X with a new MAJ node while introducing variable Y (Fig.
16d). Next, by applying rule $\mathbf{D}_{L\rightarrow{R}}$, we introduce a
new MAJ node and distribute the function F across the two MAJ nodes (Fig.
16e). Now, by applying rule R to the function F on the left, variable
${\overline{\textbf{X}}}$ is replaced with variable $\overline{\textbf{Y}}$ in
the function F on the left. Similarly, by applying rule R to the function F on
the right, variable ${\overline{\textbf{X}}}$ is replaced with variable Y in
the function F on the right (Fig. 16f). At this point, since rule
$\mathbf{M}_{R\rightarrow{L}}$ holds with any given two variables, we can
safely replace X and Y with variables A and B, respectively (Figure 16g).
Next, we expand function F (Fig. 16h) and the variables replaced as a result
of the previous rule are highlighted in blue. As shown in Fig. 16h, the
resulting graph after expanding function F has multiple node reduction
opportunities using rule $\mathbf{M}_{L\rightarrow{R}}$ and starting from the
top of the graph. The nodes that can be eliminated using this rule are marked
in red and the replacing value is indicated with a red arrow leaving the node.
Fig. 16i shows the same MIG after resolving all the node reductions. We next
use rule I to remove all three NOT primitives in the rightmost MAJ node. The
final optimized MIG that is shown in Figure 16j requires only 3 MAJ primitives
to perform the full addition operation, as opposed to the 6 we started with
(in Fig. 16b).

The node reduction step followed by the MIG reshaping step are repeated (for a
predefined number of times) until we achieve an optimized MIG that requires
minimal number of MAJ operations to perform the desired in-DRAM operation. The
process of converting an operation to a MAJ-based implementation can be
automated as suggested by prior work (epflmaj, ; soeken2016mig, ).

##  Appendix B Row-to-Operand Allocation

Algorithm 1 describes SIMDRAM’s row-to-operand allocation procedure. To enable
in-DRAM computation, our allocation algorithm copies (i.e., maps) input
operands for each MAJ node in the MIG from D-group rows (where the operands
normally reside) into compute rows. However, due to the limited number of
compute rows, the allocation algorithm cannot allocate DRAM rows to all input
operands from all MAJ nodes at once. To address this issue, the allocation
algorithm divides the allocation process into _phases_. Each phase allocates
as many compute rows to operands as possible. For example, because no rows are
allocated yet, the initial phase (Phase 0) has all six compute rows available
for allocation (i.e., the rows are vacant), and can allocate up to six input
operands to the compute rows. A phase is considered finished when either (1)
there are not enough vacant compute rows to allocate all input operands for
the next logic primitive that needs to be computed, or (2) there are no more
MAJ primitives left to process in the MIG. The phase information is used when
generating the µProgram for the MIG in Task 2 of Step 2 of SIMDRAM framework
(section 4.2.3), where µOps for all MAJ primitives in phase $i$ are generated
prior to the MAJ primitives in phase $i+1$. Knowing that all the MAJ
primitives in phase $i$ are performed before the next phase $i+1$ starts, the
allocation algorithm can safely reuse the compute rows for use in phase $i+1$,
without worrying about the output of a MAJ primitive being overwritten by a
new row-to-operand allocation.

We now describe the row-to-operand allocation algorithm in detail, using the
MIG for full addition in Fig. 5a as an example of a MIG being traversed by the
algorithm. The allocation algorithm starts at Phase 0. Throughout its
execution, the algorithm maintains (1) the list of free compute rows (rows in
the B-group of the subarray, shown in Fig. 2) that are available for
allocation (_B_rows_ and _B_rows_DCC_ in Algorithm 1, initialized in lines
3–4); and (2) the list of row-to-operand allocations associated with each MAJ
node, tagged with the phase number that the allocations were performed in
(_row_operand_allocation_ in Algorithm 1). Once a row-to-operand allocation is
performed, the algorithm removes the compute row used for the allocation from
the list of the free compute rows, and adds the new allocation to the list of
row-to-operand allocations generated in that phase for the corresponding MAJ
node. The algorithm follows a simple procedure to allocate compute rows to the
input operands of the MAJ nodes in the MIG. The algorithm does a topological
traversal starting with the leftmost MAJ node in the highest level of the MIG
(e.g., Level 0 in Fig. 5a), and traverses all the MAJ nodes in each level,
before moving to the next lower level of the graph.

Algorithm 1 SIMDRAM’s Row-to-Operand Allocation Algorithm.

1:Input: MIG G = (V, E) $\triangleright$ Majority-Inverter Graph G nodes
¡vertex, edge¿

2:Output: row_operand_allocation $\triangleright$ Allocation map of rows to
operands

3:B_rows $\leftarrow$ {T0, T1, T2, T3}

4:B_rows_DCC $\leftarrow$ {DCC0, DCC1}

5:phase $\leftarrow$ 0

6:row_operand_allocation_map $\leftarrow\emptyset$

7:for each level in G do

8: for each V in G[level] do

9: for each input edge in E[V] do

10: Search for input edge’s parent

11: if input edge has no parents then

12: if input edge is negated then

13: Allocate row in B_rows_DCC to input edge

14: Remove allocated row from B_rows_DCC

15: else

16: Allocate row in B_rows to input edge

17: Remove allocated row from B_rows

18: else

19: if input edge is negated then

20: Map allocated parent row in B_rows_DCC to input edge

21: else

22: Map allocated parent row in B_rows to input edge

23: if B_rows and B_rows_DCC are empty then

24: phase $\leftarrow$ phase + 1

25: B_rows $\leftarrow$ {T0, T1, T2, T3}

26: B_rows_DCC $\leftarrow$ {DCC0, DCC1}

27: row_operand_allocation $\leftarrow$ (input edge, allocated row, phase)

Case 1

Case 2

Case 3

For each of the three input edges (i.e., operands) of any given MAJ node, the
algorithm checks for the following three possible cases and performs the
allocation accordingly:

Case 1: if the edge is not connected to another MAJ node in a higher level of
the graph (line 11 in Algorithm 1), i.e., the edge does not have a parent
(e.g., the three edges entering the blue node in Fig. 5a), and a compute row
is available, the input operand associated with the edge is considered to be a
source input, and is currently located in the D-group rows of the subarray. As
a result, the algorithm copies the input operand associated with the edge from
its D-group row to the first available compute row. Note that if the edge _is_
complemented, i.e., the input operand is negated (e.g., the edge with operand
A for the blue node in Fig. 5a), the algorithm allocates the first available
compute row with dual contact cells (DCC0 or DCC1) to the input operand of the
edge (lines 12–14 in Algorithm 1). If the edge is _not_ complemented (e.g.,
the edge with operand B for the blue node in Fig. 5a), a regular compute row
is allocated to the input operand (lines 15–17 in Algorithm 1).

Case 2: if the edge is connected to another MAJ node in a higher level of the
graph (line 18 in Algorithm 1), the edge has a parent node and the value of
the input operand associated with the edge equals the result of the parent
node, which is available in the compute rows that hold the result of the
parent MAJ node. As a result, the algorithm maps the input operand of the edge
to a compute row that holds the result of its parent node (lines 19–22 in
Algorithm 1).

Case 3: if there are no free compute rows available, the algorithm considers
the phase as _complete_ and continues the allocations in the next phase (lines
23–26 in Algorithm 1).

Once DRAM rows are allocated to all the edges connected to a MAJ node, the
algorithm stores the row-to-operand allocation information of the three input
operands of the MAJ node in _row_operand_allocation_ (line 27 in Algorithm 1)
and associates this information with the MAJ node and the phase number that
the allocations were performed in. The algorithm finishes once DRAM rows are
allocated to _all_ the input operands of all the MAJ nodes in the MIG. Fig. 5b
shows these allocations as the output of Task 1 for the full addition example.
The resulting _row_operand_allocation_ is then used in Task 2 of Step 2 of the
SIMDRAM framework (section 4.2.3) to generate the series of µOps to compute
the operation that the MIG represents.

##  Appendix C Scalability of Operations

Table 5 lists the semantics and the total number of AAP/APs required for each
of the 16 SIMDRAM operations that we evaluate in this paper (section 7) for
input element(s) of size $n$. Each operation is classified based on how the
latency of the operation scales with respect to the element size $n$. Class 1,
2, and 3 operations scale linearly, logarithmically,and quadratically with
$n$, respectively.

Table 5. Evaluated SIMDRAM operations (for $n$-bit data).

Type | Operation | # AAPs/APs | Class | Semantics
---|---|---|---|---
Arithmetic | abs | $10n-2$ | Linear | $dst=(src>0)?\ src:-(src)$
addition | $8n+1$ | Linear | $dst=src_{1}+src_{2}$
bitcount | $\Omega=8n-8\log_{2}(n+1)$ | Linear | $\sum_{i=0}^{n}src(i)$
$O=8n$
division | $8n^{2}+12n$ | Quadratic | $dst=\frac{src_{1}}{src_{2}}$
max | $10n+2$ | Linear | $dst=(src_{1}>src_{2})?\ src_{1}:src_{2}$
min | $10n+2$ | Linear | $dst=(src_{1}<src_{2})?\ src_{1}:src_{2}$
multiplication | $11n^{2}-5n-1$ | Quadratic | $dst=src_{1}\times src_{2}$
ReLU | $3n+((n-1)\ mod\ 2)$ | Linear | $dst=(src\geq 0)?\ src:0$
subtraction | $8n+1$ | Linear | $dst=src_{1}-src_{2}$
Predication | if_else | $7n$ | Linear | $dst=(sel)?\ src_{1}:src_{2}$
Reduction | and_reduction | $5\lfloor\frac{n}{2}\rfloor+2$ | Logarithmic | $Y=src(1)\wedge src(2)\wedge src(3)$
or_reduction | $5\lfloor\frac{n}{2}\rfloor+2$ | Logarithmic | $Y=src(1)\vee src(2)\vee src(3)$
xor_reduction | $6\lfloor\frac{n}{2}\rfloor+1$ | Logarithmic | $Y=src(1)\oplus src(2)\oplus src(3)$
Relational | equal | $4n+3$ | Linear | $dst=(src_{1}==src_{2})$
greater | $3n+2$ | Linear | $dst=(src_{1}>src_{2})$
greater_equal | $3n+2$ | Linear | $dst=(src_{1}\geq src_{2})$

##  Appendix D Evaluated Real-World Applications

Convolutional Neural Networks (CNNs). CNNs (rastegari2016xnor, ; he2020sparse,
; krizhevsky2012imagenet, ) are used in many classification tasks such as
image and handwriting classification. CNNs are often computationally intensive
as they use many general-matrix-multiplication (GEMM) operations using
floating-point operations for each convolution. Prior works
(rastegari2016xnor, ; lin2017towards, ; he2020sparse, ) demonstrate that
instead of the costly floating-point multiplication operations, convolutions
can be performed using a series of bitcount, addition, shift, and XNOR
operations. In this work, we use the XNOR-NET (rastegari2016xnor, )
implementations of VGG-13, VGG-16, and LeNET provided by (he2020sparse, ), to
evaluate the functionality of SIMDRAM. We modify these implementations to make
use of SIMDRAM’s bitcount, addition, shift, and XNOR operations. We evaluate
all three networks for inference using two different datasets: VGG-13 and
VGG-16 (using CIFAR-10 (krizhevsky2010convolutional, )), and LeNet-5 (using
MNIST (deng2012mnist, )).

k-Nearest Neighbor Classifier (kNN). We use a kNN classifier to solve the
handwritten digits recognition problem (Lecun95learningalgorithms, ). The kNN
classifier finds a group of k objects in the input set using a simple distance
algorithm such as Euclidean distance (friedman2001elements, ). In our
evaluations, we use SIMDRAM to implement the Euclidean distance algorithm
entirely in DRAM. We evaluate a kNN algorithm using the MNIST dataset
(deng2012mnist, ) with 3000 training images and 1000 testing images. We
quantize the inputs using an 8-bit representation.

Database. We evaluate SIMDRAM using two different database workloads. First,
we evaluate a simple table scan query ‘select count(*) from T where c1 <= val
<= c2’ using the BitWeaving algorithm (li2013bitweaving, ). Second, we
evaluate the performance of the TPC-H (tpch, ) scheme using query 01, which
executes many arithmetic operations, including addition and multiplication.
For our evaluation, we follow the column-based data layout employed in
(santos2017operand, ) and use a scale factor of 100.

Brightness. We use a simple image brightness algorithm (foley1996computer, )
to demonstrate the benefits of the SIMDRAM predication operation. The
algorithm evaluates if a given brightness value is larger than 0. If so, it
increases the pixel value of the image by the brightness value. Before
assigning the new brightness value to the pixel, the algorithm verifies if the
new pixel value is between 0 and 255. In our SIMDRAM implementation, we use
both addition and predication operations.