Virtual channel assignment in large torus systems

• US 6,101,181 A
• Filed: 11/17/1997
• Issued: 08/08/2000
• Est. Priority Date: 11/17/1997
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Inventors: Thorson, Greg, Passint, Randal S., Galles, Michael B.
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): NGUYEN, HANH N
• Application Number:
  US08/971,591
• Time in Patent Office: 995 Days
• Field of Search: 395/200.15, 395/800.11, 395/200.71, 395/182.02, 370/60, 370/396, 370/401, 370/404, 370/409, 370/397, 709/238, 709/239, 709/240
• US Class Current: 370/352
• CPC Class Codes: G06F 15/17381 Two dimensional, e.g. mesh, torus

Abstract

A multiprocessor computer system includes processing element nodes interconnected by physical communication links. Routers route messages between processing element nodes on the physical communication links. Each router includes input ports for receiving messages, output ports for sending messages from the router, two types of virtual channels, a lookup table associated with the input port having a lookup table virtual channel number, and a virtual channel assignment mechanism. The virtual channel assignment mechanism assigns an output next virtual channel number for determining the type of virtual channel to be used for routing from a next router along a given route. The next virtual channel number is assigned based on the lookup table virtual channel number and an input next virtual channel number received from a previous router along the given route.

Claims

1. A multiprocessor computer system comprising:

a plurality of processing element nodes, each processing element node having at least one processor and memory;

physical communication links interconnecting the processing element nodes in a n-dimensional topology;

routers for routing messages between the plurality of processing element nodes on the physical communication links, each router including;

input ports for receiving messages,

output ports for sending messages from the router,

two types of virtual channels, each type of virtual channel having virtual channel buffers assigned to each physical communication link and capable of storing messages communicated between the processing element nodes over the physical communication links,

lookup tables associated with each of the input ports and each storing a lookup table virtual channel number, and

a virtual channel assignment mechanism for assigning an output next virtual channel number for determining the type of virtual channel to be used for routing from a next router along a given route, wherein the next virtual channel number is assigned based on the lookup table virtual channel number and an input next virtual channel number received from a previous router along the given route.

2. The multiprocessor system of claim 1 wherein the virtual assignment mechanism ascertains whether a given hop in a route is within one dimension or if the given hop is switching dimensions, and if the given hop is switching dimensions, the virtual assignment mechanism sets the output next virtual channel number equal to the lookup table virtual channel number, and if the given hop is within one dimension, the virtual assignment mechanism sets the output next virtual channel number equal to the lookup table virtual channel number logically OR'"'"'d with the input next virtual channel number.

3. The multiprocessor system of claim 1 wherein the topology is a torus topology, wherein at least one of the n dimensions has a radix greater than four.

4. The multiprocessor computer system of claim 1 wherein the virtual channel assignment mechanism include a programmable register having virtual channel select enable bit having a first state and a second state, wherein the virtual channel assignment mechanism is responsive to the virtual channel select enable bit being in the first state to set the output next virtual channel number equal to the input next virtual channel number.

5. The multiprocessor system of claim 4 wherein the virtual channel assignment mechanism is responsive to the virtual channel select enable bit being in the second state to ascertain whether a given hop in a route is within one dimension or if the given hop is switching dimensions, and if the given hop is switching dimensions, the virtual assignment mechanism sets the output next virtual channel number equal to the lookup table virtual channel number, and if the given hop is within one dimension, the virtual assignment mechanism sets the output next virtual channel number equal to the lookup table virtual channel number logically OR'"'"'d with the input next virtual channel number.

6. The multiprocessor system of claim 4 wherein the virtual channel select enable bit is in the first state for when the multiprocessor system is configured in a topology where none of the n dimensions have a radix greater than four.

7. The multiprocessor system of claim 6 wherein the configured topology is a n dimensional hypercube.

8. The multiprocessor system of claim 5 wherein the virtual channel select enable bit is in the second state for when the multiprocessor system is configured in a topology, wherein at least one of the n dimensions has a radix greater than four.

9. The multiprocessor system of claim 8 wherein the configured topology is a torus topology.

10. The multiprocessor system of claim 1 wherein a dateline is associated with each type of virtual channel, each dateline representing a communication link between two virtual channel buffers, which complete a cyclic path in their associated type of virtual channel, wherein if messages cross the dateline a cyclic buffer dependency can occur which creates a deadlock, and wherein the lookup table virtual channel number is set to assure that messages do not cross datelines.