Corso Di Programmazione Grafica aa 2007/2008
Ottimizzazione pipe-line
Daniele Marini
Da: Akinen-Möller
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
Programmazione Grafica aa2007/2008
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
Programmazione Grafica aa2007/2008
3
Esempio
• In generale i triangoli non sono isolati ma
fanno parte di di gruppi anche molto
grandi
4
Programmazione Grafica aa2007/2008
Strisce di triangoli
• Senza strisce: 8 triangoli * 3 vertici = 24 vertici
• Con strisce: si usa 1 vertice per triangolo invece di
3v0
v2
v4
v6
v8
T0
T2
T1
v1



T4
T3
v3
T6
T5
v5
T7
v7
v9
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
Programmazione Grafica aa2007/2008
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
Programmazione Grafica aa2007/2008
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 v2v2v2
Programmazione Grafica aa2007/2008
7
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
Programmazione Grafica aa2007/2008
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 efficiente
v0
v2
v4
T0
v6
T2
T1
v1



T3
v3
v5
Crea
4 triangoli degenerati
v7
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
Programmazione Grafica aa2007/2008
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
Programmazione Grafica aa2007/2008
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
Programmazione Grafica aa2007/2008
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
Programmazione Grafica aa2007/2008
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
Programmazione Grafica aa2007/2008
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
Programmazione Grafica aa2007/2008
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”
Programmazione Grafica aa2007/2008
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)
Programmazione Grafica aa2007/2008
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”
Programmazione Grafica aa2007/2008
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
Programmazione Grafica aa2007/2008
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 19
Programmazione Grafica aa2007/2008
Torniamo alla ottimizzazione
primo trucco:
Conoscere l’architettura su cui si
lavora!
Programmazione Grafica aa2007/2008
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.
Programmazione Grafica aa2007/2008
21
Esempio
50 ms
50 ms
0 ms
APP
10 ms
RAST
30 ms
20 ms
RAST
10 ms
APP
20 ms
GEOM
30 ms
40 ms
GEOM
Ottimizza lo stadio
geometry
40 ms
0 ms
• La barra indica il tempo per un frame
• La barra più alta è il collo di bottiglia
Dopo l’ottimizzazione il collo di bottiglia è
passato alla applicazione
 Inutile continuare su GEOM, passare a
APP

Programmazione Grafica aa2007/2008
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
Programmazione Grafica aa2007/2008
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))
Programmazione Grafica aa2007/2008
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
Programmazione Grafica aa2007/2008
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
Programmazione Grafica aa2007/2008
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 …
Programmazione Grafica aa2007/2008
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
Programmazione Grafica aa2007/2008
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à
Programmazione Grafica aa2007/2008
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
Programmazione Grafica aa2007/2008
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
Programmazione Grafica aa2007/2008
31
le normali
Ottimizzazione della
rasterizzazione
• La rasterizzazione eseque opreazioni perpixel
• 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, multisampling
Programmazione Grafica aa2007/2008
32
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
Programmazione Grafica aa2007/2008
33