HPC - Simulare la clausola "schedule(dynamic)"

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-10-14

A lezione abbiamo visto come sia possibile utilizzare la clausola schedule(dynamic) per assegnare dinamicamente ogni iterazione di un ciclo "for" al primo thread OpenMP disponibile. Lo scopo di questo esercizio è di simulare la clausola schedule(dynamic) usando solo il costrutto omp parallel (non omp parallel for).

Il file omp-dynamic.c contiene una implementazione seriale di un programma che effettua le seguenti computazioni. Il programma crea e inizializza un array vin[] di \(n\) interi (il valore \(n\) può essere passato da riga di comando). Il programma crea un secondo array vout[], sempre di lunghezza \(n\), e ne definisce il contenuto in modo tale che vout[i] = Fib(vin[i]) per ogni \(i\), essendo Fib(k) il k-esimo numero della successione di Fibonacci: Fib(0) = Fib(1) = 1; Fib(k) = Fib(k-1) + Fib(k-2) se \(k \geq 2\). Il calcolo dei numeri di Fibonacci viene fatto in modo volutamente inefficiente con un algoritmo ricorsivo, per far sì che il tempo di calcolo vari significativamente al variare di \(i\).

Iniziare parallelizzando il ciclo "for" indicato nel codice con il commento [TODO] mediante il costrutto omp parallel for. Mantenendo fissa la lunghezza n degli array, osservare i tempi di esecuzione nei casi seguenti:

  1. Parallelizzando il ciclo con la direttiva #pragma omp parallel for, in cui si usa lo schedule di default (che nel caso di GCC è lo schedule statico con dimensione del blocco \(n / \textit{numero_thread_OpenMP}\));

  2. Parallelizzando il ciclo con uno schedule statico ma con un blocco di dimensione inferiore, ad es. 64; si può usare la direttiva #pragma omp parallel for schedule(static,64);

  3. Parallelizzando il ciclo con uno schedule dinamico, usando la direttiva #pragma omp parallel for schedule(dynamic); ricordiamo che in questo caso la dimensione di default del blocco è 1.

Fatto ciò, si chiede di realizzare lo stesso comportamento del punto 3 (schedule dinamico con blocco di dimensione 1) utilizzando il solo costrutto omp parallel. Consiglio di procedere come segue: si crea un pool di thread OpenMP, e si utilizza una variabile condivisa per indicare qual è l'indice del prossimo elemento di vin[] che deve ancora essere processato. Ogni thread acquisisce in mutua esclusione il prossimo elemento di vin[], se presente, e lo elabora in parallelo.

Per compilare:

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

Per eseguire:

    ./omp-dynamic [n]

Esempio:

    OMP_NUM_THREADS=2 ./omp-dynamic

File