HPC - Calcolo dell'area dell'unione di cerchi

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-05-28

Il file mpi-circles.c contiene una implementazione seriale di un algoritmo randomizzato di tipo Monte Carlo per stimare l'area dell'unione \(N\) cerchi. Siano cx[i], cy[i] le coordinate del centro del cerchio i-esima, e r[i] il suo raggio; tutti i cerchi sono interamente contenuti all'interno del quadrato avente gli angoli opposti di coordinate (0, 0), (1000, 1000). Poiché i cerchi possono essere collocati in posizioni arbitrarie, potrebbero sovrapporsi in tutto o in parte; di conseguenza non è semplice determinare l'area della loro unione.

Implementiamo un algoritmo di tipo Monte Carlo per calcolare l'area dell'unione; l'idea è simile a quella che abbiamo già visto per calcolare il valore approssimato di \(\pi\) generando punti casuali:

Figura 1: Calcolo dell'area dell'unione di cerchi con metodo Monte Carlo
Figura 1: Calcolo dell'area dell'unione di cerchi con metodo Monte Carlo

La Figura 1 illustra l'idea. Viene fornito il file mpi-circles.c contenente uno schema di soluzione seriale, in cui il processo 0 esegue tutte le operazioni. Scopo di questo esercizio è di distribuire la computazione tra tutti i processi MPI. È richiesto che solo il processo 0 legga il file di input. Questo significa che solo il processo 0 conosce il numero \(N\) di cerchi e le loro coordinate; se tali informazioni sono necessarie agli altri processi, il master le deve comunicare esplicitamente. Il programma deve funzionare correttamente per qualsiasi valore di \(N\) e \(K\).

Per compilare:

    mpicc -std=c99 -Wall -Wpedantic mpi-circles.c -o mpi-circles

Eseguire con:

    mpirun -n P ./mpi-circles N FILEIN

Esempio, usando 4 processi MPI:

    mpirun -n 4 ./mpi-circles 10000 circles-1000.in

Suggerimento: si potrebbe essere tentati di partizionare i cerchi tra i processi MPI, in modo che ciascun processo gestisca \(N/P\) cerchi. Questa soluzione però non sarebbe corretta: perché?

File