# A Novel Reduction Circuit Based on Binary Tree Path Partition on FPGAs
## 4 Binary Tree Path Partition
### The Proposed Reduction Method  
Algorithms 1 and 2 show the pseudo-code of BTPP. BTPP is divided into two parts. The first part whose input is the pipeline stages \(p\) of the reduction operator is to obtain the initial path table that contains information such as data flow and initial scheduling. Figure 3: The design idea of BTPP. (**a**) structured calculation pattern combining binary tree and adder chain; (**b**) apply path partition to improve system performance; (**c**) BTPP hardware design: use only one reduction operator. Then, the initial path table is partitioned according to the input elements. The pipeline stages \(p\) of the reduction circuit needs to satisfy \(p\geq 2\). When \(p=1\), BTPP becomes serial execution, similar to Figure 1(a), and BTPP is not required at this time. When \(p\geq 2\), the method of Figure 1(a) fails to take advantage of the pipeline, which is a problem that BTPP needs to solve. Our main contribution is embodied in Algorithm 2, which is the core of the entire BTPP. ```
0: pipeline stages \(p\) of the reduction operator
0: initial path table
1. create a binary tree of \(p\) input;
2. add a node to add the result of the binary tree to the result of the last iteration;
3. get the data flow graph \(G=(N,E)\);
4. limiting the initial interval to \(p\) and the number of adders to 1, perform software pipeline on \(G\) to obtain scheduling scheme \(S\);
5. get the initial path table according to \(G\) and \(S\);
6. return initial path table. ```  
**Algorithm 2** BTPP Part 2: Path partition  
```
0: path table
1. **while** there is element \(x_{i}\) input do
2. if\(x_{i}\) is the last element in the data set \(X\)then
3. /* for paths belonging to \(X\) in iteration \(n\): */
4. if do not need to be added to the results of the previous iteration then
5. delete the node used for addition between iterations;
6. end if
7. delete all nodes in paths belonging to data set \(X\) that only use operand 1;
8. /* for paths that do not belong to \(X\) in iteration \(n\): */
9. delete the nodes occupied by \(X\);
10. return path table. 11. end if
12. end while
```  
**Algorithm 3** BTPP Part 1: Binary tree path initialization  
The reduction task in Figure 0(a) has \(m\) data sets, and the \(i\)-th data set contains \(n[i]\) elements. For this reduction task, Figure 4 shows the workflow executed on different hardware. Figure 3(a) is the workflow executed on the processor. First, the reduction task is statically compiled by the compiler to obtain instructions. Then, these instructions are sent to the processor. Figure 3(b) is the workflow of the reduction task executed on the BTPP hardware. BTPP part 1 is used to generate the initial path table. The initial path table is only related to the pipeline stages \(p\) of the reduction operator, and it does not contain any information about the reduction task. In other words, if the circuit directly uses the initial path table to process the reduction task, it will get the wrong result. The information obtained after the path partition of the reduction task is included in the path table, which is generated by BTPP part 2. These path tables are sent to the controller and data-path for correct calculation. Figure 3(a) already knows the number of data sets and the number of elements in each data set at the compilation phase. Unlike Figure 3(a), the initial path table generated during the compilation phase does not contain any information related to the reduction task. The reduction task is to input data into the BTPP hardware during the hardware execution phase, and then BTPP part 2 performs path partition on the hardware in real time to obtain the path table. In other words, the BTPP hardware neither knows how many data sets are input nor how many elements each data set contains before the hardware execution phase. If the reduction circuit is designed according to the process shown in Figure 4a, the circuit can only be used for the specified number of data sets and elements.