# A Novel Reduction Circuit Based on Binary Tree Path Partition on FPGAs
## 5 Hardware Design
As shown in Figure 9b-d, when the cycle is 9-11, \(mod\_cycle\) is 1, 2, and 3, respectively. At this time, columns corresponding to \(x_{i+1}-x_{i+3}\) in PGM and PTF perform OR operations to obtain PTF(1), PTF(2), and PTF(3), respectively. PTF(3) contains the information after path partition. PTF combined with the initial path table can get the partitioned path. As shown in Figure 9e, the execution time \(t_{1}-t_{4}\) of the nodes in iteration 2 are 9, 11, 16, and 22, respectively, so we can get the initial path table. The element \"0\" in PTF(3) means that the path does not pass through the node corresponding to the element, and the element \"1\" means that the path passes through the node corresponding to the element. When \(n=2\), the default path of \(x_{i}\) in the initial path table is \(\{t_{1},t_{3},t_{4}\}\), which is 9, 16, 22. However, after path partition, the first column of PTF(3) is {0, 0, 1}, which means that \(x_{i}\) does not pass through nodes 9 and 16, but only passes through node 22. Therefore, the path of \(a_{8}\) is [22]. The paths corresponding to data \(b_{0}-b_{2}\) are similar. Figure 8: The generation mechanism of the path generation matrix. Figure 9: The example of path partition of iteration 2 in Figure 6. (**a–d**) the process of obtaining PTF(3); (**e**) PTF(3) combined with the initial path table to get the final path. A working example of BTPP hardware is given. To better understand the hardware working, we first give the overall situation of the calculation, as shown in Figure 10. Different from Figure 6, buffer 1 delays the input data by \(p\) clock cycles, so the execution time of all nodes is delayed by \(p\). In this example, the reduction operator is an adder with a 4-stage pipeline (\(p=4\)), and the tasks to be solved are \(\sum_{i=0}^{4}a_{i}\) and \(\sum_{i=0}^{3}b_{i}\). Figure 11 shows the hardware working details. Path table is generated at \(x_{i,j}\) and updated at \(dout\). At cycle 0, data \(a_{0}\) is input from \(din\). The signal \(din\_valid\) is 1, which means that \(a_{0}\) is valid data. Then, data \(a_{1}-a_{3}\) are input in sequence. At cycle 4, the signal \(set\_end\) becomes valid, indicating that the data \(a_{4}\) input at the current moment are the last data of the data set \(A\). After four clock cycles are delayed by buffer 1, data \(a_{0}\) appear at \(x_{i,j}\), and its path table has been generated. In the path table, the \"5\" in \(\{5,12,18\}\) and the first \"1\" in \(\{1,1,2\}\) represent that \(a_{0}\) is sent to the reduction operator as the first operand at cycle 5. Other data represent similar meanings. The value of TNI is 1, which means that the calculation result of cycle 18 will be sent to the next iteration for calculation. Data \(a_{0}\) are not consumed at the current moment. Since it will be sent to the reduction operator as the first operand, there is no need to store it in the buffer. At cycle 5, \(x_{i,j}\) is \(a_{1}\). According to its path table, it is sent to the reduction operator as the second operand at this time. Therefore, \(op2\) is \(a_{1}\). The signal \(x_{i,j-1}\) is \(a_{0}\), which meets the demand of \(op1\) at the current moment, so \(op1\) is \(a_{0}\). The situation is similar for cycles 6-7. At cycle 8, \(x_{i,j}\) is \(a_{4}\), and it is not consumed at the current moment. It is the second operand of the node 22, so it is stored in buffer 4. At cycle 9, \(x_{i,j}\) is \(b_{0}\). According to the path table, \(b_{0}\) is sent to \(op2\). The signal \(x_{i,j-1}\) at this time does not meet the requirements of \(op1\), so \(op1\) is 0. The signal \(dout\) outputs partial result \(a_{0}+a_{1}\), and its path table is \(\{12,18\}\) and \(\{1,2\}\). From the path table of \(a_{0}\), \(a_{1}\) and \(a_{0}+a_{1}\), it is easy to see that \(a_{0}+a_{1}\) is the calculation result of \(a_{0}\) and \(a_{1}\). Since \(a_{0}+a_{1}\) needs to be consumed as the first operand at cycle 12, it is stored in buffer 2.