Lock mechanism to enable atomic updates to shared memory

• US 8,055,856 B2
• Filed: 03/24/2008
• Issued: 11/08/2011
• Est. Priority Date: 03/24/2008
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Nickolls, John R., Nyland, Lars, Coon, Brett W., Mills, Peter C.
• Primary Examiner(s): Bragdon; Reginald
• Assistant Examiner(s): Ruiz; Aracelis
• Application Number:
  US12/054,267
• Publication Number:
  US 20090240860A1
• Time in Patent Office: 1,324 Days
• Field of Search: None
• 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 performing atomic updates to a shared memory, the method comprising:

receiving a memory request for accessing an entry of the shared memory corresponding to an address;

determining a lock address of a lock entry that stores a lock flag using the address;

computing a lock result for the lock address that indicates whether or not a lock is acquired for the entry of the shared memory corresponding to the address;

setting the lock flag to indicate that the entry is locked by the memory request to prevent another memory request from writing the entry of the shared memory corresponding to the address; and

reading data stored in the entry of the shared memory corresponding to the address,

wherein the steps of determining, computing, setting, and reading are performed in parallel for multiple execution threads of a program, and the execution of the threads diverges when lock results for the multiple threads indicate that at least one of the multiple threads did not acquire a lock.

2. The method of claim 1, further comprising:

performing operations using the data to produce modified data; and

clearing the lock flag, when the lock result indicates that the lock was acquired for the entry, to indicate that the entry is unlocked by the memory request.

3. The method of claim 2, further comprising writing the modified data to the entry of the shared memory corresponding to the address.

4. The method of claim 1, further comprising repeating the steps of computing the lock result, setting the lock flag, and reading the data when the lock result indicates that the lock was not acquired for the entry.

5. The method of claim 1, wherein the lock address is a portion of the address of the entry in the shared memory.

6. The method of claim 1, wherein an instruction specifying the memory request explicitly indicates that the entry in the shared memory will be locked during execution of the instruction.

7. The method of claim 1, wherein an instruction specifying the memory request explicitly indicates that the entry in the shared memory will be unlocked during execution of the instruction.

8. The method of claim 1, further comprising synchronizing execution of the multiple threads to resume parallel execution after each one of the multiple threads acquire a lock.

9. The method of claim 1, wherein the lock flag is shared by two or more addresses of entries in the shared memory.

10. A non-transitory computer readable storage medium storing instructions for causing a processor to access a shared memory by performing the steps of:

receiving a memory request for accessing an entry of the shared memory corresponding to an address;

determining a lock address of a lock entry that stores a lock flag using the address;

computing a lock result for the lock address that indicates whether or not a lock is acquired for the entry of the shared memory corresponding to the address;

setting the lock flag to indicate that the entry is locked by the memory request to prevent another memory request from writing the entry of the shared memory corresponding to the address; and

reading data stored in the entry of the shared memory corresponding to the address,

wherein the steps of determining, computing, setting, and reading are performed in parallel for multiple execution threads of a program, and the execution of the threads diverges when lock results for the multiple threads indicate that at least one of the multiple threads did not acquire a lock.

11. The non-transitory computer readable storage medium of claim 10, further comprising:

performing operations using the data to produce modified data; and

clearing the lock flag, when the lock result indicates that the lock was acquired for the entry, to indicate that the entry is unlocked by the memory request.

12. The non-transitory computer readable storage medium of claim 10, further comprising repeating the steps of computing the lock result, setting the lock flag, and reading the data when the lock result indicates that the lock was not acquired for the entry.

13. The non-transitory computer readable storage medium of claim 10, wherein the lock flag is shared by two or more addresses of entries in the shared memory.

14. A system for performing atomic updates to a shared memory, the system comprising:

a shared storage resource to store data in multiple entries and configured to;

receive a memory request for accessing an entry of the shared storage resource corresponding to an address; and

output data stored in the entry corresponding to the address; and

a memory lock unit coupled to the shared storage resource and configured to;

receive a lock request that is specified with the memory request;

determine a lock address of a lock entry that stores a lock flag using the address; and

set the lock flag to indicate that the entry is locked by the memory request to prevent another memory request from writing the entry of the shared storage resource corresponding to the address,

wherein determining the lock address and setting the lock flag are performed in parallel for multiple execution threads of a program, and the execution of the threads diverges when lock results for the multiple threads indicate that at least one of the multiple threads did not set the lock flag.

15. The system of claim 14, wherein the memory lock unit is further configured to compute a lock result for the lock address that indicates whether or not a lock is acquired for the entry of the shared storage resource corresponding to the address.

16. The system of claim 14, wherein the memory lock unit is further configured to:

receive an unlock request that is specified with a second memory request for accessing the entry of the shared storage resource corresponding to the address; and

clear the lock flag, when the lock result indicates that the lock was acquired for the entry, to indicate that the entry is unlocked by the second memory request.

17. The system of claim 16, wherein the shared storage resource is further configured to:

receive the second memory request for accessing the entry of the shared storage resource corresponding to the address; and

write modified data to the entry of the shared storage resource corresponding to the address.

18. The system of claim 14, wherein the lock flag is shared by two or more addresses of entries in the shared storage resource.