Flowchart to find roots of a quadratic equation.

PARALLEL COMPUTING (BCS702) Program 6: Write a MPI program to demonstration of deadlock using point to point communication and avoidance of deadlock by altering the call sequence

 Department of Computer Science & Engineering, BLDEACET, Vijayapura

13 Lab Manual : PARALLEL COMPUTING (BCS702)

Program 6: Write a MPI program to demonstration of deadlock using point to point communication and avoidance of deadlock by altering the call sequence

Objective: Demonstrate deadlock and its avoidance using MPI.

Part A: Deadlock Example

Code (Deadlock-prone)

// mpi_deadlock.c

#include <stdio.h>

#include <mpi.h>

int main(int argc, char* argv[]) {

int rank, size, data;

MPI_Init(&argc, &argv);

MPI_Comm_rank(MPI_COMM_WORLD, &rank);

if (rank == 0) {

int msg = 100;

MPI_Recv(&data, 1, MPI_INT, 1, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);

MPI_Send(&msg, 1, MPI_INT, 1, 0, MPI_COMM_WORLD);

} else if (rank == 1) {

int msg = 200;

MPI_Recv(&data, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);

MPI_Send(&msg, 1, MPI_INT, 0, 0, MPI_COMM_WORLD);

}

MPI_Finalize();

return 0;

}

Explanation:

#include <stdio.h>

#include <mpi.h>

int main(int argc, char* argv[]) {

    int rank, size, data;

    MPI_Init(&argc, &argv);                  // Start MPI environment

    MPI_Comm_rank(MPI_COMM_WORLD, &rank);    // Get process rank (0, 1, ...)

....

• MPI_Init → Initializes MPI.

• MPI_Comm_rank → Gives each process a unique ID (rank).

  • Example: If you run with 2 processes → one will have rank=0, the other rank=1.

Process 0 (rank = 0)

if (rank == 0) {
    int msg = 100;
    MPI_Recv(&data, 1, MPI_INT, 1, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
    MPI_Send(&msg, 1, MPI_INT, 1, 0, MPI_COMM_WORLD);
}

• Creates an integer message msg = 100.

• First action → MPI_Recv: process 0 waits to receive an integer from process 1.

• Only after receiving, it will send its own message (100) to process 1.

---

👀 Process 1 (rank = 1)

else if (rank == 1) {
    int msg = 200;
    MPI_Recv(&data, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
    MPI_Send(&msg, 1, MPI_INT, 0, 0, MPI_COMM_WORLD);
}

• Creates an integer message msg = 200.

• First action → MPI_Recv: process 1 waits to receive an integer from process 0.

• Only after receiving, it will send its own message (200) to process 0.

---

❌ The Problem (Deadlock)

• Process 0 → waiting for data from Process 1 (via MPI_Recv).

• Process 1 → waiting for data from Process 0 (via MPI_Recv).

👉 Both are stuck waiting forever.
Since neither sends before receiving, no data is sent, so both processes are blocked.
This situation is called a deadlock.

Conclusion:

Both processes wait for Recv first, which leads to a deadlock as neither can proceed to Send.

Sample Output (Deadlock)

$ mpirun -np 2 ./mpi_deadlock

# Program hangs indefinitely — no output is produced

Part B: Deadlock-Free Version

Code (Avoiding Deadlock by Call Order)

// mpi_no_deadlock.c

#include <stdio.h>

#include <mpi.h>

int main(int argc, char* argv[]) {

int rank, data;

MPI_Init(&argc, &argv);

MPI_Comm_rank(MPI_COMM_WORLD, &rank);

if (rank == 0) {

int msg = 100;

MPI_Send(&msg, 1, MPI_INT, 1, 0, MPI_COMM_WORLD);

MPI_Recv(&data, 1, MPI_INT, 1, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);

printf("Process 0 received %d from Process 1\n", data);

} else if (rank == 1) {

int msg = 200;

MPI_Send(&msg, 1, MPI_INT, 0, 0, MPI_COMM_WORLD);

MPI_Recv(&data, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);

printf("Process 1 received %d from Process 0\n", data);

}

Explanation:

 Code (Deadlock-Free)

#include <stdio.h>
#include <mpi.h>

int main(int argc, char* argv[]) {
    int rank, data;
    MPI_Init(&argc, &argv);                  // Step 1: Start MPI environment
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);    // Step 2: Get process rank (0 or 1)

• MPI_Init → starts MPI.

• MPI_Comm_rank → gives each process a unique rank (0 or 1 here).

---

👀 Process 0 (rank = 0)

if (rank == 0) {
    int msg = 100;
    MPI_Send(&msg, 1, MPI_INT, 1, 0, MPI_COMM_WORLD);   // Step 3: Send first
    MPI_Recv(&data, 1, MPI_INT, 1, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE); // Step 4: Receive later
    printf("Process 0 received %d from Process 1\n", data);
}

• Creates message msg = 100.

• First action → MPI_Send: sends 100 to process 1.

• Then it waits to receive an integer from process 1.

• Finally prints:

  Process 0 received 200 from Process 1
  

---

👀 Process 1 (rank = 1)

else if (rank == 1) {
    int msg = 200;
    MPI_Send(&msg, 1, MPI_INT, 0, 0, MPI_COMM_WORLD);   // Step 3: Send first
    MPI_Recv(&data, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE); // Step 4: Receive later
    printf("Process 1 received %d from Process 0\n", data);
}

• Creates message msg = 200.

• First action → MPI_Send: sends 200 to process 0.

• Then it waits to receive an integer from process 0.

• Finally prints:

  Process 1 received 100 from Process 0
  

---

✅ Why This Code Does NOT Deadlock

• In Part A, both processes did MPI_Recv first → they blocked forever.

• In Part B, both processes do MPI_Send first → message is sent immediately and stored in MPI’s buffer.

• Then when they call MPI_Recv, the matching message is already available → they succeed.

Thus, no process gets stuck. 🎯

---

🔑 Key Takeaway

• Ordering matters in MPI.

• If you do Recv first on both sides → ❌ deadlock.

• If you do Send first → ✅ works fine (because MPI buffers the outgoing message until the other side receives it).

Quiz-1 for DCET 2025 (Introduction to Python)

 1. Introduction to Python

https://docs.google.com/forms/d/e/1FAIpQLSc3LFrMaswLg6mltJ3NN5QGbALA9Uc53KWPp4oV5HN4SaM0Iw/viewform?usp=sharing&ouid=105493060103049146790

Design and implement C/C++ Program to sort a given set of n integer elements using Merge Sort method and compute its time complexity. Run the program for varied values of n> 5000, and record the time taken to sort. Plot a graph of the time taken versus n.

 #include <stdio.h>

#include <stdlib.h>

#include <time.h>

// Function to merge two subarrays

void merge(int arr[], int left, int mid, int right) {

    int i, j, k;

    int n1 = mid - left + 1;

    int n2 = right - mid;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++)

        L[i] = arr[left + i];

    for (j = 0; j < n2; j++)

        R[j] = arr[mid + 1 + j];

    i = 0;

    j = 0;

    k = left;

    while (i < n1 && j < n2) {

        if (L[i] <= R[j]) {

            arr[k] = L[i];

            i++;

        } else {

            arr[k] = R[j];

            j++;

        }

        k++;

    }

    while (i < n1) {

        arr[k] = L[i];

        i++;

        k++;

    }

    while (j < n2) {

        arr[k] = R[j];

        j++;

        k++;

    }

}

// Merge Sort function

void mergeSort(int arr[], int left, int right) {

    if (left < right) {

        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);

        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);

    }

}

int main() {

    int n;

    printf("Enter number of elements (n > 5000): ");

    scanf("%d", &n);

    if (n <= 5000) {

        printf("Please enter n greater than 5000.\n");

        return 1;

    }

    int *arr = (int *)malloc(n * sizeof(int));

    if (arr == NULL) {

        printf("Memory allocation failed.\n");

        return 1;

    }

    // Generating random numbers

    srand(time(0));

    for (int i = 0; i < n; i++) {

        arr[i] = rand() % 100000; // Random numbers between 0 and 99999

    }

    clock_t start, end;

    double cpu_time_used;

    start = clock();

    mergeSort(arr, 0, n - 1);

    end = clock();

    cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;

    printf("Time taken to sort %d elements: %f seconds\n", n, cpu_time_used);

    free(arr);

    return 0;

}

What are formatted input and output functions? Discuss with syntax and e...

What is type conversion? Discuss different types with examples.

What is variable? Discuss its declaration and initialization with syntax...

OOPS with JAVA Expt.5 Develop a JAVA program to create a class named shape

Expt. 4. Distance between Two Points (OOPS with JAVA Lab.)

Expt. 3. Employee Information (OOP with JAVA Lab.)

Expt. 2. Stack Operations (OOPS with JAVA Lab)

OOPS with JAVA Lab. Expt. 1. Matrix Addition

GCD of two numbers and its application...

The greatest common divisor (gcd) of two numbers is the largest positive integer that divides both numbers without leaving a remainder. The gcd can be found using the Euclidean algorithm

GCD is useful in cases when you want different amounts of things to be arranged in the same number of order. 

For example there are 32 soldiers and 48 bandsman and during the parade you want them to march in the same number of rows. 

So , you calculate the HCF which is 8 and thus you can make 8 rows each for each group.

Write C++ program to find GCD two numbers a and b using  user defined function. i.e. GCD(a,b) using Euclids algorithm.

 #include <iostream>

using namespace std;

int gcd(int a, int b) {

   if (b == 0)

   return a;

   return gcd(b, a % b);

}

int main() {

   int a , b;

   cout<<"Enter the values of a and b: "<<endl;

   cin>>a>>b;

   cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);

   return 0;

}

Output:

Enter the values of a and b: 

10

20

GCD of 10 and 20 is 10

C program to count number of words from a sentence.

4) Java program to find largest of two integers using "if" statement.

Java program to read two integers from keyboard and find addition.

Java program to perform Arithmetic Calculations for given two integers.

TOP 10 MOTIVATIONAL STORIES - By Sandeep Maheshwari | Compilation of Bes...

Centering equations with a right-justified number in Microsoft Word

6.3 Graph Coloring Problem - Backtracking (Reference/Curtesy: Prof. Abdul Bari)

Module 5: L2: Design and implement the presence of Hamiltonian Cycle in an undirected Graph G of n vertices.

 

Design and implement the presence of Hamiltonian Cycle in an undirected Graph G of n vertices.

 

importjava.util.*;

 

 

classHamiltoniancycle

 

{

privateintadj[][],x[],n;

publicHamiltoniancycle()

{

Scanner src = newScanner(System.in);

System.out.println("Enter the number of nodes");

n=src.nextInt();

x=new int[n];

x[0]=0;

for(inti=1;i<n; i++)

x[i]=-1;

adj=new int[n][n];

System.out.println("Enter the adjacency matrix"); for (inti=0;i<n; i++)

for(intj=0; j<n; j++)

adj[i][j]=src.nextInt();

}

 

public void nextValue (intk)

 

{

inti=0;

while(true)

{

x[k]=x[k]+1;

if(x[k]==n)

x[k]=-1;

if(x[k]==-1)

return;

if(adj[x[k-1]][x[k]]==1)

for(i=0; i<k; i++)

if(x[i]==x[k])

break;

if(i==k)

if(k<n-1 || k==n-1 &&adj[x[n-1]][0]==1)

return;

}

}

public void getHCycle(intk)

{

while(true)

{

nextValue(k);

if(x[k]==-1)

return;

if(k==n-1)

{

System.out.println("\nSolution : ");

for(inti=0; i<n; i++)

System.out.print((x[i]+1)+" ");

System.out.println(1);

}

else

getHCycle(k+1);

}

 

}

}

 

 

classHamiltoniancycleExp

{

public static void main(String args[])

{

Hamiltoniancycleobj=newHamiltoniancycle(); obj.getHCycle(1);

}

}

 

 

Output:

 

Enter the number of nodes

 

6

Enter the adjacency matrix

0 1 1 1 0 0

1 0 1 0 0 1

1 1 0 1 1 0

1 0 1 0 1 0

0 0 1 1 0 1

0 1 0 0 1 0

 

Solution :					4	1
1	2	6	5	3
Solution :					3	1
1	2	6	5	4
Solution :					4	1
1	3	2	6	5
Solution :					2	1
1	3	4	5	6
Solution :					2	1
1	4	3	5	6
Solution :					3	1
1	4	5	6	2

Module-5: L1 Subset Problem :Java Program to find a subset of a given set S = {Sl, S2,…, Sn} of n positive integers whose SUM is equal to a given positive integer d

 Design and implement in Java to find a subset of a given set S = {Sl, S2,.....,Sn} of n

 

positive integers whose SUM is equal to a given positive integer d. For example, if S ={1, 2, 5,6, 8} and d= 9, there are two solutions {1,2,6}and {1,8}. Display a suitable message, if the given problem instance doesn't have a solution.

 

import java.util.Scanner;

 

import static java.lang.Math.pow;

 

 

public class subSet {

 

 

void subset(intnum,int n, int x[])

{

int i; for(i=1;i<=n;i++)

x[i]=0;

for(i=n;num!=0;i--)

{

x[i]=num%2;

num=num/2;

}

}

 

public static void main(String[] args) {

 

//                    TODO Auto-generated method stub int a[]=new int[10];

 

int x[]=new int[10]; intn,d,sum,present=0; int j;

 

System.out.println("enter the number of elements of set"); Scanner sc=new Scanner(System.in);

 

n=sc.nextInt();

System.out.println("enter the elements of set"); for(int i=1;i<=n;i++)

 

a[i]=sc.nextInt();

System.out.println("enter the positive integer sum"); d=sc.nextInt();

 

if(d>0)

{

for(int i=1;i<=Math.pow(2,n)-1;i++)

{

subSet s=new subSet(); s.subset(i,n,x); sum=0; for(j=1;j<=n;j++) if(x[j]==1)

sum=sum+a[j];

 

if(d==sum)

{

System.out.print("Subset={");

present=1;

for(j=1;j<=n;j++)

if(x[j]==1)

System.out.print(a[j]+",");

 

System.out.print("}="+d);

 

System.out.println();

}

 

}

 

}

 

if(present==0)

System.out.println("Solution does not exists");

 

}

 

}

 

Output:

 

enter the number of elements of set

 

5

enter the elements of set

1 2 5 6 8

enter the positive integer sum

9

Subset={1,8,}=9

Subset={1,2,6,}=9