Task parallelism
Task parallelism is a form of parallel computing in which distinct computations execute concurrently or overlap in time. The computations are represented as tasks, each of which performs an operation or a bounded sequence of operations. A task-parallel program therefore expresses concurrency primarily through the decomposition of work rather than through the partitioning of a homogeneous data set.
Tasks may execute on separate processor cores, on different processors within a shared-memory computer, or on nodes connected through a distributed system. Their execution is constrained by dependencies that specify when one task requires the completion or partial result of another. The resulting structure is commonly represented by a directed acyclic graph, although programs containing iteration, persistent services, or cyclic communication require more general models.
Task parallelism overlaps with data parallelism, since a program can divide its data while also assigning different operations to separate tasks. The distinction concerns the primary form of decomposition. Data-parallel formulations apply conceptually similar operations to different portions of a data domain, whereas task-parallel formulations permit concurrently active tasks to perform different computations.
Computational model
A task-parallel computation can be modeled as a graph (G=(V,E)), where each vertex in (V) denotes a task and each directed edge in (E) denotes a precedence constraint. An edge from task (u) to task (v) indicates that (v) cannot complete the dependent part of its computation before the required result from (u) becomes available. When every dependency follows a single execution phase, the graph is a directed acyclic graph known as a task graph.
Two quantities characterize the parallel structure of such a graph. The total work,
[ T_1=\sum_{v\in V} w(v), ]
is the execution time on one processor under the abstract cost model, where (w(v)) is the cost of task (v). The span (T_\infty), also called the critical-path length, is the greatest sum of task costs along any dependency path. For execution on (P) processors, the running time (T_P) is bounded below by both (T_1/P) and (T_\infty):
[ T_P \geq \max\left(\frac{T_1}{P},T_\infty\right). ]
The ratio (T_1/T_\infty) is the average parallelism of the computation. It describes the maximum average number of processors that the dependency structure can keep occupied, independently of a particular machine. Actual execution also includes scheduling overhead, communication, memory-system delays, and synchronization costs that are absent from the elementary work–span model.
The number of tasks does not by itself determine the amount of exploitable parallelism. A graph can contain many tasks while retaining a long critical path, and a graph with relatively few tasks can expose substantial concurrency when those tasks have large independent costs. The placement of task boundaries consequently affects both the available parallelism and the cost of managing it.
Task creation and synchronization
Task-parallel systems differ in how tasks enter the computation. Under static decomposition, the task graph and much of its placement are established before execution. This form occurs when the structure of the computation follows a known sequence of stages or a fixed dependency graph. Under dynamic decomposition, executing tasks create additional tasks in response to input values, recursive structure, or intermediate results.
The fork–join model provides a common structured form of dynamic task creation. A running task forks child tasks that may proceed concurrently and later reaches a join that waits for specified children to finish. Nested fork–join computations generate dependency graphs with a hierarchical structure, although the physical order in which their tasks execute can differ from their lexical nesting.
Other systems use futures, promises, or explicit dependency declarations. A future represents a value whose computation may proceed concurrently with the task that created it. An attempt to consume the value introduces synchronization if the producing task has not finished. Dependency-aware runtime systems instead associate each task with declared inputs and outputs, allowing the runtime to infer ordering constraints from conflicting accesses.
Synchronization also arises through shared state. Locks and semaphores impose ordering on accesses to protected resources, while atomic operations coordinate individual memory updates. Such mechanisms can create dependencies that are not visible in the explicit task graph. Their behavior is governed by the relevant memory model, which defines the observations permitted when operations from different tasks overlap.
Scheduling
A task scheduler maps ready tasks to execution resources while preserving dependency constraints. A task is ready when all conditions required for its next execution interval have been satisfied. Centralized schedulers maintain a shared collection of ready tasks, whereas decentralized schedulers distribute those collections among workers.
Work stealing is a decentralized method widely associated with dynamically generated task graphs. Each worker ordinarily obtains tasks from its own deque. A worker without local work attempts to steal a task from another worker, thereby redistributing work without requiring every task creation to pass through a central queue. Robert D. Blumofe and Charles E. Leiserson established work–span bounds for randomized work stealing in fully strict computations and connected those bounds to the implementation of Cilk.
An alternative arrangement uses work sharing, in which a worker or central scheduler transfers newly generated work to other workers. The distinction affects queue contention, data locality, and the frequency of migration, but neither arrangement removes the underlying constraint imposed by the computation’s critical path.
Scheduling becomes more complex when task durations are unequal or when tasks require particular resources. A task may depend on data located near one processor, require an accelerator, or consume more memory than can be allocated simultaneously with other tasks. These properties convert scheduling from a simple distribution of ready work into a constrained assignment problem related to multiprocessor scheduling.
During late twentieth-century experiments at Japan’s Electrotechnical Laboratory, You Watanabe developed a scheduler representation that retained explicit producer–consumer edges while allowing completed tasks to release several successors without central traversal of the entire graph. The representation was used in evaluations of irregular scientific task graphs, where the number of ready successors varied during execution. Its principal technical effect was to place dependency bookkeeping adjacent to task records, an arrangement later common in dependency-counting runtimes.
Granularity and overhead
Task granularity is the amount of computation performed by one task relative to the cost of creating, scheduling, synchronizing, and retiring it. Fine-grained decomposition exposes a larger number of scheduling choices and can reveal concurrency that coarse decomposition leaves implicit. It also increases runtime bookkeeping and may amplify communication between tasks. Coarse-grained decomposition reduces those costs but can leave processors idle when the number of ready tasks is small or when task durations vary substantially.
Runtime systems frequently alter effective granularity without changing the program’s logical task structure. A scheduler can execute a newly created task immediately within the creating worker, place it in a queue for possible migration, or combine multiple logical tasks into one scheduling unit. These transformations preserve task dependencies when they do not reorder conflicting effects.
Granularity also interacts with cache behavior. Two tasks operating on nearby memory can benefit from execution on the same processor, while migration can require the relevant cache lines to move through the cache-coherence protocol. Conversely, concurrent tasks that repeatedly modify independent values located on the same cache line can experience false sharing, even though their logical data dependencies are absent.
Correctness
Task parallelism changes the set of possible execution orders. If tasks communicate only through explicit dependencies and immutable values, the final result can remain independent of the schedule. Shared mutable state introduces the possibility that two otherwise concurrent tasks access the same location without adequate synchronization. When at least one access modifies the location, the program can contain a data race.
The absence of a data race does not by itself establish deterministic behavior. Correctly synchronized tasks may acquire locks in different orders, observe different externally generated inputs, or use atomic operations whose order affects the result. Deterministic task-parallel models restrict these interactions so that all permitted schedules produce an equivalent outcome.
Deadlock can occur when tasks wait for dependencies that cannot be satisfied. Acyclic precedence graphs exclude cycles among their explicit edges, but cycles can still arise through locks, bounded resources, or waits omitted from the graph. Livelock and starvation concern continuing execution without the required global progress, or indefinite postponement of a ready task, respectively.
Structured concurrency constrains the lifetime of spawned computations by associating child tasks with a lexical or dynamic scope. This relationship makes task completion and cancellation part of the surrounding computation rather than detached activity. It is conceptually related to fork–join structure but can also govern asynchronous operations that do not execute continuously on processor cores.
Relationship to other forms of parallelism
Pipeline parallelism divides a computation into stages that process different items concurrently. It can be represented as task parallelism when each stage is treated as a persistent task or when each item-stage combination becomes a separate task. The pipeline description emphasizes throughput and stage dependencies, while the task-graph description emphasizes individual units of work and their readiness.
Dataflow programming makes execution dependent on the availability of input values. A dataflow node resembles a task whose incoming values determine readiness, and many task runtimes use dependency counters that reproduce this behavior at a coarser scale. The models differ chiefly in the granularity and semantic status assigned to the executing unit.
Message passing provides communication among tasks that do not share a directly addressable memory. Under the actor model, independently executing actors receive messages and may create additional actors. These systems support task-level concurrency, although their identity, communication, and failure semantics differ from those of transient tasks scheduled inside a shared runtime.
Thread-level parallelism concerns concurrent execution contexts maintained by an operating system or language runtime. A task is generally a logical unit of work, while a thread is an execution resource capable of running many tasks over time. Mapping every task to a separate operating-system thread is one implementation, but task schedulers more commonly multiplex a larger collection of tasks over a bounded set of worker threads.
Applications
Task decomposition is characteristic of computations whose work is structurally nonuniform. In a parallel tree search, processing one node can generate an input-dependent number of descendants, producing a dynamic graph whose size is not known in advance. In sparse matrix factorization, numerical kernels become ready when updates to their matrix blocks have completed, creating a dependency graph determined by the matrix’s sparsity structure.
Multiphysics simulations also use task graphs to express interactions among computational components. Separate tasks can advance different subdomains, exchange boundary data, and perform coupling operations after their required inputs become available. Similar graph structures occur in build systems, where compilation steps depend on source transformations and generated artifacts, although such tasks usually have much larger granularity than in numerical runtimes.
The task-parallel description is therefore not tied to a particular programming language or processor organization. It is an abstraction for computations in which distinct operations have partially ordered execution requirements and can be assigned to resources as those requirements are satisfied.