Efficient store queue architecture

• US 20080082738A1
• Filed: 09/29/2006
• Published: 04/03/2008
• Est. Priority Date: 09/29/2006
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Cypher, Robert E., Chaudhry, Shailender
• Granted Patent: US 7,594,100 B2
• Time in Patent Office: Days
• US Class Current: 711/108
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 9/3824 Operand accessing
• CPC Class Codes: G06F 9/3826 Bypassing or forwarding of data results, e.g. locally between pipeline stages or within a pipeline stage
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/3867 using instruction pipelines

Abstract

One embodiment of the present invention provides a store queue that applies the stores to a memory subsystem in program order. This store queue includes a content-addressable memory (CAM), which holds pending stores and facilitates looking up stores based on addresses for the stores, wherein the CAM does not keep track of program order between stores to different addresses. The store queue also includes a program-order queue which keeps track of program order between the stores in the CAM and thereby facilitates applying the stores to the memory subsystem in program order. In a variation on this embodiment, the CAM is a priority CAM which holds separate copies of multiple stores with identical addresses, and when a lookup based on an address matches multiple stores, returns the youngest matching store.

Claims

1. An apparatus that implements a store queue which holds pending stores and applies the stores to a memory subsystem of a processor in program order, the apparatus comprising:

a content-addressable memory (CAM) which holds the stores that are pending and facilitates looking up the stores based on addresses for the stores;

wherein the CAM does not keep track of program order between stores to different addresses; and

a program-order queue which keeps track of program order between the stores in the CAM and thereby facilitates applying the stores to the memory subsystem in program order.

2. The apparatus of claim 1, wherein the CAM is a priority CAM which holds separate copies of multiple stores with identical addresses, and when a lookup based on an address matches multiple stores, returns the youngest matching store.

3. The apparatus of claim 2, wherein storage for the priority CAM is implemented using a random-access memory (RAM).

4. The apparatus of claim 2, further comprising a pipeline CAM which implements the functionality of the priority CAM and also keeps track of program order between stores, but only for a small number of issued stores that have not yet passed the trap stage of an execution pipeline in the processor;

wherein when a store passes the trap stage, the store moves from the pipeline CAM to the priority CAM.

5. The apparatus of claim 1, further comprising a store-queue finite state machine (FSM) which controls the operation of the store queue, wherein the FSM is configured to use ordering information maintained by the program-order queue to remove the oldest store from the priority CAM and to send the oldest store to the memory subsystem.

6. The apparatus of claim 5, wherein if a load matches a store in the store queue, the FSM is configured to perform a read-after-write (RAW) bypass which returns a data value for the load from the matching store.

7. The apparatus of claim 6, wherein if a load matches multiple stores in the store queue, the FSM is configured to perform a RAW bypass if all of the data being read by the load was written by the youngest matching store, otherwise the FSM is configured to not perform the RAW bypass.

8. The apparatus of claim 1, wherein each entry for a store in the CAM contains:

an address for the store;

a dataword for the store; and

a mask which indicates which bytes of the data word are to be written by the store.

9. The apparatus of claim 1, wherein the program-order queue is organized as a first-in-first-out (FIFO) buffer, wherein each entry for a store in the program-order queue contains:

an address for the store; and

an index into the CAM which specifies where an entry for the store is located in the CAM.

10. The apparatus of claim 1, wherein the CAM is not a priority CAM and is configured not to hold more than one store for the same address.

11. The apparatus of claim 1, wherein the store queue is configured to merge successive stores which are directed to the same address.

12. A computer system with a store queue which holds pending stores and applies the stores to a memory subsystem of a processor in program order, the computer system comprising:

a processor;

a memory; and

a store queue within the processor, wherein the store queue includes,

a content-addressable memory (CAM) which holds the stores that are pending and facilitates looking up the stores based on addresses for the stores, wherein the CAM does not keep track of program order between stores to different addresses, and

a program-order queue which keeps track of program order between the stores in the CAM and thereby facilitates applying the stores to the memory subsystem in program order.

13. The computer system of claim 12, wherein the CAM is a priority CAM which holds separate copies of multiple stores with identical addresses, and when a lookup based on an address matches multiple stores, returns the youngest matching store.

14. The apparatus of claim 13, wherein storage for the priority CAM is implemented using a random-access memory (RAM).

15. The computer system of claim 13, wherein the store queue further includes a pipeline CAM which implements the functionality of the priority CAM and also keeps track of program order between stores, but only for a small number of issued stores that have not yet passed the trap stage of an execution pipeline in the processor;

wherein when a store passes the trap stage, the store moves from the pipeline CAM to the priority CAM.

16. The computer system of claim 12, wherein the store queue further includes a store-queue finite state machine (FSM) which controls the operation of the store queue, wherein the FSM is configured to use ordering information maintained by the program-order queue to remove the oldest store from the priority CAM and to send the oldest store to the memory subsystem.

17. The computer system of claim 16, wherein if a load matches a store in the store queue, the FSM is configured to perform a read-after-write (RAW) bypass which returns a data value for the load from the matching store.

18. The computer system of claim 17, wherein if a load matches multiple stores in the store queue, the FSM is configured to perform a RAW bypass if all of the data being read by the load was written by the youngest matching store, otherwise the FSM is configured to not perform the RAW bypass.

19. The computer system of claim 12, wherein each entry for a store in the CAM contains:

an address for the store;

a dataword for the store; and

a mask which indicates which bytes of the data word are to be written by the store.

20. The computer system of claim 12, wherein the program-order queue is organized as a first-in-first-out (FIFO) buffer, wherein each entry for a store in the program-order queue contains:

an address for the store; and

an index into the CAM which specifies where an entry for the store is located in the CAM.

21. The computer system of claim 12, wherein the CAM is not a priority CAM and is configured not to hold more than one store for the same address.

22. The computer system of claim 12, wherein the store queue is configured to merge successive stores which are directed to the same address.

23. A method for operating a store queue which holds pending stores and applies the stores to a memory subsystem of a processor in program order, the apparatus comprising:

maintaining entries for stores that are pending in a content-addressable memory (CAM) which facilitates looking up the stores based on addresses for the stores;

wherein the CAM does not keep track of program order between stores to different addresses; and

maintaining additional entries for stores that are pending in a program-order queue which keeps track of program order between the stores in the CAM and thereby facilitates applying the stores to the memory subsystem in program order.

24. The method of claim 23, wherein the CAM is a priority CAM which holds separate copies of multiple stores with identical addresses, and when a lookup based on an address matches multiple stores, returns the youngest matching store.

25. The method of claim 24, wherein storage for the priority CAM is implemented using a random-access memory (RAM).

26. The method of claim 24, wherein the store queue further includes a pipeline CAM which implements the functionality of the priority CAM and also keeps track of program order between stores, but only for a small number of issued stores that have not yet passed the trap stage of an execution pipeline in the processor;

wherein when a store passes the trap stage, the method further comprises moving the store from the pipeline CAM to the priority CAM.

27. The method of claim 23, wherein the store queue further includes a store-queue finite state machine (FSM) which controls the operation of the store queue, wherein the FSM is configured to use ordering information maintained by the program-order queue to remove the oldest store from the priority CAM and to send the oldest store to the memory subsystem.

28. The method of claim 27, wherein if a load matches a store in the store queue, the FSM is configured to perform a read-after-write (RAW) bypass which returns a data value for the load from the matching store.

29. The method of claim 28, wherein if a load matches multiple stores in the store queue, the FSM is configured to perform a RAW bypass if all of the data being read by the load was written by the youngest matching store, otherwise the FSM is configured to not perform the RAW bypass.