marginparsep has been altered.
topmargin has been altered.
marginparpush has been altered.
The page layout violates the ICML style. Please do not change the page layout,
or include packages like geometry, savetrees, or fullpage, which change it for
you. We’re not able to reliably undo arbitrary changes to the style. Please
remove the offending package(s), or layout-changing commands and try again.

Inference Performance Optimization for Large Language Models on CPUs

Pujiang He 1  Shan Zhou 1  Wenhuan Huang 1  Changqing Li 1  Duyi Wang 1  Bin
Guo 1  Chen Meng 1  Sheng Gui 1  Weifei Yu 1  Yi Xie 1

††footnotetext:  1Intel Corporation, Shanghai, China. Correspondence to:
Pujiang He<EMAIL_ADDRESS>Shan Zhou<EMAIL_ADDRESS>Wenhuan
Huang<EMAIL_ADDRESS>
Published at ICML 2024 Workshop on Foundation Models in the Wild. Copyright
2024 by the author(s).

###### Abstract

Large language models (LLMs) have shown exceptional performance and vast
potential across diverse tasks. However, the deployment of LLMs with high
performance in low-resource environments has garnered significant attention in
the industry. When GPU hardware resources are limited, we can explore
alternative options on CPUs. To mitigate the financial burden and alleviate
constraints imposed by hardware resources, optimizing inference performance is
necessary. In this paper, we introduce an easily deployable inference
performance optimization solution aimed at accelerating LLMs on CPUs. In this
solution, we implement an effective way to reduce the KV cache size while
ensuring precision. We propose a distributed inference optimization approach
and implement it based on oneAPI Collective Communications Library.
Furthermore, we propose optimization approaches for LLMs on CPU, and conduct
tailored optimizations for the most commonly used models. The code is open-
sourced at https://github.com/intel/xFasterTransformer.

##  1 Introduction

Large language models (LLMs) based on the Transformer Vaswani et al. (2017)
architecture have garnered profound technical attention globally and achieved
remarkable accomplishments Touvron et al. (2023) , Zhang et al. (2022), Yang
et al. (2023), Wu et al. (2023), Bai et al. (2023). Their robust comprehension
and generation capabilities are profoundly changing applications of artificial
intelligence Thirunavukarasu et al. (2023). However, the practical deployment
of LLMs is significantly hindered by the high cost and resource limitations of
hardware Zhao et al. (2023). Therefore, deploying of LLM with good performance
for practical applications has become a trending topic in industry, which
helps land LLMs in more practical applications. When GPU hardware resources
are limited, we can explore alternative options on CPUs.

Optimizing the practical deployment performance of LLMs necessitates
effectively leveraging hardware capabilities for cost efficiency and improved
inference performance, which, in turn, demands that developers possess a
strong understanding of both hardware and software. To tackle the practical
deployment challenge, we propose an easy and efficient solution designed to
facilitate easy deployment on CPUs. Deploying on CPUs offers the advantage of
being unrestricted by VRAM size, preventing KV cache overflow, and enabling
the processing of extremely long-context support Liu et al. (2023).
Furthermore, deployment on CPUs can enhance system resource utilization,
making multitasking more efficient.

The paper introduces the solution for efficient deployment and inference
performance optimization for LLMs on CPUs. The solution supports for widely
used LLMs, and experiment results show the proposed solution has good
inference performance scalability on CPUs. We have established a repository
where we curate relevant optimization with real-time updates. The main
contributions are as follows:

  * •

We propose new LLM optimize solutions on CPUs, such as SlimAttention. We
conduct individual optimizations for LLM operations and layers, and the
support extends to widely used LLMs, encompassing Qwen, Llama, ChatGLM ,
Baichuan, and Opt series.

  * •

We implement an effective way to reduce the KV cache size and ensure
precision. This approach allows for a more efficient use of memory without
significantly compromising the quality of the model’s output.

  * •

We design a distributed inference optimization solution for LLMs on CPUs,
facilitating the attainment of necessary scalability and efficient low-latency
inference.

##  2 Approach

In this section, three main optimization approaches are proposed and more
details could be referred to the following sections.

###  2.1 LLM Optimization

To improve the inference performance, we proposed individual optimize
solutions for each LLM operations and layers. Taking attention layer as an
example. Since the resources consumed by the attention mechanism are directly
proportional to the square of the sequence length from theoretical, optimizing
attention is particularly important for long sequence inputs.

A new approach we called SlimAttention shown in Figure 1 is proposed.
SlimAttention is essentially a one-dimensional decomposition of the score
between query and key. In terms of computation sequence, it involves first
calculating a horizontal score, followed by applying softmax to the score. The
resulting softmax is then multiplied by the corresponding values, producing a
portion of the output. This process is repeated for the next block using the
same score buffer. In theory, each thread needs only to maintain a buffer of
the block size, thereby reducing memory usage and enhancing computational
efficiency in practice. And FlashAttention Dao et al. (2022) is a solution
initially introduced on GPUs, shown in Figure 2. Essentially, it involves a
two-dimensional decomposition of the score. In the computational process, each
thread only needs to maintain a single tile. However, as a tile doesn’t
encompass all the data in the softmax direction, there is a need for iterative
corrections to the final results during the calculation.

Compared with FlashAttention, SlimAttention entails no redundant computations
but does necessitate a larger intermediate buffer.

Figure 1: Slim Attention Figure 2: Flash Attention

###  2.2 Effective KV cache Optimization

Typical LLM architectures are predominantly decoder-only structures. Within
these models, computation is primarily divided into two categories: attention
(MHA/GQA) and matrix multiplication (MatMul), the latter often including post-
operations that can be fused into the MatMul process. During the generation of
the first token, both attention and MatMul operations are compute-bound.
However, for the generation of subsequent tokens (beyond the first token), the
attention typically exhibits a pattern of general matrix-vector multiplication
(gemv), which is bound in memory bandwidth.

The volume of the key-value (KV) cache accessed during the generation of a
single token can be calculated as follows:

$2b(L_{i}+L_{o})ln_{head}s_{head}s_{d}$ (1)

where the b is batch size, $L_{i}$ and $L_{o}$ are input sequence length and
output sequence length, $n_{head}$, $s_{head}$ $l$, an d$s_{d}$ respectively
represents head number, head size, layer, and size of the data type, and
factor of 2 accounts for both the key and value components.

Consider the Llama2-7B model as an illustrative example, which is
characterized by the following parameters: head_number=32, head_size=128, and
layers=32. Assuming a batch size of 256, an input sequence length of 1024, an
output sequence length of 1024, and the use of FP16/BF16 data types for both
weights and the KV cache, the maximum KV cache required is approximately
128GB. In contrast, the weight data that needs to be accessed is only around
14GB. This comparison underscores the significance of the KV cache size during
inference with large batch sizes.

To enhance performance by effectively reducing the KV cache size, we have
implemented an INT8 KV cache approach. To ensure that the INT8 representation
closely approximates higher precision data types, we maintain a unique scale
for each token and each head as shown in Figure 3. In this method, each head
has a unique scale value, which could regulate the KV cache in a fine grained
pattern, while with acceptable storage increasing. This approach allows for a
more efficient use of memory without significantly compromising the quality of
the model’s output. Moreover, we engineered a custom kernel capable of
supporting MatMul operations with hybrid data types. This kernel is adept at
handling INT8 data, which it dynamically converts to FP32 during execution, as
shown in Figure 4. This conversion process is integral to leveraging the Fused
Multiply-Add(FMA) instructions facilitated by the AVX512 instruction set, a
feature of the most recent x86 architectures. The conversion from INT8 to FP32
is a two-step process: initially, the _mm512_cvtepi8_epi32 intrinsic function
Intel (2024) transforms INT8 into INT32, followed by the _mm512_cvtepi32_ps
function, which then converts the INT32 data into FP32 format. This approach
ensures efficient utilization of the available instruction set for optimized
computational throughput.

Figure 3: Example of maintained unique scale. Figure 4: Custom kernel
workflow.

###  2.3 Distributed Inference Optimization

To enhance distributed inference performance, we present a solution for
optimizing distributed inference for LLMs on CPUs. This solution is
implemented using the oneAPI Collective Communications Library (oneCCL).

In the proposed solution, our solution broadcasts token IDs instead of
broadcasting the values of the Embedding part obtained based on token IDs. We
perform the reduction after each worker computes the top-k, rather than
directly reducing the logits of all tokens. The implementation is shown in
Figure 5 .

Figure 5: Distributed inference based on oneCCL.

Moreover, an aggressive optimization approach was proposed for reduce data
copying since we found that when the computation module and communication
module interact, data copying is often involved in practice. This involves the
computation module, during its last operation before communication, directly
writing the results to the location of the communication module, achieving a
zero-copy implementation which shown in Figure 6.

Figure 6: A zero-copy implementation

##  3 Experiment Results

###  3.1 Configuration

We conducted experiments on the Intel® Xeon® CPU 8563C, and detailed
information of one bare-mental machine is provided in Table 1. Note that each
machine has 2 sockets.

Table 1: Hardware configuration HEADINGS | CONFIG
---|---
CPU Model | Intel Xeon CPU 8563C
Sockets | 2
Cores per Socket | 52
Base Frequency | 2.6GHz
All-core Max Frequency | 3.1GHz

###  3.2 Performance

We measure the throughput and latency of next token generation on Intel® Xeon®
CPU 8563C by adopting the proposed solution.

Table 2 shows next token generation latency results of the Llama2 Touvron et
al. (2023) with 70B parameters under a model configuration with input tokens =
1024, output tokens = 128, batch size = 1. The latency result is better when
it is lower. With 4 bare-mental machines (8 sockets) running the proposed
distributed solution, it could bring 2.85X performance gain for Llama2-70B
compared with 1 bare-mental machine (2 sockets).

Table 2: Next token generation latency of Llama2-70B with the proposed distributed solution SOCKET | LATENCY
---|---
2 | 249.7 ms
8 | 87.7 ms

Table 3 shows the performance comparison of SlimAttention and FlashAttention
on 1 socket. In table 3, 1st column is input length, 2nd column is the
performance of FlashAttention while 3rd column is the performance of the
proposed SlimAttention. Note that performance refers to the average cost time
(ms) of each attention layer during the generation of the first token with
configuration of Llama2-7B model when batch size = 1. It shows the proposed
SlimAttention approach could achieve better performance on CPU.

INPUT | FLASH | PROPOSED SLIM
---|---|---
256 | 10.85 | 1.10
512 | 27.95 | 6.60
1024 | 61.57 | 16.02
2048 | 176.36 | 96.65
4096 | 540.14 | 392.80
Table 3: Performance comparison between FlashAttention and SlimAttention for
different input token sizes.

Table 4 shows throughput without first token of Llama2-7B on 1 socket, under a
model configuration with input tokens = 148, output tokens = 198, and the
batch size is 256/512. Throughput result is better when it is higher. The
proposed solution demonstrates its potential to enhance throughput
effectively.

Table 4: Throughput without first token of Llama2-7B BATCH SIZE | LATENCY
---|---
256 | 796.9 tokens/s
512 | 853.6 tokens/s

##  4 Conclusion and Future Work

We presented an end-to-end LLM inference accelerating solution including
distributed inference optimization, effective KV cache optimization, and
individual LLM optimization. We showcased the versatility across a range of
popular LLMs and the performance superiority over the open-source solution on
CPUs. In our forthcoming research, we intend to broaden our study to include a
wider variety of CPUs, particularly those with resource constraints. Our
primary focus will be on enhancing performance for larger batch sizes and
exploring effective deployment serving solutions. Concurrently, we aim to
adapt our solution to accommodate the latest trending models, such as the
mixture of experts (MoE) models. Our goal is to offer a practical alternative
to existing GPU solutions.

## References

  * Bai et al. (2023) Bai, J., Bai, S., Chu, Y., Cui, Z., Dang, K., Deng, X., Fan, Y., Ge, W., Han, Y., Huang, F., et al.  Qwen technical report.  _arXiv preprint arXiv:2309.16609_ , 2023.
  * Dao et al. (2022) Dao, T., Fu, D., Ermon, S., Rudra, A., and Ré, C.  Flashattention: Fast and memory-efficient exact attention with io-awareness.  _Advances in Neural Information Processing Systems_ , 35:16344–16359, 2022.
  * Intel (2024) Intel, R.  Intrinsics guide, 2024.  https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html.
  * Liu et al. (2023) Liu, N. F., Lin, K., Hewitt, J., Paranjape, A., Bevilacqua, M., Petroni, F., and Liang, P.  Lost in the middle: How language models use long contexts.  _arXiv preprint arXiv:2307.03172_ , 2023.
  * Thirunavukarasu et al. (2023) Thirunavukarasu, A. J., Ting, D. S. J., Elangovan, K., Gutierrez, L., Tan, T. F., and Ting, D. S. W.  Large language models in medicine.  _Nature medicine_ , 29(8):1930–1940, 2023.
  * Touvron et al. (2023) Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., et al.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv preprint arXiv:2307.09288_ , 2023.
  * Vaswani et al. (2017) Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Wu et al. (2023) Wu, T., He, S., Liu, J., Sun, S., Liu, K., Han, Q.-L., and Tang, Y.  A brief overview of chatgpt: The history, status quo and potential future development.  _IEEE/CAA Journal of Automatica Sinica_ , 10(5):1122–1136, 2023.
  * Yang et al. (2023) Yang, A., Xiao, B., Wang, B., Zhang, B., Bian, C., Yin, C., Lv, C., Pan, D., Wang, D., Yan, D., et al.  Baichuan 2: Open large-scale language models.  _arXiv preprint arXiv:2309.10305_ , 2023.
  * Zhang et al. (2022) Zhang, S., Roller, S., Goyal, N., Artetxe, M., Chen, M., Chen, S., Dewan, C., Diab, M., Li, X., Lin, X. V., et al.  Opt: Open pre-trained transformer language models.  _arXiv preprint arXiv:2205.01068_ , 2022.
  * Zhao et al. (2023) Zhao, W. X., Zhou, K., Li, J., Tang, T., Wang, X., Hou, Y., Min, Y., Zhang, B., Zhang, J., Dong, Z., et al.  A survey of large language models.  _arXiv preprint arXiv:2303.18223_ , 2023.


# A Novel _Approximate Hamming Weight_ Computing for Spiking Neural Networks:
an FPGA Friendly Architecture

Kaveh Akbarzadeh-Sherbaf
<EMAIL_ADDRESS>
Mikaeel Bahmani
<EMAIL_ADDRESS>
Danial Ghiaseddin
<EMAIL_ADDRESS>
Saeed Safari
<EMAIL_ADDRESS>
Abdol-Hossein Vahabie
<EMAIL_ADDRESS>

###### Abstract

Hamming weights of sparse and long binary vectors are important modules in
many scientific applications, particularly in spiking neural networks that are
of our interest. To improve both area and latency of their FPGA
implementations, we propose a method inspired from synaptic transmission
failure for exploiting FPGA lookup tables to compress long input vectors. To
evaluate the effectiveness of this approach, we count the number of ‘1’s of
the compressed vector using a simple linear adder. We classify the compressors
into shallow ones with up to two levels of lookup tables and deep ones with
more than two levels. The architecture generated by this approach shows up to
82% and 35% reductions for different configurations of shallow compressors in
area and latency respectively. Moreover, our simulation results show that
calculating the Hamming weight of a 1024-bit vector of a spiking neural
network by the use of only deep compressors preserves the chaotic behavior of
the network while slightly impacts on the learning performance.

_K_ eywords Approximate Adder $\cdot$ Hamming Weight Calculation $\cdot$
Spiking Neural Networks $\cdot$ Synaptic Transmission Failure $\cdot$ Chaotic
Networks

##  1 Introduction

The spiking neural networks (SNNs) are the possible power-efficient
alternatives to the power-hungry artificial neural networks (ANNs). The human
Brain, the source of inspiration for the SNNs, consumes much less power in
comparison to the state-of-the-art hardware accelerators of conventional ANNs.
To break this power wall, researchers strive to mimic the Brain architecture
by introducing novel spiking hardwares [1, 2] and algorithms [3, 4, 5, 6, 7].
Since Brain networks operate between order and chaos [8], the most recent bio-
inspired learning algorithms employ chaotic SNNs as their initial untrained
networks [5, 6, 7].

In an SNN, a presynaptic action potential, also known as a spike, produces a
PSP on the membranes of postsynaptic neurons. The accumulation of charge
particles on the membrane of the postsynaptic neuron may lead the postsynaptic
neuron to fire an action potential. In a typical SNN, each neuron may receives
inputs from thousands of synapses. To accumulate the PSPs, in a binary
network, the number of received spikes should be counted [9].

According to the notation of [9], the connectivity pattern of a biological
neuronal network is usually depicted as an $N\times N$ sparse matrix with the
density below 20% [10]. Each row (or column) of this matrix shows the
presynaptic (or postsynaptic) neurons of a given neuron. Here we call this
N-element vector connection vector (CV) and show its density with $d_{CV}$.
Furthermore, it is common to store the firing activity of the latest snapshot
in another N-element vector called spike vector (SV). We use a similar
notation ($d_{SV}$) to show the density of spike vector. Applying the bitwise
AND between SV and CV produce a new N-element vector in which each ‘1’
represents a presynaptic neuron fired in the previous time step. The density
of the resultant vector (RV) is $d_{CV}\times d_{SV}$. In an extreme case
which SV is an all-ones vector, RV is still sparse ($d_{RV}<20\%$). We
certainly do not expect this extreme case and SV is usually a sparse vector
too. Hence RV is a much sparser vector ($d_{RV}<<20\%$). Hamming weight of RV
is the number of its nonzero elements and it equals the number of received
spikes. Therefore, Hamming weight of RV represents the synaptic efficacy.

In the Brain, only 10-30% of presynaptic spikes produce a postsynaptic
potential (PSP) due to the synaptic transmission failure [11, 12]. In this
paper, for the first time, we implement an approximate Hamming weight
calculator inspired by this phenomenon in hardware. Undoubtedly, the
approximation should not change the activity regimes of chaotic SNNs.

The remainder of the paper is organized in three sections. In the next section
we review some related works and present our method. Section 3 shows the
details of our proposed architecture. In section 4, we compare the accuracy,
resource usage, and delay of the proposed architecture with its exact
counterpart. Finally, in section 5, we conclude the paper with a short but
informative discussion on the obtained results.

##  2 Backgrounds and goals

Several applications in coding theory, cryptography, and neural network
disciplines require counting the ‘1’s’ population in an efficient way. Its
wide range of applications encouraged Intel to support POPCNT (population
count) instruction beginning with the Nehalem architecture [13].

Researchers have proposed efficient techniques for the accurate Hamming weight
computation in both software and hardware frameworks. A good review of
software implementations including the ones who had exposed scalar and vector
parallelism was conducted in [14]. Moreover, it presented a new hybrid scalar-
vector implementation, which had improved its best prior software realizations
up to 1.23$\times$. On the other hand, new counting-based methods for
comparing either two Hamming weights or a Hamming weight with a fixed
threshold were presented in [15]. Furthermore, it reviewed the arithmetic
architectures, which had been proposed to lower the delay and cost complexity.
There is a growing interest in implementing complex computational systems
using reconfigurable devices, particularly field programmable gate arrays
(FPGAs). The work presented in [16] is among the ones concentrating on FPGA
implementations of Hamming weights. They employed a multi-level combinational
circuit to calculate Hamming weights of $2^{L}-bit$ at level $L$. Each level
uses the previous level output to reduce the original input step by step. It
finally results in a decimal vector that indicates the number of ‘1’s in the
input vector. Each level of their proposed architecture well matches the FPGA
lookup tables (LUT). Unfortunately, despite all these efforts, the hardware
resources and consequently the latencies of the circuits increase dramatically
with the number of input bits.

Figure 1: Top. An exact counter is a traditional method to count the number of
‘1’s entries of an input vector. Bottom. Reducing the number of inputs to the
exact counter using an approximate compressor.

While above-mentioned papers include applications such as rank order filters
that require the exact Hamming weight [17], there are applications, which give
robust performances in the presence of the inaccuracy. These types of
applications give us a chance of reducing both hardware cost and latency.
Among such applications, we are particularly interested in SNNs where we need
to count roughly the number of spikes arrived at synaptic clefts [9]. The
synaptic transmission failure is a biological evidence that shows an error up
to almost 90% is tolerable in counting the number of spikes (Hamming weight of
RV). Finally, Postsynaptic neurons use these approximate numbers to quantify
synaptic efficacies.

To calculate the Hamming weight using the conventional exact methods
introduced in [18, 15, 16], an exact compressor is required (Fig. 1
Top)111Throughout the paper, [N:n) denotes a circuit that counts the number of
‘1’s in its N-bit input string and stores the result in an n-bit output string
in either an exact or an approximate manner.. To lower the hardware cost and
latency, for the cases with a large number of input bits, here we propose a
set of multi-level approximate compressors, which are used to reduce the
number of inputs to the exact compressor (Fig. 1 Bottom). It, therefore,
results in an affordable circuit that shows a trade-off between its hardware
requirements, e.g., resource usage and latency, and the accuracy.

Table 1: One-level and two-level approximate compressors with their corresponding percentages of correct outputs from all possible input vectors. Config. | Level 1 | Level 2 | Overall | Correct outputs (%)
---|---|---|---|---
(A) | [6:1) | - | [6:1) | $\approx 11$
(B) | [5:2♢) | - | [5:2♢) | $50$
(C) | [5:2) | - | [5:2) | $\approx 81$
(D) | [6:1) | [6:1) | [36:1) | $\approx 5.4e-08$
(E) | [6:1) | [5:2♢) | [30:2♢) | $\approx 3.8e-06$
(F) | [6:1) | [5:2) | [30:2) | $\approx 4.7e-06$
(G) | [5:2♢) | [6:1) | [15:1) | $\approx 4.9e-02$
(H) | [5:2♢) | [5:2♢) | [25:4♢) | $\approx 1.9e-02$
(I) | [5:2♢) | [5:2) | [25:4) | $\approx 1.9e-02$
(J) | [5:2) | [6:1) | [15:1) | $\approx 4.9e-02$
(K) | [5:2) | [5:2♢) | [25:4♢) | $\approx 1.7e-03$
(L) | [5:2) | [5:2) | [25:4) | $\approx 7.8e-03$

##  3 Proposed Architecture

FPGA LUTs in general terms are designed to implement various binary functions.
They, therefore, should be fabricated in such a way that meets diverse
requirements. It seems that small lookup tables distributed throughout the
device have the best design trade-offs. To build larger memory, it is possible
to cascade multiple LUTs. Such a design opens up an opportunity to employ LUTs
in the core of an approximate hardware, especially for our domain of interest.
Let $I$ and $O$ be the number of LUTs’ inputs and outputs respectively, then
$\lceil\log_{2}(I)\rceil>O$ for a given LUT, particularly in 7-series Xilinx
FPGAs, which are our target family devices. This expression means that a
single LUT cannot count the number of ‘1’s in the input vector when the number
of ‘1’s are greater than $2^{O}$. Indeed, it is an approximate counter that
can show a near exact performance for the sparse inputs.

###  3.1 FPGA LUTs as One-Level Approximate Compressors

LUTs of Xilinx 7-series FPGAs can be configured as either a six-input (LUT6)
or two five-input (LUT5) boolean function generators (Fig. 2). Since LUT6 has
only one output, it could count up to only one nonzero element. It, therefore,
is an approximate counter that gives an accurate result just in almost
$(7/64)\times 100\approx 11\%$ of all possible cases (Configuration A in Table
1). Despite its great error at first glance, it could produce more accurate
results under sparse conditions, which will be shown in section 5. From now
on, [6,1) stands for a one-level approximate compressor built by LUT6 (Fig.
2A). Although this compressor contains inaccuracy, it is worth considering due
savings made in resource consumption. It compresses an input vector into a six
times smaller vector that is the input to the second level exact compressor
illustrated in Fig. 1. Reducing the number of inputs of an exact compressor
brings its resource usage down exponentially.

Figure 2: Overview of the lookup tables of Xilinx 7 series FPGAs. They could
be used as one-level compressors.  Figure 3: Various configurations of two-
level approximate compressors using FPGA LUTs.

LUT5, on the other hand, has two output bits along with one less input. Thus,
it results in a more accurate and less compressed vector. We interpret two
output bits as a binary code in two ways: (1) a positional and (2) a non-
positional number. Throughout the paper, [5:2) and [5:2♢) denote the
positional and nonpositional numbers respectively. The outputs of both five-
input compressors are $O=\\{``00",``01",``10",``11"\\}$. In a [5:2)
compressor, each object of the set $O$ is a binary number that shows 0, 1, 2,
or 3 ones of the input vector respectively. Hence, it could count up to three
ones of the input vector. On the contrary, the number of objects’ ones of the
set $O$ determines the number of input bits with values of ‘1’s for the [5:2♢)
compressor. Although this coding scheme has the higher error, it hopefully
lowers the resource usage of the second level exact compressor mainly because
the exact compressor is a multi-operand adder with one-bit operands (aka
counter) and two-bit operands for the [5:2♢) and [5:2) cases respectively.

The [5:2♢) and [5:2) compressors give accurate results in almost
$(16/32)\times 100=50\%$ and $(26/32)\times 100\approx 81\%$ of all possible
cases respectively (Configuration B and C shown in Table 1). As it will be
shown later, they could show much better results in sparse conditions. While
these compressors lead to more accurate results, they consume more resources
than [6:1). A five-input compressor converts the input vector to a 2.5 times
smaller vector, in contrast to six-input compressor, which produces six-times
smaller output vector.

Figure 4: Errors of one-level and two-level compressors for different
densities.

###  3.2 Two-Level Approximate Compressors

To further compress the vector injected to the exact level, it is possible to
cascade the LUT6 ([6:1) compressor) and LUT5s ([5:2♢) and [5:2) compressors)
in multiple levels. We thus obtain four main categories for the case of two-
level approximate compressors, which is of our interest in this paper (Fig.
3). Since the LUT5 has two output coding styles in this paper, there are nine
distinct configurations for two-level compressors. Fig. 3A illustrates a
configuration that uses LUT6s to form a [36:1) compressor. Fig. 3B shows the
[30:2) and [30:2♢) compressors that their outputs are 15 times smaller than
their inputs in term of the number of bits. Four of twelve possible
configurations are stated in Fig. 3C, which includes LUT5s. These four
configurations consists of two [25:4) and two [25:4♢) compressors (see Table 1
for more details about the arrangements of the LUTs). The left configurations
are two types of [15:1) compressors represented in Fig. 3D where three LUT5s
and an LUT6 are placed in the first and second level respectively.

Table 1 shows the percentage of exact outputs for 12 configurations. According
to this table, the [5:2) one-level compressor have significant accuracy, and
it could be a great compressor in a Hamming weight counter. As it will be said
later, this compressor is the best one from the accuracy point of view. On the
other hand, although the percentage of correct outputs of the [6:1) one-level
compressor is orders of magnitude higher than two-level compressors, it does
not guarantee it will have higher total accuracy than two-level ones. This is
due to the fact that more than one bit with value 1 is not recognizable in the
only six-bit distance. It will be shown that the [6:1) compressor in any
architecture highly reduces the accuracy of the circuit.

###  3.3 Deep Compressors

The density of RV (see Section 1) are usually several orders of magnitude less
than one. Consequently, we can employ deeper compressors with more levels of
LUT6s and LUT5s instead of shallow one-level and two-level ones. To show the
possibility of replacing the shallow compressors with deep ones, we will
examine their impact on the SNN performance in Section 4.2. There, the
[216:1), [540:1), and [1024:1) compressors, along with shallow [6:1) and
[36:1) compressors, will be applied to a network of 1024 Izhikevich neurons.

###  3.4 Final Exact Counter

Although the approximate compressors reduce the number of input vector bits,
it is finally necessary to calculate the Hamming weight of the reduced input
vector using an exact adder. There are many techniques to implement such a
circuit. One implementation could be a traditional tree or linear adder [19].
On the other hand, it is possible to employ dedicated architectures introduced
for Hamming weight calculation [15]. In this paper, we want to examine the
effects of approximate counters on the delay and resource usage. Indeed
approximate counter is what matters—the type of the exact counter is of
secondary importance. Therefore, we employ a simple linear adder to show the
efficacy of the proposed compressors.

##  4 Results and Discussion

In this section, we estimate the error of our proposed architecture under
different sparsities. We also show the impact of the synaptic transmission
failure modeled by the proposed architecture on the chaotic activity of a
chaotic SNN. Moreover, we use the Xilinx Vivado design suite to synthesize the
architecture in order to report the latency and area cost.

###  4.1 Accuracy of the Architecture

To evaluate the accuracy, we write a OCTAVE code to simulate the shallow one-
level and two-level compressors for 1024-bit inputs. In this code, for the
final exact adder, we employ OCTAVE built-in "sum" function. We then inject
1000 different randomly generated binary vectors (uniformly distributed) with
a given sparsity to the model. It results in 1000 different errors for an
architecture per a given sparsity. The mean and standard deviation of the
obtained errors are reported in Fig. 4. To explore the effects of sparsity, we
vary the densities of the random input vectors from 1% to 100%. Note that the
standard deviations are far too small to be visible in this chart.

As it can be clearly seen in Fig. 4, while the [5:2) configuration shows the
lowest error for all sparsities, the [36:1) denotes the highest errors, as we
have expected. One of the interesting point to note here is the ability of
even [36:1) compressor to show satisfactory errors for some applications. For
example, the error of about 12% at a density of 1% is good enough for a few
applications in spiking neural networks [9]. Comparison of one-levels and two-
levels compressors show that some two-levels’ compressors (K, H, I, L) have
lower errors than configuration (A) that is a one-level compressor.
Furthermore, (I) and (L) compressors surprisingly present an error near (B)
and (C) for densities below 10%.

###  4.2 Impact on Chaotic activity

Table 2: Synaptic failures percentages, mean firing rates, and mean squared errors of different configurations. Config. | Synaptic Failure (%) | MFR | MSE
---|---|---|---
| max, mean | spikes/sec |
Exact | 0, 0 | 7.30 | 3.77$\times$10-3
[6:1) | 1.85, 0.08 | 7.26 | 1.30$\times$10-3
[36:1) | 2.54, 1.08 | 7.33 | 2.27$\times$10-3
[216:1) | 9.01, 1.33 | 7.28 | 2.62$\times$10-3
[540:1) | 17.45, 1.52 | 7.29 | 2.32$\times$10-3
[1024:1) | 31.29, 1.68 | 7.22 | 13.89$\times$10-3
Figure 5: Top. Membrane voltage of the first neuron. Middle. Raster diagram of
the network. Bottom. Population activity calculated by the use of moving
average method with window length of 8 ms.

To test the impact of synaptic failure modeled by the proposed compressors, we
choose a network of Izhikevich neurons suggested by [6] to implement a chaotic
SNN. They trained their proposed network to learn chaotic attractors. This
network is a 1024-neuron network with density of 10% and thus sparsity of 90%.
The network has equal number of excitatory and inhibitory neurons, and
therefore connection matrices densities of both types of neurons are 5%. We
made two modifications to the original network. First, since our proposed
method is applicable to binary networks, we changed the real-valued connection
matrix to a bi-valued one. Second, we replaced the exact adder used to
accumulate the presynaptic spikes with five approximate ones with five
different shallow and deep compressors. The first three compressors consist of
one, two, and three levels of LUT6s to make [6:1), [36:1), and [216:1)
compressors. Next, [540:1) compressor which can be made by [36:1) and [15:1)
compressors is the main compressor. Finally, our compressor is [1024,1)
compressor that can represent any [x:1) compressors with x$>$1024\. To
investigate the impact of proposed compressors on the network, we consider
both chaotic activity and the learning performance.

We run the network for five seconds split into three intervals, namely
initialization, train, and generate. In initialization interval lasted two
seconds, the network run without applying target sine signal. Before
evaluating the compressors’ impacts, we study the exact network activity. Fig.
5a shows the membrane voltage of the first neuron for the initialization
period. Moreover, the whole network activity is represented by the use of
raster diagram and the population activity illustrated in Fig. 5b and Fig. 5c
respectively. To show that the network is in chaos, we delete the one spike of
the first neuron, indicated by a black arrow. As it is expected, the membrane
voltage and the network activity deviate from the original network without the
deletion of a spike. This is a clear indication of chaotic behavior [6].

Figure 6: Left. Membrane voltage of the first neuron for the networks equipped
with shallow and deep compressors. Right. The corresponding population
activities. Figure 7: A 5 Hz sine wave is used as the target signal. After
training for two seconds, the network runs freely to regenerate its learned
dynamics.

Fig. 6 shows the first neuron membrane voltage and population activity for
five network setups with approximate Hamming weight calculators. The use of
each compressor results in different membrane voltages and population
activity. However, they follow similar patterns and therefore the chaotic
behavior is preserved. The maximum variation of mean firing rate (MFR) is
about 0.5% (Table 2). This indicates that the type of the compressor has no
significant impact on the network activity, even for the deepest possible
compressor, i.e. [1024:1).

We use a 5 Hz sine wave as a teacher signal to train the network to adapt its
dynamics. The training time is two seconds, then we simulate the network for
one additional second to see its internal dynamics. Fig. 7 shows the desired
signal and the generated signal of each approximate network. As it can be
seen, all approximate networks mimic the target signal accurately. As it is
shown in Table 2, the first four approximate networks show even lower mean
squared error (MSE) than the exact network. Only the network with [1024:1)
compressor has higher MSE, which is largely due to the time lag, not the shape
of the generated signal. These interesting results are obtained while the
maximum synaptic failure (Table 2) is much less than what is in the Brain (see
Section 3.3).

Figure 8: Resource consumptions and total latencies along with their mean,
min, and max for different levels of optimizations.

###  4.3 Hardware Synthesis Results

To measure the latency and resource consumption improvement achieved through
the use of the proposed architecture, we choose Xilinx Artix-7 as our target
FPGA. First, we design all 12 approximate counters using Verilog HDL.
Moreover, we have used the "dont_touch" attribute to prevent optimizations for
these counters. We next write a behavioral code to aggregate the outputs of
the counters using a linear adder. Finally, we put the Vivado design suite to
synthesize the RTL code automatically using its various optimization levels.
In this work, we employ “Default", “AreaOptimized High", “AreaOptimized
Medium", and “FewerCarryChains" optimization levels, which result in different
resources usage and latencies.

Figure 8 illustrates the resources usage including LUTs and CarryChains as
well as the latency of the critical path in the nanosecond. All values are
reported for four optimization levels mentioned above. For the sake of
clarity, the means are shown in the red step graph, and the max and min values
are represented with dashed green lines. Moreover, we show the mean values in
Table 3. In comparison with an exact counter, this table reveals that even the
most accurate approximate counter (C) represents about 43% reduction of the
LUT consumption on average. This value is far higher for the (D) configuration
where the LUT usage decreased by more than 82%. From the latency point of
view, while the best configuration, i.e. (C), shows only 6% reduction, the
latency of the configuration with the worst accuracy, i.e. (D), reduces by
almost 35%.

We have interpreted the two outputs of LUT5 in as positional and nonpositional
systems. The synthesis results show that a [5:2♢) compressor causes more LUT
usage when it is used as either one-level or second level of a two-level
compressor. To verify this issue, we can compare configurations B, E, H, and K
with C, F, I, and L respectively. Surprisingly, while the [5:2♢) compressor
increases the LUT usage, it improves the latency. It is worth pointing out
that, in this paper, we use a simple linear adder to aggregate the outputs of
the approximate compressors. Using different methods, such as ones introduced
in [15, 16], could adversely affect the trend.

Table 3: Synthesis report for all configuration in comparison with exact one. all represented entries are mean values of four optimization levels. Config. | LUT Usage | #CarryChains | Total Latency (ns)
---|---|---|---
Exact | 1295 | 3 | 12.59
(A) | 367 | 1.5 | 10.06
(B) | 828 | 3 | 11.57
(C) | 737 | 3 | 11.78
(D) | 232 | 0 | 8.16
(E) | 301 | 0 | 9.48
(F) | 282 | 1.5 | 9.51
(G) | 352 | 0 | 9.21
(H) | 517 | 1.5 | 10.78
(I) | 473 | 1.5 | 11.17
(J) | 350 | 0 | 9.57
(K) | 540 | 1.5 | 11.09
(L) | 476 | 1.5 | 11.36

##  5 Conclusion

Inspired by synaptic transmission failure in the Brain, we have introduced an
approximate architecture to calculate Hamming weight of a sparse binary
vector. Our proposed method can be not only used to model the synaptic failure
but also can be used as a general approximate Hamming weight calculator. This
technique has split the Hamming weight calculator into two parts. First part
is a LUT-based compressor that reduces the number of inputs of the second
part, which is a smaller exact counter. This approach can improve both area
and latency of FPGA based Hamming weight counters. Meanwhile, it could give a
reasonable accuracy for sparse input vectors. Sparser vectors result in more
accurate results. We proved this hypothesis using all 12 possible
implementations of one-level and two-level compressors. Moreover, we applied
both shallow and deep compressors to a network of 1024 spiking neurons. Then,
we use this network to mimic a simple 5 Hz sine wave. Our simulation results
show that even the deepest possible compressor could result in good learning
performance while preserve the network chaotic activity. Finally, we show that
all approximate implementations on FPGAs considerably outperform the exact
one.

## References

  * [1] P A Merolla, J V Arthur, R Alvarez-Icaza, A S Cassidy, J Sawada, F Akopyan, B L Jackson, N Imam, C Guo, Y Nakamura, B Brezzo, I Vo, S K Esser, R Appuswamy, B Taba, A Amir, M D Flickner, W P Risk, R Manohar, and D S Modha.  A million spiking-neuron integrated circuit with a scalable communication network and interface.  Science, 345(6197):668–673, aug 2014.
  * [2] Mike Davies, Narayan Srinivasa, Tsung-Han Lin, Gautham Chinya, Yongqiang Cao, Sri Harsha Choday, Georgios Dimou, Prasad Joshi, Nabil Imam, Shweta Jain, Yuyun Liao, Chit-Kwan Lin, Andrew Lines, Ruokun Liu, Deepak Mathaikutty, Steven McCoy, Arnab Paul, Jonathan Tse, Guruguhanathan Venkataramanan, Yi-Hsin Weng, Andreas Wild, Yoonseok Yang, and Hong Wang.  Loihi: A Neuromorphic Manycore Processor with On-Chip Learning.  IEEE Micro, 38(1):82–99, jan 2018.
  * [3] Herbert Jaeger.  The "echo state" approach to analysing and training recurrent neural networks.  GMD Report 148, 2001.
  * [4] Wolfgang Maass, Thomas Natschläger, and Henry Markram.  Real-Time Computing Without Stable States: A New Framework for Neural Computation Based on Perturbations.  Neural Computation, 14(11):2531–2560, nov 2002.
  * [5] David Sussillo and L.F. Abbott.  Generating Coherent Patterns of Activity from Chaotic Neural Networks.  Neuron, 63(4):544–557, aug 2009.
  * [6] Wilten Nicola and Claudia Clopath.  Supervised learning in spiking neural networks with FORCE training.  Nature Communications, 8(1):2208, dec 2017.
  * [7] Aditya Gilra and Wulfram Gerstner.  Predicting non-linear dynamics by stable local learning in a recurrent spiking neural network.  eLife, 6, nov 2017.
  * [8] Junling Gao, Jicong Fan, Bonnie Wai Yan Wu, Zhiguo Zhang, Chunqi Chang, Yeung-Sam Hung, Peter Chin Wan Fung, and Hin hung Sik.  Entrainment of chaotic activities in brain and heart during MBSR mindfulness training.  Neuroscience Letters, 616:218–223, mar 2016.
  * [9] Kaveh Akbarzadeh-Sherbaf, Behrooz Abdoli, Saeed Safari, and Abdol-Hossein Vahabie.  A Scalable FPGA Architecture for Randomly Connected Networks of Hodgkin-Huxley Neurons.  Frontiers in Neuroscience, 12, oct 2018.
  * [10] Hamed Seyed-allaei.  Phase diagram of spiking neural networks.  Frontiers in Computational Neuroscience, 9, mar 2015.
  * [11] Neal A. Hessler, Aneil M. Shirke, and Roberto Malinow.  The probability of transmitter release at a mammalian central synapse.  Nature, 366(6455):569–572, 1993.
  * [12] H. Markram and M. Tsodyks.  Redistribution of synaptic efficacy between neocortical pyramidal neurons.  Nature, 382(6594):807–810, 1996.
  * [13] Hari Subramoni, Fabrizio Petrini, Virat Agarwal, , and Davide Pasetto.  High performance topology-aware communication in multicore processors.  In Jakub Kurzak, David A. Bader, and Jack Dongarra, editors, Scientific Computing with Multicore and Accelerators, pages 443–459. CRC Press, NY, USA, 1st edition, 2010.
  * [14] Enric Morancho.  A hybrid implementation of Hamming weight.  In 2014 22nd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, pages 84–92. IEEE, feb 2014.
  * [15] Behrooz Parhami.  Efficient Hamming weight comparators for binary vectors based on accumulative and up/down parallel counters.  IEEE Transactions on Circuits and Systems II: Express Briefs, 56(2):167–171, feb 2009.
  * [16] Valery Sklyarov and Iouliia Skliarova.  Design and implementation of counting networks.  Computing, 97(6):557–577, jun 2015.
  * [17] V A Pedroni.  Compact Hamming-comparator-based rank order filter for digital VLSI and FPGA implementations.  Proceedings of the 2004 IEEE International Symposium on Circuits and Systems (ISCAS’2004), 1:585–588, 2004.
  * [18] Earl E. Swartzlander.  Parallel Counters.  IEEE Transactions on Computers, C-22(11):1021–1024, nov 1973.
  * [19] Behrooz Parhami.  Computer arithmetic : algorithms and hardware designs.  Oxford University Press, NY, USA, 2nd edition, 2010.