STRUCTURED TASK HIERARCHY FOR A PARALLEL RUNTIME

• US 20110078691A1
• Filed: 09/30/2009
• Published: 03/31/2011
• Est. Priority Date: 09/30/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Yildiz, Huseyin S., Duffy, John J., Toub, Stephen H.
• Granted Patent: US 8,250,576 B2
• Time in Patent Office: Days
• US Class Current: 718/103
• CPC Class Codes: G06F 2209/481 Exception handling
• CPC Class Codes: G06F 9/461 Saving or restoring of program or task context
• CPC Class Codes: G06F 9/4812 by interrupt, e.g. masked

Abstract

The present invention extends to methods, systems, and computer program products for a structured task hierarchy for a parallel runtime. The parallel execution runtime environment permits flexible spawning and attachment of tasks to one another to form a task hierarchy. Parent tasks can be prevented from completing until any attached child sub-tasks complete. Exceptions can be aggregated in an exception array such that any aggregated exceptions for a task are available when the task completes. A shield mode is provided to prevent tasks from attaching to another task as child tasks.

Claims

1. At a computer system including one or more processors and system memory, a method for executing code in accordance with a task directed acyclic graph that divides processing into tasks, the method comprising:

an act of initiating execution of a task included in the task directed acyclic graph;

an act of spawning a plurality of concurrently executable sub-tasks during the time the task is executing, each sub-task configured to perform an indicated portion of work related to the task;

for at least one of the plurality of concurrently executable sub-tasks;

an act of attaching the sub-task as a child task of the task within the task directed acyclic graph such that the task is also the parent task of the sub-task task within the task directed acyclic graph;

an act of grouping the sub-task with any other sub-tasks attached to the task within the context of the task; and

an act of preventing completion of the task until the attached sub-task is complete;

an act of a multi-core processor concurrently executing each of the plurality of concurrently executable sub-tasks to perform the indicated portions of work related to the task, each of the plurality of concurrently executable sub-tasks concurrently executed with at least one other task at the computer system; and

upon detecting that all attached sub-tasks have completed, an act of permitting the task to complete.

2. The method as recited in claim 1, further comprising for at least one of the plurality of concurrently executable sub-tasks, an act of setting the value of a shielded task flag to a value that prevents other tasks from attaching as a child task to the at least one sub-task.

3. The method as recited in claim 1, wherein the act of initiating execution of a task included in the task directed acyclic graph comprises an act of initiating a task that is a root task in a task hierarchy.

4. The method as recited in claim 1, wherein the act of initiating execution of a task included in the task directed acyclic graph comprises an act of initiating a task that is a child task of another task in a task hierarchy.

5. The method as recited in claim 1, wherein the act of spawning a plurality of concurrently executable sub-tasks during the time the task is executing comprises an act of another different task spawning a sub-task included in the plurality of concurrently executable sub-tasks, the other different task being different than the task.

6. The method as recited in claim 5, wherein the act of attaching the sub-task as a child task of the task within the task directed acyclic graph comprises an act of attaching the sub-task spawned by the other different task as a child task of the task.

7. The method as recited in claim 1, wherein an act of grouping the sub-task with any other sub-tasks attached to the task within the context of the task comprises an act of grouping the sub-task with other sub-tasks based on the value of a parent task pointer for the sub-tasks and the other sub-tasks.

8. The method as recited in claim 1, further comprising an act of the task'"'"'s delegate terminating successfully.

9. The method as recited in claim 8, wherein the act of task'"'"'s delegate terminating successfully comprises act of task'"'"'s delegate terminating successfully subsequent to completion all attached sub-tasks;

and further comprising;

an act of the task transitioning the task to a completed state.

10. The method as recited in claim 8, wherein the act of parent task'"'"'s delegate terminating successfully comprises act of parent task'"'"'s delegate terminating successfully prior to completion all attached sub-tasks;

and further comprising;

an act of yielding control of the task'"'"'s thread to the non-completed sub-tasks; and

an act of the last sub-task to complete transitioning the task to a completed state.

11. The method as recited in claim 1, further comprising upon detecting that all attached sub-tasks have completed, an act of unblocking any threads that may have previously blocked by the tasks wait Application Program Interface (“

API”

).

16. The method as recited in claim 11, further comprising an act of one or more of the plurality of spawned concurrently executable sub-tasks attaching to the task as a child task of the task.

17. The method as recited in claim 11, wherein the act of aggregating any remaining exceptions not observed by the task into the exception array comprises an act of aggregating any remaining exceptions into a multi-level exception array that mirrors the levels of the task directed acyclic graph.

18. The method as recited in claim 11, further comprising:

an act of the task observing one or more exceptions previously stored in the exception array by other tasks; and

an act of removing the observed exceptions from the exception array.

19. The method as recited in claim 11, wherein the act of aggregating remaining exceptions not observed by the task into the exception array comprises an act of aggregating one of:

all remaining exceptions into the exception array or any remaining exceptions into the exception array.

12. At a computer system including one or more processors and system memory, a method for marshaling exceptions for code executed in accordance with a task directed acyclic graph that divides processing into tasks, the method comprising:

an act of a portion of the code joining with execution of a task included in the task directed acyclic graph;

an act of maintaining a state object providing context for the task, the state object including an exception array for storing exceptions thrown by any child sub-tasks of the task;

an act of spawning a plurality of concurrently executable sub-tasks during execution of the task, each sub-task configured to perform an indicated portion of work related to the task;

an act of a multi-core processor concurrently executing the plurality of concurrently executable sub-tasks to perform the portions of work related to the task;

an act of the task receiving a plurality of exceptions thrown by a subset of the plurality of concurrently executable sub-tasks;

an act of the task observing at least some of the plurality of exceptions within the context of the task provided by the state object;

an act of aggregating remaining exceptions not observed by the task into the exception array; and

an act of providing the remaining exceptions in the exception array to the portion of code that joined with execution of the task.

13. The method as recited in claim 12, wherein an act of a portion of the code joining with execution of a task included in the task directed acyclic graph comprises an act of another task above the task in a task hierarchy spawning the task.

14. The method as recited in claim 12, wherein the act of maintaining a state object comprising an act of maintain a state object that includes an exception array and one or more of the following:

a current task reference, a parent task pointer, a complete countdown, an exceptional child task array, and a shielded task flag.

15. The method as recited in claim 14, wherein the act of maintaining a state object comprises an act of maintaining a state object that includes a shielded flag, the value of the shield flag indicating that other tasks are permitted to attach to the task as child tasks.

20. A computer system comprising:

a multi-core processor;

system memory; and

one or more computer storage media having stored thereon computer executable instructions representing a parallel execution runtime, the parallel execution runtime configured to;

initiate execution of a task included in the task hierarchy, a state object providing context for the task;

spawn a plurality of concurrently executable sub-tasks during the time the task is executing, each sub-task configured to perform an indicated portion of work related to the task;

attach a subset, but not all, of the plurality of concurrently executable sub-tasks to the task as a child task of the task;

prevent completion of the task until the attached subset of sub-tasks complete so that exceptions for the attached sub-tasks can be appropriately aggregated;

concurrently execute each of the plurality of concurrently executable sub-tasks to perform the indicated portions of work related to the task, each of the plurality of concurrently executable sub-tasks concurrently executed with at least one other task at the computer system;

receive a plurality of exceptions thrown by the subset of sub-tasks;

observe at least some of the plurality of exceptions within the context of the task provided by the state object;

aggregate any remaining exceptions not observed by the task into the exception array;

provide the remaining exceptions in the exception array to the portion of code that joined with execution of the task; and

upon detecting that all attached sub-tasks in the subset of sub-task have completed, permit the task to complete.