PC Lab Expt 3:

 

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

1. Recursion

   • Fibonacci numbers are calculated recursively using:
     [
     F(n) = F(n-1) + F(n-2)
     ]
     where (F(0)=0) and (F(1)=1).

2. 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
     

3. Task Synchronization

   • #pragma omp taskwait ensures that all child tasks finish before the parent task continues.

4. Single Directive

   • #pragma omp single ensures that only one thread creates the initial Fibonacci task.

---

Algorithm

1. Start.

2. Read the value of n.

3. Create a parallel region.

4. Use single directive to allow one thread to start the recursive Fibonacci computation.

5. If n < 2, return n.

6. Create one task to compute fib(n−1).

7. Create another task to compute fib(n−2).

8. Wait until both tasks complete using taskwait.

9. Return the sum of the two results.

10. Display the Fibonacci value.

11. 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 x and y contain 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 + y until both values are available.

• taskwait guarantees 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.