Analysis of worst-case backlog bounds for Networks-on-Chip

In networks-on-chips (NoCs), analyzing the worst-case backlog bounds of routers is very important to identify network congestions and improve network performance. In this paper, we propose a method called DiGB (DIrected-contention-Graph-based Backlog bound derivation) to analyze worst-case backlog bounds. For primitive scenarios, we propose analytical models for backlog bound derivation. For complex scenarios, we first construct a directed-contention-graph (DCG) to analyze the relationships among traffic flows. Then, we use the Breadth-First-Search strategy to traverse the DCG so that complex scenarios can be divided into primitive scenarios. Finally we compute the worst-case backlog bounds of each router. To illustrate this method, we present the derivation of closed-form formulas to compute the worst-case backlog bounds under all-to-one gather communication. The experimental results show that our method can achieve correct and tight worst-case backlog bounds.