US6101181A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Virtual channel assignment in large torus systems
Assignee: Morgan Stanley and Co LLC
•
Filing: 1997-11-17
•
Granted: 2000-08-08
•
Expires: 2017-11-17
Abstract
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.
Inventors
- 👤 Randal S. Passint
- 👤 Greg Thorson
- 👤 Michael B. Galles
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 21:32
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17356; G06F15/17368; G06F15/17381
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
186 words
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.
Claim 2
Dependent Claim
186 words
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.
Claim 3
Dependent Claim
95 words
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.
Claim 4
Dependent Claim
27 words
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.
Claim 5
Dependent Claim
67 words
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.
Claim 6
Dependent Claim
111 words
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.
Claim 7
Dependent Claim
40 words
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.
Claim 8
Dependent Claim
15 words
The multiprocessor system of claim 6 wherein the configured topology is a n dimensional hypercube.
Claim 9
Dependent Claim
42 words
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.
Claim 10
Dependent Claim
14 words
The multiprocessor system of claim 8 wherein the configured topology is a torus topology.
Claim 11
Dependent Claim
74 words
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.
References Cited (Backward Citations)
US28577A
Cited
USRE28577E
Cited
US4330858A
Cited
US5276899A
Cited
EP0501524A2
Cited
US5341504A
Cited
US4980822A
Cited
US4630259A
Cited
WO1987001750A1
Cited
US4771391A
Cited
US4811214A
Cited
US4933933A
Cited
WO1988008652A1
Cited
US5170482A
Cited
US5008882A
Cited
US4868818A
Cited
US5361334A
Cited
US5105424A
Cited
EP0353819A2
Cited
US5117350A
Cited
US5347450A
Cited
US5031211A
Cited
US5036459A
Cited
US5157692A
Cited
US5134690A
Cited
US5218601A
Cited
US5197130A
Cited
US5280474A
Cited
US5218676A
Cited
US5161156A
Cited
US5210705A
Cited
US5201044A
Cited
EP0473452A2
Cited
EP0475282A2
Cited
US5331631A
Cited
EP0479520A2
Cited
US5239545A
Cited
US5625836A
Cited
US5383191A
Cited
US5175733A
Cited
US5365228A
Cited
US5313645A
Cited
US5367692A
Cited
US5555542A
Cited
US5517497A
Cited
US5550589A
Cited
US5548639A
Cited
US5313628A
Cited
US5590284A
Cited
US5475858A
Cited
EP0570729A2
Cited
US5333279A
Cited
US5533198A
Cited
US5440547A
Cited
US5546598A
Cited
US5596742A
Cited
US5353283A
Cited
US5546596A
Cited
US5390164A
Cited
WO1995016236A1
Cited
US5737628A
Cited
US5434995A
Cited
US5546549A
Cited
US5592610A
Cited
WO1996032681A1
Cited
US5659796A
Cited
US5701416A
Cited
US5682479A
Cited
US5721819A
Cited
WO1996037834A1
Cited
US5613071A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-08-08 | 2004-02-07 | 2004-08-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-08-08 | 2008-02-07 | 2008-08-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-08-08 | 2012-02-07 | 2012-08-08 | $7700.00 | Window Closed / Lapsed |