MEMORY-AWARE SCHEDULING FOR NUMA ARCHITECTURES

• US 20120174117A1
• Filed: 12/29/2010
• Published: 07/05/2012
• Est. Priority Date: 12/29/2010
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Karstens, Jan, Jula, Alin, Froemmgen, Alexander
• Granted Patent: US 8,635,626 B2
• Time in Patent Office: Days
• US Class Current: 718/105
• CPC Class Codes: G06F 9/5088 involving task migration

Abstract

A topology reader may determine a topology of a Non-Uniform Memory Access (NUMA) architecture including a number of, and connections between, a plurality of sockets, each socket including one or more cores and at least one memory configured to execute a plurality of threads of a software application. A core list generator may generate, for each designated core of the NUMA architecture, and based on the topology, a proximity list listing non-designated cores in an order corresponding to a proximity of the non-designated cores to the designated core. A core selector may determine, at a target core and during the execution of the plurality of threads, that the target core is executing an insufficient number of the plurality of threads, and may select a source core at the target core, according to the proximity list associated therewith, for subsequent transfer of a transferred thread from the selected source core to the target core for execution thereon.

Claims

1. A system including instructions recorded on a computer-readable medium, the system comprising:

a topology reader configured to determine a topology of a Non-Uniform Memory Access (NUMA) architecture including a number of, and connections between, a plurality of sockets, each socket including one or more cores and at least one memory configured to execute a plurality of threads of a software application;

a core list generator configured to generate, for each designated core of the NUMA architecture, and based on the topology, a proximity list listing non-designated cores in an order corresponding to a proximity of the non-designated cores to the designated core; and

a core selector configured to determine, at a target core and during the execution of the plurality of threads, that the target core is executing an insufficient number of the plurality of threads, and further configured to select a source core at the target core, according to the proximity list associated therewith, for subsequent transfer of a transferred thread from the selected source core to the target core for execution thereon.

2. The system of claim 1, wherein the topology reader is configured to access operating system files of at least one computing device implementing the NUMA architecture in order to determine the topology.

3. The system of claim 1, wherein the topology reader is configured to receive the topology from a user by way of a user interface

4. The system of claim 1, comprising a graph builder configured to receive the topology and to convert the topology into a graph.

5. The system of claim 4, wherein the core list generator is configured to generate the proximity list for the designated core using a shortest path algorithm on the graph

6. The system of claim 1, wherein the proximity of the non-designated cores to the designated core is defined in terms of relative memory latencies between each of the non-designated cores and the designated core.

7. The system of claim 1, wherein the core selector is configured to determine that the target core is idle.

8. The system of claim 1, wherein the core selector is configured to select the source core including inspecting execution threads in at least one private queue thereof.

9. The system of claim 8, wherein the at least one private queue includes a new nested thread queue and a suspended thread queue, and wherein the core selector is configured to prefer the new nested thread queue when inspecting the source core.

10. The system of claim 1, wherein the core selector is configured to inspect at least one closer core of the proximity list multiple times before inspecting at least one farther core from the proximity list.

11. The system of claim 1, wherein the core selector is configured to determine that no execution threads should be transferred from available source cores, and to thereafter inspect an application thread queue of the parallel application for obtaining execution threads for execution on the target core.

12. A computer program product, the computer program product being tangibly embodied on a computer-readable storage medium and comprising instructions that, when executed, are configured to:

determine a topology of a Non-Uniform Memory Access (NUMA) architecture including a number of, and connections between, a plurality of sockets, each socket including one or more cores and at least one memory configured to execute a plurality of threads of a software application;

generate, for each designated core of the NUMA architecture, and based on the topology, a proximity list listing non-designated cores in an order corresponding to a proximity of the non-designated cores to the designated core;

determine, at a target core and during the execution of the plurality of threads, that the target core is executing an insufficient number of the plurality of threads;

select a source core at the target core, according to the proximity list associated therewith; and

transfer a transferred thread from the selected source core to the target core for execution thereon.

13. The computer program product of claim 12, wherein the topology is determined including accessing operating system files of at least one computing device implementing the NUMA architecture

14. The computer program product of claim 12, wherein the instructions, when executed, are configured to receive the topology and to convert the topology into a graph for use in generating the proximity list.

15. The computer program product of claim 12, wherein the selection of the selected source core includes inspecting execution threads in at least one private queue thereof.

16. The computer program product of claim 15, wherein the at least one private queue includes a new nested thread queue and a suspended thread queue, and wherein the selection prefers the new nested thread queue when inspecting the source core.

17. The computer program product of claim 12, wherein the selecting includes inspecting at least one closer core of the proximity list multiple times before inspecting at least one farther core from the proximity list.

18. A computer-implemented method comprising:

determining a topology of a Non-Uniform Memory Access (NUMA) architecture including a number of, and connections between, a plurality of sockets, each socket including one or more cores and at least one memory configured to execute a plurality of threads of a software application;

generating, for each designated core of the NUMA architecture, and based on the topology, a proximity list listing non-designated cores in an order corresponding to a proximity of the non-designated cores to the designated core;

determining, at a target core and during the execution of the plurality of threads, that the target core is executing an insufficient number of the plurality of threads;

selecting a source core at the target core, according to the proximity list associated therewith; and

transferring a transferred thread from the selected source core to the target core for execution thereon.

19. The method of claim 18, wherein determining the topology includes converting the topology into a graph for use in generating the proximity list.

20. The method of claim 18, wherein the selecting includes inspecting at least one closer core of the proximity list multiple times before inspecting at least one farther core from the proximity list.