| System-on-chip(SoC)designs provide an integrated solution to challenging design problems in the telecommunications,multi-media,and many consumer electronics domains,which proven to be with higher performance,higher speed and lower power consumption.Typical SoC is composed by the chip control logic module,the microprocessor kernel module,the digital signal processor(DSP)block,the embedded memory module,the external communication interface module and other modules,which connected with a high-speed system bus and a low-speed peripheral bus.Chip design has four distinct aspects: computation,memory,communication,and I/O.As processing power has increased and data-intensive applications have emerged,the challenge of the communication aspect in Systems-on-Chip(SoC),has attracted increasing attention.With the complexity and integration of the system becomes larger and larger,many designers found it more efficient to route packet rather than using the wiring connection because the interconnection network allows limited bandwidth to be shared.In other words,because of its poor scalability and limited bandwidth,traditional Bus architecture is growing more and more difficult to satisfy the communication demand between the different PEs.As a novel communication paradigm,Network-on-chip separate the communication system from the whole system improving the SoC performance.It refers to a complete system with the independent working ability that is integrated into a single chip,and the various IP are divided into groups to enable it with higher working efficiency and lower power consumption.Compared with traditional bus structure,the main advantage lies in the four aspects which including the system bandwidth improvement,higher scalability and reusability,solving the system global synchronization problem and power consumption decreases.Topology,routing,mapping,flow control and switching mechanism are the critical technologies in the No C design.Routing determines the path that a message actual takes.A good routing algorithm can balance the traffic evenly in each channel of network in order to make the throughput to achieve the best value,and it can also shorten the length of the routing path as possible,thereby reducing latency of the network.As the high integrated technologies develop,more and more cores are designed in one chip of the No C structure,caused millions of transistors of transistors being tight in a new layout consequently.In order to solve the faults in the network,mainly two strategies are proposed in the past two decades: fault-tolerant network architecture and fault-tolerant routing algorithms.Fault-tolerant network architecture means that solving faults by improving hardware.However,the faults cannot be known at first so that some uncopied spare links or spare routers will increase the hardware costs and energy.Fault-tolerant routing algorithm does not introduce redundant hardware link or spare router.It solves fault problems by change the routing path.Once the transmitted packet encounters fault link or fault router,the routing direction will change and across that fault link or route and the path is not minimal now.Based on the above,this thesis mainly explores an efficient routing algorithm in the network design.The thesis' primary research contents are as follows:1.After exploring the adaptive and deterministic turn model,a novel turn model named VMCD is proposed.In the vertical mesh,OE turn model is applied,while the turn model is dynamic in horizontal mesh according to whether it is an even or odd mesh.OE turn model and XY turn model are used for odd and even XY meshes,respectively.Deadlock and livelock are the fundamental metrics to ensure the quality of the routing algorithm.In theoretical,this proposed turn model is proven to be deadlock and livelock free.Two routing algorithms are created based on the VMCD turn model,which are vertical first routing algorithm(VFRA)and horizontal first routing algorithm(HFRA)respectively.Taking the BOE and ZOE routing algorithm as the comparison,8*8*2 and 8*8*4 meshes are utilized for simulation with Noxim under random and transpose traffic pattern.Through the simulation,we find that the proposed two routing algorithms can improve the performance of the network in throughput,latency and energy.2.Proposed a Hamiltonian-path based odd-even Fault-tolerant Algorithm(Hoe FA).When fault links occurs,for the guarantee of the existence of alternative paths for every packet,the virtual channel is deleted and excessive routing information is cut.Redundancy design of hardware is also introduced in the Hoe FA algorithm.When meeting the boundary locations,information packets can be assigned alternative channel which is generated by modifying the boundary router of mesh topology and adding redundancy channels.In theoretic,because of the reduced prohibited turns in HOE turn model,we presume that Hoe FA can explore unused minimal paths and achieve a higher degree of traffic balance than the traditional Ham FA.The experimental results show the improvement in throughput and the number of arrival packets compared with traditional Hamiltonian-path based Fault-tolerant Algorithm(Ham FA),and it can also reduce the global average latency and max latency in some extent.We also proposed a 3D fault-tolerant routing algorithm considering the strategy of the routing involving vertical links and adopting different routing methods in different odd or even planes.Through the simulation,similar improvement in performance can be found including throughput,latency and the number of arrival packets.However,fewer permitted turn path,weakness in dealing some type of faults and increasing hardware and energy cost,all these drawbacks alert us the improvement space in the fault-tolerant routing algorithm is remaining large.3.Introduce the VMCD routing algorithm into the fault tolerant routing domain to make a better optimization.According to the different direction and location,we partitioned the link faults in the horizon mesh into 8types.In order to avoid deadlock and improve the performance,1-hop look-ahead strategy is introduced.0,4 and 7 link faults are simulated in the 4*4*4 and 8*8*4 mesh network.Through the simulation,we find the proposed VMCD routing algorithm outperforms than Ham FA and Hoe FA in throughput,average latency and arrival rate. |
PDF Full Text Request