# A Novel Reduction Circuit Based on Binary Tree Path Partition on FPGAs
## 6 Evaluations and Comparison
\begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline  & \multirow{2}{*}{**BTPP**} & \multirow{2}{*}{**SSM [23]**} & \multicolumn{4}{c}{**Prototype [21]**} & \multicolumn{4}{c}{**High Speed [21]**} & \multirow{2}{*}{**MPFA [18]**} & \multirow{2}{*}{**AeMFPA [18]**} & \multirow{2}{*}{**A\({}^{2}\)eMFPA [18]**} \\ \cline{4-4} \cline{6-11}  & & & \(\mathbf{m^{*}=512}\) & \(\mathbf{m^{*}=1024}\) & \(\mathbf{m^{*}=2048}\) & \(\mathbf{m^{*}=512}\) & \(\mathbf{m^{*}=1024}\) & \(\mathbf{m^{*}=2048}\) & \\ \hline adders & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 5 & 2 & 2 \\ Freq. (MHz) & 305 & 300 & 268 & 245 & 201 & 378 & 359 & 356 & 367 & 321 & 247 \\ Slices & 648 & 680 & 1260 & 1848 & 3645 & 1055 & 1394 & 2176 & 1692 & 1234 & 1309 \\ \hline \hline \end{tabular}  
pipeline stages of adder: 14, data type: double-precision floating-point (64-bit), \(\mathbf{m}\) is the upper limit of the number of data sets processed simultaneously by Prototype [21] and High Speed [21].  
\end{table} 
Table 1: Implementation results comparison between different designs on Xilinx XC5 VLX110T. Figure 12: The comparison of execution time and area-time product between different designs, where \(p=14\). We have implemented the two designs in Figure 13 on Xilinx Artix-7 XC7A100T, and the post-implementation results are shown in Table 2. Since the multiplier uses more DSP, its frequency is much higher than that of the adder, and it uses fewer slice LUTs and slice registers than the adder. The BTPP that uses the adder as the reduction operator and the BTPP that uses the multiplier as the reduction operator are listed in the last two columns of Table 2. Through comparison, it can be seen that the control circuit of BTPP does not use DSP but uses 9.5 BRAMs. The resources used by the two BTPP control circuits are approximately equal. We have implemented two circuits for matrix-vector multiplication on Xilinx Artix-7 XC7A100T. The first one is composed of a multiplier and an adder. The accumulation function is realized by feeding back the output of the adder to the input. The second circuit is composed of a multiplier and BTPP that uses an adder as a reduction operator. The adder and multiplier used here are the same as those in Table 2, and the data type and number of pipeline stages are unchanged. The circuit is implemented in Verilog HDL, synthesized and placed and routed through Xilinx Vivado 2019.1 software. The post-implementation results are shown in Table 3. For the circuit that does not use BTPP, the slice LUTs and slice registers consumed are less than the design using BTPP. \begin{table}
\begin{tabular}{c c c c c} \hline \hline  & **Adder** & **Multiplier** & \
\begin{tabular}{c} **BTPP** \\ **(Adder)** \\ \end{tabular} &
\begin{tabular}{c} **BTPP** \\ **(Multiplier)** \\ \end{tabular} \\ \hline bit-width & 64 & 64 & 64 & 64 \\ pipeline stages & 14 & 14 & \(--\) & \(--\) \\ Freq. (MHz) & 296 & 344 & 294 & 285 \\ Slice LUTs & 661 & 176 & 1372 & 926 \\ Slice Reg. & 995 & 557 & 1809 & 1324 \\ DSPs & 3 & 11 & 3 & 11 \\ BRAMs & 0 & 0 & 9.5 & 9.5 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: BTPP with different reduction operators are implemented on Xilinx Artix-7 XC7A100T. Figure 13: Pre-synthesis simulation. (**a**) reduction operator is a double-precision floating-point adder with a 14-stage pipeline; (**b**) reduction operator is a double-precision floating-point multiplier with a 14-stage pipeline. The two circuits in Table 3 are applied to matrix-vector multiplication, and the results are shown in Figure 14. The matrix in Figure 14 has 15 rows and the number of columns is between 15 and 30. In other words, the reduction circuit needs to handle 15 data sets, and the number of elements in each data set is between 15 and 30. For the case of not using BTPP, it needs to consume a lot of execution time. This is because the deep pipelining of the adder does not bring about an increase in throughput. BTPP takes full advantage of the deep pipelining of the adder and greatly reduces the execution time.