Fault-tolerant and Congestion Balanced Routing Algorithm for 2D Mesh NoCs

Jiao Guan^1,2, Jueping Cai^1,*, Yequn Wang² and Jian Liu²

¹State Key Discipline Laboratory of Wide Band Gap Semiconductor Technology, School of Microelectronics, Xidian University, Xi’an, China

²Institute of Information and Navigation, Air Force Engineering University, Xi’an, China

E-mail: jpcai@mai.xidian.edu.cn

*Corresponding Author

Received 25 August 2020; Accepted 03 September 2020; Publication 22 December 2020

Abstract

With the number of cores and nodes in networks-on-chips (NoCs) growing, the node fault occurrence probability is increasing. Although the existing turn model can route packets around the fault area and avoid deadlocks, a large traffic load is generated in the non-rightmost column of the fault region. This paper presents a novel fault-tolerant and congestion balanced (FTCB) routing algorithm that chooses a lower load area as the optimal router path by calculating the maximum path channels to balance traffic load and avoid network congestion. Two methods are proposed to calculate path channels for the fault-free mesh and the fault mesh. The improved odd-even turn rule is introduced to calculate path channels for the fault-free mesh. To balance the network load, free buffer length information is added to path channel calculations, which reflects the global perception. For the non-fault region, we update path channels by using the back formulas from the destination node to the source node. In a fault region, the modified calculation rules of path channels and fault-location odd-even turn rules are given. Compared to the other two related works, the throughput of the FTCB algorithm is improved by 6.92% and 10.7%. Meanwhile, the traffic load of FTCB is decreased to some degree in whole mesh, which shows the FTCB routing algorithm can obviously improve network load balanced, saturation throughput and network latency.

Keywords: Network-on-Chip (NoC), fault-tolerant routing algorithm, path channels, free buffer length.

1 Introduction

With the development of chip technology and design level, increasing numbers of cores have become the main factor in enhancing parallel computing performance of NoC processors [1]. Meanwhile, reliability problems are becoming increasingly prominent under the dual influence of decreasing chip size and increasing chip complexity. The fault-tolerant routing algorithm is used to guarantee the normal work of the chip after the failure of a node or link happens. Fault-tolerant design methods mainly includes data redundancy [2], resource redundancy [3] and router redundancy. Fault-tolerant algorithms based on router redundancy have high reliability, low hardware cost and small area, and the transmitted packets can avoid the fault path by turning around the fault region.

Some existing fault-tolerant routing algorithms consider a single path selection rule, and as a consequence, the problem of local network congestion and imbalanced load happen frequently [4–12]. Some researchers have introduced local free buffer information as the evaluated condition, which cannot solve the imbalanced load problem [13–15]. Our research proposes a FTCB routing algorithm with global perception and a hybrid path selection strategy. The traffic load imbalances and network congestion around the faulty region of an NoC can be overcome by the FTCB routing algorithm. In addition, the average saturation throughput can be improved by the proposed routing algorithm. We use an improved odd-even turn mode in the global strategy to calculate the path channels so that multiple paths are available for avoiding deadlock without using a virtual channel. The calculation of path channels also considers current free buffer length (FBL) in a fault-free mesh. Based on these indexes, the optimal path between the source node and the destination node is chosen by the proposed algorithm. For the fault mesh, the back formula considering the current FBL can be used to update the path channels. Based on these indexes, the congestion in the fault ring can be balanced. To avoid stagnation problem in the fault area, fault-location odd-even turn rules are presented. Although the east-south (ES) turns in the even column happen, the round lacks a south border and cannot form a closed loop, and the rules can effectively avoid deadlock.

The remaining five sections of this paper are as follows. In Section 2, the related prior research on fault-tolerant algorithms and the turn model is reviewed. In Section 3, the path channel formula is presented. In Section 4, the FTCB router algorithm is provided. In Section 5, the evaluation and simulation are given. Finally, in Section 6, the conclusions of this paper are given.

2 Related Work

2.1 Turn Model Based Fault-tolerant Router

The turn model based fault-tolerant methods without virtual channels always apply the Y-X rule in non-fault areas first, and negative-first [4] rules or other special turn rules in other fault areas to avoid deadlocks. The model in Zhang [5] was used for a single node failure fault-tolerant routing algorithm without a virtual channel; this algorithm adopted a negative-first rule to avoid deadlock. Jiang [6] improved the model to tolerate single link failure based on Zhang [5]. Liu [7] divided the network into multiple groups of multiple fault nodes, where each group used Zhang’s [5] turn model to improve the tolerance of the Zhang’s [5] model. Fu [8] introduced zone defence routing combined with an advance forecast, which moves packets around the fault zone in advance. Wu [9] employed the convexity of faulty blocks [10] to transfer the packets and odd-even (OE) [11] rules to avoid deadlocks, and the convex fault-tolerant routing model with multi-fault was adopted in Wu’s algorithm. Xie [12] adopted a load-balance routing algorithm; the fault-tolerant odd-even rule was used to avoid deadlock, and a small amount of fault information was stored to reduce the load around the fault region.

2.2 Fault-tolerant Routing Algorithms

Fault-tolerant routing algorithms are divided into local routing algorithms and non-local routing algorithms according to the output path when the fault information range is considered.

AReF [16] is a typical local routing algorithm with adaptation and reconfigurability, which adopted the abacus turn model [17] to avoid deadlocks. However, the AReF can tolerate only one faulty node. MiCoF [18] adopted the shortest path data packets and handled the fault node as a link. Gradient [19] and a false rejection rate (FRR) [20] divided the network into 8 and 6 zones, respectively, and defined different levels for each output port in the target zone. The minimal and defect-resilient (MD) [21] algorithm used a fault distribution mechanism, which allows each node in the network to store data within the fault information of a 2-hop adjacency node and chooses the output path according to the fault information. Chaix [22] divided the network into two virtual networks, one north of the subsequent model to avoid deadlock, and another south of the subsequent model to avoid deadlock. The path-diversity-aware fault-tolerant routing rule is adopted in Chen’s algorithm [23]. The path channel information and buffer information are considered, but the algorithm does not provide a turn strategy around the fault node and cannot effectively solve network congestion.

3 Routing Method in Fault-free Model

3.1 Improved Odd-even Turn Model

The odd-even turn model [11, 12] is only used in the faulty region, which has low performance due to its limitations. In this mode, when packets arrive at the destination node (source node) located on the eastern border of the loop and the border of the loop is an even (odd) column, then the packet can be discarded.

We adopt an improved odd-even turn mode, which has different rules in the even column and odd column. In an even column, packets are forbidden to ES and north-west (NW) turns. In contrast, in an odd column, packets are forbidden to take south-west (SW) and east-north (EN) turns. As shown in Figure 1, “o” is the symbol for a routing node, “x” is the symbol for a forbidden turn and the dotted line is the symbol for routing path.

Figure 1 Improved odd-even turn model.

Although above improved model will reduce the adaptive degree, compared to the completely adaptive algorithm, this model can avoid deadlock. Chiu proved that if all fault rings are not formed in the rightmost column [11], the routing algorithm does not create deadlock. In our rules, ES turns and SW turns can not appear in the same column; similarly, NW turns and EN turns do not appear in the same column, so both counterclockwise and clockwise rightmost columns are divided to avoid deadlock. Based on above forbidden turn rules, two valuable conclusions are given in a fault mesh: a) The rightmost column cannot be generated closed circle path when transmitted packets arrive to northern border node, southern border node and western border node; b) The rightmost column cannot be generated when transmitted packets arrive to eastern border of circle path with the fault node.

3.2 Path Channels in the Improved Odd-even Turn Mode

The path channels indicate the adaptive degree of a router; that is, the number of paths from the current node to the destination node. The path channels is also the choice criterion of the optimal path in the adaptive router algorithm. If the value of the path channels are large, the path from the current node to the next node is optional. To improve the odd-even turn mode, because turn rules in the odd columns and even columns are different, the value of the path channel is discussed as follows. Assume ( $x_{s}, y_{s}$ ) is coordinates of the source node, $(x_{d}, y_{d})$ is coordinates of the destination node, $D_{x} = | x_{d} - x_{s} |$ is distance in x-direction and $D_{y} = | y_{d} - y_{s} |$ is distance in y-direction. In addition, Let $H = D_{x} / 2$ and $H^{'} = (D_{x} - 1) / 2$ , when node ( $x_{d}$ , $y_{d}$ ) is in the southeast of node ( $x_{s}$ , $y_{s}$ ), the path channels are expressed as

$P E$	$= {\begin{matrix} 0 & D_{x} = 1 and (x_{s}, y_{s}) is in the odd column \\ \frac{[(H - 1) + H_{y}]!}{(H - 1)! H_{y}!} & D_{x} is even \\ \frac{[(H^{'} - 1) + D_{y}]!}{(H^{'} - 1)! D_{y}!} & D_{x} is even and (x_{s}, y_{s}) is in the odd column \\ \frac{(H^{'} + D_{y})!}{H^{'}! D_{y}!} & D_{x} is odd and (x_{s}, y_{s}) is in the even column \end{matrix}$	(1)
$P S$	$= {\begin{matrix} \frac{[(H + (D_{y} - 1)]!}{H! (D_{y} - 1)!} & D_{x} is even \\ \frac{[(H^{'} + 1) + (D_{y} - 1)]!}{(H^{'} + 1)! (D_{y} - 1)!} & D_{x} is odd and (x_{s}, y_{s}) \\ is in the odd column \\ \frac{[H^{'} + (D_{y} - 1)]!}{H^{'}! (D_{y} - 1)!} & D_{x} is odd and (x_{s}, y_{s}) \\ is in the even column \end{matrix}$	(2)

The path channels of the other directions are similar to the southeast direction, so the formulas of the path channels in the other directions are not listed here.

3.3 Free Buffer Length Considered in Path Channels

Based on the path channels of the turn model, there is more than one candidate channel. To balance network load, we introduce FBL as another important factor. FBL indicates the number of free buffers in the channel, which displays the free space of each buffer in the routers.

The value of FBL is zero when the current node is fault. On addition, the value of FBL is 0 $\sim$ 4 when the current node is good. For node (x $_{d}$ , y $_{d}$ ) in the southeast direction of node (x $_{s}$ , y $_{s}$ ), the path channels that consider FBL are described as follows (x $_{c}$ is expressed as a row, y $_{c}$ is expressed as a column):

{\begin{matrix} P F E_{(x_{c}, y_{c})} = P E_{(x_{c}, y_{c})} F B L_{(x_{c} + 1, y_{c})} \\ P F S_{(x_{c}, y_{c})} = P S_{(x_{c}, y_{c})} F B L_{(x_{c}, y_{c} + 1)} \end{matrix}

(3)

Figure 2 FBL considered in path channels.

Where PFi $(𝑖 = E, S, N, W)$ is the number of reachable paths between node $(x_{c}, y_{c})$ and node $(x_{d}, y_{d})$ , PE (x $_{c}$ , y $_{c}$ ) (PS(x $_{c}$ , y $_{c}$ )) is the path channel in the east (south) direction of node $(x_{c}, y_{c})$ in the fault-free mesh, FBL $(x_{c} + 1, y_{c})$ is the free buffer length in the east direction close to the node $(x_{c}, y_{c})$ , FBL(x $_{c}$ , $y_{c} + 1$ ) is the free buffer length in the south direction close to the current nodes.

If $𝑃𝐹𝐸 = 𝑃𝐹𝑆 = 0$ , the direction of the router is invalid. If PFE $\geq$ PFS, the direction of the router is east. If PFE $<$ PFS, the direction of the router is south. An example is shown in Figure 2. If FBL is not considered, the optimal router path is S-d-h-i-j-D; otherwise, the optimal router path is S-a-e-i-j-D.

4 Fault-tolerant and Congestion Avoidance Routing Algorithm

In above section, we has given routing model with improved odd-even turn rules and free buffer length in non fault mesh, which is the basis for next research. However in a fault mesh, the calculation method of free buffer length considered in path channels and turn rules are not perfectly applicable, we will give modified calculation rules of path channels in the fault mesh and fault-location odd-even turn rules.

4.1 Path Channels in the Fault Mesh

If the faulty nodes are in the region between the source and destination node, the above path channels formula is not correct because the path channel around the fault node is zero, which can influence path channels in the whole network. Therefore, we propose the S-D area, which indicates the rectangular area including the source and destination node, and the fault node is in the S-D area, which is shown in Figure 3.

Figure 3 S-D area.

When node(x $_{d}$ , y $_{d}$ ) is in the southeast of node(x $_{s}$ , y $_{s}$ ), we explain the path channels of node (x $_{c}$ , y $_{c}$ ) in the east and south directions in the following six cases (x $_{c}$ is expressed as a row, y $_{c}$ is expressed as a column):

1. If node (x $_{c}$ , y $_{c}$ ) is a fault node, the path channels of node (x $_{c}$ , y $_{c}$ ) in the east and south directions are expressed as $F P F E_{(x_{c}, y_{c})} = 0$ and $F P F S_{(x_{c}, y_{c})} = 0$ .

2. If node (x $_{c}$ , y $_{c}$ ) is west of the fault node and adjacent to the fault node, the path channels of node (x $_{c}$ , y $_{c}$ ) in the east are expressed as $F P F E_{(x_{c}, y_{c})} = 0$ ; otherwise, if node (x $_{c}$ , y $_{c}$ ) is north of the fault node and adjacent to the fault node, the path channels of node (x $_{c}$ , y $_{c}$ ) in the east are expressed as $F P F S_{(x_{c}, y_{c})} = 0$ .

3. Node (x $_{c}$ , y $_{c}$ ) is inside the S-D area, and the fault node is also inside the S-D area. In addition, node (x $_{c}$ , y $_{c}$ ) is not adjacent to the fault node. When node(x $_{d}$ , y $_{d}$ ) is in the southeast of node(x $_{s}$ , y $_{s}$ ), the path channels of node (x $_{c}$ , y $_{c}$ ) in the east and south direction are expressed as

{\begin{matrix} F P F E_{(x_{c}, y_{c})} = F P F E_{(x_{c} + 1, y_{c})} + F P F S_{(x_{c} + 1, y_{c})} \\ F P F S_{(x_{c}, y_{c})} = F P F E_{(x_{c}, y_{c} + 1)} + F P F S_{(x_{c}, y_{c} + 1)} \end{matrix}

(4)

4. If node (x $_{c}$ , y $_{c}$ ) is in an even column, the path channels of node (x $_{c}$ , y $_{c}$ ) in the south direction are expressed as $F P F S_{(x_{c}, y_{c})} = 0$ . In addition, node (x $_{c}$ -1, y $_{c}$ ) in the east direction is expressed as $F P F E_{(x_{c} - 1, y_{c})} = 0$ .

5. If node (x $_{c}$ , y $_{c}$ ) is on the southern border of the S-D region except for the destination node, the path channels of node (x $_{c}$ , y $_{c}$ ) in the east direction are expressed as $F P F E_{(x_{c}, y_{c})} = 1$ because whether node (x $_{c}$ , y $_{c}$ ) is in an odd column or an even column, it can arrive at the destination node with no turns.

6. If node (x $_{c}$ , y $_{c}$ ) is outside the S-D region, path channels in the east and south direction are expressed as $F P F E_{(x_{c}, y_{c})} = 0$ and $F P F S_{(x_{c}, y_{c})} = 0$ . That is, we do not consider the router outside the S-D region.

According to the above six rules, we present one router example: node (x $_{d}$ , y $_{d}$ ) is in the southeast of node(x $_{s}$ , y $_{s}$ ), and the fault node is inside the S-D area. The path channels of every node in the S-D region are shown in Figure 4.

Figure 4 Distribution of path channels inside the S-D area with a fault node.

Figure 4 shows that the path channels of the source node in the east and south directions are 4 and 8, respectively, when the fault node exists in the S-D region. However, if S-D region is good, the path channels of the source node in the east and south directions are 5 and 10, respectively, calculated by formulas (1) and (2). In the above example, we also know that the method of path channels in an odd-even turn model with no fault nodes is not applicable to a turn model with a fault node.

The path channels of other directions are similar to the southeast direction, so the formula for the path channels in other directions is not listed here.

4.2 Fault-location Odd-even Turn Rules

When the current node is adjacent of the fault node in the S-D region, we can change routing direction according to the improved turn model as shown in Fig. 5. The “C” is the symbol for a current routing node, “O” and “E” represent the current node is in the odd column or even column.

Figure 5 The turn rules when the current node is adjacent of the fault node.

Using the above turn rules in a fault mesh, when the fault node is on the border of the S-D area, the router is stagnant, as shown in Figure 6. Therefore, to solve the stagnant problem, the odd-even round rule is adopted when node (x $_{d}$ , y $_{d}$ ) is in the southeast of node(x $_{s}$ , y $_{s}$ ).

Figure 6 Fault node on the border of the S-D region.

(1) If the fault node is not on the south side of the S-D region, we set the node $(x_{d} - 1, y_{d})$ as the temporary destination node, formulas (1) and (2) are used to calculate the path channels of the node in the east and south directions. To avoid ES turns in the even column, the temporary destination node is set as the start node, and the path direction is counterclockwise, as shown in Figure 7.

Figure 7 Turn rule when the fault node is on the border of the S-D region.

(2) If the fault node is on the south border of the whole region, we set the node $(x_{d} - 1, y_{d} - 1)$ as the temporary destination node, formulas (1) and (2) are used to calculate the path channels of the node in the east and south directions. The node $(x_{d} - 1, y_{d} - 1)$ is set as the start node, and the round direction is clockwise. Although ES turns in even columns happened, the round lacks a south border, and a closed loop cannot be formed, as shown in Figure 8.

Figure 8 Turn rule when the fault node is on the border of the mesh region.

4.3 Flowchart of the FTCB Routing Algorithm

To realize a balanced load and avoid stagnation problem, a FTCB routing algorithm is introduced. The FTCB routing algorithm includes 3 parts, which is shown in Figure 9. After the system warms up, the build-in-self-diagnosis (BISD) strategy is used to test and diagnose. We first determine whether a fault node is located in an area between the source and destination (S-D area). If not, we use the adaptive routing algorithm considered path channels in the fault-free mesh and free buffer length. If the fault node is in the S-D area, we use the fault-location path channels considered by the adaptive routing algorithm. If the fault node is on the border of the S-D area and the router is stunted, the path channels in the fault-free area considered by the adaptive routing algorithm are used first, and the fault-location odd-even turn model is performed.

Figure 9 The flowchart of the FTCB routing algorithm.

5 Simulation Results and Discussion

5.1 Simulation Environment

Book Sim2.0 [24] is used to simulate single-fault routing algorithms. The statistical traffic load distribution (STLD) [25] method and dynamic analysis are applied to test the performance of our algorithm. The STLD can test the distribution of the network load, although the simulation has not been performed. The communication mode with a synthetic load is used to simulate dynamic analysis. We research an 8 $\times$ 8 mesh network in which adjacent nodes have one positive channel and an opposite channel, input buffer occupancy in each channel, and each packet has eight flits. The simulation time and warm-up time are 70,000 and 20,000 cycles, respectively.

5.2 Performance Analysis

To evaluate our routing algorithm, two evaluation indicators are introduced: the average latency at different packet injection rates and the saturation throughput.

The FTCB routing algorithm is compared with the Xie [26] and Zhang [5] routing algorithms under different traffic modes in the fault network. As shown in Figure 10, in the normal network, the performance of the Xie [26] and Zhang [5] routing algorithms is better than that of FTCB because our routing algorithm has more chosen paths. In our uncertainty routing algorithm, the network latency and throughput rate are no more advantageous than the certainty algorithm. However, in the fault network, the FTCB routing algorithm can improve the saturation throughput by 6.92% and 10.7% over the Xie [26] and Zhang [5] algorithms under the transpose mode, by 1.99% and 6.8% under the uniform mode and by 18.1% and 6.1% under the hotspot mode, respectively.

Figure 10 The performance in a single-fault network.

From experimental results we can see that the FTCB algorithm has better fault tolerance and slower degradation with increasing fault nodes because the FTCB routing algorithm uses the global strategy to the greatest degree. The path channels in normal mesh, path channels in fault mesh, free buffer length, and fault-location odd-even turn rules are used in the FTCB routing algorithms and are advantageous in reducing network congestion.

5.3 Load-balancing Analysis

Next, we analyse load-balancing with single fault under the 8 $\times$ 8 mesh. In the absence of actual simulation network statistics, traffic load can be predicted by STLD. With STLD, only one packet is sent between all uniform source-destination nodes, and the packet selects a path according to the routing rule. Meanwhile, we record the times of packets passing through every node.

The STLDs of the Zhang [5] and Xie [26] routing algorithms and the FTCB routing algorithm with one fault node are shown in Figure 11. The fault node is represented by the white region, and the size of statistical load in the network is represented by different grey scales.

Figure 11 STLDs of Xie, Zhang and the FTCB algorithm.

As shown in Figure 11, we can see that the traffic load of the rightmost column in the FTCB routing algorithm is lower than that in the Xie and Zhang routing algorithms, and the global traffic load distribution in the FTCB routing algorithm is more balanceable than that in the Xie and Zhang routing algorithms.

6 Conclusion

This paper introduces the FTCB routing algorithm based on global perception and adaptive strategy. Some important factors and rules are introduced, such as path channels in fault-free mesh, path channels in fault mesh, free buffer length and fault-location odd-even turn rules. Using the FTCB routing algorithm, we make the network load more balanced around the fault node and make some packets avoid the fault region in advance. Moreover, saturation throughput and average network latency in our work is lower. In the following study, the routing algorithm including multi-fault nodes in 2D and 3D mesh is considered, which will focus on the load balanced and network latency.

Acknowledgements

This work was supported by the innovation base on wide band semiconductor and micro-nano electronics (B12026). The key projects in strategic international scientific and technological innovation cooperation (2016YFE0207000).

References

[1] Rohbani, N., Shirmohammadi, Z., Zare, M., & Miremadi, S. G., Laxy: a location-based aging-resilient xy-yx routing algorithm for network on chip, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1–1, 2017.

[2] Bogdan, P., Tudor Dumitraş, & Muarculescu, R., Stochastic communication: a new paradigm for fault-tolerant networks-on-chip. VLSI Design, special issue on Networks-on-Chip, 17, 2007.

[3] Yu Ren, Leibo Liu, Shouyi Yin, Jie Han, & Shaojun Wei, A fault tolerant noc architecture using quad-spare mesh topology and dynamic reconfiguration. Journal of Systems Architecture, 59(7), 482–491, 2013.

[4] Glass, C. J., & Ni, L. M., The Turn Model for Adaptive Routing. Computer Architecture, 1992. Proceedings. The 19th Annual International Symposium on. ACM, 1992.

[5] Zhang Zhen, Alain Greiner, Sami Taktak, A reconfigurable routing algorithm for a fault-tolerant 2D-Mesh Network-on-Chip [A]. Proceedings of Design Automation Conference. 441–446, 2008.

[6] Jiang, S. Y., Luo, G., Liu, Y., Jiang, S. S., & Li, X. T., Fault-tolerant routing algorithm simulation and hardware verification of noc. IEEE Transactions on Applied Superconductivity, 24(5), 1–5, 2014.

[7] Liu, Y., Ruan, Y., Lai, Z., & Sun, L., A reconfigurable routing method for fault-tolerant mesh-based network on chip. Journal of Information and Computational Science, 10(1), 157–165, 2013.

[8] Fu, B., Han, Y., Li, H., & Li, X., Zonedefense: a fault-tolerant routing for 2-d meshes without virtual channels. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 22(1), 113–126, 2014.

[9] Wu, J., A fault-tolerant and deadlock-free routing protocol in 2d meshes based on odd-even turn model. Computers IEEE Transactions, 52(9), 1154–1169, 2003.

[10] Boppana, R. V., & Chalasani, S., [ACM Press the 1994 ACM/IEEE conference - Washington, D.C. (1994.11.14-1994.11.18)] Proceedings of the 1994 ACM/IEEE conference on Supercomputing, - Supercomputing \”94 – Fault-tolerant routing with non-adaptive wormhole algorithms in mesh networks. (pp. 693), 1994.

[11] Chiu, G. M., The odd-even turn model for adaptive routing. IEEE Transactions on Parallel and Distributed Systems, 11(7), 0–738, 2000.

[12] Xie, R., Cai, J., Xin, X., & Yang, B., Lbft: a fault-tolerant routing algorithm for load-balancing network-on-chip based on odd–even turn model. The Journal of Supercomputing, 2016.

[13] Hu, J., & Marculescu, R. Dyad – smart routing for networks-on-chip, 2004.

[14] Gratz, P., Grot, B., & Keckler, S. W, Regional congestion awareness for load balance in networks-on-chip, 2008.

[15] Chang, En Jui, et al., Path-Congestion-Aware Adaptive Routing With a Contention Prediction Scheme for Network-on-Chip Systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 33(1), 113–126, 2014.

[16] Bahrebar, Poona, and D. Stroobandt, Adaptive and reconfigurable fault-tolerant routing method for 2D Networks-on-Chip. International Conference on Reconfigurable Computing & Fpgas IEEE, 2015.

[17] Fu, Binzhang, et al., An abacus turn model for time/space-efficient reconfigurable routing. International Symposium on Computer Architecture, 2011.

[18] Ebrahimi, M., Daneshtalab, M., Plosila, J., & Tenhunen, H., Minimal-path fault-tolerant approach using connection-retaining structure in Networks-on-Chip. Networks on Chip (NoCS), 2013 Seventh IEEE/ACM International Symposium on. ACM, 2013.

[19] Ramakrishna, M., Kodati, V. K., Gratz, P. V., & Sprintson, A., Gca:global congestion awareness for load balance in networks-on-chip. IEEE Transactions on Parallel and Distributed Systems, 27(7), 2022–2035, 2016.

[20] Wang, J., Huang, L., Li, G., Wang, X., & Mak, T., A Fault-Tolerant Routing Algorithm for NoC Using Farthest Reachable Routers, 2013.

[21] Ebrahimi, M., Daneshtalab, M., Plosila, J., & Mehdipour, F., MD: Minimal path-based fault-tolerant routing in on-Chip Networks. 2013 18th Asia and South Pacific Design Automation Conference (ASP-DAC). IEEE, 2013.

[22] Chaix, F., Avresky, D., Zergainoh, N. E., & Nicolaidis, M., A Fault-Tolerant Deadlock-Free Adaptive Routing for On Chip Interconnects. Design, Automation & Test in Europe Conference & Exhibition (DATE), 2011. IEEE, 2011.

[23] Chen, Y. Y., Chang, E. J., Hsin, H. K., Chen, K. C., & Wu, A. Y., Path-diversity-aware fault-tolerant routing algorithm for network-on-chip systems. IEEE Transactions on Parallel and Distributed Systems, 1–1, 2016.

[24] Dally, William, and B. Towles, Principles and Practices of Interconnection Networks, 2004.

[25] Lin, Shu Yen, et al., Traffic-Balanced Routing Algorithm for Irregular Mesh-Based On-Chip Networks. IEEE Transactions on Computers, 57(9), 1156–1168, 2008.

[26] Cai, Jueping, Xin, Yang, Bo, & Xie, et al. (2017). Mcar: non-local adaptive network-on-chip routing with message propagation of congestion information. Microprocessors and microsystems.

Biographies

Jiao Guan received the B.S. and M.S. degrees in Computer communication engineering from Air Force Engineering University, Xi’an, China, in 2004 and 2009 respectively. She is currently working towards a Ph.D. degree with the school of Microelectronics at Xidian University, Xi’an, China. Her research interests include fault-tolerant system design and share memory in network-on-chips.

Jueping Cai received the B.S. and M.S. degrees in Electronic Engineering from Xidian University, Xi’an, China, in 1998 and 2001 respectively, and received the Ph.D. degree from Shanghai Jiaotong University, Shanghai, China, in 2004. He is currently an professor in school of Microelectronics, Xi’an, China. His research interests are singal processing, low-power mixed-signal integrated circuits and IC design.

Yequn Wang received the M.S.and Ph.D degrees from Air Force Engineering University, Xi’an, China, in 2009 and 2012 respectively, where he is currently a Lecturer with the Information and Navigation College. His main research interests include aeronautical communication, ad hoc networks, satellite communication, and HF communication.

Jian Liu received the M.S. degree from Air Force Engineering University (AFEU), in 2003, and the Ph.D. degree from the National University of Defense Technology (NUDT), in 2007. He is currently an Associate Professor with the Information and Navigation College, Air Force Engineering University (AFEU). His main research interests include integration of radar and communication, and electronic warfare and array signal processing.