Pipelined Insertion Sort -The task is to implement pipelined insertion sort usin
ID: 665397 • Letter: P
Question
Pipelined Insertion Sort -The task is to implement pipelined insertion sort using MPI
A template of the program is provided.
/* pipelined insertion sort program
* Process 0 generates random numbers to sort and the number
* of random numbers is the same as the number of processes.
* Before and after sorting, Process 0 prints the sequence of
* numbers.
*
* Input: none.
* Output: contents of the array after sorting.
*
*
*/
#include
#include "mpi.h"
#define MAX_NUMBER 1000;
int main(int argc, char* argv[]) {
int my_rank; /* rank of process */
int p; /* number of processes */
int source; /* rank of sender */
int dest; /* rank of receiver */
int tag = 0; /* tag for messages */
int* arr; /* storage for numbers */
MPI_Status status; /* return status for */
/* receive */
/* Start up MPI */
MPI_Init(&argc, &argv);
/* Find out process rank */
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
/* Find out number of processes */
MPI_Comm_size(MPI_COMM_WORLD, &p);
if (my_rank == 0) {
/* Create random numbers */
arr = malloc (p * sizeof(int));
int i;
srand(p);
for (i = 0; i < p; i++)
arr[i] = rand() % MAX_NUMBER;
/* print the numbers */
printf("The generated numbers are: ");
for (i = 0; i < p; i++) {
printf("%6d", arr[i]);
if ((i+1) % 10 == 0) printf(" ");
}
printf(" ");
}
// Write code here to do the insertion sort
// Write code here to pass the numbers back to Process 0
// and Process 0 stores the numbers in array "arr" in process
// rank order.
// Print sorted numbers
if (my_rank == 0) {
int i;
printf("The sorted numbers are: ");
for (i = 0; i < p; i++) {
printf("%6d", arr[i]);
if ((i+1) % 10 == 0) printf(" ");
}
printf(" ");
}
/* Shut down MPI */
MPI_Finalize();
return 0;
} /* main */
Explanation / Answer
Program:
#include <stdio.h>
#include <mpi.h>
#define MAX_NUMBER 1000;
int main ( int argc, char *argv[] )
{
int my_rank,p,source,dest,tag=0;
int *arr;
MPI_Status status;
MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD,&my_rank);
MPI_Comm_rank(MPI_COMM_WORLD,&p);
if(my_rank==0)
{
arr= malloc(p*sizeof(int));
int i;
srand(p);
for (i = 0; i < p; i++)
{
arr[i] = rand() % MAX_NUMBER;
printf("The generated numbers are: ");
}
for (i = 0; i < p; i++)
{
printf("%6d", arr[i]);
if ((i+1) % 10 == 0) printf(" ");
}
printf(" ");
fflush(stdout);
}
for(i=0; i<=p-my_rank; i++)
{
if(my_rank==0)
{
dest-arr[i];
if(v>0)
{
printf("Manager gets %d. ",arr[i]);
fflush(stdout);
Insertion_Sort(my_rank,i,&source,&dest);
}
MPI_Barrier(MPI_COMM_WORLD);
if (my_rank == 0)
{
int i;
printf("The sorted numbers are: ");
for (i = 0; i < p; i++)
{
printf("%6d", arr[i]);
if ((i+1) % 10 == 0) printf(" ");
}
printf(" ");
}
/* Shut down MPI */
MPI_Finalize();
return 0;
} /* main */
void Insertion_Sort(int my_rank, int i, int *s, *d)
{
if(step==0)
*s = *d;
else if(*d>*s)
{
MPI_Send(d,1,MPI_INT,myid+1,tag,MPI_COMM_WORLD);
if(v>0)
{
printf("Node %d sends %d to %d. ",myid,*d,myid+1);
fflush(stdout);
}
}
else
{
MPI_Send(s,1,MPI_INT,myid+1,tag,MPI_COMM_WORLD);
if(v>0)
{
printf("Node %d sends %d to %d. ",myid,*s,myid+1);
fflush(stdout);
}
*s = *d;
}
}