Esercizi
Scrivi un’implementazione in virgola fissa del generatore di Mandelbrot.
a.
Si noterà che la performance non è coerente tra diversi pixel e diversi frame. Perché?
b.
Qual è l’intensità aritmetica del corpo del ciclo più interno, in operazioni per byte acceduto dalla memoria? Qual è il limite di prestazione corrispondente per la tua CPU ARM? Come si confronta con le tue prestazioni osservate?
c.
Misura le seguenti metriche di prestazione per il corpo del ciclo più interno:
▪
istruzioni per iterazione
▪
istruzioni per operazione
▪
CPI
▪
cache miss rate
d.
Utilizza l’assemblaggio in linea per implementare il corpo del ciclo più interno e misura l’impatto sulle prestazioni rispetto alle metriche della parte c. Qual è l’aumento di velocità rispetto al codice generato dal compilatore?
Parallelizza il generatore del set di Mandelbrot usando OpenMP. Applica la direttiva parallel-for al ciclo più esterno (riga).
a.
Misura il numero medio di cicli richiesti per ogni iterazione del ciclo più interno (per valutare il polinomio) per un thread e due thread per il frame iniziale. Usa queste misure per calcolare la velocità, in termini di pixel al secondo, di due thread rispetto a un thread.
b.
Misura il tempo per calcolare tutti i pixel nel primo fotogramma quando usi il programma dinamico rispetto al programma statico.
Cosa rende difficile applicare l’operazione SIMD per il generatore del set di Mandelbrot? Qual è il metodo più efficiente per applicare l’operazione SIMD per il generatore di set di Mandelbrot?
Misurare il throughput di scrittura effettivo per il framebuffer di Linux. È equivalente al throughput di scrittura per un array di memoria allocato dall’heap?
Calcolare l’intensità aritmetica del programma di trasformazione delle immagini in operazioni per pixel. Qual è il suo limite di prestazione dato il throughput di memoria effettivo della tua CPU ARM? Come si confronta con le tue prestazioni osservate?
Utilizza OpenMP per aggiungere il supporto multicore al programma di trasformazione dell’immagine a virgola fissa. Per farlo, applica il pragma parallel for al ciclo più esterno (riga).
Misura le sue prestazioni su una CPU ARM a quattro core. Come scalano le sue prestazioni se eseguite con uno, due, tre e quattro thread?
Utilizza le intrinseche per aggiungere il supporto NEON SIMD alla versione a virgola fissa del programma di trasformazione delle immagini. Usa le operazioni a quattro vie per calcolare i seguenti calcoli per un gruppo di quattro pixel: posizione del pixel sorgente, estrazione della frazione e calcolo del peso. In che misura questo migliora le prestazioni?
Non possiamo facilmente ottimizzare il programma generatore di Mandelbrot usando istruzioni SIMD, poiché i pixel vicini possono richiedere un numero diverso di valutazioni del polinomio e ogni iterazione del polinomio dipende dalla valutazione precedente. Un approccio alternativo è quello di implementare il ciclo inline assembly, srotolarlo di almeno quattro, e poi usare il pipelining software per migliorare l’IPC del ciclo. In questo caso, dovremmo evitare i rami condizionali all’interno del ciclo srotolato. Poiché i valori c divergenti continueranno a divergere con le valutazioni successive, possiamo aspettare di controllare la condizione di uscita del ciclo dopo ogni gruppo di quattro iterazioni. Tuttavia, eseguire ulteriori valutazioni di polinomi dopo che un Pc() diverge potenzialmente al di fuori del cerchio di raggio-2 ci richiederà di tenere conto dei requisiti di intervallo aggiuntivi per il nostro formato a punto fisso. Ricalcolate i requisiti dell’intervallo a virgola fissa per questa ottimizzazione e determinate fino a che punto questo ridurrà il livello massimo di zoom.
I principali vantaggi del punto fisso sono la riduzione della latenza delle operazioni e la possibilità di evitare le conversioni di tipo in certi tipi di codici grafici. Il capitolo 2 evidenzia un esempio di programma le cui prestazioni sono sensibili alla latenza delle operazioni, il metodo di Horner. Supponendo di poter tollerare le limitazioni di range del punto fisso nel nostro codice del metodo di Horner, convertirlo in punto fisso migliorerebbe le prestazioni? Spiegate la vostra risposta.
La sezione 3.6.5 ha mostrato due diverse implementazioni di una macro del preprocessore per l’addizione in punto fisso generalizzata. La prima è stata generata da gcc sotto massima ottimizzazione, la seconda è stata codificata a mano usando il linguaggio assembly inline. Entrambe le implementazioni hanno richiesto approssimativamente lo stesso numero di istruzioni.
a.
Mostra le dipendenze dei dati read-after-write in entrambe le implementazioni. Supponendo che il processore usi istruzioni singole, in ordine di emissione, e supponendo che la latenza di tutte le operazioni aritmetiche intere sia di quattro cicli, quanti confrontare il numero di cicli di stallo dei dati necessari per entrambe le implementazioni.
b.
Riscrivere la versione inline assembly della macro di addizione a virgola fissa per programmare le istruzioni in modo che le istruzioni dipendenti siano separate il più possibile. In che misura si riducono gli stalli, assumendo la latenza data nella parte a?
c.
Scrivi del codice che dimostri come tutte e tre le implementazioni (generate dal compilatore, inline assembly e programmate inline assembly) possano essere caratterizzate per le prestazioni.
In questa domanda esaminiamo l’implementazione inline assembly della moltiplicazione a virgola fissa generalizzata descritta nella Sezione 3.6.6.
a.
Come si confronta, in termini di numero di istruzioni e prestazioni di runtime, con il codice equivalente generato dal compilatore per:
res = (((long long)op1 * (long long)op2) >> (rp1>rp2?rp1:rp2)) +(rp1>rp2 ? ((((long long)op1 * (long long)op2) >> (rp1-1))&1) :
((((long long)op1 * (long long)op2) >> (rp2-1))&1));
Assicurati di usare gli switch “-O3” e “-marm” quando compili con gcc.
b.
Programmate le istruzioni della versione inline assembly della macro multiply per minimizzare gli stalli da dipendenza dei dati. Misurate le sue prestazioni rispetto alla versione data nella Sezione 3.6.6.
c.
Per l’implementazione inline assembly, quanto in più si ottiene se si cambia in modo che le posizioni dei punti radix siano fisse invece che variabili come nel codice? Per questa domanda, usa sia il numero di istruzioni che il comportamento effettivo di runtime.
Calcolare i valori dei pixel per un set di Mandelbrot richiede una funzione per convertire il numero di iterazioni nei canali di colore R, G e B. Impostare tutti e tre i canali allo stesso valore genererà un’immagine grigia, quindi la pendenza di ogni funzione del canale di colore dovrebbe essere unica, e quale pendenza è più grande determinerà la tonalità dell’immagine.
Come descritto nella Sezione 3.8.1, il numero di valutazioni del polinomio può superare il valore che supera l’intervallo di un canale di colore. Per evitare un potenziale overflow, dovete usare l’aritmetica saturante quando calcolate ogni valore di pixel. In questo modo, se il valore calcolato supera il valore massimo consentito, lo imposti al valore massimo.
Scrivi una macro C che esegue una moltiplicazione saturante a 8 bit senza segno. La funzione prenderà due operandi a 8 bit e produrrà un prodotto a 8 bit impostato su 255 se il prodotto supera 255. La macro non deve includere istruzioni di ramo ed essere programmata per le dipendenze dai dati.
Questo esercizio esplorerà l’aumento della precisione dei tipi a virgola fissa per il generatore di Mandelbrot a 64 bit.
a.
Utilizzando un tasso di zoom di 1.5zoom, a quale livello si può ingrandire il fotogramma prima di superare questa precisione?
b.
Definire una macro in C per aggiungere due (64,56) valori a virgola fissa. La macro può eseguire l’addizione a 128 bit usando quattro addizioni a 32 bit e usare il flag di trasporto per implementare i trasporti da ogni gruppo di 32 bit al successivo gruppo di 32 bit più significativo.
c.
Definire una macro in C per moltiplicare due valori a virgola fissa (64,56). Costruite questa macro sopra la macro di addizione a 64 bit della parte b.
Come mostrato nella figura 3.6, un modo semplice per eseguire un moltiplicatore a 64 bit è quello di eseguire una serie di quattro operazioni di moltiplicazione/shift/accumulazione a 32 bit che producono ciascuna un risultato a 64 bit.
Figura 3.6. Un moltiplicatore a 8 bit implementato con moltiplicatori a 4 bit.
Nella figura, due valori a 4 bit A e B con valori 1110 e 1410 sono separati ciascuno in due porzioni superiori e inferiori a 2 bit, chiamate A1, A0 e B1 e B0. Assumendo che i prodotti siano a 4 bit, il prodotto a 8 bit è calcolato come (A1*B1) ≪ 4 + (A1*B0) ≪ 2 + (A0*B1) ≪ 2 + (A0*B0).
Per applicare questo a una moltiplicazione a 64 bit, ognuno dei due valori a 64 bit deve essere tenuto in due registri a 32 bit. Ogni moltiplicazione genera un risultato a 64 bit, consentendo un prodotto finale a 128 bit.
d.
Utilizzando queste macro, implementate un generatore di set di Mandelbrot a 64 bit e misurate la differenza di prestazioni risultante.
e.
Implementate entrambe le macro nel linguaggio assembly in linea e misurate la velocizzazione del risultato del generatore di Mandelbrot rispetto a quello della parte d.