# A Novel Reduction Circuit Based on Binary Tree Path Partition on FPGAs
## 5 Hardware Design  
The hardware structure of BTPP is shown in Figure 7. It is mainly composed of the controller, path table pipeline, and data-path. The controller includes modules \(\mathit{system\_time\_gen}\), \(\mathit{path\_table\_gen}\), \(\mathit{buffer\_management}\), \(\mathit{MUX\_sel\_gen}\), and \(\mathit{dout\_valid\_gen}\). Different signals are marked with different colored lines. Data are input sequentially through the port \(\mathit{din}\), and the signal \(\mathit{din\_valid}\) is used to indicate whether the current input data are valid. If the signal \(\mathit{set\_end}\) is valid, it means that the current input data are the last element of the set. Module \(\mathit{system\_time\_gen}\) is used to generate time information, which indicates that the \(i\)-th operation of the \(k\)-th iteration is being executed. Module \(\mathit{path\_table\_gen}\) generates path table based on input signals \(\mathit{din\_valid}\) and \(\mathit{set\_end}\). In addition, the path table is input into the path table pipeline. The path table pipeline has a \(p\)-stage, the same as the reduction operator. Module \(\mathit{buffer\_management}\) and \(\mathit{MUX\_sel\_gen}\) respectively generate buffer read and write signals and MUX control signals. These signals will be sent to the data-path to control data reading and writing and computations. When all the paths in the path table have been executed, and it does not need to be added to the result of the next iteration, the signal \(\mathit{dout\_valid}\) generated by the module \(\mathit{dout\_valid\_gen}\) becomes valid, which indicates that the signal \(\mathit{dout}\) at the current moment is the final result of the set. Data-path contains a \(p\)-stage pipeline adder. The data input from \(\mathit{din}\) will be stored in buffer 1 first, and it will be delayed by \(p\) clock cycles. Therefore, the size of buffer 1 is \(p\). During these \(p\) clock cycles, a path table is generated. If \(x_{i,j}\) is the last element of the data set, and it is not consumed at the current moment, it will be stored in buffer 4. The data in buffer 4 will be sent to the reduction operator as operand 2. If \(\mathit{dout}\) is not the final result of the set, it will be sent to the reduction operator or stored in the buffer. Buffer 2 and buffer 3 are used to store operand 1 and operand 2, respectively. The two operands are stored in two different buffers, which can simplify the control logic of the buffer and improve the speed of reading and writing. The path tables of the data in buffer 2 are stored in buffer 5, so the two buffers use the same control signals. The path tables of the data in buffer 3 and buffer 4 are stored in buffer 6 and buffer 7, respectively. Figure 7: The hardware structure of BTPP. When \(p=1\), BTPP executes serially, and there is no need to use a buffer. When \(p\geq 2\), buffers 2-7 have the same size, and their sizes are all \((\log_{2}p+2)\times\lceil p/2\rceil\). The maximum number of iterations executed simultaneously is \((\log_{2}p+2)\), where \(p\geq 2\). As shown in Figure 5c, there are four iterations at the same time (\(p=4\)). After iteration 0 is completed, iteration 4 is executed. When \(p\geq 2\), there are \(\lceil p/2\rceil\) nodes in an iteration that need to be allocated storage units. Taking Figure 5e as an example, there are only two possible cases for node \(t_{1}\) and node \(t_{2}\). For node \(t_{1}\), it will execute \(x_{i}+x_{i+1}\) or \(0+x_{i+1}\). In both cases, there is no need to read operands from the buffer. Only the operands of node \(t_{3}\) and node \(t_{4}\) are stored in the buffer, so \(p/2\) nodes need to be allocated storage units. If \(p\) is an odd number, it is \(p/2+1\). Therefore, the sizes are \((\log_{2}p+2)\times\lceil p/2\rceil\) when \(p\geq 2\). BTPP has a simple buffer management mechanism. From the previous description, when \(p\geq 2\), there are at most \((\log_{2}p+2)\) iterations at the same time, and only \(\lceil p/2\rceil\) nodes in each iteration need to be allocated storage units.