Lock mechanism to enable atomic updates to shared memory

• US 8,375,176 B2
• Filed: 10/18/2011
• Issued: 02/12/2013
• Est. Priority Date: 03/24/2008
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Coon, Brett W., Nickolls, John R., Nyland, Lars, Mills, Peter C.
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): Ruiz, Aracelis
• Application Number:
  US13/276,224
• Publication Number:
  US 20120036329A1
• Time in Patent Office: 483 Days
• Field of Search: 711/147, 711/152
• US Class Current: 711/152
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 2209/521 Atomic
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• CPC Class Codes: G06F 9/30185 according to one or more bits in the instruction, e.g. prefix, sub-opcode
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A system and method for locking and unlocking access to a shared memory for atomic operations provides immediate feedback indicating whether or not the lock was successful. Read data is returned to the requestor with the lock status. The lock status may be changed concurrently when locking during a read or unlocking during a write. Therefore, it is not necessary to check the lock status as a separate transaction prior to or during a read-modify-write operation. Additionally, a lock or unlock may be explicitly specified for each atomic memory operation. Therefore, lock operations are not performed for operations that do not modify the contents of a memory location.

Claims

1. A method for reading a location in a shared memory, the method comprising:

receiving a shared memory read instruction for the location in the shared memory for multiple parallel threads of a program;

determining that the shared memory read instruction includes a lock command suffix indicating that a lock of the location is requested; and

returning a lock result indicating whether or not the lock of the location was acquired for the shared memory read instruction, wherein execution across the multiple parallel threads diverges when the lock result indicates that at least one of the multiple parallel threads did not acquire the lock.

2. The method of claim 1, further comprising, after returning the lock result, locking the location by setting a lock flag when the lock is acquired for the shared memory read instruction.

3. The method of claim 2, wherein the lock result is the inverse of the lock flag prior to the locking of the location.

4. The method of claim 2, further comprising, concurrent with the locking of the location, reading the location in the shared memory.

5. The method of claim 1, further comprising computing a lock address of an entry storing the lock flag for the location in the shared memory.

6. The method of claim 5, wherein the lock address is the low eight bits of an address of the location in the shared memory.

7. The method of claim 5, wherein the lock address is a hash of an address of the location in the shared memory.

8. The method of claim 1, wherein the lock flag is shared amongst multiple locations in the shared memory.

9. The method of claim 1, further comprising storing the lock result in a condition register.

10. A method for writing a location in a shared memory with a value, the method comprising:

receiving a shared memory write instruction for the location in the shared memory for multiple parallel threads of a program;

determining that the shared memory write instruction includes an unlock command suffix indicating that a lock of the location should be released;

determining, based on a lock result, threads of the multiple parallel threads that acquired a lock, wherein execution across the multiple parallel threads diverges when the lock result indicates that at least one of the multiple parallel threads did not acquire the lock; and

storing the value in the location in the shared memory for the threads of the multiple parallel threads that acquired the lock.

11. The method of claim 10, further comprising, concurrent with the storing of the value, clearing a lock flag corresponding to the location in the shared memory to release the lock of the location.

12. The method of claim 11, further comprising computing a lock address of an entry storing the lock flag for the location in the shared memory.

13. The method of claim 12, wherein the lock address is the low eight bits of an address of the location in the shared memory.

14. The method of claim 12, wherein the lock address is a hash of an address of the location in the shared memory.

15. The method of claim 11, further comprising, prior to storing the value, reading the lock flag from a condition register.

16. The method of claim 15, further comprising determining that the lock flag indicates that the location is locked.

17. The method of claim 11, wherein the lock flag is shared amongst multiple locations in the shared memory.