SASIMI 2024 Proceedings

R1-6

Eﬃcient FPGA Implementation of Binarized Neural Networks
Based on Generalized Parallel Counter Tree
Takahiro TANIGAWA ††Mugi NODA †††Graduate School of Science and Technology
School of Engineering
Kwansei Gakuin University
1 Gakuen Uegahara, Sanda, Hyogo, 669-1330, JAPAN

Abstract—Binarized neural networks (BNN) allow compact hardware implementation by binarizing
weight values and neuron activations. The critical
path delay of a combinational circuit implementing
a BNN neuron may be curbed by adopting a Wallace
tree of full-adders. However, in FPGA implementation, a 3-input full-adder does not make full use of
LUTs of more than 5 inputs. This paper proposes
the use of a GPC (generalized parallel counter) based
compressor tree in FPGA implementation of a BNN
neuron to reduce both the delay and size of the resulting circuit. We further enhance the eﬃciency ofthe circuit by reducing the comparison of the popcount and threshould into reference to the carry signal from the compressor tree. The critical path delay
and the slice count of our BNN neuron, implemented
on a Xilinx Artinx-7 FPGA, were smaller by 15.1%
and 11.1%, respectively, compared to those of the circuit produced by regular logic synthesis, at number of
inputs 1024.

I.

Nagisa ISHIURA ††Introduction

Neural networks are a powerful tool for image and audio
recognition, and they are being used in a wide range ofapplications.
With the recent development of network technologies,
various data are collected from mobile or edge devices.
Data obtained on the edge side is often transferred tothe server side for processing, for computational load ofinference in neural network is high. However, from theperspective of communication data volume and security,
attempts have been made to shift this processing to theedge side. To achieve processing on edge devices with limited computational resources and strict power consumption constraints, research is being conducted on implementing part or all of the inference processing of neuralnetworks in hardware [1].
A popular approach to reduce resources in the hardware implementation of neural networks is to represent
data with ﬁxed-point numbers and to reduce the number of bits. The values may be constrained to binary,and then the neural network is referred to as a Binarized

Neural Network (BNN) [2]. The BNN allows multiplication operations to be calculated with a single logic gate,
leading to a signiﬁcant reduction in hardware resources.
Thus, research on eﬃcient hardware implementation of
BNNs has been conducted in recent years [3].
In the hardware implementation of BNN neurons, it
can be constructed using XNOR gates to calculate products, a pop counter (parallel counter) to count the number of ones in the result, and a comparator to comparewith a threshold. When considering a combinational circuit implementation, XNOR operations can be performedin parallel, so the comparison with the pop counter andthreshold becomes the bottleneck in the critical path delay.
A BNN neuron can be constructed using XNOR gatesto calculate products, a pop-counter (parallel counter) tocount the number of ones in the products, and a comparator to compare the count with a threshold. In the case of
combinational circuit implementation, XNOR operations
are performed in parallel, so the pop-count and comparison become the bottleneck in the critical path delay.
The pop-count can be attributed to multiple-input addition, which can be achieved by constructing Wallace
trees [4] or Dadda trees [5] with full adders to reducethe critical path delay. However, when implementing on
FPGA devices of the lookup table (LUT) type, a 3-input
full adder may not be an ideal building block because thenumber of inputs to the LUT is typically around 5 to 7. Asa measure to fully utilize the LUTs, the use of expanded
full-adders, such as 6-input/3-output adders, or further
extended generalized parallel counters (GPCs), has been
proposed.
The GPC is a parallel counter that allows both inputs
with a weight of 1 and inputs with a weight of 2k . Literatures [6, 7] propose extremely eﬃcient ways of constructing addition trees for FPGA implementation, targeting
multiple-input additions in multiplication operations andthe like.
This paper presents an eﬃcient FPGA implementationof a BNN neuron utilizing GPCs. The use of GPC tree
to construct the pop-counter is proposed to minimize its
critical path delay and the circuit size. Furthermore, comparison with the threshold is replaced by a test of the most- 32 -

(a) BNN neuron
Fig. 2. Example implementaion of carry chain(b) Logic circuit implementation
Fig. 1. BNN neuron and its logic circuit implementation

signiﬁcant carry output by switching the threshold witha bias, which further reduces the delay and circuit size.
We have implemented BNN neurons on Xilinx’s Artix7 FPGAs based on this method. Compared to neurons
generated by simple logic synthesis, our implementationachieved a 11.1% reduction in slice usage and an 15.1%
reduction in delay time when the number of inputs to theneuron is 1024.
II.

FPGA Implementation of Binarized Neural
Networks

The activation value a of a neural network neuron canbe expressed as follows, as shown in Fig. 1a :a = f (B +N∑

xi · wi ),i=1

where N is the number of neuron inputs, xi represents
the i-th input, wi is the weight associated with the i-th
input, B is the bias, and f is the activation function.
In the case of a binarized neural network (BNN), thevalues of a, xi , and wi are constrained to be either +1 or-1, and f (x) = 1 if (x ≥ 0) and f (x) = −1 otherwise.
Now, if we encode the values +1 and -1 as 0 and 1,
respectively, we can replace the multiplication of inputs
and weights with the Exclusive-NOR (XNOR) operation.
As a result, a BNN neuron can be constructed with XNOR
gates, an adder (pop counter) to count the number of onesin the output, and a comparison with a threshold T , asshown in Figure 1b.
In this paper, we consider implementing a BNN neuron as a combinational circuit, shown in Fig. 1b , on an
FPGA.
A. Lookup Tables (LUTs) and Carry Chains in FPGAs
Lookup table (LUT) type FPGAs utilize conﬁgurable
components (LUTs), ﬂip-ﬂops, and programmable interconnections to implement custom logic functions. LUTs
store truth tables in memories to implement logic functions. The typical number of inputs to LUTs ranges from

Fig. 3. FPGA-implementation of GPC(1,5;3) [8]5 to 7. In some FPGAs, a k-input/1-output LUT may be
used to implement a k − 1-input/2-output logic gate thatshare common input lines.
Furthermore, some FPGAs have built-in carry chains
which are used for eﬃcient implementation of adders andsubtractors. The carry chain accepts the carry generateand carry propagate signals for each digit of two binary
numbers as inputs and computes the sum for the binary
numbers. An example of a 4-digit carry chain circuit isshown in Figure 2. gi and pi represent the carry generate
and propagate signals, respectively, while si denotes theresultant sum.
A module called a slice or a logic block contains several LUTs, carry chains, and ﬂip-ﬂops. Logic circuits are
realized using these slices and programmable interconnections.
B.

Generalized Parallel Counter (GPC)-Based Addition
Tree

Wallace tree [4] and Dadda tree [5] are recognized as
established logic circuit designs for multi-input addtion,with both utilizing full-adders as their basic building
blocks.
However, in the context of FPGA implementation, a
traditional 3-input/2-output full adder fails to utilize thepotential of LUTs, which typically oﬀer 5 to 7 inputs. As
a consequence, the adoption of extended full-adders, suchas 6-input/3-output adders, and more advanced Generalized Parallel Counters (GPC), has been suggested. These
strategies are designed to enhance FPGA circuit eﬃciency
in terms of both size and critical path delay [6] [7] [8] [9][10].
Unlike the full adder or the 6-input/3-output adder, the
GPC accepts inputs of weight 2k as well as 1 and calcu-- 33 -

Fig. 5. FPGA-implementation of BNN neuron

Fig. 6. Replace threshold comparison with carry reference

Fig. 4. GPC-based adder tree

lates the sum of the inputs. For example, GPC(1,5;3)
performs addition of a 1-bit input of weight 21 and 5bit inputs of weight 20 , and outputs the result in 3 bits.
GPC(1,5;3) can be constructed as shown in Fig. 3 , whereb1 is the weight 21 input and a1 through a5 are weight 20
inputs, and (s2 , s1 , s0 ) are resulting outputs. It may be
accomodated in a single slice with two LUTs and a carrychain.
An example of the GPC-based addition tree is shownin Fig. 4 . Each dot represents a single bit, and thedots enclosed in rectangles represent the inputs and outputs of GPCs. Two types of GPCs, GPC(7;3) andGPC(1,3,4,3;5), are used in this design.
The total number of bits are reduced through GPCs toyield two binary numbers. The ﬁnal sum is computed byadding the two numbers using a row adder whose details
will be shown later. The GPCs reduce the total number ofbits until they become two binary numbers. The ﬁnal sum
will be computed by adding these two numbers, whose
details will be presented later.
In [6] and [7], methods were introduced for constructing
optimal addition trees utilizing GPCs, targeting multipleinput addition in binary multiplication and related applications. They aim to generate circuit conﬁgurations withminimal levels, along with the minimal LUT counts orslice counts, for given size and quantity of binary numbers.

III.

Efficient FPGA Implementation of BNNs
Using GPCs

This paper presents an eﬃcient FPGA-targeted designof a BNN neuron.
It proposes the use of optimal GPC construction for the
implementation of a population counter. It also proposes

optimation of the circuit design for threshold comparison.
The overall circuit conﬁguration for the BNN neuron
assumed in this paper is shown in Fig. 5 . At ﬁrst, thecount of 1’s in the outcome of XNOR operations between
K pairs of inputs and weights are computed using LUTs,
1
with K being set to 3 in the ﬁgure (○).
The resulting output is represented in binary format, represented
as (s1 , s0 ). Then, the sum of these outputs is calculated
2 If the sum equals or exceeds the threshold T T, the(○).
3output is set to 1; otherwise, it is set to 0 (○).
2
In this paper, we do not rely on logic synthesis for ○but instead, construct a GPC tree so as to reduce circuit
3
size and critical path delay. Furthermore, the result of ○is determined only by referencing the carry signal from
the MSB of the addition result, by incorporating a biasof 2n − T in the addition, where n is the number of thebits in the sum.
A.

Implementation of Pop-counter Using GPC Tree

The conﬁguration of the addition circuit in this paper
is illustrated in Fig. 7 . The inputs to the addition tree
are N/k binary numbers, with their individual bits represented by dots (the ﬁgure depicts the senario for k = 3,
where each binary number consists of two bits). A GPC
tree is employed to reduce the number of bits iteratively,
until they converge to two binary numbers. These twobinary numbers are then added together to produce theﬁnal result. The adder used in the ﬁnal step is referred toas a ”row adder.”The construction of the GPC (Generalized Pop Counters) tree follows the methodology proposed in references[6], [7], [8], [9], and [10]. Given our assumption of implementing BNN neurons as combinational circuits in thispaper, our goal is to identify the GPC tree conﬁgurationthat minimizes the number of slices among the ones withthe fewest stages. We formalize this as an optimization- 34 -

(a) Conventional threshold comparison.

Fig. 7. GPC-based adder tree(b) Threshold comparison by carry referencing
Fig. 9. Threshold comparison

Fig. 8. FPGA-Implementation of row adderproblem using integer linear programming.
The row adder in the last step in Fig. 7 can be efﬁciently implemented using FPGA carry chains. Fig. 8
shows an example design of a row adder employing a 4digit carry chain. Let us denote i-th digits of the twobinary numbers to be added as ai and bi . The carry generation signal gi = ai · bi and the carry propagation signal
pi = ai ⊕ bi can be computed using a single 2-input/2output LUT. These signals are then fed into the carrychain to generate the sum of the two binary numbers.

(a) Basic conﬁguration

B. Threshold Comparison
Fig. 9 (a) illustrates a straightforward conﬁgurationof the comparison circuit along with the row adder. The
output from the row adder is compared with a separate
comparator. In this paper, we attempt to eliminate thecomparator. The proposed circuit conﬁguration is shownin Fig. 9 (b). Instead of comparing the sum against thethreshould T , we integrate bias B = 2n − T into addition(where n is the number of bits of the sum) and test only
the carry signal from the MSB.
This approach eliminates the requirement to computeall the individual digits of the sum using the row adder.
Instead, it necessitates the generation of generator andpropagator signals only for the carry bit originating fromthe most signiﬁcant bit (MSB). To achieve this, we canutilize the generator and propagator signals from two adjacent digits (or, alternatively, three adjacent digits) combined. This strategy eﬀectively reduces the necessary
number of Look-Up Tables (LUTs), carry chains, andthe overall carry propagation delay during the calculation(b) Optimized conﬁguration with our approach
Fig. 10. Parameter-embedded BNN neuron

process.
C.

Application to Parameter-Embedded Neuron

When performing repeated inference using the same
weights and thresholds, it’s possible to embed the parameters of the neuron directly into the circuit rather than
supplying them from external memory, which lead to reduction both in circuit size and execution cycles.
The basic conﬁguration of a parameter-embedded neuron for BNN is shown in Fig. 10 (a). The XNOR operation between wi and xi is simpliﬁed: it becomes xi when

- 35 -TABLE I
List of GPCs
(1;1)
(3;2)
(7;3)
(1,5;3)(2,3;3)(6,2,3;5)(6,0,6;5)(6,1,5;5)(1,4,1,5;5)

GPC [cite](1,4,0,6;5)(1,3,2,5;5)[9](1,3,4,3;5)[9](2,1,3,5;5)(1,3,5;4)[9](2,2,3;4)[9](2,0,7;4)[9](2,1,5;4)
[9]

[9]
[6]
[6]
[10]
[6]

module B A S E L I N E _ N E U RO N_8 (input wire [7:0] in ,input wire [7:0] weight ,input wire [3:0] threshold ,output wire ans );wire [2:0] dst0 ;wire [2:0] dst1 ;wire [3:0] sum ;LUT6 #(. INIT (64 ’ h 966 969 966 99 696 69 )) input6_0_lower (. O ( dst0 [0]) , . I0 ( in [0]) , . I1 ( weight [0]) , . I2 ( in [1]) ,. I3 ( weight [1]) , . I4 ( in [2]) , . I5 ( weight [2]));
LUT6 #(. INIT (64 ’ h 966 969 966 99 696 69 )) input6_1_lower (. O ( dst0 [1]) , . I0 ( in [3]) , . I1 ( weight [3]) , . I2 ( in [4]) ,. I3 ( weight [4]) , . I4 ( in [5]) , . I5 ( weight [5]));
LUT6 #(. INIT (64 ’ h 966 969 966 99 696 69 )) input6_2_lower (. O ( dst0 [2]) , . I0 ( in [6]) , . I1 ( weight [6]) , . I2 ( in [7]) ,. I3 ( weight [7]) , . I4 (1 ’ h0 ) , . I5 (1 ’ h1 ));LUT6 #(. INIT (64 ’ h f99 f90 099 00 9f9 9f )) input6_0_upper (. O ( dst1 [0]) , . I0 ( in [0]) , . I1 ( weight [0]) , . I2 ( in [1]) ,. I3 ( weight [1]) , . I4 ( in [2]) , . I5 ( weight [2]));
LUT6 #(. INIT (64 ’ h f99 f90 099 00 9f9 9f )) input6_1_upper (. O ( dst1 [1]) , . I0 ( in [3]) , . I1 ( weight [3]) , . I2 ( in [4]) ,. I3 ( weight [4]) , . I4 ( in [5]) , . I5 ( weight [5]));
LUT6 #(. INIT (64 ’ h f99 f90 099 00 9f9 9f )) input6_2_upper (. O ( dst1 [2]) , . I0 ( in [6]) , . I1 ( weight [6]) , . I2 ( in [7]) ,. I3 ( weight [7]) , . I4 (1 ’ h0 ) , . I5 (1 ’ h1 ));assign sum = dst0 [0] + dst0 [1] + dst0 [2] +dst1 [0]*2 + dst1 [1]*2 + dst1 [2]*2;
assign ans = ( sum >= threshold );endmodule

Fig. 11. HDL description of baseline neuron (N = 8)

wi is 1 and x̄i when wi is 0. If 6-input LUTs are available, 6 digits of xi can be processed together to produce
a 3-digit sum, which is fed into the paddition tree.
The same methodology of eliminating the comparator
can be applied, as illustrated in Figure 10 (b). Moreover,
if the bias B contains digits with a value of 0, these digits
can be safely disregarded, further reducing the complexityof the addition tree.

IV.

and 4-bit carry chain. Logic synthesis was carried out
using Vivado 2023.1 for this experiment.
The set of GPCs utilized in this experiment is detailedin TABLE I . All these GPCs are explicitly designed torequire no more than four LUTs and a carry chain, ﬁtting perfectly in a single slice. The conﬁgurations of the
GPC adder trees, aiming for the lowest levels and minimal
slices, were determined through integer programming1 .
We utilized the CPLEX 22.1.0 solver, running on an Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz. Remarkably,
all solutions were found to be optimal and were obtainedin less than one second.
The synthesis results are displayed in Table II, with (a)representing the standard scenario where parameters are
not embedded, and (b) representing the scenario whereparameters are embedded. In both tables, N denotes thenumber of inputs for the BNN neuron, and “slices” and“delay” represent the number of utilized slices and thecritical path delay, respectively. Within each table, “baseline” corresponds to a basic description of the adder tree
and threshold comparison. “GPC-tree” signiﬁes the addertree constructed using GPCs, while “GPC-tree+bias” indicates that the threshold comparison has been replacedwith referencing the carry from the MSB. Fig. 11 shows
Verilog HDL description of the baseline neuron for N = 8.
While the addition of three pairs of XNOR operations are
explicitly mapped to LUTs, summation and comparison
are expressed with standard arithmetic operations. In the“GPC-tree” and “GPC-tree+bias” designs, every GPC is
explicitly assigned to a slice to prevent unintended increases in the slice count.
For standard BNNs, a comparison between “baseline”
and “GPC-tree” demonstrates that circuit optimization
has led to reductions in all circuit sizes. When comparing the performance of ”GPC-tree” with that of ”GPCtree+bias,” a decrease is observed, except for the casewhen N = 512. This increase can be attributed to theadditional cost incurred by the introduction of bias. Nevertheless, it is noteworthy that the delays experienced aconsistent decrease across all scenarios. In the case of
N = 1024, the circuit size and critical path delay werereduced by 11.1% and 15.1%, respectively.
The trends observed for the parameter-embedded
BNNs are similar to those of the standard BNNs, but
the impact on circuit size is more pronounced in theparameter-embedded BNNs. For instance, with N =1024, the circuit size saw a signiﬁcant reduction of 20.6%,
while the critical path delay decreased by 9.7%.

Implementation and Experiment

BNN neurons have been designed based on the proposed method in Verilog HDL. The experimental platform was the Xilinx Artix-7 FPGA (xc7a100tcsg324-3).
This FPGA is equipped with 6-input/1-output Look-Up
Tables (LUTs), which can alternatively function as 5input/2-output LUTs when input resources are shared.
The FPGA contains 15850 slices, each with four LUTs

V.

Conclusion

In this paper, we introduce an eﬃcient method for
FPGA implementation of Binary Neural Network (BNN)
1 The programs used for constructing the adder trees and GPCs
are available on GitHub at the following links: https://github.
com/void-hoge/cmpgen https://github.com/void-hoge/gpcgen- 36 -TABLE II
Synthesis results(a) BNN neuron
slicesdelay (ns)Nbaseline
GPC-tree
GPC-tree+bias
baseline
GPC-tree
GPC-tree+bias

32
28
22
21
9.93
9.64
8.72

64
69
40
38
13.90
10.24
8.86

128
177
86
78
21.17
11.64
10.43

256
176
160
151
14.41
13.32
12.26

512
352
307
314
15.12
14.99
14.12

1024
677
605
602
16.71
15.48
14.18

512
231
181
197
13.70
13.21
12.73

1024
442
364
351
15.63
14.82
14.12

(b) BNN neuron with parameter embedding
slicesdelay (ns)Nbaseline
GPC-tree
GPC-tree+bias
baseline
GPC-tree
GPC-tree+bias

32
16
15
11
7.60
8.28
8.81

Synthesizer: Xilinx Vivado (2023.1)

64
42
25
22
10.95
9.21
8.69

128
110
48
47
16.93
10.72
10.06

256
102
95
98
12.64
10.97
10.94

Target: Xilinx Artix-7(xc7a100tcsg324-3)

neurons, utilizing Generalized Parallel Counters (GPC)
to construct the adder trees. Our approach yields notable advantages, achieving a 11.1% reduction in circuit
size and a 15.1% reduction in critical path delay compared
to straightforward logic synthesis when handling 1024 inputs.
We envision that this proposed method holds promise
not only for BNNs but also for FPGA implementations ofneural networks employing ﬁxed-point arithmetic. Furthermore, while our focus in this paper is on parallel
combinatorial circuit implementation, processing all inputs simultaneously, there are future prospects to explore
its applicability in parallel/serial hybrid implementations
or pipelined implementations, where inputs undergo processing in multiple stages.

parison of FPGA, CPU, GPU, and ASIC,” in Proc. International Conference on Field-Programmable Technology (FPT2017), pp. 77–84 (May. 2017).
[4] S. C. Wallace.: “A suggestion for a fast multiplier,” in IEEE
Trans. Electronic Computer, vol. EC-13, issue 1 (Feb. 1964).
[5] L. Dadda.: “Some schemes for parallel multipliers,” in Associazione Elettrotecnica ed Elettronica Italiana, vol. 34, pp. 349–
356 (May 1965).
[6] Y. Yuan, L. Tu, K. Huang, X. Zhang, T. Zhang, D. Chen, and Z.
Wang: “Area optimized synthesis of compressor trees on Xilinx
FPGAs using generalized parallel counters,” in IEEE Access,pp. 134815–134827 (Sept. 2019).
[7] M. Kumm and J. Kappauf: “Advanced compressor tree synthesis for FPGAs,” in IEEE Trans. Computers, pp. 1078–1091(Jan. 2018).
[8] M. Kumm and P. Zipf: “Eﬃcient high speed compression
trees on Xilinx FPGAs,” in Proc. Methoden und Beschreibungssprachen zur Modellierung und Veriﬁkation von Schaltungen und Systemen (MBMV), pp. 1–13 (Jan. 2014).

Acknowledgements
Authors would like to express their appreciation to
Dr. Hiroyuki Kanbara of ASTEM/RI, Prof. Hiroyuki
Tomiyama of Ritsumeikan University, and Mr. Takayuki
Nakatani (formerly with Ritsumeikan University) for their
discussion and valuable advises. We would also like tothank to the members of Ishiura Lab. of Kwansei Gakuin
University.

[9] T. B. Preußer: “Generic and universal parallel matrix summation with a ﬂexible compression goal for Xilinx FPGAs,” inProc. International Conference on Field Programmable Logic
and Application, pp. 1–7 (Sept. 2017).
[10] M. Kumm and P. Zipf: “Pipelined compressor tree optimization using integer linear programming,” inProc. International
Comference on Filed Programmable Logic and Applications(FPL2014) pp. 1–8 (Sept. 2014).

References[1] E. Nurvitadhi, G. Venkatesh, J. Sim, D. Marr, R. Huang, J.
Hock, Y. Liew, K. Srivatsan, D. Moss, and S. Subhaschandra:“Can FPGAs beat GPUs in accelerating nextgeneration deepneural networks?”, in Proc. FPGA 2017, pp. 5–14 (Feb. 2017).
[2] M. Courbariaux, I. Hubara, D. Soudry, R. El-Yaniv, and Y.
Bengio: “Binarized neural networks: Training deep neural networks with weights and activations constrained to +1 or −1,”
Computing Research Repository (CoRR), pp. 1–11 (Mar. 2016).
[3] E. Nurvitadhi, D. Sheﬃeld, J. Sim, A. Mishra, G. Venkatesh,and D. Marr: “Accelerating binarized neural networks: Com-

- 37 -