Program 3: Calculate Fibonacci Numbers Using OpenMP Tasks
Objective
To compute the Nth Fibonacci number using OpenMP tasks, where recursive function calls are executed as parallel tasks.
Prerequisites
Recursion
Fibonacci numbers are calculated recursively using:
[
F(n) = F(n-1) + F(n-2)
]
where (F(0)=0) and (F(1)=1).
OpenMP Tasks
A task is an independent unit of work that can be executed by any available thread.
Tasks are created using:
#pragma omp task
Task Synchronization
#pragma omp taskwaitensures that all child tasks finish before the parent task continues.
Single Directive
#pragma omp singleensures that only one thread creates the initial Fibonacci task.
Algorithm
Start.
Read the value of n.
Create a parallel region.
Use
singledirective to allow one thread to start the recursive Fibonacci computation.If n < 2, return n.
Create one task to compute fib(n−1).
Create another task to compute fib(n−2).
Wait until both tasks complete using
taskwait.Return the sum of the two results.
Display the Fibonacci value.
Stop.
Program
#include <stdio.h>
#include <omp.h>
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;
}
int main() {
int n, result;
printf("Enter value of n: ");
scanf("%d", &n);
#pragma omp parallel
{
#pragma omp single
result = fib(n);
}
printf("Fibonacci(%d) = %d\n", n, result);
return 0;
}
Sample Input
Enter value of n: 10
Sample Output
Fibonacci(10) = 55
Other Possible Outputs
Input: 5
Enter value of n: 5
Fibonacci(5) = 5
Input: 6
Enter value of n: 6
Fibonacci(6) = 8
Input: 8
Enter value of n: 8
Fibonacci(8) = 21
Input: 12
Enter value of n: 12
Fibonacci(12) = 144
Result
The program successfully computes the Nth Fibonacci number using OpenMP tasks. Independent recursive calls are executed as separate tasks, and taskwait synchronizes them before combining their results, demonstrating task-based parallelism in OpenMP.
Explanation of OpenMP Task Directives (Connected to the Problem Statement)
Problem Statement:
Write an OpenMP program to calculate the Nth Fibonacci number using tasks.
The Fibonacci sequence is defined as:
[
F(n) = F(n-1) + F(n-2)
]
To compute F(n), the program must calculate F(n−1) and F(n−2). These two calculations are independent, so they can be performed simultaneously using OpenMP tasks.
1. #pragma omp task shared(x)
#pragma omp task shared(x)
x = fib(n - 1);
Explanation:
Creates a new task to compute the Fibonacci value of n−1.
Any available thread in the OpenMP thread team can execute this task.
The computed result is stored in the shared variable
x.
Connection to the problem:
While calculating F(n), one independent subproblem is F(n−1).
Instead of waiting for it to finish sequentially, OpenMP executes it as a separate task.
2. #pragma omp task shared(y)
#pragma omp task shared(y)
y = fib(n - 2);
Explanation:
Creates another independent task to compute F(n−2).
This task can execute concurrently with the task computing F(n−1).
The result is stored in the shared variable
y.
Connection to the problem:
The second independent subproblem, F(n−2), is also executed in parallel.
Since F(n−1) and F(n−2) do not depend on each other, they are ideal candidates for task-based parallelism.
3. #pragma omp taskwait
#pragma omp taskwait
Explanation:
Suspends the current task until all child tasks created by it have completed.
Ensures that both
xandycontain valid results before they are added.
Connection to the problem:
The Fibonacci formula is:
[
F(n) = F(n-1) + F(n-2)
]The program cannot compute
x + yuntil both values are available.taskwaitguarantees that the calculations of F(n−1) and F(n−2) are finished before returning the final Fibonacci value.
Working Example (n = 5)
fib(5)
├── Task 1 → fib(4)
└── Task 2 → fib(3)
↓
taskwait
↓
Return fib(4) + fib(3)
Task 1: Computes fib(4) and stores the result in
x.Task 2: Computes fib(3) and stores the result in
y.taskwait: Waits until both tasks finish.Final Result: Returns
x + y = 3 + 2 = 5.
Summary
| OpenMP Directive | Purpose | Role in Fibonacci Problem |
|---|---|---|
#pragma omp task shared(x) | Creates a task to compute fib(n-1) | Computes the first recursive subproblem in parallel |
#pragma omp task shared(y) | Creates a task to compute fib(n-2) | Computes the second recursive subproblem in parallel |
#pragma omp taskwait | Waits for all child tasks to complete | Ensures both results are available before calculating fib(n) = x + y |
Key Idea: The Fibonacci problem naturally breaks into two independent recursive computations (fib(n−1) and fib(n−2)). OpenMP tasks execute these computations concurrently, and taskwait synchronizes them before combining their results.
