#  Implementing CNN Layers on the Manticore Cluster-Based Many-Core
Architecture
Technical Report Implementing CNN Layers on the Manticore Cluster-Based Many-
Core Architecture

Andreas Kurth, Fabian Schuiki, and Luca Benini
Digital Circuits and Systems Group, ETH Zurich Andreas Kurth, Fabian Schuiki,
and Luca Benini

(v1.0, April 2021)

## Abstract

This document presents implementations of fundamental convolutional neural
network (CNN) layers on the Manticore cluster-based many-core architecture and
discusses their characteristics and trade-offs.

##  1 Introduction

Figure 1: Conceptual floorplan of Manticore’s package (left) and an individual
chiplet (right) [1].

The _Manticore_ architecture [1] is a many-core processor designed for high-
performance, high-efficiency data-parallel floating-point computing. The
implementation proposed in [1] consists of four chiplets on an interposer, see
Fig. 1. Each chiplet contains 1024 cores grouped into 128 clusters, one
$8\text{\,}\mathrm{GiB}\text{/}$ HBM2E controller and PHY, as well as L2
memory and I/Os to connect to the other chiplets.

Figure 2: Simplified block diagram of a Manticore cluster [1].

Each cluster, shown in Fig. 2, contains eight small 32-bit integer RISC-V
cores [2], each paired with a large double-precision floating-point unit (FPU)
[3], and $128\text{\,}\mathrm{KiB}\text{/}$ of tightly-coupled L1 scratchpad
memory (SPM) organized in 32 banks of $64\text{\,}\mathrm{bit}\text{/}$ width
each. The FPU is capable of computing one double-precision floating-point
multiply-and-accumulate (MAC) operation or two single-precision MAC operations
in each clock cycle. As primary means for moving data into and out of L1, each
cluster contains two 512-bit-wide direct memory access (DMA) engines [4,
Section 2.5] – one for reads and one for writes – which are attached to the L1
memory and share one master port into the on-chip network. DMA engines in
other clusters can access the L1 memory through an additional 512-bit-wide
slave port. Each cluster has a 64-bit master port to let its cores access
external memory and a 64-bit slave port to let cores in other clusters access
its L1 memory. Four clusters form an L1 quadrant, four L1 quadrants form an L2
quadrant, four L2 quadrants form an L3 quadrant, and two L3 quadrants form a
chiplet.

Figure 3: On-chip network of one Manticore chiplet, adapted from [4, Section
4].

Manticore’s on-chip network [4, Section 4], shown in Fig. 3, features:

  1. (1)

physically separate networks for traffic by DMA engines and cores to minimize
the interference between the wide bursts of DMA engines and the word-wise
accesses of the cores;

  2. (2)

a tree topology to combine a high bandwidth between off-chip main memory and
any cluster for effective data transfers and low latency between any two cores
for efficient concurrency;

  3. (3)

fully-connected crossbars within each quadrant to provide units within the
same quadrant with a high bandwidth for effective local data sharing; and

  4. (4)

the same data width and frequency throughout the DMA network to provide a high
bandwidth between off-chip main memory and any clusters.

This document describes the implementation of convolutional and fully-
connected layers, which together account for $95\text{\,}\mathrm{\char
37\relax}\text{/}99\text{\,}\mathrm{\char 37\relax}\text{/}$ of the floating-
point operations in convolutional neural networks (CNNs), on a Manticore
chiplet.

###  1.1 Convolutional Neural Networks (CNNs)

We follow the notation used in Stanford University’s “CS231n Convolutional
Neural Networks for Visual Recognition” [5, Module 2: CNNs]. There is no
single established convention on describing neural networks, but adapting the
notation of a course rather than that of a specific paper in the field
hopefully makes this document understandable for a wide range of readers.

Figure 4: A convolutional neural network (CNN)with its input layer in red on
the left, two hidden layers in blue in the middle, and its output layer in
green on the right [5]. Every layer of a CNN transforms a 3D input volume of
neuron activations to a 3D output volume of neuron activations. The neurons of
each layer are arranged in three dimensions: width, height, and depth.

A CNN is generally a sequence of layers, and each _layer_ transforms one
three-dimensional _volume_ of activations to another three-dimensional volume
of activations. The layers of a CNN, shown in Fig. 4, have neurons arranged in
three dimensions: width, height, and depth. _Width_ and _height_ are the
_spatial dimensions_ , and _depth_ is the third dimension of a layer (and not
the number of layers in a network).

The neurons in convolutional and fully-connected layers are also called
_filter parameters_ , because they are the parameters of mathematical filters
that are applied to transform an input volume to an output volume.

The _hyperparameters_ of a layer, listed in Table 1, describe the shape of its
input and output volumes and how its filter is applied.

$W_{I}$ | width and height of input volume
---|---
$D_{I}$ | depth of input volume
$W_{O}$ | width and height of output volume
$D_{O}$ | depth of output volume
$F$ | receptive field (i.e., width and height) of the filter
$P$ | zero padding elements in the spatial dimensions
$S$ | stride of the filter
$B$ | batch size
Table 1: Hyperparameters of CNN layers.

A convolutional layer transforms an input volume $\mathbf{I}[W_{I}\times
W_{I}\times D_{I}]$ (i.e., of width and height $W_{I}$ and depth $D_{I}$) to
an output volume $\mathbf{O}[W_{O}\times W_{O}\times D_{O}]$. It does this
transformation by convolving every two-dimensional _depth slice_ (i.e., a
matrix with $W_{I}$ rows and columns) of the input volume with a two
dimensional filter kernel (i.e., a matrix with $F$ rows and columns) to
produce one two-dimensional depth slice (i.e., a matrix with $W_{O}$ rows and
columns) of the output volume. Each pair of input and output depth slice has
its own filter kernel. The overall filter parameters of one layer (also known
as the neurons of the convolutional layer) are thus $\mathbf{F}[F\times
F\times D_{I}\times D_{O}]$. Before the convolution with the filter kernel,
each input depth slice is _padded_ with $P$ zeros at the beginning and end of
each row and column. The convolutional filter is then applied with a _stride_
$S$, i.e., to every $S$-th row and column. The width and height of the output
volume are thus given by $W_{O}=(W_{I}+2P-F)/S+1$.

A fully-connected layer transforms an input volume $\mathbf{I}[W_{I}\times
W_{I}\times D_{I}]$ to an output volume $\mathbf{O}[1\times 1\times D_{O}]$.
Any fully-connected layer can be represented as convolutional layer by setting
$F=W_{I}$ (and $S=1$, $P=0$), so the filter parameters of a convolutional
layer are $\mathbf{F}[W_{I}\times W_{I}\times D_{I}\times D_{O}]$.

###  1.2 Notation

####  1.2.1 Algorithms

For loops are written as “for $\mathit{var}\leftarrow\mathit{lb}$ to
$\mathit{ub}$ do $\mathit{body}$ end”, where the loop variable $\mathit{var}$
is initialized to $\mathit{lb}$ and is incremented in each iteration by one.
The loop $\mathit{body}$ is executed as long as $\mathit{var}<\mathit{ub}$.

For loops executed in parallel by all clusters start with “parallelize for”
and their loop header ends with “over clusters do”. The schedule of the
parallelization is not restricted and may be optimized by the compiler, the
runtime environment (RTE), or both. In this document, we do not detail
parallel execution _within_ clusters.

Indices into multi-dimensional volumes are written in square brackets with
dimensions separated by commas (e.g., $[a,b,c]$), where the innermost
dimension is on the left and the outermost dimension is on the right. Indexing
starts at zero. A range of indexes is written with a colon, e.g., $[d:e]$ is a
one-dimensional range including all elements starting at $d$ and ending before
$e$, i.e., $\\{n\in\mathbb{N}\mid d\leq n<e\\}$. A range without start and
end, such as $[:]$, includes all elements in a dimension.

Data is loaded from main memory into cluster local memory and stored back
primarily through DMA engine transfers. Such loads and stores are denoted with
DmaLoad(__) and DmaStore(__) , respectively. DMA engine transfers run
asynchronous to computation. That is, the cores of the cluster can continue to
compute while the DMA engine transfers data. Of course, the cores can only
compute on data in local memory that has already been transferred. To ensure
synchronization between cores and DMA engine where necessary, the DmaWait(__)
function blocks until the data given in the argument is completely
transferred.

Each cluster has a constant, unique numerical ID. Numbering starts at $0$ for
the first cluster in the first L1 quadrant of the first L2 quadrant of the
first L3 quadrant. The next cluster cluster in that same L1 quadrant has ID
$1$, the first cluster in the next L1 quadrant of the same L2 quadrant has ID
$4$, and so on. The cluster ID is denoted as $\mathit{CID}$.

####  1.2.2 Units

Single- and double-precision floating-point numbers and operations according
to IEEE 754 are both supported by Manticore. In this document, we assume that
all numbers in a layer have either single- or double-precision. This allows
for a generic discussion where each number is a _word_. A single-precision
word is $4\text{\,}\mathrm{B}\text{/}$ (four byte) in size, and a double-
precision word is $8\text{\,}\mathrm{B}\text{/}$ (eight byte) in size.

The main compute operation in CNN layers are _multiply-and-accumulates
(MACs)_. We count one MAC as two floating-point operations (since it consists
of one multiplication and one addition). An operation on single-precision
numbers is called _single-precision floating-point operation (
$\mathrm{spflop}\text{/}$)_, and an operation on double-precision numbers is
called _double-precision floating-point operation (
$\mathrm{dpflop}\text{/}$)_.

##  2 Convolutional Layers

###  2.1 Parallelize Output Depth Slices over Clusters

Input: $\mathbf{I}[W_{I}\times W_{I}\times D_{I}]$ input volume

Input: $\mathbf{F}[F\times F\times D_{I}\times D_{O}]$ filter parameters

Output: $\mathbf{O}[W_{O}\times W_{O}\times D_{O}]$ output volume

parallelize for  _$d_{o}\leftarrow 0$ to $D_{O}$_ over clusters do

initialize $\mathbf{O}[:,:,d_{o}]$ in local memory to zero;

DmaLoad(_$\mathbf{I}[:,:,0]$_) from main memory;

DmaLoad(_$\mathbf{F}[:,:,0,d_{o)}]$_) from main memory;

for  _$d_{i}\leftarrow 0$ to $D_{I}$_ do

if  _$d_{i}+1 <D_{I}$_ then

DmaLoad(_$\mathbf{I}[:,:,d_{i}+1]$_) from main memory;

DmaLoad(_$\mathbf{F}[:,:,d_{i}+1,d_{o)}]$_) from main memory;

end if

DmaWait(_$\mathbf{I}[:,:,d_{i}]$_);

DmaWait(_$\mathbf{F}[:,:,d_{i},d_{o)}]$_);

$\mathbf{O}[:,:,d_{o}]$ $\mathrel{+}=$ Conv(_$\mathbf{I}[:,:,d_{i}]$ ,
$\mathbf{F}[:,:,d_{i},d_{o}]$_);

end for

DmaStore(_$\mathbf{O}[:,:,d_{o}]$_) to main memory;

end

Algorithm 1 Implementation of a convolutional layer where the depth slices of
the output volumes are parallelized over the clusters.

The implementation of a convolutional layer shown in Algorithm 1 parallelizes
the output depth slices over the clusters. In the parallel section, the
cluster first initializes the output depth slice in its local memory to zero
and then loops over the input depth slices. Within that loop, the cluster
loads the input depth slice and the filter parameters for the current pair of
input and output depth slices from main memory.111The loading of input data is
split into two parts: Before the loop over the input depth slices, the data
for the first iteration of the loop is loaded. Within the loop, the data for
the subsequent iteration of the loop is loaded (except for the last
iteration). The calls to DmaWait(__) make sure that the data for the current
iteration is present in local memory before the computation.  Then the cluster
convolves the input depth slice with the filter parameters and accumulates the
result to the output depth slice in local memory. After it has looped over all
input depth slices, the cluster stores the output depth slice to main memory.

This implementation exploits the independence of the output depth slices,
necessitating no communication between the clusters.

The main drawback of this implementation is that each cluster loads all input
depth slices for each output depth slice it processes, because it cannot store
the entire input volume in local memory. This leads to a lot of data loaded
over and over again, which significantly reduces the compute-to-communication
ratio (CCR) and causes the implementation to become memory-bound. The
implementation in Section 2.2 will resolve this limitation by processing
output depth slices in stacks.

####  2.1.1 Compute Complexity

The convolution (Conv(__)) does $W_{I}\cdot W_{I}\cdot F^{2}$ MACs, and it is
placed inside a loop with $D_{I}$ iterations. In total, each cluster task does
$W_{I}^{2}\cdot F^{2}\cdot D_{I}$ MACs. Together, the clusters do
$W_{I}^{2}\cdot F^{2}\cdot D_{I}\cdot D_{O}$ MACs.

####  2.1.2 Space Complexity

Each cluster must store:

  1. (1)

its output depth slice, which are $W_{O}^{2}$ words;

  2. (2)

one input depth slice, which are $W_{I}^{2}$ words;

  3. (3)

the filter parameters for one input-output depth slice pair, which are $F^{2}$
words.

Thus, the minimum local memory required per cluster is
$W_{O}^{2}+W_{I}^{2}+F^{2}$ words. For a typical layer with $W_{I}=32$, $F=3$,
and $W_{O}=32$ (due to $S=1$ and $P=1$), this corresponds to $2057$ words, or
less than $8.1\text{\,}\mathrm{KiB}\text{/}$ for single-precision and
$16.1\text{\,}\mathrm{KiB}\text{/}$ for double-precision data. Both easily fit
into the $128\text{\,}\mathrm{KiB}\text{/}$ of local memory of each cluster.

Beyond the minimum local memory requirements, additional storage can be
required to hide the latency of loads from off-chip main memory. Especially
the input depth slice (2) and the filter parameters (3), which are loaded once
per inner loop iteration, can benefit from a buffer. The size of that buffer
depends on the latency to the main memory. Assuming a round-trip latency of
256 clock cycles and a data bus width of
$$512\text{\,}\mathrm{bit}\text{/}$=$64\text{\,}\mathrm{B}\text{/}$$, up to
$16\text{\,}\mathrm{KiB}\text{/}$ can be in transfer in the on-chip network. A
buffer of the same size can be added for output depth slice (1), so that data
transfers by the DMA engine run fully in background.222The DMA transfer buffer
could be shared by the input depth slices and the filter parameters, since the
total amount of data in transfer in the on-chip network does not depend on the
type of data being transferred. This would save local memory in the cluster,
but it requires the RTE to dynamically partition the DMA transfer buffer
between different data types and variables, which is not trivial. We therefore
do not assume this RTE capability.  In total, roughly
$48\text{\,}\mathrm{KiB}\text{/}$ are required as buffers.

####  2.1.3 Communication Complexity

##### Inter-Cluster Communication

No communication between the clusters is required. The clusters exclusively
access data that is not shared among the clusters in main memory.

##### Main Memory Accesses

Inside the parallel section, each cluster executes a loop of $D_{I}$
iterations. Inside that loop, each cluster loads one input depth slice, which
are $W_{I}^{2}$ words, and the filter parameters for one input-output depth
slice pair, which are $F^{2}$ words, from main memory. Over all loop
iterations, each cluster thus loads $D_{I}\cdot(W_{I}^{2}+F^{2})$ words from
main memory. After the loop, each cluster stores one output depth slice, which
are $W_{O}^{2}$ words, to main memory. Together, the clusters in all
iterations load $D_{O}\cdot D_{I}\cdot(W_{I}^{2}+F^{2})$ words from and store
$D_{O}\cdot W_{O}^{2}$ words to main memory.

####  2.1.4 Compute-to-Communication Ratio

Dividing the number of MACs by the number of words accessed in main memory
gives the CCR: rCl CCR & = $W_{I}$ 2⋅$F$ 2⋅$D_{I}$ ⋅$D_{O}$$D_{O}$ ⋅$D_{I}$
⋅($W_{I}$ 2\+ $F$ 2) + $D_{O}$ ⋅$W_{O}$ 2
$\mathrm{MAC}\text{/}$$\mathrm{word}\text{/}$
= $D_{I}$ ⋅$W_{I}$ 2⋅$F$ 2$D_{I}$ ⋅($W_{I}$ 2\+ $F$ 2) + $W_{O}$ 2
$\mathrm{MAC}\text{/}$$\mathrm{word}\text{/}$.

To give some numerical intuition: For typical values $W_{I}=W_{O}=32$,
$D_{I}=D_{O}=128$, and $F=3$, the CCR is ca.
$8.9\text{\,}\mathrm{MAC}\text{/}\mathrm{word}$. That is, the CCR for single-
precision data is $4.4\text{\,}\mathrm{spflop}\text{/}\mathrm{B}$ and for
double-precision data $2.2\text{\,}\mathrm{dpflop}\text{/}\mathrm{B}$. These
are very low values, which cause Algorithm 1 to be memory-bound on Manticore.

The reason is that the algorithm reloads each input depth slice once per
output depth slice. Thus, the CCR is mainly determined by the receptive field
of the filter, $F$. This can also be seen analytically as follows: Make the
reasonable assumption that $W_{O}=W_{I}$ (i.e., stride $S$ and padding $P$ are
set accordingly). Then the CCR becomes rCl CCR & =$W_{O}$ = $W_{I}$ $D_{I}$
⋅$W_{I}$ 2⋅$F$ 2$D_{I}$ ⋅($W_{I}$ 2\+ $F$ 2) + $W_{I}$ 2
$\mathrm{MAC}\text{/}$$\mathrm{word}\text{/}$
= $W_{I}$ 2⋅$D_{I}$ ⋅$F$ 2$W_{I}$ 2⋅($D_{I}$ \+ 1) + $F$ 2⋅$D_{I}$
$\mathrm{MAC}\text{/}$$\mathrm{word}\text{/}$. Typically, $D_{I}\gg 1$, so

$\text{\lx@glossaries@gls@link{acronym}{ccr}{\leavevmode
CCR}}\stackrel{{\scriptstyle D_{I}\gg 1}}{{\approx}}\frac{D_{I}\cdot
W_{I}^{2}\cdot
F^{2}}{D_{I}\cdot(W_{I}^{2}+F^{2})}\frac{$\mathrm{MAC}\text{/}$}{$\mathrm{word}\text{/}$}=\frac{W_{I}^{2}\cdot
F^{2}}{W_{I}^{2}+F^{2}}\frac{$\mathrm{MAC}\text{/}$}{$\mathrm{word}\text{/}$}.$
(1)

Finally, typically $W_{I}^{2}\gg F^{2}$, thus

$\text{\lx@glossaries@gls@link{acronym}{ccr}{\leavevmode
CCR}}\stackrel{{\scriptstyle W_{I}^{2}\gg
F^{2}}}{{\approx}}F^{2}\frac{$\mathrm{MAC}\text{/}$}{$\mathrm{word}\text{/}$}.$
(2)

####  2.1.5 Summary

Algorithm 1 implements convolutional layers in parallel on all clusters of
Manticore without necessitating communication or synchronization between the
clusters. The modest memory requirements of this implementation allow to
process large layers. The main drawback of this implementation is that each
cluster loads the entire input volume once for each output depth slice it
processes. This leads to a lot of redundant data loads, which significantly
reduces the CCR and causes this implementation to be memory-bound.

###  2.2 Parallelize Stacks of Output Depth Slices over Clusters

Input: $\mathbf{I}[W_{I}\times W_{I}\times D_{I}]$ input volume

Input: $\mathbf{F}[F\times F\times D_{I}\times D_{O}]$ filter parameters

Output: $\mathbf{O}[W_{O}\times W_{O}\times D_{O}]$ output volume

parallelize for  _$\delta_{o}\leftarrow 0$ to $\lceil D_{O}/\Delta_{O}\rceil$_
over clusters do

$D_{O,\mathrm{begin}}\leftarrow\delta_{o}\cdot\Delta_{O}$;

$D_{O,\mathrm{end}}\leftarrow\min(D_{O,\mathrm{begin}}+\Delta_{O},D_{O})$;

initialize $\mathbf{O}[:,:,D_{O,\mathrm{begin}}:D_{O,\mathrm{end}}]$ in local
memory to zero;

DmaLoad(_$\mathbf{I}[:,:,0]$_) from main memory;

for  _$d_{i}\leftarrow 0$ to $D_{I}$_ do

if  _$d_{i}+1 <D_{I}$_ then

DmaLoad(_$\mathbf{I}[:,:,d_{i}+1]$_) from main memory;

end if

DmaLoad(_$\mathbf{F}[:,:,d_{i},D_{O,\mathrm{begin}}]$_) from main memory;

DmaWait(_$\mathbf{I}[:,:,d_{i}]$_);

for  _$d_{o}\leftarrow D_{O,\mathrm{begin}}$ to $D_{O,\mathrm{end}}$_ do

if  _$d_{o}+1 <D_{O,\mathrm{end}}$_ then

DmaLoad(_$\mathbf{F}[:,:,d_{i},d_{o}+1]$_) from main memory;

end if

DmaWait(_$\mathbf{F}[:,:,d_{i},d_{o}]$_);

$\mathbf{O}[:,:,d_{o}]$ $\mathrel{+}=$ Conv(_$\mathbf{I}[:,:,d_{i}]$ ,
$\mathbf{F}[:,:,d_{i},d_{o}]$_);

end for

end for

DmaStore(_$\mathbf{O}[:,:,D_{O,\mathrm{begin}}:D_{O,\mathrm{end}}]$_) to main
memory;

end

Algorithm 2 Implementation of a convolutional layer where stacks of depth
slices of the output volumes are parallelized over the clusters.

The implementation of a convolutional layer shown in Algorithm 2 extends
Algorithm 1 by processing output depth slices in stacks: each cluster computes
$\Delta_{O}$ output depth slices in each parallel task. Within the parallel
task, the stack of output depth slices is initialized in the beginning and
stored to main memory at the end as a whole. Between that, output depth slices
are calculated as in Algorithm 1. This stacking of output depth slices
increases the reuse factor of each input depth slice and therefore reduces the
CCR compared to Algorithm 1.

####  2.2.1 Compute Complexity

The convolution (Conv(__)) does $W_{I}^{2}\cdot F^{2}$ MACs, and it is placed
inside an inner loop with $\Delta_{O}$ iterations. (If $\Delta_{O}$ does not
evenly divide $D_{O}$, one cluster task processes $D_{O}\bmod\Delta_{O}$
instead of $\Delta_{O}$ depth slices.) The inner loop is placed inside an
outer loop with $D_{I}$ iterations. Thus, one cluster task in the common case
does $W_{I}^{2}\cdot F^{2}\cdot\Delta_{O}\cdot D_{I}$ MACs, and all clusters
together do $W_{I}^{2}\cdot F^{2}\cdot D_{O}\cdot D_{I}$ MACs. Thus, in
comparison to Algorithm 1, this algorithm does not add additional MACs.

####  2.2.2 Space Complexity

Each cluster must store as many input depth slices and filter parameters as
described in Section 2.1.2, but instead of one output depth slice, it must now
store $\Delta_{O}$ output depth slices. Thus, the minimum local memory
required per cluster is $\Delta_{O}\cdot W_{O}^{2}+W_{I}^{2}+F^{2}$ words.

With $32\text{\,}\mathrm{KiB}\text{/}$ of local memory reserved for buffers
for the input depth slice and the filter parameters (see Section 2.1.2),
$96\text{\,}\mathrm{KiB}\text{/}$ are left for the stack of output depth
slices. To give some numerical intuition, for a typical layer with $W_{O}=32$,
this limits $\Delta_{O}\leq 24$ for single-precision data and $\Delta_{O}\leq
12$ for double-precision data.

####  2.2.3 Communication Complexity

##### Inter-Cluster Communication

As for Algorithm 1, no communication between the clusters is required.

##### Main Memory Accesses

The accesses to main memoryBy cleverly using the local memory of each cluster
and the high-performance on-chip network, two convolutional layer
implementations and one fully-connected layer implementation attain a high
CCR, w

are similar to those discussed in Section 2.1.3, with one important
difference: Whereas Algorithm 1 loaded each input depth slice once _per output
depth slice_ , Algorithm 2 loads each input depth slice once _per stack of
output depth slices_. The total number of words loaded from main memory is
thus:

$\underbrace{\left\lceil\frac{D_{O}}{\Delta_{O}}\right\rceil\cdot D_{I}\cdot
W_{I}^{2}}_{\text{input depth slices}}+\underbrace{D_{O}\cdot D_{I}\cdot
F^{2}}_{\text{filter parameters}}.$ (3)

The total number of words stored to main memory remains $D_{O}\cdot
W_{O}^{2}$.

####  2.2.4 Compute-to-Communication Ratio

Dividing the number of MACs by the number of words accessed in main memory
gives the CCR:

$\lx@glossaries@gls@link{acronym}{ccr}{\leavevmode CCR}=\frac{W_{I}^{2}\cdot
F^{2}\cdot D_{I}\cdot
D_{O}}{\left\lceil\frac{D_{O}}{\Delta_{O}}\right\rceil\cdot D_{I}\cdot
W_{I}^{2}+D_{O}\cdot D_{I}\cdot F^{2}+D_{O}\cdot
W_{O}^{2}}\frac{$\mathrm{MAC}\text{/}$}{$\mathrm{word}\text{/}$}$ (4)

To give some numerical intuition for a typical layer with $W_{I}=32$, $F=3$,
$W_{O}=32$ (due to $S=1$ and $P=1$), and $D_{I}=D_{O}=128$: For single-
precision data, $\Delta_{O}$ may be at most 24, and the CCR would then be
$141.8\text{\,}\mathrm{MAC}\text{/}\mathrm{word}$ or
$70.9\text{\,}\mathrm{spflop}\text{/}\mathrm{B}$. For double-precision data,
$\Delta_{O}$ may be at most 12, and the CCR would then be
$87.8\text{\,}\mathrm{MAC}\text{/}\mathrm{word}$ or
$21.9\text{\,}\mathrm{dpflop}\text{/}\mathrm{B}$. Compared to Algorithm 1,
reusing each input depth slice for a stack of output depth slices
significantly increases the CCR and makes this algorithm compute-bound.

####  2.2.5 Summary

Algorithm 2 significantly increases the CCR compared to Algorithm 1 by using
more of the local memory in each cluster to store and work on a stack of
output depth slices at a time. Algorithm 2 maintains the design goal of
Algorithm 1: still no communication or synchronization is required between the
clusters.

###  2.3 Parallelize Stacks of Output Depth Slices over Clusters and Reuse
Input Depth Slice of Previous Cluster

Input: $\mathbf{I}[W_{I}\times W_{I}\times D_{I}]$ input volume

Input: $\mathbf{F}[F\times F\times D_{I}\times D_{O}]$ filter parameters

Output: $\mathbf{O}[W_{O}\times W_{O}\times D_{O}]$ output volume

parallelize for  _$\delta_{o}\leftarrow 0$ to $\lceil D_{O}/\Delta_{O}\rceil$_
over clusters do

$D_{O,\mathrm{begin}}\leftarrow\delta_{o}\cdot\Delta_{O}$;

$D_{O,\mathrm{end}}\leftarrow\min(D_{O,\mathrm{begin}}+\Delta_{O},D_{O})$;

initialize $\mathbf{O}[:,:,D_{O,\mathrm{begin}}:D_{O,\mathrm{end}}]$ in local
memory to zero;

$\mathit{CID}_{\mathrm{in\,L2\,quad}}\leftarrow\mathit{CID}\bmod 16$;

DmaLoad(_$\mathbf{I}[:,:,\mathit{CID}_{\mathrm{in\,L2\,quad}}]$_) from main
memory;

for  _$d_{i}\leftarrow\mathit{CID}_{\mathrm{in\,L2\,quad}}$ to $D_{I}$
$\mathrm{then}$ $d_{i}\leftarrow 0$ to $\mathit{CID}_{\mathrm{in\,L2\,quad}}$_
do

if  _$d_{i}+1=D_{I}$_ then

$d_{i,\mathrm{next}}\leftarrow 0$;

else

$d_{i,\mathrm{next}}\leftarrow d_{i}+1$;

end if

if  _$d_{i,\mathrm{next}}\neq\mathit{CID}_{\mathrm{in\,L2\,quad}}$_ then

if  _$d_{i,\mathrm{next}}\bmod 16=\mathit{CID}_{\mathrm{in\,L2\,quad}}$_ then

DmaLoad(_$\mathbf{I}[:,:,d_{i,\mathrm{next}}]$_) from main memory;

else

DmaLoad(_$\mathbf{I}[:,:,d_{i,\mathrm{next}}]$_) from cluster
$(\mathit{CID}-1)\bmod 16$;

end if

end if

DmaLoad(_$\mathbf{F}[:,:,d_{i},D_{O,\mathrm{begin}}]$_) from main memory;

DmaWait(_$\mathbf{I}[:,:,d_{i}]$_);

for  _$d_{o}\leftarrow D_{O,\mathrm{begin}}$ to $D_{O,\mathrm{end}}$_ do

if  _$d_{o}+1 <D_{O,\mathrm{end}}$_ then

DmaLoad(_$\mathbf{F}[:,:,d_{i},d_{o}+1]$_) from main memory;

end if

DmaWait(_$\mathbf{F}[:,:,d_{i},d_{o}]$_);

$\mathbf{O}[:,:,d_{o}]$ $\mathrel{+}=$ Conv(_$\mathbf{I}[:,:,d_{i}]$ ,
$\mathbf{F}[:,:,d_{i},d_{o}]$_);

end for

end for

DmaStore(_$\mathbf{O}[:,:,D_{O,\mathrm{begin}}:D_{O,\mathrm{end}}]$_) to main
memory;

end

Algorithm 3 Implementation of a convolutional layer where stacks of depth
slices of the output volumes are parallelized over the clusters and the 16
clusters within one L2 quadrant reuse input depth slices.

The implementation of a convolutional layer shown in Algorithm 3 improves
Algorithm 2 in one aspect: instead of loading each input depth slice from main
memory, clusters within the same L2 quadrant load every input depth slice that
has already been loaded by another cluster in the same L2 quadrant from that
cluster. The main motivation for this is reducing the off-chip traffic to
improve the energy efficiency.

####  2.3.1 Compute Complexity

The compute complexity is identical to that of Algorithm 2, which is described
in Section 2.2.1.

####  2.3.2 Space Complexity

In addition to the buffers described in Section 2.2.2, this implementation
requires a buffer to store the input depth slice so that another cluster can
load it. The round-trip latency within one L2 cluster is in the low tens of
cycles, so the dominating factor for this buffer is the size of one input
depth slice: $W_{I}^{2}$ words. This leaves $92\text{\,}\mathrm{KiB}\text{/}$
for the stack of output depth slices for single-precision data and
$88\text{\,}\mathrm{KiB}\text{/}$ for double-precision data. To give some
numerical intuition, for a typical layer with $W_{O}=32$, this limits
$\Delta_{O}\leq 23$ for single-precision data and $\Delta_{O}\leq 11$ for
double-precision data.

####  2.3.3 Communication Complexity

##### Inter-Cluster Communication

As there are 16 clusters within one L2 quadrant, in 15 out of 16 iterations
over the input depth slices, the input depth slice is loaded from another
cluster instead of main memory. The number of words communicated between
clusters is thus:

$\frac{15}{16}\cdot\left\lceil\frac{D_{O}}{\Delta_{O}}\right\rceil\cdot
D_{I}\cdot W_{I}^{2}.$ (5)

To synchronize the update of an input depth slice buffer, the destination
cluster sends an atomic increment to the epoch counter in the source cluster.

##### Main Memory Accesses

The number of words loaded from main memory is significantly reduced, as input
depth slices are mostly loaded from other clusters:

$\underbrace{\frac{1}{16}\cdot\left\lceil\frac{D_{O}}{\Delta_{O}}\right\rceil\cdot
D_{I}\cdot W_{I}^{2}}_{\text{input depth slices}}+\underbrace{D_{O}\cdot
D_{I}\cdot F^{2}}_{\text{filter parameters}}.$ (6)

The number of words stored to main memory remains $D_{O}\cdot W_{O}^{2}$.

####  2.3.4 Compute-to-Communication Ratio

The overall CCR is not affected by loading most input depth slices from other
clusters instead of main memory. However, the CCR considering only off-chip
main memory is significantly increased due to the substantially reduced number
of words loaded from main memory.

To give some numerical intuition for a typical layer with $W_{I}=W_{O}=32$,
$F=3$, and $D_{I}=D_{O}=128$. For single-precision data, $\Delta_{O}$ may be
at most 23, and the CCR considering only off-chip memory accesses would then
be $541.4\text{\,}\mathrm{MAC}\text{/}\mathrm{word}$ or
$270.7\text{\,}\mathrm{spflop}\text{/}\mathrm{B}$. For double-precision data,
$\Delta_{O}$ may be at most 11, and the CCR considering only off-chip memory
accesses would then be $540.6\text{\,}\mathrm{MAC}\text{/}\mathrm{word}$ or
$135.2\text{\,}\mathrm{dpflop}\text{/}\mathrm{B}$.

####  2.3.5 Summary

Algorithm 3 improves Algorithm 2 in that it loads input depth slices that have
already been loaded by another cluster in the same L2 quadrant from that
cluster instead of off-chip main memory. This significantly reduces the off-
chip memory traffic.

##  3 Fully-Connected Layers

###  3.1 Parallelize Input Depth Slices over Clusters

Input: $\mathbf{I}[W_{I}\times W_{I}\times D_{I}]$ input volume

Input: $\mathbf{F}[W_{I}\times W_{I}\times D_{I}\times D_{O}]$ filter
parameters

Output: $\mathbf{O}[1\times 1\times D_{O}]$ output volume

initialize a private output volume $\mathbf{O}^{\prime}$ on each cluster to
zero;

parallelize for  _$d_{i}\leftarrow 0$ to $D_{I}$_ over clusters do

DmaLoad(_$\mathbf{I}[:,:,d_{i},:]$_) from main memory;

DmaLoad(_$\mathbf{F}[:,:,d_{i},0]$_) from main memory;

DmaWait(_$\mathbf{I}[:,:,d_{i},:]$_);

for  _$d_{o}\leftarrow 0$ to $D_{O}$_ do

if  _$d_{o}+1 <D_{O}$_ then

DmaLoad(_$\mathbf{F}[:,:,d_{i},d_{o}+1]$_) from main memory;

end if

DmaWait(_$\mathbf{F}[:,:,d_{i},d_{o}]$_);

for  _$b\leftarrow 0$ to $B$_ do

$\mathbf{O}^{\prime}[0,0,d_{o},b]$ $\mathrel{+}=$
ElemMac(_$\mathbf{I}[:,:,d_{i},b]$ , $\mathbf{F}[:,:,d_{i},d_{o}]$_);

end for

end for

end

sum-reduce the private output volumes $\mathbf{O}^{\prime}$ of all clusters to
$\mathbf{O}$;

DmaStore(_$\mathbf{O}[:,:,:]$_) to main memory;

Algorithm 4 Implementation of a fully-connected layer where the depth slices
of the input volumes are parallelized over the clusters.

The implementation of a fully-connected layer shown in Algorithm 4
parallelizes the input depth slices over the clusters. Before the parallel
section, each cluster allocates a private output volume $\mathbf{O}^{\prime}$
and initializes it to zero. In the parallel section, the cluster first loads
the entire batch of one depth slice of the input volume and then loops over
the output depth slices. Within that loop, the cluster loads the filter
parameters for the current pair of input and output depth slices and then
enters an inner loop over the batch. Within the inner loop, the cluster in the
ElemMac(__) operation multiplies the input depth slice of a batch element with
the loaded filter parameters element-wise and then accumulates all products to
a single value, which it adds to the output element for the current output
depth slice and batch element. After the parallel section, the private output
volumes of all clusters are reduced by summation to a single output volume,
which contains the contributions of all input depth slices.

This implementation exploits batching of input and output data, so the filter
parameters for each pair of input and output depth slices can be used $B$
times. This is crucial for increasing the operational intensity to a range
where the implementation is not memory-bound.

The main problem of this implementation, however, is that each cluster must
store a private copy of the entire output volume, which are $D_{O}\cdot B$
words. This limits the maximum output depth (which restricts the generality of
the implementation) or the batch size (which limits the operational
intensity). The implementation in Section 3.2 will resolve this limitation by
processing output depth slices in stacks.

####  3.1.1 Compute Complexity

The element-wise MAC operation (ElemMac(__)) does $W_{I}\cdot W_{I}$ MACs, and
it is placed inside two loops, so it is executed $D_{O}\cdot B$ times per
cluster task. In total, each cluster task does $W_{I}^{2}\cdot B\cdot D_{O}$
MACs. Together, the clusters do $W_{I}^{2}\cdot B\cdot D_{O}\cdot D_{I}$ MACs.

####  3.1.2 Space Complexity

Each cluster must store:

  1. (1)

its private output volume, which are $D_{O}\cdot B$ words;

  2. (2)

the entire batch of one input depth slice, which are $W_{I}^{2}\cdot B$ words;

  3. (3)

the filter parameters for one input-output depth slice pair, which are
$W_{I}^{2}$ words.

Thus, the minimum local memory required per cluster is $D_{O}\cdot
B+W_{I}^{2}\cdot(B+1)$ words. For a typical layer with $W_{I}=7$ and
$D_{O}=4096$ and a reasonable batch size of $B=32$, this corresponds to
$132\,689$ words, or ca. $519\text{\,}\mathrm{KiB}\text{/}$ for single-
precision and ca. $1037\text{\,}\mathrm{KiB}\text{/}$ for double-precision
data. This is too much for a cluster with $128\text{\,}\mathrm{KiB}\text{/}$
of local memory. Decreasing the batch size below 32 usually leads into a
memory-bound regime and is therefore not an option. However, this algorithm
can be viable up for $D_{O}$ on the order of 512 for single-precision data and
$D_{O}$ on the order of 256 for double-precision data; more on that below.

Beyond the minimum local memory requirements, additional storage can be
required to hide the latency of loads from off-chip main memory. Especially
the filter parameters (3), which are loaded once per very short inner loop
iteration, can benefit from a buffer. The size of that buffer depends on the
latency to the main memory. Assuming a round-trip latency of 256 clock cycles
and a data bus width of
$$512\text{\,}\mathrm{bit}\text{/}$=$64\text{\,}\mathrm{B}\text{/}$$, up to
$16\text{\,}\mathrm{KiB}\text{/}$ can be in transfer in the on-chip network. A
buffer of the same size can be added for input depth slices (2), so that data
transfers by the DMA engine run fully in background.333The DMA transfer buffer
could be shared by the input depth slices and the filter parameters, since the
total amount of data in transfer in the on-chip network does not depend on the
type of data being transferred. This would save local memory in the cluster,
but it requires the RTE to dynamically partition the DMA transfer buffer
between different data types and variables, which is not trivial. We therefore
do not assume this RTE capability.  In total, roughly
$32\text{\,}\mathrm{KiB}\text{/}$ are required as buffers for input depth
slices and filter parameters, which leaves $96\text{\,}\mathrm{KiB}\text{/}$
for the cluster-private output volume. For $W_{I}=7$ and $B=32$, this allows
$D_{O}\leq 768$ for single-precision and $D_{O}\leq 384$ for double-precision
data.

####  3.1.3 Communication Complexity

##### Inter-Cluster Communication

Before and inside the parallel section, the clusters do not communicate
between them. After the parallel section, the private output volumes
$\mathbf{O}^{\prime}$ of all clusters must to be accumulated to one output
volume $\mathbf{O}$. The optimal way in terms of latency to do this is by tree
reduction: In the first step, for every two clusters in an L1 quadrant, one
reads $\mathbf{O}^{\prime}$ of the other cluster and adds it to its own. In
the second step, one of the two clusters in an L1 quadrant that read
$\mathbf{O}^{\prime}$ in step 1 reads it from the other cluster and adds it to
its own. This then goes on until one cluster in one L3 quadrant reads the
accumulated $\mathbf{O}^{\prime}$ of the other L3 and adds it to its own. In
the first two steps, $\mathbf{O}^{\prime}$ is read three times over each L1
network. In steps three and four, $\mathbf{O}^{\prime}$ is read three times
over each L2 network. In steps five and six, $\mathbf{O}^{\prime}$ is read
three times over each L3 network. And in the last step, $\mathbf{O}^{\prime}$
is read once between L3 networks. In total, $127\cdot D_{O}\cdot B$ words are
communicated between clusters to reduce all $\mathbf{O}^{\prime}$s into
$\mathbf{O}$.

##### Main Memory Accesses

Inside the parallel section, each cluster loads the entire batch of one input
depth slice, which are $W_{I}^{2}\cdot B$ words, from main memory. Then, in a
loop of $D_{O}$ iterations, each cluster loads the filter parameters for the
current pair of input and output depth slices, which are $W_{I}^{2}$ words,
from main memory. Thus, within every cluster task, each cluster loads
$W_{I}^{2}\cdot(B+D_{O})$ words from main memory. Together, the clusters in
all iterations load $D_{I}\cdot W_{I}^{2}\cdot(B+D_{O})$ words from main
memory. After the parallel section, one cluster stores the accumulated output
volume, $\mathbf{O}$, which are $D_{O}\cdot B$ words, to main memory.

####  3.1.4 Compute-to-Communication Ratio

The bulk of accesses to main memory are the loads by each cluster within the
parallel region. Dividing the compute complexity by that memory access
complexity gives the CCR within the parallel region:

$\text{\lx@glossaries@gls@link{acronym}{ccr}{\leavevmode
CCR}}=\frac{W_{I}^{2}\cdot B\cdot
D_{O}}{W_{I}^{2}\cdot(B+D_{O})}\frac{\text{MAC}}{\text{word}}=\frac{B\cdot
D_{O}}{B+D_{O}}\frac{\text{MAC}}{\text{word}}.$ (7)

As typically $D_{O}\gg B$, the CCR tends to scale linearly with the batch
size. Equation 7 also describes the overall CCR, because both compute and
communication complexity are multiplied by the factor $D_{I}$.

Clearly, the CCR increases with increasing batch size $B$ and output volume
depth $D_{O}$. To give some numerical intuition for $B=32$: with single-
precision data, $D_{O}$ may be at most 768 and the CCR would then be
$30.7\text{\,}\mathrm{MAC}\text{/}\mathrm{word}$ or
$15.4\text{\,}\mathrm{spflop}\text{/}\mathrm{B}$; and with double-precision
data, $D_{O}$ may be at most 384 and the CCR would then be
$29.5\text{\,}\mathrm{MAC}\text{/}\mathrm{word}$ or
$7.4\text{\,}\mathrm{dpflop}\text{/}\mathrm{B}$.

####  3.1.5 Summary

Algorithm 4 implements fully-connected layers with a favorable CCR, which
scales linearly with the batch size, and it provides large parallel sections
within which no inter-cluster communication is required. The main limitation
of this algorithm is the local memory required to hold a cluster-private copy
of the output volume, which limits it to $D_{O}\leq 768$ for single-precision
and $D_{O}\leq 384$ for double-precision data.

###  3.2 Stacks of Output Depth Slices and Parallel Input Depth Slices

Input: $\mathbf{I}[W_{I}\times W_{I}\times D_{I}]$ input volume

Input: $\mathbf{F}[W_{I}\times W_{I}\times D_{I}\times D_{O}]$ filter
parameters

Output: $\mathbf{O}[1\times 1\times D_{O}]$ output volume

for  _$\delta_{o}\leftarrow 0$ to $\lceil D_{O}/\Delta_{O}\rceil$_ do

$D_{O,\mathrm{begin}}\leftarrow\delta_{o}\cdot\Delta_{O}$;

$D_{O,\mathrm{end}}\leftarrow\min(D_{O,\mathrm{begin}}+\Delta_{O},D_{O})$;

initialize a private output volume
$\mathbf{O}^{\prime}[:,:,D_{O,\mathrm{begin}}:D_{O,\mathrm{end}},:]$ on each
cluster to zero;

parallelize for  _$d_{i}\leftarrow 0$ to $D_{I}$_ over clusters do

DmaLoad(_$\mathbf{I}[:,:,d_{i},:]$_) from main memory;

DmaLoad(_$\mathbf{F}[:,:,d_{i},D_{O,\mathrm{begin}}]$_) from main memory;

DmaWait(_$\mathbf{I}[:,:,d_{i},:]$_);

for  _$d_{o}\leftarrow D_{O,\mathrm{begin}}$ to $D_{O,\mathrm{end}}$_ do

if  _$d_{o}+1 <D_{O,\mathrm{end}}$_ then

DmaLoad(_$\mathbf{F}[:,:,d_{i},d_{o}+1]$_) from main memory;

end if

DmaWait(_$\mathbf{F}[:,:,d_{i},d_{o}]$_);

for  _$b\leftarrow 0$ to $B$_ do

$\mathbf{O}^{\prime}[0,0,d_{o},b]$ $\mathrel{+}=$
ElemMac(_$\mathbf{I}[:,:,d_{i},b]$ , $\mathbf{F}[:,:,d_{i},d_{o}]$_);

end for

end for

end

sum-reduce the private output volumes
$\mathbf{O}^{\prime}[:,:,D_{O,\mathrm{begin}}:D_{O,\mathrm{end}},:]$ of all
clusters to $\mathbf{O}[:,:,D_{O,\mathrm{begin}}:D_{O,\mathrm{end}},:]$;

DmaStore(_$\mathbf{O}[:,:,D_{O,\mathrm{begin}}:D_{O,\mathrm{end}},:]$_) to
main memory;

end for

Algorithm 5 Implementation of a fully-connected layer where the depth slices
of the output volume are processed in stacks of size $\Delta_{O}$ and the
depth slices of the input volumes are parallelized over the clusters.

The implementation of a fully-connected layer shown in Algorithm 5 extends
Algorithm 4 by adding an outer loop that processes the output depth slices in
stacks: each cluster processes $\Delta_{O}$ output depth slices in each
parallel task. Within the outer loop, the input depth slices are processed in
parallel over the clusters, as in Algorithm 4. This algorithm can be seen as a
generalization of Algorithm 4: one sets $\Delta_{O}$ below the limit
identified in Section 3.1.2 and then loops over stacks of output depth slices,
executing Algorithm 4 on each stack of output depth slices.

####  3.2.1 Compute Complexity

The compute complexity is analogous to that in Section 3.1.1: for each
parallel task, each cluster does $W_{I}^{2}\cdot B\cdot\Delta_{O}$ MACs. (If
$\Delta_{O}$ does not evenly divide $D_{O}$, the last iteration of the
outermost loop processes $D_{O}\bmod\Delta_{O}$ instead of $\Delta_{O}$ depth
slices.) Over all iterations of the outermost loop, the clusters together do
$W_{I}^{2}\cdot B\cdot D_{O}\cdot D_{I}$ MACs. Thus, in comparison to
Algorithm 4, this algorithm does not add additional MACs.

####  3.2.2 Space Complexity

The space complexity is analogous to that in Section 3.1.2, with $D_{O}$
replaced by $\Delta_{O}$. Thus, the minimum local memory required per cluster
is $\Delta_{O}\cdot B+W_{I}^{2}\cdot(B+1)$ words. Accounting for buffers for
DMA transfers and setting $B=32$, a typical value of $W_{I}=7$ allows for
$\Delta_{O}\leq 768$ for single-precision and $\Delta_{O}\leq 384$ for double-
precision data.

####  3.2.3 Communication Complexity

##### Inter-Cluster Communication

The inter-cluster communication is analogous to that in Section 3.1.3: in
total, $127\cdot D_{O}\cdot B$ words are communicated between clusters to
reduce all $\mathbf{O}^{\prime}$s into $\mathbf{O}$.

##### Main Memory Accesses

The accesses to main memory are similar to those discussed in Section 3.1.3,
with one important difference: Whereas Algorithm 4 loaded each input depth
slice only once for all output depth slices, Algorithm 5 loads each depth
slice of $\mathbf{I}$ once _per stack of output depth slices_. This overhead
is a result of the trade-off for reduced local memory requirements that we
struck by processing the output depth slices in stacks. Within every cluster
task, each cluster loads $W_{I}^{2}\cdot(B+\Delta_{O})$ words from main
memory. Together, the clusters load $D_{I}\cdot W_{I}^{2}\cdot(B+\Delta_{O})$
words from main memory in every iteration of the outermost loop, and one
cluster stores the current depth slice stack of the accumulated output volume,
which are $\Delta_{O}\cdot B$ words, to main memory. As there are $\lceil
D_{O}/\Delta_{O}\rceil$ iterations of the outermost loop, the total number of
words loaded from main memory is:

$\underbrace{\left\lceil\frac{D_{O}}{\Delta_{O}}\right\rceil\cdot D_{I}\cdot
B\cdot W_{I}^{2}}_{\text{batch of input volumes}}+\underbrace{D_{O}\cdot
D_{I}\cdot W_{I}^{2}}_{\text{filter parameters}}.$ (8)

Thus, the entire input volume is loaded $\lceil D_{O}/\Delta_{O}\rceil$ times
instead of once as in Algorithm 4, but each filter parameter is still loaded
only once. For the same reason, the total number of words stored to main
memory remains $D_{O}\cdot B$. For the sake of computing the CCR, we rewrite
Eq. 8 as

$D_{I}\cdot
W_{I}^{2}\cdot\left(\left\lceil\frac{D_{O}}{\Delta_{O}}\right\rceil\cdot
B+D_{O}\right).$ (9)

####  3.2.4 Compute-to-Communication Ratio

The bulk of accesses to main memory are again the loads of the input volume
and the filter parameters; the total number of loaded words is given by Eq. 9.
Dividing the compute complexity by those loads gives the CCR:

$\text{\lx@glossaries@gls@link{acronym}{ccr}{\leavevmode
CCR}}=\frac{D_{I}\cdot W_{I}^{2}\cdot B\cdot D_{O}}{D_{I}\cdot
W_{I}^{2}\cdot\left(\left\lceil\frac{D_{O}}{\Delta_{O}}\right\rceil\cdot
B+D_{O}\right)}\frac{\text{MAC}}{\text{word}}=\frac{B\cdot
D_{O}}{\left\lceil\frac{D_{O}}{\Delta_{O}}\right\rceil\cdot
B+D_{O}}\frac{\text{MAC}}{\text{word}}.$ (10)

The overhead of the redundant input volume loads also manifests itself in the
denominator (i.e., in the communication) of the CCR.

To give some numerical intuition for $B=32$ and $D_{O}=4096$: with single-
precision data, $\Delta_{O}$ may be at most 768 and the CCR would then be
$30.6\text{\,}\mathrm{MAC}\text{/}\mathrm{word}$ or
$15.3\text{\,}\mathrm{spflop}\text{/}\mathrm{B}$; and with double-precision
data, $\Delta_{O}$ may be at most 384 and the CCR would be
$29.5\text{\,}\mathrm{MAC}\text{/}\mathrm{word}$ or
$7.4\text{\,}\mathrm{dpflop}\text{/}\mathrm{B}$. Clearly, the impact on the
CCR of the overhead of processing output depth slices in stacks diminishes for
large $D_{O}$.

####  3.2.5 Summary

Algorithm 5 is a generalization of Algorithm 4 in that the depth of the output
volume is no longer limited by the local memory of each cluster. This
algorithm maintains the large parallel sections as well as the favorable CCR
of Algorithm 4 for large output volume depths.

##  4 Summary

This document has presented three implementations of convolutional layers and
two implementations of fully-connected layers on the Manticore cluster-based
many-core architecture. By cleverly using the local memory of each cluster and
the high-performance on-chip network, two convolutional layer implementations
and one fully-connected layer implementation attain a high CCR, which allow
them to exploit the full computational potential of Manticore.

## References

  * [1] F. Zaruba, F. Schuiki, and L. Benini, “Manticore: A 4096-core RISC-V chiplet architecture for ultra-efficient floating-point computing,” in _IEEE Hot Chips_ , Aug. 2020.
  * [2] 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_ , pp. 1–1, 2020.
  * [3] S. Mach, F. Schuiki, F. Zaruba, and L. Benini, “A 0.80pJ/flop, 1.24Tflop/sW 8-to-64 bit transprecision floating-point unit for a 64 bit RISC-V processor in 22nm FD-SOI,” in _2019 IFIP/IEEE 27th International Conference on Very Large Scale Integration (VLSI-SoC)_ , 2019, pp. 95–98.
  * [4] A. Kurth, W. Rönninger, T. Benz, M. Cavalcante, F. Schuiki, F. Zaruba, and L. Benini, “An open-source platform for high-performance non-coherent on-chip communication,” 2020.
  * [5] F.-F. Li, R. Krishna, and D. Xu. (2020) CS231n: Convolutional neural networks for visual recognition. [Online]. Available: https://cs231n.github.io