# A Low-Latency Fair-Arbiter Architecture for Network-on-Chip Switches
## 2 Related Works and Analyses  
In high-speed switching systems, the performance of the arbiter is critical. In computer network packet switching, studies have been conducted on the iterative round-robin algorithm (iSLIP) [15] and dual round-robin matching (DRRM) algorithm [16]. Moreover, [PERSON] and [PERSON] proposed two new programmable priority encoders (PPE) [17; 18]. PPE is complicated for a simple round-robin arbiter; additionally, it is the centralized rotating-priority-pointer design.  
With the expansion of the network exchange scale, a centralized arbitration structure becomes complex, which is detrimental to the implementation. To obtain better scalability, the tree structure has been proposed. [PERSON] et al. proposed the arbitration algorithm named the ping-pong arbiter (PPA) [19], which features an \(O(log_{2}N)\)-level tree structure. PPA has good scalability and low latency, but its fairness cannot be satisfied under unbalanced traffic [20]. As shown in Figure 2, when the number of input requests is less than \(N\), although the root node permanently grants evenly, leaf nodes and intermediate nodes  
Figure 1: Network-on-chip switch architecture.  
will obtain unbalanced grants owing to unbalanced input. Consequently, this results in different grant probabilities between different requests.  
Another arbiter design using the similar research algorithm of \"ping-pong\", called the switch arbiter (SA), was proposed in [21]. It is constructed using the 4-input instead of the 2-input arbiter block. Theoretically, it can obtain a lower delay than PPA [22]. However, in some special cases, the priority updates step-by-step results in an unfair situation. As shown in Figure 3, the SA becomes unfair with non-uniformly distributed requests. For example, when both channels 1 and 3 have data packets entering, supposing that the initial priority is \(r_{1}>r_{2}>r_{3}>r_{0}\), channel 1 will be authorized first. Thereafter, the channel priority order will be \(r_{2}>r_{3}>r_{0}>r_{1}\), and channel 3 will be authorized at this time. Subsequently, the channel priority order becomes \(r_{3}>r_{0}>r_{1}>r_{2}\). At this time, channel 3 is still authorized, which means unfairness occurs.  
In addition, [PERSON] and [PERSON] provided two main designs in the form of a parallel round-robin arbiter (PRRA) and an improved PRRA (IPRRA) [23]. Based on their work, the PRRA and IPRRA provide round-robin fairness for input conditions, whereas the IPRRA is expected to reduce timing delay over the PRRA. PRRA and IPRRA consist of \(log_{2}(n)+1\) levels of the binary tree. The lowest level nodes of the binary tree are called leaf nodes, which are connected in series by a priority pointer. The highest node is called the root node,  
Figure 3: Unfair example of an SA cell.  
Figure 2: Unfair example of PPA.  
and the rest of the nodes are called intermediate nodes. Although PRRA and IPRRA can provide fair arbitration, it significantly increases path delay.  
In order to reduce the critical path delay (CPD) [24] of the arbiter, a gate-level circuit was proposed named ping-lock arbiter (PLA) [25]. This is also an architecture based on the \"ping-pong\" search algorithm. It improves the PPA structure to provide lower latency. Meanwhile, in order to solve the unfairness caused by the \"ping-pong\" algorithm, a lock structure is proposed to ensure the fairness of the tree structure. This lock structure exists at every node, which will increase the PLA's critical path delay and utilization.