# Fast matrix multiplication for binary and ternary CNNs on ARM CPU

Anton Trusov123, Elena Limonova23, Dmitry Nikolaev34 and Vladimir V.
Arlazarov23 Email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>1 Moscow Institute of Physics and
Technology, Dolgoprudny, Russia  2 Federal Research Center “Computer Science
and Control” of Russian Academy of Sciences, Moscow, Russia  3 Smart Engines
Service LLC, Moscow, Russia  4 Institute for Information Transmission
Problems, RAS, Moscow, Russia

###### Abstract

Low-bit quantized neural networks (QNNs) are of great interest in practical
applications because they significantly reduce the consumption of both memory
and computational resources. Binary neural networks (BNNs) are memory and
computationally efficient as they require only one bit per weight and
activation and can be computed using Boolean logic and bit count operations.
QNNs with ternary weights and activations (TNNs) and binary weights and
ternary activations (TBNs) aim to improve recognition quality compared to BNNs
while preserving low bit-width. However, their efficient implementation is
usually considered on ASICs and FPGAs, limiting their applicability in real-
life tasks. At the same time, one of the areas where efficient recognition is
most in demand is recognition on mobile devices using their CPUs. However,
there are no known fast implementations of TBNs and TNN, only the daBNN
library for BNNs inference. In this paper, we propose novel fast algorithms of
ternary, ternary-binary, and binary matrix multiplication for mobile devices
with ARM architecture. In our algorithms, ternary weights are represented
using 2-bit encoding and binary – using one bit. It allows us to replace
matrix multiplication with Boolean logic operations that can be computed on
128-bits simultaneously, using ARM NEON SIMD extension. The matrix
multiplication results are accumulated in 16-bit integer registers. We also
use special reordering of values in left and right matrices. All that allows
us to efficiently compute a matrix product while minimizing the number of
loads and stores compared to the algorithm from daBNN. Our algorithms can be
used to implement inference of convolutional and fully connected layers of
TNNs, TBNs, and BNNs. We evaluate them experimentally on ARM Cortex-A73 CPU
and compare their inference speed to efficient implementations of full-
precision, 8-bit, and 4-bit quantized matrix multiplications. Our experiment
shows our implementations of ternary and ternary-binary matrix multiplications
to have almost the same inference time, and they are 3.6 times faster than
full-precision, 2.5 times faster than 8-bit quantized, and 1.4 times faster
than 4-bit quantized matrix multiplication but 2.9 slower than binary matrix
multiplication.

##  I Introduction

Convolutional neural networks (CNNs) are the primary tool for solving various
computer vision problems: pattern recognition [1], detection of different
objects [2, 3], semantic segmentation [4] and many others. Although new
transformer-based [5, 6] or deep MLP-based [7, 8] neural networks sometimes
outperform CNNs on challenging datasets, they are usually harder to train,
have more parameters and require more computational resources for inference
[8, 9]. That is why CNNs remain irreplaceable in practical applications. The
high performance of CNNs is essential for on-device intelligence systems,
which allows for solving computer vision problems directly on a mobile device
without the transmission of information to an external server and thus solve
them faster, as well as in a more energy-efficient and secure way [10].

The most computationally-challenging operation in a CNN is a discrete
convolution of a feature map with a convolution kernel. A widely used approach
for its efficient computation is a general matrix multiplication-based (GeMM-
based) approach. Using this approach, the feature map and the convolution
kernel are unrolled to matrices and then multiplied with the help of optimized
BLAS libraries [11]. The most common method for transforming a feature map to
a matrix is the im2col method. Unfortunately, it suffers from significant
memory overhead, which is why several more resource-efficient methods were
proposed [12, 13].

It is worth mentioning that efficient algorithms for discrete convolution are
not limited to GeMM-based. For example, FPGAs, ASICs, and sometimes GPUs can
benefit from the reduction of the number of multiplications using Winograd’s
minimal filtering algorithms [14] but also can use more straightforward
algorithms [15]. At the same time, on CPUs it is critical to optimize data
flow in memory, so that the number of cache misses is low and data-parallel
execution with Single Instruction Multiple Data (SIMD) instructions is
possible. That can be achieved with the help of just-in-time code generation
of direct convolution for specific kernel sizes [16]. However, all mentioned
algorithms are specific to devices and/or convolution parameters, so GeMM-
based algorithms are still widely used in practice.

One of the most efficient ways to speedup and reduce the memory footprint of a
CNN is to replace floating-point values of weights and activations with
integers. This process is called quantization, and a neural network with
integer weights is referred to as quantized neural network (QNN) [10]. Widely
used 8-bit quantization allows for a 4-times reduction of network size and
significant speedup on mobile CPUs while maintaining the quality close to full
precision models [17]. 4-bit QNNs demonstrate a noticeable drop in recognition
quality on challenging tasks [18, 19]; still, 4-bit quantization can be used
to accelerate CPU inference of small CNNs significantly [20]. The most memory-
efficient quantization is binarization: in binary QNNs (BNNs), weights and
activations only take the values of $1$ or $-1$ and require a single bit for
storage. In BNNs, convolutions and matrix multiplications can be computed
using only XOR/XNOR and bit count operations [21]. That makes such networks
exceptionally computationally efficient, especially on FPGAs and ASICs. There
is also a CPU implementation of BNNs available in daBNN library [22].

Although training techniques for binary networks have improved in the past few
years [23, 24], they still show a significant gap in accuracy in comparison
with full-precision ones. Ternary neural networks (TNNs) allow weights and
activations take the values $1$, $0$ or $-1$ [25]. They show higher quality
than BNNs and can be efficiently implemented on ASICS and FPGAs [26, 27].
Ternary-binary networks (TBNs), which have ternary activations and binary
weights, take medium place between TNNs and BNNs in terms of computational
complexity and show almost the same recognition quality as TNNs [28]. However,
no computationally-efficient CPU-oriented algorithms of ternary and ternary-
binary convolution and/or matrix multiplications were previously published to
the best of our knowledge.

In this paper, we propose novel algorithms for high-performance matrix
multiplication of binary, ternary, and ternary-binary matrices for CPUs with
ARMv8 architecture. They can be used in convolutional and fully-connected
(linear) layers of BNNs, TNNs, and TBNs to obtain computationally efficient
inference of such networks on mobile devices. Our algorithms use binary logic
operations instead of multiplications and accumulate their products in 16-bit
integer values. It allows us to take full advantage of data-parallel computing
with the help of SIMD extension NEON of ARM CPUs.

In the experimental section of our work, we compare the performance of the
proposed algorithms to computationally-efficient algorithms of matrix
multiplication for different data types: 32-bit floating-point, 8-bit integer
from Google’s gemmlowp library [29], 4-bit presented in [20], and binary from
daBNN library [22].

##  II Efficient matrix multiplication on CPUs

###  II-A High-performance GeMM

In this section, we discuss commonly used high-performance matrix
multiplication computation methods. We use $A$ to denote left matrix of size
$m\times k$, $B$ to denote right matrix of size $k\times n$ and $C=AB$ to
denote their product. We refer to $m$, $n$ and $k$ as “height”, “width” and
“depth” of matrix multiplication respectively. $X_{ij}$ denotes element of $X$
in row $i$ and column $j$.

Most modern machine-learning and linear algebra libraries implement matrix
multiplication in the following way: they split the matrix $A$ along rows, the
matrix $B$ along columns, and possibly both along the depth, then they use a
high-performance function called “inner-kernel” or “microkernel” to compute
small block of matrix $C$. Actually, there are several ways in which matrices
$A$, $B$, and $C$ could be split as described in detail in [30]. One of them
is presented as Algorithm 1. Here matrix $A$ is first split by blocks of
$m_{blk}$ rows, values in those blocks are reordered by function PackNRowsA so
that small blocks of its rows can be easily processed by microkernel, the
result is stored in $A_{buf}$. Likewise matrix $B$ is split by blocks of
$n_{blk}$ columns, reordered by PackNColsB and stored into $B_{buf}$. After
that algorithm extracts smaller blocks: $m_{mk}$ rows and $k_{eff}\leq
k_{blk}$ columns from $A_{buf}$, and $n_{mk}$ columns and $k_{eff}$ rows from
$B_{buf}$. Those blocks are multiplied by the microkernel. Values of $m_{mk}$
and $n_{mk}$ as well as the storage order of values in buffers $A_{buf}$ and
$B_{buf}$ depend on the microkernel implementation. Values of $k_{blk}$,
$m_{blk}$ and $n_{blk}$ are independent of the microkernel. They are chosen so
that reordered buffers fit into the L2 CPU cache and smaller buffers that
microkernel processes fit into the L1 cache. This way, the number of cache
misses is minimized, so multiplication computes faster.

Input: $m$, $n$, $k$ – height, width, depth;
$A$ – left matrix $m\times k$;
$B$ – right matrix $k\times n$;

Output: $C$ – matrix $m\times n$, $C=AB$

for  _$y\leftarrow 0$ ; $y<m$; $y\leftarrow y+m_{blk}$_ do

$m_{eff}\leftarrow\min(m_{blk},m-y)$

$A_{buf}$ $[0:m_{eff}-1]$ $\leftarrow$ PackNRowsA(_$A$ , y, $m_{eff}$_)

for  _$x\leftarrow 0$ ; $x<n$; $x\leftarrow x+n_{blk}$_ do

$n_{eff}\leftarrow\min(n_{blk},n-x)$

$B_{buf}$ $[0:n_{eff}-1]$ $\leftarrow$ PackNColsB(_$B$ , x, $n_{eff}$_)

for  _$d\leftarrow 0$ ; $d<k$; $d\leftarrow d+k_{blk}$_ do

$k_{eff}\leftarrow\min(k_{blk},k-d)$

for  _$c\leftarrow 0$ ; $c<n_{eff}$; $c\leftarrow c+n_{mk}$_ do

for  _$r\leftarrow 0$ ; $r<m_{eff}$; $r\leftarrow r+m_{mk}$_ do

$j\leftarrow y+c;~{}i\leftarrow x+r$

_ _$C[j:j+m_{mk}-1][i:i+n_{mk}-1]$ $\leftarrow$ microkernel(__

__ $A_{buf}$ $[r:r+m_{mk}-1]$,

 __ $B_{buf}$ $[c:c+n_{mk}-1]$, $k_{eff}$)

end for

end for

end for

end for

end for

Algorithm 1 General high-level GeMM algorithm

If we consider neural network inference, the matrix $B$ is a weights matrix.
It is usually small enough to fit into the L2 cache. Also, it does not change
during inference of the neural network, so one can reorder it and store it in
the PackedB buffer beforehand. Taking it into consideration, we use a little
simpler algorithm to compute convolutions (Algorithm 2). In our version of the
algorithm, buffer $A_{buf}$ is noticeably smaller: it contains only $m_{mk}$
rows and $k_{eff}\leq k_{blk}$ columns from the matrix $A$. That can help the
inference on mobile devices where memory is limited.

Input: $m$, $n$, $k$ – height, width, depth;
$A$ – left matrix $m\times k$;
PackedB – pre-reordered right matrix $k\times n$;

Output: $C$ – matrix $m\times n$, $C=AB$

for  _$d\leftarrow 0$ ; $d<k$; $d\leftarrow d+k_{blk}$_ do

$k_{eff}\leftarrow\min(k_{blk},k-d)$

for  _$r\leftarrow 0$ ; $r<m$; $r\leftarrow r+m_{mk}$_ do

$A_{buf}$ $[0:m_{eff}-1]$ $\leftarrow$ PackNRowsA(_A, r, $m_{mk}$_)

for  _$c\leftarrow 0$ ; $c<n$; $c\leftarrow c+n_{mk}$_ do

_ _$C[r:r+m_{mk}-1][c:c+n_{mk}-1]$ $\leftarrow$ microkernel(_$A_{buf}$ ,_

 __ PackedB $[c:c+n_{mk}-1]$, $k_{eff}$)

end for

end for

end for

Algorithm 2 Our high-level GeMM algorithm

In Algorithms 1 and 2 height and width ($n$ and $m$) are assumed to be
multiples of microkernel height and width ($m_{mk}$ and $n_{mk}$)
respectively. In practice, several microkernels of different shapes are
implemented to compute multiplications on matrices of arbitrary shapes. Most
computations are performed with a bigger microkernel, and smaller microkernels
compute the remains.

The values $m_{mk}$ and $n_{mk}$ should be chosen as high as possible to
minimize the number of loads and stores from memory but low enough so that the
result of matrix multiplication can be stored in CPU registers. This way, in
the inner loop, the microkernel loads values from Ablock and Bblock,
multiplies them, and accumulates results in registers. After whole
multiplication is computed, the results are offloaded to memory. So, the shape
of the microkernel depends on the number of registers available on specific
CPU architecture and bit-width of values used in computation (the smaller it
is, the more values can be stored in a single register). For example, AArch64
(ARMv8) CPUs have 32 128-bit SIMD registers.

###  II-B Integer GeMM

Now let us point out key differences between floating-point matrix
multiplication in CNNs and integer matrix multiplication in QNNs. The first is
that CNNs just multiply matrices. On ARM CPUs multiplication microkernel can
use FMLA instruction that for 3 SIMD registers $a$, $b$ and $c$ (each holding
four 32-bit floating-point values) computes $\texttt{FMLA}(a,b,c)=a+bc$
element-wise.

In QNNs, integer computations are used to approximate floating-point
computations of CNNs. That can be done through linear quantization – the
procedure in which all floating-point values of a neural network layer weights
or activation are approximated with integers according to:

$\hat{x}=\max\Bigg{(}\min\Big{(}\left\lfloor\frac{x}{s}-z\right\rfloor,Q\Big{)},0\Bigg{)},$
(1)

where $Q$ is a maximal quantized value, $s$ is a floating-point value called
“scale” and $0\leq z<Q$ is an integer value called “zero-point” ($\hat{0}=z$),
$\left\lfloor y\right\rfloor$ denotes integer part of $y$. For $n$-bit
quantization $Q=2^{n}-1$. Strategies to obtain scale and zero-point can vary
[29, 19, 18].

Let us consider $\hat{A}$ to be a quantized approximation of matrix $A$ with
scale $s_{A}$ and zero-point $z_{A}$. We use similar notation for $\hat{B}$,
$B$, $s_{B}$, and $z_{B}$. Then matrix multiplication can be approximated as:

$\begin{split}C_{ij}&=\sum_{t=1}^{k}A_{it}B_{tj}\simeq\sum_{t=1}^{k}s_{A}(\hat{A}_{it}-z_{A})s_{B}({\hat{B}_{tj}}-z_{B})=\\\
&=s_{A}s_{B}\sum_{t=1}^{k}\bigg{(}(\hat{A}_{it}-z_{A})({\hat{B}_{tj}}-z_{B})\bigg{)}=s_{A}s_{B}\tilde{C}_{ij},\end{split}$
(2)

where $\tilde{C}_{ij}$ can be computed using integer-only arithmetic. In
gemmlowp [29] and [20] it is done with the following transformation:

$\begin{split}\tilde{C}_{ij}&=\sum_{t=1}^{k}\bigg{(}(\hat{A}_{it}-z_{A})(\hat{B}_{tj}-z_{B})\bigg{)}=\sum_{t=1}^{k}(\hat{A}_{it}\hat{B}_{tj})-\\\
&-z_{B}\sum_{t=1}^{k}\hat{A}_{it}-z_{A}\sum_{t=1}^{k}\hat{B}_{tj}+kz_{A}z_{B}.\end{split}$
(3)

The first term of (3) presents matrix multiplication of quantized matrices:
8-bit with 32-bit product in case of gemmlowp and 4-bit with 16-bit product in
case of [20]. The second and third terms do not depend on $j$ and $i$
respectively, so they are easier to compute: in terms of algorithmic
complexity, the first term requires $O(mnk)$, the second – $O(mk)$, the third
– $O(nk)$, and the fourth – $O(1)$ operations.

It is worth mentioning that integer accumulators can overflow, which limits
the depth of matrix multiplication. If matrices $A$ and $B$ hold $p$-bit
values, and their product is accumulated in $q$-bit accumulators, then maximum
depth that guarantees the absence of overflow is:

$k_{\max}=\left\lfloor\frac{2^{q}-1}{(2^{p}-1)^{2}}\right\rfloor.$ (4)

In GeMM-based convolution it limits the number of channels in the input
feature map [20]. Let us consider convolution with $H_{k}\times W_{k}$ kernel.
Then the maximum number of channels in the input feature map, for which the
absence of overflow in guaranteed is:

$C_{in\\_\max}=\left\lfloor\frac{k_{\max}}{H_{k}W_{k}}\right\rfloor.$ (5)

##  III Low-bit matrix multiplication

In this section we present our algorithms for matrix multiplication of binary,
ternary and ternary-binary matrices.

We consider matrix multiplication $A\times B=C$ for three cases:

BNN

$A$ and $B$ are binary ($A_{ij}\in\\{-1,1\\}$, $B_{ij}\in\\{-1,1\\}$),

TNN

$A$ and $B$ are ternary ($A_{ij}\in\\{-1,0,1\\}$, $B_{ij}\in\\{-1,0,1\\}$),

TBN

$A$ is ternary and $B$ is binary ($A_{ij}\in\\{-1,0,1\\}$,
$B_{ij}\in\\{-1,1\\}$).

For all the cases we assume that $C$ holds integer values stored in signed
16-bit representation.

###  III-A Values, encoding and multiplication

In the considered algorithms values of matrix elements of $A$ and $B$ are
either binary or ternary. For binary values we use single-bit encoding $x\to
x^{b}:1\to 0,-1\to 1$. This way matrix multiplication $z=xy$ can be computed
using our representation as $z^{b}=x^{b}\oplus y^{b}$ (where $\oplus$ is an
addition modulo 2 or XOR operation). Using this representation we can compute
matrix multiplication using only XOR, bit-count and addition operation in the
inner loop:

$c=\sum_{t=1}^{k}a_{t}b_{t}=\sum_{t=1}^{k}(1-2a^{b}_{t}\oplus
b^{b}_{t})=k-2\sum_{t=1}^{k}(a^{b}_{t}\oplus b^{b}_{t}).$ (6)

For ternary values we use 2-bit encoding $x\to(x^{+},x^{-})$: $1\to(1,0)$,
$0\to(0,0)$, $-1\to(0,1)$, and code $(1,1)$ is invalid. Using those operations
we can compute ternary multiplication $z=xy$ as

$(z^{+},z^{-})=((x^{+}\land y^{+})\lor(x^{-}\land y^{-}),(x^{+}\land
y^{-})\lor(x^{-}\land y^{+}))$

and ternary-binary multiplication as

$(z^{+},z^{-})=((x^{+}\lor
y^{b})\land(x^{-}\lor\overline{y^{b}}),(x^{+}\lor\overline{y^{b}})\land(x^{-}\lor
y^{b})),$

where $\land$, $\lor$, and $\overline{*}$ denote logical AND, OR, and NOT.
Truth tables for ternary and ternary-binary multiplication illustrating these
equations are presented in Table I.

TABLE I: Ternary multiplication $z=xy$ and Ternary-binary multiplication $u=xy$ $x$ |  $y$ |  $z$ |  $x^{+}$ |  $x^{-}$ |  $y^{+}$ |  $y^{-}$ |  $y^{b}$ |  $z^{+}$ |  $z^{-}$ |  $u^{+}$ |  $u^{-}$
---|---|---|---|---|---|---|---|---|---|---|---
1 |  1 |  1 |  1 |  0 |  1 |  0 |  0 |  1 |  0 |  1 |  0
1 |  0 |  0 |  1 |  0 |  0 |  0 |  – |  0 |  0 | —
1 |  -1 |  -1 |  1 |  0 |  0 |  1 |  1 |  0 |  1 |  0 |  1
0 |  1 |  0 |  0 |  0 |  1 |  0 |  0 |  0 |  0 |  0 |  0
0 |  0 |  0 |  0 |  0 |  0 |  0 |  – |  0 |  0 | —
0 |  -1 |  0 |  0 |  0 |  0 |  1 |  1 |  0 |  0 |  0 |  0
-1 |  1 |  -1 |  0 |  1 |  1 |  0 |  0 |  0 |  1 |  0 |  1
-1 |  0 |  0 |  0 |  1 |  0 |  0 |  – |  0 |  0 | —
-1 |  -1 |  1 |  0 |  1 |  0 |  1 |  1 |  1 |  0 |  1 |  0

Assuming that $a_{t}b_{t}=(c^{+},c^{-})$ is a ternary or ternary-binary
multiplication of a couple of elements as shown above, we can compute dot
product (and matrix multiplication) as:

$c=\sum_{t=1}^{k}a_{t}b_{t}=\sum_{t=1}^{k}((a_{t},b_{t})^{+}-(a_{t},b_{t})^{-}).$
(7)

###  III-B Binary microkernel

Now that we have encoding and operation definitions for matrix multiplication
based on binary-logic operations available in the ARM instruction set, we move
to matrix multiplication microkernels. As we stated in Section II-A
microkernel multiplies $m_{mk}$ rows stored in buffer Ablock by $n_{mk}$ cols
stored in buffer Bblock. To describe a multiplication microkernel we need to
specify its shape $m_{mk}\times n_{mk}$, storage order in buffers Ablock and
Bblock and operations used in the computation. All the microkernels we propose
in this work have $16\times 8$ shape and use 16 128-bit SIMD registers
($c00,...c07,c10,...c17$) to hold the corresponding block of matrix $C$ as
16-bit integers. However, storage order and SIMD instructions are different
for all multiplications (BNN, TNN and TBN). Let us start with binary matrix
multiplication.

To pack values into Ablock we

  1. 1.

take 16 rows of $A$ matrix encoded as binary values and pack them into 8-bit
values (each holding 8 consecutive bits from the corresponding row);

  2. 2.

store this 8-bit matrix in column-major order (first go 8 bits from the
$1^{st}$ row, then 8 bits from the $2^{nd}$ and so on until the $16^{th}$,
after that bits $9...16$ from the $1^{s}t$ row, then bits $9...16$ from the
$2^{nd}$ and so on).

To pack values into Bblock we

  1. 1.

take 8 columns of $B$ matrix encoded as binary values and pack them into 8-bit
values (each holding 8 consecutive bits from the corresponding column);

  2. 2.

store this 8-bit matrix in row-major order (first 8 bits from the $1^{st}$
column, then 8 bits from the $2^{nd}$ and so on until the $8^{th}$, after that
bits $9...16$ from the $1^{st}$ column, than bits $9...16$ from the $2^{nd}$
and so on).

In one iteration of the loop over depth dimension in the microkernel (shown in
Fig. 1) we

  1. 1.

load a column of 8-bit values from Ablock into two 128-bit registers $a$;

  2. 2.

load a row 8-bit values from Bblock into one 64-bit register $b$;

  3. 3.

for each 8-bit element of $b$ compute XOR (EOR instruction in ARM) with
register $a$, count number of 1-bites in the “product” with CNT instruction
and accumulate the result with SADDW instruction.

Figure 1: Binary GeMM microkernel.

###  III-C Ternary microkernel

As described in Section III-A we use 2-bit representation for ternary values.
To pack them into Ablock we

  1. 1.

consider that $A^{+}$ and $A^{-}$ are stored as two separate matrices;

  2. 2.

take 8 rows of $A^{+}$ matrix and pack them into 8-bit values (each holding 8
consecutive bits from the corresponding row);

  3. 3.

do the same for $A^{-}$;

  4. 4.

store the first 8 8-bit elements from the first column of $A^{+}$ block, then
store the first 8 8-bit elements from the first column of $A-$ block, then the
last 8 elements from the first columns from $A^{+}$ and $A^{-}$ blocks, then
repeat this for the $2^{nd}$, the $3^{d}$ and all the remaining columns.

To pack values into Bblock we

  1. 1.

consider tat $B^{+}$ and $B^{-}$ are stored as two separate matrices;

  2. 2.

take 8 columns of $B^{+}$ matrix and pack them into 8-bit values (each holding
8 consecutive bits from the corresponding column);

  3. 3.

do the same for $B^{-}$;

  4. 4.

for the first row: store the $1^{s}t$ element from $B^{+}$ block, then store
the $1^{s}t$ element from $B^{-}$ block, then the $2^{nd}$ elements and so on;
repeat that procedure for all rows.

On each iteration ternary microkernel loads a column from the Ablock as two
128-bit registers ($a0$ and $a1$) and a row from Bblock as a single 128-bit
register $b$. For each pair of elements in $b$ it computes the product with
registers $a0$ and $a1$ using AND and OR operations, then applies bit-count
CNT to compute sums of “+” and “-” bits of the product, computes their
difference with SSUBL and accumulates the result in the corresponding register
with ADD. Fig 2 demonstrates a half of this microkernel – 8 rows from Ablock.

Figure 2: Ternary GeMM microkernel.

###  III-D Ternary-binary microkernel

For ternary-binary multiplication we store values ternary in Ablock in the
same way as for ternary multiplication and binary values in Bblock in the same
way as for binary multiplication.

This way multiplication this microkernel is almost the same as ternary with
only two differences:

  * •

Bblock contains 8 column of 8-bit values, so we use 64-bit register $b$ to
load them;

  * •

as we show in Section III-A, different instructions (OR, AND and ORN – OR with
negation of the second operand) are used to compute the product.

Figure 3: Ternary-binary GeMM microkernel.

##  IV Matrix multiplication evaluation

In this section, we demonstrate the efficiency of the proposed ternary (TNN),
ternary-binary (TBN), and binary (BNN) matrix multiplication on ARM Aarch64
CPUs and compare them to known efficient algorithms: binary from daBNN library
[22] (daBNN), 8-bit from gemmlowp library [29] (U8), 4-bit from [20] with a
microkernel upscaled to $24\times 8$ size (U4, the original size was $24\times
4$ for ARMv7 architecture), and our implementation of floating-point 32-bit
baseline which uses the same register layout as gemmlowp, but computes
operations in floating-point (F32).

###  IV-A Theoretical evaluation

In Table II we show a comparison of the microkernels for multiplication
algorithms under consideration. We compare them by a number of columns in
Ablock ($m$), a number of rows in Bblock ($n$), a step over depth per
iteration ($k$), a number of computational instructions per iteration (COM –
FMLA for F32 algorithm, UMLAL/UMLAL2 for U8, etc.), a number of loads of SIMD
register per microkernel instruction (LD), a number of other SIMD instructions
per iteration (MOV – MOV, DUP, INS, etc.), and by a number of SIMD
instructions per microkernel element
$\text{{INS}}=(\text{COM}+\text{LD}+\text{MOV})/(nmk)$. We also estimate a
maximum depth of multiplication ($k_{\max}$) as (4) for U8 and U4 algorithms.
In a ternary and binary matrix multiplication $xy=z,|z|\leq 1$, so $k_{\max}$
equals to the maximum possible value that a register can hold. TNN, TBN, and
BNN use 16-bit signed registers, and $k_{\max}=2^{15}-1$. daBNN uses 32-bit
floating point registers (with 23-bit significand field) to store Cblock, so
$k_{\max}=2^{23}-1$.

TABLE II: Comparison of the multiplication microkernels Algo | $m\times n\times k$ | COM | LD | MOV | INS | $k_{\max}$
---|---|---|---|---|---|---
F32 | $12\times 8\times 1$ | 24 | 5 | 0 | 0.302 | —
U8 | $12\times 8\times 2$ | 48 | 5 | 5 | 0.302 | 66051
U4 | $24\times 8\times 2$ | 48 | 5 | 16 | 0.180 | 291
TNN | $16\times 8\times 8$ | 96 | 3 | 64 | 0.159 | 32767
TBN | $16\times 8\times 8$ | 96 | 3 | 56 | 0.151 | 32767
BNN | $16\times 8\times 8$ | 32 | 2 | 8 | 0.041 | 32767
daBNN | $8\times 6\times 128$ | 156 | 12 | 36 | 0.033 | 8388607

A multiplication algorithm reaches maximal efficiency when multiplication
parameters height, width, and depth are multiples of corresponding microkernel
parameters ($m,n,k$). It limits the applicability of the multiplication
algorithm in CNNs. If a convolution is computed using im2col transformation,
the height is the number of pixels in the input feature map; the width is the
number of filters (from only a few in upper layers of small CNNs to hundreds
and thousands in lower layers of big CNNs). $k_{\max}$ limits the number of
input channels in the feature maps (5). Taking all the limitations into
account, we can see that U4 algorithm is only suitable for small CNNs, daDNN,
on the other hand, will show better results in large networks, and all the
rest (including three proposed algorithms) will work fine in small, medium and
large CNNs.

###  IV-B Experimental evaluation

Although the number of instructions (COM, LD, MOV, and INS in Table II) can
give us general ideas on which algorithm should have better computational
efficiency, in practice the efficiency also depends on cache misses (which in
turn depends on the order of loads and stores in memory), the ability of CPU
to use the instruction pipelining (that depends on the order in which
instructions are fetched). Furthermore, the overall efficiency of the matrix
multiplication is affected also by reordering operations that prepare matrix
blocks for microkernel and by post-processing in algorithms U8 and U4, which
is shown in (3). That is why we experimentally measure the efficiency of all
the algorithms under consideration.

We implemented matrix multiplication algorithms F32, U4, TNN, TBN, TNN
according to Algorithm 2. All the microkernels were written on ARMv8 assembly
to optimize the usage of SIMD registers. We ran time measurements for
different values of height ($H\in\\{72,120,240,360\\}$), width
($W\in\\{24,48,72,96\\}$) and depth ($D\in\\{128,256,384,512\\}$). Those
values are chosen to be multiples of the microkernel size for each algorithm,
so that they all can show the maximum efficiency. They also are representative
for matrix multiplications in small and medium CNNs, which can be used in
real-life tasks on mobile CPUs.

We ran our experiment on the ARM Cortex-A73 CPU, a part of Odroid-N2
development board with Linux. For each value of parameters, we took the median
of 5 measurements (to exclude random errors) and repeated the whole experiment
50 times, taking the average of the measurements to reach 0.8% empirical
relative error of running time. We summarize them in Table III. Each cell
compares algorithms $A$ and $B$ as
$\mathbf{E}_{\theta}(T_{B}(\theta)/T_{A}(\theta))$, where $T_{A}$ and $T_{B}$
denote execution times of corresponding on test $\theta$, $\mathbf{E}$ is
mathematical expectation.

TABLE III: Efficiency ratio of the multiplication algorithms B A | F32 | U8 | U4 | TNN | TBN | BNN | daBNN
---|---|---|---|---|---|---|---
F32 | 1.00 | 1.44 | 2.52 | 3.63 | 3.75 | 10.9 | 9.60
U8 | 0.69 | 1.00 | 1.75 | 2.51 | 2.60 | 7.52 | 6.63
U4 | 0.40 | 0.57 | 1.00 | 1.44 | 1.49 | 4.32 | 3.81
TNN | 0.28 | 0.40 | 0.70 | 1.00 | 1.03 | 2.99 | 2.64
TBN | 0.27 | 0.39 | 0.67 | 0.97 | 1.00 | 2.90 | 2.55
BNN | 0.093 | 0.13 | 0.23 | 0.34 | 0.35 | 1.00 | 0.88
daBNN | 0.11 | 0.15 | 0.27 | 0.39 | 0.40 | 1.15 | 1.00

According to Table III our TNN algorithm significantly outperforms matrix
multiplication for types with greater bit-width: it is 3.6 faster than F32,
2.5 times faster than U8 and 1.4 times faster than U4. TBN is only slightly
faster than TNN because of a simpler data flow in Bblock. BNN is almost 3
times faster than TNN (and 2.9 times faster than TBN. Moreover our
implementation of binary multiplication turns out to be 1.15 times faster than
that of daBNN library, due to a bigger microkernel and 16-bit representation
of the result.

Proposed algorithms for ternary, ternary-binary, and binary matrix
multiplication show significantly higher computational efficiency than
algorithms with greater bit-width. They can be used for the inference of low-
bit CNNs on mobile devices and do not pose strict constraints on the network
architecture (although to achieve maximal efficiency, numbers of channels in
feature maps and convolutional filters should be multiples of 8). It opens an
opportunity to investigate the trade-off between recognition quality (which
usually decreases along with the bit-width of QNN) and efficiency gain from
low-bit quantization of several layers or whole CNNs. Note that in the pursuit
of high computational efficiency, different libraries for network inference
usually implement direct convolution algorithms for the most common shape of
convolution kernels that do not rely on matrix multiplication. For example,
daBNN library implements $3\times 3$ binary convolution directly. Our ideas of
encoding and computation of ternary and binary dot products can be used in
those algorithms as well.

##  V Conclusion

In this paper, we presented algorithms for matrix multiplication of ternary,
ternary-binary, and binary matrices of ARM CPUs. Those algorithms are superior
to existing CPU implementations of matrix multiplication. For example,
ternary, ternary-binary, and binary multiplications are 3.6, 3.7, and 11 times
faster, respectively, than floating-point multiplication. They have also shown
good computational efficiency compared to 8-bit multiplication from Google’s
gemmlwop library (ternary multiplication is 2.5 times faster) and binary
multiplication from daBNN library (our binary algorithm is 1.15 faster).

Our algorithms can be used in the GeMM-based convolution implementations of
CNNs over a wide range of parameters, which allows for computationally- and
resource-efficient inference of low-bit CNNs on mobile devices.

## Acknowledgment

This work is partially supported by Russian Foundation for Basic Research
(projects 19-29-09066 and 19-29-09092).

## References

  * [1] X.-C. Wen, K.-H. Liu, W.-M. Zhang, and K. Jiang, “The application of capsule neural network based cnn for speech emotion recognition,” in _2020 25th International Conference on Pattern Recognition (ICPR)_. IEEE, 2021, pp. 9356–9362.
  * [2] L. Teplyakov, K. Kaymakov, E. Shvets, and D. Nikolaev, “Line detection via a lightweight cnn with a hough layer,” in _ICMV 2020_ , vol. 11605, no. 116051B. Bellingham, Washington 98227-0010 USA: Society of Photo-Optical Instrumentation Engineers (SPIE), Jan. 2021, dOI: 10.1117/12.2587167.
  * [3] S. P. Ye, C. X. Chen, A. Nedzved, and J. Jiang, “Building detection by local region features in sar images,” _Computer optics_ , vol. 44, no. 6, 2020\.
  * [4] P. A. Kurnikov and D. L. Sholomov, “Dnns for multi-map semantic segmentation,” in _ICMV 2020_ , vol. 11605, no. 1160517. Bellingham, Washington 98227-0010 USA: Society of Photo-Optical Instrumentation Engineers (SPIE), Jan. 2021, dOI: 10.1117/12.2587178.
  * [5] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly _et al._ , “An image is worth 16x16 words: Transformers for image recognition at scale,” _arXiv preprint arXiv:2010.11929_ , 2020.
  * [6] Z. Liu, Y. Lin, Y. Cao, H. Hu, Y. Wei, Z. Zhang, S. Lin, and B. Guo, “Swin transformer: Hierarchical vision transformer using shifted windows,” _arXiv preprint arXiv:2103.14030_ , 2021.
  * [7] I. Tolstikhin, N. Houlsby, A. Kolesnikov, L. Beyer, X. Zhai, T. Unterthiner, J. Yung, D. Keysers, J. Uszkoreit, M. Lucic _et al._ , “Mlp-mixer: An all-mlp architecture for vision,” _arXiv preprint arXiv:2105.01601_ , 2021\.
  * [8] T. Yu, X. Li, Y. Cai, M. Sun, and P. Li, “S2-mlp: Spatial-shift mlp architecture for vision,” in _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , 2022, pp. 297–306.
  * [9] R. Liu, Y. Li, D. Liang, L. Tao, S. Hu, and H.-T. Zheng, “Are we ready for a new paradigm shift? a survey on visual deep mlp,” _arXiv preprint arXiv:2111.04060_ , 2021.
  * [10] J. Gorospe, R. Mulero, O. Arbelaitz, J. Muguerza, and M. Á. Antón, “A generalization performance study using deep learning networks in embedded systems,” _Sensors_ , vol. 21, no. 4, p. 1031, 2021.
  * [11] K. Chellapilla, S. Puri, and P. Simard, “High Performance Convolutional Neural Networks for Document Processing,” in _Tenth International Workshop on Frontiers in Handwriting Recognition_ , G. Lorette, Ed., Université de Rennes 1. La Baule (France): Suvisoft, Oct. 2006, http://www.suvisoft.com. [Online]. Available: https://hal.inria.fr/inria-00112631
  * [12] A. Anderson, A. Vasudevan, C. Keane, and D. Gregg, “High-performance low-memory lowering: GEMM-based algorithms for DNN convolution,” in _2020 IEEE 32nd International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD)_. IEEE, 2020, pp. 99–106.
  * [13] A. V. Trusov, E. E. Limonova, D. P. Nikolaev, and V. V. Arlazarov, “p-im2col: Simple yet efficient convolution algorithm with flexibly controlled memory overhead,” _IEEE Access_ , vol. 9, pp. 168 162–168 184, 2021, dOI: 10.1109/ACCESS.2021.3135690.
  * [14] A. Lavin and S. Gray, “Fast algorithms for convolutional neural networks,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 4013–4021.
  * [15] D.-O. G. Sotiropoulos and G.-P. Economou, “Porting a convolutional neural network for stereo vision in hardware,” in _2020 25th International Conference on Pattern Recognition (ICPR)_. IEEE, 2021, pp. 1313–1320.
  * [16] E. Georganas, S. Avancha, K. Banerjee, D. Kalamkar, G. Henry, H. Pabst, and A. Heinecke, “Anatomy of high-performance deep learning convolutions on simd architectures,” in _SC18: International Conference for High Performance Computing, Networking, Storage and Analysis_. IEEE, 2018, pp. 830–841.
  * [17] B. Jacob, S. Kligys, B. Chen, M. Zhu, M. Tang, A. Howard, H. Adam, and D. Kalenichenko, “Quantization and training of neural networks for efficient integer-arithmetic-only inference,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2018, pp. 2704–2713.
  * [18] R. Banner, Y. Nahshan, E. Hoffer, and D. Soudry, “Post-training 4-bit quantization of convolution networks for rapid-deployment,” _arXiv preprint arXiv:1810.05723_ , 2018.
  * [19] Y. Choukroun, E. Kravchik, F. Yang, and P. Kisilev, “Low-bit quantization of neural networks for efficient inference.” in _ICCV Workshops_ , 2019, pp. 3009–3018.
  * [20] A. V. Trusov, E. E. Limonova, D. G. Slugin, D. P. Nikolaev, and V. V. Arlazarov, “Fast implementation of 4-bit convolutional neural networks for mobile devices,” in _Proceedings of International Conference on Pattern Recognition 2020_. IEEE, May 2021, pp. 9897–9903, dOI: 10.1109/ICPR48806.2021.9412841.
  * [21] M. Rastegari, V. Ordonez, J. Redmon, and A. Farhadi, “Xnor-net: Imagenet classification using binary convolutional neural networks,” in _European conference on computer vision_. Springer, 2016, pp. 525–542.
  * [22] J. Zhang, Y. Pan, T. Yao, H. Zhao, and T. Mei, “dabnn: A super fast inference framework for binary neural networks on arm devices,” 2019.
  * [23] A. Bulat and G. Tzimiropoulos, “Xnor-net++: Improved binary neural networks,” _arXiv preprint arXiv:1909.13863_ , 2019.
  * [24] W. Tang, G. Hua, and L. Wang, “How to train a compact binary neural network with high accuracy?” in _Thirty-First AAAI conference on artificial intelligence_ , 2017.
  * [25] H. Alemdar, V. Leroy, A. Prost-Boucle, and F. Pétrot, “Ternary neural networks for resource-efficient ai applications,” in _2017 international joint conference on neural networks (IJCNN)_. IEEE, 2017, pp. 2547–2554.
  * [26] A. Prost-Boucle, A. Bourge, F. Pétrot, H. Alemdar, N. Caldwell, and V. Leroy, “Scalable high-performance architecture for convolutional ternary neural networks on fpga,” in _2017 27th International Conference on Field Programmable Logic and Applications (FPL)_. IEEE, 2017, pp. 1–7.
  * [27] L. Deng, P. Jiao, J. Pei, Z. Wu, and G. Li, “Gxnor-net: Training deep neural networks with ternary weights and activations without full-precision memory under a unified discretization framework,” _Neural Networks_ , vol. 100, pp. 49–58, 2018.
  * [28] D. Wan, F. Shen, L. Liu, F. Zhu, J. Qin, L. Shao, and H. T. Shen, “Tbn: Convolutional neural network with ternary inputs and binary weights,” in _Proceedings of the European Conference on Computer Vision (ECCV)_ , 2018, pp. 315–332.
  * [29] B. Jacob _et al._ , “gemmlowp: a small self-contained low-precision gemm library,” 2017. [Online]. Available: https://github.com/google/gemmlowp
  * [30] K. Goto and R. A. v. d. Geijn, “Anatomy of high-performance matrix multiplication,” _ACM Transactions on Mathematical Software (TOMS)_ , vol. 34, no. 3, pp. 1–25, 2008.