[go: up one dir, main page]

WO2015196461A1 - Deadlock-free adaptive routing of interconnect network - Google Patents

Deadlock-free adaptive routing of interconnect network Download PDF

Info

Publication number
WO2015196461A1
WO2015196461A1 PCT/CN2014/080973 CN2014080973W WO2015196461A1 WO 2015196461 A1 WO2015196461 A1 WO 2015196461A1 CN 2014080973 W CN2014080973 W CN 2014080973W WO 2015196461 A1 WO2015196461 A1 WO 2015196461A1
Authority
WO
WIPO (PCT)
Prior art keywords
router
routers
routing
gjr
group
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.)
Ceased
Application number
PCT/CN2014/080973
Other languages
French (fr)
Inventor
Dong Xiang
Xiaowei Liu
Zhigang Yu
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Tsinghua University
Original Assignee
Tsinghua University
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Tsinghua University filed Critical Tsinghua University
Priority to PCT/CN2014/080973 priority Critical patent/WO2015196461A1/en
Publication of WO2015196461A1 publication Critical patent/WO2015196461A1/en
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/28—Data switching networks characterised by path configuration, e.g. LAN [Local Area Networks] or WAN [Wide Area Networks]
    • H04L12/46—Interconnection of networks
    • H04L12/4641—Virtual LANs, VLANs, e.g. virtual private networks [VPN]

Definitions

  • the present invention relates to distributed computing, and more particularly, to an interconnect network and adaptive routing algorithm.
  • An interconnection network is used to implement synchronizing and communicating among different process nodes, and is an important component in multiprocessor systems for connecting the processors, memory modules and I/O devices.
  • the interconnection network is a critical aspect that may significantly impact the overall performance and scalability of multi-processor systems. In view of the prior art, it is a key requirement for interconnection networks to provide low latency, high efficiency communication among process nodes.
  • serial channel becomes an effective selection of signal transmission.
  • High-speed serial channel may highly increase the bandwidth of a single pin, and thus the number of pin of a router chip may be cut down.
  • the bandwidth of pins of a router is limited within lOGbps, which reaches to 10-20Tbps in 21st century.
  • the use of high-radix routers is becoming a tendency of interconnection networks.
  • the interconnect networks constructed by high-radix routers may connect tens of thousands of processors with several hops, and usually have shorter network diameter as well as smaller message latency and lower cost, and therefore can realize high efficiency communication among process nodes and improve the system performance.
  • the Black Widow system from the Cray Corporation firstly employs radix-64 router chips and provides interconnection among 32000 processors with Clos topology, which guarantees that any two nodes can communicate within 7 hops.
  • the Cascade system from the Cray Corporation utilizes radix-48 router chips and provides interconnection among 370216 processors with dragonfly architectures, which guarantees that any two nodes can communicate within 5 hops.
  • Cray Cascade requires 4 virtual channels to provide deadlock-free adaptive routing.
  • Blackwidow Clos network is the first network using high-radix routers. But it has a high cost and a long network diameter, which has a bad impact on the system performance.
  • Cascade Dragonfly network also uses high-radix routers, with high scalability and low cost features, and has a short network diameter. But it requires 4 virtual channels to avoid deadlocks, which increases the router design complexity and message latency, and limits the system performance.
  • the interconnection network and adaptive routing algorithm not only maintain low cost, high scalability, and short network diameter feature of the existing dragonfly network, but require no virtual channels to achieve fully deadlock-free adaptive routing algorithm.
  • the present invention provides an interconnect network, wherein the routers in the system are divided into n groups of routers, each group of routers contains one or more routers, with achieving full connectivity among the n group of routers, so that the communication between any two groups of routers only requires one hop, wherein n is an integer greater than or equal to 1 ;
  • the connection algorithm among router groups complies the following principles:
  • PI label the routers in the interconnection network, wherein n groups of routers are sequentially labeled G 0 , G 1; G n-1 , and m routers in the group are sequentially labeled 0 , R 1; R m -i;
  • P3 for i from 0 to n-3, for j from i+2 to n-1, connect the router R v in group Gj with the router Ry in group G j , wherein v is the highest available slot in group Gj and v' is the lowest available slot in group G j for the global connection.
  • each group of routers comprises m routers, wherein m is an integer greater than or equal to one.
  • each router in the network comprises a local ports, p processor ports and g global ports; wherein the a local ports are to achieve the interconnection among the routers within a router group, the corresponding channels are local interconnected channels; wherein the p processors ports interconnects processor nodes with routers; wherein the g global ports interconnects among the groups of routers, and the corresponding interconnected channels are global channels.
  • a partially adaptive routing algorithm of interconnect network which comprises the steps of:
  • a unidirectional channel can be classified as minus and plus directions
  • the partially adaptive routing algorithm when classified channels to label minus direction or label plus direction in step S2, should comply with the following principles:
  • the channel is defined as label minus direction
  • the channel is defined as label plus direction
  • the channel is defined as label minus direction
  • the channel is defined as label plus direction.
  • step S2 comprises the following steps:
  • G x R f for m ⁇ x, only when j ⁇ c and f > y, misroute the packet to G m ; for x ⁇ m ⁇ i, only when j ⁇ c and d ⁇ e, misroute the packet to G m ;
  • a fully adaptive routing algorithm on interconnect network which comprises the steps of:
  • Dl according to the channel type used by the next hop of message packet, classify the message package into safe package or unsafe package; if routing channel used by the message packet to the next hop complies with the principle of minus direction-first routing, the packet is a safe package for the router of the next hop; otherwise, it is an unsafe package;
  • D2 set channel buffer with a size of bw ⁇ packets, which can store buff message packets at most, wherein buff is greater than or equal to 2;
  • the channels should be considered separately.
  • message packages are divided into safe packages and unsafe packages in step Dl .
  • Unsafe packets which do not comply with the flow control principle can be routed with the partial algorithm, and then the unsafe packets can be converted into safe packets. Otherwise, the unsafe packets should wait route process until they comply with the flow control principle so that they can route according to minimal path algorithm.
  • the present invention provides a novel interconnection network; the interconnection network not only keeps the low cost, high scalability, short network diameter of the original dragonfly network, but also is conducive to implementing the adaptive routing algorithm proposed by the present invention.
  • the present invention proposes an adaptive routing algorithm based on the novel interconnection network, through labeling the interconnection network routers, and using specific label minus direction first or label plus direction first principle, this algorithm does not require virtual channel to achieving deadlock-free adaptive routing, and guarantees that communication steps between any processor nodes no more than five hops. Because the interconnection network and its adaptive routing algorithm can achieve deadlock-free without using virtual channel, which avoids the virtual channel distribution mechanism, the interconnection network and routing algorithm of the present invention can greatly simplify router design, reduce message latency and improve network performance.
  • the invention further proposes fully adaptive routing method, with using of free deadlock characteristics of the part adaptive routing method of the invention, supplemented by a new flow control mechanism, fully adaptive deadlock-free routing can be obtained.
  • the fully adaptive routing algorithm allows all messages reach the destination node router through the minimal path that effectively improve channel utilization, and network throughput.
  • the flow control mechanism can apply to all virtual channels switching network, which can implement fully adaptive routing without virtual channel.
  • FIG.1 is a block diagram of an example embodiment of the interconnection network.
  • FIG.2 is a block diagram of an example embodiment of connection of the interconnection network.
  • FIG.3 is a flow diagram of an example embodiment of the step S3 in the partially adaptive routing algorithm.
  • FIG.4 is a schematic diagram of an example embodiment of hopping in partially adaptive deadlock free routing algorithm.
  • FIG.5 is a schematic diagram illustrating the process of the partially deadlock free adaptive routing algorithm.
  • FIG.6 (a) is a block diagram illustrating a routing algorithm which generate deadlock.
  • FIG.6 (b) is a block diagram illustrating a deadlock caused by cyclic dependency.
  • FIG.6 (c) is a block diagram illustrating eliminating deadlock according to the label minus first principle.
  • FIG.7 is a flow diagram of an example embodiment of the partially adaptive routing algorithm.
  • FIG.8 is a flow diagram of an example embodiment of the fully adaptive routing algorithm.
  • FIG.9 is a block diagram illustrating the router label of the partially adaptive routing algorithm.
  • the invention provides an interconnect network system, wherein the routers in the system are divided into n groups of routers, with achieving full connectivity among the n groups of routers, so that the communication between any two groups of routers only requires one hop, wherein n is an integer greater than or equal to 1 ; each router group contains one or more routers, with full connecting among the routers in the group, so that the distance between any two routers in the group is only one hop; the following are steps of the connection algorithm among groups of routers :
  • PI label the interconnection network routers, wherein n groups of routers are sequentially labeled G 0 , G 1; G n-1 , m routers in a group are sequentially labeled 0 , R 1; R m -i;
  • P3 for i from 0 to n-3, and j from i+2 to n-1, connect R v within Gj with R V ' within G j , wherein v is the highest available slot in Gj and v' is the lowest available slot in G j .
  • each group of routers may be set including m routers, wherein m is greater than or equal to one.
  • routers within a group of routers achieve fully connection, ensuring that distance of any two routers within a group is one hop.
  • Groups of router also achieve fully connection, ensuring that there must be a global channel between any two groups of routers.
  • the present invention proposes a partially adaptive routing algorithm of interconnect network, comprising the steps of:
  • a unidirectional channel can be classified as minus direction and plus direction;
  • the message packet comply the label minus first direction when forward message package in step 3 of the embodiment of the algorithm invention.
  • an example embodiment of the partially adaptive routing which comply the label minus first direction should comprise the following steps:
  • the present invention proposed a fully adaptive routing algorithm of interconnect network, comprising the following steps:
  • Dl according to the channel type used by the next hop of message packet, classify the message package into safe package or unsafe package according to the following principles: if routing channel used by the message packet to the next hop complies with the principle of minus direction-first routing, the packet is a safe package for the router of the next hop; otherwise, it is an unsafe package;
  • D2 set channel buffer with a size of bw ⁇ packets, which can store buff message packets at most, wherein buffi?, greater than or equal to 2;
  • Figure 4 shows two example embodiments of the partially routing algorithm of the present application, which respectively are (source router node G 0 Ri, destination router node G 3 Ri) and (source router node G 3 R 1; destination router node G 0 Ri), based on the label minus direction first partially adaptive deadlock free routing algorithm, providing the following routing:
  • the routing path is: (G0R1, G2R1) -> (G2R1, G 2 R 2 ) -> (G 2 R 2 , G 3 R 0 ) -> (G3R0, G3R1);
  • the routing path is: (G3R1, G3R0) -> (G3R0, G 2 R 2 ) -> (G 2 R 2 , G2R1) -> (G2R1, G0R1).
  • Figure 5 shows the label minus first direction always ensures that message packet can arrive at the destination router node in five hops for any two router nodes according to the interconnection network system and the partially adaptive routing algorithm of the present invention.
  • GjR j is source node router
  • G x R y is destination node router.
  • the deadlock free partially routing algorithm always provides routing path: (GjR j , GjR c ) -> (GjR c , G x-1 R d ) -> (G x-1 R d , Gx-iRm a x) -> (Gx-iRm a x, G x Ro) -> (G x Ro, G x R y );
  • the deadlock free partially routing algorithm always provides routing path: (GjR j , GiR 0 ) -> (GjRo, G ⁇ R ⁇ ) -> (G ⁇ R ⁇ , Gi.jR d ) -> (Gi.jRd, G X R C ) -> (G x R c , G x R y ).
  • the max subscript means the max label router within a router group.
  • the reason that the partially routing algorithm proposed by the present invention can avoid deadlock is: consider the four necessary conditions for deadlock: resource mutex, request and hold, non-preemptive, and circular wait. Therefore, using the label minus first direction, by eliminating the circular wait, deadlock can be avoided.
  • a routing algorithm in figure 6 (a) generates a deadlock is showed in figure 6 (b). After restricting some waiting paths, the circular dependency is eliminated and deadlock is avoided as shown in figure 6 (c). Therefore, the embodiment of the partially adaptive routing algorithm proposed by the present invention can implement an adaptive routing in interconnection network without using virtual channels.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

The present invention discloses a novel interconnect network system. The system divides the routers in the system into n groups, and n groups of routers achieve full connectivity. Each group contains one or more routers; and routers within a group achieve full connectivity. The present invention also provides an adaptive routing method based on the new interconnect network, by labeling the routers in the system, and using label minus hops first or label plus hops algorithm, deadlock-free adaptive routing can be achieved without using any virtual channel, and hops between any two routers can be ensured no more than five steps. The invention also proposes a fully adaptive routing scheme. With the deadlock free characteristic of partially adaptive routing algorithm of the invention, in combination with a new flow control mechanism, deadlock free full adaptive routing can be achieved.

Description

Deadlock-free adaptive routing of interconnect network
Field of the Invention
The present invention relates to distributed computing, and more particularly, to an interconnect network and adaptive routing algorithm.
Background of the Invention
An interconnection network is used to implement synchronizing and communicating among different process nodes, and is an important component in multiprocessor systems for connecting the processors, memory modules and I/O devices. The interconnection network is a critical aspect that may significantly impact the overall performance and scalability of multi-processor systems. In view of the prior art, it is a key requirement for interconnection networks to provide low latency, high efficiency communication among process nodes.
Development of microprocessor technology has made computing capacity of a single processing node increasing rapidly, which also brings about higher requirements for the performance of the interconnection network. In fact, bandwidth increase of the interconnection network has a 30% disparity from performance increase of microprocessors. Therefore, the latency and bandwidth of interconnection network have become the bottleneck of performance improvement of multiprocessor systems.
As the development of semiconductor industry and the improvement of electrical circuits, serial channel becomes an effective selection of signal transmission. High-speed serial channel may highly increase the bandwidth of a single pin, and thus the number of pin of a router chip may be cut down. In the early 1990s, the bandwidth of pins of a router is limited within lOGbps, which reaches to 10-20Tbps in 21st century. These improvements enable the implementing of high-radix routers.
The use of high-radix routers is becoming a tendency of interconnection networks. The interconnect networks constructed by high-radix routers may connect tens of thousands of processors with several hops, and usually have shorter network diameter as well as smaller message latency and lower cost, and therefore can realize high efficiency communication among process nodes and improve the system performance.
In 2006, the Black Widow system from the Cray Corporation firstly employs radix-64 router chips and provides interconnection among 32000 processors with Clos topology, which guarantees that any two nodes can communicate within 7 hops. In 2012, the Cascade system from the Cray Corporation utilizes radix-48 router chips and provides interconnection among 370216 processors with dragonfly architectures, which guarantees that any two nodes can communicate within 5 hops. However, Cray Cascade requires 4 virtual channels to provide deadlock-free adaptive routing.
According to the existing chip technology and high-radix router technology, how to design a highly efficient network interconnection topology and efficient routing algorithms has become a new urgent research topic. Blackwidow Clos network is the first network using high-radix routers. But it has a high cost and a long network diameter, which has a bad impact on the system performance. Cascade Dragonfly network also uses high-radix routers, with high scalability and low cost features, and has a short network diameter. But it requires 4 virtual channels to avoid deadlocks, which increases the router design complexity and message latency, and limits the system performance.
Summary of the Invention
Technical problems to be solved
Technical problems solved by the present invention are: providing an interconnection network based on router label and its corresponding adaptive routing algorithm. The interconnection network and adaptive routing algorithm not only maintain low cost, high scalability, and short network diameter feature of the existing dragonfly network, but require no virtual channels to achieve fully deadlock-free adaptive routing algorithm.
The technical solutions
To solve the technical problem above, the present invention provides an interconnect network, wherein the routers in the system are divided into n groups of routers, each group of routers contains one or more routers, with achieving full connectivity among the n group of routers, so that the communication between any two groups of routers only requires one hop, wherein n is an integer greater than or equal to 1 ; the connection algorithm among router groups complies the following principles:
PI : label the routers in the interconnection network, wherein n groups of routers are sequentially labeled G0, G1; Gn-1, and m routers in the group are sequentially labeled 0, R1; Rm-i;
P2: for i from 0 to n-2, connect the router Rm-1 in group Gj to the router Ro in group Gi+1;
P3: for i from 0 to n-3, for j from i+2 to n-1, connect the router Rv in group Gj with the router Ry in group Gj, wherein v is the highest available slot in group Gj and v' is the lowest available slot in group Gj for the global connection.
Preferably, each group of routers comprises m routers, wherein m is an integer greater than or equal to one.
Preferably, each router in the network comprises a local ports, p processor ports and g global ports; wherein the a local ports are to achieve the interconnection among the routers within a router group, the corresponding channels are local interconnected channels; wherein the p processors ports interconnects processor nodes with routers; wherein the g global ports interconnects among the groups of routers, and the corresponding interconnected channels are global channels.
Preferably, each group of routers includes m=a+l routers, the number of groups of routers is n = mg +1 , which means that each group contains k - m (p + g) ports.
In another aspect of the invention, a partially adaptive routing algorithm of interconnect network is provided, which comprises the steps of:
SI : label the interconnection network routers, wherein n groups of routers are sequentially labeled G0, G1; Gn-1, and m routers in the groups are sequentially labeled 0, R1; Rm-i; interconnect the highest labeled router GsRm-1 in any group of routers Gs with the lowest labeled router GtRo in group of routers Gt during labeling, wherein t= (s+1) mod n, i.e., t is the remainder of dividing s+1 by n; interconnect the highest labeled router GuRm-1 in group of routers Gu with the lowest labeled router GsRo in group of routers Gs during labeling, wherein u= (s-1) mod n, i.e., u is the remainder of dividing s-1 by n;
S2: according to the label of routers at each end of the channel, a unidirectional channel can be classified as minus and plus directions;
S3 : when routing a message packet, all the paths should comply with the principle of minus-first routing that all routing paths from the source router to the destination router comprise w minus direction paths followed by v plus direction paths; or all the paths should comply with the principle of plus-first routing that all routing paths from the source router to the destination router comprise w plus direction paths followed by v minus direction paths.
Preferably, the partially adaptive routing algorithm, when classified channels to label minus direction or label plus direction in step S2, should comply with the following principles:
For any channel (GuRji, GxlRyl),
If il > xl, the channel is defined as label minus direction;
If il < xl, the channel is defined as label plus direction;
If il = xl and j l > yl, the channel is defined as label minus direction;
If il = xl and j l < yl, the channel is defined as label plus direction.
Preferably, in the partially adaptive routing algorithm complies with the principle of label minus direction-first routing when routing message package in step S3. Preferably, step S2 comprises the following steps:
S31 : When routing a message packet, set the router of the current node as GjRj, and the router of destination node as GxRy, Ch is an available set of message packet output channels, which has an initial value of empty set 0, compare the group label i of the router of the current node with the group label x of the router of the destination node, if i = x, go to step S32 if i < x, go to step S33, otherwise go to step S34;
S32: check whether the router of the current node is the router of the destination node, if the router of the current node is the router of the destination node, i.e., i = x and j = y, the message packet has reached the destination node by the router, and the algorithm ends; otherwise, if i = x and j≠ y, providing local channel (GjRj, GxRy) so that the message packet can be delivered to the router of destination node, Ch = Ch + {(GiRj, GxRy)}, return Ch;
S33: assume router GjRa in the group of routers of the current node and router GxRb in the group of routers of the destination node are connected;
If b > y and a≠ j, then provide routing channel from GjRj to GjRa, Ch = Ch + {(GiRj, GiRa)} ;
If b < y, set router GjRc in the group of routers of the current node connecting with the router GmRd and the router GmRe connecting with the router GxRf;
For m < i, only when j < c and f > y, misroute the packet to Gm;
For i < m < x, only when j < c and d < e, misroute the packet to Gm;
If c≠ j, provide router channel from GjRj to GjRc, Ch = Ch + {(GjRj,
If c = j , provide router channel from GjRj to GmRd, Ch = Ch + {(GjRj, GmRd)}, return Ch;
S34: assume router GjRa in the group of routers of the current node and router Gx¾ in the group of routers of the destination node are connected;
If a < j, provide routing channel from GjRj to GjRa, Ch = Ch + {(GjRj,
If a = j, provide routing channel from GjRj to GxRb, Ch = Ch + {(GjRj, GxRb)} ;
If a > j, set router GjRc in the group of routers of the current node connecting with router GmRd and router GmRe connecting with router
GxRf; for m < x, only when j < c and f > y, misroute the packet to Gm; for x < m < i, only when j < c and d < e, misroute the packet to Gm;
If c≠ j , provide router channel from GjRj to GjRc, Ch = Ch + {(GiRj, GiRc)} ;
If c = j, provide router channel from GjRj to GmRd, Ch = Ch + {(GiRj, GmRd)}, return Ch.
In another aspect of the invention, a fully adaptive routing algorithm on interconnect network is provided, which comprises the steps of:
Dl : according to the channel type used by the next hop of message packet, classify the message package into safe package or unsafe package; if routing channel used by the message packet to the next hop complies with the principle of minus direction-first routing, the packet is a safe package for the router of the next hop; otherwise, it is an unsafe package;
D2: set channel buffer with a size of bw^ packets, which can store buff message packets at most, wherein buff is greater than or equal to 2;
D3: set the router of the current node as GjRj, and the router of the destination node as GxRy, Chi is a set including all the routing channels for message packets which comply the principle of minus direction-first; if i = x and j = y, the packet has reached the destination node, so the routing process ends; otherwise, invoke the partially adaptive routing algorithm of interconnect network stated above to provide set of channels Chi which comply the principle of minus direction-first for message packets;
D4: set the router of the current node as GjRj, and the router of the destination node as Gx y, Ch2 is a set including all the routing channels for message packets which comply minimal routing; if i = x and j = y, the message packet has arrived at the destination node, so the routing process ends; if i = x and j≠ y, Ch2 = {(GjRj, GxRy)} ; if i≠ x, set router Gx¾ in the current group of routers and the router GjRa in the destination group are connected; if a≠ j, provide routing channel from router GjRj to router GjRa, Ch2 = {(GjRj, GiRa)}, if a = j, provide routing channel from router GjRj to router GxRb, Ch2 = {(GjRj, GxRb)} ;
D5: for the set of channels Ch2 in which all the routing channels comply the minimal routing path, the channels should be considered separately. Assume the channel by which the message packages arrives the next router node according to the minimal routing path provided by Ch2 has f empty buffers, and s buffer safe packages, the message packets comply the following flow control mechanisms: if f > 1 , the message packet can be delivered to the next node with the channel included in Ch2; if f = 1 and s > 1, the message packet can be delivered to the next node with the channel included in Ch2; if f = 1 and s = 0, the message packet is the safe package for the channel to the next hop, which is included in Ch2, and the package can be delivered to the next node with the channel included in Ch2; in other cases, the packet cannot be delivered via channels included in Ch2, and then empty Ch2, i.e. Ch2 = 0;
D6: according to the routing channel set Chi provided by step D3 and the routing channel set Ch2 provided by step D5, get all the routing channels that provided by fully adaptive routing algorithm Ch3, Ch3 = Chi + Ch2, wherein packets will be routed by Claim5 if they do not comply the flow control principle; or let Ch3 = Ch2 and route them with the minimal routing path after they are converted into complying with the flow control in the next routing, return Ch3.
Preferably, message packages are divided into safe packages and unsafe packages in step Dl . Unsafe packets which do not comply with the flow control principle can be routed with the partial algorithm, and then the unsafe packets can be converted into safe packets. Otherwise, the unsafe packets should wait route process until they comply with the flow control principle so that they can route according to minimal path algorithm.
Beneficial effects
The present invention provides a novel interconnection network; the interconnection network not only keeps the low cost, high scalability, short network diameter of the original dragonfly network, but also is conducive to implementing the adaptive routing algorithm proposed by the present invention. The present invention proposes an adaptive routing algorithm based on the novel interconnection network, through labeling the interconnection network routers, and using specific label minus direction first or label plus direction first principle, this algorithm does not require virtual channel to achieving deadlock-free adaptive routing, and guarantees that communication steps between any processor nodes no more than five hops. Because the interconnection network and its adaptive routing algorithm can achieve deadlock-free without using virtual channel, which avoids the virtual channel distribution mechanism, the interconnection network and routing algorithm of the present invention can greatly simplify router design, reduce message latency and improve network performance. The invention further proposes fully adaptive routing method, with using of free deadlock characteristics of the part adaptive routing method of the invention, supplemented by a new flow control mechanism, fully adaptive deadlock-free routing can be obtained. The fully adaptive routing algorithm allows all messages reach the destination node router through the minimal path that effectively improve channel utilization, and network throughput. On the other hand, the flow control mechanism can apply to all virtual channels switching network, which can implement fully adaptive routing without virtual channel.
Brief Description of the Drawings
FIG.1 is a block diagram of an example embodiment of the interconnection network.
FIG.2 is a block diagram of an example embodiment of connection of the interconnection network.
FIG.3 is a flow diagram of an example embodiment of the step S3 in the partially adaptive routing algorithm.
FIG.4 is a schematic diagram of an example embodiment of hopping in partially adaptive deadlock free routing algorithm.
FIG.5 is a schematic diagram illustrating the process of the partially deadlock free adaptive routing algorithm.
FIG.6 (a) is a block diagram illustrating a routing algorithm which generate deadlock.
FIG.6 (b) is a block diagram illustrating a deadlock caused by cyclic dependency.
FIG.6 (c) is a block diagram illustrating eliminating deadlock according to the label minus first principle.
FIG.7 is a flow diagram of an example embodiment of the partially adaptive routing algorithm.
FIG.8 is a flow diagram of an example embodiment of the fully adaptive routing algorithm.
FIG.9 is a block diagram illustrating the router label of the partially adaptive routing algorithm.
Detailed Description of Preferred Embodiments
In the following detailed description of example embodiments of the invention, reference is made to specific examples by way of drawings and illustrations. As shown in Figure 1, the invention provides an interconnect network system, wherein the routers in the system are divided into n groups of routers, with achieving full connectivity among the n groups of routers, so that the communication between any two groups of routers only requires one hop, wherein n is an integer greater than or equal to 1 ; each router group contains one or more routers, with full connecting among the routers in the group, so that the distance between any two routers in the group is only one hop; the following are steps of the connection algorithm among groups of routers :
PI : label the interconnection network routers, wherein n groups of routers are sequentially labeled G0, G1; Gn-1, m routers in a group are sequentially labeled 0, R1; Rm-i;
P2: for i from 0 to n-2, connect the router Rm-1 in router group Gj to router R0 in group Gj+1;
P3: for i from 0 to n-3, and j from i+2 to n-1, connect Rv within Gj with RV' within Gj, wherein v is the highest available slot in Gj and v' is the lowest available slot in Gj.
In order to unify the interconnect network and facilitate the algorithm, each group of routers may be set including m routers, wherein m is greater than or equal to one.
The routers in the interconnect network may be k-radix routers; and each k-radix router within the system comprises a local ports, p processor ports and g global ports, a, p and g are integer greater than or equal to 1 ; wherein a local ports are used to achieve the interconnection among the routes within a group of routes, and the corresponding channels are local interconnected channels; wherein p processors ports are to used to achieve interconnection between the processor nodes and the route nodes, the corresponding channels are processor interconnected channels; wherein g global ports are to used to achieve interconnection among the groups, the corresponding channels are global interconnected channels, and k =p + a + g. Because m routers compose a group of routers, for implementing fully connection of routers within a router group, the number of local ports a = m - 1 ; for implementing fully connection of groups of routers, the number of global ports g = (n - 1) / m; while the number of process nodes is nmp, and each router group acts like a virtual router with k' = m (p + g) ports.
FIG2 show an example embodiment of the interconnect network proposed by the present invention, in this interconnect network, m = 4, p = 2, g = 2, n = 9. As shown in FIG2, routers within a group of routers achieve fully connection, ensuring that distance of any two routers within a group is one hop. Groups of router also achieve fully connection, ensuring that there must be a global channel between any two groups of routers.
Based on the interconnect network proposed by the present invention, as shown in FIG7, the present invention proposes a partially adaptive routing algorithm of interconnect network, comprising the steps of:
SI : label the interconnection network routers, wherein n group of routers are sequentially labeled G0, G1; Gn-1, m routers in the group are sequentially labeled 0, R1; Rm-1. Thereby, each router can be determined with its group label and intra- group label.
Meanwhile, interconnect the highest labeled router GsRm-1 in any group of routers Gs with the lowest labeled router GtRo in group of routers Gt during labeling, wherein t= (s+1) mod n, i.e., t is the remainder of dividing s+1 by n; interconnect the highest labeled router GuRm-1 in group of routers Gu with the lowest labeled router GSR0 in group of routers Gs during labeling, wherein u= (s-1) mod n, i.e., u is the remainder of dividing s-1 by n;
S2: according to the labels of routers at two ends of the channel, a unidirectional channel can be classified as minus direction and plus direction;
Since each channel connects two routers, for a channel with a leading end router GuRji and a rear end router GxlRyl, the following principles should be followed when classifying a channel as a minus direction or plus direction channel: for any channel (G^R^, GxlRyl), if il > xl, the channel is defined as minus direction; if il < xl, the channel is defined as plus direction; if il = xl and j l > yl, the channel is defined as minus direction; if il = xl and j l < yl, the channel is defined as plus direction.
S3 : when routing a message packet, all the paths should comply with the principle of minus-first routing that all routing paths from the source node to the destination node comprise w minus direction paths followed by v plus direction paths; or all the paths should comply with the principle of plus-first routing that all routing paths from the source router to the destination router comprise w plus direction paths followed by v minus direction paths.. Therein, v and w are integers greater than or equal to 1.
For convenience aspect of showing the present invention, the message packet comply the label minus first direction when forward message package in step 3 of the embodiment of the algorithm invention.
As shown in FIG3, an example embodiment of the partially adaptive routing which comply the label minus first direction should comprise the following steps:
S31 : When routing a message packet, set the router of the current node as GjRj, and the router of destination node as GxRy, Ch is an available set of message packet output channels, which has an initial value of empty set 0, compare the group label i of the router of the current node with the group label x of the router of the destination node, if i = x, go to step S32 if i < x, go to step S33, otherwise go to step S34;
S32: check whether the router of the current node is the router of the destination node, if the router of the current node is the router of the destination node, i.e., i = x and j = y, the message packet has reached the destination node by the router, and the algorithm ends; otherwise, if i = x and j≠ y, providing local channel (GjRj, GxRy) so that the message packet can be delivered to the router of destination node, Ch = Ch + {(GiRj, GxRy)}, return Ch;
S33: assume router GjRa in the group of routers of the current node and router GxRb in the group of routers of the destination node are connected;
If b > y and a≠ j, then provide routing channel from GjRj to GjRa, Ch = Ch + {(GiRj, GiRa)} ;
If b < y, set router GjRc in the group of routers of the current node connecting with the router GmRd and the router GmRe connecting with the router GxRf;
For m < i, only when j < c and f > y, misroute the packet to Gm;
For i < m < x, only when j < c and d < e, misroute the packet to Gm;
If c≠ j, provide router channel from GjRj to GjRc, Ch = Ch + {(GjRj,
If c = j, provide router channel from GjRj to GmRd, Ch = Ch + {(GjRj, GmRd)}, return Ch;
S34: assume router GjRa in the group of routers of the current node and router GxRb in the group of routers of the destination node are connected;
If a < j, provide routing channel from GjRj to GjRa, Ch = Ch + {(GjRj,
If a = j, provide routing channel from GjRj to GxRb, Ch = Ch + {(GjRj, GxRb)} ;
If a > j, set router GjRc in the group of routers of the current node connecting with router GmRd and router GmRe connecting with router
GxRf;
for m < x, only when j < c and f > y, misroute the packet to Gm; for x < m < i, only when j < c and d < e, misroute the packet to Gm;
If c≠ j, provide router channel from GjRj to GjRc, Ch = Ch + {(GiRj, GiRc)} ; If c = j, provide router channel from GjRj to Gm d, Ch = Ch + {(GiRj, GmRd)}, return Ch.
As shown in FIG 8, based on the partially routing algorithm above proposed by the present invention, the present invention proposed a fully adaptive routing algorithm of interconnect network, comprising the following steps:
Dl : according to the channel type used by the next hop of message packet, classify the message package into safe package or unsafe package according to the following principles: if routing channel used by the message packet to the next hop complies with the principle of minus direction-first routing, the packet is a safe package for the router of the next hop; otherwise, it is an unsafe package;
D2: set channel buffer with a size of bw^ packets, which can store buff message packets at most, wherein buffi?, greater than or equal to 2;
D3: set the router of the current node as GjRj, and the router of the destination node as GxRy, Chi is a set including all the routing channels for message packets which comply the principle of minus direction-first; if i = x and j = y, the packet has reached the destination node, so the routing process ends; otherwise, invoke the partially adaptive routing algorithm of interconnect network stated above to provide set of channels Chi which comply the principle of minus direction-first for message packets;
D4: set the router of the current node as GjRj, and the router of the destination node as GxRy, Ch2 is a set including all the routing channels for message packets which comply minimal routing; if i = x and j = y, the message packet has arrived at the destination node, so the routing process ends; if i = x and j≠ y, Ch2 = {(GjRj, GxRy)} ; if i≠ x, set router GxRb in the current group of routers and the router GjRa in the destination group are connected; if a≠ j, provide routing channel from router GjRj to router GjRa, Ch2 = {(GjRj, GjRa)}, if a = j, provide routing channel from router GjRj to router GxRb, Ch2 = {(GjRj, GxRb)} ;
D5: for the set of channels Ch2 in which all the routing channels comply the minimal routing path, the channels should be considered separately. Assume the channel by which the message packages arrives the next router node according to the minimal routing path provided by Ch2 has f empty buffers, and s buffer safe packages, the message packets comply the following flow control mechanisms: if f > 1 , the message packet can be delivered to the next node with the channel included in Ch2; if f = 1 and s > 1, the message packet can be delivered to the next node with the channel included in Ch2; if f = 1 and s = 0, the message packet is the safe package for the channel to the next hop, which is included in Ch2, and the package can be delivered to the next node with the channel included in Ch2; in other cases, the packet cannot be delivered via channels included in Ch2, and then empty Ch2, i.e. Ch2 = 0.
With the process above, message packages will not be deadlocked with the channel provided by Ch2.
D6: according to the routing channel set Chi provided by step D3 and the routing channel set Ch2 provided by step D5, get all the routing channels that provided by fully adaptive routing algorithm Ch3, Ch3 = Chi + Ch2, wherein packets will be routed by the partially adaptive routing algorithm if they do not comply the flow control principle; or let Ch3 = Ch2 and route them with the minimal routing path after they are converted into complying with the flow control in the next routing, return Ch3.
Figure 4 shows two example embodiments of the partially routing algorithm of the present application, which respectively are (source router node G0Ri, destination router node G3Ri) and (source router node G3R1; destination router node G0Ri), based on the label minus direction first partially adaptive deadlock free routing algorithm, providing the following routing:
For (source node G0Ri, the destination node G3R4), the routing path is: (G0R1, G2R1) -> (G2R1, G2R2) -> (G2R2, G3R0) -> (G3R0, G3R1);
For (source node G3R1; the destination node G0Ri), the routing path is: (G3R1, G3R0) -> (G3R0, G2R2) -> (G2R2, G2R1) -> (G2R1, G0R1).
Figure 5 shows the label minus first direction always ensures that message packet can arrive at the destination router node in five hops for any two router nodes according to the interconnection network system and the partially adaptive routing algorithm of the present invention. In figure 5, GjRj is source node router, GxRy is destination node router. Based on the label minus first direction partially adaptive deadlock free routing algorithm, it provides the following routing path:
For i < x, the deadlock free partially routing algorithm always provides routing path: (GjRj, GjRc) -> (GjRc, Gx-1Rd) -> (Gx-1Rd, Gx-iRmax) -> (Gx-iRmax, GxRo) -> (GxRo, GxRy);
For i > x, the deadlock free partially routing algorithm always provides routing path: (GjRj, GiR0) -> (GjRo, G^R^) -> (G^R^, Gi.jRd) -> (Gi.jRd, GXRC) -> (GxRc, GxRy).
The max subscript means the max label router within a router group.
The reason that the partially routing algorithm proposed by the present invention can avoid deadlock is: consider the four necessary conditions for deadlock: resource mutex, request and hold, non-preemptive, and circular wait. Therefore, using the label minus first direction, by eliminating the circular wait, deadlock can be avoided. For example, a routing algorithm in figure 6 (a) generates a deadlock is showed in figure 6 (b). After restricting some waiting paths, the circular dependency is eliminated and deadlock is avoided as shown in figure 6 (c). Therefore, the embodiment of the partially adaptive routing algorithm proposed by the present invention can implement an adaptive routing in interconnection network without using virtual channels.
Although specific embodiments have been illustrated and described herein, it will be appreciated by those of ordinary skill in the art that any arrangement which is calculated to achieve the same purpose may be substituted for the specific embodiments shown. This application is intended to cover any adaptations or variations of the example embodiments of the invention described herein. It is intended that this invention be limited only by the claims, and the full scope of equivalents thereof.

Claims

What is claimed is:
1. An interconnect network system, wherein routers in the system are divided into n groups of routers with full connecting among the n router groups, so that communication between any two groups of routers only requires one hop, wherein n is an integer greater than or equal to 1 ; each group of routers contains one or more routers with full connecting among the routers in the group, so that a distance between any two routers in the group is only one hop; a connection algorithm among the groups of routers complies the following principles:
PI : label the routers in the interconnection network, wherein n groups of routers are sequentially labeled G0, G1; Gn-1, and m routers in the group are sequentially labeled 0, R1; Rm-i;
P2: for i from 0 to n-2, connect the router Rm-1 in group Gj to the router Ro in group Gi+1;
P3: for i from 0 to n-3, for j from i+2 to n-1, connect the router Rv in group Gj with the router Rv> in group Gj, wherein v is the highest available slot in group Gj and v' is the lowest available slot in group Gj for the global connection.
2. The interconnect network of Claim 1, wherein each group of routers including m routers, wherein m is greater than or equal to one.
3. The interconnect network of Claim 1 or 2, each router in the network comprises a local ports, p processor ports and g global ports; wherein the a local ports are to achieve the interconnection among the routers within a router group, the corresponding channels are local interconnected channels; wherein the p processors ports interconnects processor nodes with routers; wherein the g global ports interconnects among the groups of routers, and the corresponding interconnected channels are global channels.
4. The interconnect network of Claim 3, wherein each group of routers includes m=a+l routers, the number of groups of routers is n = mg +1, which means that each group contains k - m (p + g) ports.
5. The partially adaptive routing algorithm for interconnect network, comprising the steps of: SI : label the interconnection network routers, wherein n groups of routers are sequentially labeled G0, G1; Gn-1, and m routers in the groups are sequentially labeled 0, R1; Rm-i; interconnect the highest labeled router GsRm-1 in any group of routers Gs with the lowest labeled router GtRo in group of routers Gt during labeling, wherein t= (s+1) mod n, i.e., t is the remainder of dividing s+1 by n; interconnect the highest labeled router GuRm-1 in group of routers Gu with the lowest labeled router GsRo in group of routers Gs during labeling, wherein u= (s-1) mod n, i.e., u is the remainder of dividing s-1 by n;
S2: according to the label of routers at each end of the channel, a unidirectional channel can be classified as minus and plus directions;
S3 : when routing a message packet, all the paths should comply with the principle of minus-first routing that all routing paths from the source router to the destination router comprise w minus direction paths followed by v plus direction paths; or all the paths should comply with the principle of plus-first routing that all routing paths from the source router to the destination router comprise w plus direction paths followed by v minus direction paths.
6. The partially adaptive routing algorithm for interconnect network of Claim 5, wherein when classified channels as minus direction and plus direction in the step S2, the following principles should be complied with:
For any channel (G Rji, GxlRyl),
If il > xl, the channel is defined as label minus direction;
If il < xl, the channel is defined as label plus direction;
If il = xl and j l > yl, the channel is defined as label minus direction;
If il = xl and j l < yl, the channel is defined as label plus direction.
7. The partially adaptive routing algorithm for interconnect network of Claim 5, wherein the step S3 complies with minus direction-first principle when routing a packet.
8. The partially adaptive routing algorithm for interconnect network of Claim 7, wherein the step S3 comprises the following steps:
S31 : When routing a message packet, set the router of the current node as GjRj, and the router of destination node as GxRy, Ch is an available set of message packet output channels, which has an initial value of empty set 0, compare the group label i of the router of the current node with the group label x of the router of the destination node, if i = x, go to step S32 if i < x, go to step S33, otherwise go to step S34;
S32: check whether the router of the current node is the router of the destination node, if the router of the current node is the router of the destination node, i.e., i = x and j = y, the message packet has reached the destination node by the router, and the algorithm ends; otherwise, if i = x and j≠ y, providing local channel (GjRj, GxRy) so that the message packet can be delivered to the router of destination node, Ch = Ch + {(GiRj, GxRy)}, return Ch;
S33: assume router GjRa in the group of routers of the current node and router GxRb in the group of routers of the destination node are connected;
If b > y and a≠ j, then provide routing channel from GjRj to GjRa, Ch = Ch + {(GiRj, GiRa)} ;
If b < y, set router GjRc in the group of routers of the current node connecting with the router GmRd and the router GmRe connecting with the router GxRf;
For m < i, only when j < c and f > y, misroute the packet to Gm;
For i < m < x, only when j < c and d < e, misroute the packet to Gm;
If c≠ j, provide router channel from GjRj to GjRc, Ch = Ch + {(GjRj, If c = j, provide router channel from GjRj to Gm d, Ch = Ch + {(GjRj, GmRd)}, return Ch;
S34: assume router GjRa in the group of routers of the current node and router GxR in the group of routers of the destination node are connected;
If a < j, provide routing channel from GjRj to GjRa, Ch = Ch + {(GjRj,
If a = j, provide routing channel from GjRj to GxR , Ch = Ch + {(GjRj, GxRb)} ;
If a > j, set router GjRc in the group of routers of the current node connecting with router GmRd and router GmRe connecting with router
GxRf;
for m < x, only when j < c and f > y, misroute the packet to Gm; for x < m < i, only when j < c and d < e, misroute the packet to Gm;
If c≠ j, provide router channel from GjRj to GjRc, Ch = Ch + {(GiRj, GiRc)} ;
If c = j, provide router channel from GjRj to GmRd, Ch = Ch + {(GiRj, GmRd)}, return Ch.9. The fully adaptive routing algorithm for the interconnect network, comprising the steps of:
Dl : according to the channel type used by the next hop of message packet, classify the message package into safe package or unsafe package; if routing channel used by the message packet to the next hop complies with the principle of minus direction-first routing, the packet is a safe package for the router of the next hop; otherwise, it is an unsafe package;
D2: set channel buffer with a size of bw^ packets, which can store buff message packets at most, wherein buff is greater than or equal to 2;
D3: set the router of the current node as GjRj, and the router of the destination node as GxRy, Chi is a set including all the routing channels for message packets which comply the principle of minus direction-first; if i = x and j = y, the packet has reached the destination node, so the routing process ends; otherwise, invoke the partially adaptive routing algorithm of interconnect network stated above to provide set of channels Chi which comply the principle of minus direction-first for message packets;
D4: set the router of the current node as GiRj, and the router of the destination node as GxRy, Ch2 is a set including all the routing channels for message packets which comply minimal routing; if i = x and j = y, the message packet has arrived at the destination node, so the routing process ends; if i = x and j≠ y, Ch2 = {(GjRj, GxRy)} ; if i≠ x, set router GxR in the current group of routers and the router GjRa in the destination group are connected; if a≠ j, provide routing channel from router GjRj to router GjRa, Ch2 = {(GjRj, GjRa)}, if a = j, provide routing channel from router GjRj to router GxR , Ch2 = {(GjRj, GxRb)} ;
D5: for the set of channels Ch2 in which all the routing channels comply the minimal routing path, the channels should be considered separately. Assume the channel by which the message packages arrives the next router node according to the minimal routing path provided by Ch2 has f empty buffers, and s buffer safe packages, the message packets comply the following flow control mechanisms: if f > 1 , the message packet can be delivered to the next node with the channel included in Ch2; if f = 1 and s > 1, the message packet can be delivered to the next node with the channel included in Ch2; if f = 1 and s = 0, the message packet is the safe package for the channel to the next hop, which is included in Ch2, and the package can be delivered to the next node with the channel included in Ch2; in other cases, the packet cannot be delivered via channels included in Ch2, and then empty Ch2, i.e. Ch2 = 0;
D6: according to the routing channel set Chi provided by step D3 and the routing channel set Ch2 provided by step D5, get all the routing channels that provided by fully adaptive routing algorithm Ch3, Ch3 = Chi + Ch2, wherein packets will be routed by Claim5 if they do not comply the flow control principle; or let Ch3 = Ch2 and route them with the minimal routing path after they are converted into complying with the flow control in the next routing, return Ch3.
10: The fully adaptive routing algorithm of Claim 10, wherein message packages are divided into safe packages and unsafe packages in step Dl . Unsafe packets which do not comply with the flow control principle can be routed with the partial algorithm, and then the unsafe packets can be converted into safe packets. Otherwise, the unsafe packets should wait route process until they comply with the flow control principle so that they can route according to minimal path algorithm.
PCT/CN2014/080973 2014-06-27 2014-06-27 Deadlock-free adaptive routing of interconnect network Ceased WO2015196461A1 (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
PCT/CN2014/080973 WO2015196461A1 (en) 2014-06-27 2014-06-27 Deadlock-free adaptive routing of interconnect network

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/CN2014/080973 WO2015196461A1 (en) 2014-06-27 2014-06-27 Deadlock-free adaptive routing of interconnect network

Publications (1)

Publication Number Publication Date
WO2015196461A1 true WO2015196461A1 (en) 2015-12-30

Family

ID=54936522

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/CN2014/080973 Ceased WO2015196461A1 (en) 2014-06-27 2014-06-27 Deadlock-free adaptive routing of interconnect network

Country Status (1)

Country Link
WO (1) WO2015196461A1 (en)

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN108337196A (en) * 2017-12-29 2018-07-27 曙光信息产业(北京)有限公司 A kind of exchange system and its routing algorithm built by exchange chip
CN109146196A (en) * 2018-09-07 2019-01-04 河北工程大学 A kind of residential communities hourly water demand forcast method
CN112698960A (en) * 2020-12-28 2021-04-23 北京理工大学 Anti-deadlock method for three-core-based network based on classification and transmission of data by using tip subgraph
CN117135110A (en) * 2023-10-25 2023-11-28 苏州元脑智能科技有限公司 An adaptive routing method, device, system, equipment and storage medium
CN120151272A (en) * 2025-04-18 2025-06-13 山东云海国创云计算装备产业创新中心有限公司 Routing method and device for multi-dimensional hypercube interconnection network

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20100049942A1 (en) * 2008-08-20 2010-02-25 John Kim Dragonfly processor interconnect network
US20120144065A1 (en) * 2010-11-05 2012-06-07 Cray Inc. Table-driven routing in a dragonfly processor interconnect network
CN103973564A (en) * 2013-01-31 2014-08-06 清华大学 Interconnection network system and self-adaptation routing method

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20100049942A1 (en) * 2008-08-20 2010-02-25 John Kim Dragonfly processor interconnect network
US20120144065A1 (en) * 2010-11-05 2012-06-07 Cray Inc. Table-driven routing in a dragonfly processor interconnect network
CN103973564A (en) * 2013-01-31 2014-08-06 清华大学 Interconnection network system and self-adaptation routing method

Cited By (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN108337196A (en) * 2017-12-29 2018-07-27 曙光信息产业(北京)有限公司 A kind of exchange system and its routing algorithm built by exchange chip
CN109146196A (en) * 2018-09-07 2019-01-04 河北工程大学 A kind of residential communities hourly water demand forcast method
CN109146196B (en) * 2018-09-07 2021-07-23 河北工程大学 A method for predicting water consumption in residential communities
CN112698960A (en) * 2020-12-28 2021-04-23 北京理工大学 Anti-deadlock method for three-core-based network based on classification and transmission of data by using tip subgraph
CN112698960B (en) * 2020-12-28 2022-08-09 北京理工大学 Anti-deadlock method for three-core-based network based on classification and transmission of data by using tip subgraph
CN117135110A (en) * 2023-10-25 2023-11-28 苏州元脑智能科技有限公司 An adaptive routing method, device, system, equipment and storage medium
CN117135110B (en) * 2023-10-25 2024-03-01 苏州元脑智能科技有限公司 An adaptive routing method, device, system, equipment and storage medium
CN120151272A (en) * 2025-04-18 2025-06-13 山东云海国创云计算装备产业创新中心有限公司 Routing method and device for multi-dimensional hypercube interconnection network

Similar Documents

Publication Publication Date Title
US12386759B2 (en) Algorithms for use of load information from neighboring nodes in adaptive routing
US6947433B2 (en) System and method for implementing source based and egress based virtual networks in an interconnection network
US7039058B2 (en) Switched interconnection network with increased bandwidth and port count
US7046633B2 (en) Router implemented with a gamma graph interconnection network
US9600440B2 (en) Network topology of hierarchical ring with recursive shortcuts
US20080291919A1 (en) Traffic Distribution and Bandwidth Management for Link Aggregation
CN103973564B (en) The adaptive routing method of interconnected network system
US11070474B1 (en) Selective load balancing for spraying over fabric paths
KR20190112804A (en) Packet processing method and apparatus
WO2015196461A1 (en) Deadlock-free adaptive routing of interconnect network
CN104995884A (en) Distributed switchless interconnect
WO2024093778A1 (en) Packet processing method and related apparatus
CN105871761A (en) High order matrix switch, network on chip and communication method
Yang et al. MRBS: An area-efficient multicast router for network-on-chip using buffer sharing
CN116647883B (en) Enhanced virtual channel switching
Umoh et al. BANM: A Distributed Network Manager Framework for Software Defined Network-On-Chip (SDNoC)
US20120195314A1 (en) Destination-Based Virtual Channel Assignment in On-Chip Ring Networks
US11265268B1 (en) High-throughput multi-node integrated circuits
Lin et al. Power and latency efficient mechanism: a seamless bridge between buffered and bufferless routing in on-chip network
US20250240187A1 (en) Network Device with High Bandwidth Packet Processing Capabilities
US20250119393A1 (en) Congestion mitigation in interconnection networks
US12289227B2 (en) Computing system, computing processor and data processing method
US20250337697A1 (en) In-link flit resizing with end-to-end credits
US20250112864A1 (en) Congestion detection in interconnection networks
Wang et al. Study on hybrid switching mechanism in network on chip

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 14896151

Country of ref document: EP

Kind code of ref document: A1

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 14896151

Country of ref document: EP

Kind code of ref document: A1