Alcuni commenti al compito del 09/02/2022
=========================================

I voti sono stati arrotondati per eccesso (quindi 24.5 diventa 25).

==============================================================================

DOMANDA 1 (problemi su GPU): alcuni hanno indicato la ricerca di
chiavi su un array o su un albero binario di ricerca (ABR) come esempi
di applicazioni che verosimilmente non traggono vantaggio dalle GPU.
Non sono d'accordo sulla ricerca in un array, e sono parzialmente
d'accordo sulla ricerca in un ABR:

1. la ricerca su un array sulla GPU non viene realizzata come quella
OpenMP vista in laboratorio. Per cercare la prima occorrenza di una
chiave k su un array di n elementi si possono lanciare n CUDA thread;
il thread i setta found[i] = i se v[i] == k, found[i] = n
altrimenti. L'array found[0..n-1] è un array ausiliario allocato nel
device. A questo punto basta fare una riduzione sul minimo per avere
l'indice della prima occorrenza. Se si vogliono avere le posizioni di
tutte le occorrenze la cosa diventa leggermente più laboriosa ma
fattibile. Quindi, non si divide l'array in blocchi come si farebbe
con OpenMP, e non ci sarebbero problemi di località degli accessi né
di computazioni divergenti.

2. la ricerca di m chiavi in un ABR è sicuramente un esempio di
applicazione in cui gli accessi in memoria sono irregolari. Inoltre,
le computazioni sono sì divergenti ma non a livello tale da rendere
l'uso di GPU sconsigliabile. Possiamo infatti immaginare che, per
cercare m chiavi in un ABR, vengano lanciati m cuda thread che
eseguono tutti lo pseudocodice seguente:

n = root;
while (n != NULL && n->key != k) {
  if (n->key > k)
    n = n->left;
  else
    n = n->right;
}

Quindi c'è divergenza relativamente all'"if" interno, ma si tratta di
un tipo di divergenza a cui il compilatore potrebbe porre rimedio, ad
esempio realizzando il test + assegnamento usando una qualche forma di
"selection and masking" simile a quella vista con la programmazione
SIMD.

Un esempio migliore di computazione divergente potrebbe essere quella
che avviene nei programmi di ray tracing basati sulla tecnica
ricorsiva vista nell'esempio OpenMP in laboratorio. Raggi diversi
potrebbero intersecare oggetti diversi con caratteristiche diverse
(es. uno riflettente e uno traslucido) che innescherebbero flussi di
computazione completamente diversi. Inoltre, il ray tracer visto in
laboratorio è un programma ricorsivo, e come sappiamo la ricorsione è
problematica nelle GPU. Ciò non significa che il ray tracing su GPU
sia impossibile (si veda
https://developer.nvidia.com/rtx/ray-tracing), ma è certamente un tipo
di applicazione problematica.

==============================================================================

DOMANDA 2 (MPI): vedi implementazione mostrata sulla pagina del corso.
Nelle risposte è stato penalizzato fortemente l'uso di operazioni
punto-punto, che in questo problema potevano (dovevano!) essere
evitate.

==============================================================================

DOMANDA 3 (Speedup superlineare): le ragioni principali per speedup
superlinare sono: uso di istruzioni SIMD; miglior uso della cache
causato dalla riduzione del dominio all'aumentare del numero di core;
uso di processori multicore di tipo eterogeneo.

==============================================================================

Domanda 4 (OpenMP): Il frammento di codice fornito era preso pari pari
dall'esercitazione sul crivello di Eratostene; il frammento di codice
dato calcola p[i] == 1 se e solo se i è un numero primo con i>=2.  Si
poteva parallelizzare in questo modo:

#define N ...
int p[N], s, t;
#pragma omp parallel for default(none) shared(p)
for (s = 0; s<N; s++) {
    p[s] = 1;
}
for (s=2; s*s <= N; s++) {
    if (p[s]) {
#pragma omp parallel for default(none) shared(s,p)    
        for (t = s*s; t<N; t = t+s) {
            p[t] = 0;
        }
    }
}

Il ciclo "for (s=2; s*s <= N; s++)" NON si può parallelizzare perché
il corpo presenta una loop-carried dependency: infatti si controlla il
valore di p[] che potrebbe essere modificato all'interno del corpo del
ciclo più interno. È errato usare una direttiva "atomic" per
proteggere la lettura: infatti la clausola garantisce che un thread
OpenMP alla volta possa eseguire il corpo della direttiva "atomic", ma
non impedisce che thread diversi accedano contemporaneamente a blocchi
differenti protetti con "atomic"!

C'è anche un motivo più subdolo per cui non si può parallelizzare il
ciclo esterno: la condizione "s*s <= N" non consente la
parallelizzazione automatica, perché non è del tipo "variabile <=
limite".