# A Novel Reduction Circuit Based on Binary Tree Path Partition on FPGAs
## 1 Introduction  
In field-programmable gate array (FPGA) applications, reduction circuits can be applied to reduce vectors to scalars. In recent years, advances in integrated circuit technology have brought significant improvements to FPGA performance. Coupled with the inherently high hardware parallelism, FPGAs are used as hardware accelerators in more and more fields, such as signal processing [1, 2], scientific computing [3, 4, 5], machine learning [6, 7, 8], and data centers [9, 10, 11]. In these applications, some algorithms include a large number of operations of vector and matrix, which belongs to the category of reduction problem. Therefore, a high-performance reduction circuit is key to matrix operations.  
The combination of a high-performance reduction circuit and a small-sized binary tree can effectively solve the trade-off between area and performance. The computing task in Figure 1(a) contains \(m\) data sets \(Set_{0}-Set_{m-1}\), and the data set \(Set_{i}\) contains \(n_{i}\) elements. It can be executed by a variety of hardware solutions. Figure 1(b) shows the use of a reduction circuit as a solution. The data are serially input, one data per cycle. Its advantage lies in its small area, usually only a reduction operator is needed. Figure 1(c) is the diagram of the binary tree. Data are input in parallel, and all elements of a data set are input at a time. Compared with the reduction circuit, the performance of the binary tree is higher. However, it requires more operators, which consumes a lot of area. A compromise is to combine the reduction circuit with a small-sized binary tree, as shown in Figure 1(d). It can not only ensure that the area is maintained in a reasonable range, but also has higher performance. Therefore, a high-performance, small-area reduction circuit is required.  
The design of the reduction circuit faces many challenges. The first is the number of reduction operators. Reduction operators are the primary area source of reduction circuit, so it is necessary to reduce the number of reduction operators as much as possible. The second is data hazards. When the reduction operator of the multi-stage pipeline is used, some partial results cannot be consumed immediately. It needs to be stored in the buffer, waiting for the arrival of another operand. In order to reduce the size of the buffer, the partial results of different data sets are stored in the same buffer. For a unit in the buffer, only data can be written after it is used; otherwise, write after read hazards will occur. Therefore, the data in the buffer need to be properly managed. Third, the circuit needs to be capable of processing any number of data sets, and each data set contains any number of elements. If the reduction circuit can only handle a certain amount of data, it will greatly limit its application. Finally, there are necessities for the performance and complexity of the reduction method.  
In this paper, a novel reduction circuit based on binary tree path partition (BTPP) is proposed. It can handle multiple data sets, and each data set can have any number of elements. The proposed method is implemented on FPGAs, which has the smallest area-time product compared with other designs.  
The remainder of this paper is organized as follows. Section 2 describes the background of the reduction circuit, and Section 3 gives some previous works. Then, Section 4 details the principle and working mechanism of BTPP. After that, the hardware design of BTPP is discussed in Section 5, and the evaluation and comparison results are given in Section 6. Finally, Section 7 summarizes the paper.