# A Novel Reduction Circuit Based on Binary Tree Path Partition on FPGAs
## 6 Evaluations and Comparison  
We implemented BTPP on Xilinx XC5 VLX110T platform using Verilog HDL because most of the existing work is implemented on the same platform. Our circuit is designed and validated manually. To ensure that the reduction operator used by BTTP is the same as other works, a double-precision floating-point adder with 14-stage pipeline, which is synthesized by Xilinx ISE 10.1, is chosen as the reduction operator. The post-implementation results are shown in Table 1. MFPA, AeMFPA, and A2 eMFPA are designs of multiple reduction operators. They consume more slices than the design of a single reduction operator, but the two designs proposed by [21] are exceptions. Although they are designs of a single reduction operator, their frequency and slices are related to the number of data sets they can process simultaneously. As the number of data sets grows, the slices increase more, which will limit its application. The frequency and slices of BTPP and SBM are stable. It has nothing to do with the number of data sets and the number of elements contained in each data set. Their frequency and slices are more balanced in all designs. However, the circuit of SBM is more complicated, which is mainly reflected in the buffer management unit. It needs to identify which units in the buffer store data that are valid, and it also needs to detect elements in the buffer that belong to the same data set. Compared with SBM, the hardware structure of BTPP is simple, without particularly complex logic. At the same time, it can guarantee a better clock frequency and slice consumption than SBM. On Virtex-5, each slice includes four 6-input LUTs and four registers. BTPP uses 1554 slice registers. In addition, 1495 slice LUTs are used as logic, and only three slice LUTs are used as route-thru. The buffers in BTPP are all implemented with dual-port RAM, so 10 BRAMs are used. In addition, 3 DSP48 Es are used in BTPP. Figure 11: An example to show how BTPP hardware works. The reduction operator used is an adder with 4-stage pipeline, and the calculation tasks are \(\sum_{i=0}^{4}a_{i}\) and \(\sum_{i=0}^{3}b_{i}\). We compared the execution time and area-time product of different designs in Table 1, and the results are shown in Figure 12. The number of pipeline stages of reduction operator is 14. The parameter \(m\) is the number of data sets, and \(n\) is the number of elements in each data set. The two designs of [21] in Figure 12 are two circuits that support a maximum of 512 data sets. Since the clock frequency of BTPP is lower than High Speed, MFPA and AeMFPA, BTPP does not have an advantage in execution time. However, it has a smaller consumption of slices, so it has the least area-time product of all designs, which makes BTPP extremely competitive. To prove that the BTPP can be used for different reduction operators, we give presynthesis simulation examples of BTPP using an adder and a multiplier, respectively, in Figure 13. Since the most common problems are \(\sum_{i=0}^{n-1}x_{i}\) and \(\prod_{i=0}^{n-1}x_{i}\), which are the main problems solved by the reduction circuit, we chose adder and multiplier as the reduction operator. The adder and multiplier are IPs generated by Xilinx Vivado 2019.1 software, their data are double-precision floating-point numbers, and the number of pipeline stages is 14. The circuit is implemented in Verilog HDL, and is simulated by ModelSim called by Vivado. Data sets \(\{1,2,3\}\), \(\{1,2,3,4\}\), \(\{1,2,3,4,5\}\), and \(\{1,2,3,4,5,6\}\) are the test. It can be seen from the figure that the input signals of Figure 13a,b are the same, and the time for \(\mathit{dout\_valid}\) to become valid is also the same. At 256 ns, both circuits output the calculation results of the last data set. The output of Figure 13a is 21 (\(=1+2+3+4+5+6\)), and the output of Figure 13b is 720 (\(=1\times 2\times 3\times 4\times 5\times 6\)).