Cross dependency checking logic

• US 9,158,691 B2
• Filed: 12/14/2012
• Issued: 10/13/2015
• Est. Priority Date: 12/14/2012
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Saund, Gurjeet S., Kaushikkar, Harshavardhan
• Primary Examiner(s): Tseng, Cheng-Yuan
• Assistant Examiner(s): Perez-Velez, Rocio Del Mar
• Application Number:
  US13/715,623
• Publication Number:
  US 20140173218A1
• Time in Patent Office: 1,033 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0822 Copy directories local copy tags for implementing a bus snooping protocol G06F12/0831
• CPC Class Codes: G06F 12/0828 with concurrent directory accessing, i.e. handling multiple concurrent coherency transactions

Abstract

Systems and methods for maintaining an order of transactions in the coherence point. The coherence point stores attributes associated with received transactions in an input request queue (IRQ). When a new transaction is received by the coherence point, the IRQ is searched for other entries with the same request address or the same victim address as the new transaction. If one or more matches are found, the new transaction entry points to the entry storing the most recently received transaction with the same address. The new transaction is stalled until the transaction it points to has been completed in the coherence point.

Claims

1. A coherence point comprising:

a queue configured to store a plurality of outstanding transactions;

a level two (L2) duplicate tag unit; and

a dependency logic unit coupled to the queue, wherein the dependency logic unit comprises circuitry configured to;

search the queue for outstanding transactions that reference a first address responsive to receiving a first transaction at the coherence point, wherein the first transaction includes a request address equal to the first address; and

mark the first transaction as dependent on a second transaction responsive to determining the second transaction is a most recently received transaction in the queue that references the first address;

wherein the coherence point is configured to prevent the first transaction from searching the L2 duplicate tags until the second transaction is completed.

2. The coherence point as recited in claim 1, wherein the queue is searched for outstanding transactions that reference the first address in either a request address field or a victim address field.

3. The coherence point as recited in claim 2, wherein the coherence point is configured to stall the first transaction until the second transaction is completed in the coherence point.

4. The coherence point as recited in claim 3, wherein marking the first transaction as dependent on the second transaction comprises setting a head pointer field of the first transaction to point to the second transaction.

5. The coherence point as recited in claim 4, wherein the coherence point is configured to store attributes associated with the first transaction in a first entry of the queue, and wherein the first entry comprises the head pointer field.

6. The coherence point as recited in claim 5, wherein the coherence point is configured to set the head pointer field of the first entry to point to itself responsive to determining the second transaction has been completed in the coherence point.

7. A method comprising:

receiving a first transaction with a first request address and a first victim address at a coherence point, wherein the coherence point includes level two (L2) duplicate tags;

searching a queue for any transactions with the first request address or the first victim address in any address field, wherein the queue is configured to store entries corresponding to a plurality of outstanding transactions;

identifying a most recently received transaction in the queue that references either the first request address or the first victim address;

marking the first transaction as dependent on the most recently received transaction in the queue that references either the first request address or the first victim address;

stalling the first transaction until the most recently received transaction that references either the first request address or the first victim address is completed in the coherence point;

preventing the first transaction from searching the L2 duplicate tags until the most recently received transaction in the queue that references either the first request address or the first victim address is completed.

8. The method as recited in claim 7, further comprising storing attributes associated with the first transaction in a first entry of the queue.

9. The method as recited in claim 8, wherein the attributes comprise a head pointer field, and wherein marking the first transaction as dependent on the most recently received transaction in the queue that references either the first request address or the first victim address comprises setting the head pointer field of the first entry to point to an entry corresponding to the most recently received transaction in the queue that references either the first request address or the first victim address.

10. The method as recited in claim 9, further comprising setting the head pointer field of the first entry to point to itself responsive to determining the most recently received transaction in the queue that references either the first request address or the first victim address has been completed in the coherence point.

11. The method as recited in claim 10, further comprising allowing the first transaction to proceed responsive to determining the head pointer field of the first entry references itself.

12. A method comprising:

receiving a first transaction at a coherence point, wherein the first transaction references a first address;

searching a queue for any transactions that reference the first address, wherein the queue comprises a plurality of entries configured to store an outstanding transaction, and wherein each entry includes an address dependency head pointer field;

storing the first transaction in a first entry of the queue;

setting a first head pointer of the first entry to point to the first entry of the queue responsive to finding no transactions that reference the first address in the queue; and

setting the first head pointer of the first entry to point to a second entry of the queue that stores a second transaction, responsive to determining the second transaction is a most recently received transaction in the queue that references the first address.

13. The method as recited in claim 12, further comprising stalling the first transaction responsive to determining the first head pointer points to the second transaction.

14. The method as recited in claim 13, further comprising allowing the first transaction to proceed responsive to determining the first head pointer points to the first entry.

15. The method as recited in claim 14, further comprising storing a plurality of attributes associated with the first transaction in a first entry of the queue.

16. The method as recited in claim 15, wherein the plurality of attributes comprise the first head pointer.

17. The method as recited in claim 16, further comprising setting the first head pointer to point to the first entry of the queue responsive to determining the second transaction has been completed in the coherence point.

18. An apparatus comprising a coherence point, wherein the coherence point comprises:

a queue comprising a plurality of entries, wherein each entry is configured to store an outstanding transaction and includes an address dependency head pointer field; and

an address dependency logic unit coupled to the queue;

wherein the coherence point is configured to;

search one or more address fields of each entry of the queue for matches to any of one or more first addresses, responsive to receiving a new transaction with the one or more first addresses;

identify a most recently received transaction in the queue with an address field that matches any of the one or more first addresses;

store the new transaction in a first entry of the queue;

update a head pointer field of the first entry to point to a second entry of the queue, wherein the second entry stores the most recently received transaction in the queue with an address field that matches any of the one or more first addresses; and

stall the new transaction until the most recently received transaction in the queue with an address field that matches any of the one or more addresses has been completed in the coherence point.

19. The apparatus as recited in claim 18, wherein the coherence point is further configured to allow the new transaction to proceed responsive to determining the most recently received transaction in the queue with an address field that matches any of the one or more addresses has been completed in the coherence point.

20. The apparatus as recited in claim 19, wherein the one or more first addresses comprise a first request address and a first victim address, and wherein the one or more address fields of each entry of the queue comprise a request address field and a victim address field.

21. The apparatus as recited in claim 20, wherein the coherence point is further configured to update the head pointer field of the first entry to point to itself responsive to determining the most recently received transaction in the queue with either a request address field or a victim address field that matches either the first request address or the first victim address has been completed.