Task Parallelism

Task parallelism begins with functional decomposition, where a program is broken down into distinct, independent tasks or functions. Each task represents a unique unit of work, such as reading a file, processing an image, or solving a sub-problem. This contrasts with data parallelism, where the same operation is applied to different data subsets. The key is that tasks can be heterogeneous, performing different algorithms on potentially different data structures. For example, a web server might concurrently handle tasks for request parsing, database querying, and response formatting.

The workflow of a task-parallel program is formally represented as a task graph or directed acyclic graph (DAG). In this graph:

• Nodes represent individual tasks.
• Edges represent dependencies between tasks, indicating that one task must complete before another can begin. This graph is crucial for scheduling. The critical path—the longest path through the DAG—determines the minimum possible execution time. Runtime systems use this graph to identify which tasks are ready (all dependencies satisfied) and can be scheduled for execution.

Because tasks may have unpredictable execution times, effective task parallelism relies on dynamic scheduling. A central task scheduler or a work-stealing algorithm assigns ready tasks to available processors. Work stealing is a prominent technique where idle processors (or threads) 'steal' tasks from the queues of busy processors, ensuring high utilization and automatic load balancing. This dynamic approach is essential for handling irregular workloads and maximizing throughput across heterogeneous cores, such as those in modern NPUs and CPUs.

Task parallelism is typically coarse-grained, meaning each task encapsulates a significant amount of work (e.g., processing a chunk of data, running a simulation step). This contrasts with fine-grained parallelism (like SIMD). The overhead of task creation, scheduling, and synchronization is amortized over the substantial computation within the task. This makes it suitable for orchestrating high-level components in a system, such as running inference, data preprocessing, and logging as concurrent tasks within an ML pipeline.

Correct execution requires managing dependencies between tasks. Programmers or frameworks must explicitly define precedence constraints. Synchronization primitives like barriers, futures, and promises are used to enforce these constraints. A future represents a placeholder for a result that will be computed asynchronously. The consuming task can wait for the future to become ready. This model avoids data races for shared results while allowing maximum concurrency for independent tasks.

A defining strength of task parallelism is its ability to schedule heterogeneous tasks across heterogeneous processors. Different tasks can be mapped to the most suitable processing unit (e.g., a matrix multiplication task to an NPU tensor core, a control logic task to a CPU). This is central to modern accelerator-centric architectures. The runtime system must be aware of device capabilities and data location (NUMA effects) to minimize data movement and latency when scheduling such diverse workloads.

Task parallelism is fundamental for orchestrating complex, multi-modal AI pipelines where different stages are independent tasks. A single request might trigger concurrent execution of:

• Preprocessing (image resizing, audio normalization)
• Feature extraction (running a vision model, transcribing audio)
• Post-processing (formatting results, generating summaries)

These heterogeneous tasks are dispatched to specialized hardware units (e.g., NPU for model inference, CPU for data formatting) simultaneously, drastically reducing end-to-end latency compared to sequential execution.

Modern web servers leverage task parallelism to handle incoming HTTP requests. Each user request represents an independent task that can involve:

• Database queries (fetching user data, product info)
• External API calls (payment processing, geolocation)
• Template rendering (generating the final HTML/JSON)

Frameworks like Node.js (with its event loop) and Go (with goroutines) use task-parallel models to manage thousands of concurrent connections. The server's runtime schedules these I/O-bound tasks across a thread pool, keeping cores utilized while waiting for network or disk responses.

In computational science, simulations often involve coupled but distinct physical models. Task parallelism allows different solvers to run concurrently. For example, a climate model might concurrently execute tasks for:

• Atmospheric dynamics
• Ocean circulation
• Ice sheet modeling
• Carbon cycle computation

These tasks exchange boundary condition data at synchronization points. This approach, often coordinated by workflow managers like Apache Airflow or Nextflow, maximizes resource usage on heterogeneous clusters where different tasks have varying CPU/GPU/memory requirements.

Enterprise data pipelines use task parallelism to transform and enrich streaming data. A single data event (e.g., a financial transaction) can fan out to multiple parallel processing tasks:

• Validation & Cleansing
• Fraud detection scoring
• Customer profile enrichment
• Real-time aggregation for dashboards

Stream processing frameworks like Apache Flink and Apache Storm explicitly model these pipelines as directed acyclic graphs (DAGs) of tasks. This enables low-latency processing as each independent transformation operates on its own copy of the data stream.

Robotics and autonomous vehicles rely on task parallelism to process diverse sensor inputs within strict real-time deadlines. A perception system must concurrently execute tasks for:

• LiDAR point cloud segmentation
• Camera-based object detection
• Radar signal processing
• Sensor fusion (combining results)

These tasks, each with different computational characteristics, are scheduled across dedicated processing units (GPU, NPU, DSP). The fused result is then passed to the planning task. This concurrency is critical for achieving the high-frequency update rates required for safe operation.

Modern compilers (like LLVM and GCC) and build tools (like Make, Ninja, and Bazel) are classic examples of task parallelism. The compilation of a large software project involves thousands of independent tasks:

• Parsing individual source files
• Code generation for each translation unit
• Linking object files

A build system analyzes the dependency graph between these tasks (e.g., file A.o depends on file A.c) and schedules all tasks with satisfied dependencies to run in parallel. This can lead to near-linear speedups for large projects, turning hour-long builds into minutes.

A parallel computing paradigm where the same operation is applied concurrently to different subsets of a dataset across multiple processing units. This is the dominant strategy for training neural networks.

• Key Mechanism: The model is replicated across devices (e.g., GPUs), and each device processes a different mini-batch of data. Gradients are synchronized (e.g., via All-Reduce) to update the global model.
• Example: Training a ResNet-50 model by splitting a batch of 256 images across 8 GPUs, with each GPU processing 32 images.
• Contrast with Task Parallelism: Data parallelism performs identical functions on different data, while task parallelism executes different functions, potentially on the same or different data.

A strategy that partitions a neural network's layers or stages across multiple devices, forming a processing pipeline. Different devices process different microbatches of data simultaneously to increase throughput.

• Key Mechanism: The model is split vertically by layer. While Device 2 processes layer 2 of microbatch N, Device 1 can begin processing layer 1 of microbatch N+1.
• Primary Goal: To enable the training of models that are too large to fit the memory of a single device, by splitting the model's weights and activations across devices.
• Scheduling Challenge: Requires careful management of the pipeline schedule (e.g., GPipe, 1F1B) to minimize pipeline 'bubbles' (idle time) and ensure high hardware utilization.

A broad technique for distributing the computational graph or parameters of a single neural network across multiple processors or devices. It is an umbrella term that includes tensor and pipeline parallelism.

• Core Driver: To handle models whose memory footprint (parameters, activations, optimizer states) exceeds the capacity of a single accelerator.
• Tensor Parallelism: A specific form of model parallelism that splits individual tensor operations (e.g., a large matrix multiplication) across devices. Devices must frequently communicate partial results.
• Use Case: Essential for training and inferencing with modern Large Language Models (LLMs) like GPT-4, where a single layer's weight matrix may be distributed across many devices.

A directed acyclic graph (DAG) that represents the computational workflow of a parallel program. Nodes are tasks (units of work), and edges denote data or control dependencies between them.

• Scheduling Foundation: Runtime schedulers use the task graph to determine which tasks are eligible for execution (those whose dependencies are satisfied) and to map them to available hardware resources.
• Critical Path: The longest path through this graph determines the minimum possible execution time for the entire computation. Optimizing parallel execution often involves reducing the length of the critical path.
• Frameworks: Explicit task graphs are used in systems like Apache Spark, Dask, and CUDA Graphs, while deep learning frameworks (PyTorch, TensorFlow) often generate them implicitly from the computational graph of a neural network.

A dynamic load-balancing scheduling algorithm where idle processors (or threads) take, or 'steal,' tasks from the deque (double-ended queue) of a busy processor.

• Mechanism: Each processor maintains its own ready queue of tasks. When a processor finishes its own work, it randomly selects another processor and 'steals' a task from the tail of its deque (often the largest, coarsest-grained task).
• Advantage: Provides excellent load balancing with low overhead, especially for irregular or unpredictable workloads where task execution times are not known in advance.
• Contrast with Static Scheduling: Unlike static partitioning, work stealing adapts to runtime conditions, making it resilient to variance in task duration and system load. It is a foundational scheduler in many runtime systems, including Cilk, Intel TBB, and Java's ForkJoinPool.

An execution model, notably used in GPUs, where a single instruction is issued to a warp (NVIDIA) or wavefront (AMD) of threads, each of which executes it on its own data.

• Core Concept: A hardware scheduler manages warps of threads (typically 32 threads). All threads in a warp execute the same instruction in lockstep, but on different data elements. This is the hardware mechanism that enables massive data parallelism.
• Divergence Handling: When threads within a warp take different control flow paths (e.g., an if/else statement), execution serializes for each path, with threads not on the current path masked out. This control flow divergence can significantly impact performance.
• Relation to Task Parallelism: While SIMT is optimized for data-parallel workloads, modern GPUs also support more explicit task-parallel models (e.g., CUDA Dynamic Parallelism, separate task graphs per Stream Multiprocessor) to handle irregular workloads.