OpenMP Tasking is an OpenMP programming model extension that expresses irregular parallelism by creating explicit tasks with dependency annotations — complementing loop-based parallelism for recursive algorithms, unstructured graphs, and producer-consumer patterns.

Why OpenMP Tasks?

• OpenMP parallel for: Excellent for regular loops over independent iterations.
• Limitation: Recursive algorithms (quicksort, tree traversal), pipeline stages, irregular graphs cannot be expressed as simple loops.
• Tasks: Create work items that the runtime schedules dynamically.

Basic Task Creation

#pragma omp parallel
#pragma omp single  // Only one thread creates tasks
{
    #pragma omp task
    { compute_A(); }     // Task A created
    
    #pragma omp task
    { compute_B(); }     // Task B created (may run in parallel with A)
    
    #pragma omp taskwait  // Wait for all tasks to complete
    compute_C();           // Sequential after A and B
}

Task Dependencies (OpenMP 4.0+)

#pragma omp task depend(out: data_a)
{ produce_A(data_a); }         // Task A writes data_a

#pragma omp task depend(in: data_a)
{ consume_A(data_a); }         // Task B reads data_a — waits for A

#pragma omp task depend(in: data_a) depend(out: data_b)
{ transform(data_a, data_b); } // Task C: depends on A, enables D

Recursive Tasks (Fibonacci Example)

int fib(int n) {
    if (n < 2) return n;
    int x, y;
    #pragma omp task shared(x)
    x = fib(n-1);
    #pragma omp task shared(y)
    y = fib(n-2);
    #pragma omp taskwait
    return x + y;
}

Task Scheduling and Overhead

• Tasks are placed in a task pool; idle threads steal work.
• Task overhead: ~1–5 μs per task — coarse-grain tasks only (avoid fine-grained).
• if clause: #pragma omp task if(n>THRESHOLD) — create task only for large work items.

Task Priorities

• priority(n) clause: Higher priority tasks scheduled preferentially (OpenMP 4.5+).
• Critical tasks (path-critical) given higher priority.

OpenMP tasking is the standard approach for irregular parallelism in shared-memory programs — enabling recursive decomposition, pipeline parallelism, and dependency-aware scheduling without the complexity of explicit thread management.