1)Write a Open MP program to sort an array on n elements
using both sequential and parallel merge sort (using
Section). Record the difference in execution time.
#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
void merge(int arr[], int l, int m, int r) {
int i = l, j = m + 1, k = 0;
int temp[r - l + 1];
while (i <= m && j <= r) {
if (arr[i] <= arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
while (i <= m) temp[k++] = arr[i++];
while (j <= r) temp[k++] = arr[j++];
for (i = l, k = 0; i <= r; i++, k++)
arr[i] = temp[k];
}
void sequentialMergeSort(int arr[], int l, int r) {
if (l < r) {
int m = (l + r) / 2;
sequentialMergeSort(arr, l, m);
sequentialMergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
void parallelMergeSort(int arr[], int l, int r) {
if (l < r) {
int m = (l + r) / 2;
#pragma omp parallel sections
{
#pragma omp section
parallelMergeSort(arr, l, m);
#pragma omp section
parallelMergeSort(arr, m + 1, r);
}
merge(arr, l, m, r);
}
}
int main() {
int n = 100000;
int arr1[n], arr2[n];
for (int i = 0; i < n; i++) {
arr1[i] = rand() % 1000;
arr2[i] = arr1[i];
}
double start, end;
start = omp_get_wtime();
sequentialMergeSort(arr1, 0, n - 1);
end = omp_get_wtime();
printf("Sequential Merge Sort Time: %f seconds\n", end - start);
start = omp_get_wtime();
parallelMergeSort(arr2, 0, n - 1);
end = omp_get_wtime();
printf("Parallel Merge Sort Time: %f seconds\n", end - start);
return 0;
}
OUTPUT
==========Case 1: Array Size = 1000 ========
Serial Merge Sort Time: 0.004405 sec
Parallel Merge Sort Time: 0.000428 sec
=========== Case 2: Array Size = 10000 ========
Serial Merge Sort Time: 0.001092 sec
Parallel Merge Sort Time: 0.000733 sec
=========== Case 3: Array Size = 100000 ========
Serial Merge Sort Time: 0.205361 sec
Parallel Merge Sort Time: 0.006890 sec
2). Write a Open MP program that divides the Iteration into
chunks containing 2 iterations, respectively
(OMP_SCHEDULE=static, 2). Its input should be the number of
iteration, and its output should be which iterations of a
parallelized for loops are executed by which thread.
For example, if there are two threads and four iterations, the output
might be the following:
a. Thread 0 : Iteration 0 – 1
b. Thread 1: Iteration 2 – 3
#include <stdio.h>
#include <omp.h>
int main()
{
int n = 16, thread;
printf("\n Enter the number of tasks");
scanf("%d", &n);
printf("\n Enter the number of threads");
scanf("%d", &thread);
omp_set_num_threads(thread);
printf("\n----------------------------\n");
int i; // Declare loop variable outside
#pragma omp parallel for schedule(static, 2)
for(i = 0; i < n; i++)
{
printf("Thread %d executes iteration %d\n", omp_get_thread_num(),
i);
}
return 0;
}
OUTPUT
Enter the number of tasks 24
Enter the number of threads 12
Thread 4 executes iteration 8
Thread 4 executes iteration 9
Thread 0 executes iteration 0
Thread 0 executes iteration 1
Thread 5 executes iteration 10
Thread 5 executes iteration 11
Thread 3 executes iteration 6
Thread 3 executes iteration 7
Thread 2 executes iteration 4
Thread 2 executes iteration 5
Thread 11 executes iteration 22
Thread 11 executes iteration 23
Thread 6 executes iteration 12
Thread 6 executes iteration 13
Thread 10 executes iteration 20
Thread 10 executes iteration 21
Thread 8 executes iteration 16
Thread 8 executes iteration 17
Thread 9 executes iteration 18
Thread 9 executes iteration 19
Thread 7 executes iteration 14
Thread 7 executes iteration 15
Thread 1 executes iteration 2
Thread 1 executes iteration 3
3). Write a Open MP program to calculate n Fibonacci numbers
using tasks.
#include <stdio.h>
#include <omp.h>
int fib(int n) {
int x, y;
if (n < 2)
return n;
#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;
printf("Enter number of Fibonacci terms: ");
scanf("%d", &n);
printf("Fibonacci Series:\n");
for (int i = 0; i < n; i++) {
int result;
#pragma omp parallel
{
#pragma omp single
{
result = fib(i);
}
}
printf("%d ", result);
}
printf("\n");
return 0;
}
OUTPUT
Enter the value of n: 32
Fibonacci (32) = 2178309
The time used to execute the program in parallel mode = 0.294209 seconds
Fibonacci (32) = 2178309
The time used to execute the program in parallel mode = 0.130700 seconds
4). Write a Open MP program to find the prime numbers from 1
to n employing parallel for directive. Record both serial and
parallel execution times.
#include <stdio.h>
#include <math.h>
#include <omp.h>
int is_prime(int num) {
if (num < 2) return 0;
for (int i = 2; i <= sqrt(num); i++) {
if (num % i == 0)
return 0;
return 1;
int main() {
int n;
printf("Enter the value of n: ");
scanf("%d", &n);
printf("\nPrime numbers from 1 to %d:\n", n);
for (int i = 1; i <= n; i++) {
if (is_prime(i))
printf("%d ", i);
printf("\n");
double start_time, end_time;
start_time = omp_get_wtime();
for (int i = 1; i <= n; i++) {
is_prime(i);
end_time = omp_get_wtime();
printf("Serial Time: %f seconds\n", end_time - start_time);
start_time = omp_get_wtime();
#pragma omp parallel for
for (int i = 1; i <= n; i++) {
is_prime(i);
end_time = omp_get_wtime();
printf("Parallel Time: %f seconds\n", end_time - start_time);
return 0;
OUTPUT
Prime numbers from 1 to 200:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157,
163, 167, 173, 179, 181, 191, 193, 197, 199
Serial Time: 0.000004 seconds
Parallel Time: 0.000633 seconds
