# A Low-Latency Fair-Arbiter Architecture for Network-on-Chip Switches
## 3 Fair Switch Arbiter
### Round-Robin Arbiter Tree  
The FSA features an \(O(log_{4}N)\)-level tree structure. Considering that the number of ports is not a power of four, the level of the tree shown is as follows:  
\[l=\lfloor log_{4}N+0.5\rfloor \tag{4}\]  
The tree structure is a decentralized framework that may disintegrate jobs into small chunks and distribute them to different nodes for completion. Each node in the tree structure is subdivided into leaf nodes, internal nodes and root nodes. Each node has the ability to act independently as an arbiter. The leaf node is in charge of replying to the node's request while seeking authorization from the upper layer. The requests from the leaf nodes are grouped by the internal node, and the requests from the corresponding lower-level nodes are handled by the root node. The structure of the leaf node is shown in Figure 6, and the internal and root nodes are shown in Figure 7. If \(\lfloor log_{2}N\rfloor\) is odd, the root node uses the root2 node.  
The FSA structure is shown in Figure 4; all nodes are connected using \(up\_req\) and \(ack\) signals. The leaf node receives a four-bit _request_ signal in each arbitration cycle, selects the authorization signal based on the priority signal and creates the \(up\_req\) signal to request authorization from the upper layer. The _request_ signal is forwarded to the root node after passing through a gathering of internal nodes. Thereafter, the root node acknowledges the request and transmits the information to the lower-level node through the \(ack\) signal.  
According to the analysis in Section 2, the tree structure is unfair for nonuniformly distributed requests, as it utilizes a generic priority update mechanism. To address this  
Figure 6: Block diagram of the FSA’s leaf node. (**a**) Leaf node. (**b**) Lock logic module.  
unfairness, we suggested that every input of leaf nodes should be serviced once before the priority vector of the higher-level node is updated. Therefore, the arbitration of the internal node and root node should ensure that the priority is not updated until the lower-level node completes its arbitration.  
Based on the new priority strategy, first, the node granted all requests. As shown in Equation (2), the _lock_ signal indicates the completion of the node arbitration. We filtered out the upward request signal through the _lock_ signal, which can indirectly ensure the update of the priority of the upper node. The proposed arbiter modified the _up_req_ signal as in Equation (3), to ensure that higher-level nodes could use the absolutely fair round-robin arbiter [26] as follows.  
\[g_{i}=\begin{cases}1,&i=max\ \{j\ |\ r_{j}=1,\ (0\leq j\leq N-1)\}.\\ 0,&otherwise\end{cases} \tag{5}\]  
As shown in Figure 7, to achieve a shorter delay, we adopted the parallel prefix FPA [27] as the structure of the internal node and root node, which can obtain \(log_{2}N\) delay. By defining a prefix \(p_{i;j}\), we could express priority encoding as a prefix operation:  
\[p_{i;i}=\overline{r_{i}} \tag{6}\]  
\[p_{i;j}=p_{i;k}\cdot p_{k;j} \tag{7}\]  
\[g_{i}=r_{i}\cdot p_{i-1;0} \tag{8}\]  
The resulting signals of the parallel prefix FPA in the internal node have to be ANDed with the ack signal, which is from the higher level, to indicate whether the result is valid or not. The updated signal in the root node indicates that the arbitration is complete.