Ottimizzazione pipe-line

Daniele Marini Da: Akinen-Möller

Corso Di Programmazione Grafica

Introduzione

• Parliamo di ottimizzazione a basso livello

• Ottimizzazione ad alto livello riguarda il programma applicativo– Es: usare o non usare una organizzazione

spaziale dei dati• A basso livello si considera la pipeline• Una prima soluzione è usare stringhe

di triangoli e di mesh

2

Strisce di triangoli• Possiamo spedire un triangolo alla

pipeline inviando 3 vertici per ogni triangolo

• Non è efficiente• Le strisce di triangoli o di mesh

sfruttano informazione locale

3

Esempio

• In generale i triangoli non sono isolati ma fanno parte di di gruppi anche molto grandi

4

Strisce di triangoli

• Senza strisce: 8 triangoli * 3 vertici = 24 vertici• Con strisce: si usa 1 vertice per triangolo invece di 3

Spediamo al graphics hardware: Costo di strartup: v0, v1 in seguitov2 (T0), v3 (T1), v4 (T2), v5 (T3), v6 (T4), v7

(T5), v8 (T6), v9 (T7). 9 vertici 100*9/24= 37.5% ovvero 9/8=1.125 vertici/triangolo

v0

v1

v2

T0

v3

T1

v4

T2

v5

T3

v6

T4

v7

T5

v8

T6

v9

T7

5

Strisce di triangoli

• 9 vertici invece di 24 – 100*9/24= 37.5% di dati spediti– 9/8=1.125 vertici/triangolo

• Possiamo attenderci che l’hardware grafico migliori le prestazioni del 37%

• OpenGL: glBegin(GL_TRIANGLE_STRIP);• La definizione di strisce di triangoli impone

un orientamento a ogni triangolo

6

Cambi di orientamento nelle strisce

• Cosa possiamo fare in questo caso?

Implementare uno swap! Costo di Startup: v0, v1 quindi

– v2 (T0)– v3 (T1)– v2,– v4 (T2)– v5 (T3), v6 (T4)

– Triangolo degenerato v2v2v27

Swaps…

• Costo del triangolo degenerato 1 extra vertice

• Sempre più economico che ricominciare a spedire una nuova strisca

• Esempio: 8 vertici spediti / 5 triangoli = 1.6 vertici/triangolo

• Ricominciare la striscia costa di più:– 4 vertici (2 triangoli) +– 5 vertici (3 triangoli)

8

Swaps…• Inoltre, hardware determina triangoli degenerati

in modo efficiente e li salta• Si può usare lo swap anche per connettere

triangoli non connessi: – Evitare overhead di chiamate di API– Hardware ha bisogno di una cache per essere

efficientev0

v1

v2

T0

v3

T1

v4

v5

v6

T2

v7

T3

Spedisci questi vertici: 0,1,2,3, 3,4, 4,5,6,7 10 vertici (spediti come 2 strips: 8 vertici) Se 3 e 4 sono cached, allora 8 vertici

Crea4 triangoli degenerati

9

Come creare le strisce dai modelli 3D?

• A mano– Fattibile per modelli piccoli, noioso …

• NVIDIAs NVTriStripper (cercare su web)

• Fare un proprio programma– Occore conoscere i triangoli del

vicinato– Vedi su Haines-Möller

10

Meshes di triangoli

• Specificare i vertici una volta sola nel buffer

• Quindi spedire (e.g., 16 bit) gli indici per individuare i vertici nel buffer

• Es: crea un buffer di 100 vertici singoli– Un triangolo viene spedito come 3 indici

nel buffer: 97, 5, 32

• Cosa interessante: gli indici possono essere spediti com strisce di triangoli

11

Vertex arrays (OpenGL) vertex buffers (DirectX)

• Memorizza i vertici in modo sequenziale in memoria

• Passa alle API solo il puntatore• L’API stessa copia i dato dalla memoria• Evita di eseguire copie costose

12

Ottimizzazione della pipeline

• ”Premature optimization is the root of all evil”, Donald Knuth

• Prima far funzionare il programma poi ottimizzare!

• Ma ottimizzare solo se vale la pena• Occorre trovare i colli di bottiglia e

come liberarsene

13

Ottimizzazione della pipeline

• Prima provare a modificare l’algoritmo– Es: tecniche di culling, strutture dati spaziali ecc.

• Quando siamo quasi soddisfatti:– Affrontare le tecniche di ottimizzazione (appunto:

alla fine!)

• I tre stadi principali:– Applicazione– Geometria– Rasterizzazione

• L’ottimizzzazione può essere fatta in ogni stadio

14

La pipeline

• Gli stadi sono eseguiti in parallelo• Lo stadio più lento è il collo di bottiglia• Il collo di bottiglia determina il throughput (cioè

la velocità massima)• Il collo di bottiglia si può individuare in un

singolo frame, non ”intra-frame”

15

Trovare il collo di bottiglia

• Due tecniche• Prima:

– Far lavorare di meno un certo stadio– Se le prestazioni migliorano allora questo è un collo di

bottiglia

• Seconda tecnica:– Far lavorare di meno gli altri due stadi (o escluderli del

tutto) – Se le prestazioni non cambiano allora lo stadio escluso è

il collo di bottiglia

• Complicazione: il bus tra CPU e scheda grafica può essere il colllo di bottiglia (non è uno stadio)

16

L’applicazione (CPU) è il collo di bottiglia?

• Usare una funzione di monitor dei task del sistema (top su Unix, TaskManager su Windows).– Se l’applicazione usa (quasi) il 100% di CPU time, allora

molto probabilmente è il collo di bottiglia– Ridurre il carico di CPU (e.g., disattiva collision-detection)– Rimpiazza glVertex e glNormal con glColor

• Le fasi di geometria e rasterizzazione non fanno quasi nulla• Non ci sono vertici da trasfomare, o normali con cui calcolare la luce

o triangoli da rasterizzare

• Il vostro programma è ”CPU-bound”, o ”CPU-limited”?

17

La geometry stage è il collo di bottiglia?

• É lo stadio più difficile da testare• Infatti in questo caso cambiano anche le

prestazioni dell’applicazione e della rasterizzazione

• Però è il calcolo della illuminazione che influisce lo stadio di geometria

• Provare a disabilitare le sorgenti di luce– Se le prestazioni migliorano allora la geometry è lo stadio

critico e il programma è ”transform-limited”

• Test negativo: abilita tutte le sorgenti di luce– Se le performance non migliorano allora la geometria

NON è il collo di bottiglia

18

Lo stadio di rasterizzazione è il collo di bottiglia?

• Il più facile e veloce da testare• Ridurre la dimensione della window • Questo non cambia il carico dell’applicazione e

della geometria• Ma il rasterizzatore deve calcolare meno pixel• Se le performance migliorano, il progamma è

”fill-limited” o ”fill-bound”• Si può anche ridurre il carico di lavoro del

rasterizzatore:– Disabilita texturing, fog, blending, depth buffering etc

19

Torniamo alla ottimizzazione primo trucco:

Conoscere l’architettura su Conoscere l’architettura su cui si lavora!cui si lavora!

20

Ottimizzazione

• Ottimizza lo stage collo di bottiglia• Fare piccole modifiche finchè si

vedono miglioramenti.• I miglioramenti sono suffucienti?• Si! Fermati!• NO! Continua ad ottimizzare finchè

vedi miglioramenti.

21

Esempio

• La barra indica il tempo per un frame

• La barra più alta è il collo di bottiglia

AP

P

GE

OM

RA

ST

10 ms

0 ms

20 ms

30 ms

40 ms

50 ms

AP

P

GE

OM

RA

ST

10 ms

0 ms

20 ms

30 ms

40 ms

50 ms

Ottimizza lo stadio geometry

Dopo l’ottimizzazione il collo di bottiglia è passato alla applicazione

Inutile continuare su GEOM, passare a APP 22

Ottimizzazione della APP:acune idee

• 2 vie:– Codice efficiente

• Ridurrre i numero di istruzioni• Usare instruzioni + efficienti• Ricodificare gli algoritmi

– Criteri di accesso a memoria efficienti• Ma prima:

– Attiva opzioni di ottimizzazione nel compilatore– Sono molto utili profilers del codice

• Aiutano a trovare i punti in cui si impega più tempo• È spesso inutile ottimizzare parti che consumano solo 1%

del tempo

• Tutto ciò richiede tempo

23

Alcune tecniche di ottimizzazione del codice

• Istruzioni tipo SIMD sono perfette per operazioni su vettori– Spesso vengono eseguite 2-4 operazioni in parallelo

• La divisione è una operazione costosa!– Tra 4 e 39 volte + lenta di altre istruzioni– Es: normalizzare un vettore, v

• Invece di v=(vx/d,vy/d,vz/d)• d=v.v• i=1/d• v=v*i

– In alcune CPUs sono disponibili calcoli per il reciproco e il reciproco del quadrato: (1/x); (1/sqrt(x))

24

Altri trucchi

• Test condizionali sono costosi– Se potete evitare if, fatelo!– Tuttavia a volte predizioni su salti condizionali sono

implementate in modo motlo efficiente su CPU

• Funzioni matematiche come: sin, cos, tan, sqrt, exp, etc sono costose!– A volte è sufficiente una approssimazione grossolana– Ad esempio usate solo i primi termini di uno sviluppo in serie

di Taylor

• Codice Inline (versus behind) è efficace(evita chiamate di funzioni)

• float (32 bits) è più veloce di double (64 bits)– Inoltre si spediscono meno dati alla pipeline

25

Ancora trucchi per il codice• Provate diverse strategie

– Ottimizzazioni del compilatore sono difficili da prevedere– E.g., in C qualche volta --counter; è più veloce di counter--;

• Usare const in C and C++ per aiutare il compilatore

• Queste tecniche spesso producono overhead– Dynamic casting (C++)– Virtual methods– Inherited constructors– Passing struct’s per valore

26

Ottimizzazione della memoria

• Siate consapevoli delle gerarchie di memoria nei computer moderni (cache)

• Cattive soluzioni di accesso a memoria possono danneggiare le prestazioni

• A volte usare poca memoria può aiutare …

27

Trucchi sulla ottimizzazione della memoria

• Se alla memoria si accede in modo sequenziale, adottare strutture dati sequenziali :– Tex coords #0, position #0, normal #0, tex

coords #1, position #1, normal #1 tex coords #2, position #2, normal #2, etc.

• Cache prefetching è molto utile– Difficile da controllare

• malloc() and free() può essere lento– A volte allocare all’inizio del programma un

pool di memoria può aiutare

28

Ancora sulla memoria• Allineare la dimensione dei dati alle dimensioni

della cache– Es: In motli Pentium, la dimensione di una locazione di

cache è 32 bytes– Se per memorizzare un vertice ci voglionio 30 bytes

allora fare un padding con altri 2 bytes 32 bytes– Questo può migliorare molto le prestazioni della cache

• Inseguire puntatori (linked list) è costoso (in particolare se la memoria è allocata in modo arbitrario)– Non si usa alcuna coerenza che la cache può sfruttare– Ovvero un indirizzo appena usato potrebbe essere

usato nuovamente con alta probabilità

29

Ottimizzazione dello stadio Geometry

• Esegue operazioni per-vertice• Il miglior modo di ottimizzare:

– Triangle strips!!!

• Ottimizzazione della fase di lighting– Spot lights sono costosi, point light più

economici, directional light la più economica– Disabilitare le luci appena possibile– Usare il minor numero di luci possibile

• Se ad es: la riduzione segue la legge 1/d2 e d>10 meglio disabilitare del tutto la luce

30

Ottimizzazione GEOM

• Le normali vanno normalizzate per ottenere illuminazione corretta– Normalizzare in anticipo

• L’illuminazione potrebbe essere computata per entrambi i lati di un triangolo– Se non è necessario: disabilitare!

• Se le sorgenti di luce sono statiche rispetto alla geometria e il materiale è puramente diffusivo:– Pre-computare l’illuminazione nella CPU– Spedite soltanto i colori ai vertici precomputati e non le

normali

31

Ottimizzazione della rasterizzazione

• La rasterizzazione eseque operazioni per-pixel

• Un modo semplice: disabilitare il backface culling

• Disabilitare lo Z-buffering se possibile– Es: dopo un clear-screen, disegnare un grande

poligono di background– Usare BSP trees con poligoni allineati agli assi

• Disegnare nell’ordine front-to-back• Provate a disabilitare: texture filtering, fog,

blending, multisampling32

Ottimizzazione RASTER

• Ridurre il numero di pixel da rasterizzare– Ridurre la dimensione della window– Rendere con texture più piccole, quindi

allargarle a schermo

• Un fattore di complessità è il numero di volte in cui un pixel viene scritto– Utile per comprendere il comportamento

di una applicazione

33