# HPC - Monte Carlo estimation of the area of the union of circles

Last updated: 2022-10-31

File mpi-circles.c contains a serial implementation of a Monte Carlo algorithm that estimates the area of ​​the union of $$N$$ circles. Let cx[i], cy[i], and r[i] be the coordinates of the center of circle $$i$$ and its radius. Assume that all circles are entirely contained within the bounding square with opposites corners $$(0, 0)$$ and $$(1000, 1000)$$. Since circles can be in any position, they may overlap in in whole or in part; therefore it is not easy to determine the area of their union.

We implement a Monte Carlo algorithm to estimate the area; the idea is similar to the one we used to estimate the value of $$\pi$$ by generating random points:

• generate $$K$$ randomly distributed points inside the bounding square $$(0, 0)$$, $$(1000, 1000)$$. Let $$C$$ be the number of points that fall within at least one circle.

• The area $$A$$ of the union of the circles is estimated as the product of the area of the bounding square and the fraction of points that fall within at least one circle: $$A = 1000000 \times C/S$$;

Figure 1 illustrates the idea.

The file mpi-circles.c containing a serial program where process 0 performs the whole computation. The purpose of this exercise is to distribute the computation among all MPI processes. Assume that only process 0 can read the input file; this means that only process 0 knows the number $$N$$ of circles and their coordinates. Should this information be needed by other processes, some explicit communication must be performed. The program must work correctly for any value of $$N$$ and $$K$$.

Hint. You might be tempted to to partition the circles among the MPI processes, in such a way that each process handles $$N/P$$ circles. However, this solution would not work (or better, would be very inefficient): why?.

The correct approach is to let each process $$p$$ generate $$K/P$$ points and test each point with all the circles, and compute the number of points $$C_p$$ that fall inside at least one circle. Then, the master computes the sum $$C = \sum_{p=0}^{P-1} C_p$$ using a reduction, and estimates the area as above. To do this, each process must receive a copy of the arrays cx[], cy[] and r[] using three broadcast operations.

To compile:

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

To execute:

    mpirun -n P ./mpi-circles N input_file_name

Example:

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