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\) rectanglesEach 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 -lm`

To execute:

` mpirun -n P ./mpi-bbox FILE`

Example:

` mpirun -n 4 ./mpi-bbox bbox-1000.in`

- mpi-bbox.c
- bbox-gen.c (this program generates random inputs for
`mpi-bbox.c`

) - bbox-1000.in
- bbox-10000.in
- bbox-100000.in