COMPLETING LOAD AND STORE INSTRUCTIONS IN A WEAKLY-ORDERED MEMORY MODEL

• US 20140215190A1
• Filed: 01/25/2013
• Published: 07/31/2014
• Est. Priority Date: 01/25/2013
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Mylius, John H., Goel, Rajat, Kanapathipillai, Pradeep, Kannan, Hari S.
• Granted Patent: US 9,535,695 B2
• Time in Patent Office: Days
• US Class Current: 712/220
• CPC Class Codes: G06F 9/30043 LOAD or STORE instructions; Clear instruction
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding
• CPC Class Codes: G06F 9/3856 Reordering of instructions, e.g. using queues or age tags

Abstract

Techniques are disclosed relating to completion of load and store instructions in a weakly-ordered memory model. In one embodiment, a processor includes a load queue and a store queue and is configured to associate queue information with a load instruction in an instruction stream. In this embodiment, the queue information indicates a location of the load instruction in the load queue and one or more locations in the store queue that are associated with one or more store instructions that are older than the load instruction. The processor may determine, using the queue information, that the load instruction does not conflict with a store instruction in the store queue that is older than the load instruction. The processor may remove the load instruction from the load queue while the store instruction remains in the store queue. The queue information may include a wrap value for the load queue.

Claims

1. A processor, comprising:

a load queue; and

a store queue;

wherein the processor is configured to;

associate queue information with a load instruction in an instruction stream being executed by the processor, wherein the queue information indicates a location of the load instruction in the load queue, and wherein the queue information indicates one or more locations in the store queue that are associated with one or more store instructions that are older than the load instruction;

determine, using the queue information, that the load instruction does not conflict with a store instruction in the store queue that is older than the load instruction; and

remove the load instruction from the load queue while the store instruction remains in the store queue.

2. The processor of claim 1, wherein the queue information further indicates a current wrap value for the load queue.

3. The processor of claim 1,

wherein the load queue includes a first number of entries;

wherein the load instruction is a second number of load instructions younger than the store instruction that remains in the store queue; and

wherein the second number is greater than the first number.

4. The processor of claim 1,

wherein the load instruction targets a particular address;

and

wherein, to determine that the load instruction does not conflict with the store instruction, the processing element is configured to determine whether the store instruction targets the particular address.

5. The processor of claim 1, wherein the store instruction is retired from a reorder buffer for at least a portion of the time the store instruction resides in the store queue.

6. The processor of claim 1, further comprising:

a dispatch unit configured to associate the queue information with the load instruction; and

receive program instruction in program order.

7. The processor of claim 1, wherein the queue information includes:

a load number indicative of a location of the load instruction in the load queue; and

a store number indicative of a location associated with a next-youngest or next-oldest store instruction in an instruction stream, relative to the load instruction, in the store queue.

8. The processor of claim 1, further comprising:

a load/store unit configured to determine, using the queue information, that the load instruction does not conflict with the store instruction in the store queue and to remove the load instruction from the load queue while the store instruction remains in the store queue

9. A method, comprising:

associating queue information with a load instruction in an instruction stream being executed by a computer processor, wherein the queue information indicates a location of the load instruction in a load queue, and wherein the queue information indicates one or more store instructions in a store queue that are older than the load instruction;

determining, using the queue information for the load instruction, that the load instruction does not conflict with a set of store instructions in the store queue that are older than the load instruction; and

removing the load instruction from the load queue while at least one of the set of store instructions remains in the store queue.

10. The method of claim 9, wherein the queue information further indicates a current wrap value for the load queue.

11. The method of claim 10, wherein the wrap value is represented using a plurality of bits.

12. The method of claim 9, wherein the associating is performed by a dispatch unit.

13. The method of claim 9, wherein the determining and the removing are performed by a load/store unit.

14. The method of claim 9,

wherein the load queue includes a first number of entries;

wherein there are a second number of load instructions in the instruction stream between the load and at least one of the set of store instructions remaining in the store queue; and

wherein the second number is greater than the first number.

15. A processor, comprising:

a load queue; and

a store queue;

wherein the processor is configured to;

associate queue information with a store instruction in an instruction stream being executed by the processor, wherein the queue information indicates a location of the store instruction in the store queue, and wherein the queue information indicates one or more load instructions in the load queue that are younger than the store instruction;

determine, using the queue information, that the store instruction does not conflict with a particular load instruction in the load queue that is younger than the store instruction;

retire the particular load instruction from the load queue while the store instruction is still in the store queue.

16. The processor of claim 15, wherein the queue information further indicates a current wrap value for the store queue and a current wrap value for the load queue.

17. The processor of claim 16, wherein the current wrap value for the load queue is represented using a plurality of bits.

18. The processor of claim 15, wherein the processor is further configured to:

determine, using the queue information, that the store instruction conflicts with one or more load instructions in the load queue that are younger than the store instruction; and

replay the one or more load instructions in response to the determination.

19. The processor of claim 15,

wherein the load queue includes a first number of entries;

wherein the processor is configured to execute a second number of load instructions in the instruction stream between the store instruction and the particular load instruction; and

wherein the second number is greater than the first number.

20. The processor of claim 15, further comprising:

a load counter; and

a store counter;

wherein the queue information includes a load number assigned using the load counter and a store number assigned using the store counter.