Performance Analysis of Priority-Aware NoCs with
Deflection Routing under Traffic Congestion

In priority-aware NoCs, the packets already in the network have higher priority than the packets waiting in the egress queues of the sources. Assume that Node 2 in Figure 2 sends a packet to Node 12 following Y-X routing (highlighted by red arrows). Suppose that a packet in the egress queue of Node 6 collides with this packet. The packet from Node 2 to Node 12 will take precedence since the packets already in the NoC have higher priority. Hence, packets experience a queuing delay at the egress queues but have predictable latency until they reach the destination or turning point (Node 10 in Figure 2). Then, it competes with the packets already in the corresponding row. That is, the path from the source (Node 2) to the destination (Node 12) can be considered as two segments, which consist of a queuing delay followed by a predictable latency.

Deflection in priority-aware NoCs happens when the ingress queue at the turning point (Node 10) or final destination (Node 12) become full. This can happen if the receiving node, such as a cache controller, cannot process the packets fast enough. The probability of observing a full queue increases with smaller queues (needed to save area) and heavy traffic load from the cores. If the packet is deflected at the destination node, it circulates within the same row, as shown in Figure 2. Consequently, a combination of regular and deflected traffic can load the corresponding row and pressure the ingress queue at the turning point (Node 10). This, in turn, can lead to deflection on the column and propagates the congestion towards the source. Finally, if a packet is deflected more than a specific number of times, it reserves a slot in the ingress queue. This bounds the maximum number of deflections and avoids livelock.

Our goal is to construct an accurate analytical model to compute the end-to-end latency for priority-aware NoCs with deflection routing. The proposed approach can be used to accelerate full system simulations and also to perform design space exploration. We assume that the parameters of the GGeo distribution of the input traffic to the NoC ($\lambda,C^{A}$) are known from the knowledge of the application. The proposed model uses the deflection probability ($p_{d}$) as the second major input, in contrast to existing techniques that ignore deflection. Its range is found from architecture simulations as a function of the NoC architecture (topology, number of processors, and buffer sizes). Its analytical modeling is left for future work. The proposed analytical model utilizes the distribution of the input traffic to the NoC ($\lambda,C^{A}$) and the deflection probability ($p_{d}$) to compute the average end-to-end latency as a sum of four components: (1) Queuing delay at the source, (2) the latency from the source router to the junction router, (3) queuing delay at the junction router, and (4) the latency from the junction router to the destination. Note that all these components account for deflection, and it is challenging to compute them, especially under high traffic load.

Figure 3(a) shows an example of a single class input traffic and egress queue that inject traffic to a network with deflection routing. The input packets are buffered in the egress queue $Q_{i}$ (analogous to the packets stored in the egress queue of Node 2 in Figure 2). We denote the traffic of $Q_{i}$ as class-$i$, which is modeled using GGeo distribution with two parameters ($\lambda_{i},C_{i}^{A}$). The packets in $Q_{i}$ are dispatched to a priority arbiter and assigned a low priority, marked with . In contrast, the packets already in the network have a high priority, which are routed to the port marked with . The packet traverses a certain number of hops (similar to the latency from the source router to the junction router in Figure 2) and reaches the destination. Since the number of hops is constant for a particular traffic class, we omit these details in Figure 3(a) for simplicity. If the ingress queue at the destination is full (with probability $p_{d_{i}}$), the packet is deflected back into the network. Otherwise, it is consumed at the destination (with probability $1-p_{d_{i}}$). Deflected packets travel through the NoC (within the column or row as illustrated in Figure 2) and pass through the source router, but this time with higher priority. The profile of the deflected packets in the network is modeled by a buffer ($Q_{d}$) in Figure 3(a), since they remain in order and have a fixed latency from the destination to the original source. This process continues until the destination can consume the deflected packets.

Our goal is to compute the average waiting time $W_{i}$ in the source queue, i.e., components 1 and 3 of the end-to-end latency described in Section 3.2. To obtain $W_{i}$, we first need to derive the analytical expression for the rate of deflected packets of class-$i$ ($\lambda_{d_{i}}$) and the coefficient of variation of inter-arrival time of the deflected packets ($C_{d_{i}}^{A}$) as follows.

The input traffic to the egress queue, as well as the deflected traffic, may exhibit bursty behavior. Indeed, the deflected traffic distribution can be bursty because of the server-process effect and the priority interactions between the input traffic and the deflected traffic, even when the input traffic is not bursty. Therefore, we approximate the distribution of the deflected traffic via GGeo distribution. To compute the parameters of the GGeo traffic, we need to apply the principle of maximum entropy (ME) as shown in  (Kouvatsos, 1994). To obtain the modified service process of class-$i$, we first calculate the probability of no packets in $Q_{i}$ and in its corresponding server (i.e., $p_{Q_{i}}(0)$) using ME as,

where $\rho_{i}$ and $\rho_{d_{i}}$ denote the utilization of the respective servers, and $\overline{n}_{i}$ is the occupancy of class-$i$ in $Q_{i}$. Next, we apply Little’s law to compute the first order moment of modified service time ($\widehat{T}_{i}$) as:

Subsequently, we obtain the effective coefficient of variation $\widehat{C}_{i}^{S}$ as:

where $\widehat{\rho}_{i}=\lambda_{i}\widehat{T}_{i}$. We follow similar steps (Equation 3 – Equation 5) for the deflected traffic to obtain $\widehat{T}_{d_{i}}$ and $\widehat{C}_{d_{i}}^{S}$. With the modified service process, the coefficients of variation of inter-departure time of the packets in $Q_{d}$ (${C}_{d_{i}}^{D}$) and $Q_{i}$ (${C}_{i}^{D}$) are computed using the process merging method (Pujolle and Ai, 1986). Then, we find the coefficient of variation (${C}_{i}^{M}$) of the merged traffic from queues $Q_{d}$ and $Q_{i}$ as:

We note that ${C}_{i}^{M}$ is a function of the coefficient of variation of the inter-arrival time of deflected traffic $C_{d_{i}}^{A}$. Since part of this merged traffic is consumed at the sink, we apply the traffic splitting method from  (Pujolle and Ai, 1986) to approximate $C_{d_{i}}^{A}$ as:

Finally, we extend the priority-aware formulations in continuous time domain (Bolch et al., 2006) to discrete time domain to obtain the average waiting time of the packets in $Q_{d_{i}}$ and $Q_{i}$:

The analytical model for the system with a single class presented in Section 4.1 becomes intractable with a higher number of traffic classes. This section introduces a scalable approach based on the superposition principle that builds upon our canonical system used in Section 4.1.

Figure 4(a) shows an example with priority arbitration and $N$ egress queues, one for each traffic class. We note that this queuing system is a simplified representation of a real system. The packets routed to port  have higher priority than those routed to port  for $i<j$. The deflected traffic in the network is buffered in $Q_{d}$, which has the highest priority in the queuing system. The primary goal is to model the queuing time of the packets of each traffic class. Modeling the coefficient of variations of the deflected traffic becomes harder since deflected packets interact with all traffic classes rather than a single class. These interactions complicate the analytical expressions significantly.

Priority arbitration enables us to sort the queues in the order at which the packets are served. The queue of the deflected packets has the highest priority, while the rest are ordered with respect to their indices. Due to this inherent order between the priority classes, their impact on the deflected traffic distribution can be approximated as being independent of each other. This property enables us to decompose the queuing system into multiple subsystems and model each subsystem separately, as illustrated in Figure 4(b). Then, we apply the principle of superposition to obtain the parameters of the GGeo distribution of the deflected traffic. Note that each of these subsystems is identical to the canonical system analyzed in Section 4.1. Hence, we first compute $\lambda_{d_{i}}$ and $C_{d_{i}}^{A}$ of each subsystem-$i$ following the procedure described in Section 4.1. Subsequently, we apply the superposition principle to $\lambda_{d_{i}}$ and $C_{d_{i}}^{A}$ for $i=1\ldots N$ to obtain the GGeo distribution parameters of the deflected traffic ($\lambda_{d},C_{d}^{A}$).

In general, we obtain the GGeo distribution parameters of the deflected traffic corresponding to class-$i$ by setting all traffic classes to zero expect class-$i$, ($\lambda_{j}=0$, $j=1\ldots N,j\neq i$). The values of $\lambda_{d_{i}}$ and $C_{d_{i}}^{A}$ can be expressed as:

Subsequently, we apply the principle of superposition to obtain the distribution parameters of $Q_{d}$ as shown in Figure 4(c). First, we compute $\lambda_{d}$ by adding all $\lambda_{d_{i}}$ as:

The value of $C_{d}^{A}$ is approximated by applying the superposition-based traffic merging process (Pujolle and Ai, 1986) for each $C_{d_{i}}^{A}$, as shown below:

Next, we use these distribution parameters ($\lambda_{d},C_{d}^{A}$) of the deflected packets to calculate the waiting time of the traffic classes in the system. The formulation of the priority-aware queuing system is applied to obtain the waiting time of each traffic class-$i$ ($W_{i}$) (Bertsekas et al., 1992):

Figure 5 shows the average latency comparison between the proposed analytical model and simulation for the system in Figure 4. In this setup, we assume the number of classes is 5 ($N=5$), $p_{d}=0.3$, and input traffic distribution is geometric. The results show that the analytical model performs well against the simulation, with only 4% error on average. In contrast, the analytical model from (Kiasari et al., 2013) highly overestimates the latency as it does not consider multiple traffic classes. The performance model of the priority-aware NoC in (Mandal et al., 2019) accounts for multiple traffic classes, but it does not model deflection. Hence, it severely underestimates the average latency.

One of the key components of the proposed analytical model is estimating the average number of deflected packets. This section evaluates the accuracy of this estimation compared to simulation with a 6$\times$6 mesh. To perform evaluations under heavy load, we set the deflection probability at each junction and sink to $p_{d}=0.3$ and injection rates at each source to 0.33 packets/cycle/source, which are relatively large values seen in actual systems. We first run cycle-accurate simulations to obtain the average number of deflected packets at each row and column of the mesh. Then, the analytical model estimates the same quantities for the 6$\times$6 mesh. Figure 6 shows the estimation accuracy for all rows and columns. The average estimation accuracy across all rows and columns is 96% and the worst-case accuracy is 92%. Overall, this evaluation shows that the proposed model accurately estimates the average number of deflected packets.

This section evaluates the accuracy of our latency estimation technique when the sources inject packets following a geometric traffic distribution. We note that our technique can also handle bursty traffic, which is significantly harder. However, we start with this assumption to make a fair comparison to two state-of-the-art techniques from the literature (Kiasari et al., 2013; Mandal et al., 2019). The model presented in (Kiasari et al., 2013) does not incorporate multiple traffic classes and deflection routing. On the other hand, the model presented in (Mandal et al., 2019) considers multiple traffic classes but does not consider bursty traffic and deflection routing.

The evaluations are performed first on the server-like 6$\times$6 mesh for deflection probabilities $p_{d}=$ 0.1 and $p_{d}=$ 0.3 while sweeping the packet injection rates. Figure 7(a) and Figure 7(b) show that the proposed technique follows the simulation results closely for all injections. More specifically, the proposed analytical model has only 7% and 6% percentage error on average for deflection probabilities of 0.1 and 0.3, respectively. In sharp contrast, the analytical model proposed in (Kiasari et al., 2013) significantly overestimates the latency starting with moderate injection rates, since it does not consider multiple traffic classes. Its performance degrades even further with larger deflection probability, as depicted in Figure 7(b). We note that it also slightly underestimates the latency at low injection rates since it ignores deflection. Unlike this approach, the technique presented in (Mandal et al., 2019) considers multiple traffic classes in the same queue, but it ignores deflected packets. Consequently, it severely underestimates the latency impact of deflection, as shown in Figure 7.

We repeated the same evaluation on a 6$\times$1 priority-aware ring NoC which follows a high-end industrial quad-core CPU with an integrated GPU and memory-controller (Jeffers et al., 2016). The average error between the proposed analytical model and simulations are 7% and 4% for deflection probabilities of 0.1 and 0.3, respectively. In contrast, the model presented in (Kiasari et al., 2013) underestimates the latency at low injection rates and significantly overestimates it under high traffic load similar to the 6$\times$6 results in Figure 7. Similarly, the analytical model presented in (Mandal et al., 2019) severely underestimates the average latency. It leads to an average 43% error with respect to simulation. The plots of these results are not included for space considerations since they closely follow the results in Figure 7.

Since real applications exhibit burstiness, it is crucial to perform accurate analytical modeling under bursty traffic. Therefore, this section presents the comparison of our proposed analytical model with respect to simulation under bursty traffic. For an extensive and thorough validation, we sweep the packet injection rate ($\lambda$), probability of burstiness ($p_{br}$), and deflection probability ($p_{d}$). The injection rates cover a wide range to capture various traffic congestion scenarios in the network. Likewise, we report evaluation results for two different burstiness ($p_{br}=$ {0.2,0.6}), and three different deflection probabilities ($p_{d}=$ {0.1,0.2,0.3}). The coefficient of variation for the input traffic ($C_{A}$), the final input to the model, is then computed as a function of $p_{br}$ and $\lambda$ (Kouvatsos and Luker, 1984). We simulate the 6$\times$6 mesh and 6$\times$1 ring NoCs using their cycle-accurate models for all input parameter values mentioned above. Then, we estimate the average packet latencies using the proposed technique, as well as the most relevant prior work (Kiasari et al., 2013; Mandal et al., 2019).

The estimation error of all three performance analysis techniques is reported in Table 2 for all input parameters. The mean and median estimation errors of our proposed technique are 9.3% and 9.5%, respectively. Furthermore, we do not observe more than 14% error even with relatively higher traffic load, probability of deflection, and burstiness than seen in real applications (presented in the following section). In strong contrast, the analytical models proposed in (Kiasari et al., 2013) severely overestimate the latency similar to the results presented in Section 5.2. The estimation error is more than 100% for most cases since the impact of multiple traffic classes and deflected packet become more significant under these challenging scenarios. Similarly, the model proposed in (Mandal et al., 2019) underestimates the latency because it does not model bursty traffic.

The right-hand side of Table 2 summarizes the estimation errors obtained on the 6$\times$1 ring NoC that follows high-end client systems. In most cases, the error with the proposed analytical model is within 10% of simulation, and the error is as low as 1%. With $p_{d}=0.1$, $p_{br}=0.6$ and $\lambda=0.4$, the error is 14%, which is acceptable, considering that the network is severely congested. In contrast, the analytical models proposed in (Kiasari et al., 2013) overestimate the latency, whereas the models in (Mandal et al., 2019) underestimate the latency which conforms the results with geometric traffic, as in the 6$\times$6 mesh results.

In addition to the synthetic traffic, the proposed analytical model is evaluated with applications from SPEC CPU®2006 (Henning, 2006), SPEC CPU®2017 benchmark suites (Bucek et al., 2018), and the SYSmark®2014 application ((BAPCo), [n.d.]). Specifically, the evaluation includes SYSmark14, gcc, bwaves, mcf, GemsFDTD, OMNeT++, Xalan, and perlbench applications. The chosen applications represent a variety of injection rates for each source in the NoC and different levels of burstiness. Each application is profiled offline to find the input traffic parameters. Of note, the probability of burstiness for these applications ranges from $p_{b}=$ 0.25 to $p_{b}=$ 0.55, which is aligned with the evaluations in Section 5.3.

The benchmark applications are executed on both 6$\times$6 mesh and 6$\times$1 ring architectures. The comparison of average latency between simulation and proposed analytical model for the 6$\times$6 mesh is shown in Figure 8. The proposed model follows the simulation results very closely for deflection probability $p_{d}=$ 0.1 and $p_{d}=$ 0.3, as shown in Figure 8(a) and Figure 8(b), respectively. These plots show the average packet latencies normalized to the smallest latency from the 6$\times$1 ring simulations due to the confidentiality of the results. On average, the proposed analytical model achieves less than 5% modeling error. In contrast, the analytical models which do not consider deflection routing (Kiasari et al., 2013; Mandal et al., 2019) underestimate the latency, since the injection rates of these applications are in the range of 0.02–0.1 flits/cycle/source (low injection region).

We observe similar results for the 6$\times$1 ring NoC. The average estimation error of our proposed technique is less than 8% for all applications. In contrast, the prior techniques underestimate the latency by more than 2$\times$ since they ignore deflected packets, and the average traffic loads are small. In conclusion, the proposed technique outperforms state-of-the-art for real applications and a wide range of synthetic traffic inputs.

Finally, we evaluate the scalability of the proposed technique for larger NoCs. We note that accuracy results for larger NoCs are not available since they do not have detailed cycle-accurate simulation models. We implemented the analytical model in C. Figure 9 shows that the analysis completes in the order of seconds for up to 16$\times$16 mesh. In comparison, cycle-accurate simulations take hours with this size, even considering linear scaling. When we scale the mesh size aggressively to 16$\times$16, the analysis completes in about 5 seconds, which is orders of magnitude faster than cycle-accurate simulations of NoCs of this size.