Lock caching for compound atomic operations on shared memory

• US 7,228,391 B2
• Filed: 06/08/2004
• Issued: 06/05/2007
• Est. Priority Date: 07/15/2003
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Silvera, Raul Esteban, Blainey, Robert James
• Primary Examiner(s): NGUYEN, THAN VINH
• Application Number:
  US10/864,777
• Publication Number:
  US 20050010729A1
• Time in Patent Office: 1,092 Days
• Field of Search: None
• US Class Current: 711/152
• CPC Class Codes: G06F 2209/522 Manager
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A system and method for lock caching for compound atomic operations (i.e. a read or write operation to more than one 4-byte word) on shared memory is provided. In a computer system including a memory shared among a plurality of processing entities, for example, multiple threads, a method of performing compound atomic operations comprises providing a pool of locks for synchronizing access to the memory; assigning the locks among the plurality of entities to minimize lock contention; and performing the compound atomic operations using the assigned locks. Each lock may be assigned in accordance with an address of the shared memory from the processing entity'"'"'s compound atomic operations. Assigning locks may be performed in a manner to minimize concurrent atomic updates to the same or overlapping portions of the shared memory. For example, the addresses of the memory from the compound atomic operations may be aliased in accordance with a known upper bound on the amount of the shared memory that may be affected by any atomic operation.

Claims

1. In a computer system including a memory shared among a plurality of processing entities, a method of performing compound atomic operations by said processing entities comprising:

providing a pool of locks for synchronizing access to the memory;

sharing the locks among the plurality of processing entities to minimize lock contention, wherein a lock is selected from the pool to minimize concurrent atomic updates to same or overlapping portions of the shared memory by aliasing memory addresses in accordance with a known upper bound on an amount of the shared memory that is capable of being effected by an atomic operation; and

performing the compound atomic operations using assigned locks.

2. The method of claim 1 wherein each lock is assigned in accordance with an address of the shared memory from an entity'"'"'s compound atomic operations.

3. The method of claim 1 comprising configuring the pool of locks in accordance with a count of the plurality of processing entities expected to contend for the locks.

4. The method of claim 1 wherein performing comprises, for each respective processing entity, synchronizing the entity in accordance with availability of a lock assigned to the entity.

5. The method of claim 4 comprising releasing the lock assigned to the entity.

6. The method of claim 1 including providing a software tool to generate instructions for said computer system to define said pool and a mechanism to use said pool.

7. The method of claim 6 wherein said software tool further generates instructions to define said processing entities, said entities including instructions to use said mechanism to perform assigning and performing.

8. The method of claim 6 wherein said software tool operates in accordance with a standard for shared-memory parallel processing.

9. In a computer system including a memory shared among a plurality of processing entities, a lock sharing system for performing compound atomic operations by said processing entities comprising:

a pool of locks for synchronizing access to the memory; and

a mechanism for sharing the locks among the plurality of processing entities to minimize lock contention, said processing entities adapted to perform the compound atomic operations using assigned locks, the mechanism adapted to select a lock from the pool to minimize concurrent atomic updates to same or overlapping portions of the shared memory by aliasing memory addresses in accordance with a known upper bound on an amount of the shared memory that is capable of being effected by an atomic operation.

10. The lock sharing system of claim 9 wherein said mechanism is adapted to assign each lock in accordance with an address of the shared memory from an entity'"'"'s compound atomic operations.

11. The lock sharing system of claim 9 wherein the pool is configured in accordance with a count of the plurality of processing entities expected to contend for the locks.

12. The lock sharing system of claim 9 wherein the mechanism comprises a component to synchronize a processing entity in accordance with availability of a lock assigned to the processing entity.

13. The lock sharing system of claim 12 wherein the mechanism comprises a component to release the lock assigned to the processing entity.

14. The lock sharing system of claim 9 including a software tool component configured to generate instructions for said computer system for defining said pool and mechanism.

15. The lock sharing system of claim 14 wherein said software tool component further generates instructions to define said processing entities, said entities including instructions to use said pool and mechanism.

16. The lock sharing system of claim 14 wherein said software tool component operates in accordance with a standard for shared-memory parallel processing.

17. A computer program product having a computer readable medium tangibly embodying computer executable code for generating instructions for a computer system including a memory to be shared among a plurality of processing entities, said computer program product comprising:

code to define a pool of locks for synchronizing access to the memory;

code to define a mechanism for sharing the locks among the plurality of processing entities to minimize lock contention, wherein a lock is selected from the pool to minimize concurrent atomic updates to same or overlapping portions of the shared memory by aliasing memory addresses in accordance with a known upper bound on an amount of the shared memory that is capable of being effected by an atomic operation; and

code to define the plurality of processing entities, said processing entities adapted to perform compound atomic operations using the mechanism.

18. The computer program product of claim 17 wherein the mechanism is adapted to assign a lock to a processing entity in accordance with an address of the shared memory from the processing entity'"'"'s compound atomic operations.

19. The computer program product of claim 17 wherein the code to define the pool is configured in accordance with a count of the plurality of processing entities expected to contend for the locks.

20. The computer program product of claim 17 configured in accordance with a standard for shared-memory parallel processing.

21. A computer program product having a computer readable medium tangibly embodying computer executable code for performing compound atomic operations in a computer system including a memory to be shared among a plurality of processing entities, said computer program product comprising:

code defining a pool of locks for synchronizing access to the memory;

code defining a mechanism for sharing the locks among the plurality of processing entities to minimize lock contention, wherein a lock is selected from the pool to minimize concurrent atomic updates to same or overlapping portions of the shared memory by aliasing memory addresses in accordance with a known upper bound on an amount of the shared memory that is capable of being effected by an atomic operation; and

code defining the plurality of processing entities, said processing entities adapted to perform compound atomic operations using the mechanism.

22. The computer program product of claim 21 wherein the mechanism is adapted to assign a lock to a processing entity in accordance with an address of the shared memory from the processing entity'"'"'s compound atomic operations.

23. The computer program product of claim 21 wherein the pool is configured in accordance with a count of the plurality of processing entities expected to contend for the locks.

24. The computer program product of claim 21 wherein said code is defined by a software tool configured in accordance with a standard for shared-memory parallel processing.