Research On Routing Algorithm For Vertically Partically Connected 3D NoC

Three-Dimensional Network-on-Chip(3D NoC)architecture is the combination of the ThreeDimensional Integrated Circuit(3D IC)technology and NoC architecture,and it becomes an attractive topic in NoC research field with the reason which has shorter global interconnection,higher package density and better scalability.But the Through Silicon Via(TSV)in 3D NoC used for inter layer interconnection has some disadvantages,such as high cost and low yield.At the same time,3D chip can’t ensure each of layers to arrange components regularly.So the vertically partially connected 3D NoC,which limits number of TSV and allows each layer to have different layout,has been researched widely.Based on analyzing the existing NoC routing algorithm,this dissertation does some research about routing algorithm in vertically partially connected 3D NoC from unicast and multicast aspects,in order to improve network performance and reduce resource cost.There are three research points.Firstly,this dissertation presents a novel TSV table aiming at solving the problem that traditional TSV table has poor scalability.And based on the new TSV table,A unicast routing algorithm with fault tolerance and congestion avoidance is proposed.Then,in order to reduce the hardware cost and power consumption without reducing data transmission performance,a deflection routing algorithm is proposed.Finally,an adaptive hybrid multicast routing algorithm is present with the purpose of further improve the efficiency of data transmission.Specific work of this dissertation is outlined as follows:(1)A unicast routing algorithm in vertically partially connected 3D NoC is proposed.This algorithm chooses output port according to the relationship between source node and destination node and the congestion state of neighbor node,and it solves the problem that nodes near TSV are prone to congest.In addition,A novel TSV table,which only records location and distance of TSV nearest from router’s output ports,is used in this algorithm,and it solves the problem that traditional TSV table has high hardware cost and poor scalability.Experimental results show that our proposed unicast algorithm has better network performance and reliability than traditional unicast routing algorithm in vertically partially connected 3D NoC.(2)A deflection routing algorithm in vertically partially connected 3D NoC is proposed.This algorithm calculates the best output port according to the relationship between source node and destination node and the record of TSV table.Additionally,A new micro buffered router based on MinBD router is used in this algorithm.This router can reduce deflection rate in data transmission by modifying original side-buffer microarchitecture and permute network policies.And it can suit itself to vertically partially connected 3D NoC topology through TSV injection/ ejection scheme.Experimental results show that our proposed deflection algorithm can provide more efficient data transmission than reference deflection routing algorithm.(3)A multicast routing algorithm in vertically partially connected 3D NoC is proposed.This algorithm adopts adaptive multi-path routing scheme based on Hamilton graph,which divides destination node set into several parts by bit mask,for intra-layer communication.And it adopts tree-based multicast routing method for inter-layer communication.It builds multicast tree for each destination node by taking source node as root and taking TSV’s upstream node as branch.Experimental results show that our proposed multicast algorithm can provide efficient data transmission and ensure the reliability of data transmission at the same time.