Table-driven routing in a dragonfly processor interconnect network

Patent metadata

Field	Value
Publication number	US-9282037-B2
Application number	US-201113290567-A
Country	US
Kind code	B2
Filing date	Nov 7, 2011
Priority date	Nov 5, 2010
Publication date	Mar 8, 2016
Grant date	Mar 8, 2016

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.

First claim

What is claimed is:

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.

Assignees

• Parker Mike
• Scott Steve
• Cheng Albert
• Alverson Robert
• Intel Corp

Inventors

• Parker Mike
• Scott Steve
• Cheng Albert
• Alverson Robert

Classifications

• H04L45/125

  based on throughput or bandwidth · CPC title

• H04L45/586

  of virtual routers · CPC title

• H04L45/10

  Routing in connection-oriented networks, e.g. X.25 or ATM · CPC title

• G06F15/17312

  Routing techniques specific to parallel machines, e.g. wormhole, store and forward, shortest path problem congestion (routing on a LAN H04L45/00) · CPC title

• H04L45/745 Primary

  Address table lookup; Address filtering · CPC title