Multiprocessing system employing pending tags to maintain cache coherence

• US 6,272,602 B1
• Filed: 03/08/1999
• Issued: 08/07/2001
• Est. Priority Date: 03/08/1999
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Yamauchi, Alan, Lauterbach, Gary, Singhal, Ashok
• Primary Examiner(s): Kim, Matthew
• Assistant Examiner(s): CHACE, CHRISTIAN
• Application Number:
  US09/265,233
• Time in Patent Office: 883 Days
• Field of Search: 711/141, 711/144, 711/146
• US Class Current: 711/144
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0831 using a bus scheme, e.g. with bus monitoring or watching means

Abstract

A pending tag system and method to maintain data coherence in a processing node during pending transactions in a transaction pipeline. A pending tag storage unit may be coupled to a cache controller and configured to store pending tags each indicative of a coherence state for a data line corresponding to a pending transaction within the transaction pipeline. The pending tag storage unit includes a total amount of storage which is substantially less than an amount required to store tags contained in the full tag array for the cache memory. When a pending tag exists in the pending tag storage unit, the coherence state of the corresponding data line within the cache memory is dictated by the pending tag for snoop operations. Accordingly, data coherence is maintained during the period when transactions are pending, e.g., not yet presented to a processor and cache. When a pending transaction is completed, the coherence state of the corresponding data line as indicated by the fill tag array may be overwritten by the coherence state as indicated by the pending tag and the pending tag may deleted from the pending tag storage.

Claims

1. A processing node for connection to a transaction bus in a multiprocessor system, said processing node comprising:

a transaction pipeline having an input to receive transactions from said transaction bus;

a processor core coupled to receive said transactions output from said transaction pipeline;

a cache memory for storing a plurality of data lines, wherein said cache memory is coupled to said processor core;

a tag array for storing a plurality of tags each comprising address information and a coherence state for one of said plurality of data lines in said cache memory;

a cache controller coupled to said processor core, to said transaction bus, to said cache memory, and to said tag array, wherein said cache controller is configured to manage access to said cache memory and to update said tag array;

a pending tag storage unit coupled to said cache controller and configured to store a plurality of pending tags each indicative of a coherence state for a data line corresponding to a pending transaction within said transaction pipeline, wherein said pending tag storage unit includes a total amount of storage which is less than an amount required to store said plurality of tags contained in said tag array.

2. The processing node as recited in claim 1, wherein said pending tag storage unit is configured to store only pending tags corresponding to pending transactions.

3. The processing node as recited in claim 1, wherein said cache controller is configured to snoop transactions on said transaction bus to determine if a transaction on said transaction bus affects the coherence state indicated by one of said tags or one of said pending tags.

4. The processing node as recited in claim 1, wherein said tag array is set associative, and wherein said pending tag storage unit is fully associative.

5. The processing node as recited in claim 1, wherein said cache controller determines the coherence state according to a current transaction on said transaction bus based on the coherence state indicated by one of said pending tags stored in said pending tag storage unit when said current transaction corresponds to said one of said pending tags.

6. The processing node as recited in claim 1, wherein said cache controller determines the coherence state according to a current transaction on said transaction bus based on the coherence state indicated by of one of said tags stored in said tag array when said current transaction corresponds to said one of said tags and no corresponding pending tag is present in said pending tag storage unit.

7. The processing node as recited in claim 1, wherein a pending tag is created or updated in said pending tag storage unit for each transaction on said transaction bus that affects the coherence state indicated by one of said pending tags stored in said pending tag storage unit or one of said tags stored in said tag array according to tags in both said tag array and said pending tag storage unit.

8. The processing node as recited in claim 1, wherein each one of said pending tags corresponds to a pending transaction in said transaction pipeline, and wherein the each one of said pending tags indicates the coherence state as if its corresponding pending transaction has completed.

9. The processing node as recited in claim 1, wherein a transaction that is received from said bus is entered into said transaction pipeline and a corresponding pending tag is stored in said pending tag storage unit.

10. The processing node as recited in claim 9, wherein said pending tag that is stored in said pending tag storage unit upon receiving said transaction from said bus is deleted from said pending tag storage unit as said transaction is outputted from said transaction pipeline to said processor core.

11. The processing node as recited in claim 10, wherein a coherence state indicated by one of said tags stored within said tag array is updated with the coherence state indicated by the corresponding pending tag as said transaction is outputted from said transaction pipeline to said processor core.

12. A cache system within a node of a multi-node computer system, wherein a processor is coupled to said cache system and to a bus between nodes, said cache system comprising:

a tag array configured to store a tag including an address and a coherence state for each data line in a cache memory;

a pending tag storage unit configured to store a pending tag in response to a transaction being presented on said bus which affects the coherence state for a current cache data line or a transaction pending in the node according to tags in both said tag array and said pending tag storage unit; and

a controller coupled to said tag array and said pending tag storage unit, wherein said controller is configured to snoop transactions on said bus according to tags in both said tag array and said pending tag storage unit.

13. The cache system as recited in claim 12, wherein said pending tag indicates a coherence state as if said transaction is complete.

14. The cache system as recited in claim 12, wherein if a pending tag exists within said pending tag storage unit that corresponds to a transaction being snooped on said bus, a coherence state contained in said corresponding pending tag is used for said snooping regardless of if a corresponding tag exists in said tag array.

15. The cache system as recited in claim 14, wherein if said tag corresponding to the snooped transaction exists within said tag array and no corresponding pending tag exists within said pending tag storage unit, a coherence state contained in said tag array tag is used for said snooping.

16. The cache system as recited in claim 12, wherein the snooped transaction is ignored if no tag in said pending tag storage unit or in said tag array corresponds to the snooped transaction.

17. A computer system comprising:

a processor coupled to a bus;

a cache memory; and

a cache controller system coupled to said processor and said cache memory, wherein said cache controller system comprises;

a tag array configured to store a plurality of tags each including an address and a coherence state for a data line in said cache memory,

a pending tag storage unit configured to store a pending tag in response to a transaction being presented on said bus which corresponds to a particular data line in said cache memory and which will affect the coherence state for said particular data line when the transaction is completed, and

a control unit coupled to said tag array and said pending tag storage unit, wherein said control unit is configured to determine if a tag exists in said tag array having an address corresponding to a transaction present on said bus and to determine if a pending tag exists in said pending tag storage unit having an address corresponding to said transaction present on said bus.

18. The computer system as recited in claim 17, wherein said pending tag indicates a coherence state as if the transaction is complete.

19. The computer system as recited in claim 17, wherein said pending tag storage unit is further configured to store a pending tag or update an existing pending tag in response to a transaction being presented on said bus which corresponds to the existing pending tag.

20. The computer system as recited in claim 17, wherein said controller is further configured to perform a snoop operation to update coherence state information if said controller determines a tag or pending tag exists that corresponds to a transaction on said bus.

21. The computer system as recited in claim 20, wherein if a corresponding tag exists within said tag array and a corresponding pending tag also exists within said pending tag storage unit, the coherence state contained in said pending tag is used for said snoop operation.

22. A cache coherence method for a computer system having at least two nodes coupled by a transaction bus for communicating transactions between nodes, wherein a transaction on said transaction bus becomes a pending transaction in a node before completing in the node, wherein at least one node has a processor and cache memory, and wherein said cache memory comprises a plurality of cache lines, the method comprising:

storing tags in a tag array, wherein each tag indicates coherence information for a cache line according to completed transactions;

storing pending tags in a pending tag storage unit, wherein each pending tag indicates coherence information for a cache line according to a pending transaction; and

snooping a current transaction on the transaction bus, wherein said snooping comprises;

checking said tags and said pending tags for a tag that corresponds to said current transaction; and

if a corresponding tag or pending tag is found by said checking, updating said pending tags.

23. The method as recited in claim 22, wherein said updating comprises creating a new pending tag or modifying the coherence information indicated by an existing pending tag.

24. The method as recited in claim 22, wherein said pending tags indicate coherence information as if a corresponding transaction is complete.

25. The method as recited in claim 22, wherein said tags are not updated until a transaction completes.

26. The method as recited in claim 22, wherein if a corresponding tag or pending tag is found by said checking, using the coherence information indicated by the corresponding tag or pending tag for said updating, wherein if both a tag and a pending tag are found, then using the coherence information indicated by the corresponding pending tag for said updating.

27. A method for snooping bus transactions in a computer system having at least two nodes coupled by a transaction bus, the method comprising:

in response to a current transaction on the transaction bus, checking for a tag that corresponds to the current transaction in both a tag array and a pending tag storage unit, wherein said tag array stores tags indicating coherence information for cycles that have completed in a node and said pending tag storage unit stores tags indicating coherence information according to cycles that have not completed in the node;

if a tag corresponding to the current transaction is found at said checking, using coherence information indicated by the corresponding tag to determine if coherence information needs to be updated; and

updating the coherence information in the pending tag storage unit if necessary as determined at said using.

28. The method as recited in claim 27, wherein if both said tag array and said pending tag storage unit contain a corresponding tag at said checking, the corresponding tag from said pending tag storage unit is used for said using.

29. The method as recited in claim 27, wherein said tag array is configured to store a tag indicating coherence information for each cache line of a cache memory, and wherein said pending tag storage unit is configured to store tags indicating coherence information according to pending transactions only.

30. The method as recited in claim 27, wherein the maximum number of tags stored by said pending tag storage unit equals the maximum number of transactions that have not completed in the node.

31. The method as recited in claim 27, further comprising deleting a tag from said pending tag storage unit when a transaction corresponding to that tag completes.