US 9,317,339 B2Granted

Systems and methods for implementing work stealing using a configurable separation of stealable and non-stealable work items

AssigneeOracle International Corporation

InventorsYosef Lev, Guy L. Steele, Jr.

Life of this patent

Estimating the term…

Loading patent…

Abstract

A system may perform work stealing using a dynamically configurable separation between stealable and non-stealable work items. The work items may be held in a double-ended queue (deque), and the value of a variable (index) may indicate the position of the last stealable work item or the first non-stealable work item in the deque. A thread may steal a work item only from the portion of another thread's deque that holds stealable items. The owner of a deque may add work items to the deque and may modify the number or percentage of stealable work items, the number or percentage of non-stealable work items, and/or the ratio between stealable and non-stealable work items in the deque during execution. For example, the owner may convert stealable work items to non-stealable work items, or vice versa, in response to changing conditions and/or according to various work-stealing policies.

Claims20

Dependent claims

A method, comprising:

performing, by a computer:
beginning execution of a multithreaded application;
adding, by a given thread of the application to a pool of work items that were generated by the given thread, a work item, wherein the pool of work items is configured to hold a number of work items that are stealable by other threads and a number of work items that are not stealable by other threads, and wherein the number of work items in the pool of work items that are stealable by other threads is adjustable by the given thread during execution of the multithreaded application;
determining, by the given thread, that there are not sufficient stealable work items in the pool of work items;
and
converting, by the given thread and in response to determining that there are not sufficient stealable work items in the pool of work items, one or more work items that are not stealable into work items that are stealable;
wherein, prior to converting the one or more work items that are not stealable into work items that are stealable, the one or more work items that are not stealable are stored in either or both of:
a representation in which an amount of context information needed for execution of the work items that is included in the representation is less than an amount of context information needed for execution that is included in a representation used to represent stealable work items, or
a different data structure than a data structure in which work items that are stealable are stored.

6 more elements

A system, comprising:

one or more processor cores;
and
a memory coupled to the one or more processor cores and storing program instructions that when executed on the one or more processor cores cause the one or more processor cores to perform:
beginning execution of a multithreaded application;
adding, by a given thread of the application to a pool of work items that were generated by the given thread, a work item, wherein the pool of work items is configured to hold a number of work items that are stealable by other threads and a number of work items that are not stealable by other threads, and wherein the number of work items in the pool of work items that are stealable by other threads is adjustable by the given thread during execution of the multithreaded application;
determining, by the given thread, that there are not sufficient stealable work items in the pool of work items;
and
converting, by the given thread and in response to determining that there are not sufficient stealable work items in the pool of work items, one or more work items that are not stealable into work items that are stealable;
wherein, prior to converting the one or more work items that are not stealable into work items that are stealable, the one or more work items that are not stealable are stored in either or both of:
a representation in which an amount of context information needed for execution of the work items that is included in the representation is less than an amount of context information needed for execution that is included in a representation used to represent stealable work items, or
a different data structure than a data structure in which work items that are stealable are stored.

8 more elements

A non-transitory, computer-readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to perform:

beginning execution of a multithreaded application;
adding, by a given thread of the application to a pool of work items that were generated by the given thread, a work item, wherein the pool of work items is configured to hold a number of work items that are stealable by other threads and a number of work items that are not stealable by other threads, and wherein the number of work items in the pool of work items that are stealable by other threads is adjustable by the given thread during execution of the multithreaded application;
determining, by the given thread, that there are not sufficient stealable work items in the pool of work items;
and
converting, by the given thread and in response to determining that there are not sufficient stealable work items in the pool of work items, one or more work items that are not stealable into work items that are stealable;
wherein, prior to converting the one or more work items that are not stealable into work items that are stealable, the one or more work items that are not stealable are stored in either or both of:
a representation in which an amount of context information needed for execution of the work items that is included in the representation is less than an amount of context information needed for execution that is included in a representation used to represent stealable work items, or
a different data structure than a data structure in which work items that are stealable are stored.

5 more elements

Dependencies are inferred from the claim text.