System and method for implementing constrained data-driven parallelism

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:
• executing a given task in a data-driven computation, wherein said executing comprises spawning one or more other tasks in response to one or more respective trigger conditions for the data-driven computation being met, wherein each trigger condition identifies a particular memory location and wherein the trigger condition is met in response to the particular memory location being modified;
• for each of the spawned tasks:
• determining whether to schedule the spawned task for execution or defer execution of the spawned task;
• placing the spawned task in a pool of tasks to be executed or in a pool of tasks for which execution is deferred, dependent on said determining whether to schedule the spawned task for execution or defer execution of the spawned task;
• in response to determining that at least one of the spawned tasks is to be scheduled for execution:
• executing a subset of the spawned tasks, wherein the subset comprises all of the spawned tasks that were scheduled for execution;
• in response to determining that execution of at least one of the spawned tasks is to be deferred:
• executing, subsequent to completing said executing the subset of the spawned tasks, another subset of the spawned tasks, wherein the other subset comprises one or more spawned tasks for which execution was deferred;
• wherein at least one of said executing the subset of spawned tasks or said executing the other subset of spawned tasks is performed by a thread that placed the spawned tasks in the pools and by one or more other threads according to a work-stealing policy.

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:

• executing a given task in a data-driven computation, wherein said executing comprises spawning one or more other tasks in response to one or more respective trigger conditions for the data-driven computation being met, wherein each trigger condition identifies a particular memory location and wherein the trigger condition is met in response to the particular memory location being modified;
• for each of the spawned tasks:
• determining whether to schedule the spawned task for execution or defer execution of the spawned task;
• creating a task group comprising:
• the given task;
• a subset of spawned tasks comprising spawned tasks scheduled for execution;
• and
• another subset of spawned tasks comprising spawned tasks for which execution was deferred;
• wherein said creating comprises executing an operation that blocks execution of a task that initiated execution of the given task until execution of all tasks that are added to the task group subsequent to adding the given task to the task group has been completed;
• executing in response to determining that at least one of the spawned tasks is to be scheduled for execution, the subset of the spawned tasks;
• executing, in response to determining that execution of at least one of the spawned tasks is to be deferred and subsequent to completing said executing the subset of the spawned tasks, the other subset of the spawned tasks;
• and
• beginning execution, subsequent to completing execution of the tasks that were added to the task group subsequent to adding the given task to the task group, of one or more tasks in another task group.