Table-driven routing in a dragonfly processor interconnect network

• US 9,282,037 B2
• Filed: 11/07/2011
• Issued: 03/08/2016
• Est. Priority Date: 11/05/2010
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Parker, Mike, Scott, Steve, Cheng, Albert, Alverson, Robert
• Primary Examiner(s): BOUTAH, ALINA A
• Application Number:
  US13/290,567
• Publication Number:
  US 20120144065A1
• Time in Patent Office: 1,583 Days
• Field of Search: 709238-242, 712/29, 712/30, 712/203, 711/151, 711/122, 370/216, 370/225, 370/227
• US Class Current: 1/1
• CPC Class Codes: G06F 15/17312 Routing techniques specific to parallel machines, e.g. wormhole, store and forward, shortest path problem congestion routing on a LAN H04L45/00
• CPC Class Codes: G06F 15/17362 hierarchical topologies
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/586 of virtual routers
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

Abstract

A multiprocessor computer system comprises a dragonfly processor interconnect network that comprises a plurality of processor nodes and a plurality of routers. The routers are operable to route data by selecting from among a plurality of network paths from a target node to a destination node in the dragonfly network based on one or more routing tables.

Claims

1. A multiprocessor computer system including a processor interconnect network, comprising:

a plurality of groups of routers, wherein the plurality of groups of routers are interconnected through an intergroup interconnection network, each group of routers comprises a respective plurality of local routers locally coupled to each other router in the corresponding plurality of local routers through a respective intragroup interconnection network,

wherein at least a particular router in a particular one of the plurality of groups of routers is to;

access at least one routing table from a plurality of routing tables, wherein the plurality of routing tables comprises at least one local routing table corresponding to the intragroup interconnection network of the particular group of routers and a plurality of global routing tables corresponding to the intergroup interconnection network;

route data to another router coupled to the intergroup interconnection network by selecting a network path from among a plurality of network paths from a target node to a destination node in the network based on the at least one routing table, wherein the plurality of global routing tables include;

a non-minimal table to route non-minimal traffic to an intermediate group of routers that is connected to all other groups of routers in the plurality of groups of routers,

a minimal table to determine a direct path from one router group to another router group in the plurality of router groups,

network congestion information corresponding to the intragroup interconnection network of the particular group of routers, and

failed network link information corresponding to the intragroup interconnection network of the particular group of routers,

wherein the network path is selected based on one or more of the network congestion information and failed network link information.

2. The multiprocessor computer system of claim 1, wherein routing within a group comprises using one or more minimal or non-minimal local routing tables.

3. The multiprocessor computer system of claim 1, wherein routing between groups comprises using one or more minimal or non-minimal global routing tables.

4. The multiprocessor computer system of claim 1, the routing tables comprising minimal and non-minimal tables.

5. A method of operating a multiprocessor computer system, comprising:

routing data within a processor interconnect network, wherein the processor interconnect network comprises a plurality of groups of routers, the plurality of groups of routers are interconnected through an intergroup interconnection network, and each group of routers comprises a respective plurality of local routers locally coupled to each other router in the corresponding plurality of local routers through a respective intergroup interconnection network,

wherein the data is routed from a first router in a first one of the plurality of groups of routers to a second router in a second one of the plurality of groups of routers, and routing the data comprises;

accessing at least one routing table from a plurality of routing tables, wherein the plurality of routing tables comprises at least one local routing table corresponding to the one of the intragroup interconnection networks and a plurality of global routing tables corresponding to the intergroup interconnection network, the plurality of global routing tables comprises a non-minimal table and a minimal table;

selecting from among a plurality of network paths from a target node to a destination node in the network based on information in the plurality of global routing tables and one or more of network congestion information corresponding to at least one of the intragroup interconnection networks and failed network link information corresponding to at least one of the intragroup interconnection networks.

6. The method of operating a multiprocessor computer system of claim 5, wherein routing within a group comprises using one or more minimal or non-minimal local routing tables.

7. The method of operating a multiprocessor computer system of claim 5, wherein routing between groups comprises using one or more minimal or non-minimal global routing tables.

8. The method of operating a multiprocessor computer system of claim 5, the routing tables comprising minimal and non-minimal tables.