Lock address contention predictor

Patent metadata

Field	Value
Publication number	US-11868818-B2
Application number	US-201615273304-A
Country	US
Kind code	B2
Filing date	Sep 22, 2016
Priority date	Sep 22, 2016
Publication date	Jan 9, 2024
Grant date	Jan 9, 2024

Abstract

Techniques for selectively executing a lock instruction speculatively or non-speculatively based on lock address prediction and/or temporal lock prediction. including methods an devices for locking an entry in a memory device. In some techniques, a lock instruction executed by a thread for a particular memory entry of a memory device is detected. Whether contention occurred for the particular memory entry during an earlier speculative lock is detected on a condition that the lock instruction comprises a speculative lock instruction. The lock is executed non-speculatively if contention occurred for the particular memory entry during an earlier speculative lock. The lock is executed speculatively if contention did not occur for the particular memory entry during an earlier speculative lock.

First claim

What is claimed is:

1. A method for locking an entry in a memory device, comprising:
executing a lock instruction of a thread to lock a particular memory entry of the memory device,
wherein the lock instruction is executed either speculatively or non-speculatively based on whether the particular memory entry was modified by a second thread during a window of exposure of an earlier speculative lock;
wherein executing the lock instruction non-speculatively includes disallowing modification by the second thread to the particular memory entry;
wherein executing the lock instruction speculatively includes permitting modification by the second thread to the particular memory entry; and
wherein the window of exposure is a time interval from a time when the particular memory entry was read during the earlier speculative lock to a time when the earlier speculative lock completed.

2. The method of claim 1 , further comprising:
responsive to the lock instruction being executed as a speculative lock, detecting whether another thread writes to the particular memory entry during the speculative lock.

3. The method of claim 2 , further comprising:
responsive to another thread writing to the particular memory entry during the speculative lock, flushing an execution pipeline in which the thread is executing, and re-executing the thread starting from the lock instruction, wherein the lock instruction is re-executed non-speculatively.

4. The method of claim 2 , wherein detecting whether another thread writes to the particular memory entry during the speculative lock comprises detecting whether the particular memory entry contains invalid data.

5. The method of claim 1 , wherein detecting whether another thread writes to the particular memory entry comprises detecting any one of: access to, modification of, a request to access, or a request to modify a memory entry by another thread during a lock of the memory entry.

6. The method of claim 1 , wherein detecting whether another thread writes to the particular memory entry during an earlier speculative lock comprises detecting whether another thread requested access, accessed, requested to modify, or modified the particular memory entry during the earlier speculative lock.

7. The method of claim 1 , wherein executing the lock instruction speculatively comprises relaxing a constraint of the lock.

8. The method of claim 1 , wherein executing the lock instruction speculatively comprises relaxing an atomic access property or a fencing property of the lock.

9. A method for locking an entry in a memory device, comprising:
executing a lock instruction of a thread to lock a particular memory entry of a memory device,
wherein the lock instruction is executed either speculatively or non-speculatively based on whether, during a particular time period, a number of times the particular memory entry was modified to by a second thread during a window of exposure of an earlier speculative lock exceeds a threshold number;
wherein executing the lock instruction non-speculatively includes disallowing modification by the second thread to the particular memory entry;
wherein executing the lock instruction speculatively includes permitting modification by the second thread to the particular memory entry; and
wherein the window of exposure is a time interval from a time when the particular memory entry was read during one of the earlier speculative locks to a time when the one of the earlier speculative lock completed.

10. The method of claim 9 , wherein the lock instruction is executed either speculatively or non-speculatively based on whether, during the particular time period, a number of times any memory entry in the memory device was written to by another thread during a window of exposure of an earlier speculative lock exceeds a threshold number.

11. The method of claim 9 , further comprising, responsive to the lock instruction being executed speculatively, detecting whether another thread writes to the particular memory entry during the speculative lock.

12. The method of claim 11 , further comprising, responsive to another thread writing to the particular memory entry during the speculative lock, flushing an execution pipeline in which the thread is executing, and re-executing the thread starting from the lock instruction.

13. The method of claim 11 , wherein detecting whether another thread writes to the particular memory during the speculative lock comprises detecting whether the particular memory entry contains invalid data.

14. The method of claim 9 , wherein detecting whether another thread wrote to the particular memory entry comprises detecting any one of: access to, modification of, a request to access, or a request to modify a memory entry by a thread during a lock of the memory entry.

15. The method of claim 9 , wherein detecting whether, during a particular time period, a number of earlier speculative locks during which another thread wrote to the particular memory entry exceeds a threshold number comprises detecting whether another thread requested access, accessed, requested to modify, or modified the particular memory entry during the earlier speculative lock.

16. The method of claim 9 , wherein executing the lock speculatively comprises relaxing a constraint of the lock.

17. The method of claim 9 , wherein executing the lock speculatively comprises relaxing an atomic access property or a fencing property of the lock.

18. A processing device configured for speculative locking, the device comprising:
a processor core including an execution pipeline;
wherein the processing device is configured to:
execute a lock instruction of a thread to lock a particular memory entry of a memory device,

wherein the lock instruction is executed either speculatively or non-speculatively based on whether the particular memory entry was modified by a second thread during a window of exposure of an earlier speculative lock;
wherein executing the lock instruction speculatively includes permitting modification by the second thread to the particular memory entry; and
wherein the window of exposure is a time interval from a time when the particular memory entry was read during the earlier speculative lock to a time when the earlier speculative lock completed.

19. The processing device of claim 18 , further configured to detect whether another thread writes to the particular memory during the speculative lock responsive to the lock instruction being executed as a speculative lock.

20. The processing device of claim 19 , further configured to flush an execution pipeline in which the thread is executing, and re-execute the thread starting from the lock instruction responsive to another thread writing to the particular memory entry during the speculative lock.

21. The processing device of claim 19 , wherein detecting whether another thread writes to the particular memory entry during the speculative lock comprises detecting whether the particular memory entry contains invalid data.

22. The processing device of claim 18 , wherein detecting whether another thread writes to the particular memory entry comprises detecting any one of: access to, modification of, a request to access, or a request to modify a memory entry by another thread during a lock of the memory entry.

23. The processing device of claim 18 , wherein detecting whether another thread writes to the particular memory entry during an earlier speculative lock comprises detecting whethe

Assignees

• Advanced Micro Devices Inc

Inventors

• Smaus Gregory W
• King John M
• Rafacz Matthew A
• Crum Matthew M

Classifications

• G06F9/52 Primary

  Program synchronisation; Mutual exclusion, e.g. by means of semaphores · CPC title

• G06F9/50

  Allocation of resources, e.g. of the central processing unit [CPU] · CPC title

• G06F9/30087 Primary

  Synchronisation or serialisation instructions · CPC title

• G06F3/0604 Primary

  Improving or facilitating administration, e.g. storage management · CPC title

• G06F9/528

  by using speculative mechanisms · CPC title