HPC - Bounding box di un insieme di rettangoli

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-11-09

Scopo di questo esercizio è il calcolo del bounding box di un insieme di rettangoli. Il bounding box è il rettangolo di area minima che contiene tutti i rettangoli dati; un esempio è mostrato nella Figura 1 (il bounding box è quello tratteggiato).

Figura 1: Bounding box di un insieme di rettangoli
Figura 1: Bounding box di un insieme di rettangoli

Le coordinate dei rettangoli sono indicate in un file di testo con il formato seguente. La prima riga contiene il numero \(N\) di rettangoli; seguono \(N\) righe, ciascuna composta da quattro valori x1[i] y1[i] x2[i] y2[i] di tipo float, separati da spazi. Le righe rappresentano le coordinate degli angoli opposti di ciascun rettangolo: (x1[i], y1[i]) sono le coordinate dell'angolo in basso a sinistra, mentre (x2[i], y2[i]) sono quelle dell'angolo in alto a destra. Il riferimento sono gli assi cartesiani.

Viene fornito un programma mpi-bbox.c che risolve il problema in modo sequenziale, dato che solo il processo master effettua le computazioni. Scopo di questo esercizio è di parallelizzare il programma in modo che \(P\) processi MPI cooperino per il calcolo del bounding box. Si suggerisce di strutturare il programma in base ai passi seguenti:

  1. Il master legge i dati dal file di input, inserendo le coordinate negli array x1[], y1[], x2[], y2[]; si può inizialmente assumere che il numero di rettangoli \(N\) sia un multiplo del numero \(P\) di processi MPI.

  2. Il master comunica il valore \(N\) ai processi usando MPI_Bcast() distribuisce le coordinate dei rettangoli tra i processi MPI usando MPI_Scatter(); in questo modo ogni processo riceve i dati di \(N/P\) rettangoli (assumere inizialmente che N sia multiplo di \(P\)).

  3. Ciascun processo calcola il bounding box dei rettangoli a lui assegnati.

  4. Il master usa MPI_Reduce() per calcolare i minimi/massimi delle coordinate dei bounding box parziali, usando gli operatori di riduzione MPI_MIN e MPI_MAX. Al termine di questa fase il master avrà determinato il bounding box di tutti i rettangoli.

Nell'archivio dell'esercitazione è fornito un programma bbox-gen.c che può essere usato per generare dei file di input composti da rettangoli generati casualmente; le istruzioni d'uso sono contenute nel sorgente.

Dopo aver risolto il problema assumendo che \(N\) sia multiplo di \(P\), modificare il codice per funzionare correttamente per un numero \(N\) arbitrario di rettangoli.

Per compilare:

    mpicc -std=c99 -Wall -Wpedantic mpi-bbox.c -o mpi-bbox -lm

Per eseguire:

    mpirun -n P ./mpi-bbox FILE

Esempio, usando 4 processi MPI:

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

File