High-performance non-blocking switch with multiple channel ordering constraints
First Claim
1. A switch for receiving data simultaneously from multiple sources and for forwarding data to multiple destinations, the switch having a plurality of input ports and a plurality of output ports and comprising:
- at least one buffer provided within the switch to store a plurality of packets received simultaneously from the plurality of input ports, wherein each of the plurality of packets is associated with one of a plurality of channels and wherein there are ordering constraints between the plurality of channels;
at least one ordered queue comprising a plurality of flag fields, each of the plurality of flag fields for storing a channel identification flag associated with at least one of the plurality of channels to indicate storage of one of the plurality of packets of the associated channel by said at least one buffer; and
a plurality of output managers provided within the switch, one output manager associated with each of the plurality of output ports, each of the plurality of output managers coupled to the at least one ordered queue to select a packet from the at least one buffer for output at the associated one of a plurality of output ports in response to the flag fields of each of the at least one ordered queue, wherein the packets are selected from the at least one buffer in response to the ordering constraints between the plurality of channels.
4 Assignments
0 Petitions
Accused Products
Abstract
An architecture and coherency protocol for use in a large SMP computer system includes a hierarchical switch structure which allows for a number of multi-processor nodes to be coupled to the switch to operate at an optimum performance. Within each multi-processor node, a simultaneous buffering system is provided that allows all of the processors of the multi-processor node to operate at peak performance. A memory is shared among the nodes, with a portion of the memory resident at each of the multi-processor nodes. Each of the multi-processor nodes includes a number of elements for maintaining memory coherency, including a victim cache, a directory and a transaction tracking table. The victim cache allows for selective updates of victim data destined for memory stored at a remote multi-processing node, thereby improving the overall performance of memory. Memory performance is additionally improved by including, at each memory, a delayed write buffer which is used in conjunction with the directory to identify victims that are to be written to memory. An arb bus coupled to the output of the directory of each node provides a central ordering point for all messages that are transferred through the SMP. The messages comprise a number of transactions, and each transaction is assigned to a number of different virtual channels, depending upon the processing stage of the message. The use of virtual channels thus helps to maintain data coherency by providing a straightforward method for maintaining system order. Using the virtual channels and the directory structure, cache coherency problems that would previously result in deadlock may be avoided.
-
Citations
46 Claims
-
1. A switch for receiving data simultaneously from multiple sources and for forwarding data to multiple destinations, the switch having a plurality of input ports and a plurality of output ports and comprising:
-
at least one buffer provided within the switch to store a plurality of packets received simultaneously from the plurality of input ports, wherein each of the plurality of packets is associated with one of a plurality of channels and wherein there are ordering constraints between the plurality of channels;
at least one ordered queue comprising a plurality of flag fields, each of the plurality of flag fields for storing a channel identification flag associated with at least one of the plurality of channels to indicate storage of one of the plurality of packets of the associated channel by said at least one buffer; and
a plurality of output managers provided within the switch, one output manager associated with each of the plurality of output ports, each of the plurality of output managers coupled to the at least one ordered queue to select a packet from the at least one buffer for output at the associated one of a plurality of output ports in response to the flag fields of each of the at least one ordered queue, wherein the packets are selected from the at least one buffer in response to the ordering constraints between the plurality of channels. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 41, 42, 43, 44)
a first channel, wherein packets on the first channel are selected in any order for transmission to one of the plurality of output ports;
a second channel, wherein packets on the second channel are selected for multi-cast transmission to more than one of the plurality of output ports in a common order;
a third channel, wherein packets in the third channel that are received after packets in the second channel are retained at the at least one buffer until the packets in the second channel are forwarded to at least one of the plurality of output ports; and
a fourth channel, wherein packets on the fourth channel are transmitted to one of the plurality of output ports in the same order at which they were received at the at least one buffer.
-
-
10. The switch according to claim 1, wherein the at least one buffer further comprises a plurality of entries, with each entry further comprising:
-
a channel field for identifying a channel of the packet stored at a first entry corresponding to the channel; and
at least one index field for identifying a next entry in the at least one buffer, the next entry storing a packet corresponding to a type of packet of the first entry.
-
-
11. The switch according to claim 10, further comprising a plurality of head pointers corresponding to the at least one ordered queue, each of the head pointers storing an index to an entry of the at least one buffer that is the next entry to be processed in the at least one ordered queue.
-
12. The switch according to claim 1, wherein packets associated with a subset of the plurality of channels have processing dependencies with regard to packets associated with other ones of the plurality of channels, and wherein each of the flag fields in each of the entries in each of the at least one ordered queue further comprises a plurality of dependency flags for indicating channels having dependencies.
-
13. The switch according to claim 12, wherein the channel dependency flags are set to preclude processing of one of the plurality of packets in the at least one buffer associated with one of the plurality of channels until previously received packets associated with the channels having the dependency flags set are processed.
-
14. The switch according to claim 12, wherein the channel dependency flags are set in an entry of one of the at least one ordered queue to identify previously received packets that are to be processed before the packet associated with the entry.
-
15. The switch according to claim 1, further comprising a plurality of search engines, one search engine for each flag field of the at least one ordered queue, for selecting one of the packets of the at least one buffer corresponding to the channel associated with the flag field for forwarding to the output manager.
-
16. The switch according to claim 15, wherein each one of the search engines further comprises means for clearing the flag corresponding to the selected packet when the selected packet is selected for output by the output manager.
-
17. The switch according to claim 12, further comprising means for conditionally setting the dependency flags responsive to addresses of previously received packets in the at least one buffer.
-
18. The switch according to claim 12, wherein the dependency flags are set if an address of one of the plurality of packets at an associated location in the at least one buffer matches an address of a previously stored address in the input buffer.
-
41. The switch according to claim 1 wherein the at least one buffer further comprises:
a plurality of buffers.
-
42. The switch according to claim 1 wherein the at least one buffer further comprises:
an input buffer.
-
43. The switch according to claim 1 wherein the at least one ordered queue further comprises:
a plurality of output queues.
-
44. The switch according to claim 1 wherein said at least one ordered queue further comprises:
a plurality of ordered queues.
-
19. A multi-processing system comprising:
-
a plurality of nodes;
a switch, coupling the plurality of nodes, the switch having a plurality of input ports for receiving data from the plurality of nodes and a plurality of output ports for forwarding data to the plurality of nodes, wherein the switch comprises;
at least one buffer provided within the switch to store a plurality of packets received from the plurality of input ports, wherein each of the plurality of packets are associated with one of a plurality of channels and wherein there are ordering constraints between the plurality of channels;
at least one ordered queue comprising a plurality of flag fields, each of the plurality of flag fields including a channel identification flag associated with at least one of the plurality of channels for indicating storage of one of the plurality of packets of the associated channel by the at least one buffer; and
a plurality of output managers provided within the switch, one output manager associated with each of the plurality of output ports, each of the plurality of output managers coupled to the at least one ordered queue to select a packet from the at least one buffer for output at the associated one of a plurality of output ports in response to the flag fields of each of the at least one ordered queue, wherein the packets are selected from the at least one buffer in response to the ordering constraints between the plurality of channels. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 45, 46)
a first channel, wherein packets on the first channel are selected in any order for transmission to one of the plurality of output ports;
a second channel, wherein packets on the second channel are selected for multi-cast transmission to more than one of the plurality of output ports in a common order;
a third channel, wherein packets in the third channel that are received after packets in the second channel are retained at the at least one buffer until the packets in the second channel are forwarded to at least one of the plurality of output ports; and
a fourth channel, wherein packets on the fourth channel are transmitted to one of the plurality of output ports in the same order at which they were received at the at least one buffer.
-
-
28. The switch according to claim 19, wherein the at least one buffer further comprises a plurality of entries, with each entry further comprising:
-
a channel field for identifying a channel of the packet stored at a first entry corresponding to the channel;
at least one index field for identifying a next entry in the at least one buffer, the next entry storing a packet corresponding to a type of packet of the first entry; and
a plurality of head pointers corresponding to the plurality of ordered queues, each of the head pointers storing an index to an entry of the at least one buffer that is the next entry to be processed in the associated queue.
-
-
29. The switch according to claim 19, wherein packets associated with a subset of the plurality of channels have processing dependencies with regard to packets associated with other ones of the plurality of channels, and wherein each of the flag fields in each of the entries in each of the at least one ordered queue further comprises a plurality of dependency flags for indicating channels having dependencies.
-
30. The switch according to claim 29, wherein the channel dependency flags are set to preclude processing of one of the plurality of packets in the at least one buffer associated with one of the plurality of channels until previously received packets associated with the channels having the dependency flags set are processed.
-
31. The switch according to claim 29, wherein the channel dependency flags are set in an entry of one of the at least one ordered queue to identify previously received packets that are to be processed before the packet associated with the entry.
-
45. The switch according to claim 19 wherein the at least one buffer further comprises:
an input buffer.
-
46. The switch according to claim 19 wherein said at least one ordered queue further comprises:
a plurality of ordered queues.
-
32. A method of transferring data packets received into a switch from a plurality of inputs to a plurality of outputs such that predetermined ordering constraints are satisfied, the method including the steps of:
-
storing within the switch, in at least one buffer comprising a plurality of entries, data packets received from the plurality of input ports, wherein each of the packets is associated with at least one of a plurality of channels and where there are ordering constraints between the data packets;
providing within the switch at least one ordered queue comprising a plurality of entries corresponding in number to the plurality of entries of the at least one input buffer, each of the plurality of entries comprising a plurality of flag fields, each one of the flag fields associated with one or more of the channels, the plurality of flag fields comprising an identity flag for indicating the channel of a packet stored in a corresponding location of the at least one buffer;
setting the identity flag for each entry in the at least one ordered queue to indicate the receipt the packet from the one or more channels associated with the identity flag; and
selecting a data packet from the at least one buffer within said switch in response to the flag fields of the at least one ordered queue and further in response to the ordering constraints of the channels. - View Dependent Claims (33, 34, 35, 36, 37, 38, 39, 40)
a first channel, wherein packets on the first channel are selected in any order for transmission to one of the plurality of output ports;
a second channel, wherein packets on the second channel are selected for multi-cast transmission to more than one of the plurality of output ports in a common order;
a third channel, wherein packets in the third channel that are received after packets in the second channel are retained at the at least one buffer until the packets in the second channel are forwarded to at least one of the plurality of output ports; and
a fourth channel, wherein packets on the fourth channel are transmitted to one of the plurality of output ports in the same order at which they were received at the at least one buffer.
-
Specification