Sorting With Message Passing Sorting with Message Passing A compare-exchange ope

Question

Sorting With Message Passing

Sorting with Message Passing A compare-exchange operation merges two sorted sequences of length M, contained in tasks A and B. Upon completion of the operation, both tasks have M data, and all elements in task A are less than or equal to all elements in task B. As illustrated in the Figure, each task sends its data to the other task. Task A identifies the M lowest elements and discards the remainder; this process requires at least M/2 and at most M comparisons. Similarly, task B identifies the M highest elements. Write a message passing algorithm that will sort an array on a Hyper-cube. This should be the code for a single node. Assume that nodes start with their own portion of an array of input numbers and end with their portion of the sorted array; ie At the end, Node 0 will hold the first N/P sorted elements. Each node will process and communicate based on their Process ID. You can simplify by using functions for methods described above, but be sure to include then in your analysis.

Explanation / Answer

#include<stdio.h>

#include<conio.h>

void call(int a[].int b[],int n3){

int a[],b[],c[],d[],i,j,n,low,mid,high;

void merging(int low,int mid,int high){

int l1,l2,i;

for(l1=low , l2=mid+1, i =low; l1 < =mid && l2 < = high; i++)

if(c[l1] < = c[l2])

d[i]=c[l1++];

else

d[i]=c[l2++];

}

while(l1 < = mid)

d[i++] = c[l1++];

while(l2 < = high)

d[i++] = c[l2++];

for(i=low;i<=high;i++)

c[i]=d[i];

}

void sort(int low,int high)

{

int mid;

if(low< high)

{

mid=(low+high)/2;

sort(low,mid);

sort(mid+1,high);

merging(low,mid,high);

}

else{

return;

}

void break(){

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

{

printf("%d",d[i]);

}

for(i=n3;i<=n2;i++)

{

printf("%d",d[i]);

}

}

}

void main(int argc,char *argv)

{

int size1,rank1;size2,rank2;

MPI_Init(&argc,&argv);

MPI_Comm_rank1(MPI_COMM_WORLD,&rank1);

MPI_Comm_size1(MPI_COMM_WORLD,&size1);

MPI_Comm_rank2(MPI_COMM_WORLD,&rank2);

MPI_Comm_size2(MPI_COMM_WORLD,&size2);

int* a1=malloc(size*sizeof(int));

int* a2=malloc(size*sizeof(int));

a1[rank1]=rank1;

a2[rank2]=rank2;

printf("enter the elemens of first array");

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

{

scanf("%d",&a[i]);

}

printf("enter elements of second array");

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

{

scanf("%d",&b[i]);

}

size3=(size1+size2)/2;

for(i=0;i<(size1+size2);i++)

{

scanf("%d",&c[i]);

}

sort(0,size3);

sort(size3,size2);

MPI_ALLgather(&a1[rank1],1,MPI_INT,a1[ ],1,MPI_INT,MPI_COMM_WORLD);

MPI_ALLgather(&a2[rank2],1,MPI_INT,a2[ ],1,MPI_INT,MPI_COMM_WORLD);

MPI_Barrier(MPI_COMM_WORLD);

call(a1[size1],a2[size2],size3);

break();

}

}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.