task scheduling parallel
**Parallel Task Scheduling** is the **algorithmic problem of assigning computational tasks to processing elements (cores, threads, GPUs) to maximize throughput, minimize completion time, and balance load** — a fundamental challenge because optimal scheduling is NP-hard in general, requiring practical heuristics that balance computational overhead, load balance, data locality, and communication costs in real parallel systems.
**Scheduling Taxonomy**
| Type | When Assigned | Overhead | Balance | Best For |
|------|-------------|----------|---------|----------|
| Static | Before execution | Zero runtime | Poor (if tasks uneven) | Regular, predictable workloads |
| Dynamic | During execution | Runtime overhead | Good | Irregular, unpredictable workloads |
| Guided | Hybrid (decreasing chunks) | Medium | Good | Mixed regularity |
| Adaptive | Feedback-driven | Higher | Best | Heterogeneous systems |
**Static Scheduling**
- Tasks divided evenly at compile/launch time.
- OpenMP: `#pragma omp parallel for schedule(static)`
- Chunk size = N/P (N iterations, P threads). Thread 0 gets iterations 0..N/P-1, etc.
- **Pros**: Zero overhead, excellent cache locality (each thread always processes same data region).
- **Cons**: Disastrous if tasks have different durations → fast threads idle while slow threads still working.
**Dynamic Scheduling**
- Tasks distributed from a shared queue at runtime — each thread takes next available task.
- OpenMP: `#pragma omp parallel for schedule(dynamic, chunk_size)`
- **Pros**: Perfect load balance — no thread idles while work remains.
- **Cons**: Queue contention overhead, poor cache locality (each thread processes different data each time).
**Guided Scheduling**
- Start with large chunks (reduces overhead) → progressively smaller chunks (improves balance).
- Chunk size = remaining_iterations / num_threads (decreasing).
- OpenMP: `#pragma omp parallel for schedule(guided)`
- Best tradeoff for many workloads.
**Work Stealing (Advanced Dynamic)**
- Each thread has own local deque (double-ended queue) of tasks.
- When local deque empty → **steal** from another thread's deque (from the bottom/oldest).
- **Pros**: Low contention (steal is rare), good locality (mostly process own tasks).
- **Used by**: Intel TBB, Java ForkJoinPool, Cilk, Tokio (Rust).
**DAG Scheduling (Task Graphs)**
- Tasks have dependencies forming a DAG (Directed Acyclic Graph).
- Scheduler must respect dependencies while maximizing parallelism.
- **Critical path**: Longest chain of dependent tasks — determines minimum completion time.
- **Priority scheduling**: Assign priority = distance to end of critical path → schedule highest priority first.
**GPU Task Scheduling**
- GPU kernel launch: Blocks scheduled to SMs by hardware scheduler.
- **Persistent kernels**: Launch one kernel that loops fetching work → avoids kernel launch overhead.
- **CUDA Dynamic Parallelism**: Kernels launch child kernels → recursive task decomposition on GPU.
Parallel task scheduling is **the runtime foundation that determines whether parallel hardware is used efficiently** — even the fastest parallel algorithm performs poorly with bad scheduling, making the choice of scheduling strategy one of the most impactful decisions in parallel system design.