# Communication Bounds for Convolutional Neural Networks

Anthony Chen  0000-0003-0760-8329 University of Michigan, Ann ArborAnn
ArborUSA ,  James Demmel  University of California, BerkeleyBerkeleyUSA ,
Grace Dinh  University of California, BerkeleyBerkeleyUSA ,  Mason Haberle
New York UniversityNew YorkUSA and  Olga Holtz  University of California,
BerkeleyBerkeleyUSA

###### Abstract.

Convolutional neural networks (CNNs) are important in a wide variety of
machine learning tasks and applications, so optimizing their performance is
essential. Moving words of data between levels of a memory hierarchy or
between processors on a network is much more expensive than the cost of
arithmetic, so minimizing communication is critical to optimizing performance.
In this paper, we present new lower bounds on data movement for mixed
precision convolutions in both single-processor and parallel distributed
memory models, as well as algorithms that outperform current implementations
such as Im2Col. We obtain performance figures using GEMMINI, a machine
learning accelerator, where our tiling provides improvements between 13% and
150% over a vendor supplied algorithm.

Convolutional neural networks, communication avoiding algorithms

††conference: PASC ’21: ACM Platform for Advanced Scientific Computing
Conference; June 27–29, 2022; Basel, CH††booktitle: PASC ’22: ACM Platform for
Advanced Scientific Computing Conference, June 27–29, 2022, Basel, CH††ccs:
Computing methodologies Machine learning algorithms††ccs: Computing
methodologies Parallel algorithms††ccs: Mathematics of computing Mathematical
analysis

##  1\. Introduction

Convolutional neural networks (CNNs) are important in many machine learning
applications and their computational intensity makes their computation a major
bottleneck, requiring efficient implementations on modern architectures. To do
so, it is important to recognize that most of the time and energy spent during
the execution of a CNN often goes towards communication, the movement of data
between different levels of the memory hierarchy (RAM to L3 cache) or between
processors operating in parallel. The cost of moving one word of data is
frequently orders of magnitude larger than the cost of performing one
arithmetic operation both in terms of time and power consumption. This
disparity is only increasing as time passes (Council, 2011). Minimizing
communication has driven optimization efforts in numerical linear algebra,
giving rise to the highly tuned implementations seen in BLAS and LAPACK which
attain a high fraction of a machine’s maximum possible performance.

In this paper, we consider the problem of computing a single convolution layer
of a CNN, which can be written as seven nested loops. Our model is described
in Section 2.1. In our theoretical work, we consider various ways of
organizing this computation, and we ask which order minimizes the amount of
communication between main memory and cache in the single processor case, or
between the network of processors in the parallel case. We describe our CNN
and memory model in detail in 2.1.

Our first contribution is to provide new communication lower bounds in both
single processor and parallel architectures including precise constants and
allowing for mixed precision data. These bounds are presented in Section 2.2
with proofs in Sections 3.1 and 4.1. Our second contribution is to provide
algorithms which meet these bounds in the parallel case for large parameters,
and which approach them more closely than previously attainable in the single
processor case. These results are described in Sections 3.2 and 4.2.

The rest of the paper is organized as follows. Section 2 describes our CNN
model before we briefly discuss our results, and introduces the main
theoretical tool for computing lower bounds, the Hölder-Brascamp-Lieb
inequalities. Sections 3 and 4 present lower bounds for the single processor
and parallel cases respectively with discussions of attainability. In Section
5, we discuss performance results obtained using GEMMINI, a machine learning
accelerator.

##  2\. Preliminaries

###  2.1. CNN and Memory Model

We consider the following loop nest for directly computing a convolution layer
of a CNN. Since it has 7 nested loops surrounding a simple update instruction,
we call it 7NL CNN:

$\displaystyle{\text{for}}\\{i_{1},i_{2},i_{3},i_{4},i_{5},i_{6},i_{7}\\}=0:\\{N,c_{I},c_{O},w_{O},h_{O},w_{F},h_{F}\\}-1$
$\displaystyle\ \
\text{Output}(i_{1},i_{3},i_{4},i_{5})\,+=\text{Input}(i_{1},i_{2},\sigma_{w}i_{4}+i_{6},\sigma_{h}i_{5}+i_{7})\times$
(1) $\displaystyle\ \
\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\text{Filter}(i_{2},i_{3},i_{6},i_{7})$

where the Input has dimensions $N\times
c_{I}\times(w_{F}+\sigma_{w}w_{O})\times(h_{F}+\sigma_{h}h_{O})$, the Output
has dimensions $N\times c_{O}\times w_{O}\times h_{O}$, and the Filter has
dimensions $c_{I}\times c_{O}\times w_{F}\times h_{F}$. $N$ is the number of
images, $c_{I}$ is the number of channels of the input image, $c_{O}$ is the
number of channels of the output image, $w_{O}$ and $h_{O}$ are the width and
height of the output image, $w_{F}$ and $h_{F}$ are the width and height of
one convolution filter, and $\sigma_{w}$ and $\sigma_{h}$ are the stride sizes
in the horizontal and vertical dimensions respectively. We assume that the
filter sizes are smaller than the input image sizes, and in practice, they are
usually much smaller. This gives us the assumptions $w_{F}\leq\sigma_{w}w_{O}$
and $h_{F}\leq\sigma_{h}h_{F}$. We also assume that $\sigma_{w}\leq w_{F}$ and
$\sigma_{h}\leq h_{F}$ so that all elements of the image are used. Then, the
input has size $|I|=Nc_{I}(\sigma_{w}w_{O}+w_{F})(\sigma_{h}h_{O}+h_{F})$, the
output has size $|O|=Nc_{O}w_{O}h_{O}$, and the filter has size
$|F|=c_{I}c_{O}w_{F}h_{F}$. The precisions of the input, output, and filter
are $p_{I}$, $p_{O}$, and $p_{F}$ respectively. These are in units of words
(32 bits). We define the sum of the precisions as $p_{T}=p_{I}+p_{O}+p_{F}$.

Note that each iteration of the loop nest requires access to a single element
of both the Input and Filter arrays, and must make a single update to the
Output array. The order in which these updates are made does not impact the
result, so they may be reorganized as desired to optimize for data movement.
We consider a _computation_ of the 7NL CNN algorithm to be an execution of all
$G:=Nc_{I}c_{O}w_{O}h_{O}w_{F}h_{F}$ updates, performed in any order.

We consider computations of 7NL CNN within two different architectures. The
first is a single processor architecture with a 2-layer memory model: a cache
which may hold $M$ words of data and may be accessed instantaneously by the
processor, and a main memory of arbitrary size. The movement of one word of
data from the main memory to the cache, or back, is counted as a single unit
of communication. Data begins in the main memory, and the output of the
computation must reside in the main memory before the computation is complete.

The second architecture is a parallel processor architecture with a
distributed memory model. There are $P$ processors, each with their own local
instantaneously accessible memory of size $M$ words. Any one processor may
communicate with any other processor, and each word sent is counted as a
single unit of communication. Data may begin in any processor, and may end in
any processor by the completion of the computation.

###  2.2. Our Results

Before we discuss the mathematical tools involved in our analysis, we first
briefly summarize our results. We find results corresponding both to the
single and parallel architectures with mixed precision data. Proofs are found
in Sections 3.1 and 4.1.

We find the following lower bound for the number of words communicated in a
single-processor memory model with fast memory (cache) and slow memory, where
the Input array takes entries which are $p_{I}$ words in length, and similarly
$p_{F}$ for the Filter and $p_{O}$ for the Output.

###### Theorem 2.1.

If $X$ is the number of words communicated by _7NL CNN_ within a single-
processor memory model with $M$ words of fast memory, where _Input_ , _Filter_
, and _Output_ are non-overlapping arrays and
$G:=Nc_{I}c_{O}w_{O}h_{O}w_{F}h_{F}$ is the total number of updates performed
during the computation, we have

$X\geq\max\big{\\{}p_{I}|I|+p_{F}|F|+p_{O}|O|,C_{p}GM^{-1}-M,\\\
{2(p_{I}p_{F}p_{O})^{1/2}(\sigma_{w}\sigma_{h})^{1/2}G}{(w_{F}h_{F}M)^{-1/2}}-2M\big{\\}}$

where the value of $C_{p}=C_{p}(p_{I},p_{F},p_{O})$ depends on the precisions
satisfying a triangle condition:

$C_{p}=\begin{cases}\frac{1}{4}p_{T}^{2}&p_{j}\leq
p_{k}+p_{\ell}\quad\textrm{for all distinct }j,k,\ell\\\
p_{j}(p_{k}+p_{\ell})&p_{j}>p_{k}+p_{\ell}\quad\textrm{for some distinct
}j,k,\ell\end{cases}$

In the standard case when each matrix has precision $1$, $C_{p}=9/4$. The
first bound corresponds to accessing each memory location at least once. The
second bound dominates when individual $w_{F}\times h_{F}$ filters are large
relative to the memory size $M$, and the third bound dominates when filters
are small relative to $M$. In all practical cases, the precisions satisfy the
triangle condition, so the first expression for $C_{p}$ is more relevant.

We additionally discuss a blocking technique for evaluating 7NL CNN which
comes close to meeting this bound. Plots depicting this attainability are
found in Figure 2.

We also derive the following lower bounds for the number of words communicated
by some processor in a parallel-processor distributed memory model. Again,
these bounds accept mixed precision data. The first two bounds are similar to
our bounds in Theorem 2.1, decaying with the memory size.

###### Theorem 2.2.

If $X$ is the number of words communicated by _7NL CNN_ within a parallel
processor memory model with $P$ processors each with $M$ words of memory,
where _Input_ , _Filter_ , and _Output_ are nonoverlapping arrays with
precisions $p_{I},p_{F},p_{O}$ respectively and
$G:=Nc_{I}c_{O}w_{O}h_{O}w_{F}h_{F}$ is the total number of updates performed
during the computation, we have

$X\geq\max\left\\{\frac{C_{p}G}{PM}-M,\frac{2(p_{I}p_{F}p_{O})^{1/2}(\sigma_{w}\sigma_{h})^{1/2}G}{P(w_{F}h_{F}M)^{1/2}}-2M\right\\}$

with $C_{p}$ as in Theorem 2.1.

The above bounds are only nontrivial when $M$ and $P$ are small relative to
$G$. If there are many processors, or each processor has access to more
memory, then we require new lower bounds corresponding in spirit to the 2.5D
matrix multiplication data replication algorithms presented in (Demmel et al.,
2013). These two bounds are memory independent and require a load-balancing
assumption.

###### Theorem 2.3.

Consider an execution of _7NL CNN_ within a parallel processor memory model
with the setup of Theorem 2.2. Suppose further that each array is initially
load balanced and that and $A_{p}:=\max\\{p_{I}|I|,p_{F}|F|,p_{O}|O|\\}$ is
the memory size of the largest array. Some processor must communicate $X$
words, where

$X\geq(p_{I}p_{F}p_{O})^{1/3}\max\left\\{\frac{G^{1/2}}{P^{1/2}},\frac{(G\sigma_{w}\sigma_{h})^{2/3}}{(Pw_{F}h_{F})^{2/3}}\right\\}-\frac{A_{p}}{P}.$

We introduce the machinery used to obtain these lower bounds, and then present
careful proofs.

###  2.3. The Hölder-Brascamp-Lieb Inequality

One of the key mathematical tools for proving theoretical lower bounds for the
communication cost of nearly any numerical linear algebra computation is the
collection of Hölder-Brascamp-Lieb inequalities. These inequalities bound the
sizes of sets in terms of the sizes of their linear projections. Their
simplest form, the Loomis-Whitney inequality, is already useful for bounding
the communication cost of matrix multiplication (Ballard et al., 2014). When
$A\subset\mathbb{Z}^{3}$ is a finite set of integer lattice points and
$A_{x}$, $A_{y}$, and $A_{z}$ its 2D projections along each axis, the Loomis-
Whitney inequality states

$|A|\leq\sqrt{|A_{x}||A_{y}||A_{z}|}.$

In words, the size of $A$ is bounded in terms of the sizes of its shadows.

Figure 1. Loomis-Whitney inequality $|A|\leq\sqrt{|A_{x}||A_{y}||A_{z}|}$.

To perform 3-nested-loop matrix multiplication, the $(i,j,k)$th operation in
computing $C=AB$ is setting $C[i,k]=A[i,j]B[j,k]$. But these locations are the
projections. So one must access
$|A_{x}|+|A_{y}|+|A_{z}|$ memory locations to perform all $|A|$ operations.
The Loomis-Whitney inequality tells us how many operations we can perform when
accessing a limited number of memory locations.

This idea can be generalized to loop nests of arbitrary size whose array
accesses are affine functions of the indices. The key tool is a generalization
of the Loomis-Whitney inequalities, a discrete formulation of the Hölder-
Brascamp-Lieb inequalities:

###### Theorem 2.4 (Discrete HBL (Christ et al., 2013)).

Let $d$ and $d_{j}$ be nonnegative integers, and for $j=1,\dots,m$ let
$\phi_{j}:\mathbb{Z}^{d}\to\mathbb{Z}^{d_{j}}$ be group homomorphisms. If
$s_{j}\in[0,1]$ for $j=1,\dots,m$ satisfy the following collection of linear
constraints:

$\operatorname{rank}(H)\leq\sum_{j=1}^{m}s_{j}\operatorname{rank}(\phi_{j}(H))\textrm{
for each subgroup }H\leq\mathbb{Z}^{d}$

then we find the bound

$|V|\leq\prod_{j=1}^{m}|\phi_{j}(V)|^{s_{j}}\textrm{ for each finite set
}V\subseteq\mathbb{Z}^{d}.$

This result is stated and proved in detail in Section 3 of (Christ et al.,
2013). We call such a tuple $(s_{1},\dots,s_{m})$ _HBL exponents_ for the _HBL
datum_ $(\mathbb{Z}^{d},(\mathbb{Z}^{d_{j}}),(\phi_{j}))$ and attempt to
minimize the sum of the $s_{j}$ subject to the linear constraints.

These inequalities provide a powerful tool for understanding data movement.
For our purposes, they allow us to bound the number of updates that an
execution of the 7NL CNN algorithm is able to complete if it is only allowed a
certain number of accesses to each array. More specifically, suppose we run
7NL CNN within a single-processor one level memory model with cache size $M$.
We allow the updates to be executed in an arbitrary order. Consider a
continuous segment of updates during the execution which makes exactly $T$
communications with main memory, whether loads from Input or Filter, or stores
to Output. At the start of the segment, we have access to no more than $M$
elements from any of the three arrays, and we may load no more than $T$
elements during the segment. So the number of elements accessible from each
array is at most $M+T$.

Now define three _array access homomorphisms_ which map any tuple of loop
indices $(i_{j})$ to each of the tuples of indices accessed in each array. For
example, $\phi_{O}:\mathbb{Z}^{7}\to\mathbb{Z}^{4}$ defined by
$\phi_{O}(i_{1},\dots,i_{7})=(i_{1},i_{3},i_{4},i_{5})$ is the array access
homomorphism for the Output array as seen in the model presented in Section
2.1. Then any valid tuple of HBL exponents $(s_{j})$ satisfying the
constraints of Theorem 2.4 provides a bound on the size of $V$, the set of
updates the execution may compute during this segment, in terms of the sizes
of the $\phi_{j}(V)$’s, the number of elements which need to be accessed from
each array:

$|V|\leq\prod_{j=1}^{m}|\phi_{j}(V)|^{s_{j}}\leq\prod_{j=1}^{m}(M+T)^{s_{j}}=(M+T)^{\sum_{j}s_{j}}$

Let $s=\sum_{j}s_{j}$. Now, if the entire execution must make $G$ updates,
then splitting the entire execution up into $L$ segments each with about $T$
communications, each segment may do no more than $(M+T)^{s}$ updates and so
there must be at least $G/(M+T)^{s}-1$ segments. Each has $T$ communications,
so the total number of communication must be at least $GT/(M+T)^{s}-T$.
Choosing $T=M$ for now, we find the number of communications to be
$\Omega(G/M^{s-1})$. If one takes the time to compute the optimal $(s_{j})$
for various choices of array access homomorphisms, this exact same proof
sketch results in the well-known asymptotic communication lower bounds one
finds for many common linear algebra algorithms such as those tabulated in
(Ballard et al., 2014). We now discuss how to make practical use of Theorem
2.4. Note that because each rank is an integer between $0$ and $d$, the number
of constraints that we need to check for a given tuple $(s_{1},\dots,s_{j})$
is finite. We can further reduce the workload by showing that the only
subgroups which need to be checked are those in the subgroup lattice generated
by the kernels of the $\phi_{j}$. The _lattice_ generated by a family of
subgroups is the smallest collection of subgroups which contains this family
and which is closed under intersection and sum of subgroups. We denote our
lattice of interest by $\operatorname{Lattice}(\ker\phi_{j})$. This is
formalized in the following proposition:

###### Proposition 2.5.

Let $\phi_{j}$ be homomorphisms and $s_{j}$ exponents as in Theorem 2.4, and
consider $\operatorname{Lattice}(\ker\phi_{j})$, the lattice generated by the
subgroups $\ker\phi_{j}$. If

$\operatorname{rank}(H)\leq\sum_{j=1}^{m}s_{j}\operatorname{rank}(\phi_{j}(H))\textrm{
for each }H\in\operatorname{Lattice}(\ker\phi_{j})$

then

$\operatorname{rank}(H)\leq\sum_{j=1}^{m}s_{j}\operatorname{rank}(\phi_{j}(H))\textrm{
for each subgroup }H\leq\mathbb{Z}^{d}$

and the conclusion of HBL follows.

###### Proof.

Let $\Phi_{j}:\mathbb{Q}^{d}\to\mathbb{Q}^{d_{j}}$ extend $\phi_{j}$ to a
$\mathbb{Q}$-linear map. In Section 2.2 of (Christ et al., 2015), it is proved
that the polytope of $(s_{j})$ satisfying the linear constraints in Theorem
2.4 is exactly equal to the polytope of $(s_{j})$ satisfying, for each
subspace $V\leq\mathbb{Q}^{d}$,

$\dim V\leq\sum_{j=1}^{m}s_{j}\dim\Phi_{j}(V).$

In (Valdimarsson, 2010), Theorem 8 states that it suffices to check only these
inequalities from subspaces in $\operatorname{Lattice}(\ker\Phi_{j})$. To
check these, it suffices to check the original inequalities from Theorem 2.4
on the subgroups in $\operatorname{Lattice}(\ker\phi_{j})$ and then to take
$\mathbb{Q}$-linear spans of these subgroups. This completes the proof. ∎

We can reduce the number of subgroups to check even further. We do this by
splitting $\operatorname{Lattice}(\ker\phi_{j})$ into several independent
sublattices. We call two collections of subgroups $\\{A_{i}\\}$ and
$\\{B_{k}\\}$ _independent_ if $\sum_{i}A_{i}\cap\sum_{k}B_{k}=\\{0\\}$. If
$A=\\{A_{i}\\}$ and $B=\\{B_{k}\\}$ are independent collections, it quickly
follows that

$\displaystyle\operatorname{Lattice}(A\cup B)$
$\displaystyle=\operatorname{Lattice}(A)+\operatorname{Lattice}(B)$
$\displaystyle\operatorname{rank}(A_{i}+B_{k})$
$\displaystyle=\operatorname{rank}(A_{i})+\operatorname{rank}(B_{k})$
$\displaystyle\operatorname{rank}(\phi_{j}(A_{i}+B_{k}))$
$\displaystyle=\operatorname{rank}(\phi_{j}(A_{i}))+\operatorname{rank}(\phi_{j}(B_{k})).$

Then if
$\operatorname{Lattice}(\ker\phi_{j})=\sum_{k}\operatorname{Lattice}(A^{k})$
where the $A^{k}$’s are pairwise independent collections of subgroups, it
suffices to check the constraints in Theorem 2.4 on the subgroups in each
$\operatorname{Lattice}(A^{k})$. As we will see, these reductions are capable
of reducing the number of linear constraints we need to check from hundreds to
only a few. We will leverage this to compute optimal exponent tuples $(s_{j})$
for the array access homomorphisms in 7NL CNN.

##  3\. Single Processor Communication Bounds

###  3.1. Derivation of New Bounds

In this section, we prove Theorem 2.1. Performing an analysis with the HBL
inequalities, we derive precise lower bounds, taking care to optimize
constants. For example, in the standard precision case $p_{I}=p_{F}=p_{O}=1$,
the bound becomes

$X\geq\max\left\\{|I|+|F|+|O|,\frac{9G}{4M}-M,\frac{2G(\sigma_{w}\sigma_{h})^{1/2}}{(w_{F}h_{F}M)^{1/2}}-2M\right\\}$

The first bound doesn’t depend on the memory size. The second bound exhibits
$\Omega(1/M)$ decay, while the third bound exhibits $\Omega(1/M^{1/2})$ decay.
However, it is important to note that the third bound only eclipses the second
bound when $w_{F}h_{F}<\frac{64M\sigma_{w}\sigma_{h}}{81}$, i.e. when the
filters are small relative to the memory size.

We prove each of the three bounds below. For the second and third bound, we
will make use of the HBL theory discussed in Section 2.3. First, we have a
trivial memory-independent bound:

###### Lemma 3.1.

With the setup in Theorem 2.1, the number of words communicated $X$ satisfies

$X\geq p_{I}|I|+p_{F}|F|+p_{O}|O|$

###### Proof.

Every entry of Input and Filter must be accessed at least once, and every
entry in Output must be filled by the computation. All three arrays reside in
slow memory, so at minimum $p_{j}$ words must be communicated for every entry
in the $j$th array, for $j\in\\{I,F,O\\}$. So the number of words communicated
$X$ satisfies

$X\geq
p_{I}\absolutevalue{I}+p_{F}\absolutevalue{F}+p_{O}\absolutevalue{O}\qed$

Before proving the second bound, we perform an HBL analysis on the array-
access homomorphisms corresponding to 7NL CNN. First, we define the
homomorphisms $\phi_{I},\phi_{F},\phi_{O}:\mathbb{Z}^{7}\to\mathbb{Z}^{4}$:

$\displaystyle\phi_{I}(i_{1},i_{2},i_{3},i_{4},i_{5},i_{6},i_{7})$
$\displaystyle=(i_{1},i_{2},i_{6}+\sigma_{w}i_{4},i_{7}+\sigma_{h}i_{5})$
$\displaystyle\phi_{F}(i_{1},i_{2},i_{3},i_{4},i_{5},i_{6},i_{7})$
$\displaystyle=(i_{2},i_{3},i_{6},i_{7})$
$\displaystyle\phi_{O}(i_{1},i_{2},i_{3},i_{4},i_{5},i_{6},i_{7})$
$\displaystyle=(i_{1},i_{3},i_{4},i_{5})$

Note that in Section 2.1 the iteration of 7NL CNN corresponding to the loop
indices $(i_{j})$ uses the data at Input$(\phi_{I}(i_{j}))$ and
Filter$(\phi_{F}(i_{j}))$ to update the data at Output$(\phi_{O}(i_{j}))$. The
discussion in Section 2.3 suggests that we analyze the lattice generated by
the kernels of these homomorphisms. Using the indices $i_{j}$ as free
variables in $\mathbb{Z}$, we can write the kernels as follows:

$\displaystyle\ker\phi_{I}$
$\displaystyle=(0,0,i_{3},i_{4},i_{5},-\sigma_{w}i_{4},-\sigma_{h}i_{5})$
$\displaystyle\ker\phi_{F}$ $\displaystyle=(i_{1},0,0,i_{4},i_{5},0,0)$
$\displaystyle\ker\phi_{O}$ $\displaystyle=(0,i_{2},0,0,0,i_{6},i_{7})$

We can identify the following independent families of indices: $\\{i_{1}\\}$,
$\\{i_{2}\\}$, $\\{i_{3}\\}$, $\\{i_{4},i_{6}\\}$, and $\\{i_{5},i_{7}\\}$. We
call these independent because they give rise to the following pairwise
independent collections of subgroups which generate the kernels we want, and
hence the lattice we want:

$\displaystyle C_{1}$ $\displaystyle=\\{(i_{1},0,0,0,0,0,0)\\}=\\{C_{1,1}\\}$
$\displaystyle C_{2}$ $\displaystyle=\\{(0,i_{2},0,0,0,0,0)\\}=\\{C_{2,1}\\}$
$\displaystyle C_{3}$ $\displaystyle=\\{(0,0,i_{3},0,0,0,0)\\}=\\{C_{3,1}\\}$
$\displaystyle C_{4}$
$\displaystyle=\\{(0,0,0,i_{4},0,0,0),(0,0,0,0,0,i_{6},0),(0,0,0,i_{4},0,-\sigma_{w}i_{4},0)\\}$
$\displaystyle=\\{C_{4,1},C_{4,2},C_{4,3}\\}$ $\displaystyle C_{5}$
$\displaystyle=\\{(0,0,0,0,i_{5},0,0),(0,0,0,0,0,0,i_{7}),(0,0,0,0,i_{5},0,-\sigma_{h}i_{5})\\}$
$\displaystyle=\\{C_{5,1},C_{5,2},C_{5,3}\\}$

These subgroups give the following breakdown of the kernels:

$\displaystyle\ker\phi_{I}$ $\displaystyle=C_{3,1}+C_{4,3}+C_{5,3}$
$\displaystyle\ker\phi_{F}$ $\displaystyle=C_{1,1}+C_{4,1}+C_{5,1}$
$\displaystyle\ker\phi_{O}$ $\displaystyle=C_{2,1}+C_{4,2}+C_{5,2}$

In order to apply Theorem 2.4, the discussion in Section 2.3 concludes that it
suffices to check the constraints only on subgroups in the five lattices,
$\operatorname{Lattice}(C_{j})$. Fortunately,
$\operatorname{Lattice}(C_{j})=C_{j}$ for $j=1,2,3$. For $C_{4}$ and $C_{5}$
we have:

$\displaystyle\operatorname{Lattice}(C_{4})$
$\displaystyle=C_{4}\cup\\{(0,0,0,i_{4},0,i_{6},0)\\}=C_{4}\cup\\{C_{4,4}\\}$
$\displaystyle\operatorname{Lattice}(C_{5})$
$\displaystyle=C_{5}\cup\\{(0,0,0,0,i_{5},0,i_{7})\\}=C_{5}\cup\\{C_{5,4}\\}$

Now suppose $s_{I},s_{F},s_{O}\in[0,1]$. Then to apply Theorem 2.4, we need to
satisfy the following inequality for each $H$ in some
$\operatorname{Lattice}(C_{j})$:

$\operatorname{rank}(H)\leq
s_{I}\operatorname{rank}(\phi_{I}(H))+s_{F}\operatorname{rank}(\phi_{F}(H))+s_{O}\operatorname{rank}(\phi_{O}(H)).$

We enumerate these inequalities in the table below:

$H$ | $\mathrm{rk}$ | $\mathrm{rk}\circ\phi_{I}$ | $\mathrm{rk}\circ\phi_{F}$ | $\mathrm{rk}\circ\phi_{O}$ | Constraint
---|---|---|---|---|---
$C_{1,1}$ | 1 | 1 | 0 | 1 | $1\leq s_{I}+s_{O}$
$C_{2,1}$ | 1 | 1 | 1 | 0 | $1\leq s_{I}+s_{F}$
$C_{3,1}$ | 1 | 0 | 1 | 1 | $1\leq s_{F}+s_{O}$
$C_{4,1}$ | 1 | 1 | 0 | 1 | $1\leq s_{I}+s_{O}$
$C_{4,2}$ | 1 | 1 | 1 | 0 | $1\leq s_{I}+s_{F}$
$C_{4,3}$ | 1 | 0 | 1 | 1 | $1\leq s_{F}+s_{O}$
$C_{4,4}$ | 2 | 1 | 1 | 1 | $2\leq s_{I}+s_{F}+s_{O}$
$C_{5,1}$ | 1 | 1 | 0 | 1 | $1\leq s_{I}+s_{O}$
$C_{5,2}$ | 1 | 1 | 1 | 0 | $1\leq s_{I}+s_{F}$
$C_{5,3}$ | 1 | 0 | 1 | 1 | $1\leq s_{F}+s_{O}$
$C_{5,4}$ | 2 | 1 | 1 | 1 | $2\leq s_{I}+s_{F}+s_{O}$

Removing repeated inequalities, Theorem 2.4 states that as long as $1\leq
s_{I}+s_{F}$, $1\leq s_{I}+s_{O}$, $1\leq s_{F}+s_{O}$, and $2\leq
s_{I}+s_{F}+s_{O}$, then for any finite set $V\subseteq\mathbb{Z}^{7}$ we
have:

$|V|\leq|\phi_{I}(V)|^{s_{I}}|\phi_{F}(V)|^{s_{F}}|\phi_{O}(V)|^{s_{O}}.$

We can now begin the proof of the second bound. First, we handle the case when
the triangle condition is met.

###### Lemma 3.2.

With the setup in Theorem 2.1, as long as $p_{I}\leq p_{F}+p_{O}$, $p_{F}\leq
p_{I}+p_{O}$, and $p_{O}\leq p_{I}+p_{F}$, the number of words communicated
$X$ satisfies

$X\geq\frac{(p_{I}+p_{F}+p_{O})^{2}G}{4M}-M$

###### Proof.

We split the execution of the 7NL CNN computation into $L$ segments of
contiguous updates. In each segment, we allow exactly $T$ words to be
loaded/stored, except for possibly the last segment which may have $\leq T$
words.

We fix our attention to a single segment. Let $V$ be the set of indices of
updates computed during the current segment. $V$ contains tuples
$(i_{j})\in\mathbb{Z}^{7}$. Then $\phi_{I}(V)$ is the set of indices of Input
whose data must be accessed during the segment, $\phi_{F}(V)$ the set of
indices of Filter, and $\phi_{O}(V)$ the set of indices of Output. We have at
most $M$ words of data in fast memory before the segment begins, and may load
at most $T$ more during the segment. The number of words we access from the
$j$th array during the segment is $p_{j}|\phi_{j}(V)|$. Then the number of
words we access during this segment is

$p_{I}|\phi_{I}(V)|+p_{F}|\phi_{F}(V)|+p_{O}|\phi_{O}(V)|\leq M+T.$

Let $s_{I}$, $s_{F}$, and $s_{O}$ satisfy $1\leq s_{I}+s_{F}$, $1\leq
s_{I}+s_{O}$, $1\leq s_{F}+s_{O}$, and $2\leq s_{I}+s_{F}+s_{O}$. The
discussion in Section 2.3 suggests that we require $s_{I}+s_{F}+s_{O}=2$ in
order to obtain the best asymptotic lower bound. Then by the HBL inequality
proved above, we find

$|V|\leq|\phi_{I}(V)|^{s_{I}}|\phi_{F}(V)|^{s_{F}}|\phi_{O}(V)|^{s_{O}}.$

Let $v_{j}:=2p_{j}|\phi_{j}(V)|/(M+T)$. The inequality becomes

$|V|\leq\frac{(M+T)^{2}}{4}(v_{I}/p_{I})^{s_{I}}(v_{F}/p_{F})^{s_{F}}(v_{O}/p_{O})^{s_{O}}.$

The number of updates $|V|$ possible during this segment is bounded by $C\max
v_{I}^{s_{I}}v_{F}^{s_{F}}v_{O}^{s_{O}}$ subject to the constraint
$v_{1}+v_{2}+v_{3}\leq 2$.

We assume $v_{I}+v_{F}+v_{O}=2$ and apply Lagrange multipliers:

$\displaystyle v_{I}+v_{F}+v_{O}$ $\displaystyle=2$ $\displaystyle
s_{I}v_{I}^{s_{I}-1}v_{F}^{s_{F}}v_{O}^{s_{O}}=s_{F}v_{F}^{s_{F}-1}v_{I}^{s_{I}}v_{O}^{s_{O}}=s_{O}v_{O}^{s_{O}-1}v_{I}^{s_{I}}v_{F}^{s_{F}}$
$\displaystyle=\lambda$

Taking an inner product with $(v_{I},v_{F},v_{O})$ we find:

$(s_{I}+s_{F}+s_{O})v_{I}^{s_{I}}v_{F}^{s_{F}}v_{O}^{s_{O}}=\lambda(v_{I}+v_{F}+v_{O})\quad\implies\quad
v_{I}^{s_{I}}v_{F}^{s_{F}}v_{O}^{s_{O}}=\lambda$

since $s_{I}+s_{F}+s_{O}=2=v_{I}+v_{F}+v_{O}$. Substituting into each equation
and dividing, we find $s_{I}=v_{I}$, $s_{F}=v_{F}$, $s_{O}=v_{O}$. Then we
have shown that the maximum number of updates during the current segment is

$|V|\leq\frac{1}{4}(M+T)^{2}(s_{I}/p_{I})^{s_{I}}(s_{F}/p_{F})^{s_{F}}(s_{O}/p_{O})^{s_{O}}$

This holds for all triples $(s_{j})$ with $s_{I}+s_{F}+s_{O}=2$ and
$s_{I},s_{F},s_{O}\leq 1$. In particular, it holds for the triple $(s_{j})$
which minimize the right hand side. We apply Lagrange multipliers again
ignoring the last three constraints on the $s_{j}$:

$\displaystyle s_{I}+s_{F}+s_{O}$ $\displaystyle=2$
$\displaystyle(1+\log(s_{I}/p_{I}))(s_{I}/p_{I})^{s_{I}}(s_{F}/p_{F})^{s_{F}}(s_{O}/p_{O})^{s_{O}}$
$\displaystyle=\lambda$
$\displaystyle(1+\log(s_{F}/p_{F}))(s_{I}/p_{I})^{s_{I}}(s_{F}/p_{F})^{s_{F}}(s_{O}/p_{O})^{s_{O}}$
$\displaystyle=\lambda$
$\displaystyle(1+\log(s_{O}/p_{O}))(s_{I}/p_{I})^{s_{I}}(s_{F}/p_{F})^{s_{F}}(s_{O}/p_{O})^{s_{O}}$
$\displaystyle=\lambda$

Equating and dividing by
$(s_{I}/p_{I})^{s_{I}}(s_{F}/p_{F})^{s_{F}}(s_{O}/p_{O})^{s_{O}}$ we find
$s_{I}/p_{I}=s_{F}/p_{F}=s_{O}/p_{O}$. This leads to
$s_{j}=2p_{j}/(p_{I}+p_{F}+p_{O})$. Note that these minimizers always satisfy
$s_{j}\leq 1$ for all $j$. Indeed, the triangle condition guarantees
$2p_{j}\leq p_{I}+p_{F}+p_{O}$ for all $j$. Then we have shown that the
maximum number of computations during any segment is

$\displaystyle|V|$
$\displaystyle\leq\frac{1}{4}(M+T)^{2}(s_{I}/p_{I})^{s_{I}}(s_{F}/p_{F})^{s_{F}}(s_{O}/p_{O})^{s_{O}}$
$\displaystyle=\frac{1}{4}(M+T)^{2}\left(\frac{2}{p_{I}+p_{F}+p_{O}}\right)^{2}=\frac{(M+T)^{2}}{(p_{I}+p_{F}+p_{O})^{2}}$

Since we must do $G$ updates in total, the total number of segments is bounded
below:

$L\geq\left\lfloor\frac{G}{|V|}\right\rfloor\geq\frac{(p_{I}+p_{F}+p_{O})^{2}G}{(M+T)^{2}}-1$

Each segment besides the last has $T$ loads/stores, so the total number of
words moved is:

$X\geq
T\left(\frac{(p_{I}+p_{F}+p_{O})^{2}G}{(M+T)^{2}}-1\right)=\frac{(p_{I}+p_{F}+p_{O})^{2}TG}{(M+T)^{2}}-T$

To choose optimal segment length, we note that $T/(M+T)^{2}$ is maximized when
$T=M$ and we find the following lower bound on the communication cost:

$X\geq\frac{(p_{I}+p_{F}+p_{O})^{2}G}{4M}-M\qed$

Should the triangle condition fail, we slightly modify the last proof by
finding a valid set of minimizers. Note that only one of the three constraints
may fail at once: if $p_{j}>p_{k}+p_{\ell}$, then $p_{k}+p_{j}>p_{\ell}$.

###### Lemma 3.3.

With the setup in Theorem 2.1, if $p_{j}>p_{k}+p_{\ell}$ for some distinct
$j,k,\ell\in\\{I,F,O\\}$, the number of words communicated $X$ satisfies

$X\geq\frac{p_{j}(p_{k}+p_{\ell})G}{M}-M$

###### Proof.

The proof is the same as the proof of Lemma 3.2, except now we prescribe
$s_{j}=1$ and $s_{k}+s_{\ell}=1$. This guarantees that all conditions for HBL
are met. We maximize $(s_{k}/p_{k})^{s_{k}}(s_{\ell}/p_{\ell})^{s_{\ell}}$
with respect to $s_{k}$ and $s_{\ell}$ as before, and find
$s_{k}/p_{k}=s_{\ell}/p_{\ell}$. This leads to $s_{k}=p_{k}/(p_{k}+p_{\ell})$
and $s_{\ell}=p_{\ell}/(p_{k}+p_{\ell})$. All constraints are satisfied. Pick
$T=M$. Then we have shown that the maximum number of computations during any
segment is

$\displaystyle|V|$
$\displaystyle\leq\frac{1}{4}(2M)^{2}(s_{j}/p_{j})^{s_{j}}(s_{k}/p_{k})^{s_{k}}(s_{\ell}/p_{\ell})^{s_{\ell}}$
$\displaystyle=\frac{1}{4}(2M)^{2}\frac{1}{p_{j}}\left(\frac{1}{p_{k}+p_{\ell}}\right)^{s_{j}+s_{k}}=\frac{(M+T)^{2}}{4p_{j}(p_{k}+p_{\ell})}$

We convert this into a communication bound as in Lemma 3.2:

$X\geq\frac{p_{j}(p_{k}+p_{\ell})G}{M}-M\qed$

When $M>(C_{p}G)^{1/2}$, the previous bounds become trivial. When the filter
size $w_{F}h_{F}$ is small relative to $M$, we are able to reduce the decay in
our bounds from $1/M$ to $1/M^{1/2}$ and extend them to larger memory sizes.
To show this third “small filter” bound, we rewrite the problem and exploit
new array access homomorphisms. In particular, we rewrite the loops over
$i_{6}$ and $i_{7}$ as loops over $q_{6},r_{6},q_{7},r_{7}$. We have
$i_{6}=\sigma_{w}q_{6}+r_{6}$ for $r_{6}\in[0,\sigma_{w}-1]$ and
$q_{6}\in[0,w_{F}/\sigma_{w}-1]$, and we similarly divide $i_{7}$ by
$\sigma_{h}$ for $q_{7}$ and $r_{7}$. This has the effect of lifting $Input$
and $Filter$ to higher dimensional arrays, with 6 indices instead of 4. Under
the lift, we make the following accesses to each array during an update:

$\displaystyle\mathrm{Input}(i_{1},i_{2},i_{4}+q_{6},r_{6},i_{5}+q_{7},r_{7})$
$\displaystyle\mathrm{Filter}(i_{2},i_{3},q_{6},r_{6},q_{7},r_{7})$
$\displaystyle\mathrm{Output}(i_{1},i_{3},i_{4},i_{5})$

In our proof, we will find it valuable to fix the indices $q_{6}$ and $q_{7}$.
A new collection of array access homomorphisms ignores these. With an implicit
translation by $\vec{q}=(q_{6},q_{7})$, we define the homomorphisms
$\phi_{I}^{\prime},\phi_{O}^{\prime}:\mathbb{Z}^{7}\to\mathbb{Z}^{4}$,
$\phi_{F}^{\prime}:\mathbb{Z}^{7}\to\mathbb{Z}^{6}$:

$\displaystyle\phi_{I}^{\prime}(i_{1},i_{2},i_{3},i_{4},i_{5},r_{6},r_{7})$
$\displaystyle=(i_{1},i_{2},i_{4},r_{6},i_{5},r_{7})$
$\displaystyle\phi_{F}^{\prime}(i_{1},i_{2},i_{3},i_{4},i_{5},r_{6},r_{7})$
$\displaystyle=(i_{2},i_{3},r_{6},r_{7})$
$\displaystyle\phi_{O}^{\prime}(i_{1},i_{2},i_{3},i_{4},i_{5},r_{6},r_{7})$
$\displaystyle=(i_{1},i_{3},i_{4},i_{5})$

Each homomorphism selects a subset of the indices, and every index appears in
exactly two of the homomorphisms. This is the case of a tensor contraction
analyzed in Section 6.3 of (Christ et al., 2013). They find the optimal HBL
exponents to be $s_{I}=s_{F}=S_{O}=1/2$ and an HBL inequality for finite
subsets $V$ of $\mathbb{Z}^{7}$,

$|V|\leq|\phi_{I}^{\prime}(V)|^{1/2}|\phi_{F}^{\prime}(V)|^{1/2}|\phi_{O}^{\prime}(V)|^{1/2}.$

We can now begin the proof of the third bound.

###### Lemma 3.4.

The number of words communicated $X$ satisfies

$X\geq\frac{2(p_{I}p_{F}p_{O})^{1/2}(\sigma_{w}\sigma_{h})^{1/2}G}{(w_{F}h_{F}M)^{1/2}}-2M$

###### Proof.

We split the 7NL CNN computation into $L$ segments with $T$ loads/stores as
before. Let $V$ be the set of updates computed during a given segment. For
fixed indices $\vec{q}=(q_{6},q_{7})$, let $V(\vec{q})$ be the slice of $V$
with those two coordinates held constant: $V(\vec{q})=\pi^{-1}(\vec{q})$ where
$\pi$ is the projection of $\mathbb{Z}^{9}$ onto the $\vec{q}$ coordinates.
Then to compute every update in $V(\vec{q})$ we must access the entries of
Input corresponding to indices $\phi_{I}^{\prime}(V(\vec{q}))$, and similarly
for Filter and Output (we embed $V(\vec{q})$ in the domain of
$\phi_{I}^{\prime}$ by ignoring the constant $\vec{q}$ coordinates). We apply
our HBL inequality to $V(\vec{q})$,

$|V(\vec{q})|\leq|\phi_{I}^{\prime}(V(\vec{q}))|^{1/2}|\phi_{F}^{\prime}(V(\vec{q}))|^{1/2}|\phi_{O}^{\prime}(V(\vec{q}))|^{1/2}$

Note that $V$ is the disjoint union of the $V(\vec{q})$’s. Also, the set of
indices of $Filter$ accessed is the disjoint union of the
$\phi^{\prime}_{F}(V(\vec{q}))$’s. Let $u$ be the number of indices of $Input$
accessed during the segment, $v$ the number of indices of $Output$ accessed
during the segment, and $w(\vec{q})=|\phi_{F}^{\prime}(V(\vec{q}))|$ the
number of indices of Filter accessed by each slice. We have:

$\displaystyle|\phi^{\prime}_{I}(V(\vec{q}))|$ $\displaystyle\leq
u,\quad\absolutevalue{\phi^{\prime}_{O}(V(\vec{q}))}\leq
v\qquad\forall\vec{q}$
$\displaystyle\Big{|}{\textstyle\bigcup}_{\vec{q}}V(\vec{q})\\}\Big{|}$
$\displaystyle={\textstyle\sum}_{\vec{q}}w(\vec{q})$

We have at most $M$ words in memory before the segment begins, and may load at
most $T$ more:

$p_{I}u+p_{O}v+p_{F}{\textstyle\sum}_{\vec{q}}w(\vec{q})\leq M+T$

Using our HBL inequality,

$\displaystyle|V|$
$\displaystyle={\textstyle\sum}_{\vec{q}}\left|V(\vec{q})\right|\leq
u^{1/2}v^{1/2}{\textstyle\sum}_{\vec{q}}w(\vec{q})^{1/2}$

The max of $u^{1/2}v^{1/2}\sum_{\vec{q}}w(\vec{q})^{1/2}$ over
$p_{I}u+p_{O}v+p_{F}\sum_{\vec{q}}w(\vec{q})\leq M+T$ bounds the number of
updates during our segment. We assume equality and apply Lagrange multipliers:

(2) $\displaystyle p_{I}u+p_{O}v+p_{F}{\textstyle\sum}_{\vec{q}}w(\vec{q})$
$\displaystyle=M+T$ (3)
$\displaystyle\frac{1}{2}\frac{v^{1/2}}{u^{1/2}}{\textstyle\sum}_{\vec{q}}w(\vec{q})^{1/2}$
$\displaystyle=p_{I}\lambda$ (4)
$\displaystyle\frac{1}{2}\frac{u^{1/2}}{v^{1/2}}{\textstyle\sum}_{\vec{q}}w(\vec{q})^{1/2}$
$\displaystyle=p_{O}\lambda$ (5)
$\displaystyle\frac{1}{2}u^{1/2}v^{1/2}w(\vec{q})^{-1/2}$
$\displaystyle=p_{F}\lambda\qquad\forall\vec{q}$

Then by dividing (3) and (4), $p_{I}u=p_{O}v$. Equating instances of (5), all
the $w(\vec{q})=:w$ are equal. There are
$\frac{w_{F}h_{F}}{\sigma_{w}\sigma_{h}}$ pairs of $(\vec{q})$, so equating
(3) and (5),

$\frac{1}{p_{I}}{\textstyle\sum}_{\vec{q}}w(\vec{q})^{1/2}=\frac{1}{p_{I}}\frac{w_{F}h_{F}}{\sigma_{w}\sigma_{h}}w^{1/2}=\frac{u}{p_{F}w^{1/2}}$

so that $p_{F}w=\frac{\sigma_{w}\sigma_{h}}{w_{F}h_{F}}p_{I}u$. Then by (1),
the maximizing values are
$u=\frac{M+T}{3p_{I}}$, $v=\frac{M+T}{3p_{O}}$, and
$w(\vec{q})=\frac{\sigma_{w}\sigma_{h}}{w_{F}h_{F}}\frac{M+T}{3p_{F}}$ for all
$\vec{q}$. Using these values, the maximum number of updates during this
segment is

$\displaystyle|V|$ $\displaystyle\leq
u^{1/2}v^{1/2}{\textstyle\sum}_{\vec{q}}w(\vec{q})^{1/2}\leq\frac{(M+T)^{3/2}}{3^{3/2}(p_{I}p_{F}p_{O})^{1/2}}\frac{(w_{F}h_{F})^{1/2}}{(\sigma_{w}\sigma_{h})^{1/2}}$

and the number of segments $L$ is bounded below by

$L\geq\left\lfloor\frac{G}{|V|}\right\rfloor\geq\frac{3^{3/2}(p_{I}p_{F}p_{O})^{1/2}(\sigma_{w}\sigma_{h})^{1/2}G}{(w_{F}h_{F})^{1/2}(M+T)^{3/2}}-1$

Each segment besides the last has at most $T$ loads/stores, so the
communication cost is

$X\geq\frac{3^{3/2}(p_{I}p_{F}p_{O})^{1/2}(\sigma_{w}\sigma_{h})^{1/2}TG}{(w_{F}h_{F})^{1/2}(M+T)^{3/2}}-T$

To choose optimal segment length, we note that $T/(M+T)^{3/2}$ is maximized
when $T=2M$ and we find the communication cost

$X\geq\frac{2(p_{I}p_{F}p_{O})^{1/2}(\sigma_{w}\sigma_{h})^{1/2}G}{(w_{F}h_{F}M)^{1/2}}-2M\qed$

Taken together, Lemmas 3.1, 3.2, 3.3, and 3.4 complete the proof of Theorem
2.1.

###  3.2. Attainability

We now discuss practical algorithms for attaining the previously presented
communication bounds. We will focus on four algorithms in particular: im2col,
blocking, Winograd convolutions, and FFT convolutions. im2col (San Juan et
al., 2020), Winograd (Meng and Brothers, 2019), and FFT techniques (Zlateski
et al., 2019) for performing convolutions are all well documented in the
literature. We will focus on designing improved blocking algorithms. For loop
bounds $(N,c_{I},c_{O},w_{O},h_{O},w_{F},h_{F})$ we call

$B=(b_{N},b_{c_{I}},b_{c_{O}},b_{w_{O}},b_{h_{O}},b_{w_{F}^{\prime}},b_{h_{F}^{\prime}},b_{w_{F}^{\prime\prime}},b_{h_{F}^{\prime}})$

a blocking. Note that we are using a small filter trick in the style of
(Demmel and Rusciano, 2016). To obtain a communication-optimal blocking, we
use a linear program. For each bound variable, we have a lower bound of $1$
and an appropriate upper bound, being the corresponding array sizes for most
indices, and an expression of the filter size and strides for the filter
indices $q_{6},q_{7},r_{6}$, and $r_{7}$. Additionally, we know that the three
blocks of the output, image, and filter must all simultaneously fit in memory.
We thus have that

$\displaystyle p_{O}b_{N}b_{c_{O}}b_{w_{O}}b_{h_{O}}$
$\displaystyle\leq\frac{p_{O}M}{p_{T}}$ (6) $\displaystyle
p_{F}b_{c_{I}}b_{c_{O}}b_{w_{F^{\prime}}}b_{w_{F^{\prime\prime}}}b_{h_{F^{\prime}}}b_{h_{F^{\prime\prime}}}$
$\displaystyle\leq\frac{p_{F}M}{p_{T}}$ $\displaystyle
p_{I}b_{N}b_{c_{I}}(b_{w_{O}}+b_{w_{F^{\prime}}})(b_{h_{O}}+b_{h_{F^{\prime}}})b_{w_{F^{\prime\prime}}}b_{h_{F^{\prime\prime}}}$
$\displaystyle\leq\frac{p_{I}M}{p_{T}}$

We expand the last term into four terms, each bounded by $\frac{M}{12}$. Then,
taking logarithms and setting up the linear program, we have for our vector
$x=\log B$ elementwise, the problem of maximizing $c^{T}x$ where

$c^{T}=\begin{bmatrix}1&1&1&1&1&1&1&1&1\end{bmatrix}$

subject to the constraints $Ax\leq b$ where

$A=\begin{bmatrix}1&0&1&1&1&0&0&0&0\\\ 0&1&1&0&0&1&1&1&1\\\
1&1&0&1&1&0&1&0&1\\\ 1&1&0&1&0&0&1&1&1\\\ 1&1&0&0&1&1&1&0&1\\\
1&1&0&0&0&1&1&1&1\end{bmatrix}\textrm{ and
}b=\begin{bmatrix}1-\log_{M}p_{T}\\\ 1-\log_{M}p_{T}\\\ 1-\log_{M}4p_{T}\\\
1-\log_{M}4p_{T}\\\ 1-\log_{M}4p_{T}\\\ 1-\log_{M}4p_{T}\end{bmatrix}$

We solve this linear program and take exponentials to find our blocking. Using
a linear program, we can asymptotically meet the lower bounds we have derived.
To compare the various algorithms for performing the convolution, we
symbolically calculate the amount of communication each one requires. We use
the FFT communication bound provided in (Elango, 2016) and the matrix
multiplication communication bound provided in (Kwasniewski et al., 2019) to
compute the relevant communication volumes. We compute communication volumes
using parameters taken from AlexNet. We compare these four with the bounds
derived in 3.1 and the communication for a naive convolution. The parameters
used are taken from (He et al., 2016). The results are presented in Figure 1.

Figure 2. Theoretically computed communication volumes for mixed precision
ResNet50 layers 1 and 2, relative to the communication bound. We take
$\sigma_{I}=\sigma_{F}=1$ and $\sigma_{O}=2$. Layer 1 refers to conv1 and
layer 2 refers to conv2_x as specified in (He et al., 2016). We use a batch
size of $1000$. We see that in general, communication volumes are a constant
multiple of the communication bound. However, we do see scaling in blocking,
and for conv2_x, the strides of 1 are more favorable to the blocking, and
blocking beats im2col for sufficiently large memory sizes. Convolutional
layers conv3_x, conv4_x, and conv5_x, which are not depicted, resemble
conv2_x.

We observe several trends. Blocking and im2col scale better than FFT and
Winograd in the memory size, and the relative performance of blocking and
im2col is dependent on the ratio $\frac{\sigma_{w}\sigma_{h}}{w_{F}h_{F}}$.
This is expected because of how the small filter blocking is used. We note
that in all cases, the communication bound is not attained precisely. Work
remains to either strengthen the communication bound or devise better
algorithms to meet the bound.

##  4\. Parallel Communication Bounds

###  4.1. Derivation of New Bounds

In this section, we prove Theorems 2.2 and 2.3. These provide lower bounds for
the number of words communicated in a distributed memory parallel processor
memory model, with $P$ processors each with local memory size $M$. We assume
that all the data is non-overlapping. A single word of communication
corresponds to the transmission of one word of data from any one processor to
any other. Each array has its own precision.

We now prove Theorem 2.2. For this result, the input data may begin
distributed among the local memories in any configuration and the output data
may reside anywhere in memory at the end of the execution. In the case
$p_{I}=p_{F}=p_{O}=1$, Theorem 2.2 becomes

$X\geq\max\left\\{\frac{9G}{4PM}-M,\frac{2G(\sigma_{w}\sigma_{h})^{1/2}}{P(w_{F}h_{F}M)^{1/2}}-2M\right\\}.$

###### Proof of Theorem 2.2.

Some processor must perform at least $G/P$ of the updates. Splitting the
computations executed by this processor into segments, each having a total of
$M$ words communicated into and out of the processor, we need to bound the
number of computations possible in a segment. By the same technique as in
Lemmas 3.2 and 3.3, we find that the number of calculations $|V|$ possible in
a segment is $|V|\leq M^{2}/C_{p}$. Since we must do at least $G/P$ updates,
the total number of segments is bounded below:

$L\geq\frac{G}{P|V|}-1\geq\frac{C_{p}G}{PM^{2}}-1$

and the number of words communicated by this processor is

$X\geq ML\geq\frac{C_{p}G}{PM}-M$

This is the first term in the desired lower bound. Now, instead splitting into
segments with $2M$ communications and using the technique in Lemma 3.4, we
find that the number of calculations $|V|$ possible in a segment is

$|V|\leq\frac{M^{3/2}}{(p_{I}p_{F}p_{O})^{1/2}}\left(\frac{w_{F}h_{F}}{\sigma_{w}\sigma_{h}}\right)^{1/2}$

Since we must do at least $G/P$ updates, and as before the number of words
communicated by this processor is

$X\geq
2M\left(\frac{G}{P|V|}-1\right)\geq\frac{2(p_{I}p_{F}p_{O})^{1/2}(\sigma_{w}\sigma_{h})^{1/2}G}{P(w_{F}h_{F}M)^{1/2}}-2M$

This is the second term in the desired lower bound. ∎

When $M>\frac{3G^{1/2}}{2P^{1/2}}$ and
$M>\frac{G^{2/3}(\sigma_{w}\sigma_{h})^{1/3}}{P^{2/3}(w_{F}h_{F})^{1/3}}$,
both of the above lower bounds are trivial. This becomes a concern if the
memory size per processor or the number of processors is large relative to the
size of the computation. Taking inspiration from the methods in (Demmel et
al., 2013) which introduce lower bounds for parallel matrix multiplication
corresponding to 2.5D algorithms, we find memory independent lower bounds in
Theorem 2.3. Now we make a load balancing assumption on each of the three
arrays: image, filter, and output data are all evenly distributed across the
processors. When $p_{I}=p_{F}=p_{O}=1$, the bound is

$X\geq\max\left\\{\frac{G^{1/2}}{P^{1/2}}-\frac{A_{p}}{P},\frac{(G\sigma_{w}\sigma_{h})^{2/3}}{(Pw_{F}h_{F})^{2/3}}-\frac{A_{p}}{P}\right\\}.$

###### Proof.

Recall that in Lemma 3.2 we show that if $V$ is any subset of indices of
updates of 7NL CNN, then we can bound the size of $V$:

$\displaystyle|V|$
$\displaystyle\leq|\phi_{I}(V)|^{2/3}|\phi_{F}(V)|^{2/3}|\phi_{O}(V)|^{2/3}$
$\displaystyle=\frac{1}{(p_{I}p_{F}p_{O})^{2/3}}(p_{I}|\phi_{I}(V)|)^{2/3}(p_{F}|\phi_{F}(V)|)^{2/3}(p_{O}|\phi_{O}(V)|)^{2/3}$

Because the total number of updates is $G$, one processor must do at least
$G/P$ updates. Let $V$ be the set of all iterations performed by this
processor. Then for at least one $j\in\\{I,F,O\\}$, we must have

$\frac{G^{1/3}}{P^{1/3}}=|V|^{1/3}\leq\frac{1}{(p_{I}p_{F}p_{O})^{2/9}}(p_{j}|\phi_{j}(V)|)^{2/3}.$

So the processor must access at least $(p_{I}p_{F}p_{O})^{1/3}G^{1/2}/P^{1/2}$
words from some array during the full computation. Recall that
$A_{p}:=\max\\{p_{I}|I|,p_{F}|F|,p_{O}|O|\\}$. At most $A_{p}/P$ words from
this array are accessible to the processor at the beginning of the computation
by the load balancing assumption, therefore this processor must receive at
least $X$ words of data from other processors, where

$X\geq\frac{(p_{I}p_{F}p_{O})^{1/3}G^{1/2}}{P^{1/2}}-\frac{A_{p}}{P}.$

Similarly, in Lemma 3.4 we show that $V$ has size:

$\displaystyle|V|$
$\displaystyle\leq{\textstyle\sum}_{\vec{q}}|\phi_{I}^{\prime}(V(\vec{q}))|^{1/2}|\phi_{F}^{\prime}(V(\vec{q}))|^{1/2}|\phi_{O}^{\prime}(V(\vec{q}))|^{1/2}$
$\displaystyle\leq\frac{w_{F}h_{F}}{\sigma_{w}\sigma_{h}}|\phi_{I}(V)|^{1/2}|\phi_{F}(V)|^{1/2}|\phi_{O}(V)|^{1/2}$

Then for at least one $j\in\\{I,F,O\\}$, it must be true that

$\frac{G^{1/3}}{P^{1/3}}=|V|^{1/3}\leq\left(\frac{w_{F}h_{F}}{\sigma_{w}\sigma_{h}}\right)^{1/3}\frac{1}{(p_{I}p_{F}p_{O})^{1/6}}(p_{j}|\phi_{j}(V)|)^{1/2}.$

So the processor accesses
$(p_{I}p_{F}p_{O})^{1/3}(G\sigma_{w}\sigma_{h})^{2/3}/(Pw_{F}h_{F})^{2/3}$
words from some array during the full computation. At most $A_{p}/P$ words
from this array are accessible to the processor at the beginning of the
computation, so the processor must receive at least $X$ words of data from
other processors, where

$X\geq\frac{(p_{I}p_{F}p_{O})^{1/3}(G\sigma_{w}\sigma_{h})^{2/3}}{(Pw_{F}h_{F})^{2/3}}-\frac{A_{p}}{P}.$

Combining the two lower bounds proves the theorem. ∎

Note that as in the single processor case, the lower bounds come in pairs, the
second eclipsing the first when the filter is sufficiently small. We now
discuss the attainability of these results.

###  4.2. Attainability

We now discuss algorithms for attaining the previously presented communication
bounds, focusing once again on im2col, blocking, Winograd, and FFT. For
blocking, instead of blocking in the memory size, we block in the number of
processors. For each loop variable, we have a corresponding parallel blocking
variable $a_{(\cdot)}$ representing the segment of the loop variable being
assigned to each processor. We then have the blocking

$B=(a_{N},a_{c_{I}},a_{c_{O}},a_{w_{O}},a_{h_{O}},a_{w_{F}},a_{h_{F}})$

and each processor then does
$a_{N}a_{c_{I}}a_{c_{O}}a_{w_{O}}a_{h_{O}}a_{w_{F}}a_{h_{F}}$ computations. We
do not use an additional small filter blocking in this instance. To find the
blocking, we once again take logarithms, giving us the following linear
program: for a variable $x=\log\\{B\\}$ we maximize $c^{T}x$ for

$c^{T}=\begin{bmatrix}1&1&1&1&1&1&1\end{bmatrix}$

subject to $Ax\leq b$ where

$A=\begin{bmatrix}-1&0&-1&-1&-1&0&0\\\ 0&-1&-1&0&0&-1&-1\\\
-1&-1&0&-1&-1&0&0\\\ -1&-1&0&-1&0&0&-1\\\ -1&-1&0&0&-1&-1&0\\\
-1&-1&0&0&0&-1&-1\\\ -1&-1&-1&-1&-1&-1&-1\end{bmatrix}$

and

$b=\begin{bmatrix}1-\log_{P}p_{T}-\log_{P}Nc_{O}w_{F}h_{F}\\\
1-\log_{P}p_{T}-\log_{P}c_{I}c_{O}w_{O}h_{O}\\\
1-\log_{P}4p_{T}-\log_{P}Nc_{I}w_{F}h_{F}\\\
1-\log_{P}4p_{T}-\log_{P}Nc_{I}w_{F}h_{O}\\\
1-\log_{P}4p_{T}-\log_{P}Nc_{I}h_{C}w_{F}\\\
1-\log_{P}4p_{T}-\log_{P}Nc_{I}w_{O}h_{O}\\\
1-\log_{P}Nc_{I}c_{O}w_{O}h_{O}w_{F}h_{F}\end{bmatrix}$

To compare the four algorithms, we once again symbolically compute the amount
of communication each one requires, and we compare it with the bounds given in
4.1. One should note that the communication models used in the three different
bounds for our work, (Kwasniewski et al., 2019) for matrix multiplication, and
(Elango, 2016) for FFT are not quite the same. However, there is a
straightforward conversion between them. The difference between the memory
models is the assumption as to whether the data initially resides outside of
the distributed network or inside of it. To convert between these, we simply
add or subtract the total size of the problem
$\absolutevalue{\text{Image}}+\absolutevalue{\text{Filter}}+\absolutevalue{\text{Output}}$.
The results are presented in Figure 2.

Figure 3. Theoretically computed communication volumes for parallel ResNet
layers 1 and 2, with $p_{I}=p_{F}=1$ and $p_{O}=2$, as a multiple of the
communication bound, as the number of processors increases. Layer 1 refers to
conv2 and layer 2 refers to conv2_x. We use a batch size of $1000$. We see
that blocking outperforms im2col considerably, especially for layer 2.
Convolutional layers conv3_x, conv4_x, and conv5_x, which are not depicted,
resemble conv2_x. The dashes lines for conv2_x do not begin at the smallest
number of processors because of assumptions on the memory model. We see that
blocking performs better than im2col in almost all cases, with significant
improvements in conv2_x when $\sigma_{x}=\sigma_{y}=1$ is more favorable to
blocking.

In both cases, we note that the communication bound goes to 0 very quickly as
the number of processors increases. Additionally, we note that for blocking,
we have the additional hypothesis that all of the inputs/filter/output
elements can reside in the distributed memory, so this method of blocking is
not immediately feasible for smaller numbers of processors. However, we see
that when blocking is applicable, it rapidly reaches the communication bound
as the number of processors increases. We note that Winograd and FFT remain
quite far from the communication bound, and that FFT and Winograd have
comparable performances, which is validated by the experimental results of
(Zlateski et al., 2019), while im2col performs orders of magnitude better.

##  5\. Performance Results

To show real-world applicability of this tiling, we benchmark our results on a
GEMMINI (Genc et al., 2021) machine learning accelerator running on Firesim
(Karandikar et al., 2018), a cycle-accurate hardware simulator.

GEMMINI’s memory architecture consists of two separate memory buffers: a
_scratchpad_ , which holds the input and the filter, and an _accumulator_
buffer, which holds the output at a higher precision (to prevent floating-
point rounding issues) and performs additions to it. At each tile, the input
and the filter are reloaded from off-chip memory, but the partially summed
output is held in the accumulator until it is fully summed (the loop ordering
is fixed to ensure that the innermost loop axes in the outer loops correspond
to reduction axes), at which point it is rounded and written off-chip in low
precision.

We use the default GEMMINI chip configuration, in which, the scratchpad is
256KiB, holding 8-bit words, while the accumulator is 64KiB and holds 32-bit
words. However, memory accesses are interleaved with computation using
_double-buffering_ , in which only half of the scratchpad and the accumulator
are accessible to the processor at any one time (with the other half pulling
in data from main memory). As a result, for tiling calculations, our memory
sizes are halved: the scratchpad can hold 128K words, while the accumulator
can hold 8K words.

As a result, we modify the optimization problem (6) to account for buffer
sharing between the input and the filter and to enforce integral tile sizes.
Although this introduces nonlinearity (and an integrality constraint), the
built-in numerical optimization routine NMaximize on Mathematica is still able
to find a tile in around 400 iterations, or about five seconds on our test
laptop.

We compare the performance of the five standard ResNet convolution sizes (He
et al., 2016) evaluated on GEMMINI using both our tiling and the vendor-
supplied tiling system included with GEMMINI. In the vendor implementation,
each ResNet convolution size takes roughly the same number of cycles, roughly
$500$M for batch size $1000$.

We measure both the estimated communication complexity (the number of
scratchpad and accumulator rows allocated by chip’s memory controller per
tile, multiplied by the total number of operations divided by the size of a
tile) and the counted number of clock cycles taken by each computation.

Figure 4. Experimentally measured Resnet50 layer performance (both total clock
cycles and communication) on GEMMINI accelerator. Our optimization-generated
tiling consistently uses less communication than the vendor-supplied tiling,
which leads to performance increases for layers where vendor tiling has poor
scratchpad utilization (convs 1 through 3).

As shown in Figure 4, our system consistently uses between $45\%$ and $85\%$
as much estimated communication compared to the vendor tiling on all ResNet
layers; this can be used as a proxy for energy consumption, which is dominated
by communication costs ((Yang et al., 2020) attributes over 80% of energy
costs to communication). Furthermore, for convs 1, 2, and 3 (together
comprising roughly half of the workload of a standard ResNet50 instance) where
the vendor tiling was unable to take full advantage of the buffer (indicated
by low scratchpad utilization per-tile), our tiling reduces clock cycle count
(i.e. runtime) by $2.5\times$ for conv1 and $13\%$ for conv2 and conv3.
However, for layers 4 and 5, where the vendor tiling already achieves
scratchpad utilizations of $99\%$ and $93\%$ respectively, there is little
room for improvement; in these cases, our tiling, which does not take into
account non-memory related, hardware-specific factors such as optimal
microkernel size and memory coalescing, performs worse with respect to clock
cycles. In such cases, additional constraints may be added to encode these
factors, as in (Huang et al., 2021). For instance, for conv5, simply adding a
single constraint forbidding the $7\times 7$ image from being tiled (as an
entire row will fit in a line of scratchpad) reduces cycles count from $124\%$
to $104\%$ of the vendor figure.

##  6\. Conclusion

In this work, we have reduced the gap between theoretical communication lower
bounds and practical implementations for convolution layers of CNNs. We
addressed both a single processor memory model with one cache layer, and a
parallel processor distributed memory model. The lower bounds presented in
Theorems 2.1, 2.2, and 2.3 contain constants and allow for the relative
precisions of the data to vary. The single processor lower bound is
asymptotically optimal. In Sections 3.2 and 4.2 we analyzed the attainability
of these lower bounds across popular convolution algorithms such as Im2Col,
and found in some cases that a blocking strategy inspired by (Christ et al.,
2013) communicates less. We included results comparing the performance of our
blocking strategy with Im2Col, FFT, and Winograd in Section 5.

While our lower bounds are nearly attained, there is more work to be done to
close the gap. Future directions of work include determining whether further
optimization techniques can tighten the constants in the bounds, and
investigating other algorithms to attempt to meet the existing lower bounds.
It is also possible that pebbling methods could be used to remove lower order
terms from our lower bounds. Finally, it is of interest to extend our results
to other memory models, such as single processors with more levels of cache or
parallel processors with shared memory.

###### Acknowledgements.

This research was supported by the University of California, Berkeley College
of Letters and Sciences Summer Undergraduate Research Fellowship Math Team
Grant. We would like to thank Victoria Cheng and the rest of the SURF staff
for their valuable support and the donors who made this grant possible. We
also thank Hogli Zhao, Jon Hillery, Rahul Jain, and Evangelos Georganas for
their insight. Hasan Genc was invaluable for support regarding GEMMINI.

## References

  * (1)
  * Ballard et al. (2014) Gray Ballard, Erin Carson, James Demmel, Mark Hoemmen, Nicholas Knight, and Oded Schwartz. 2014\.  Communication lower bounds and optimal algorithms for numerical linear algebra.  _Acta Numerica_ 23 (2014), 1–155.
  * Christ et al. (2013) Michael Christ, James Demmel, Nicholas Knight, Thomas Scanlon, and Katherine Yelick. 2013.  Communication lower bounds and optimal algorithms for programs that reference arrays – Part 1.  arXiv:1308.0068 [math.CA]
  * Christ et al. (2015) Michael Christ, James Demmel, Nicholas Knight, Thomas Scanlon, and Katherine Yelick. 2015.  On Holder-Brascamp-Lieb inequalities for torsion-free discrete Abelian groups.  arXiv:1510.04190 [math.CA]
  * Council (2011) National Research Council. 2011\.  _The Future of Computing Performance: Game Over or Next Level?_ The National Academies Press, Washington, DC.
  * Demmel et al. (2013) James Demmel, David Eliahu, Armando Fox, Shoaib Kamil, Benjamin Lipshitz, Oded Schwartz, and Omer Spillinger. 2013.  Communication-Optimal Parallel Recursive Rectangular Matrix Multiplication. In _2013 IEEE 27th International Symposium on Parallel and Distributed Processing_. 261–272.
  * Demmel and Rusciano (2016) James Demmel and Alex Rusciano. 2016.  Parallelepipeds obtaining HBL lower bounds.  arXiv:1611.05944 [cs.DS]
  * Elango (2016) Venmugil Elango. 2016\.  Techniques for Characterizing the Data Movement Complexity of Computations.
  * Genc et al. (2021) Hasan Genc, Seah Kim, Alon Amid, Ameer Haj-Ali, Vighnesh Iyer, Pranav Prakash, Jerry Zhao, Daniel Grubb, Harrison Liew, Howard Mao, Albert Ou, Colin Schmidt, Samuel Steffl, John Wright, Ion Stoica, Jonathan Ragan-Kelley, Krste Asanovic, Borivoje Nikolic, and Yakun Sophia Shao. 2021.  Gemmini: Enabling Systematic Deep-Learning Architecture Evaluation via Full-Stack Integration. In _Proceedings of the 58th Annual Design Automation Conference (DAC)_.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016\.  Deep residual learning for image recognition. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 770–778.
  * Huang et al. (2021) Qijing Huang, Aravind Kalaiah, Minwoo Kang, James Demmel, Grace Dinh, John Wawrzynek, Thomas Norell, and Yakun Sophia Shao. 2021\.  CoSA: Scheduling by Constrained Optimization for Spatial Accelerators. In _2021 ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA)_. IEEE, 554–566.
  * Karandikar et al. (2018) Sagar Karandikar, Howard Mao, Donggyu Kim, David Biancolin, Alon Amid, Dayeol Lee, Nathan Pemberton, Emmanuel Amaro, Colin Schmidt, Aditya Chopra, Qijing Huang, Kyle Kovacs, Borivoje Nikolic, Randy Katz, Jonathan Bachrach, and Krste Asanović. 2018.  FireSim: FPGA-accelerated Cycle-exact Scale-out System Simulation in the Public Cloud. In _Proceedings of the 45th Annual International Symposium on Computer Architecture_ (Los Angeles, California) _(ISCA ’18)_. IEEE Press, Piscataway, NJ, USA, 29–42.
  * Kwasniewski et al. (2019) Grzegorz Kwasniewski, Marko Kabić, Maciej Besta, Joost VandeVondele, Raffaele Solcà, and Torsten Hoefler. 2019.  Red-Blue Pebbling Revisited: Near Optimal Parallel Matrix-Matrix Multiplication. In _Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis_ (Denver, Colorado) _(SC ’19)_. Association for Computing Machinery, New York, NY, USA, Article 24, 22 pages.
  * Meng and Brothers (2019) Lingchuan Meng and John Brothers. 2019.  Efficient Winograd Convolution via Integer Arithmetic.  arXiv:1901.01965 [cs.NE]
  * San Juan et al. (2020) Pablo San Juan, Adrián Castelló, Manuel F. Dolz, Pedro Alonso-Jordá, and Enrique S. Quintana-Ortí. 2020\.  High Performance and Portable Convolution Operators for Multicore Processors. In _2020 IEEE 32nd International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD)_. 91–98.
  * Valdimarsson (2010) Stefán Ingi Valdimarsson. 2010\.  The Brascamp–Lieb Polyhedron.  _Canadian Journal of Mathematics_ 62, 4 (2010), 870–888.
  * Yang et al. (2020) Xuan Yang, Mingyu Gao, Qiaoyi Liu, Jeff Setter, Jing Pu, Ankita Nayak, Steven Bell, Kaidi Cao, Heonjae Ha, Priyanka Raina, Christos Kozyrakis, and Mark Horowitz. 2020\.  Interstellar: Using Halide’s Scheduling Language to Analyze DNN Accelerators. In _Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems_ (Lausanne, Switzerland) _(ASPLOS ’20)_. Association for Computing Machinery, New York, NY, USA, 369–383.
  * Zlateski et al. (2019) Aleksandar Zlateski, Zhen Jia, Kai Li, and Fredo Durand. 2019\.  The Anatomy of Efficient FFT and Winograd Convolutions on Modern CPUs _(ICS ’19)_. Association for Computing Machinery, New York, NY, USA, 414–424.