Lab for Chapter 5 – Pipelined Insertion Sort in C This is the lab exercise for C
ID: 665367 • Letter: L
Question
Lab for Chapter 5 – Pipelined Insertion Sort in C
This is the lab exercise for Chapter 5 – Pipelined Computation. The task is to implement pipelined
insertion sort using MPI. The guidelines for the implementation include the following:
1. Use one process to implement one function unit in the pipeline. Communications between
processes must follow the pipeline structure, i.e., process i only communicates with process i-1
and process i+1 where 0<i<p-1, process 0 only communicates with process 1 and process p-1
only communicates with process p-2, etc.
2. Use the master process, Process 0, to generate random numbers to sort and start the sorting
process. The number of numbers to sort should be equal to the number of processes. Process 0
should use a dynamically allocated array to store generated numbers. Process 0 prints the
generated numbers before the sorting starts.
3. After sorting, numbers must be transferred back to Process 0 using the pipeline structure and
Process 0 prints out the sorted numbers.
Explanation / Answer
#include <stdio.h>
#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
Int c,t,d;
// 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 */
int main ( int argc, char*argv[] )
{
int i,p,*n,j,g,s;
MPI_Status status;
MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD,&p);
MPI_Comm_rank(MPI_COMM_WORLD,&i);
if(i==0)
/*manager generates p random numbers*/
{
n = (int*)calloc(p,sizeof(int));
srand(time(NULL));
for(j=0; j<p; j++) n[j] = rand() % 100;
if(v>0)
{
printf("The %d numbers to sort : ",p);
for(j=0; j<p; j++) printf(" %d", n[j]);
printf(" "); fflush(stdout);
}
}
for(j=0; j<p-i; j++)
/*processor i performs p-i steps*/
if(i==0)
{
g = n[j];
if(v>0)
{ printf("Manager gets %d. ",n[j]); fflush(stdout); }
Compare_and_Send(i,j,&s,&g);
}
else
{
MPI_Recv(&g,1,MPI_INT,i-1,tag,MPI_COMM_WORLD,&statu
s);
if(v>0)
{ printf("Node %d receives %d. ",i,g);
fflush(stdout); }
Compare_and_Send(i,j,&s,&g);
}
MPI_Barrier(MPI_COMM_WORLD);
/*to synchronize for printing*/
Collect_Sorted_Sequence(i,p,s,n);
MPI_Finalize();
return 0;
}
void Compare_and_Send( int myid, int step, int*smaller, int*gotten )
/*Processor "myid" initializes smaller with gotten*at step zero,*or ompares smaller to gotten and*sends the larger number through.*/
{
if(step==0)
*smaller =*gotten;
Else if(*gotten >*smaller){
MPI_Send(gotten,1,MPI_INT,myid+1,tag,MPI_COMM_WORLD);
if(v>0)
{
printf("Node %d sends %d to %d. ",myid,*gotten,myid+1);
fflush(stdout);
}
}
else
{
MPI_Send(smaller,1,MPI_INT,myid+1,tag,MPI_COMM_WORLD);
if(v>0)
{
printf("Node %d sends %d to %d. ",myid,*smaller,myid+1);
fflush(stdout);
}
*smaller =*gotten;
}
}
void Collect_Sorted_Sequence( int myid, int p, int smaller, int*sorted ) {
/*Processor "myid" sends its smaller number to the*manager who ollects*the sorted numbers in the*sorted array, which is then rinted.*/
MPI_Status status;
int k;
if(myid==0) {
sorted[0] = smaller;
for(k=1; k<p; k++)
MPI_Recv(&sorted[k],1,MPI_INT,k,tag,
MPI_COMM_WORLD,&status);
printf("The sorted sequence : ");
for(k=0; k<p; k++) printf(" %d",sorted[k]);
printf(" ");
}
else
MPI_Send(&smaller,1,MPI_INT,0,tag,MPI_COMM_WORLD);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.