IMPLEMENTING ATOMIC PRIMITIVES USING CACHE LINE LOCKING

• US 20180173625A1
• Filed: 12/14/2017
• Published: 06/21/2018
• Est. Priority Date: 12/15/2016
• Status: Active Grant

• Current Assignee: Optimum Semiconductor Technologies, Inc.
• Original Assignee: Optimum Semiconductor Technologies, Inc.
• Inventors: Moudgill, Mayan, Hoane, A. Joseph
• Granted Patent: US 11,157,407 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0817 using directory methods
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 12/0895 of parts of caches, e.g. directory or tag array
• CPC Class Codes: G06F 2212/62 Details of cache specific to multiprocessor cache arrangements
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30047 Prefetch instructions; cache control instructions
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• CPC Class Codes: G06F 9/3861 Recovery, e.g. branch miss-prediction, exception handling error detection or correction G06F11/00
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: G06F 9/54 Interprogram communication

Abstract

A processor comprising a cache, the cache comprising a cache line, an execution unit to execute an atomic primitive to responsive to executing a read instruction to retrieve a data item from a memory location, cause to store a copy of the data item in the cache line, execute a lock instruction to lock the cache line to the processor, execute at least one instruction while the cache line is locked to the processor, and execute an unlock instruction to cause the cache controller to release the cache line from the processor.

Claims

1. A processor comprising:

a cache, the cache comprising a cache line;

an execution unit to execute an atomic primitive to;

responsive to executing a read instruction to retrieve a data item from a memory location, cause to store a copy of the data item in the cache line;

execute a lock instruction to lock the cache line to the processor;

execute at least one instruction while the cache line is locked to the processor; and

execute an unlock instruction to cause the cache controller to release the cache line from the processor.

2. The processor of claim 1, wherein the cache is one of an L1 data cache or an L2 data cache.

3. The processor of claim 1, wherein a cache controller associated with the processor is to:

determine that the cache line is in an exclusive state under a cache coherence protocol; and

responsive to determining that the cache line is in the exclusive state, mark the cache line as locked to the processor.

4. The processor of claim 1, wherein to mark the cache line as locked to the processor, a cache controller is to set a lock status flag in the cache line.

5. The processor of claim 4, wherein responsive to completing execution of the plurality of instructions, the cache controller is to unset the lock status flag the cache line.

6. The processor of claim 1, wherein responsive to identifying a request to access the cache line by a second processor, a cache controller is to delay granting access by the second processor to the cache line until the execution unit completes execution of the plurality of instructions.

7. The processor of claim 1, wherein a cache controller is to access a directory stored in a memory, the directory comprising an entry to store a lock status flag, and wherein to mark the cache line as locked to the processor, the cache controller is to set the lock status flag in the entry.

8. The processor of claim 1, wherein a cache controller is to access a pool to store a plurality of a memory addresses that correspond to locked cache lines, and wherein to mark the cache line as locked to the processor, the cache controller is to place a memory address associated with the cache line in the pool.

9. The processor of claim 8, wherein the cache controller is to remove the memory address from the pool to unlock the cache line.

10. The processor of claim 1, wherein the lock instruction is a privileged instruction of the operating system, and wherein the unlock instruction is a privileged instruction of the operating system.

11. The processor of claim 10, wherein the processor is to support an operating system to call the atomic primitive.

12. The processor of claim 1, wherein processors other than the processor are denied access to the cache line while the cache line is locked to the processor.

13. The processor of claim 1, wherein a second processor is to access the cache line while the cache line is unlocked.

14. The processor of claim 1, wherein the execution unit is to:

determine whether execution of the lock instruction is successful;

responsive to determining that the execution of the lock instruction fails, the execution unit is to at least one of;

return a status flag indicating that the execution fails;

branch to a pre-determined memory address;

trigger an exception to notify an exception handler;

or

repeatedly execute the lock instruction until successfully acquiring the lock; and

responsive to determining that the execution of the lock instruction is successful,

guarantee that the memory location is locked to the processor until completion of executing the unlock instruction.

15. A method of executing an atomic primitive, the method comprising:

responsive to executing a read instruction to retrieve a data item from a memory location, causing to store a copy of the data item in a cache line of a cache;

executing a lock instruction to lock the cache line to the processor;

executing at least one instruction while the cache line is locked to the processor; and

executing an unlock instruction to cause the cache controller to release the cache line from the processor.

16. The method of claim 15, wherein the cache is one of an L1 data cache or an L2 data cache.

17. The method of claim 15, further comprising:

determining that the cache line is in an exclusive state under a cache coherence protocol; and

responsive to determining that the cache line is in the exclusive state, marking the cache line as locked to the processor.

18. The method of claim 15, wherein marking the cache line as locked to the processor further comprises setting a lock status flag in the cache line.

19. The method of claim 18, wherein responsive to completing execution of the plurality of instructions, unsetting the lock status flag the cache line.

20. The method of claim 15, further comprising:

responsive to identifying a request to access the cache line by a second processor, delaying granting access by the second processor to the cache line until the execution unit completes execution of the plurality of instructions.