Adaptive Contention-Aware Thread Placement for Parallel Runtime Systems

• US 20160246647A1
• Filed: 02/19/2015
• Published: 08/25/2016
• Est. Priority Date: 02/19/2015
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Collins, Alexander J., Harris, Timothy L.
• Granted Patent: US 10,133,602 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 2209/501 Performance criteria
• CPC Class Codes: G06F 2209/508 Monitor
• CPC Class Codes: G06F 9/4856 resumption being on a different machine, e.g. task migration, virtual machine migration G06F9/5088 takes precedence
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

An adaptive contention-aware thread scheduler may place software threads for pairs of application on the same socket of a multi-socket machine for execution in parallel. Initial placements may be based on profile data that characterizes the machine and its behavior when multiple applications execute on the same socket. The profile data may be collected during execution of other applications. It may identify performance counters within the cores of the processor sockets whose values are suitable for use in predicting whether the performance of a pair of applications will suffer when they are executed together on the same socket (e.g., values indicative of their demands for particular shared resources). During execution, the scheduler may examine the performance counters (or performance metrics derived therefrom) and determine different placement decisions (e.g., placing an application with high demand for resources of one type together with an application with low demand for those resources).

Claims

1. A method, comprising:

performing, by a computer that includes multiple processor sockets, each of which includes one or more processor cores;

receiving an application that is configured for parallel execution on the computer;

determining, dependent on profile data that characterizes the behavior of the computer when multiple applications are executed in parallel on a single one of the processor sockets, that the application is to be executed on a given one of the multiple processor sockets while a particular other application is also executing on the given one of the multiple processor sockets;

beginning execution of the given application, wherein execution of the given application comprises executing program instructions that perform work on behalf of the given application and that cause a respective value of each of one or more performance counters in one or more processor cores of the given one of the multiple processor sockets on which respective software threads of the given application are executing to be updated; and

determining, prior to completing execution of the given application or the particular other application, and dependent on the updated values of the one or more performance counters, that execution of the given application or execution of the particular other application is to continue on a different one of the multiple processor sockets.

2. The method of claim 1, wherein the updated values of the performance counters are indicative of the extent to which the given application and the particular other application compete for a resource of a given type on the given processor socket that is shared by the given application and the particular other application.

3. The method of claim 2, wherein said determining that execution of the given application or execution of the particular other application is to continue on a different one of the multiple processor sockets comprises determining that demand for the shared resource by both the given application and the particular other application is high.

4. The method of claim 3, further comprising:

selecting the different one of the multiple processor sockets, wherein selecting the different one of the multiple processor sockets comprises identifying a processor socket on which is executing an application for which demand for resources of the given type is low.

5. The method of claim 2, wherein the updated values of the performance counters are indicative of the demand by the given application for shared memory resources.

6. The method claim 2, wherein the updated values of the performance counters are indicative of a cache miss rate for the given application or a rate at which load instructions are attempted by the given application.

7. The method of claim 1, wherein the profile data that characterizes the behavior of the computer when multiple applications are executed in parallel on a single one of the multiple processor sockets of the computer indicates that contention for a shared resource of a given type by multiple applications executing in parallel on a single one of the multiple processor sockets negatively impacts the performance of the multiple applications.

8. The method of claim 1, wherein the profile data that characterizes the behavior of the computer when multiple applications are executed in parallel on a single one of the multiple processor sockets of the computer indicates that values of the one or more performance counters in the one or more processor cores of the given one of the multiple processor sockets on which respective software threads of the given application are executing are suitable for use in predicting whether or not the performance of a pair of applications executed in parallel on the same one of the multiple sockets will be significantly lower than the performance of the pair of applications when executed in parallel on respective different ones of the multiple sockets.

9. The method of claim 1,

wherein the method further comprises, prior to said receiving, performing an operation to characterize the behavior of the computer when multiple applications are executed in parallel on a single one of the multiple processor sockets of the computer;

wherein characterizing the behavior of the computer comprises one or more of;

identifying the one or more performance counters whose values are suitable for use in predicting whether or not the performance of a pair of applications executed in parallel on the same one of the multiple sockets will be significantly lower than the performance of the pair of applications when executed in parallel on respective different ones of the multiple socket;

or

identifying the given type of the shared resources for which contention by multiple applications executing in parallel on a single one of the multiple processor sockets negatively impacts the performance of the multiple applications.

10. The method of claim 1, further comprising:

performing, periodically, at pre-determined time intervals, an operation to determine whether or not execution of the given application and the particular other application should continue in parallel on the given one of the multiple processor sockets;

wherein performing the operation comprises comparing the updated values of the one or more performance counters with values of one or more performance counters in one or more other processor cores of the given one of the multiple processor sockets on which respective software threads of the particular other application are executing.

11. The method of claim 1, further comprising:

performing, in response to a context switch between software threads of the applications executing on the given one of the multiple processor sockets, an operation to determine whether or not execution of the given application and the particular other application should continue in parallel on the given one of the multiple processor sockets;

wherein performing the operation comprises comparing the updated values of the one or more performance counters with values of one or more performance counters in one or more other processor cores of the given one of the multiple processor sockets on which respective software threads of the particular other application are executing.

12. The method of claim 1, wherein at least one of said determining that the application is to be executed on a given one of the multiple processor sockets or said determining that execution of the given application or execution of the particular other application is to continue on a different one of the multiple processor sockets is performed by a process or thread of an operating system executing on the computer or a resource-management-enabled parallel runtime system executing on the computer.

13. The method of claim 1,

wherein the method further comprises:

aggregating the updated values of the one or more performance counters to generate one or more performance metrics for the given application;

aggregating values of one or more performance counters in one or more other processor cores of the given one of the multiple processor sockets on which respective software threads of the particular other application are executing to generate one or more performance metrics for the particular other application;

aggregating values of one or more performance counters in one or more processor cores of the different one of the multiple processor sockets on which respective software threads of a third application are executing to generate one or more performance metrics for the third application; and

wherein said determining that execution of the given application or execution of the particular other application is to continue on a different one of the multiple processor sockets is dependent on one or more of;

the one or more performance metrics for the given application, the one or more performance metrics for the particular other application, or the one or more performance metrics for the third application.

14. A system, comprising:

a plurality of collections of processor cores, each of which includes multiple processor cores, wherein each of the multiple processor cores includes a plurality of performance counters, and wherein the multiple processor cores in each collection of processor cores share at least one hardware resource;

a memory comprising;

program instructions that when executed on one or more of the multiple processor cores in a given one of the collections of processor cores cause the one or more processor cores to implement a given one of the multiple applications; and

additional program instructions that when executed on one or more other ones of the multiple processor cores in the given one of the collections of processor cores cause the one or more other processor cores to implement another one of the multiple applications;

wherein, when executed by a worker thread of the given application, a portion of the program instructions perform work on behalf of the given application and cause a respective value of each of one or more of the plurality of performance counters of the one or more processor cores in the given one of the collections of processor cores to be updated;

wherein, when executed by a worker thread of the other application, a portion of the additional program instructions perform work on behalf of the other application and cause a respective value of each of one or more of the plurality of performance counters of the one or more other processor cores in the given one of the collections of processor cores to be updated; and

wherein a scheduler thread of the given application is configured to;

collect the updated values of the one or more of the plurality of performance counters of the one or more processor cores and the one or more other processor cores in the given one of the collections of processor cores; and

determine, prior to completing execution of the given application, and dependent on the collected updated values of the performance counters, that execution of the given application or execution of the other application is to continue on one or more processor cores in a different one of the plurality of collections of processor cores.

15. The system of claim 14,

wherein the memory further comprises a performance metrics table that is accessible by a respective software thread of each of multiple applications that is executing on one of the multiple processor cores in a respective one of the plurality of collections of processor cores;

wherein the performance metrics table stores performance counter information that was aggregated from data collected during execution of each of the multiple applications;

wherein the scheduler thread of the given application is further configured to;

aggregate the collected updated values of the performance counters to generate one or more performance metrics for the given application; and

write, to the performance metrics table, data representing the one or more performance metrics for the given application;

wherein to determine that execution of the given application or execution of the other application is to continue on one or more processor cores in a different one of the plurality of collections of processor cores, the scheduler thread of the given application is configured to examine data stored in the performance metrics table that represents one or more performance metrics for the other application or data stored in the performance metrics table that represents one or more performance metrics for a third application that is executing on a different one of the plurality of collections of processor cores.

16. The system of claim 15, wherein to determine that execution of the given application is to continue on one or more processor cores in a different one of the plurality of collections of processor cores, the scheduler thread of the given application is configured to determine that the performance metrics for the given application and the performance metrics for the third application indicate that demand for shared resources of a given type is high for at most one of given application and the third application.

17. The system of claim 14,

wherein the memory further comprises a schedule table that is accessible by a respective software thread of each of multiple applications that is executing on one of the multiple processor cores in a respective one of the plurality of collections of processor cores;

wherein the schedule table stores information indicating an assignment of a respective one of the plurality of collections of processor cores to each of the multiple applications; and

wherein, in response to a determination that execution of the given application is to continue on one or more processor cores in a different one of the plurality of collections of processor cores, the scheduler thread of the given application is further configured to;

update the information stored in the schedule table to indicate the assignment of the different one of the plurality of collections of processor cores to the given application; and

initiate the continued execution of the given application on the different one of the plurality of collections of processor cores.

18. A non-transitory, computer-readable storage medium storing program instructions that when executed on a multi-socket computer cause the multi-socket computer to implement an adaptive contention-aware thread scheduler;

wherein the adaptive contention-aware thread scheduler is configured to;

collect, during execution of two applications on two or more processor cores of a given processor socket of the multi-socket computer, values of one or more performance counters in each of the two or more processor cores of the given processor socket, wherein the values of the one or more performance counters in each of the two or more processor cores indicate the extent to which the two applications compete for a resource of a given type on the given processor socket that is shared by the two applications;

determine, prior to completing execution of the two applications, and dependent on the collected values, that demand for the shared resource by both of the two applications is high; and

select, in response to determining that demand for the shared resource by both of the two applications is high, a different one of the processor sockets of the multi-socket computer on which to continue execution of one of the two applications, wherein to select a different one of the processor sockets, the adaptive contention-aware thread scheduler is configured to identify a processor socket on which an application with a low demand for resources of the given type is executing.

19. The non-transitory, computer-readable storage medium of claim 18,

wherein to collect the values of the one or more performance counters in each of the two or more processor cores of the given processor socket, the adaptive contention-aware thread scheduler is configured to call a function of a performance-focused library using an application programming interface that is defined for the performance-focused library.

20. The non-transitory, computer-readable storage medium of claim 19, wherein the adaptive contention-aware thread scheduler is a component of an operating system executing on the multi-socket computer or is a component of a resource-management-enabled parallel runtime system executing on the multi-socket computer.