System and Method for Controlling Excessive Parallelism in Multiprocessor Systems

• US 20120180062A1
• Filed: 01/12/2011
• Published: 07/12/2012
• Est. Priority Date: 01/12/2011
• Status: Active Grant

• Current Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Original Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Inventors: Sohi, Gurindar S., Sridharan, Srinath, Gupta, Gagan
• Granted Patent: US 8,843,932 B2
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/508 Monitor
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Execution of a computer program on a multiprocessor system is monitored to detect possible excess parallelism causing resource contention and the like and, in response, to controllably limit the number of processors applied to parallelize program components.

Claims

1. A method of executing a program on a computer having multiple processors that may execute a portion of the program in parallel, the method comprising the steps of:

(a) measuring an execution of at least a portion of the program with different numbers of processors executing the program in parallel to provide at least one value related to a speed of execution of the program on a computer;

(b) adjusting the number of processors executing the program in parallel according to at least one value.

2. The method of claim 1 wherein step (b) includes, at times, reducing the number of processors executing the program to change the value.

3. The method of claim 1 wherein the step of measuring an execution of the program measures a speed of execution of at least a portion of the program.

4. The method of claim 1 wherein the value is at least in part a function of a number of processors executing the portion of the program in parallel.

5. The method of claim 4 wherein the value is further a function of a time of the measurement.

6. The method of claim 1 wherein the method includes the step of associating computational operations of the program with processors during an execution of the program and wherein step (a) and step (b) occur during the execution of the program.

7. The method of claim 1 including the step of (c) repeating steps (a) and (b) during execution of the program.

8. The method of claim 1 wherein the program includes at least one computational operation that may be executed in parallel on the processors and the step of measuring execution of the program measures an execution of at least a portion of the computational operation on at least one processor.

9. The method of claim 1 wherein the step of measuring execution of the program measures an execution of at least a portion of the program on at least one processor when the portion is executed on at least two different numbers of processors in parallel.

10. The method of claim 8 wherein the measuring of the execution of the portion of the program monitors a cycle counter near a start and completion of the portion of the program.

11. The method of claim 1 wherein the step of measuring execution of the program derives speed of execution of the program from data selected from the group consisting of data related to cache misses, data related to cache usage, data related to memory traffic, and data related to resource utilization of at least one processor.

12. The method of claim 1 wherein the value indicates a trend in execution time of the portion of the program

13. The method of claim 1 wherein the measuring of an execution of the program includes the steps of:

(i) executing a portion of the program on only a single processor to obtain a baseline measure for the portion; and

(ii) comparing execution measures of the portion during execution on more than one processor to the baseline measure.

14. The method of claim 1 wherein the adjusting compares the value to at least two ranges to increase the number of processors executing the portion of the program when the value is in the first range and decrease the number of processors executing the portion of the program when the value is in the second range.

15. The method of claim 14 wherein the adjusting further compares the value to a third range to leave the number of processors executing the program unchanged when the value is in the third range.

16. The method of claim 1 wherein the program includes multiple different computational operations that may be executed in parallel on the computer and wherein the measuring an execution of the program measures an execution of a given computational operations on at least one processor when the given computational operation is executed in parallel with different numbers of other computational operations.

17. A method of executing a program in parallel in which at least one computational operation of the program is executed simultaneously on different processors on a computer having N processors available for execution of the computational operation, the method comprising the steps of:

(a) determining a relationship between program execution speed and simultaneous execution of at least portions of the program on different numbers of the processors;

(b) limiting the number of processors that may simultaneously execute the computational operation to less than N based on the relationship.

18. The method of claim 17 wherein the relationship is derived during execution of the program by monitoring the computer at different times when different numbers of processors are executing at least a portion of the program.

19. A computer having multiple processors that may execute a program in parallel, the computer executing a stored program and operating to:

(a) execute the stored program on different numbers of processors in parallel;

(b) measure the execution of at least a portion of the program with the different numbers of processors in parallel to provide at least one value related to a speed of execution of the program on a computer; and

(c) adjust the number of processors executing the program in parallel according to at least one value.

20. The computer of claim 19 wherein the computer executes the stored program to at times, reduce the number of processors executing the program to change the value.

21. The computer of claim 19 wherein the measure of execution of the program measures a speed of execution of at least a portion of the program and a number of processors executing the program in parallel.

22. The electronic computer of claim 19 wherein the electronic computer further operates to repeat steps (b) and (c) during step (a).