HPC - Stima del valore di \(\pi\) con metodo Monte Carlo

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-10-13

Il file omp-pi.c contiene un programma seriale per il calcolo del valore approssimato di \(\pi\) usando un algoritmo di tipo Monte Carlo. Negli algoritmi Monte Carlo si fa uso di numeri (pseudo-)casuali per calcolare una approssimazione di qualche espressione numerica di interesse.

Figura 1: Calcolo di \pi con metodo Monte Carlo
Figura 1: Calcolo di \(\pi\) con metodo Monte Carlo

Il principio è semplice (si faccia riferimento alla Figura 1). Si generano \(N\) punti casuali uniformemente distribuiti all'interno del quadrato di vertici \((-1, -1)\) e \((1, 1)\). Detto \(x\) il numero di punti che si trovano all'interno del cerchio inscritto in esso, il rapporto \(x / N\) approssima il rapporto tra l'area del cerchio e l'area del quadrato. Poiché l'area del cerchio inscritto è \(\pi\) e l'area del quadrato è \(4\), possiamo stimare il valore di \(\pi\) come \((4x / N)\). Tale stima tende ad essere più accurata all'aumentare del numero \(N\) di punti generati.

Modificare il programma seriale in modo da sfruttare il parallelismo con OpenMP. Iniziare con una implementazione che usi il costrutto omp parallel. Detto \(P\) il numero di thread OpenMP, il programma potrebbe operare come segue:

  1. Il thread \(p\) genera \(N/P\) punti invocando la funzione generate_points(), ponendo il risultato nell'elemento inside[p] di un array inside[] di lunghezza \(P\). Tale array va dichiarato fuori dal blocco parallelo perché deve essere condiviso da tutti i thread.

  2. Al termine del blocco parallelo, il master somma i valori dell'array inside[], determinando il numero totale di punti interni al cerchio e completando il calcolo di \(\pi\)

Si può inizialmente assumere che il numero di punti \(N\) sia multiplo di \(P\); una volta ottenuta una versione funzionante, si modifichin il programma in modo da funzionare correttamente con qualsiasi valore di \(N\).

Per compilare:

    gcc -std=c99 -fopenmp -Wall -Wpedantic omp-pi.c -o omp-pi -lm

Per eseguire:

    ./omp-pi [N]

Esempio, usando 4 thread OpenMP:

    OMP_NUM_THREADS=4 ./omp-pi 20000

File