HPC - Scan inclusiva

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-10-14

Il file omp-inclusive-scan.c contiene un programma seriale che calcola le somme prefisse di un array v[] di \(n\) elementi applicando l'operatore scan inclusivo; il risultato viene memorizzato in un secondo array s[]. Al termine dell'operazione si ha quindi \(s[i] = v[0] + v[1] + \ldots + v[i]\) per ogni \(i=0, \ldots, n-1\).

Poiché nella programmazione OpenMP si assume che il numero \(P\) di thread sia limitato (in generale, \(P \ll n\)), non è conveniente realizzare la scan usando lo schema ad albero visto a lezione, che invece è adeguato per sistemi come le GPU. Usiamo invece una strategia più adeguata ad OpenMP, detta segmented scan; si faccia riferimento alla Figura 1, dove si assumono \(P=4\) thread OpenMP.

Figura 1: Schema scan inclusiva
Figura 1: Schema scan inclusiva

Ogni thread opera su porzioni di v[] ed s[] i cui estremi vengono determinati in modo opportuno.

  1. Ogni thread esegue la scan inclusiva della propria porzione di v[] usando l'algoritmo seriale. Il risultato viene memorizzato nella corrispondente porzione di s[].

  2. Il valore dell'ultimo elemento di ciascun sotto-vettore di s[] viene copiato in un array temporaneo blksum[] di lunghezza \(P\).

  3. Il master calcola la scan inclusiva di blksum[], memorizzando il risultato su un nuovo array blksum_s[] (in realtà si potrebbe anche modificare direttamente il contenuto di blksum[] senza usare un array separato).

  4. Ogni thread \(p\) somma il valore blksum_[p] a tutti gli elementi della propria porzione di s[].

Al termine, s[] contiene le somme prefisse di v[]

Le fasi 1 e 4 possono essere realizzate in parallelo dai thread OpenMP.

Per compilare:

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

Per eseguire:

    OMP_NUM_THREADS=2 ./omp-inclusive-scan

File