CN105577539A - Routing method and system for non-regular three-dimensional integrated circuit network-on-chip - Google Patents
Routing method and system for non-regular three-dimensional integrated circuit network-on-chip Download PDFInfo
- Publication number
- CN105577539A CN105577539A CN201610057261.6A CN201610057261A CN105577539A CN 105577539 A CN105577539 A CN 105577539A CN 201610057261 A CN201610057261 A CN 201610057261A CN 105577539 A CN105577539 A CN 105577539A
- Authority
- CN
- China
- Prior art keywords
- node
- chip
- network
- irregular
- hamilton
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/02—Topology update or discovery
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/12—Shortest path evaluation
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/14—Routing performance; Theoretical aspects
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/24—Multipath
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/48—Routing tree calculation
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
The invention provides a routing method and system for a non-regular three-dimensional integrated circuit network-on-chip. The method comprises the steps of according to the topological structure of the non-regular three-dimensional integrated circuit network-on-chip, determining that a Hamiltonian path based error tolerance routing algorithm route data package or a spanning tree based error tolerance routing algorithm route data package is adopted; if the Hamiltonian path based error tolerance routing algorithm route data package is adopted, determining to perform routing error tolerance by use of the sequence of monotonous ascending node number or monotonous descending node number according to positions of a source node and a destination node; and if the spanning tree based error tolerance routing algorithm route data package is adopted, selecting to generate a tree root node, and selecting a transmission path to finish transmission of the data package according to the root node and positions of the source node and the destination node.
Description
Technical field
The present invention relates to the technical field of integrated circuit, particularly a kind of method for routing towards irregular three dimensional integrated circuits network-on-chip and system.
Background technology
Three-dimensional integration technology a kind ofly device layers stack different for chip to be gathered into folds, Vertical collection a kind of encapsulation technology (BanerjeeK together, etal., " 3-DICs:anovelchipdesignforimprovingdeep-submicrometerint erconnectperformanceandsystems-on-chipintegration; " inProceedingsoftheIEEE, Volume:89, Issue:5,2001, pp.602-633.).This technology can shorten physical connection length in chip, reaches the effect reducing Time Delay of Systems and power consumption.Fig. 1 is the schematic diagram of simple 4*2*3 three-dimensional chip network-on-chip (network-on-chip, NoC), and topological structure is common three-dimensional Mesh structure.Have 3 different components layers in figure, 24 processing units (processingelement, PE) connect router nodes (calling in the following text " node ") different separately respectively, by level or vertical mode interconnection between node.
Network topology is an important framework attribute of network on three-dimensional chip, the regular network topology of network on three-dimensional chip has a variety of, such as three-dimensional Mesh, three-dimensional Torus, three-dimensional FoldedTorus and three-dimensional BFT (ButterflyFat-Tree) etc., but, at the industrial quarters three-dimensional multiprocessor chip (chipmulti-processor of reality, CMP) in, because processing unit generally all adopts isomery patten's design, different processing units is set to different functional modules usually to meet the demand of practical application, such as, some processing unit can settle processor, other processing units can embed secondary or three grades of high-speed caches etc., therefore, the network-on-chip topology of three-dimensional CMP mostly is irregular topology, specifically, in network, the structure of each device layer is neither identical, and the vertical distribution linked between each node neighbor node up and down corresponding with it is also heterogeneous, the irregular network on three-dimensional chip of typical case as shown in Figure 2.
Because the complexity of three dimensional integrated circuits and integrated level improve constantly, the extreme influence communication efficiency of network-on-chip, cause that the fault occurrence probability of parts in network is also corresponding to be increased simultaneously, in order to ensure the proper communication of network on three-dimensional chip, need to introduce suitable fault-tolerance approach, usually, the fault of network-on-chip is divided into transient state fault and permanent fault, these faults may occur in processing unit, network interface, in the parts such as the link between router or router, in the present invention, we mainly pay close attention to permanent link failure common in network, this kind of fault, once occur, can not be repaired, communication for network-on-chip will produce the impact even more serious than transient state link failure, it should be noted that, generation due to permanent fault also may cause the network topology structure of rule originally to have irregular feature, this situation is equally applicable to the method and system that the present invention proposes.
Comparative maturity is studied both at home and abroad for the fault-tolerance approach of traditional two-dimentional network-on-chip, but for network on three-dimensional chip, especially the related ends of Irregular topology structure three-dimensional network-on-chip (calling in the following text " irregular network on three-dimensional chip ") is then less, generally speaking, the fault-tolerance approach towards the network-on-chip that there is permanent link failure is divided into following a few class usually: 1) use redundant component to replace inoperative component; 2) packet is made to avoid fault zone by adding peripheral logical circuit around trouble unit; 3) use reliable routing method, direct control data held broken link.
Usually, network-on-chip scale for major applications design is less, the present situation that Resources on Chip is limited, how to design low cost and the fault-tolerance approach of high reliability for ensureing that the communication quality of this type of network on three-dimensional chip is most important, because redundant technique and periphery circuit design all need to transform the physical structure of chip, the expense of area to a certain degree and power consumption can be produced, and circuit scale this expense larger is more obvious, on the other hand, reliable routing method is as a kind of network-on-chip fault tolerance method of lightweight, not only can not change the structure of chip, and communication task can have been continued when network failure, and ensure higher communication performance, these class methods have been widely used in two and three dimensions network-on-chip, but be mainly limited to the three-dimensional network topological structure of rule.
First, it should be noted that, Virtual Channel (virtualchannel, VC) and turn to restriction (steering model etc.) to be that two kinds of main network-on-chip communicating abstract that can destroy rely on the formation of ring (calling in the following text " abstract ring ") thus the key technology that occurs of deadlock prevention phenomenon.
Existing achievement in research is main not enough as follows:
1) need to use the VC technology of high cost to avoid the generation of network lock-up.The use of Virtual Channel can introduce larger area overhead and complicated control logic, is not suitable for the strict circuit design of cost requirement.
2) even if do not use Virtual Channel technology, and adopt the steering model of low cost, or introduce new theory for Avoid deadlock, also other problem may be brought, such as, because network configuration is irregular, there is the situation that cannot perform in the routing algorithm that single steering model can cause it to guide, introduces the support that multiple steering model then needs VC technology; In addition, also there is hidden danger in simple some specific path route data packets of introducing, namely in a lot of irregular network on three-dimensional chip, possibly cannot find out qualified specific path.
3) port of a lot of existing scheme selects mechanism to adopt the strategy of Stochastic choice, and namely when legal port is not unique, Stochastic choice port exports packet, can not walk around conflict area well, cause network service performance lower.
Above 3 directly cause existing achievement to have three large defects: the first, can not ensure higher communication performance (mainly comprising communication delay and throughput two indices); The second, the reliability index of communication is lower; 3rd, higher overhead.
Summary of the invention
For the deficiencies in the prior art, the present invention proposes a kind of method for routing towards irregular three dimensional integrated circuits network-on-chip and system.
The present invention proposes a kind of method for routing towards irregular three dimensional integrated circuits network-on-chip, comprising:
Step 1, according to the topological structure of described irregular three dimensional integrated circuits network-on-chip, judges to adopt based on the Fault-tolerant Routing Algorithm route data packets in Hamilton path, or based on the Fault-tolerant Routing Algorithm route data packets of spanning tree;
Step 2, according to the Fault-tolerant Routing Algorithm route data packets based on described Hamilton path, position according to source node and destination node is determined to use the order according to node serial number monotone increasing or monotonic decreasing to carry out router operating system, described packet carries out in transmitting procedure along the Hamilton path chosen, and makes packet often through a node all nearlyer steps of distance destination node;
Step 3, according to the Fault-tolerant Routing Algorithm route data packets based on described spanning tree, then selects spanning-tree root node, according to root node, and the position of source node and destination node, select transmission path to complete the transmission of described packet;
Step 4, when described packet arrives node, check that whether the address of node of arrival is identical with the address of described destination node, if identical, then described packet arrives described destination node, otherwise circulation performs step 2 or 3, until packet arrives destination node.
Described step 1 comprises:
If the Hamilton path of existence anduniquess in described irregular three dimensional integrated circuits network-on-chip, then select the execution of described unique Hamilton path based on the Fault-tolerant Routing Algorithm in Hamilton path; If there are many Hamilton paths in described irregular three dimensional integrated circuits network-on-chip, then in described many Hamilton paths, select one arbitrarily, perform the Fault-tolerant Routing Algorithm based on Hamilton path; If do not find Hamilton path in network, then adopt the Fault-tolerant Routing Algorithm route data packets based on spanning tree.
In described step 2 by the node in described irregular three dimensional integrated circuits network-on-chip according to the order number consecutively on Hamilton path.
Root node described in described step 3 meets:
1) K
rbe positioned on L layer, wherein
k
rfor described root node, J is the horizontal device number of plies, and L is certain one deck horizontal device in horizontal device;
2) of described irregular three dimensional integrated circuits network-on-chip is established
layer there is I node, is numbered the present node p of p in its middle level, 0≤p≤I-1, if Δ
pifor the shortest leapfrog number of the node of i-th in present node p and layer except node p, then K
rnode p is removed with the shortest average leapfrog number of exterior node for N in distance layer
r, N
rfor:
Described step 3 also comprises:
Be always into, be always out to, first enter to going out again and select transmission path to complete the transmission of packet in these three kinds of transmission directions.Packet carries out in transmitting procedure in the spanning tree determining root node, makes packet often through a node all nearlyer steps of distance destination node.
Also comprise: if the next-hop node in described step 2 or described step 3 is not unique, then according to DP-3D mechanism, obtain the flow sensing situation of each legal port of present node, the legal port selecting flow minimum exports, reduce the probability of message transition collision, avoid hot spot region.
The present invention also proposes a kind of route system towards irregular three dimensional integrated circuits network-on-chip, comprising:
Judge module, for the topological structure according to described irregular three dimensional integrated circuits network-on-chip, judges to adopt based on the Fault-tolerant Routing Algorithm route data packets in Hamilton path, or based on the Fault-tolerant Routing Algorithm route data packets of spanning tree;
Hamilton routing algorithm module, for according to the Fault-tolerant Routing Algorithm route data packets based on described Hamilton path, position according to source node and destination node is determined to use the order according to node serial number monotone increasing or monotonic decreasing to carry out router operating system, described packet carries out in transmitting procedure along the Hamilton path chosen, and makes packet often through a node all nearlyer steps of distance destination node;
Spanning tree algorithm module, for according to the Fault-tolerant Routing Algorithm route data packets based on described spanning tree, then selects spanning-tree root node, according to root node, and the position of source node and destination node, select transmission path to complete the transmission of described packet;
Arrive destination node module, for when described packet arrives node, check that whether the address of node of arrival is identical with the address of described destination node, if identical, then described packet arrives described destination node, otherwise circulation performs described Hamilton routing algorithm module or described spanning tree algorithm module, until packet arrives destination node.
Described judge module comprises:
If the Hamilton path of existence anduniquess in described irregular three dimensional integrated circuits network-on-chip, then select the execution of described unique Hamilton path based on the Fault-tolerant Routing Algorithm in Hamilton path; If there are many Hamilton paths in described irregular three dimensional integrated circuits network-on-chip, then in described many Hamilton paths, select one arbitrarily, perform the Fault-tolerant Routing Algorithm based on Hamilton path; If do not find Hamilton path in network, then adopt the Fault-tolerant Routing Algorithm route data packets based on spanning tree.
In described Hamilton routing algorithm module by the node in described irregular three dimensional integrated circuits network-on-chip according to the order number consecutively on Hamilton path.
Root node described in described spanning tree algorithm module meets:
1) K
rbe positioned on L layer, wherein
k
rfor described root node, J is the horizontal device number of plies, and L is certain one deck horizontal device in horizontal device;
2) of described irregular three dimensional integrated circuits network-on-chip is established
layer there is I node, is numbered the present node p of p in its middle level, 0≤p≤I-1, if Δ
pifor the shortest leapfrog number of the node of i-th in present node p and layer except node p, then K
rnode p is removed with the shortest average leapfrog number of exterior node for N in distance layer
r, N
rfor:
Described spanning tree algorithm module also comprises:
Be always into, be always out to, first enter to going out again and select transmission path to complete the transmission of packet in these three kinds of transmission directions.Packet carries out in transmitting procedure in the spanning tree determining root node, makes packet often through a node all nearlyer steps of distance destination node.
Also comprise: if the next-hop node in described Hamilton routing algorithm module or described spanning tree algorithm module is not unique, then according to DP-3D mechanism, obtain the flow sensing situation of each legal port of present node, the legal port selecting flow minimum exports, reduce the probability of message transition collision, avoid hot spot region.
From above scheme, the invention has the advantages that:
First point, the present invention can improve the communication performance of three dimensional integrated circuits network-on-chip on fault-tolerant basis, comprises and reduces average communication time delay and improve network throughput.This point mainly because the shortest-path first algorithm based on Hamilton path or spanning tree selects mechanism with the port expanded to three-dimensional scenic, can be avoided hot spot region, reduce the probability that packet clashes.Routing self-adaption degree of the present invention is higher, can be judged according to the physical fault situation occurred of network-on-chip, selects the legal output port that conflict is minimum;
Second point, the present invention can utilize the own characteristic of Hamilton path or these two graphtheoretic concepts of spanning tree, eliminating the possibility forming abstract ring in network-on-chip, the communication deadlock under three-dimensional scenic just can be avoided when not using expensive VC technology to occur.From the angle realizing cost, the Fault-tolerant Routing Algorithm of the low expense three dimensional integrated circuits network-on-chip in the present invention possesses stronger engineering meaning;
Thirdly, the present invention can ensure higher communication reliability.An important indicator of network reliability is exactly within the given time, and the quantity that can route to the packet of destination node by source node occupies during this period of time the ratio being injected into packet total quantity in network.If this ratio is higher, then the reliability of corresponding route designing method is higher.The present invention can make packet route to destination node in the short time as far as possible, ensures the reliability communicated within the time of setting.
Accompanying drawing explanation
Fig. 1 is the schematic diagram of a three-dimensional Mesh network-on-chip of typical 4*2*3;
Fig. 2 is the schematic diagram of a typical irregular network on three-dimensional chip;
Fig. 3 is the Hamilton path schematic diagram in irregular network on three-dimensional chip;
Fig. 4 is the spanning tree schematic diagram in irregular network on three-dimensional chip;
Fig. 5 is the routing algorithm exemplary plot based on Hamilton path;
Fig. 6 is the routing algorithm exemplary plot based on spanning tree.
Embodiment
First, briefly introduce technical background of the present invention, two graphtheoretic concepts---Hamilton path and the spanning tree namely introduced in routing algorithm.
Concept 1: Given Graph G, if there is a paths, in figure, each summit just once, this paths is then referred to as a Hamilton path (EbrahimiM of figure G, DaneshtalabM, PlosilaJ. " Fault-tolerantroutingalgorithmfor3DNoCusinghamiltonianpa thstrategy, " inProceedingsofDesign, Automation & TestinEuropeConference & Exhibition.LosAlamitos:IEEEComputerSocietyPress, 2013, pp.1601-1604.).
From concept 1, Hamilton path is a basic conception in graph theory, in the three-dimensional Mesh structure of rule, certainly exist many Hamilton paths, by all nodes according to numbering ascending order or descending just past once, as shown in Figure 3, it is an irregular three-D network-on-chip, wherein all four-headed arrows composition path representation be a Hamilton path of this network, advantage based on this paths route data packets is can avoid occurring the abstract loop of transfer of data, does not need Virtual Channel (VC) technology using high cost.
It should be noted that, due to the feature in Hamilton path self, node serial number rule in Fig. 3 is different from Fig. 2, need to number in order according to path, then there is not Hamilton path in the irregular network in Fig. 2, this also illustrates that not all irregular network on three-dimensional chip all exists Hamilton path, and meanwhile, each scramble network also may exist not unique Hamilton path (different Hamilton paths can make node serial number generation respective change).
On the other hand, essence based on the routing algorithm in Hamilton path is " the shortest " with good conditionsi routing algorithm, but it is non-essential strictly along Hamilton path route, as long as without prejudice to the prerequisite of " strictly pressing node serial number ascending order or descending transmission ", then select other non-Hamilton path also can't introduce the abstract loop of transfer of data, still can Avoid deadlock, such as, node 6 is source nodes, node 10 is destination nodes, the path then selected is 6 → 7 → 10, but not 6 → 7 → 8 → 9 → 10, but, if shortest path there is permanent linkage fault, then need the legal path selecting other, such as, link 7-10 breaks down, then the packet at node 7 place can be selected to link 7-8, order according to 7 → 8 → 9 → 10 continues according to node serial number ascending order route, this operation also improves the reliability of routing algorithm.
Concept 2: Given Graph G, if there is all summit to link together by limit, and there is not the tree in loop, then this tree is called spanning tree (MatsutaniH, BogdanP, a MarculescuR of figure G, etal. " Acaseforwireless3DNoCsforCMPs; " inProceedingsofthe18thAsiaandSouthPacificDesignAutomatio nConference.LosAlamitos:IEEEComputerSocietyPress, 2013, pp.23-28.).
Equally as the concept of a graph theory, spanning tree itself does not have directivity, in order to retain limit as much as possible with the quantity of Logistics networks communication path, spanning tree routing algorithm needs to introduce transmission direction to eliminate the abstract transmission loop in network, here, the present invention introduces two transmission directions: enter to (In) and go out to (Out), thus not producing on the basis in loop, in spanning tree, retain more limit (link), improve the communication reliability of network.In and Out is for spanning-tree root node, with other seven directions of three-dimensional network, i.e. east (East), south (South), west (West), north (North), upper (Up), under (Down) and local (Local) different, abstract process has been done in above seven directions by In and Out both direction, as shown in Figure 4 (network in Fig. 2), if select node 12 as the root node of spanning tree, what then solid arrow represented is exactly the path that transmission direction is In, and the transmission direction that dotted arrow represents is the path of Out.
After introducing In and Out two transmission directions, data packet by possessing one-way feature equally, thus can avoid network lock-up, specifically, if destination node can be gone directly by In direction or Out direction, then direct according to which route; Otherwise, then according to first In direction Out direction route (not allowing generation 180 ° to turn to avoid occurring abstract loop in network) again, still also can prevent deadlock from occurring.Such as, in the network shown in Fig. 4, source node is node 2, and destination node is node 5, then 2 → 1 → 0 → 5 or 2 → 1 → 4 → 5 is all feasible transmission path; If source node location is constant, destination node changes node 6 into, then path 2 → 1 → 8 → 11 → 12 → 13 → 6 or 2 → 1 → 0 → 5 → 12 → 13 → 6 is all optional path, it should be noted that, be not first must through root node according to Out direction route data packets again according to In direction, such as, source node is still node 2, destination node is node 10, then the transmission path of packet is 2 → 1 → 8 → 11 → 10, meanwhile, the permanent linkage fault in network once occur, then can affect concrete path planning to some extent.Such as, if link 1-4 breaks down, then source node is node 2, and destination node is that the transmission path of node 5 still has 2 → 1 → 0 → 5 can select.
It should be noted that, if there is multiple spanning tree (namely having multiple root node) in network and each spanning tree simultaneously in order to instruct the Route Selection of network, then need the Virtual Channel support of respective numbers, therefore, the present invention only relates to the Design of Routing Algorithm of single spanning tree, after root node is determined, the structure of the spanning tree of network is also determined thereupon.
The routing algorithm based on Hamilton path introduced hereinbefore and spanning tree routing algorithm, network lock-up can be avoided under the prerequisite not using Virtual Channel mechanism, packet is routed to destination node simultaneously, here, the present invention provides hypothesis 1, for the enforceability ensureing Fault-tolerant Routing Algorithm in irregular network and the reliability communicated.
Suppose 1: no matter in network, permanent linkage fault occurs in any position, all there will not be inaccessible node.
Routing algorithm based on Hamilton path is different with spanning tree routing algorithm essence, there is respective feature, comparatively speaking, the former is stricter than the structural requirement of the latter to network, as said above, be not that each irregular network on three-dimensional chip exists Hamilton path, in addition, because dull ascending order or descending route can directly be carried out according to node serial number in Hamilton path, therefore its maximum leapfrog number can be subtracted each other by the numbering of source node and destination node and draws, if leapfrog number is N, source node be numbered N
s, destination node be numbered N
d, then N≤| N
d– N
s|, and the route leapfrog number of spanning tree algorithm and the position of spanning-tree root node select the degree of correlation very high, different this network core indexs of root node position meeting extreme influence, therefore, spanning tree routing algorithm is relative to the routing algorithm based on Hamilton path, bring certain uncertainty by systematic function, need to design corresponding technical scheme and make its stable performance as far as possible and promoted.
If the nodes of irregular network on three-dimensional chip is K (node serial number in network is 0 ~ K-1), in network, horizontal device number of layers is J (in network each layer numbering according to bottom-up be 0 ~ J-1).
Due to Hamilton path once determine, node is according to path order numbering (the present invention adopts ascending order numbering 0 ~ K-1 by bottom-up device layer order to node), between the node in network, mutual reachable path is also just decided, relative to spanning tree routing algorithm, there is higher stability, when there is no Hamilton path in irregular three-D network, then must perform spanning tree Fault-tolerant Routing Algorithm, the coding rule of node is comparatively simple, namely from the 0th layer to J-1 layer, need only at every layer by line order numbering, only can (can number with reference to the network node in figure 2) as node label.
The core of spanning tree Fault-tolerant Routing Algorithm is the choosing method of its root node position, here thinking is chosen in the concrete quantification introducing this position, consider from fairness angle, the leapfrog number of root node and each node needs little as far as possible, the node of far-end can be avoided like this to count to through more leapfrog and to reach destination node, therefore, if be numbered K
rnode be the root node of the spanning tree of network, the present invention selects K
rtwo constraintss below demand fulfillment:
1) K
rbe positioned on L layer, wherein
2) of irregular network is established
layer there is I node, in layer, is numbered p, 0≤p≤I-1 (sphere of action of numbering is only limited to this layer, only for convenience of description, numbers irrelevant with network node).If Δ
pifor the shortest leapfrog number of present node p and other node of this layer (i-th except node p altogether in I-1 node), then K
rin distance layer, the shortest average leapfrog number of other nodes is N
rfor:
If meet of formula (1)
layer interior nodes is not unique, then select one arbitrarily wherein.
It should be noted that, the data traffic of spanning-tree root node periphery is usually comparatively large, easily cause this regional temperature to raise, and the normal function affecting physical unit performs.The present invention supposes chip heat radiator (i.e. the 0th layer of below) under the bottom of chip, and therefore when the device number of plies of three-dimensional chip is even number, the present invention is
in layer, but not the
select spanning-tree root node in layer, be beneficial to the timely dissipation of the overall heat of chip.
On the other hand, Dynamic Programming (dynamicprogramming, DP) mechanism (MakT is selected, CheungPYK, LamKP, etal. " Adaptiveroutinginnetwork-on-chipsusingadynamic-programmi ngnetwork, " IEEETransactionsonIndustrialElectronics, 2011, 58 (8), pp.3701-3716.), it is a low expense towards conventional two-dimensional network, high efficiency port selects mechanism, DP mechanism is not according to the traffic conditions of present node close region, but according to real-time by source node to the path planning update status of destination node, optimum transmission path is selected in alternative.Because DP mechanism has obtained good experiment effect in two-dimensional network, this mechanism is expanded in three dimensions by the present invention, be designated as DP-3D port and select mechanism, to obtain higher communication performance, DP-3D mechanism combines with Fault-tolerant Routing Algorithm, just constitutes the complete self adaptation reliable routing method that the present invention proposes.
Concrete steps of the present invention are:
Step 100: whether it exists Hamilton path according to the structure decision of irregular network on three-dimensional chip;
Step 200: according to the judgement structure of step 100, carries out next step operation.If there is Hamilton path in network and uniquely, then select the execution of this path based on the Fault-tolerant Routing Algorithm in Hamilton path; If there is Hamilton path in network and uniquely, then need to select one arbitrarily in these paths, then perform the Fault-tolerant Routing Algorithm based on Hamilton path; If there is not Hamilton path in network, then adopt the Fault-tolerant Routing Algorithm route data packets based on spanning tree;
Step 201: if network on three-dimensional chip adopts the Fault-tolerant Routing Algorithm route data packets based on Hamilton path, first determine to use according to the position of source node S and destination node D and carry out fault tolerance rout ing according to the monotone increasing of node serial number or the order of decline, this order once selected, then can not be changed.Packet, in a network along in the process of the Hamilton path transmission chosen, should ensure packet as far as possible often through a node all nearlyer steps of distance destination node;
Step 202: if network on three-dimensional chip adopts the Fault-tolerant Routing Algorithm route data packets based on spanning tree, first suitable spanning-tree root node R should be selected, again according to root node R, and the position of source node S and destination node D, be always In, be always Out and first In and select suitable transmission path to complete the routing procedure of packet in these three kinds of transmission directions of Out again.In the process that packet transmits in the spanning tree determining root node, packet should be ensured as far as possible often through a node all nearlyer steps of distance destination node;
Step 300: if the optional next-hop node in step 201 or 202 is not unique, then according to DP-3D mechanism, obtain the flow sensing situation of each legal port of present node, the legal port selecting flow minimum exports, reduce the probability of message transition collision, avoid hot spot region;
Step 400: after packet arrives next node, first comparison node address, if this node is destination node D, then arrive destination node, otherwise, according to the difference of offered load, again perform the content in step 201 or 202, and the associative operation in step 300, draw the position of next-hop node;
Step 500: the content in repeated execution of steps 400, until packet arrives destination node D.
For example, be still described for the scramble network in Fig. 3.Obviously, there is the Hamilton path of more than in the network, be described for the path shown in Fig. 3.If source node is node 2, destination node is node 17, as shown in Figure 5.Due to link 6-13 fault, " the shortest " path 2 → 3 → 4 → 5 → 6 → 13 → 14 → 17 therefore cannot be used to carry out route, then adopt another " the shortest " path 2 → 3 → 8 → 9 → 10 → 11 → 16 → 17.What this example adopted is carry out dull ascending order route by node serial number, otherwise also in like manner.
As shown in Figure 6, be the example performing spanning tree Fault-tolerant Routing Algorithm when there is not Hamilton path in scramble network.Due to the constraints according to spanning tree of network root node demand fulfillment, only have node 8 and node 11 to meet the demands, therefore node 12 can not be re-used as the root node of the spanning tree of network.Here set node 11 as root node.When linking 11-12 and permanent fault occurring, path 2 → 1 → 8 → 16 → 15 → 17 and 2 → 1 → 8 → 7 → 15 → 17 still all can use, the output port legal when the node 8 due to packet is not unique, need to select machine-processed DP-3D to carry out real-time judge according to port, suppose finally to have selected 2 → 1 → 8 → 7 → 15 → 17 for data transfer path, experienced by the transmission of 2 In directions (link 1-2 and 1-8) and 3 Out directions subsequently (link 7-8,7-15 and 15-17) respectively.
The present invention also proposes a kind of route system towards irregular three dimensional integrated circuits network-on-chip, comprising:
Judge module, for the topological structure according to described irregular three dimensional integrated circuits network-on-chip, judges to adopt based on the Fault-tolerant Routing Algorithm route data packets in Hamilton path, or based on the Fault-tolerant Routing Algorithm route data packets of spanning tree;
Hamilton routing algorithm module, for according to the Fault-tolerant Routing Algorithm route data packets based on described Hamilton path, position according to source node and destination node is determined to use the order according to node serial number monotone increasing or monotonic decreasing to carry out router operating system, described packet carries out in transmitting procedure along the Hamilton path chosen, and makes packet often through a node all nearlyer steps of distance destination node;
Spanning tree algorithm module, for according to the Fault-tolerant Routing Algorithm route data packets based on described spanning tree, then selects spanning-tree root node, according to root node, and the position of source node and destination node, select transmission path to complete the transmission of described packet;
Arrive destination node module, for when described packet arrives node, check that whether the address of node of arrival is identical with the address of described destination node, if identical, then described packet arrives described destination node, otherwise circulation performs described Hamilton routing algorithm module or described spanning tree algorithm module, until packet arrives destination node.
Described judge module comprises:
If the Hamilton path of existence anduniquess in described irregular three dimensional integrated circuits network-on-chip, then select the execution of described unique Hamilton path based on the Fault-tolerant Routing Algorithm in Hamilton path; If there are many Hamilton paths in described irregular three dimensional integrated circuits network-on-chip, then in described many Hamilton paths, select one arbitrarily, perform the Fault-tolerant Routing Algorithm based on Hamilton path; If do not find Hamilton path in network, then adopt the Fault-tolerant Routing Algorithm route data packets based on spanning tree.
In described Hamilton routing algorithm module by the node in described irregular three dimensional integrated circuits network-on-chip according to the order number consecutively on Hamilton path.
Root node described in described spanning tree algorithm module meets:
1) K
rbe positioned on L layer, wherein
k
rfor described root node, J is the horizontal device number of plies, and L is certain one deck horizontal device in horizontal device;
2) of described irregular three dimensional integrated circuits network-on-chip is established
layer there is I node, is numbered the present node p of p in its middle level, 0≤p≤I-1, if Δ
pifor the shortest leapfrog number of the node of i-th in present node p and layer except node p, then K
rnode p is removed with the shortest average leapfrog number of exterior node for N in distance layer
r, N
rfor:
Described spanning tree algorithm module also comprises:
Be always into, be always out to, first enter to going out again and select transmission path to complete the transmission of packet in these three kinds of transmission directions.Packet carries out in transmitting procedure in the spanning tree determining root node, makes packet often through a node all nearlyer steps of distance destination node.
Also comprise: if the next-hop node in described Hamilton routing algorithm module or described spanning tree algorithm module is not unique, then according to DP-3D mechanism, obtain the flow sensing situation of each legal port of present node, the legal port selecting flow minimum exports, reduce the probability of message transition collision, avoid hot spot region.
Be described specific embodiments of the invention above and illustrate, it is exemplary that these embodiments should be considered to it, and is not used in and limits the invention, and the present invention should make an explanation according to appended claim.
Claims (12)
1., towards a method for routing for irregular three dimensional integrated circuits network-on-chip, it is characterized in that, comprising:
Step 1, according to the topological structure of described irregular three dimensional integrated circuits network-on-chip, judges to adopt based on the Fault-tolerant Routing Algorithm route data packets in Hamilton path, or based on the Fault-tolerant Routing Algorithm route data packets of spanning tree;
Step 2, according to the Fault-tolerant Routing Algorithm route data packets based on described Hamilton path, position according to source node and destination node is determined to use the order according to node serial number monotone increasing or monotonic decreasing to carry out router operating system, described packet carries out in transmitting procedure along the Hamilton path chosen, and makes packet often through a node all nearlyer steps of distance destination node;
Step 3, according to the Fault-tolerant Routing Algorithm route data packets based on described spanning tree, then selects spanning-tree root node, according to root node, and the position of source node and destination node, select transmission path to complete the transmission of described packet;
Step 4, when described packet arrives node, check that whether the address of node of arrival is identical with the address of described destination node, if identical, then described packet arrives described destination node, otherwise circulation performs step 2 or 3, until packet arrives destination node.
2., as claimed in claim 1 towards the method for routing of irregular three dimensional integrated circuits network-on-chip, it is characterized in that, described step 1 comprises:
If the Hamilton path of existence anduniquess in described irregular three dimensional integrated circuits network-on-chip, then select the execution of described unique Hamilton path based on the Fault-tolerant Routing Algorithm in Hamilton path; If there are many Hamilton paths in described irregular three dimensional integrated circuits network-on-chip, then in described many Hamilton paths, select one arbitrarily, perform the Fault-tolerant Routing Algorithm based on Hamilton path; If do not find Hamilton path in network, then adopt the Fault-tolerant Routing Algorithm route data packets based on spanning tree.
3., as claimed in claim 1 towards the method for routing of irregular three dimensional integrated circuits network-on-chip, it is characterized in that, in described step 2 by the node in described irregular three dimensional integrated circuits network-on-chip according to the order number consecutively on Hamilton path.
4. as claimed in claim 1 towards the method for routing of irregular three dimensional integrated circuits network-on-chip, it is characterized in that, root node described in described step 3 meets:
1) K
rbe positioned on L layer, wherein
k
rfor described root node, J is the horizontal device number of plies, and L is certain one deck horizontal device in horizontal device;
2) of described irregular three dimensional integrated circuits network-on-chip is established
layer there is I node, is numbered the present node p of p in its middle level, 0≤p≤I-1, if Δ
pifor the shortest leapfrog number of the node of i-th in present node p and layer except node p, then K
rnode p is removed with the shortest average leapfrog number of exterior node for N in distance layer
r, N
rfor:
5., as claimed in claim 1 towards the method for routing of irregular three dimensional integrated circuits network-on-chip, it is characterized in that, described step 3 also comprises:
Be always into, be always out to, first enter to going out again and select transmission path to complete the transmission of packet in these three kinds of transmission directions.Packet carries out in transmitting procedure in the spanning tree determining root node, makes packet often through a node all nearlyer steps of distance destination node.
6. as claimed in claim 1 towards the method for routing of irregular three dimensional integrated circuits network-on-chip, it is characterized in that, also comprise: if the next-hop node in described step 2 or described step 3 is not unique, then according to DP-3D mechanism, obtain the flow sensing situation of each legal port of present node, the legal port selecting flow minimum exports, and reduces the probability of message transition collision, avoids hot spot region.
7., towards a route system for irregular three dimensional integrated circuits network-on-chip, it is characterized in that, comprising:
Judge module, for the topological structure according to described irregular three dimensional integrated circuits network-on-chip, judges to adopt based on the Fault-tolerant Routing Algorithm route data packets in Hamilton path, or based on the Fault-tolerant Routing Algorithm route data packets of spanning tree;
Hamilton routing algorithm module, for according to the Fault-tolerant Routing Algorithm route data packets based on described Hamilton path, position according to source node and destination node is determined to use the order according to node serial number monotone increasing or monotonic decreasing to carry out router operating system, described packet carries out in transmitting procedure along the Hamilton path chosen, and makes packet often through a node all nearlyer steps of distance destination node;
Spanning tree algorithm module, for according to the Fault-tolerant Routing Algorithm route data packets based on described spanning tree, then selects spanning-tree root node, according to root node, and the position of source node and destination node, select transmission path to complete the transmission of described packet;
Arrive destination node module, for when described packet arrives node, check that whether the address of node of arrival is identical with the address of described destination node, if identical, then described packet arrives described destination node, otherwise circulation performs described Hamilton routing algorithm module or described spanning tree algorithm module, until packet arrives destination node.
8., as claimed in claim 7 towards the route system of irregular three dimensional integrated circuits network-on-chip, it is characterized in that, described judge module comprises:
If the Hamilton path of existence anduniquess in described irregular three dimensional integrated circuits network-on-chip, then select the execution of described unique Hamilton path based on the Fault-tolerant Routing Algorithm in Hamilton path; If there are many Hamilton paths in described irregular three dimensional integrated circuits network-on-chip, then in described many Hamilton paths, select one arbitrarily, perform the Fault-tolerant Routing Algorithm based on Hamilton path; If do not find Hamilton path in network, then adopt the Fault-tolerant Routing Algorithm route data packets based on spanning tree.
9. as claimed in claim 7 towards the route system of irregular three dimensional integrated circuits network-on-chip, it is characterized in that, in described Hamilton routing algorithm module by the node in described irregular three dimensional integrated circuits network-on-chip according to the order number consecutively on Hamilton path.
10. as claimed in claim 7 towards the route system of irregular three dimensional integrated circuits network-on-chip, it is characterized in that, root node described in described spanning tree algorithm module meets:
1) K
rbe positioned on L layer, wherein
k
rfor described root node, J is the horizontal device number of plies, and L is certain one deck horizontal device in horizontal device;
2) of described irregular three dimensional integrated circuits network-on-chip is established
layer there is I node, is numbered the present node p of p in its middle level, 0≤p≤I-1, if Δ
pifor the shortest leapfrog number of the node of i-th in present node p and layer except node p, then K
rnode p is removed with the shortest average leapfrog number of exterior node for N in distance layer
r, N
rfor:
11. as claimed in claim 7 towards the route system of irregular three dimensional integrated circuits network-on-chip, and it is characterized in that, described spanning tree algorithm module also comprises:
Be always into, be always out to, first enter to going out again and select transmission path to complete the transmission of packet in these three kinds of transmission directions.Packet carries out in transmitting procedure in the spanning tree determining root node, makes packet often through a node all nearlyer steps of distance destination node.
12. as claimed in claim 7 towards the route system of irregular three dimensional integrated circuits network-on-chip, it is characterized in that, also comprise: if the next-hop node in described Hamilton routing algorithm module or described spanning tree algorithm module is not unique, then according to DP-3D mechanism, obtain the flow sensing situation of each legal port of present node, the legal port selecting flow minimum exports, and reduces the probability of message transition collision, avoids hot spot region.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201610057261.6A CN105577539B (en) | 2016-01-27 | 2016-01-27 | A kind of method for routing and system towards irregular three dimensional integrated circuits network-on-chip |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201610057261.6A CN105577539B (en) | 2016-01-27 | 2016-01-27 | A kind of method for routing and system towards irregular three dimensional integrated circuits network-on-chip |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN105577539A true CN105577539A (en) | 2016-05-11 |
| CN105577539B CN105577539B (en) | 2018-08-10 |
Family
ID=55887227
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201610057261.6A Active CN105577539B (en) | 2016-01-27 | 2016-01-27 | A kind of method for routing and system towards irregular three dimensional integrated circuits network-on-chip |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN105577539B (en) |
Cited By (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107104909A (en) * | 2017-05-10 | 2017-08-29 | 华南理工大学 | The special network-on-chip Topology g eneration method of fault tolerant |
| CN107797541A (en) * | 2016-08-29 | 2018-03-13 | 河北百亚信息科技有限公司 | The light decompression algorithm of image file based on ZigBee firmware upgrades in smart home environment |
| CN112511924A (en) * | 2020-10-28 | 2021-03-16 | 河北电信设计咨询有限公司 | PeOTN network routing planning method based on service demand |
| CN114185844A (en) * | 2021-12-07 | 2022-03-15 | 浙江大学 | On-chip network fault-tolerant routing method suitable for power edge calculation |
| CN114666008A (en) * | 2022-03-10 | 2022-06-24 | 清华大学 | Data transmission method and device, computer equipment and storage medium |
| CN114844827A (en) * | 2022-05-05 | 2022-08-02 | 浙江大学 | Shared storage-based spanning tree routing hardware architecture and method for network-on-chip |
Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP1475927A2 (en) * | 2003-05-09 | 2004-11-10 | Samsung Electronics Co., Ltd. | Apparatus and method for setting up of optimum route using tree-topology |
| CN103986664A (en) * | 2014-05-15 | 2014-08-13 | 厦门大学 | Mixed interconnection Mesh topological structure for on-chip network and routing algorithm thereof |
| CN104079480A (en) * | 2014-05-30 | 2014-10-01 | 中国科学院计算技术研究所 | Routing method and system of network on three-dimensional integrated circuit chip |
| CN104092617A (en) * | 2014-05-30 | 2014-10-08 | 中国科学院计算技术研究所 | Three-dimensional integrated circuit on-chip network routing method and system thereof |
| CN105072032A (en) * | 2015-09-17 | 2015-11-18 | 浪潮(北京)电子信息产业有限公司 | Method and system for determining routing path of network on chip |
-
2016
- 2016-01-27 CN CN201610057261.6A patent/CN105577539B/en active Active
Patent Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP1475927A2 (en) * | 2003-05-09 | 2004-11-10 | Samsung Electronics Co., Ltd. | Apparatus and method for setting up of optimum route using tree-topology |
| CN103986664A (en) * | 2014-05-15 | 2014-08-13 | 厦门大学 | Mixed interconnection Mesh topological structure for on-chip network and routing algorithm thereof |
| CN104079480A (en) * | 2014-05-30 | 2014-10-01 | 中国科学院计算技术研究所 | Routing method and system of network on three-dimensional integrated circuit chip |
| CN104092617A (en) * | 2014-05-30 | 2014-10-08 | 中国科学院计算技术研究所 | Three-dimensional integrated circuit on-chip network routing method and system thereof |
| CN105072032A (en) * | 2015-09-17 | 2015-11-18 | 浪潮(北京)电子信息产业有限公司 | Method and system for determining routing path of network on chip |
Cited By (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107797541A (en) * | 2016-08-29 | 2018-03-13 | 河北百亚信息科技有限公司 | The light decompression algorithm of image file based on ZigBee firmware upgrades in smart home environment |
| CN107104909A (en) * | 2017-05-10 | 2017-08-29 | 华南理工大学 | The special network-on-chip Topology g eneration method of fault tolerant |
| CN107104909B (en) * | 2017-05-10 | 2021-06-08 | 华南理工大学 | Fault-tolerant special network-on-chip topology generation method |
| CN112511924A (en) * | 2020-10-28 | 2021-03-16 | 河北电信设计咨询有限公司 | PeOTN network routing planning method based on service demand |
| CN112511924B (en) * | 2020-10-28 | 2022-11-04 | 河北电信设计咨询有限公司 | PeOTN network routing planning method based on service demand |
| CN114185844A (en) * | 2021-12-07 | 2022-03-15 | 浙江大学 | On-chip network fault-tolerant routing method suitable for power edge calculation |
| CN114185844B (en) * | 2021-12-07 | 2024-04-26 | 浙江大学 | Network-on-chip fault-tolerant routing method suitable for power edge calculation |
| CN114666008A (en) * | 2022-03-10 | 2022-06-24 | 清华大学 | Data transmission method and device, computer equipment and storage medium |
| CN114844827A (en) * | 2022-05-05 | 2022-08-02 | 浙江大学 | Shared storage-based spanning tree routing hardware architecture and method for network-on-chip |
Also Published As
| Publication number | Publication date |
|---|---|
| CN105577539B (en) | 2018-08-10 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN105577539A (en) | Routing method and system for non-regular three-dimensional integrated circuit network-on-chip | |
| CN104539547B (en) | A kind of router and method for routing for three dimensional integrated circuits network-on-chip | |
| CN103986664B (en) | A kind of mixing for network-on-chip interconnects Mesh topological structures and its routing algorithm | |
| CN101808032B (en) | Static XY routing algorithm-oriented two-dimensional grid NoC router optimization design method | |
| Liu et al. | Fault-tolerant networks-on-chip routing with coarse and fine-grained look-ahead | |
| CN101778049A (en) | Router and transmission method thereof on packet-circuit switching chip | |
| CN102387077B (en) | Network path selection method for heat balance sheet with fault tolerance function | |
| CN101834780B (en) | Method for optimizing topological structure and mapping of network on chip | |
| CN102882783B (en) | Based on topological structure, the method for routing of the network-on-chip of the three dimensional integrated circuits of TSV | |
| CN107612746A (en) | A kind of method, Torus networks and the routing algorithm of structure Torus networks | |
| CN105119833B (en) | It is a kind of for the mixing interconnection structure of network-on-chip, its network node coding method and its mixed logic dynamic algorithm | |
| CN104092617B (en) | A kind of three dimensional integrated circuits network-on-chip method for routing and its system | |
| CN104579951B (en) | Novel failure and the fault-tolerance approach under congestion model in network-on-chip | |
| CN102761475A (en) | Internetwork-on-chip fault-tolerance routing method based on channel dependency graphs | |
| CN102780628B (en) | On-chip interconnection network routing method oriented to multi-core microprocessor | |
| CN104079480B (en) | A kind of method for routing and its system of three dimensional integrated circuits network-on-chip | |
| CN103036787A (en) | Network route convergence processing method and network route convergence processing device | |
| CN109587048A (en) | It is a kind of with balance policy without Virtual Channel Fault-tolerant Routing Algorithm | |
| CN101262444A (en) | Routing method for avoiding dead lock in fault tolerance mesh based on channel overlapping | |
| CN101267394A (en) | No dead lock plane self-adapted routing method in 3-D mesh | |
| CN101242372A (en) | Non lock routing method for k-element N-dimension mesh | |
| CN105530206A (en) | Torus network based dual-access structures and working mode thereof | |
| CN111193971A (en) | Machine learning-oriented distributed computing interconnection network system and communication method | |
| CN101488923A (en) | Implementing method for network-on-chip data packet encoding optimization | |
| CN107171954A (en) | Fault tolerance rout ing method, device and network-on-chip |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| CB03 | Change of inventor or designer information | ||
| CB03 | Change of inventor or designer information |
Inventor after: Li Xiaowei Inventor after: Zhou Jun Inventor after: Li Huawei Inventor before: Zhou Jun Inventor before: Li Huawei Inventor before: Li Xiaowei |
|
| GR01 | Patent grant | ||
| GR01 | Patent grant | ||
| EE01 | Entry into force of recordation of patent licensing contract | ||
| EE01 | Entry into force of recordation of patent licensing contract |
Application publication date: 20160511 Assignee: Zhongke Jianxin (Beijing) Technology Co.,Ltd. Assignor: Institute of Computing Technology, Chinese Academy of Sciences Contract record no.: X2022990000752 Denomination of invention: A Routing Method and System for Irregular 3D Integrated Circuit Network on Chip Granted publication date: 20180810 License type: Exclusive License Record date: 20221009 |