Critical section detection and prediction mechanism for hardware lock elision

Patent metadata

Field	Value
Publication number	US-9262173-B2
Application number	US-201213350572-A
Country	US
Kind code	B2
Filing date	Jan 13, 2012
Priority date	Nov 13, 2006
Publication date	Feb 16, 2016
Grant date	Feb 16, 2016

Abstract

A method and apparatus for detecting lock instructions and lock release instruction, as well as predicting critical sections is herein described. A lock instruction is detected with detection logic, which potentially resides in decode logic. A lock instruction entry associated with the lock instruction is stored/created. Address locations and values to be written to those address location of subsequent potential lock release instruction are compared to the address loaded from by the lock instruction and the value load by the lock instruction. If the addresses and values match, it is determined that the lock release instruction matches the lock instruction. A prediction entry stores a reference to the lock instruction, such as a last instruction pointer (LIP), and an associated value to represent the lock instruction is to be elided upon subsequent detection, if it is determined that the lock release instruction matches the lock instruction.

First claim

What is claimed is:

1. A method comprising:
detecting a read modify write (RMW) lock instruction, which references a first address location;
pushing a lock instruction entry (LIE) associated with the lock instruction onto a lock stack in response to detecting the lock instruction, wherein the LIE includes a lock address referenced by the RMW lock instruction and a lock value to be written to the lock address by the RMW lock instruction;
attempting to find a subsequent lock release instruction that corresponds to the RMW lock instruction;
attempting a late-lock acquire in response to not finding the subsequent lock release instruction that corresponds to the RMW lock instruction before a time out; and
storing a prediction entry in a critical section predictor to represent the lock instruction is to be elided in response to finding the subsequent lock release instruction that corresponds to the RMW lock instruction before the time out.

2. The method of claim 1 , further comprising:
popping the LIE associated with the lock instruction off the stack in response to finding the subsequent lock release instruction that corresponds to the lock instruction and the LIE associated with the lock instruction is on top of the stack; and
setting a found corresponding lock release instruction flag in the LIE and popping the LIE off the stack after at least one other LIE is popped from the stack in response to finding the subsequent lock release instruction that corresponds to the lock instruction and the LIE associated with the lock instruction is not on top of the stack.

3. The method of claim 2 , further comprising:
initiating a watchdog timer to count for a predetermined amount of time, in response to pushing the entry onto the stack; and
determining the subsequent lock instruction is not found in response to the watchdog timer expiring before finding a subsequent lock release instruction that corresponds to the lock instruction; and
storing an entry in the critical section predictor to represent the lock instruction is not to be elided in response to subsequently detecting the lock instruction in response to determining the subsequent lock instruction is not found.

4. The method of claim 3 , further comprising:
tracking a plurality of tentative accesses to a memory subsequent in program order to the lock instruction, in response to detecting the lock instruction;
committing the tentative accesses to the memory in response to finding the subsequent lock release instruction that corresponds to the lock instruction before the time out.

5. The method of claim 4 , further comprising:
checking the critical section predictor in response to subsequently detecting the lock instruction; and
eliding the lock instruction in response to the entry in the critical section predictor representing the lock instruction is to be elided.

6. The method of claim 5 , wherein eliding the lock instruction comprises:
creating a register checkpoint in response to subsequently detecting the lock instruction;
eliding a first store operation to an address location associated with the subsequently detected lock instruction;
tracking a plurality of tentative memory accesses subsequent in program order to the subsequently detected lock instruction.

7. An apparatus comprising:
means for: detecting a read modify write (RMW) lock instruction, which references a first address location; pushing a lock instruction entry (LIE) associated with the lock instruction onto a lock stack in response to detecting the lock instruction, wherein the LIE includes a lock address referenced by the RMW lock instruction and a lock value to be written to the lock address by the RMW lock instruction; attempting to find a subsequent lock release instruction that corresponds to the RMW lock instruction; attempting a late-lock acquire in response to not finding the subsequent lock release instruction that corresponds to the RMW lock instruction before a time out; and storing a prediction entry in a critical section predictor to represent the lock instruction is to be elided in response to finding the subsequent lock release instruction that corresponds to the RMW lock instruction before the time out.

8. The apparatus of claim 7 , further comprising:
means for: popping the LIE associated with the lock instruction off the stack in response to finding the subsequent lock release instruction that corresponds to the lock instruction and the LIE associated with the lock instruction is on top of the stack; and setting a found corresponding lock release instruction flag in the LIE and popping the LIE off the stack after at least one other LIE is popped from the stack in response to finding the subsequent lock release instruction that corresponds to the lock instruction and the LIE associated with the lock instruction is not on top of the stack.

9. The apparatus of claim 8 , further comprising:
means for initiating a watchdog timer to count for a predetermined amount of time, in response to pushing the entry onto the stack; and determining the subsequent lock instruction is not found in response to the watchdog timer expiring before finding a subsequent lock release instruction that corresponds to the lock instruction; and storing an entry in the critical section predictor to represent the lock instruction is not to be elided in response to subsequently detecting the lock instruction in response to determining the subsequent lock instruction is not found.

10. The apparatus of claim 9 , further comprising:
means for tracking a plurality of tentative accesses to a memory subsequent in program order to the lock instruction, in response to detecting the lock instruction;
committing the tentative accesses to the memory in response to finding the subsequent lock release instruction that corresponds to the lock instruction before the time out.

11. The apparatus of claim 10 , further comprising:
means for checking the critical section predictor in response to subsequently detecting the lock instruction; and eliding the lock instruction in response to the entry in the critical section predictor representing the lock instruction is to be elided.

12. The apparatus of claim 11 , wherein eliding the lock instruction comprises:
means for creating a register checkpoint in response to subsequently detecting the lock instruction; eliding a first store operation to an address location associated with the subsequently detected lock instruction; tracking a plurality of tentative memory accesses subsequent in program order to the subsequently detected lock instruction.

Assignees

• Akkary Haitham
• Rajwar Ravi
• Srinivasan Srikanth T
• Intel Corp

Inventors

• Akkary Haitham
• Rajwar Ravi
• Srinivasan Srikanth T

Classifications

• G06F9/3004

  to perform operations on memory · CPC title

• G06F9/3842

  Speculative instruction execution · CPC title

• G06F9/3865 Primary

  using deferred exception handling, e.g. exception flags · CPC title

• G06F9/30087

  Synchronisation or serialisation instructions · CPC title

• G06F9/3834

  Maintaining memory consistency · CPC title