US 9,542,221 B2Granted

Dynamic co-scheduling of hardware contexts for parallel runtime systems on shared machines

AssigneeOracle International Corporation

InventorsTimothy L. Harris, Virendra J. Marathe, Martin C. Maas

Life of this patent

Estimating the term…

Loading patent…

Abstract

Multi-core computers may implement a resource management layer between the operating system and resource-management-enabled parallel runtime systems. The resource management components and runtime systems may collectively implement dynamic co-scheduling of hardware contexts when executing multiple parallel applications, using a spatial scheduling policy that grants high priority to one application per hardware context and a temporal scheduling policy for re-allocating unused hardware contexts. The runtime systems may receive resources on a varying number of hardware contexts as demands of the applications change over time, and the resource management components may co-ordinate to leave one runnable software thread for each hardware context. Periodic check-in operations may be used to determine (at times convenient to the applications) when hardware contexts should be re-allocated. Over-subscription of worker threads may reduce load imbalances between applications. A co-ordination table may store per-hardware-context information about resource demands and allocations.

Claims20

Dependent claims

A method, comprising:

performing by a computer:
receiving two or more applications configured for parallel execution on the computer, each application implementing multiple software threads for performing work on behalf of the respective application;
for each of the two or more applications, associating each of the application's multiple software threads with a respective one of multiple hardware contexts in the computer, wherein a single software thread of each of the two or more applications is associated with each of the multiple hardware contexts, and wherein the software threads of the two or more applications remain associated with their respective hardware contexts during execution of the two or more applications;
for each of the two or more applications:
determining one or more of the multiple hardware contexts to allocate to the application, dependent on collective resource demands of the two or more applications, wherein each of the multiple hardware contexts is allocated to only one of the two or more applications;
and
allocating the one or more determined hardware contexts to the software threads of the application that are associated with the one or more determined hardware contexts, wherein each hardware context is allocated to a single software thread of one of the two or more applications;
the software threads of the two or more applications to which hardware contexts are allocated beginning to perform work on behalf of the two or more applications on the hardware contexts;
and
prior to completing execution of the two or more applications, and in response to detecting a change in the collective resource demands of the two or more applications, re-allocating at least one of the hardware contexts to another software thread that is associated with the hardware context, wherein the other software thread is a software thread of an application other than the application to which the hardware context is allocated, and wherein the software thread of the application to which the hardware context is allocated remains associated with the hardware context while the other software thread is executing on the hardware context.

7 more elements

A system, comprising:

a plurality of processor cores, each of which includes one or more hardware contexts;
a memory comprising program instructions that when executed on the plurality of processor cores cause the plurality of processor cores to implement:
two or more resource management component instances;
two or more resource-management-enabled parallel runtime systems;
and
a co-ordination table that is accessible by the two or more resource management component instances and that stores information about resource demands for and allocations of each of the hardware contexts in each of the plurality of processor cores;
wherein each of the two or more resource-management-enabled parallel runtime systems is configured to:
receive two or more applications configured for parallel execution on the plurality of processor cores;
and
for each of the two or more applications:
create a respective software thread for the application for each of the hardware contexts in each of the plurality of processor cores;
associate the respective software thread for the application with each of the hardware contexts in each of the plurality of processor cores, wherein a single software thread of each of the two or more applications is associated with each of the multiple hardware contexts, and wherein the software threads of the two or more applications remain associated with their respective hardware contexts during execution of the two or more applications;
determine one or more of the hardware contexts to allocate to the application, dependent on collective resource demands of the two or more applications, wherein each of the multiple hardware contexts is allocated to only one of the two or more applications;
and
allocate the one or more determined hardware contexts to the software threads of the application that are associated with the one or more determined hardware contexts, wherein each hardware context is allocated to a single software thread of one of the two or more applications;
wherein each of the two or more resource management component instances is configured to:
record information indicating the allocation of the determined hardware contexts to the associated threads for the application in the co-ordination table;
and
receive up-calls from the software threads for the two or more applications to which hardware contexts are allocated to begin performing work on behalf of the two or more applications on the hardware contexts;
and
wherein one of the two or more resource-management-enabled parallel runtime systems is further configured to:
re-allocate at least one of the hardware contexts to another software thread that is associated with the hardware context, wherein the other software thread is a software thread of an application other than the application to which the hardware context is allocated dependent, at least in part, on the information stored in the co-ordination table, and wherein the software thread of the application to which the hardware context is allocated remains associated with the hardware context while the other software thread is executing on the hardware context.

19 more elements

A non-transitory, computer-readable storage medium storing program instructions that when executed on a multi-core computer cause the multi-core computer to perform:

receiving two or more applications configured for parallel execution on the multi-core computer, each application implementing multiple software threads for performing work on behalf of the respective application;
for each of the two or more applications, associating each of the application's multiple software threads with a respective one of multiple hardware contexts in the multi-core computer, wherein a single software thread of each of the two or more applications is associated with each of the multiple hardware contexts, and wherein the software threads of the two or more applications remain associated with their respective hardware contexts during execution of the two or more applications;
for each of the two or more applications:
determining one or more of the multiple hardware contexts to allocate to the application, dependent on collective resource demands of the two or more applications, wherein each of the multiple hardware contexts is allocated to only one of the two or more applications;
and
allocating the one or more determined hardware contexts to the software threads of the application that are associated with the one or more determined hardware contexts, wherein each hardware context is allocated to a single software thread of one of the two or more applications;
the software threads of the two or more applications to which hardware contexts are allocated beginning to perform work on behalf of the two or more applications on the hardware contexts;
and
prior to completing execution of the two or more applications, and in response to detecting a change in the collective resource demands of the two or more applications, re-allocating at least one of the hardware contexts to another software thread that is associated with the hardware context, wherein the other software thread is a software thread of an application other than the application to which the hardware context is allocated, and wherein the software thread of the application to which the hardware context is allocated remains associated with the hardware context while the other software thread is executing on the hardware context.

6 more elements

Dependencies are inferred from the claim text.

Facts

Application: 14/285,513Filed 22 May 2014
Published: US 2015/0339158 A126 Nov 2015
Granted: 10 Jan 2017
Term ends: Not estimatedThe source records don’t support an estimate.

Classification11 codes

G06F 9/4881
By program, e.g. task dispatcher, supervisor, operating system: scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
G06F 9/48
Multiprogramming arrangements: program initiating; Program switching, e.g. by interrupt
G06F 9/4856
Task life-cycle, e.g. stopping, restarting, resuming execution: resumption being on a different machine, e.g. task migration, virtual machine…
G06F 9/50
Multiprogramming arrangements: allocation of resources, e.g. of the central processing unit [CPU]