# A Novel Reduction Circuit Based on Binary Tree Path Partition on FPGAs
## 5 Hardware Design
For these \((\log_{2}p+2)\times\lceil p/2\rceil\) nodes, their operand 1 is stored in buffer 4, and operand 2 is stored in buffer 2 or buffer 3. The sizes of buffers are \((\log_{2}p+2)\times\lceil p/2\rceil\), which means that each node has a dedicated storage unit. When the execution of the node is completed, the storage unit will be released. For example, in Figure 5c, after iteration 0 is executed, the storage units it occupied are released and used to store the data of iteration 4. Therefore, when a node is executed, the module \(buffer\_management\) generates the address to read the dedicated storage unit of the node. The most significant bits of the data in buffers 5-7 are valid bits. According to these valid bits, the circuit can determine whether the data in buffers 2-4 are valid. After reading the data, the circuit writes \"0\" to the valid bit in buffer 5-7, which means that the data are invalid. When writing data, module \(buffer\_management\) generates a write enable signal and an address to write data to the dedicated storage unit of the node. Path partition is the core of the BTPP. Complicated hardware circuits will cause a large delay, leading to performance degradation. If the configuration codes corresponding to all possible situations of the path partition are stored in the memory, a large amount of memory resources will be consumed. Therefore, we need to use simple hardware to achieve path partition. In BTPP hardware, the module \(path\_table\_gen\) is used to achieve path partition and generate path tables. It is mainly implemented by the initial path table, path generation matrix (PGM), and path table flag (PTF). Figure 8 shows an example of obtaining the path generation matrix. We rewrite the initial path table of iteration \(k\) in Figure 5e into the form in Figure 8. For operations, when the second operand comes, we can confirm its execution. Therefore, we use this feature to determine the priority of nodes in the iteration. When \(x_{i}\) is input, by judging whether it needs to be added to the result of the previous iteration, it can be determined whether the node at the time \(t_{4}\) needs to be passed. In the same way, when \(x_{i+1},x_{i+2},x_{i+3}\) are input, it can be determined whether it is necessary to pass the nodes at \(t_{1},t_{3}\), and \(t_{2}\). This essentially reorders the nodes in the initial path table. We use the element \"1\" to indicate that the path passes through the node corresponding to the element, and the element \"0\" indicates that it does not pass, so we get the PGM. The first column in the PGM stores the address of the initial path table. For example, the data in the second row of the initial path table are \([t_{4},t_{4},t_{4},t_{4}]\), which is stored in the 0 th row of the PGM together with the location address to get the data \([2,t_{4},t_{4},t_{4},t_{4}]\). Use \"1\" to represent the node passing \(t_{4}\), so the 0 th row of PGM is \([2,1,1,1,1]\). It can be seen from the PGM that the nodes that the data \(x_{i}-x_{i+3}\) pass have not changed. Since the execution time of nodes in different iterations is different, this method can reduce the amount of data storage. The PGM can be reused in each iteration. Figure 9 gives an example of the path partition of iteration 2 in Figure 6. According to the information in Figure 5e, when \(n=2\), the data input time of iteration 2 is 8-11. The data corresponding to the data \(x_{i}-x_{i+3}\) are respectively \(a_{8}-b_{2}\), so \(x_{i}\) belongs to set \(A\), and \(x_{i+1}-x_{i+3}\) belongs to set \(B\). Path partition is obtained through multiple OR operations on elements in PGM and PTF. In an iteration, the elements belonging to the same set in the PGM and PTF will perform the OR operation. All elements of the PTF are zero in the initial situation, and \(mod\_cycle\) is the current cycle modulo \(p\). As shown in Figure 9a, when the cycle is 8, \(mod\_cycle\) is 0. At this time, columns corresponding to only \(x_{i}\) in the PGM and initial PTF perform an OR operation to obtain PTF(0).