Table-driven routing in a dragonfly processor interconnect network

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.

1 .- 21 . (canceled) 
     
     
         22 . An apparatus comprising:
 a routing device to support adaptive routing of data in a multiprocessor network comprising a Dragonfly network topology,   wherein the routing of the data is to be based on one or more routing tables, the Dragonfly network topology is to comprise a plurality of groups, one or more of the groups is to comprise a respective plurality of routers and is to couple by a respective link to the other groups in the plurality of groups, and respective of the routers is to connect to one or more processor nodes in the network.   
     
     
         23 . The apparatus of  claim 22 , wherein the apparatus is a switch or a router and the routing device is a chip. 
     
     
         24 . The apparatus of  claim 22 , wherein at least one of the plurality of groups is to function as a virtual router in the network. 
     
     
         25 . The apparatus of  claim 24 , wherein each of the plurality of groups is to function as a respective virtual router in the network. 
     
     
         26 . The apparatus of  claim 22 , wherein the routing device is to further monitor congestion associated with at least one channel in the network. 
     
     
         27 . The apparatus of  claim 26 , wherein adaptive routing decisions are to be based at least in part on the congestion monitoring. 
     
     
         28 . The apparatus of  claim 27 , wherein the routing device is to route data using credit round-trip latency as an indicator of channel congestion. 
     
     
         29 . The apparatus of  claim 26 , wherein the channel comprises a global channel. 
     
     
         30 . The apparatus of  claim 22 , wherein the Dragonfly network topology comprises at least one virtual channel. 
     
     
         31 . The apparatus of  claim 22 , wherein the network interconnects at least two sub-networks. 
     
     
         32 . The apparatus of  claim 22 , wherein the virtual radix of each group is the product of the number of routers in each group times the sum of the number of processor nodes connected to each router plus the number of global channels in the network. 
     
     
         33 . The apparatus of  claim 22 , wherein the number of routers per group is equal to twice the number of processor nodes per router, and the number of processor nodes per router is equal to the number of channels per router connected to other groups. 
     
     
         34 . The apparatus of  claim 22 , wherein the network comprises a number of processor nodes and the virtual router has a radix of approximately 2 times the square root of the number of processor nodes. 
     
     
         35 . The apparatus of  claim 22 , wherein the plurality of routers in at least one of the groups is greater than twice the number of global channels per router. 
     
     
         36 . The apparatus of  claim 22 , wherein the number of processor nodes per router is greater than the number of global channels per router. 
     
     
         37 . The apparatus of  claim 22 , wherein the group comprises a sub-network having a flattened butterfly network topology. 
     
     
         38 . The apparatus of  claim 22 , wherein the routing device is to route data using selective virtual channel discrimination. 
     
     
         39 . The apparatus of  claim 22 , wherein the one or more tables comprises at least one global table for routing the data between groups of the plurality of groups. 
     
     
         40 . The apparatus of  claim 22 , wherein the one or more tables comprises at least one local table used for routing the data within a group of the plurality of groups. 
     
     
         41 . A method comprising:
 detecting congestion of at least one channel in a multiprocessor network comprising a Dragonfly network topology; and   performing adaptive routing of data within the network based on the congestion; using one or more routing tables corresponding to the Dragonfly network,   wherein the Dragonfly network topology comprises a plurality of groups, respective of the groups within the plurality of groups comprises a plurality of routers and is coupled by a respective link to the other groups in the plurality of groups, and respective of the routers are connected to one or more processor nodes in the network.   
     
     
         42 . A system comprising:
 a plurality of processor nodes; and   a plurality of router devices, wherein each router is coupled to a respective subset of the plurality of processor nodes, each router is included in a respective one of a plurality of router groups, each group has a respective group topology and is connected via a respective link to each other group in the plurality of router groups, and   at least one of the routers is to perform routing within the system using adaptive routing, and the routing is to be performed based at least in part on one or more routing tables.   
     
     
         43 . The system of  claim 42 , wherein each of the plurality of router groups is to function as a virtual router in the network. 
     
     
         44 . The system of  claim 42 , further comprising at least one global channel. 
     
     
         45 . The system of  claim 44 , wherein the adaptive routing is based on congestion determined for the at least one global channel. 
     
     
         46 . The system of  claim 45 , wherein the congestion of the global channel is determined from congestion detected at a local channel. 
     
     
         47 . The system of  claim 42 , wherein the plurality of processor nodes comprises at least one hundred thousand processor nodes. 
     
     
         48 . The system of  claim 42 , wherein each of the router groups comprises a sub-network with a respective topology. 
     
     
         49 . The system of  claim 48 , wherein the topology of at least one of the router groups comprises a flattened butterfly topology. 
     
     
         50 . The system of  claim 42 , wherein the one or more tables comprises at least one global table for routing the data between groups of the plurality of groups. 
     
     
         51 . The system of  claim 42 , wherein the one or more tables comprises at least one local table used for routing the data within a group of the plurality of groups.