Last updated: 2022-11-09
Write a parallel program that computes the bounding box of a set of rectangles. The bounding box is the rectangle of minimal area that contains all the given rectangles (see Figure 1).
The progra reads the coordinates of the rectangles from a test file. The first row contains the number \(N\) of rectangles; \(N\) lines follow, each consisting of four space-separated values x1[i] y1[i] x2[i] y2[i] of type float. These values are the coordinates of the opposite corners of each rectangle: (x1[i], y1[i]) is the top left, while (x2[i], y2[i]) is the bottom right corner.
You are provided with a serial implementation mpi-bbox.c where process 0 performs the entire computation. The purpose of this exercise is to parallelize the program so that \(P\) MPI processes cooperate for determining the bounding box. Only process 0 can read the input and write the output.
The parallel program should operated according to the following steps:
Process 0 reads the data from the input file; you can initially assume that the number of rectangles \(N\) is a multiple of the number \(P\) of MPI processes.
Process 0 broadcasts \(N\) to all processes using MPI_Bcast(). The input coordinates are scattered across the processes, so that each one receives the data of \(N/P\) rectangles
Each process computes the bounding box of the rectangles assigned to it.
The master uses MPI_Reduce() to compute the coordinates of the corners of the bounding box using the MPI_MIN and MPI_MAX reduction operators.
To generate additional random inputs you can use bbox-gen.c; usage instructions are at the beginning of the source code.
When you have a working program, try to relax the assumption that \(N\) is multiple of \(P\).
To compile:
mpicc -std=c99 -Wall -Wpedantic mpi-bbox.c -o mpi-bbox -lmTo execute:
mpirun -n P ./mpi-bbox FILEExample:
mpirun -n 4 ./mpi-bbox bbox-1000.inmpi-bbox.c)