Prova scritta di High Performance Computing del 10 gennaio 2024 =============================================================== Alcune osservazioni: Come detto all'inizio dell'esame, è stato assegnato punteggio parziale alle risposte non del tutto complete, oppure scritte in maniera non adeguata dal punto di vista grammaticale. Come da regole d'esame, il voto massimo assegnato è 30; tuttavia, si terrà conto degli eventuali punti eccedenti per assegnare la lode in caso di progetto di qualità particolarmente elevata. ------------------------------------------------------------------------------ AGGIORNAMENTO 16/1/2023: chi intende rifiutare il voto e ritentare la prova scritta deve darmene comunicazione via mail in modo che possa registrare "rifiutato" su AlmaEsami. Invito a riflettere con la massima serietà prima di rifiutare una valutazione sufficiente. ------------------------------------------------------------------------------ - Prima domanda (speedup superlineare). A lezione sono stati menzionati tre possibili motivi per uno speedup superlineare: (i) l'uso di parallelismo eterogeneo (es., la CPU della Playstation3 dispone di otto coprocessori vettoriali basati su una architettura diversa dai core della CPU, e se usati possono produrre speedup superlineare rispetto ad un programma equivalente che gira sui core della CPU); (ii) l'uso migliore della cache che si può verificare se la dimensione del "working set" di ciascun thread diminuisce all'aumentare del numero di thread; (iii) nel caso della programmazione SIMD, si può osservare uno speedup superlineare causato dalla diminuzione del numero di istruzioni che devono essere recuperate dalla RAM per l'esecuzione. Chi ha descritto e motivato correttamente una delle cause precedenti ha ottenuto 7 punti; chi ne ha descritte almeno due ha ottenuto 8 punti. Esiste anche una ulteriore spiegazione, e cioè che il calcolo dello speedup sia fatto in modo non del tutto corretto utilizzando un programma seriale sviluppato appositamente, anziché il programma parallelo con P=1 processori. Chi ha scritto solo questa motivazione ha ottenuto 6 punti, in quanto è tecnicamente corretta ma meno rilevante delle motivazioni sopra. La legge di Amdahl non è rilevante per questa domanda; non è corretto affermare che uno speedup superlineare è vietato dalla legge di Amdahl, dato che essa è una approssimazione che vale sotto certe ipotesi (ossia, la presenza di una porzione seriale il cui wall-clock time non cambi al variare di P; il fatto che il resto del codice ha un wall-clock time che cala come 1/P). Se le ipotesi non sono verificate, la legge di Amdahl non risulta valida. 2. (rimozione loop-carried dependences) Qualcuno ha suggerito di riallineare le iterazioni nel modo seguente (altre varianti simili sono state proposte): v[0] = 3; for (int i = 1; i < N-1; i++) { v[i+1] = v[i] + 1; } Nel codice precedente sono presenti due problemi: il primo è che il ciclo non inizializza v[1]. Occorrerebbe quindi scrivere: v[0] = 3; for (int i = 0; i < N-1; i++) { v[i+1] = v[i] + 1; } Oltre a ciò, nel ciclo è presente la stessa loop-carried dependence di prima: ogni iterazione usa il valore v[i] che viene modificato dall'iterazione precedente. Non può quindi essere considerata corretta. 3. (Tipi di memoria di una GPU) A lezione abbiamo visto la gerarchia di memoria di una GPU dal punto di vista del programmatore, più che dell'hardware. Di conseguenza, i tipi di memoria sono: memoria locale/registri, memoria shared, memoria globale/costanti/texture. Questi tipi di memoria fanno riferimento ai concetti di thread e blocchi, piuttosto che a quelli di streaming processor/streaming multiprocessor. Come detto a lezione la mappatura tra streming multiprocessor (SM) e thread/thread block/grid non è scontata. In particolare, lo stesso SM può esseguire contemporaneamente più thread block (si veda https://developer.nvidia.com/blog/cuda-refresher-cuda-programming-model/ ). I motivi che portano ad avere una gerarchia di memoria nelle CPU sono in parte diversi da quelli che portano ad avere una gerarchia di memoria della GPU. Nel caso delle GPU ci sono centinaia (in alcuni casi, migliaia) di unità di esecuzione che accedono in modo concorrente alla memoria, per cui nessuna tecnologia di memoria attualmente nota sarebbe in grado di sostenere in throughput richiesto. In alcune risposte si confonde causa con effetto. Ad esempio, la memoria di una GPU non è organizzata in quel modo per ottimizzare gli accessi adiacenti da parte dei thread di un warp, ma è il contrario. Gli accessi adiacenti da parte dei thread di un warp sono efficienti perché la memoria è organizzata in un certo modo (e perché l'hardware è in grado di raggruppare gli accessi per ridurre il numero di transazioni da/verso la memoria delle GPU). 4. (comunicazione MPI con deadlock) Il problema del codice fornito è che PUO' manifestarsi deadlock, ma non necessariamente si manifesta (la spiegazione è stata data a lezione). Di conseguenza sono state penalizzate le risposte dalle quali traspare che il deadlock si manifesti sistematicamente, o la cui spiegazione risulta confusa o non del tutto corretta (ad es., come detto a lezione la MPI_Send non ritorna quando il messaggio è stato "recepito" dal destinatario, come qualcuno suggerisce, né è in generale corretto affermare che il mittente riceva una sorta di conferma di invio). Esistono tre modi per risolvere il problema, in ordine crescente di preferenza: 1. fare in modo di invertire l'ordine di Send e Recv per almeno uno dei processi coinvolti; 2. Usare le versioni asincrone MPI_Isend/MPI_Irecv 3. Usare MPI_Sendrecv Si noti che MPI_Sendrecv _è_ una operazione di comunicazione collettiva. Lo schema di comunicazione illustrato nel frammento di codice non si può realizzare con una broadcast o scatter, come qualcuno suggerisce.