Out-of-order processor with a memory subsystem which handles speculatively dispatched load operations

• US 5,751,983 A
• Filed: 10/03/1995
• Issued: 05/12/1998
• Est. Priority Date: 10/03/1995
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Glew, Andrew F., Hinton, Glenn J., Akkary, Haitham H., Papworth, David B., Konigsfeld, Kris G., Madland, Paul D., Abramson, Jeffrey M.
• Primary Examiner(s): Lim, Krisna
• Application Number:
  US08/538,594
• Time in Patent Office: 952 Days
• Field of Search: 395/392, 395/382, 395/393
• US Class Current: 712/216
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency

Abstract

A method and apparatus for speculatively dispatching and/or executing LOADs in a computer system includes a memory subsystem of a out-of-order processor that handles LOAD and STORE operations by dispatching them to respective LOAD and STORE buffers in the memory subsystem. When a LOAD is subsequently dispatched for execution, the store buffer is searched for STOREs having unknown addresses. If any STOREs are found which are older than the dispatched LOAD, and which have an unknown address, the LOAD is tagged with an unknown STORE address identification (USAID). When a STORE is dispatched for execution, the LOAD buffer is searched for loads that have been denoted as mis-speculated loads. Mis-speculated loads are prevented from corrupting the architectural state of the machine with invalid data.

Claims

1. A method of performing memory operations in a computer system comprising the steps of:

(a) dispatching a load operation having a first address;

(b) identifying a most recent store operation that was dispatched prior to the load operation and which has an unknown address;

(c) dispatching a store operation having a second address;

(d) blocking the load operation in the event that the first address matches the second address of the store operation and the store operation was dispatched earlier than, or at the same time as the most recent store operation; and

(e) executing the store operation.

2. The method of claim 1 further comprising the step, following step (a), of:

detecting previously dispatched store operations which have unknown addresses.

3. The method of claim 1 further comprising the step, after step (d) of:

blocking another load operation which is data dependent upon the load operation.

4. The method of claim 1 further comprising the additional steps, after step (a), of:

buffering store operations in a store buffer according to a sequential order;

assigning an identifier to each store operation in the store buffer in correspondence to the sequential order.

5. In a computer system comprising a processor having a data cache, and an external memory coupled to the processor via a bus, a method of executing a program that includes memory operations comprising the steps of:

(a) buffering store operations prior to their execution according to a sequential order of the program;

(b) dispatching a load operation having a first address;

(c) assigning to the load operation a first identifier of a previously buffered store operation which is most recent in the sequential order to the load operation;

(d) tagging the load operation with a second identifier when the previously buffered store operation identified by the first identifier also has an unknown address;

(e) dispatching a store operation having a second address;

(f) blocking the tagged load operation in the event that the first address matches the second address of the store operation and the store operation was dispatched at an earlier or same time than the previously buffered store operator and

(g) executing the store operation.

6. The method of claim 5 further comprising the step of:

blocking other load operations tagged with second identifiers of buffered store operations that are earlier in the sequential program order than the previously buffered store operation of the load operation.

7. The method of claim 6 wherein the load operation comprises a mis-speculated load operation.

8. The method of claim 5 further comprising the step of:

re-dispatching the load operation.

9. The method of claim 5 further comprising the step of:

storing data associated with the store operation in the data cache.

10. The method of claim 5 further comprising, after step (d), the additional steps of:

executing the load operation; and

buffering execution data of the load operation in a storage location.

11. The method of claim 10 further comprising the steps of:

discarding the execution data of the load operation from the storage location; and

re-dispatching the load operation.

12. The method of claim 11 wherein step (b) comprises the step of:

allocating a buffer location in a load buffer for the load operation in accordance with the sequential order of the program.

13. The method of claim 8 further comprising the steps of:

re-executing a first load operation which is earliest in the sequential order of the program;

discarding load and store operations dispatched subsequent to the dispatch of the first load operation.

14. The method of claims 5, 6, 7, 8, 9, 10, 11, or 13 wherein the system further comprises a bus controller unit coupled to the bus, and wherein execution of dispatched load or store operations occurs either in the data cache or in the bus controller unit accessing the external memory.

15. In a computer which speculatively executes instructions, a method of executing a program having a sequential order that directs operations in a memory subsystem of the computer comprising the steps of:

dispatching a load operation and a store operation, the load operation having a first address and an associated set of bits representing a value which identifies a most recent store operation relative to the load operation, the store operation having a second address and an associated identifier (ID) value;

identifying a previously dispatched store operation which is most recent in the sequential order to the load operation, and which has an unknown address, the previously dispatched store operation also having an associated ID value;

detecting whether the value of the associated set of bits of the load operation is the same as, or greater than, the associated ID value of the store operation;

preventing the load operation from executing when the first and second addresses match, and the previously dispatched store operation occurred earlier in the sequential order than the store operation;

executing the store operation; and

forwarding execution data of the store operation to the load operation.

16. In a processor which speculatively executes instructions, a method of executing a program having a sequential order that directs memory operations in a functional unit of the processor comprising the steps of:

issuing load and store operations to the functional unit in a sequential order;

assigning an identifier to each issued load and store operation, the identifier corresponding to the sequential order and having a value that increases with each newly issued operation;

allocating a location in a storage buffer for each load and store operation, the location corresponding to the sequential order;

dispatching a load operation having a first address and a first identifier from the storage buffer to a first execution unit of the processor;

detecting buffered store operations having unknown addresses;

tagging the load operation to indicate a previously buffered store operation with an unknown address and which has an associated identifier having a next lower value than that of the first identifier;

executing the load operation;

dispatching a store operation having a second address and a second identifier from the storage buffer to a second execution unit of the processor;

comparing the first and second addresses to determine if they match;

preventing data from the load operation from being committed to a permanent processor state when the first and second addresses match and the second identifier has a value which is the same as or lower than the associated identifier of the previously buffered store operation; and

executing the store operation.

17. The method of claim 16 wherein the step of detecting buffered store operations having unknown addresses comprises the step of searching the storage buffer between a first store operation in the sequential order and a location corresponding to the first identifier of the load operation.

18. The method of claim 17 further comprising, after the step of executing the load operation, the step of buffering the data of the load operation in a data storage location.

19. The method of claim 20 wherein the preventing step comprises the steps of:

executing the store operation;

discarding the data of the load operation from the data storage location; and

re-dispatching the load operation for re-execution.

20. The method of claim 17 wherein after the step of dispatching a load operation, the method further comprises the steps of:

detecting buffered store operations having valid data and valid addresses which correspond to the first address of the load operation; and

forwarding valid data of one of the buffered store operations to the load operation when the one buffered store operations has an associated identifier which is the same or greater than the first identifier.

21. In a processor which speculatively executes instructions, a method of executing a program having a sequential order that directs memory operations in a functional unit of the processor comprising the steps of:

issuing load and store operations to the functional unit in a sequential order;

assigning to each issued store operation, and at least a first load operation, an identifier corresponding to the sequential order, the identifier having a value which is incremented with each newly issued operation;

allocating a location in a storage buffer for each store operation, the location corresponding to the sequential order;

dispatching the first load operation having a first address and a first identifier to a first execution unit of the processor;

detecting buffered store operations having unknown addresses;

tagging the first load operation to indicate a previously buffered store operation with an unknown address and which has an associated identifier having a next lower value than that of the first identifier;

executing the first load operation;

dispatching a store operation having a second address and a second identifier from the storage buffer to a second execution unit of the processor;

comparing the first and second addresses to determine if they match;

data from the first load operation from being committed to an architectural state when the first and second addresses match and the second identifier has a value which is the same as or lower than the associated identifier of the previously buffered store operation; and

executing the store operation.

22. A processor comprising:

means for issuing load and store operations;

means coupled to the issuing means for executing the load and store operations;

a memory unit which includes;

means for detecting pending store operations having unknown addresses;

means for tagging a load operation issued by the issuing means with an unknown store address identifier (USAID) identifying a youngest pending store operation which has an unknown address and is older than the load operation in response to the detecting means detecting a pending store operation having an unknown address;

means for generating a signal upon detection of a mis-speculated load operation which has an associated USAID and is younger than the pending store operation; and

means for preventing a mis-speculated load operation being committed to an architectural state of the processor in response to the signal.

23. A processor for executing a program which includes instructions arranged in a sequential order, the processor comprising:

a first unit that fetches and issues the instructions in accordance with the sequential order, the instructions specifying various operations which include load and store operations;

a second unit, coupled to the first unit, that executes the various operations in a different order as compared to the sequential order;

a third unit, coupled to the first and second unit, that commits results produced by the various operations to an architectural state of the processor;

a memory subsystem having load and store buffers, which respectively buffer the load and store operations prior to execution, and associated logic;

upon dispatch of a load operation to the second unit, the associated logic being operative to tag the load operation with an identifier value corresponding to a youngest one of the store operations pending in the store buffer which is both older than the load operation and which has an unknown address, as determined by a search of the store buffer; and

upon dispatch of a store operation to the second unit, the associated logic being operative to search the load buffer for a mis-speculated load operation, and, in response thereto, prevent the third unit from committing data associated with the mis-speculated load operation to the architectural state of the processor.

24. The processor of claim 23 wherein the mis-speculated load operation has an associated identifier value that is younger than the store operation being dispatched to the second unit, and the mis-speculated load operation is currently being executed, or has been executed.

25. The processor of claim 23 wherein each of the store operations pending in the store buffer have a store buffer identification (SBID) which establishes an ordering of the store operations in the store buffer.

26. The processor of claim 25 wherein the identifier value comprises to the SBID of the youngest one of the store operations pending in the store buffer which is both older than the load operation and which has an unknown address.