# A Novel Reduction Circuit Based on Binary Tree Path Partition on FPGAs
## 2 Background  
The function of the reduction circuit is to reduce vector to a scalar by using associative and commutative reduction operators [12]. For the data set \(X=\{x_{0},x_{1},\cdots,x_{n-1}\}\), reduction circuit performs the following operations:  
\[y=x_{0}\xoplus x_{1}\xoplus\cdots\xoplus x_{n-1} \tag{1}\]  
where is the reduction operator. The reduction operator is a binary operator, such as adder, multiplier, max/min function, etc. If the reduction operator is an adder, then \(y=\sum_{i=0}^{n-1}x_{i}\). If the reduction operator is a multiplier, the output of the reduction circuit is \(\prod_{i=0}^{n-1}x_{i}\). The reduction circuit is only related to the number of pipeline stages and bit width of the reduction operator, and does not care about the hardware structure of the reduction operator. This means that the reduction circuit can use the existing IP core as the reduction operator, which greatly reduces the design difficulty and shortens the design cycle. In addition, it also helps the reduction circuit change its function. For example, the  
Figure 1: Reduction of multiple data sets: different solutions. (**a**) computing tasks; (**b**) reduction circuit; (**c**) binary tree; (**d**) a compromise solution: reduction circuit \(+\) binary tree. reduction operator of a reduction circuit is an adder. By changing the adder to a multiplier, as long as their pipeline stages and bit widths are equal, the reduction circuit can work normally without changing the control circuit. In this paper, the reduction operator takes the adder as an example to analyze the reduction circuit. The simplest reduction circuit can be realized by feeding back the output of the reduction operator to the input, as shown in Figure 2a. It only requires a reduction operator and can handle any amount of data. However, the increase in the frequency of the reduction operator does not bring about an increase in throughput. The reduction operator used in Figure 2b is combinational logic, and calculating \(y[0]=\sum_{j=0}^{2}x[0][j]\) requires \(c_{c}\) clock cycles, while Figure 2c uses a reduction operator of a \(p\)-stage pipeline (\(p=2\)), and calculating \(y[0]=\sum_{j=0}^{2}x[0][j]\) requires \(c_{s}\) clock cycles, where \(c_{c}\), \(c_{s}\) satisfy  
\[\frac{c_{s}}{c_{c}}=p+1 \tag{2}\]  
There is a feedback loop in Figure 2a, assuming that the reduction operator is combinational logic and its critical path delay is \(D\). Since there is a register in the loop, its frequency \(f_{c}\) is  
\[f_{c}=\frac{1}{T_{c}}=\frac{1}{D/1}=\frac{1}{D} \tag{3}\]  
where \(T_{c}\) is the time of one cycle. For a \(p\)-stage pipeline adder, there are \(p+1\) registers in the loop, then its frequency \(f_{s}\) becomes  
\[f_{s}=\frac{1}{T_{s}}=\frac{1}{D/(p+1)}=\frac{p+1}{D} \tag{4}\]  
where \(T_{s}\) has the same properties as \(T_{c}\). The frequency of the latter is increased by \(p+1\) times. Therefore, the calculation time required in Figure 2b is  
\[t_{c}=\frac{c_{c}}{f_{c}}=c_{c}\times D, \tag{5}\]  
and the calculation time required in Figure 2c is  
\[t_{s}=\frac{c_{s}}{f_{s}}=\frac{(p+1)\times c_{c}}{f_{s}}=c_{c}\times D \tag{6}\]  
This means that, when handling the same amount of data, the time required for these two solutions is the same. Figure 2d shows an example of performing one operation per clock cycle. It can only reduce the input data to \(p+1\) partial results, and the reduction calculation cannot be completed. Therefore, it is necessary to propose a reduction circuit to complete the calculation correctly and give full play to the advantages of the pipelined reduction operator. There are some differences between the reduction circuit and accumulator [13; 14; 15; 16], which are listed as follows:  
* The accumulator has a single function, while the reduction circuit can choose different types of reduction operators to achieve different functions, such as accumulation and max function. * The accumulator needs to implement the addition function in the circuit, and the circuit structure is complicated.