Method and apparatus for integrated local and express routing in a multiprocessor

• US 5,546,596 A
• Filed: 03/30/1995
• Issued: 08/13/1996
• Est. Priority Date: 08/24/1993
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Geist, Alan
• Primary Examiner(s): Bowler, Alyssa H.
• Assistant Examiner(s): Tran, Denise
• Application Number:
  US08/415,084
• Time in Patent Office: 502 Days
• Field of Search: 395/800, 395/200, 395/280, 395/200.01, 395/200.02, 326/41, 370/85.9, 370/94.3, 370/60
• US Class Current: 709/243
• CPC Class Codes: G06F 15/17381 Two dimensional, e.g. mesh, torus

Abstract

A router for routing a message among nodes in an N dimensional network of processor nodes. The router includes a message logic unit determining in which direction the message is traveling in the network. The router features a number of (D) of express ports, each express port having an input for inputting and an output for outputting the message in a corresponding one of (D) express directions. A routing logic unit in the router is capable of transmitting the message in a selected express direction through a corresponding local port, each local port inputting and outputting the message in one dimension of the network. The routing logic unit also includes express routing logic that is capable of transmitting the message in the selected express direction through a corresponding express port. The message logic unit includes detection logic for determining the distance in each dimension remaining to be traveled by the message to a destination node. The routing logic unit transmits the message in the express direction through the express port if the remaining distance in the express direction is greater than or equal to a quantity S, where S is greater than or equal to 2N/D. The routing logic unit transmits the message in the express direction through the local port if the remaining distance in the express direction is less than S.

Claims

1. An N dimensional network comprising a plurality of processor nodes, in which N is a value of at least one, the network further comprising a plurality of integrated routers for routing a message from a source processor node of the plurality of processor nodes to a destination processor node of the plurality of processor nodes in 2N orthogonal directions, said each integrated router coupled to a processor node of the plurality of processor nodes, said each integrated router further coupled to a plurality of adjacent routers, said each adjacent router located in an identified direction from the integrated router, and said each integrated router coupled to at least one non-adjacent router, said each non-adjacent router located in an identified direction from the integrated router, said each integrated router comprising:

a processor pen to communicate the message between the coupled processor node and the integrated router;

2N local ports to receive the message from and output the message to the adjacent routers in 2N orthogonal directions, each local port having an identified direction, said each local port further comprising a local input to receive the message from the identified direction and a local output to output the massage to the identified direction;

M express ports, 2N>

M>

=1, to receive the message from and output the message to the non-adjacent routers in less than 2N orthogonal directions, each express port having an identified direction, said each express port further including an express input to receive the message from the identified direction and an express output to output the message to the identified direction;

a message status unit coupled to said each local port and said each express input, said message status unit to select a direction to route the message, and if said direction to route the message is not equal to the directions identified by the express ports of the router, said message status unit to output the message through the local output having an identified direction equal to the direction to mute the message; and

a muting logic unit coupled to the message status unit, said routing logic unit further coupled to said each express port and said each local port having the same identified direction as said each express port, and if said direction to route the message is equal to the directions identified by the express ports of the router, said routing logic unit selectively outputting the message through the express output or the local output in said direction to route the massage, said muting logic unit further comprising logic to select the express output to output the received message if the remaining distance in said direction to route the message is greater than a value D, where D is indicative of a number of processor nodes between the router and the destination processor node in said direction to route the message, D having a value of at least one.

2. The router of claim 1, the message status unit further comprising logic for determining a remaining distance to the destination processor node to be traveled by the message in each identified direction.

3. The router of claim 1, the routing logic unit further comprising logic to select the local port for outputting the message if the remaining distance in the selected direction is less than or equal to a value D, where D is indicative of a number of processor nodes in the selected direction between the router and the destination processor node, D having a value of at least one.

4. An N dimensional network, in which N has a value of at least one, comprising:

a plurality of processor nodes;

a plurality of integrated routers, each integrated router coupled to a processor node of the plurality of processor nodes, the integrated routers for routing a message from a source processor node of the plurality of processor nodes to a destination processor node of the plurality of processor nodes, each integrated router comprising;

a processor port to communicate the message between the coupled processor node and the integrated router;

2N local ports coupled to a plurality of adjecent routers to receive the message from and output the message to the adjacent routers in 2N orthogonal directions, each local port having an identified direction, said each local port further comprising a local input to receive the message from the identified direction and a local output to output the message to the identified direction;

M express ports, 2N>

M>

=1, coupled to at least one non-adjacten router to receive the message from and output the message to the non-adjacent routers in less than 2N orthogonal directions, each express port having an identified direction, said each express port further including an express input to receive the message from the identified direction and an express output to output the message to the identified direction;

a message status unit coupled to said each local port and said each express input, said message status unit to select a direction to route the message, and if said direction to route the message is not equal to the directions identified by the express ports of the router, said message status unit to output the message through the local output having an identified direction equal to the direction to route the message; and

a routing logic unit coupled to the message status unit, said routing logic unit further coupled to said each express port and said each local port having the same identified direction as said each express port, and if said direction to route the message is equal to the directions identified by the express ports of the router, said routing logic unit selectively outputting the message through the express output or the local output in said direction to route the message, said routing logic unit further comprising logic to select the express output to output the received message if the remaining distance in said direction to route the message is greater than a value D, where D is indicative of a number of processor nodes between the router and the destination processor node in said direction to route the message, D having a value of at least one.

5. The network of claim 4, the message status unit further comprising logic for determining a remaining distance to the destination processor node to be traveled by the message in each identified direction.

6. The network of claim 4, the routing logic unit further comprising logic to select the local port for outputting the message if a remaining distance in the selected direction is less than or equal to a value D, where D is indicative of a number of processor nodes in the selected direction between the router and the destination processor node, D having a value of at least one.

7. The network of claim 4, in which no two adjacent routers comprise express ports with the same identified direction.

8. In an N-dimensional network comprising a plurality of processor nodes and a plurality of integrated routers, N having a value of at least one, each integrated router coupled to a processor node, said each integrated router including 2N local ports to receive a message from and output the message to a plurality of adjacent routers in 2N orthogonal directions, each local port having an identified direction, said each integrated router further including M express ports, 2N>

M>

=1, each express port to receive the message from and output the message to at least one non-adjacent router in less than 2N orthogonal directions, said each express port having an identified direction, a method for routing the message from a source processor node of the plurality of processor nodes to a destination processor node of the plurality of processor nodes, the method comprising the steps of;

if an integrated router of the plurality of integrated routers is connected to the source processor node for the message, receiving the message from the source processor node;

if the integrated router is not connected to the source processor node, the integrated router receiving the message through a local port or an express port of the integrated router;

the integrated router determining whether the integrated router is coupled to the destination processor node;

if the integrated router is coupled to the destination processor node, the integrated router communicating the message to the destination processor node;

if the integrated router is not coupled to the destination processor node;

the integrated router selecting a selected direction in which to route the message;

the integrated router determining whether the selected direction is an identified direction of one of the express ports;

if the selected direction is an identified direction of one of the express ports, the integrated router determining whether a remaining distance to the destination processor node to be traveled by the message in the selected direction is greater than a value D, where D is indicative of a number of processor nodes between the integrated router and the destination processor node in the selected direction, D having a value of at least one;

if the remaining distance is greater than the value D, the integrated router outputting the message through the express port having an identified direction that is the same as the selected direction; and

if the remaining distance is less than or equal to the value D, the integrated router outputting the message through the local port having an identified direction that is that same as the selected direction;

if the selected direction is not identified by one of the express ports, the integrated router outputting the message through the local port having an identified direction that is that same as the selected direction.