1.
Write a OpenMP program to sort an array on n elements using both sequential and parallel
mergesort(using Section). Record the difference in execution time.
#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j])
arr[k++] = L[i++];
else
arr[k++] = R[j++];
}
while (i < n1)
arr[k++] = L[i++];
while (j < n2)
arr[k++] = R[j++];
}
// Sequential Merge Sort
void mergeSortSequential(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSortSequential(arr, left, mid);
mergeSortSequential(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
// Parallel Merge Sort
void mergeSortParallel(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
#pragma omp parallel sections
{
#pragma omp section
mergeSortParallel(arr, left, mid);
#pragma omp section
mergeSortParallel(arr, mid + 1, right);
}
merge(arr, left, mid, right);
}
}
int main() {
int n;
printf("Enter number of elements: ");
scanf("%d", &n);
int *arr1 = (int *)malloc(n * sizeof(int));
int *arr2 = (int *)malloc(n * sizeof(int));
printf("Enter %d elements: ", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr1[i]);
arr2[i] = arr1[i]; // Copy for parallel sorting
}
double start, end;
// Sequential Sort
start = omp_get_wtime();
mergeSortSequential(arr1, 0, n - 1);
end = omp_get_wtime();
printf("Sequential Merge Sort Time: %f seconds\n",end-start);
// Parallel Sort
start = omp_get_wtime();
mergeSortParallel(arr2, 0, n - 1);
end = omp_get_wtime();
printf("Parallel Merge Sort Time: %f seconds\n",end-start);
printf("Sorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr1[i]);
printf("\n");
free(arr1);
free(arr2);
return 0;
}
OUTPUT :
root@Mvit:~# gcc -fopenmp prog1.c
root@Mvit:~# ./[Link]
Enter number of elements: 6
Enter 6 elements: 2 9 1 5 10 4
Sequential Merge Sort Time: 0.000003 seconds
Parallel Merge Sort Time: 0.020377 seconds
Sorted array: 1 2 4 5 9 10
2. Write an OpenMP program that divides the Iterations into chunks containing 2
iterations, respectively (OMP_SCHEDULE=static,2). Its input should be the number
of iterations, and its output should be which iterations of a parallelized for loop are
executed by which thread.
For example, if there are two threads and four iterations, the output might be the
following:
a. Thread 0 : Iterations 0 – 1
b. Thread 1 : Iterations 2 −− 3
#include <stdio.h>
#include <omp.h>
int main() {
int num_iterations;
printf("Enter the number of iterations: ");
scanf("%d", &num_iterations);
#pragma omp parallel
{
#pragma omp for schedule(static,2)
for (int i = 0; i < num_iterations; i++) {
printf("Thread %d: Iteration %d\n", omp_get_thread_num(), i);
}
}
return 0;
}
OUTPUT :
root@Mvit:~# gcc -fopenmp prog2.c
root@Mvit:~# ./[Link]
Enter the number of iterations: 6
Thread 1: Iteration 2
Thread 1: Iteration 3
Thread 2: Iteration 4
Thread 2: Iteration 5
Thread 0: Iteration 0
Thread 0: Iteration 1
3. Write a OpenMP program to calculate n Fibonacci numbers using tasks.
#include <stdio.h>
#include <omp.h>
int fib(int n)
{
int i, j;
if (n<2)
return n;
else
{
#pragma omp task shared(i) firstprivate(n)
i=fib(n-1);
#pragma omp task shared(j) firstprivate(n)
j=fib(n-2);
#pragma omp taskwait
return i+j;
}
}
int main()
{
int n = 10;
omp_set_dynamic(0);
omp_set_num_threads(4);
#pragma omp parallel shared(n)
{
#pragma omp single
printf ("fib(%d) = %d\n", n, fib(n));
}
}
OUTPUT :
root@Mvit:~# gcc -fopenmp prog3.c
root@Mvit:~# ./[Link]
fib(10) = 55
4. Write a OpenMP 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 <omp.h>
int main()
{
int prime[1000], i, j, n;
// Prompt user for input
printf("\n In order to find prime numbers from 1 to n, enter the value of n:");
scanf("%d", &n);
// Initialize all numbers as prime (set all to 1)
for(i = 1; i <= n; i++) {
prime[i] = 1;
}
// 1 is not a prime number
prime[1] = 0;
// Sieve of Eratosthenes with parallelization
for(i = 2; i * i <= n; i++) {
#pragma omp parallel for
for(j = i * i; j <= n; j = j + i) {
if(prime[j] == 1) {
prime[j] = 0;
}
}
}
// Print prime numbers
printf("\n Prime numbers from 1 to %d are\n", n);
for(i = 2; i <= n; i++) {
if(prime[i] == 1) {
printf("%d\t", i);
}
}
double start, end;
// Sequential
start = omp_get_wtime();
prime[i];
end = omp_get_wtime();
printf("\nSequential Time: %f seconds\n",end-start);
// Parallel
start = omp_get_wtime();
prime[i];
end = omp_get_wtime();
printf("Parallel Time: %f seconds\n",end-start);
printf("\n");
}
OUTPUT :
root@Mvit:~# gcc -fopenmp prog4.c
root@Mvit:~# ./[Link]
In order to find prime numbers from 1 to n, enter the value of n:100
Prime numbers from 1 to 100 are
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
Sequential Time: 0.000001 seconds
Parallel Time: 0.000000 seconds
5. Write a MPI Program to demonstration of MPI_Send and MPI_Recv.
#include <stdio.h>
#include <mpi.h>
int main(int argc, char *argv[])
{
int rank, size;
MPI_Status status;
int number;
// Initialize MPI environment
MPI_Init(&argc, &argv);
// Get the rank (ID) of the current process
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
// Get the total number of processes
MPI_Comm_size(MPI_COMM_WORLD, &size);
if (size < 2) {
if (rank == 0)
printf("Please run this program with at least 2 processes.\n");
MPI_Finalize();
return 0;
}
if (rank == 0) {
// Process 0 sends a number to Process 1
number = 2025;
printf("Process 0 sending number %d to Process 1...\n", number);
MPI_Send(&number, 1, MPI_INT, 1, 0, MPI_COMM_WORLD);
}
else if (rank == 1) {
// Process 1 receives the number from Process 0
MPI_Recv(&number, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
printf("Process 1 received number %d from Process 0.\n", number);
}
// Finalize MPI environment
MPI_Finalize();
return 0;
}
OUTPUT :
root@Mvit:~# mpicc prog5.c
root@Mvit:~# mpirun --allow-run-as-root -np 2 ./[Link]
Process 0 sending number 2025 to Process 1...
Process 1 received number 2025 from Process 0.
6. Write a MPI program to demonstration of deadlock using point to point
communication and avoidance of deadlock by altering the call sequence
#include <stdio.h>
#include <mpi.h>
int main(int argc, char *argv[])
{
int rank, size;
int data;
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &size);
if (size != 2) {
if (rank == 0)
printf("Run this program with exactly 2 processes!\n");
MPI_Finalize();
return 0;
}
if (rank == 0) {
data = 100;
printf("Process 0: Sending data to Process 1...\n");
MPI_Send(&data, 1, MPI_INT, 1, 0, MPI_COMM_WORLD); // Blocking send
printf("Process 0: Waiting to receive data from Process 1...\n");
MPI_Recv(&data, 1, MPI_INT, 1, 0, MPI_COMM_WORLD, &status);
printf("Process 0: Received data = %d\n", data);
}
else if (rank == 1) {
data = 200;
printf("Process 1: Sending data to Process 0...\n");
MPI_Send(&data, 1, MPI_INT, 0, 0, MPI_COMM_WORLD); // Blocking send
printf("Process 1: Waiting to receive data from Process 0...\n");
MPI_Recv(&data, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
printf("Process 1: Received data = %d\n", data);
}
MPI_Finalize();
return 0;
}
OUTPUT :
root@Mvit:~# mpicc prog6.c
root@Mvit:~# mpirun --allow-run-as-root -np 2 ./[Link]
Process 0: Sending data to Process 1...
Process 0: Waiting to receive data from Process 1...
Process 1: Sending data to Process 0...
Process 1: Waiting to receive data from Process 0...
Process 1: Received data = 100
Process 0: Received data = 200
7. Write a MPI Program to demonstration of Broadcast operation.
#include <stdio.h>
#include <mpi.h>
int main(int argc, char *argv[])
{
int rank, size;
int number;
// Initialize the MPI environment
MPI_Init(&argc, &argv);
// Get the rank of the process
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
// Get the number of processes
MPI_Comm_size(MPI_COMM_WORLD, &size);
if (rank == 0) {
// Process 0 initializes the data
number = 1234;
printf("Process 0: Broadcasting number = %d to all processes...\n", number);
}
// Broadcast the variable 'number' from process 0 to all others
MPI_Bcast(&number, 1, MPI_INT, 0, MPI_COMM_WORLD);
// All processes print the received number
printf("Process %d: Received number = %d\n", rank, number);
// Finalize the MPI environment
MPI_Finalize();
return 0;
}
OUTPUT :
root@Mvit:~# mpicc prog7.c
root@Mvit:~# mpirun --allow-run-as-root -np 2 ./[Link]
Process 0: Broadcasting number = 1234 to all processes...
Process 0: Received number = 1234
Process 1: Received number = 1234
8. Write a MPI Program demonstration of MPI_Scatter and MPI_Gather
#include <stdio.h>
#include <mpi.h>
int main(int argc, char *argv[])
{
int rank, size;
int send_data[8]; // Data to be scattered (only meaningful in root)
int recv_data; // Each process will receive one integer
int gathered_data[8]; // Data gathered back at root
MPI_Init(&argc, &argv); // Initialize MPI
MPI_Comm_rank(MPI_COMM_WORLD, &rank); // Get process rank
MPI_Comm_size(MPI_COMM_WORLD, &size); // Get total number of processes
if (size != 4) {
if (rank == 0)
printf("Please run this program with 4 processes.\n");
MPI_Finalize();
return 0;
}
// Process 0 initializes the data to scatter
if (rank == 0) {
printf("Process 0 initializing data: ");
for (int i = 0; i < 8; i++) {
send_data[i] = i + 1;
printf("%d ", send_data[i]);
}
printf("\n");
}
// Scatter data: root process sends equal parts to all processes
MPI_Scatter(send_data, 2, MPI_INT, &recv_data, 2, MPI_INT, 0,
MPI_COMM_WORLD);
printf("Process %d received data: ", rank);
for (int i = 0; i < 2; i++)
printf("%d ", (&recv_data)[i]);
printf("\n");
// Each process modifies its data
int local_data[2];
local_data[0] = (&recv_data)[0] * 10;
local_data[1] = (&recv_data)[1] * 10;
// Gather modified data back to root
MPI_Gather(local_data, 2, MPI_INT, gathered_data, 2, MPI_INT, 0,
MPI_COMM_WORLD);
// Root process prints the gathered result
if (rank == 0) {
printf("\nProcess 0 gathered modified data: ");
for (int i = 0; i < 8; i++)
printf("%d ", gathered_data[i]);
printf("\n");
}
MPI_Finalize();
return 0;
}
OUTPUT :
root@Mvit:~# mpicc prog8.c
root@Mvit:~# mpirun --allow-run-as-root -np 4 ./[Link]
Process 0 initializing data: 1 2 3 4 5 6 7 8
Process 3 received data: 7 8
Process 0 received data: 1 2
Process 1 received data: 3 4
Process 2 received data: 5 6
Process 0 gathered modified data: 10 20 30 40 50 60 70 80
9. Write a MPI Program to demonstration of MPI_Reduce and MPI_Allreduce
(MPI_MAX, MPI_MIN, MPI_SUM, MPI_PROD)
#include <stdio.h>
#include <mpi.h>
int main(int argc, char *argv[])
{
int rank, size;
int number;
int sum, product, maximum, minimum;
int all_sum, all_product, all_max, all_min;
// Initialize MPI environment
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank); // Get process rank
MPI_Comm_size(MPI_COMM_WORLD, &size); // Get total number of processes
// Each process initializes its number differently
number = rank + 1; // Example: process 0 -> 1, process 1 -> 2, etc.
printf("Process %d has value %d\n", rank, number);
// ---------------------------
// MPI_Reduce Demonstrations
// ---------------------------
MPI_Reduce(&number, &sum, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);
MPI_Reduce(&number, &product, 1, MPI_INT, MPI_PROD, 0,
MPI_COMM_WORLD);
MPI_Reduce(&number, &maximum, 1, MPI_INT, MPI_MAX, 0,
MPI_COMM_WORLD);
MPI_Reduce(&number, &minimum, 1, MPI_INT, MPI_MIN, 0,
MPI_COMM_WORLD);
if (rank == 0)
{
printf("\n--- Results using MPI_Reduce (available only in Root Process) ---\n");
printf("Sum = %d\n", sum);
printf("Product = %d\n", product);
printf("Maximum = %d\n", maximum);
printf("Minimum = %d\n", minimum);
}
// ---------------------------
// MPI_Allreduce Demonstrations
// ---------------------------
MPI_Allreduce(&number, &all_sum, 1, MPI_INT, MPI_SUM,
MPI_COMM_WORLD);
MPI_Allreduce(&number, &all_product, 1, MPI_INT, MPI_PROD,
MPI_COMM_WORLD);
MPI_Allreduce(&number, &all_max, 1, MPI_INT, MPI_MAX,
MPI_COMM_WORLD);
MPI_Allreduce(&number, &all_min, 1, MPI_INT, MPI_MIN, MPI_COMM_WORLD);
printf("\nProcess %d results using MPI_Allreduce:\n", rank);
printf(" Sum = %d, Product = %d, Max = %d, Min = %d\n",
all_sum, all_product, all_max, all_min);
// Finalize MPI environment
MPI_Finalize();
return 0;
}
OUTPUT :
root@Mvit:~# mpicc prog9.c
root@Mvit:~# mpirun --allow-run-as-root -np 4 ./[Link]
Process 1 has value 2
Process 2 has value 3
Process 3 has value 4
Process 0 has value 1
--- Results using MPI_Reduce (available only in Root Process) ---
Sum = 10
Product = 24
Maximum = 4
Minimum = 1
Process 0 results using MPI_Allreduce:
Sum = 10, Product = 24, Max = 4, Min = 1
Process 3 results using MPI_Allreduce:
Sum = 10, Product = 24, Max = 4, Min = 1
Process 1 results using MPI_Allreduce:
Sum = 10, Product = 24, Max = 4, Min = 1
Process 2 results using MPI_Allreduce:
Sum = 10, Product = 24, Max = 4, Min = 1