HPC - Bounding box of a set of rectangles

Moreno Marzolla

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

Figure 1: Bounding box of a set of rectangles
Figure 1: Bounding box of a set of rectangles

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


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