Ottimizzazione pipe-line Daniele Marini Da: Akinen-Möller Corso Di Programmazione Grafica aa...

Ottimizzazione pipe-line

Daniele Marini Da: Akinen-Möller

Corso Di Programmazione Grafica aa 2007/2008

Programmazione Grafica aa2007/2008

Introduzione

• Parliamo di ottimizzazione a basso livello

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

spaziale dei date• A basso livello si considera la pipeline• Una prima soluzione è usare striche 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


Triangle strips

• 9 vertices instead of 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 orinetamneto 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

(chioè 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: abilità tutte le sorgenti di luce– Se le performance non migliorano allora la gemoetria

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 matematiceh come: sin, cos, tan, sqrt, exp, etc sono costose!– A volte è sufficiente una approssimazione grossolana– Se p così usate solo i primi termini di uno sviluppo i serie

di Taylor

• Codice Inline è buono (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 qualch evolta --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 gerarchied i 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, tex coords #1,

position #1, tex coords #2, position #2, etc.• Cache prefetching è molto utile

– Difficile da controllare• malloc() and free() può essere lento

– A volte allocare ll’inizio del programma un pool di memoria può aiutare

28


Ancora sulla memoria• Allineare la diimenzione dei dati alle dimenzioni

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

cache è 32 bytes– S per memorizzare un vertice ci voglioni 30 – 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– Ovver un indirizzo appena usato potrebbe essereusato

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 noramli vanno normalizzate per ottenere illuminazione corretta– Normalizzare in anticipo

• Lìilluminazione potrebbe esere 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 diffusico:– Pre-computare l’illuminazione nella CPU– Spedite soltanto i colori ai vertici precomputati e non le

normali

31


Ottimizzazione della rasterizzazione

• La rasterizzazione eseque opreazioni per-pixel

• U modo sempice: disabilitare il backface culling e possibile

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

poligono di background– Usare BSP trees on 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

Ottimizzazione pipe-line Daniele Marini Da: Akinen-Möller Corso Di Programmazione Grafica aa...

Documents

Transcript of Ottimizzazione pipe-line Daniele Marini Da: Akinen-Möller Corso Di Programmazione Grafica aa...