Multi-processor system for transferring data without incurring deadlock using hierarchical virtual channels

• US 6,094,686 A
• Filed: 12/23/1998
• Issued: 07/25/2000
• Est. Priority Date: 10/24/1997
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Compaq Computer Corporation (HP Inc.)
• Inventors: Sharma, Madhumitra
• Primary Examiner(s): An, Meng-Ai T.
• Assistant Examiner(s): Whitmore, Stacy
• Application Number:
  US09/220,161
• Time in Patent Office: 580 Days
• Field of Search: 710/129, 710/131, 710/20, 710/21, 710/33, 710/29, 710/52, 710/100, 712/1, 712/28, 712/32, 713/200-209, 711/100, 711/130, 711/147, 711/159, 370/229, 370/235, 370/351, 370/464, 340/825, 340/825.01, 709/236-240
• US Class Current: 709/240
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0826 Limited pointers directories; State-only directories without pointers
• CPC Class Codes: G06F 15/17375 One dimensional, e.g. linear array, ring

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 into 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.

Claims

1. A multi-processor computer system comprising:

a plurality of nodes, each of the plurality of nodes including a global port for transmitting a plurality of packets to other ones of the plurality of nodes, each of the plurality of packets being associated with one of a plurality of channels having a hierarchical order from lowest to highest order; and

a switch, coupling the plurality of nodes, the switch including at least one buffer coupled to receive packets, said buffer including gencric entry slots for receiving and storing packets from a channel of any hierarchical order, and dedicated entry slots for receiving and storing packets from a channel of a predetermined hierarchical order, a packet entry into a generic entry slot being a generic entry, and a packet entry into a dedicated entry slot being a dedicated entry,

wherein each of the plurality of nodes includes a plurality of sources, each of the sources for transmitting packets on one of the plurality of channels, and wherein the switch further comprises;

flow control logic for providing a flow control signal to selectively disable the transmission of packets by one or more of the plurality of sources responsive to an availability of the at least one generic entry and the at least one dedicated entry of each one of the plurality of channels, wherein the availability of the at least one generic entry and the at least one dedicated entry is determined by a number of packets in transit between the at least one source element and the destination buffer, such that the availability is a presence of the at least one generic entry and the at least one dedicated entry of each one of the plurality of channels.

2. The multi-processor of claim 1, wherein the flow control logic further comprises:

a destination count register, coupled to at least one buffer, the destination count register including a plurality of entries corresponding in number to the plurality channels, each entry for storing a count of the number of packets being associated with the channel that are stored in at least one buffer; and

a flag register comprising a plurality of entries corresponding in number to the plurality of entries in the destination count register, for indicating whether the count in the corresponding entry of the destination count register is zero.

3. The multi-processor of claim 2, wherein the flow control logic further comprises:

a transit counter, coupled to the at least one buffer, the transit counter comprising a plurality of transit count entries corresponding in number to the at least one node coupled to the buffer, each entry of the transit counter storing a transit count indicating a number of packets data that are in transit between the associated node and the at least one buffer.

4. The multi-processor of claim 3, wherein the transit count is determined in response to the number of previous cycles during which the flow control signal was asserted.

5. The interface according to claim 4, wherein the flow control signal is asserted in response to a count of the number of at least one generic entries (Gen_-- count) available in the buffer, a number of the at least one generic entries used in the buffer (Gen_-- dest_-- count), a total number of entries in the buffer (Size), a number of flags in the flag register that are zero (Flags_-- unasserted), the transit count (Transit_-- count) and a number of the plurality of nodes (Num_-- Nodes).

6. The interface according to claim 5, wherein the count of the number of generic entries (Gen_-- count) is determined by the below equation:

space="preserve" listing-type="equation">Gen.sub.-- count=Size-Gen.sub.-- dest.sub.-- count-Flags.sub.-- unasserted.

7. The interface according to claim 6, wherein the flow control signal is asserted if the below equation is true:

space="preserve" listing-type="equation">Gen.sub.-- count≧

Transit.sub.-- count+Num.sub.-- Nodes.

8.

8. A multi-processor computer system comprising:

a plurality of nodes, including source nodes, each of the plurality of nodes including a global port for transmitting a plurality of packets to other ones of the plurality of nodes, each of the plurality of packets being associated with one of a plurality of channels having a hierarchical order from lowest to highest order; and

a switch, coupling the plurality of nodes, the switch including at least one buffer coupled to receive packets, said buffer including generic entry slots for receiving and storing packets from a channel of any hierarchical order, and dedicated entry slots for receiving and storing packets from a channel of a predetermined hierarchical order, a packet entry into a generic entry slot being a generic entry, and a packet entry into a dedicated entry slot being a dedicated entry; and

a source count register at each of the plurality of source nodes, the source count register including a number of source count entries corresponding to the plurality of channels, each entry for storing a count of the number packet of the associated channel stored in the destination buffer.

9. The multi-processor of claim 8, wherein transmission of packets associated with a given channel is always permitted if the value of the source count entry corresponding to the given channel is equal to zero.

10. An interface for transferring data between two elements of a computer system without incurring deadlock comprising:

at least one source clement capable of providing a plurality of packets, each of the plurality of packets associated with one of a plurality of channels;

a destination, receiving packets from at least one source element;

a destination buffer, coupled to at least one data line associated with the at least one source element and including a plurality of entries including at least one dedicated entry for each one of the plurality of channels and at least one generic entry for storing packets associated with any of the plurality of channels; and

flow control logic, coupled to the at least one source element, for selectively disabling the transmission of packets by the at least one source element responsive to availability of the at least one generic entry and the at least one dedicated entry for each one of the plurality of channels, wherein the availability of the at least one generic entry and the at least one dedicated entry is determined by an estimated number of packets in transit between the at least one source element and the destination buffer.

11. The interface according to claim 10, wherein the flow control logic further includes means for allowing the at least one source element to transmit packets to the destination buffer when the at least one dedicated entry associated with the channel that is associated with the at least one source element is available.

12. The interface of claim 10, wherein the source element further comprises:

a source counter including a plurality of entries corresponding in number to the plurality of channels, each entry for storing a count of the number of packets associated with the channel that are stored in the destination buffer.

13. The interface of claim 10 further comprising:

a destination count register, coupled to the destination buffer, the destination count register including a plurality of entries corresponding in number to the plurality channels, each entry for storing a count of the number of packets associated with the channel that are stored in the destination buffer; and

a flag register comprising a plurality of entries corresponding in number to the plurality of entries in the destination count register, for indicating whether the count in the corresponding entry of the destination count register is zero.

14. Thc interface of claim 13 further comprising:

a transit count register, coupled to the destination buffer, for storing a transit count indicating a number of packets that are in transit between the at least one source element and the destination buffer as a result of a latency between the at least one source element and the destination buffer.

15. The interface of claim 14, wherein the flow control logic asserts a flow control signal to inhibit transmission of packets by the at least one source element in response to the contents of the destination count register and the transit count register.

16. The interface of claim 15, wherein the transit count is determined in response to the number of previous cycles during which the flow control signal was asserted.

17. The interface according to claim 16, wherein the flow control signal is determined in response to a count of the number of generic entries (Gen_-- count) available in the buffer, a number of generic entries used in the buffer (Gen_-- dest_-- count), a number of entries in the buffer (Size), a number of flags in the flag register that are zero (Flags_-- unasserted), the transit count (Transit_-- count) and a number of the at least one source (Num_-- Sources).

18. The interface according to claim 17, wherein the count of the number of generic entries (Gen_-- count) is determined by the below equation:

space="preserve" listing-type="equation">Gen.sub.-- count=Size-Gen.sub.13 dest.sub.-- count-Flags.sub.-- unassertcd.

19.

19. The interface according to claim 18, wherein the flow control signal is asserted if the below equation is true:

space="preserve" listing-type="equation">Gen.sub.-- count>

=Transit.sub.-- count+Num.sub.-- Sources.

20. The interface according to claim 12, wherein transmission of packets corresponding to one of the channels is enabled if the value of the source counter entry corresponding to the channel is equal to zero.

21. The interface according to claim 12, wherein the at least one source further comprises arbitration logic for selecting one of the plurality of channels for transmission of a packet in response to the flow control logic, the source counter and further in response to ordering constraints of the plurality of channels.

22. A method for interfacing a plurality of source nodes to a shared buffer without incurring deadlock, each of the plurality of source nodes transmitting packets on a plurality of different channels comprising the steps of:

dedicating, in the shared buffer comprising a plurality of entries, at least one entry for each of the plurality of different channels of each of the source nodes, the remaining entries being generic entries for storing packets on any of the plurality of channels from any of the source nodes;

monitoring, at each of the plurality of source nodes, the number of packets of each of the plurality of different channels that are stored in the shared buffer;

monitoring, at the shared buffcr, whether the dedicated entries for each of the different channels for each of the plurality of source nodes are available; and

providing a flow control signal to inhibit the writing of the shared buffer by the plurality of source nodes in response to a determined availability of generic entries in the shared buffer and further in response to a determined number of packets in transit between the plurality of source nodes and the dedicated buffer.

23. The method of claim 22, wherein the step of providing the flow control signal further comprises the step of determining, for each of the source nodes, a transit count indicating a number of packets that are in transit between the source node and the shared buffer, wherein the transit count is determined in response to the status of the flow control signal in a plurality of previous packet transfer cycles.

24. The method of claim 23 further comprising the steps of:

issuing packets by the plurality of source nodes in response to the number of packets of each of the channels that are stored in the shared buffer and further in response to the flow control signal, wherein a source node is always permitted to issue packet on a given channel to the buffer when the monitored count of the number of packets of the given channel that are stored in the buffer is equal to zero.