# HPC - Bounding box of a set of rectangles

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:

1. 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.

2. 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

3. Each process computes the bounding box of the rectangles assigned to it.

4. 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