Store queue with token to facilitate efficient thread synchronization

Patent metadata

Field	Value
Publication number	US-9280343-B2
Application number	US-53871709-A
Country	US
Kind code	B2
Filing date	Aug 10, 2009
Priority date	Aug 10, 2009
Publication date	Mar 8, 2016
Grant date	Mar 8, 2016

Abstract

Some embodiments of the present invention provide a system for operating a store queue, wherein the store queue buffers stores that are waiting to be committed to a memory system in a processor. During operation, the system examines an entry at the head of the store queue. If the entry contains a membar token, the system examines an unacknowledged counter that keeps track of the number of store operations that have been sent from the store queue to the memory system but have not been acknowledged as being committed to the memory system. If the unacknowledged counter is non-zero, the system waits until the unacknowledged counter equals zero, and then removes the membar token from the store queue.

First claim

What is claimed is:

1. A method for processing entries in a store queue, wherein the store queue buffers stores that are waiting to be committed to a memory system in a processor, comprising:
examining a given entry at the head of the store queue, wherein each entry in the store queue includes a membar flag and a data field, wherein the membar flag indicates whether the entry contains a membar token and wherein, when the entry corresponds to a store, the data field stores data for the store for the entry, and, when the entry corresponds to a membar instruction, the data field stores the membar token, wherein the data is to be committed from the store queue to the memory system; and
if the membar flag for the given entry indicates that the given entry contains a membar token,
examining an unacknowledged counter that keeps track of the number of store operations that have been sent from the store queue to the memory system but have not been acknowledged as being committed to the memory system,
if the unacknowledged counter is non-zero, waiting until the unacknowledged counter equals zero, and
removing the membar token from the store queue by marking the given entry as invalid and unsetting the membar flag for the given entry.

2. The method of claim 1 , wherein if the given entry is a store, the method further comprises:
waiting, if necessary, until the memory system is ready to accept the store;
sending the store to the memory system so that the memory system can commit the store;
incrementing the unacknowledged counter; and
removing the store from the store queue.

3. The method of claim 2 , wherein removing the store from the store queue involves:
marking the given entry as invalid; and
incrementing a send pointer that points to the head of the store queue, to point to a following entry in the store queue modulo the size of the store queue.

4. The method of claim 1 , wherein upon encountering a store or a membar instruction while the processor is executing instructions, the method further comprises:
if the store queue is full, waiting until the store queue is not full; and
inserting the store or a membar token into the store queue.

5. The method of claim 4 , wherein inserting the store or the membar token into the store queue involves:
marking the entry containing the store or the membar token as valid;
if a membar token is being inserted, setting a membar flag in the entry; and
incrementing a tail pointer that points to the tail of the store queue, to point to a following entry in the store queue modulo the size of the store queue.

6. The method of claim 1 , further comprising decrementing the unacknowledged counter upon receiving an acknowledgment from the memory system at the store queue, the acknowledgment indicating that the memory system has committed a store received from the store queue.

7. The method of claim 1 , wherein each entry in the store queue includes:
a valid flag indicating whether there exists a valid store or membar token in the entry;
an address for a store; and
a byte mask for the store.

8. The method of claim 7 , wherein removing the membar token from the store queue involves incrementing a send pointer that points to the head of the store queue to point to a following entry in the store queue modulo the size of the store queue,
wherein marking the given entry as invalid comprises changing the valid flag and the membar flag for the given entry.

9. The method of claim 1 , wherein the membar instruction is a store-store membar that ensures that all stores preceding the membar instruction in program order have been committed to the memory system before any stores following the membar instruction in program order are committed to the memory system.

10. The method of claim 1 , further comprising:
in response to receiving the membar instruction, placing the membar token in a first entry of the store queue and setting a membar flag for the first entry, wherein the first entry is at the head of the store queue.

11. A processor with a store queue, comprising:
the processor;
the store queue within the processor, wherein each entry in the store queue includes a membar flag and a data field, wherein the membar flag indicates whether the entry contains a membar token and wherein, when the entry corresponds to a store, the data field stores data for the store for the entry, and when the entry corresponds to a membar instruction, the data field stores the membar token, wherein the data is to be committed from the store queue to the memory system; and
an unacknowledged counter within the store queue that keeps track of the number of store operations that have been sent from the store queue to a memory system but have not been acknowledged as being committed to the memory system;
wherein when the membar token is at the head of the store queue, the store queue is configured to,
examine the unacknowledged counter,
if the unacknowledged counter is non-zero, wait until the unacknowledged counter equals zero, and
remove the membar token from the store queue by marking the entry containing the membar token as invalid and unsetting the membar flag for the entry.

12. The processor of claim 11 , wherein if the entry at the head of the store queue is a store, the store queue is configured to:
wait, if necessary, until the memory system is ready to accept the store;
send the store to the memory system so that the memory system can commit the store;
increment the unacknowledged counter; and
remove the store from the store queue.

13. The processor of claim 12 , wherein while removing the store from the store queue, the store queue is configured to:
mark the entry containing the store as invalid; and
increment a send pointer that points to the head of the store queue, to point to a following entry in the store queue modulo the size of the store queue.

14. The processor of claim 12 , wherein upon encountering a store or a membar instruction while the processor is executing instructions, the store queue is configured to:
wait, if the store queue is full, until the store queue is not full; and
insert the store or a membar token into the store queue.

15. The processor of claim 14 , wherein while inserting the store or the membar token into the store queue, the store queue is configured to:
mark the entry containing the store or the membar token as valid;
if a membar token is being inserted, set a membar flag in the entry; and
increment a tail pointer that points to the tail of the store queue, to point to a following entry in the store queue modulo the size of the store queue.

16. The processor of claim 11 , wherein upon receiving an acknowledgment from the memory system at the store queue, wherein the acknowledgment indicates that the memory system has committed a store received from the store queue, the store queue is configured to decrement the unacknowledged counter.

17. The processor of claim 11 , wherein the membar is a store-store membar that ensures that all stores preceding the membar in program order have been committed to the memory system before any stores following the membar in program order are committed to the memory system.

18. A computer system containing a processor with a store queue, comprising:
the processor;
the store queue within the processor, wherein each entry in the store queue includes a membar flag and a data field, wherein the membar flag indicates whether the entry contains a membar token and wherein, when the entry corresponds to a store, the data field stores data for th

Assignees

• Zeffer Haakan E
• Cypher Robert E
• Chaudhry Shailender
• Oracle America Inc

Inventors

• Zeffer Haakan E
• Cypher Robert E
• Chaudhry Shailender

Classifications

• G06F9/522

  Barrier synchronisation · CPC title

• G06F9/30087

  Synchronisation or serialisation instructions · CPC title

• G06F9/3834

  Maintaining memory consistency · CPC title

• G06F9/3004 Primary

  to perform operations on memory · CPC title