| With the technology development of big data,intelligent computing,and cloud computing,multi-cores So C(System-on-Chip,So C)based on bus architecture can not meet the requirements of data processing.Besides,the So C based on network-on-chip(No C)communication interconnection mode with the multi-cores processing ability becomes the development trend of high-performance data processing system.The manufacturing process,production defects,working environment and system complexity greatly increase the probability of the No C failure.The fault-tolerant routing algorithm of the No C can effectively guarantee the reliability of data transmission on the No C.Due to the limitation of on-chip storage resources,area and power consumption,load balancing routing algorithm is an effective method to avoid network congestion for the low transmission delay and high throughput rate network.Therefore,the fault-tolerant routing algorithms with the load-balanced No C are studied and analyzed.The main research contents are as follows:1.For the No C without faults,although the oblivious routing algorithm does not consider the network status and not increase the additional information transmission cost,the congestion degree at the central nodes of the network is much higher than that of the side nodes.In order to relax the network congestion of the oblivious routing algorithm,an oblivious and load-balanced routing algorithm(OLBR)without the virtual channel is proposed to statically divide the No C into two regions(the east-west and north-south region)according to the "fishtail region" model.The data packets in the east-west region are routed in accordance with the OE-YX rule,while the data packets in the north-south region are routed according to the OE-Alterable Priority Arbiter(APA)rules based on the diversity principle of path selection.The proposed routing algorithm not only avoids deadlocks and live locks,but also partially diverts the traffic from the central nodes of the network to the side nodes.Simulation results show that compared with other deterministic fault-tolerant routing algorithms,the proposed OLBR algorithm can enhance the average saturation throughput by 11.6%,which is proven as a simple and feasible load balancing routing algorithm.2.For the No C with the fault regions,under the sufficient network resources,a fault-tolerant and congestion balanced(FTCB)routing algorithm is presented with link state awareness and hybrid path selection strategy.The routers’ health status of and links information can be obtained based on network link state perception,and the number of idle cache units of the candidate nodes.The modified non-deadlock OE-turn model gives the routing turn rules for the fault situations.Firstly,the number of available paths from the current node to the target node is calculated in the fault and fault-free region.Secondly,alternative node idle buffer unit number is evaluated.Finally,the product of the available paths and the idle buffer unit number is regard as the scoring value of the alternative node to implement adaptive load balancing routing.Simulation results show that compared with other fault-tolerant routing algorithms,the average saturation throughput rate is increased by 8.3%.Hence,it is an effective way to realize fault-tolerant routing and load balancing in on-chip networks.3.For the No C with faulty nodes or faulty links,under the limited network resources,a low-cost oblivious and fault-tolerant routing(OFTR)algorithm without virtual channels is presented to avoid the bypass loops and the bypass links in advance.The proposed algorithm adopts a simple coarse-grained model which uses a 4-bit fault vector in each router to represent the fault status of four direct neighbors.If the fault from the current node and the target node isn’t detected,the FTOE-APA rules are used to route data packets to achieve the diversity of routing paths.Otherwise,the priority of output port can be dynamically modified according to the relative positional relationship between the source node,the current node,and the target node.By do so,the data packets can be retransmitted through the shortest path,thereby minimizing the number of rerouting obviously.Benefiting from the improved OE-turn rule and the dynamic priority of output port rule,the OFTR algorithm can avoid network deadlock and live lock,and reduce the probability of data packets entering the fault surrounding region.The simulation results show that OFTR algorithm reduces the network average delay and the network overhead.Compared with other deterministic fault-tolerant routing algorithms,the average saturation throughput of OFTR algorithm is increased by 11.6%.4.For the 3D No C,through silicon via(TSV)technology can connect adjacent layers vertically,reducing network overhead.However,the existing deterministic routing algorithm based on 3D NOC is difficult to achieve load balance of non-uniform data flow.An adaptive selecting elevator routing based on load balance,(ASELB)algorithm is proposed to overcome the shortcoming of deterministic routing algorithm.The ASELB algorithm divides the 3D No C into 4 subnets,and the different deadlock-free subnet selection strategies for current layer and cross-layer packet routing are chosen.Taken the number of transmission hops,free buffers,and the subnets into consideration,the effective elevator to the next level is selected adaptively by setting the priority.Meanwhile,this algorithm only uses two virtual channels in three dimensions to avoid deadlock.The simulation results show that when the elevator is partially bidirectional and the position of the elevator is different at each layer,the proposed algorithm has better performance in the average transmission delay,network saturation throughput,and load balancing than the other related algorithms. |
PDF Full Text Request