Prova scritta di High Performance Computing del 10 gennaio 2023 =============================================================== Alcune osservazioni: - La valutazione delle risposte ha tenuto conto della qualità del testo: uso corretto della punteggiatura, chiarezza e precisione delle argomentazioni, completezza. Devo purtroppo segnalare che in molti casi ho riscontrato un uso non corretto della grammatica e/o della punteggiatura. Certi colloquialismi ("pescare i dati") e abbreviazioni ("lv" invece di "livello") non sono accettabili in un esame scritto. Invito a prestare la massima attenzione nella stesura della relazione del progetto, perché una esposizione di scarsa qualità verrà *pesantemente penalizzata*. - Nella prima domanda (speedup superlineare) qualcuno ha menzionato la possibilità che lo speedup venga calcolato in modo errato (es., usando il tempo di esecuzione del programma seriale al numeratore, anziché il tempo di esecuzione del programma parallelo con P=1 processori). Sebbene ciò sia corretto in linea di principio, la domanda assumeva che lo speedup fosse calcolato correttamente. I motivi per uno speedup superlineare erano quindi: (i) l'uso di architetture eterogenee (es., SIMD oppure processori con core eterogenei come era la PlayStation 3), e (ii) miglior uso della cache a causa della riduzione del "working set", cioè della porzione di dominio su cui i processori/core operano. Qualcuno ha ricordato l'esempio visto in laboratorio della decifratura di un messaggio cifrato con una tecnica "a forza bruta": in questo caso si potevano osservare speedup superlineari, perché la posizione della chiave all'interno del blocco assegnato a ciascun thread OpenMP poteva cambiare in base al numero di blocchi (in certi casi si trovava all'inizio di un blocco, in altri alla fine). Anche questa spiegazione è corretta, ma ovviamente non è l'unica e non bastava indicare questa. - L'esercizio sull'individuazione delle dipendenze (che è una versione semplificata dell'esercizio 5.4 del libro di testo di Pacheco) chiedeva di considerare il frammento di codice seguente: #define N ... double A[N][N] = ...; double b[N] = ...; double x[N]; for (int i = N-1; i >= 0; i--) { /* (1) */ x[i] = b[i]; /* S1 */ for (int j = i+1; j < N; j++) { /* (2) */ x[i] += -A[i][j] * x[j]; /* S2 */ } x[i] /= A[i][i]; /* S3 */ } e spiegare se e come ciascuno dei cicli (1) e (2) poteva essere parallelizzato (gli statemente S1, S2, S3 li ho aggiunti io ora per semplificare la spiegazione seguente). Come detto a lezione, quando si cercano delle dipendenze tra le iterazioni di cicli occorre considerare esclusivamente le variabili che vengono modificate nelle iterazioni; sono infatti le operazioni di scrittura quelle che possono causare problemi. Nel nostro caso, le operazioni di scrittura sono tutte relative al contenuto dell'array x[] (non viene modificata la matrice A[][]). Iniziamo a considerare i ciclo esterno (1). Esaminando il codice osserviamo che il valore x[i] dipende dai valori x[j] con j=i+1, ..., N-1. Il diagramma delle dipendenze è il seguente: i=0 i=1 i=2 i=N-1 S1 +---S1 +---S1 +---S1 | +-- | -----+ | | | | +-- | -------- | ---- | | v +-- v -------- v ---- .... ---+ v S2<--+ S2 S2 S2 | | | | | | | | v v v v S3 S3 S3 S3 (mi scuso per l'"ASCII art" scadente; ci sono delle frecce che vanno dall'istruzione S1 delle iterazioni i+1, i+2, ... N-1 verso l'istruzione S2 dei ciascuna iterazione i). l'istruzione S2 dell'iterazione i dipende dalle istruzioni S1 delle iterazioni i+1, i+2, ... N-1. NOTA: S2 è all'interno del ciclo (2), quindi più che una singola istruzione rappresenta una sequenza di istruzioni. Dal diagramma si vede che non è possibile eseguire le iterazioni del ciclo (1) in un ordine qualsiasi, dato che sono presenti delle dipendenze. Tali dipendenze non sono eliminabili: non basta proteggere l'istruzione S2 con una direttiva "omp atomic" o "omp critical" come qualcuno ha suggerito, dato che la direttiva atomic/critical non garantisce che le iterazioni del ciclo (1) vengano eseguite esattamente nell'ordine in cui sono indicate (cosa essenziale in questo caso per garantire la correttezza). Una volta appurato che il ciclo (1) non si può parallelizzare, consideriamo il ciclo (2). Si vede che tutte le iterazioni del ciclo (2) modificano lo _stesso_ elemento x[i]; di conseguenza, il ciclo _non è_ banalmente parallelizzabile in quanto le iterazioni _non_ sono indipendenti. Tuttavia, riconosciamo che il ciclo calcola una riduzione su x[i] con l'operatore summa, che può essere gestita con una clausola "reduction". | NON È CORRETTO AFFERMARE CHE "NON CI SONO DIPENDENZE TRA LE | ITERAZIONI DEL CICLO (2) PERCHÉ I THREAD LEGGONO VALORI x[j] E | MODIFICANO x[i] con i