# A Novel Reduction Circuit Based on Binary Tree Path Partition on FPGAs
## 4 Binary Tree Path Partition
### The Proposed Reduction Method
When the number of data sets is changed or the number of elements in each data set is changed, the scheme in Figure 4a needs to be recompiled to generate new instructions. However, BTPP does not have this problem because it can handle any number of data sets, and each data set can have any number of elements. Only when the pipeline stages \(p\) of the reduction operator is changed does BTPP part 1 need to be re-executed to generate a new initial path table. Figure 5 is an example of Algorithm 1, where the adder pipeline stage \(p=4\). First, we construct a binary tree with \(p\) input, and then add an operation to add the results of the previous iteration, as shown in Figure 5a,b. Then, we execute the software pipeline based on Figure 5b, and the result is shown in Figure 5c. Its initial interval is \(p\), and only one addition operation is performed per clock cycle. Due to the use of a software pipeline, the \(p\) addition operations in one iteration can be implemented by an adder with a \(p\)-stage pipeline in a time-division multiplexing manner. We mark the clock cycle of each addition operation in the data flow graph to get Figure 5d. After using the software pipeline, the execution time of nodes in different iterations shows a certain regularity, so we only need to analyze a single iteration. As shown in Figure 5e, the input data of iteration \(k\) is \(x_{i}\)-\(x_{i+3}\), and they start to be input at time \(k\times p\), and one piece of data are input every clock cycle. The execution time of each node in iteration \(k\) can also be obtained by \(k\) and \(p\). Thus, we get the initial path table of iteration \(k\). For data \(x_{i}\), the nodes it passes are \(t_{1}\to t_{3}\to t_{4}\). The nodes that the data \(x_{i+1}\) pass through is the same as the data \(x_{i}\), which is also \(t_{1}\to t_{3}\to t_{4}\). However, the situation of node \(t_{1}\) is different from that of nodes \(t_{3}\) and \(t_{4}\). For node \(t_{1}\), \(x_{i}\) is used as the first operand input, and \(x_{i+1}\) is used as the second operand input. For nodes \(t_{3}\) and \(t_{4}\), \(x_{i}\) and \(x_{i+1}\) go through the same operand. To further distinguish the path of each data, we added the operand information of each node in the initial path table. Since an addition operation requires two operands, we use \"1\" to represent the data as the first operand of the node and use \"2\" to represent the data as the second operand of the node. The path of the data \(x_{i+2}\) and \(x_{i+3}\) is similar to that of \(x_{i}\) and \(x_{i+1}\). TNI (to next iteration) in the path table is used to indicate whether the result produced at the end of the data path is a partial result or the final result. For example, for \(x_{i}\), its path ends at node \(t_{4}\). If TNI is 1, it means that the result produced by node \(t_{4}\) is a partial result, and it needs to be sent to the next iteration. Otherwise, the result produced by node \(t_{4}\) is the final result. In the initial  
Figure 4: The workflow of the reduction task in Figure 1a on different hardware. (**a**) execute on the processor; (**b**) execute on BTPP hardware. path table, the default value of TNI is 1. Path partition is carried out on the basis of the initial path table. Figure 6 shows an example of path partition, in which the pipeline stage \(p\) of the adder is 4. For data set \(A=\{a_{0},a_{1},\cdots,a_{8}\}\), solving \(\sum_{i=0}^{8}a_{i}\) requires \(\lceil 9/4\rceil=3\) iterations to complete. For iteration 0, the input data are \(a_{0}\)-\(a_{3}\). Since none of the input data of iteration 0 are the last elements of the data set, iteration 0 does not require path partition. Paths of iteration 0 in the path table are the same as paths of iteration 0 in the initial path table. Since iteration 0 does not need to be added to the result of the previous iteration, the operand 1 of node 14 is 0. The output of iteration 0 is a partial result, not the final result, so the partial result needs to be sent to iteration 1. The situation of iteration 1 is similar to iteration 0.