# A Low-Latency Fair-Arbiter Architecture for Network-on-Chip Switches
## 3 Fair Switch Arbiter
### Fair Round-Robin Arbiter Scheme  
It is essential that an arbiter provides dynamic, fair arbitration. Consider an n-input packet switch; herein, each input submits a one-bit request signal \(r_{i}\) (\(0\leq i\leq N-1\)) to every output, which indicates whether its packet is destined for the output. Each output arbiter collects all request signals and computes binary grant outputs \(g_{i}\) (\(0\leq i\leq N-1\)), among which one input is granted to transmit packets. Assuming that in the previous arbitration cycle \(g_{j}=1\)(if there is no \(g_{j}=1\), \(j=N\); if \(g_{0}=1\), \(j=N\)), and \(g_{i}\)s are set as follows. \[g_{i}= \begin{cases}1,&i=max\ \{(j-a)\mid r_{(j-a)}=1,\ (0<a\leq j)\}.\\ 0,&otherwise.\end{cases}  \tag{1}\]  
An arbiter guarantees fairness among masters by changing the priority of all the requests. Initially, all ports obtain arbitration according to a certain priority order; if any input obtains the grant signal, assumed to be \(r_{i}\), the priority vector is pointed to \(r_{k}\) next to \(r_{i}\). Figure 4: Round-robin 32-node binary tree structure. To search for the maximum \(j\), we encoded different states, as shown in Table 1. Different states have different priorities to ensure the request that has the highest priority can be met. Each state performs as a fixed priority arbiter (FPA) and priority vector as the condition for jumping among states. Contrary to the SA, we used a loop state machine with feedback, which can provide fair arbitration. As shown in Figure 5b, after a request is granted in each arbitration cycle, the state jumps to ensure that the highest priority is passed to the next request and the priority of the granted request is adjusted to the lowest point. Figure 6 shows the structure of the leaf nodes of the arbiter. The proposed leaf node consists of a D flip-flop, four priority logic blocks, a MUX and a lock logic block. Four priority logic blocks correspond to the different states in Table 1. This will result in up to four different grant outcomes to choose from. The proposed architecture uses the previous grant feedback as the priority signal to instruct the loop state machine jumps. As shown in Table 1, each bit of the priority signal corresponds to a different output for a different priority case. Furthermore, we proposed a lock signal as an indication for the leaf node to complete a round of arbitration. When all requests from the leaf node are authorized, the lock signal will be set. As shown in Figure 6b, when the lock signal is set, the req signal passed to the upper layer is blocked. The definition of the lock logic is as follows. \[lock=g_{0}+g_{1}\overline{r_{0}}+\ g_{2}\overline{r_{1}}\cdot\overline{r_{0 }}+\ g_{3}\overline{r_{2}}\cdot\overline{r_{1}}\cdot\overline{r_{0}} \tag{2}\]  
\[up\_req=\overline{lock}\cdot any\_req \tag{3}\]  
For example, in the initialization phase, the result of the first priority logic block will be taken from the MUX. At this time, the state is 00, and the priority of four requests is \(req[3]>req[2]>req[1]>req[0]\). Supposing that only \(req[0]\) and \(req[2]\) want to be authorized, the token at this moment is four (\(grant=4\)b0100, which indicates \(req[2]\) gets authorized) because the \(req[2]\) has higher priority. In the next arbitration cycle, the grant changes the priority signal to 4'b0100, and the state is jumped to 10. Thus, the arbiter processes request signals following the execution order of the third priority logic block in the current clock slot; \(req[1]\) indicates the highest priority. Considering the connection of the requests, because neither \(req[1]\) nor \(req[3]\) makes a request, \(req[0]\) has the highest priority and \(req[2]\) has the next highest priority. The \(lock\) signal is set when port 0 gets authorized; at this time the priority signal and up\_req signal are not updated.