Method and means for increasing performance of multiprocessor computer systems by reducing accesses to global memory locations through the use of quanta

• US 6,430,659 B1
• Filed: 09/22/2000
• Issued: 08/06/2002
• Est. Priority Date: 09/22/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dierks, Herman, Sharma, Satya, Hymas, William James, Cossmann, Helmut
• Primary Examiner(s): Yoo, Do Hyun
• Assistant Examiner(s): MCLEAN MAYO, KIMBERLY N
• Application Number:
  US09/668,503
• Time in Patent Office: 683 Days
• Field of Search: 711/147, 711/153, 711/154, 711/141, 711/150, 707/201, 707/202, 707/203, 707/8, 707/10, 714/6, 709/200, 709/201, 709/215, 709/217, 709/248, 709/400
• US Class Current: 711/147
• CPC Class Codes: G06F 12/0837 with software control, e.g. non-cacheable data
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

The present invention relates to means, a method and a computer program product of administrating in a computer system a global data element shared by a multitude of exploiters within said computer system for reducing contention among said exploiters.

It is suggested to execute a first step by a first exploiter of accumulating one or a multitude of modifications performed by said first exploiter with respect to the current contents of said global data element into a first local data element not shared by other exploiters.

In a second step executed by the first exploiter a size of the accumulated modifications in the first local data element with respect to the current contents of the global data element is determined. Moreover it is determined, if said size exceeds a specified quantum.

If said size exceeds the specified quantum, the global data element is updated with the accumulated modifications as new contents.

Claims

1. A computerized method of administrating in a computer system a global data element shared by a multitude of exploiters within said computer system for reducing contention,

said method comprising

a first-step executed by a first exploiter of accumulating one or a multitude of modifications performed by said first exploiter with respect to the current contents of said global data element into a first local data element not shared by other exploiters;

a second-step executed by said first exploiter of determining a size of said accumulated modifications in said first local data element with respect to said current contents of said global data element and determining, if said size exceeds a specified quantum;

a third-step of updating, if said size exceeds said specified quantum, said global data element with said accumulated modifications as new contents.

2. A computerized method of administrating in a computer system a global data element shared by a multitude of exploiters within said computer system for reducing contention according to claim 1,

said method comprising

a fourth-step of notifying a second exploiter of said updating,

whereby said second exploiter is executing said first-step, said second-step and said third-step with respect to accumulated modifications of said second exploiter in a second local data element not shared with other exploiters, and,

in response to said fourth-step, a fifth-step

of causing said second exploiter to readjust accumulated modifications in said second local data element with respect to said new contents of said global data element if required, and

of causing said second exploiter to execute said first-step, said second-step and said third-step with respect to said new contents of said global data element.

3. A computerized method of administrating in a computer system a global data element shared by a multitude of exploiters within said computer system for reducing contention according to claim 2,

wherein said size is rated based on a predefined measure.

4. A computerized method of administrating in a computer system a global data element shared by a multitude of exploiters within said computer system for reducing contention according to claim 3,

wherein, if said global data element comprises a numerical value, said measure is based on the difference of said current contents and said next contents of said global data element, or

wherein said measure is based on an estimated execution path length required to update said current contents of said global data element with said accumulated modifications.

5. A computerized method of administrating in a computer system a global data element shared by a multitude of exploiters within said computer system for reducing contention according to claim 3,

wherein said global data element comprises a measure for the amount of a resource allocable by said computer system.

6. A computerized method of administrating in a computer system a global data element shared by a multitude of exploiters within said computer system for reducing contention according to claim 5,

wherein said specified quantum is dynamically redefined depending on said new contents of said global data element.

7. A computerized method of administrating in a computer system a global data element shared by a multitude of exploiters within said computer system for reducing contention according to claim 3,

wherein said exploiters are parallel processes controlled by an operating system.

8. A computerized method of administrating in a computer system a global data element shared by a multitude of exploiters within said computer system for reducing contention according to claim 5,

wherein said computer system is a multiprocessor system with a global memory and said exploiters are individual processors, and

wherein said global data element comprises a measure for the memory allocable to any of said exploiters.

9. A computerized method of administrating in a computer system a global data element shared by a multitude of exploiters within said computer system for reducing contention according to claim 3,

wherein said computer system is a system according to the NUMA architecture with local memory attached to each NUMA node and the combination of all of said local memories forming the global memory.

10. Means of administrating in a multiprocessor computer system a global data element shared by a multitude of processors within said computer system in a global memory for reducing contention,

said means comprising

means of a first-type executable by a first processor for accumulating one or a multitude of modifications performed by said first processor with respect to the current contents of said global data element into a first local data element not shared by other processors;

means of a second-type executable by said first processor for determining a size of said accumulated modifications in said first local data element with respect to said current contents of said global data element and determining, if said size exceeds a specified quantum;

means of a third-type for updating, if said size exceeds said specified quantum, said global data element with said accumulated modifications as new contents.

11. Means of administrating in a multiprocessor computer system a global data element shared by a multitude of processors within said computer system in a global memory for reducing contention according to claim 10,

said means comprising

means of a fourth-type for notifying a second processor of said updating, whereby said second processor is enabled to execute means of said first-type, means of said second-type and means of said third-type with respect to accumulated modifications of said second processor in a second local data element not shared with other processors, and,

means of a fifth-type, responsive to means of said fourth-type,

for causing said second processor to readjust accumulated modifications in said second local data element with respect to said new contents of said global data element if required, and

for causing said second processor to execute means of said first-type, means of said second-type and means of said third-type with respect to said new contents of said global a data element.

12. Means of administrating in a multiprocessor computer system a global data element shared by a multitude of processors within said computer system in a global memory according for reducing contention to claim 11,

wherein said size is rated based on a predefined measure.

13. Means of administrating in a multiprocessor computer system a global data element shared by a multitude of processors within said computer system in a global memory according for reducing contention to claim 12,

wherein, if said global data element comprises a numerical value, said measure is based on the difference of said current contents and said next contents of said global data element, or

wherein said measure is based on an estimated execution path length required to update said current contents of said global data element with said accumulated modifications.

14. Means of administrating in a multiprocessor computer system a global data element shared by a multitude of processors within said computer system in a global memory according for reducing contention to claim 12,

wherein said global data element comprises a measure for the amount of a resource allocable by said computer system.

15. Means of administrating in a multiprocessor computer system a global data element shared by a multitude of processors within said computer system in a global memory for reducing contention according to claim 14,

wherein said specified quantum is dynamically redefined depending on said new contents of said global data element.

16. Means of administrating in a multiprocessor computer system a global data element shared by a multitude of processors within said computer system in a global memory for reducing contention according to claim 12,

wherein said multiprocessor computer system is a system according to the NUMA architecture with local memory attached to each NUMA node and the combination of all of said local memories forming the global memory.

17. A computer program product in a computer-readable medium for use in a data processing system for administrating in a computer system a global data element shared by a multitude of exploiters within said computer system for reducing contention,

said computer program product comprising

instructions executable in a first-step by a first exploiter for accumulating one or a multitude of modifications performed by said first exploiter with respect to the current contents of said global data element into a first local data element not shared by other exploiters;

instructions executable in second-step by said first exploiter for determining a size of said accumulated modifications in said first local data element with respect to said current contents of said global data element and determining, if said size exceeds a specified quantum;

instructions executable in a third-step for updating, if said size exceeds said specified quantum, said global data element with said accumulated modifications as new contents.

18. A computer program product in a computer-readable medium for use in a data processing system for administrating in a computer system a global data element shared by a multitude of exploiters within said computer system for reducing contention according to claim 17,

said computer program product comprising

instructions executable in a fourth-step for notifying a second exploiter of said updating, whereby said second exploiter is executing said first-step, said second-step and said third-step with respect to accumulated modifications of said second exploiter in a second local data element not shared with other exploiters, and,

instructions executable in a fifth-step in response to said fourth-step

for causing said second exploiter to readjust accumulated modifications in said second local data element with respect to said new contents of said global data element if required, and

for causing said second exploiter to execute said first-step, said second-step and said third-step with respect to said new contents of said global a data element.

19. A computer program product in a computer-readable medium for use in a data processing system for administrating in a computer system a global data element shared by a multitude of exploiters within said computer system for reducing contention according to claim 18,

wherein said size is rated based on a predefined measure.

20. A computer program product in a computer-readable medium for use in a data processing system for administrating in a computer system a global data element shared by a multitude of exploiters within said computer system for reducing contention according to claim 19,

wherein, if said global data element comprises a numerical value, said measure is based on the difference of said current contents and said next contents of said global data element, or

wherein said measure is based on an estimated execution path length required to update said current contents of said global data element with said accumulated modifications.

21. A computer program product in a computer-readable medium for use in a data processing system for administrating in a computer system a global data element shared by a multitude of exploiters within said computer system for reducing contention according to claim 19,

wherein said global data element comprises a measure for the amount of a resource allocable by said computer system.

22. A computer program product in a computer-readable medium for use in a data processing system for administrating in a computer system a global data element shared by a multitude of exploiters within said computer system for reducing contention according to claim 21,

wherein said specified quantum is dynamically redefined depending on said new contents of said global data element.

23. A computer program product in a computer-readable medium for use in a data processing system for administrating in a computer system a global data element shared by a multitude of exploiters within said computer system for reducing contention according to claim 19,

wherein said exploiters are parallel processes controlled by an operating system.

24. A computer program product in a computer-readable medium for use in a data processing system for administrating in a computer system a global data element shared by a multitude of exploiters within said computer system for reducing contention according to claim 21,

wherein said computer system is a multiprocessor system with a global memory and said exploiters are individual processors, and wherein said global data element comprises a measure for the memory allocable to any of said exploiters.

25. A computer program product in a computer-readable medium for use in a data processing system for administrating in a computer system a global data element shared by a multitude of exploiters within said computer system for reducing contention according to claim 19,

wherein said computer system is a system according to the NUMA architecture with local memory attached to each NUMA node and the combination of all of said local memories forming the global memory.