US 8,914,799 B2 · High performance implementation of the OpenMP tasking feature

Abstract

A method and system for creating and executing tasks within a multithreaded application composed according to the OpenMP application programming interface (API). The method includes generating threads within a parallel region of the application, and setting a counter equal to the quantity of the threads. The method also includes, for each one of the plurality of threads, assigning an implicit task, and executing the implicit task. Further, the method includes, upon encountering a task construct, during execution of the implicit tack, for an explicit asynchronous task generating the explicit asynchronous task, adding the explicit asynchronous task to a first task queue, where the first task queue corresponds to the one of the plurality of threads; and incrementing the counter by one.

Drawings

Drawings are temporarily unavailable. Open the PDF at USPTO

Drawings

Claims20

Dependent claims

A system, comprising:

a processor;
a memory;
and
a plurality of instructions stored in the memory that, when executed by the processor, perform the steps of:
generating a plurality of threads within a parallel region of an application;
setting a counter equal to a quantity of the plurality of threads;
for each one of the plurality of threads:
assigning an implicit task;
executing the implicit task;
upon encountering a task construct, during execution of the implicit task, for an explicit task:
determining that a first task queue of a plurality of task queues is not full;
setting an execution mode of the explicit task as an explicit asynchronous task within the task construct based on the determination that the first task queue is not full;
converting at least one ancestor stack task to a heap task based on a determination that the explicit asynchronous task is descended from the at least one ancestor stack task;
generating the explicit asynchronous task;
adding the explicit asynchronous task to the first task queue,
wherein the first task queue corresponds to the one of the plurality of threads,
wherein each of the plurality of task queues corresponds to one of the plurality of threads, and
wherein the explicit asynchronous task is executed by allocating a data environment data structure for the explicit asynchronous task on a heap of a host routine;
and
incrementing the counter by one.

17 more elements

A non-transitory computer readable medium for generating tasks for a parallel processing application, comprising instructions for:

generating a plurality of threads within a parallel region of the application;
setting a counter equal to a quantity of the plurality of threads;
for each one of the plurality of threads:
assigning an implicit task;
executing the implicit task;
upon encountering a task construct, during execution of the implicit task, for an explicit task:
determining that a first task queue of a plurality of task queues is not full;
setting an execution mode of the explicit task as an explicit asynchronous task within the task construct based on the determination that the first task queue is not full;
converting at least one ancestor stack task to a heap task based on a determination that the explicit asynchronous task is descended from the at least one ancestor stack task;
generating the explicit asynchronous task;
adding the explicit asynchronous task to the first task queue,
wherein the first task queue corresponds to the one of the plurality of threads,
wherein each of the plurality of task queues corresponds to one of the plurality of threads, and
wherein the explicit asynchronous task is executed by allocating a data environment data structure for the explicit asynchronous task on a heap of a host routine;
and
incrementing the counter by one.

13 more elements

A method for generating tasks for a parallel processing application, comprising:

generating a plurality of threads within a parallel region of the application;
setting a counter equal to a quantity of the plurality of threads;
for each one of the plurality of threads:
assigning an implicit task;
executing the implicit task;
upon encountering a task construct, during execution of the implicit task, for an explicit task:
determining that a first task queue of a plurality of task queues is not full;
setting an execution mode of the explicit task as an explicit asynchronous task within the task construct based on the determination that the first task queue is not full;
converting at least one ancestor stack task to a heap task based on a determination that the explicit asynchronous task is descended from the at least one ancestor stack task;
generating the explicit asynchronous task;
adding the explicit asynchronous task to the first task queue,
wherein the first task queue corresponds to the one of the plurality of threads,
wherein each of the plurality of task queues corresponds to one of the plurality of threads, and
wherein the explicit asynchronous task is executed by allocating a data environment data structure for the explicit asynchronous task on a heap of a host routine;
and
incrementing the counter by one.

13 more elements

Dependencies are inferred from the claim text.

Description4,217 words

Summary515 words

#A typical computer system includes hardware and software. The hardware includes at least one processing device that executes instructions defined by the software (i.e., an application). The processing device may be a processor, a micro-core on a multi-core processor, or other such device that can process instructions. Often a computer system may include multiple processing devices that execute the application(s) in parallel. For example, multiple processors and/or multiple micro-cores may execute in parallel. Parallel execution may shorten the amount of time required to process the instructions of the application. Thus, parallel applications, or applications developed to be executed in parallel, tend to execute faster than applications that execute serially.

#One Application Program Interface (API) that may be used to develop parallel applications is OpenMP. The OpenMP API supports multi-platform shared-memory parallel programming in C/C++ and Fortran on various processor architectures. Further, the OpenMP API includes compiler directives, library routines, and environment variables that influence run-time behavior.

#In general, in one aspect, the invention relates to a system including a processor, a physical memory, and a computer usable storage medium having computer readable program code embodied therein. The computer readable program code is adapted to, when executed by the processor, implement a method for generating tasks for a parallel processing application. The method includes generating threads within a parallel region of the application, and setting a counter equal to the quantity of the threads. The method also includes, for each one of the plurality of threads, assigning an implicit task, and executing the implicit task. Further, the method includes, upon encountering a task construct, during execution of the implicit tack, for an explicit asynchronous task: generating the explicit asynchronous task, adding the explicit asynchronous task to a first task queue, where the first task queue corresponds to the one of the plurality of threads, and incrementing the counter by one.

Brief description of the drawings6 figures

#FIG. 1 shows a block diagram of the compilation of an OpenMP program, in accordance with embodiments of the invention.

#FIG. 2 shows a diagram of the execution of an OpenMP program, in accordance with embodiments of the invention.

#FIG. 3 shows a diagram of a OpenMP runtime environment, in accordance with embodiments of the invention.

Detailed description3,583 words

#Specific embodiments of the invention will now be described in detail with reference to the accompanying Figs. Like elements in the various Figs. are denoted by like reference numerals for consistency.

#In the following detailed description of embodiments of the invention, numerous specific details are set forth in order to provide a more thorough understanding of the invention. However, it will be apparent to one of ordinary skill in the art that the invention may be practiced without these specific details. In other instances, well-known features have not been described in detail to avoid unnecessarily complicating the description.

#Those skilled in the art will appreciate that while the invention is described with respect to OpenMP, the invention is not limited to OpenMP implementations.

Facts

Application

12/495,403Filed 30 Jun 2009

Published

US 2010/0333091 A130 Dec 2010

Granted

16 Dec 2014

Term ends

14 Nov 2031

Estimated · how

20 years from earliest known nonprovisional domestic filing plus recorded patent term adjustment, including 867 days of adjustment. Maintenance-fee lapses, terminal disclaimers and statutory extensions have not been checked. The continuity chain may be incomplete; this is not an enforceability determination.

Classification4 codes

G06F 8/314
Programming languages or programming paradigms: parallel programming languages
G06F 9/4843
Task transfer initiation or dispatching: by program, e.g. task dispatcher, supervisor, operating system
G06F 9/522
Program synchronisation; Mutual exclusion, e.g. by means of semaphores: barrier synchronisation
G06F
Computing and data processing

Timeline

30 Jun 2009Application filedUS 12/495,403
7 Jul 2009Assigned to Sun Microsystems, Inc.assignment of assignor's interest
30 Dec 2010PublishedUS 2010/0333091 A1
16 Dec 2014GrantedUS 8,914,799 B2
12 Oct 2026TodayWithin its term
14 Nov 2031Term endsEstimated, includes 867 days of adjustment

High performance implementation of the OpenMP tasking feature

Life of this patent

High performance implementation of the OpenMP tasking feature

Life of this patent

Life of this patent

Abstract

Drawings

Drawings

Claims20

Description4,217 words

Drawings

Classification4 codes

Life of this patent

Description4,217 words