Using the programming language C, write a parallel program with MPI functions to
ID: 3687386 • Letter: U
Question
Using the programming language C, write a parallel program with MPI functions to do the following:
1) Define an array of size 1000.
2) Generate a random integer in the range of: 0 t0 999 for: n.
3) Generate n random integers in the range of: 0 to 1000 and save them in array.
4) For m (its value comes from the keyboard) processes divide that array to (m-1) segments. All the segments except the last one must be equal (Note that the last segment may get bigger than other segments)
5) Each of process p1, p2, p3,…, pm-1 obtains the biggest number from its segment and send it to the process with rank = 0.
6) Process 0 receives a number from each process: p1, p2, p3,…, pm-1, finds the biggest number and print it.
Note: If m -1 is bigger n terminate the execution of the program with an appropriate message the shows the value of m-1 and n.
You may follow the following serial program and convert it to parallel program with MPI functions in C to find the biggest number and print it..
Note: Remember the variable comm_sz in the parallel program must not get its value in the program or via scanf.
===============================================
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define atmost 1000
int find(int* a, int from, int to){
int i, b;
printf("%d----%d ", from,to);
b = a[from];
for(i = from + 1; i <= to; i++)
if(a[i] > b)
b = a[i];
return b;
}
int main(){
int i, n, a[atmost], comm_sz, biggest, h, b;
printf("How many segments? ");
scanf("%d", &comm_sz);
srand((unsigned)time(NULL));
n = rand()%atmost;
printf("n = %d ", n);
for(i = 0; i < n; i++){
a[i] = rand() % 10001;
printf("a[%d] = %d, ", i, a[i]);
}
printf(" ");
h = n/(comm_sz-1);
biggest = -1;
printf("h = %d ", h);
for(i = 0; i < comm_sz - 1; i++){
if(i == comm_sz - 2)
b = find(a, i * h, n-1);
else
b = find(a, i * h, (i+1) * h - 1);
if(b > biggest)
biggest = b;
}
printf("The biggest is: %d ", biggest);
return 0;
}
Explanation / Answer
The complete parallel program to find the biggest element in a array
Here is the expanded parallel version of the same program using MPI calls.
/* This program finds biggest element in an array using MPI parallelism.
* The root process acts as a master and sends a portion of the
* array to each child process. Master and child processes then
* all calculate a maximum element of the portion of the array assigned
* to them, and the child processes send their maximum element to
* the master, who calculates a grand total.
**/
#include <stdio.h>
#include <mpi.h>
#define max_rows 1000
#define send_data_tag 2001
#define return_data_tag 2002
int array[max_rows];
main(int argc, char **argv)
{
maximum, size, c, location = 1;
MPI_Status status;
int my_id, root_process, ierr, i, num_rows, num_procs,
an_id, num_rows_to_receive, avg_rows_per_process,
sender, num_rows_received, start_row, end_row, num_rows_to_send;
/* Now replicte this process to create parallel processes.
* From this point on, every process executes a seperate copy
* of this program */
ierr = MPI_Init(&argc, &argv);
root_process = 0;
/* find out MY process ID, and how many processes were started. */
ierr = MPI_Comm_rank(MPI_COMM_WORLD, &my_id);
ierr = MPI_Comm_size(MPI_COMM_WORLD, &num_procs);
if(my_id == root_process) {
/* I must be the root process, so I will query the user
* to determine how many numbers to sum. */
printf("please enter the number of rows in the array : ");
scanf("%i", &num_rows);
if(num_rows > max_rows) {
printf("Too many numbers. ");
exit(1);
}
avg_rows_per_process = num_rows / num_procs;
/* initialize an array */
printf("Enter the number of elements in array ");
scanf("%d", &size);
printf("Enter %d integers ", size);
for (c = 0; c < size; c++)
scanf("%d", &array[c]);
maximum = array[0];
/* distribute a portion of the bector to each child process */
for(an_id = 1; an_id < num_procs; an_id++) {
start_row = an_id*avg_rows_per_process + 1;
end_row = (an_id + 1)*avg_rows_per_process;
if((num_rows - end_row) < avg_rows_per_process)
end_row = num_rows - 1;
num_rows_to_send = end_row - start_row + 1;
ierr = MPI_Send( &num_rows_to_send, 1 , MPI_INT,
an_id, send_data_tag, MPI_COMM_WORLD);
ierr = MPI_Send( &array[start_row], num_rows_to_send, MPI_INT,
an_id, send_data_tag, MPI_COMM_WORLD);
}
/* and calculate the sum of the values in the segment assigned
* to the root process */
for (c = 1; c < size; c++)
{
if (array[c] > maximum)
{
maximum = array[c];
location = c+1;
}
}
printf("Maximum element is present at location %d and it's value is %d. ", location, maximum);
return 0;
}
/* and, finally, I collet the partial sums from the slave processes,
* print them, and add them to the grand sum, and print it */
for(an_id = 1; an_id < num_procs; an_id++) {
ierr = MPI_Recv( &maximum_element, 1, MPI_LONG, MPI_ANY_SOURCE,
return_data_tag, MPI_COMM_WORLD, &status);
sender = status.MPI_SOURCE;
printf("maximum element %i returned from process %i ", maximum_element, sender);
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.