Research On Deadlock-free On-chip Routing Algorithm

As semiconductor technology advances rapidly and the application requirement changes,processor has been driven strikingly into multi-core and many-core era.While disadvantages like low performance,high power consumption and low scalability are threatening the traditional bus or point-to-point communication mechanisms.Referencing the computer network technology,Network-on-Chip(No C),a new on-chip communication architecture is proposed to address above disadvantages.With the increasing of processor cores,the reliability of No C is undermined owning to the hard fault induced by manufacturing defect,technological deviation and aging.At the same time,congestion results in higher network latency and the rapid dropping of No C performance.With the fault-tolerant routing and congestion routing as the research subject,this dissertation focuses on the fault-tolerant routing algorithm without deadlock and the congestion-aware adaptive routing algorithm without deadlock for 2D mesh No C.The routing algorithm mainly uses virtual channels technique and turn model technique to avoid deadlock.The main contributions are summarized as follows: 1.Fault-tolerant routing algorithm without virtual channels for all single faulty link or node is proposed.On basis of analyzing the structure feature of single fault No C,this dissertation proposes a Fault-Tolerant Odd-Even(FTOE)turn model to solve the problems of traffic load imbalance and packet loss when existing turn model is adapted to fault-tolerant routing algorithm without virtual channels.Based on FTOE turn model,a Reconfigurable and Fault-Tolerant Routing(RFTR)algorithm without virtual channels is proposed.RFTR can tolerate any single faulty link or node,balance the traffic load around the fault and reduce the fault-tolerant paths.2.Fault-tolerant routing algorithm without virtual channels for multiple faulty nodes is proposed.In the fault-tolerant routing algorithm without virtual channels for multiple faulty nodes,the multiple faulty nodes are transformed into faulty region by using fault model,and then packet is routed around the faulty region along its boundary,which simplifies the complexity of the routing algorithm significantly.Most existing fault-tolerant routing algorithms without virtual channels for multiple faulty nodes have traffic load imbalanceand long circuitousness.Meanwhile,prohibited turns may be introduced if a packet vertically hits the boundary of a faulty region,which would lead to network deadlock.Applying FTOE rules and routing packets around faulty regions in advance,a Load-Balancing and Fault-Tolerant(LBFT)routing algorithm without virtual channels is proposed.LBFT can use small amounts of fault information to find the faulty regions in advance,and then route packets around them to avoid vertically hitting on the boundary of a faulty region.More importantly,LBFT can tolerate any number of faulty nodes,balance the traffic load around the faulty region and reduce the fault-tolerant paths.3.Adaptive and fault-tolerant routing algorithm for multiple faulty links and faulty nodes is proposed.A fault-tolerant routing algorithm without virtual channels avoids deadlock by using turn model,but it has less adaptivity because of the prohibited turns in turn model.To minimize amount of virtual channels and design an adaptive and fault-tolerant routing algorithm,double-Y network is adopted that requires only respectively two and one virtual channels along the Y and X dimensions.However,because the limitation of existing turn models based on the double-Y network results in the routing algorithm only tolerate single faulty link or node;more and more packets are lost as the fault rates increasing.To address above problems,a novel turn model called NMad-y is proposed,which supports the prohibited turns in existing turn models and improves their adaptivity.A new fault information distribution mechanism is also proposed,which propagates the link status of neighbor nodes within 2-hop.Based on NMad-y turn model and the link status of neighbor nodes within 2-hop,this dissertation finally proposes an Adaptive and Fault-Tolerant Routing(AFTR)algorithm that can maintain high reliability of more than 97.43% on average without losing the performance of network and can tolerate any number of faulty links and faulty nodes.4.Non-local adaptive routing algorithm with efficient message propagation of congestion information is proposed.Non-Local adaptive routing algorithms utilize the congestion information of both local and distant links to decide the output link selection,which can greatly improve the network performance.Existing non-local and adaptive routing algorithms adopt a congestion propagation network or embed the congestion information in packet headers to propagate the congestion information.The propagated congestion information makes every node in network to know the status of distant links.However,these mechanisms can either introduce additional hardware cost or lead to a less timeliness of congestion information.To address problems,two specific kinds of messages are used to propagate the congestion information of distant links across the network without introducing additional hardware cost and leading to a better timeliness of congestion information.This dissertation finally proposes an Efficient and Non-local Adaptive Routing(ENAR)algorithm.ENAR efficiently utilizes the propagated congestion information to decide the output link selection,which can avoid congestion.ENAR takes into consideration only the status of links that are on the path to the destination in the minimum quadrant and compares only the links status which have the same amount during the process of selecting the output path,which eliminates the redundant status information.