Algoritmi per la dinamica dei complessi simpliciali in GPU

(1)

Facolt`

a di Scienze Matematiche Fisiche e Naturali

Corso di Laurea Specialistica in Informatica

Algoritmi per la gestione della dinamica di

complessi simpliciali in GPU

Candidato

Guido Ranzuglia

Relatori:

Dott. Paolo Cignoni

Dott. Fabio Ganovelli

Controrelatore:

Prof. Roberto Grossi

(2)

alle pennellesse intrise del sudore di mio padre, a tutti i dolori che attanagliano le ossa di mia madre, all’azzurro di quegli occhi che rappresentano la meta.

(3)

Innanzi tutto non posso esimermi dal ringraziare i componenti del Vcg group del CNR di Pisa che mi hanno accolto, con grande dispendio di energie e risorse, presso di loro per poter compiere questo lavoro di tesi. Un grazie particolare va a Fabio e al prof. Cignoni. Senza le loro idee, i loro consigli e la loro presenza fisica nulla sarebbe stato. Grazie anche a tutte le giovani leve che nell’ultimo anno mi sono state sedute accanto: Andrea, Giuseppe, Valentino, Marco...e sicuramente ne dimentico qualcuno. Non certo Nico a cui `e, per forza di cose, dedicato un GRAZIE con tutte le lettere maiuscole...

(4)

Indice

1 Concetti introduttivi 5

1.1 La pipeline di rendering . . . 6

1.2 La prima generazione di Hardware grafico . . . 8

1.2.1 La prima scheda grafica . . . 8

1.2.2 Una possibile soluzioni alternativa . . . 10

1.2.3 Evoluzione del bus di trasferimento dati . . . 12

1.2.4 Transform & Lighting unit . . . 13

1.3 Dagli acceleratori grafici alle GPU . . . 14

1.3.1 Applicazioni, driver e API . . . 14

1.3.2 Pipeline grafica standard di OpenGL . . . 15

1.4 Limiti imposti dalla pipeline statica . . . 23

1.5 Vertex Shader . . . 24

1.5.1 Fragment Shader . . . 26

1.5.2 Ripercussioni dovute all’introduzione degli shader . . . 28

1.6 Linguaggi di shading . . . 29

1.7 Caratteristiche principali di OGLSL . . . 31

1.7.1 Tipi pre-definiti e definibili . . . 32

1.7.2 Attributi . . . 35

1.7.3 Variabili pre-definite . . . 36

(5)

INDICE 2

2 GPGPU 38

2.1 CPU vs GPU: qualche numero . . . 39

2.2 Linee guida nello sviluppo hardware . . . 40

2.2.1 Very Large Scale Integration . . . 41

2.2.2 Banda di trasferimento e latenza . . . 42

2.3 Indirizzi tecnologici per massimizzare la computazione . . . 42

2.4 Considerazioni sulle scelte architettoniche della CPU . . . 45

2.5 La GPU come stream processor . . . 46

2.6 Meccanismi hardware per il controllo sul flusso d’esecuzione . 49 2.7 GPGPU: Un esempio concreto . . . 51

2.8 Limiti e difficolt`a del GPGPU . . . 59

3 Elementi di fisica e di integrazione numerica 61 3.1 Mass spring . . . 62

3.2 Metodi di integrazione numerica . . . 63

3.2.1 Metodi di Runge Kutta . . . 64

3.2.2 Metodi impliciti . . . 65

4 Complessi simpliciali in GPU 67 4.1 Elementi e complessi simpliciali . . . 67

4.2 Gestione della dinamica dei complessi simpliciali . . . 70

4.3 Catena di masse in CPU . . . 71

4.4 Simulazioni fisiche in GPU . . . 74

4.4.1 Parametri di input di un fragment program . . . 74

4.4.2 Risultato di una computazione . . . 76

4.4.3 Interazione tra applicazione principale e shader . . . . 77

4.4.4 Tipi di dato . . . 81

(6)

INDICE 3

4.5.1 Masse e molle . . . 83

4.5.2 Difficolt`a implementativa del modello . . . 85

4.6 Una nuova strategia di calcolo . . . 89

4.6.1 Organizzazione di dati e texture . . . 90

4.6.2 il vertex-program . . . 91

4.6.3 Il fragment-program . . . 93

4.6.4 Condizioni al contorno . . . 94

4.6.5 Aggiornare la texture delle masse . . . 103

4.7 Render to texture . . . 107

4.8 Look-up di una texture da vertex program . . . 107

4.9 Interazione con il mouse . . . 110

4.10 Terza dimensione . . . 112

4.11 Complessi simpliciali di dimensione uno . . . 112

4.11.1 Texture di connettivit`a . . . 112

4.11.2 Accedere alla texture . . . 115

4.11.3 Massa . . . 115

4.11.4 Fragment-program . . . 116

4.12 Complessi simpliciali di dimensione due . . . 116

4.12.1 Fragment-program . . . 119

4.13 Complessi simpliciali di dimensione tre . . . 122

4.14 Eliminare simplessi . . . 123

5 Risultati sperimentali e sviluppi futuri 127 5.1 Tabelle dei risultati . . . 128

5.2 Commenti sui risultati ottenuti . . . 130

5.3 Sviluppi futuri . . . 133

(7)

INDICE 4 A Screenshot del simulatore 135 B Corrispondenza con la Nvidia 138 B.1 Bug nel compilatore . . . 138 B.2 Bug nel driver . . . 141

(8)

Capitolo 1

Concetti introduttivi

Lo sviluppo e la diffusione di hardware specializzato, destinato a supportare e coadiuvare la CPU nelle funzionalità di grafica, ha conosciuto nell’ultimo decennio un deciso incremento che fonda, in ultima analisi, la sua ragione di essere su solide basi economiche. Non solo l’industria dei videogiochi muove fatturati ormai paragonabili, se non superiori, a quelli dell’industria cine-matografica (che a sua volta, già dalla fine degli anni settanta, investe nel settore quantità ingenti di denaro) ma la necessità di simulazioni credibili ha ormai da tempo travalicato i limiti propri dell’intrattenimento per diffonder-si sempre maggiormente in campi come la medicina, la fidiffonder-sica, l’ingegneria e l’industria militare. Si è passati cos`ı in un tempo relativamente breve dalle workstation dedicate, immesse sul mercato a prezzi che le rendevano inac-cessibili ad un bacino di utenza che andasse oltre i laboratori di ricerca, alle moderne schede grafiche che rappresentano la dotazione basilare di qualsiasi personal computer di oggi giorno. Tratteggiare brevemente i passi intermedi di questo viaggio e sottolinearne le conseguenze immediate a livello software derivatene sara’ l’obiettivo preminente di questo capitolo.

(9)

CAPITOLO 1. CONCETTI INTRODUTTIVI 6

1.1 La pipeline di rendering

In computer graphics il termine rendering indica il processo tramite cui è possibile passare da una descrizione tridimensionale di una scena complessa (nella quale, ad esempio, siano stati definiti una camera virtuale, dei modelli 3D, i materiale di cui tali modelli sono composti ed una o più sorgenti lumi-nose) ad un’immagine bidimensionale della scena stessa facilmente rappre-sentabile sullo schermo di un pc. Fine ultimo di ogni hardware dedicato alla grafica è di velocizzare in maniera significativa tale processo di renderizzazio-ne 1 _{di modo da permettere un’interazione “confortevole” con la successione}

di immagini che appaiano sul monitor. Si `e soliti fissare il limite minimo di tale soglia di comfort sui 10 fps 2 _{. Sotto suddetto limite sopraggiunge una}

difficoltà oggettiva da parte dell’utente a rapportarsi con quanto gli viene mostrato sullo schermo; difficoltà che non di rado sfocia in un vero e proprio disagio fisico. È, altres`ı, interessante notare come, d’altro canto, oltre i 70 fps l’occhio umano non riesca a percepire sostanziali variazioni di frame-rate. Negli anni vari algoritmi e varie tecniche sono state definite per risolvere il problema del rendering; un approccio che si è dimostrato vincente nell’ambito della grafica 3D con real-time si basa sul tassellare in un insieme di poligoni (tendenzialmente triangoli) le entità geometriche che compongono la scena tridimensionale e di dare tale insieme in pasto ad una pipeline grafica.

Nella pipeline le diverse unità lavorano in parallelo elaborando, in un dato istante, ognuna una porzione di input diversa lungo il percorso di trasforma-zione da triangoli tridimensionali a pixel sullo schermo. È importante notare come nessuna assunzione sia fatta su dove tale pipeline sarà effettivamente

1_{Non a caso le prime schede grafiche venivano descritte con la locuzione “acceleratori} grafici”.

(10)

CAPITOLO 1. CONCETTI INTRODUTTIVI 7 eseguita; quello che si sta definendo è un ente concettuale per la risoluzione di un dato problema. Ovviamente quanti più stadi saranno lasciati alla CPU tanti più cicli di clock della CPU stessa saranno consumati per permettere il rendering della scena; con la conseguenza che tale tempo di calcolo si andrà a sommare con quello dovuto alla normale elaborazione dei dati dell’appli-cativo stesso. Nel caso di implementazione in hardware di un segmento del processo di rendering è invece possibile, per la durata di tale stadio, eseguire in parallelo la computazione che ha luogo sull’unità centrale con la compu-tazione affidata al settore di pipeline in questione. Sarà scelta e compito dei costruttori dell’hardware stesso decidere quali e quanti stadi implemen-tare su un supporto specifico e quali demandare alla CPU. Tale affermazione porta con se, come conseguenza, la necessità di una interfaccia software tra la pipeline di rendering e l’applicazione che si sta progettando, di modo da rendere trasparente al programmatore quante e quali parti di pipeline gra-fica siano effettivamente implementate su supporto dedicato e quante siano ancora demandate alla CPU.

Tre sono i blocchi principali di una pipeline grafica(fig. 1.1) :

- lo stadio dell’applicazione da cui escono i triangoli tridimensionali che costituiscono la scena da rappresentare

- lo stadio geometrico dove tali triangoli vengono mappati in manie-ra coerente(prospettiva,posizione della camemanie-ra) in coordinate 2D di schermo

- lo stadio finale di rastering in cui tali primitive sono scomposte in fram-menti a cui viene assegnato un colore per essere tradotte in immagini memorizzabili in un color-buffer 3.

(11)

CAPITOLO 1. CONCETTI INTRODUTTIVI 8 Di norma tali blocchi saranno suddivisi al loro interno in un numero variabile di sottoblocchi a cui viene affidata solo una porzione della computazione eseguita dallo stadio di pipeline suddetto.

Figura 1.1: Pipeline di rendering minimale

1.2 La prima generazione di Hardware

grafi-co

1.2.1 La prima scheda grafica

La tendenza che è andata affermandosi negli anni è stata quella, come ov-vio, di portare quante più porzioni di pipeline possibile sul supporto grafico

dello schermo, dove in posizione (x,y) verr`a inserito il corrispettivo colore che il pixel (x,y) dovr`a avere sul monitor del PC

(12)

CAPITOLO 1. CONCETTI INTRODUTTIVI 9 dedicato. Nel 1995 la 3dFx immise sul mercato “Voodoo”, universalmen-te riconosciuta come il primo acceleratore grafico low-cost della storia. La “Voodoo” si faceva carico al suo interno dello stadio di rastering (fig. 1.2). Se di primo acchito puo’ sembrare sorprendente scoprire che non sia stato lo stadio di trasformazione della geometria e di illuminazione ad essere imple-mentato ad hardware per primo, la cosa diventa decisamente più logica se si riflette su quanto in realtà sia piu’ pesante in una applicazione real-time (come un videogioco) la fase di rasterizzazione, in cui è frequente che un nu-mero di frammenti maggiori della totalità dei pixel dello schermo necessitino di essere processati per determinare il proprio colore.

Lo stadio geometrico era lasciato alla CPU che inviava, tramite bus Peri-pheral Component Interconnect (PCI), triangoli bidimensionali alla memoria locale alla scheda grafica; qui sarebbero stati presi in consegna dal rasterizza-tore che avrebbe provveduto a partizionare ogni triangolo 2D in una moltitu-dine di frammenti ed, inoltre, avrebbe associato a ciascuno di essi un valore di profondit`a prospetticamente coerente per determinarne successivamente la visibilit`a.

La Texture unit assegnava, quindi, ad ogni fragment la corrispettiva por-zione di texture, interpolando i valori associati ai vertici del triangolo cui il frammento stesso apparteneva.

Compito, infine, della raster operation unit (fig. 1.3) era quello di determi-nare come effettivamente il singolo fragment avrebbe influenzato l’immagine finale contenuta nella porzione del frame buffer riferita come color-buffer.

Sempre all’interno del frame-buffer era presente, inoltre, un’altra area di memoria, denominata z-buffer, il cui scopo era quello di contenere informa-zioni utili per arbitraggio della visibilit`a tra frammenti nel caso che due o piu’

(13)

Figura 1.2: Architettura della Voodo3 della 3dfx

di essi avessero concorso per l’assegnazione di un singolo pixel dello schermo4.

1.2.2 Una possibile soluzioni alternativa

Sebbene le mesh triangolari, come accennato in precedenza, siano la forma più comune di rappresentazione di un oggetto tridimensionale questo non si-gnifica, ovviamente, che non ce ne siano altre. In molti pacchetti applicativi CAD la geometria di un elemento 3D è definita da superfici matematiche; nella maggior parte dei casi Non-Uniform Rational B-Splines meglio note co-me NURBS. Oltre ad una moderatissima occupazione di co-memoria le NURBS presentano l’innegabile vantaggio di poter descrivere superfici smooth senza dover ricorrere, come accade con le mesh triangolari, ad un aumento con-siderevole della complessità geometrica della scena. Non deve, quindi,

sor-4_{Se un nuovo frammento si fosse sovrapposto ad uno gi`}_{a presente nel color-buffer,} quest’ultimo o veniva sovraimpresso oppure, nel caso di trasparenza, concorreva al colore finale del pixel conteso.

(14)

Figura 1.3: Stadio di rastering

prendere che in un passato non troppo remoto (1996) l’Nvidia avesse deciso di basare le sue prime schede grafiche su una particolare implementazione delle NURBS stesse: le quadratic texture maps. Come il nome suggerisce le quadratic texture maps erano l’implementazione di una generica superficie quadratica di equazione:

ax2+ by2+ cz2+ dxy + exz + f yz + gx + hy + iz + j = 0 (1.1) Il sostantivo texture sta indicare come non ci fosse alcuna distinzione forma-le tra la geometria e la tessitura che ne avrebbe dovuto arricchire l’aspetto. La texture, cio`e, non era attaccata sopra il modello tridimensionale, come avviene normalmente, ma essa stessa delimitava i contorni dell’oggetto 3D che si andava a visualizzare. A dispetto di un’eleganza matematica e di una resa effettiva superiore a qualsiasi altra periferica grafica dell’epoca la

(15)

CAPITOLO 1. CONCETTI INTRODUTTIVI 12 soluzione non ebbe seguito principalmente per una sorta di divergenza tem-porale con le linee guida nello sviluppo del software multimediale di quegli anni. Nello stesso periodo della NV1, infatti, si andarono ad affermare API grafiche come Direct3D ed OpenGL entrambe orientate alla gestione di poli-goni. `E superfluo specificare come applicazione scritte sfruttando tali librerie non ricevessero alcun beneficio da schede grafiche che perseguivano filosofie totalmente diverse.

Sebbene l’NVidia fosse talmente convinta della bontà del suo approccio (tanto da rischiare il fallimento economico per produrre una seconda genera-zione di schede quadratic oriented) è convinzione oggi comune che sia stato un bene per la storia della computer graphics che tale approccio non abbia avuto successo. Non solo i triangoli sono entità matematiche più semplici e quindi più facilmente gestibili rispetto alle NURBS, ma soprattutto senza alcuna distinzione tra texture e geometria sarebbe stato estremamente diffi-cile creare algoritmi generali per fare clipping dei vertici non visibili; senza contare, infine, che una volta spezzata una quadratica genera due superfi-ci geometriche di grado superiore; le quali, quindi, non avrebbero potuto beneficiare dei vantaggi offerti dalla scheda grafica stessa.

1.2.3 Evoluzione del bus di trasferimento dati

Nel 1998 nVidia, oramai scesa a piu’ miti consigli, ed ATI, introducono ri-spettivamente la TNT e la Rage. Oltre alla capacità di poter influenzare il colore di un pixel basandosi su più di una texture (multi-texturing) queste due nuove classi di acceleratori grafici erano le prime a sfruttare un nuovo tipo di bus per velocizzare il trasferimento dei dati dalla memoria principale alla memoria dedicata del supporto hardware. Si passava cos`ı dal PCI, a con-nessione parallela e condivisa tra più periferiche, alla AGP con connessione

(16)

CAPITOLO 1. CONCETTI INTRODUTTIVI 13 seriale (protocollo più semplice quindi scalabile) dedicata esclusivamente alla comunicazione con la scheda grafica e con una memoria propria che, pur non essendo locale alla scheda video permette a quest’ultima, ad esempio, di fare look up delle texture. La velocità base di una comunicazione AGP tra CPU e hardware grafico (e solo in questa direzione) è due volte quella consentita dalla normale PCI.

Storia di oggigiorno `e l’affermarsi di un nuovo standard: la PCI-Express; seriale e dedicata come la AGP ma che consente una velocita’ sedici volte superiore della PCI originale (quindi il doppio rispetto ad una AGP8x) e non a senso unico, cio`e full-band sia da CPU verso la scheda video sia nel percorso inverso.

1.2.4 Transform & Lighting unit

Tra il 1999 ed il 2000 tramite la definizione della Transform & Lighting Unit (T&L) all’interno di schede come la GeForce2 o la ATI 7500, anche lo sta-dio geometrico venne spostato dalla CPU sull’acceleratore grafico; liberando, cos`ı, definitivamente il processore centrale dal carico di calcolo dovuto all’e-secuzione dei blocchi della pipeline standard. In figura 1.4 `e presentata una tipica T&L unit.

La commercializzazione su larga scala dei sopracitati modelli segna la fine di una fase evolutiva importante nella definizione delle caratteristiche del moderno hardware grafico. Le funzionalit`a dell’acceleratore grafico ven-gono sfruttate appieno sia dalla comunit`a scientifica che dalle case produt-trici di software (modellatori e videogame) delineando e suggerendo nuove direzioni verso lo sviluppo di un chipset dedicato alla grafica completo e programmabile.

(17)

Figura 1.4: Transform and Lighting unit

1.3 Dagli acceleratori grafici alle GPU

Per poter meglio comprendere ed apprezzare le potenzialità insite nella suc-cessiva generazione di hardware grafico è opportuno osservare con maggior grado di dettaglio sia come avvenga l’interazione tra una applicazione grafica ed il device sottostante, sia cosa accada allorquando tale interazione termini e il supporto hardware è pronto ad assumersi l’onere di completare il processo di rendering.

1.3.1 Applicazioni, driver e API

Tipicamente qualsiasi applicazione che sfrutti una componente hardware del calcolatore `e, di fatto, suddivisa in due sottosistemi: la parte

(18)

dell’applica-CAPITOLO 1. CONCETTI INTRODUTTIVI 15 zione vera e propria (che si occupa della logica del programma e che concet-tualmente e’ indipendente dallo specifico supporto fisico su cui tale processo venga eseguito) e la parte a cui si è soliti riferirsi con il termine di driver, il cui compito preminente è quello di presentare i dati che il device dovrà ela-borare in una forma “comprensibile” al device stesso. È importante notare come il driver da solo non sia sufficiente a rendere l’applicazione hardware independent. Per fare ciò è necessaria la presenza di un ulteriore strato soft-ware (Application Programming Interface) che implementi una interfaccia astratta, comune a tutta un’intera classe di supporti hardware corrisponden-ti. Nel nostro caso i supporti hardware da astrarre sono, ovviamente, tutte le varie tipologie di schede grafiche che le industrie del settore immettano sul mercato.

Come abbiamo precedentemente accennato , OpenGL e Direct3D sono divenute, dalla metà degli anni ’90, la base per lo sviluppo di applicazioni grafiche real-time. Sebbene nell’approccio presentino sostanziali differenze (Direct3D, più che rimanere un’API vera e propria, come accade per Open-GL, è effettivamente un Software Development Kit ) le due filosofie, comun-que, vivono di forti punti di contatto. In ultima istanza la vera differenza tra le due API è che mentre OpenGL resta system operating independent, Direct3D, essendo diretta filiazione della Microsoft, è totalmente Windows oriented.

Per il resto della trattazione si assumer`a OpenGL come Application Pro-gramming Interface di riferimento.

1.3.2 Pipeline grafica standard di OpenGL

L’insieme delle funzionalit`a che OpenGL espone al programmatore, rappre-sentano un’astrazione ad alto livello di una particolare pipeline grafica. Tali

(19)

CAPITOLO 1. CONCETTI INTRODUTTIVI 16 funzioni non si limitano solo al passaggio dei dati (tipicamente geometria e texture) dall’applicazione al supporto sottostante destinato a completare il processo di rendering, ma includono anche procedure per alterare, influenzare e controllare lo stato della pipeline stessa. In ultima istanza si pu`o conside-rare OpenGL come una macchina a stati per l’aggiornamento del contenuto di un frame-buffer, costruita su un’architettura client-server.

Lo schema 1.5 rappresenta una buona approssimazione di quali siano le operazioni previste dal processo di renderizzazione implementato da OpenGL e in quale ordine tale operazioni avvengano. Per evitare di addentrarci troppo in aspetti tecnici che sviino dalle reali necessità di comprensione del lavoro in esame, la trattazione successiva si concentrerà solo sulle unità riportate nella figura. I restanti frammenti di pipeline , seppur rivestano un ruolo fondamentale nella definizione e nel completamento del processo di rendering, non aggiungono dettagli significativi in termini di astrazione del processo stesso.

Figura 1.5: Pipeline grafica standard di OpenGL

OpenGL permette di definire per ogni vertice cinque tipologie differenti di attributi: posizione, normale al vertice (usata principalmente per il calcolo

(20)

CAPITOLO 1. CONCETTI INTRODUTTIVI 17 della luce incidente sul vertice stesso), colore, informazione sul materiale di cui e’ composto e coordinate relative alla texture che andr`a ad arrichire la descrizione visiva della mesh tridimensionale. Tali attributi possono essere definiti tramite una delle tre modalit`a differenti previste dall’API:

• Enumerazione diretta degli attributi componenti tutti i vertici di una singola primitiva grafica (punti, linee, triangoli, poligoni generici) per mezzo delle funzioni glVertex, glNormal, glColor, glMaterial e glTex-Coord.

• Impacchettamento in un array per attributo di tutti i vertici componen-ti una intera mesh tridimensionale e passaggio successivo del riferimento del vettore ad OpenGL (meccanismo dei vertex-array).

• Definizione di liste precompilate di comandi OpenGL con il metodo del-le display-list. Al loro interno del-le display-list possono contenere sia invo-cazioni di funzioni riconducibili alla modalit`a “un vertice alla volta” sia la definizione di vertex-array. Essendo basato sulla pre-compilazione dei comandi tale metodo presenta la forte limitazione di necessitare che gli attributi non cambino di valore durante l’esecuzione dell’applicazione. Tali dati, entrati a far parte della memoria controllata dall’applicazione, po-tranno essere effettivamente allocati sia nella memoria centrale del calcolatore sia in quella locale alla scheda grafica. Sebbene, grazie a recenti introduzioni alle specifiche di OpenGL, sia effettivamente possibile tentare di forzare l’allo-cazione sul dispositivo hardware dedicato, nel proseguimento della trattazio-ne considereremo la questiotrattazio-ne come marginale e completamente trasparente al programmatore.

(21)

CAPITOLO 1. CONCETTI INTRODUTTIVI 18 Per-Vertex Operations (2)

A questo punto indipendentemente da quale delle tre modalit`a sopraelencate si sia prescelta, OpenGL attiva la sua prima sezione di pipeline: per-vertex operations. Come lascia facilmente intuire il nome in questo stadio una serie di operazioni prefissate vengono applicate ad ogni vertice che fluisce attraver-so di esattraver-so. La maggior parte di queste operazioni riguarda la trasformazione dei punti constituenti la scena tridimensionale da uno spazio vettoriale ad un altro.

Per semplificare la trattazione successiva si ritiene necessario introdurre un esempio concreto, sviluppato passo passo.

Si supponga di voler disegnare un quadrato come quello in figura 1.7.a e di definire la geometria in openGL tramite la modalit`a diretta:

glBegin(GL_QUADS); glVertex(0.0,0.0); glVertex(1.0,0.0); glVertex(1.0,1.0); glVertex(0.0,1.0); glEnd(); Figura 1.6:

Come si può notare dalla figura tutti gli altri vertici sono stati definiti rispetto al vertice A, assurto ad origine de sistema di riferimento locale nel quale è stato modellato il quadrato. In letteratura si è soliti riferirsi a tale sistema di riferimento con il nome di object-space.

Si voglia, a questo punto, ruotare il quadrato di 45 rispetto al suo punto centrale; di modo da fargli assumere una connotazione romboidale. Per far

(22)

Figura 1.7: Esempio di rotazione di un quadrato. La seconda immagine della serie presenta una rotazione attorno ad un asse che non `e il centro del quadrato stesso.

questo è necessario introdurre un nuovo sistema di coordinate: world-space. Come suggerisce il nome tale spazio simula il nostro mondo virtuale, in cui tutte le varie istanze di mesh tridimensionale verranno a convivere ed in-teragire tra di loro. Anche world space ha, come ovvio, la sua origine, il suo punto (0,0). Se si mappasse, semplicemente, con la funzione identità le coordinate di object-space in quelle di world-space si otterrebbe qualcosa di simile a quanto riportato in figura 1.7.b. Poichè in OpenGL tutte le ro-tazioni avvengono attorno all’origine del mondo, ciò non permetterebbe di muovere il quadrato in maniera coerente con quanto ci si era prefissati. È quindi necessario prima di tutto spostare l’origine del mondo in modo da farla coincidere con il centro di rotazione del quadrato (fig. 1.7.c). Ora sarà sufficiente ruotare il quadrato per ottenere quanto voluto(fig. 1.7.d). Quindi la funzione di mappatura per inserire il nostro quadrato in world-space nella giusta connotazione romboidale, prevederà, sicuramente, la composizione di una traslazione dello spazio vettoriale seguita da una rotazione del nuovo sistema di coordinate ottenuto. Trasformazioni affini (rotazioni, traslazioni e scalatura) vengono rappresentate in OpenGL per mezzo di matrici 4x4. La composizione di più trasformazioni è ottenuta dalla moltiplicazione delle ma-trici rappresentanti singole operazioni di trasformazione. Portare un punto

(23)

CAPITOLO 1. CONCETTI INTRODUTTIVI 20 tridimensionale dallo spazio di coordinate dell’oggetto allo spazio di coordi-nate di mondo implica quindi , come gi`a accennato in precedenza, il dover moltiplicare tale punto per una matrice di trasformazione corrispondente.

Una volta composta la scena tridimensionale è necessaria una nuova tra-sformazione del sistema di riferimento: da world-space ad eye-space. Eye-space rappresenta lo spazio di coordinate con origine nel punto in cui è piaz-zata la camera virtuale che dovrà inquadrare la scena. Varie sono le ragioni per cui è necessario questo ulteriore cambio di frame, la più importante delle quali è che nella pipeline standard di OpenGL il calcolo della luce incidente su ogni singolo vertice si basa sulle coordinate espresse nello spazio di ca-mera. Anche questa ulteriore trasformazione avviene tramite moltiplicazioni matriciali. Benchè alcune API 3D tengano separate la matrice di world-space da quella di eye-space, OpenGL condensa le due in una matrice nota come model-view ; ciò implica di fatto che dopo la moltiplicazione con tale matrice un punto passi direttamente da object-space nello spazio della camera. Una volta in eye-space, come già accennato prima, per ogni vertice ha luogo il calcolo di come le fonti luminose definite dal programmatore influenzino il colore finale del vertice stesso. Riveste un ruolo centrale in tale computazio-ne (basato sul modello di illuminaziocomputazio-ne di Phong) la normale definita per il singolo punto tridimensionale.

Parallelamente al calcolo dell’influsso della luce, ha luogo un’ulteriore trasformazione atta a definire il volume di vista della camera virtuale. Tale volume sar`a rappresentato da un parallelepipedo nel caso di una proiezione ortogonale, da un tronco di piramide nel caso di una, naturale, visione pro-spettica. Anche questo cambio di coordinate, avvenga per mezzo di un’ulte-riore matrice, nota in OpenGL come Projection-matrix. In successive sezioni di pipeline i vertici facenti parte di primitive che ricadano fuori dal volume di

(24)

CAPITOLO 1. CONCETTI INTRODUTTIVI 21 vista verranno scartati, esentando, cos`ı, OpenGL dal carico di calcolo dovuto a punti che non influenzeranno l’immagine che alla fine del rendering sara’ impressa nel frame buffer. Per questa ragione lo spazio vettoriale in cui sono stati trasformati i vertici dalla matrice di proiezione è noto come clip-space. Poichè, come si è appena visto, le operazioni principali che avvengono nella per-vertex unit sono le trasformazioni nei vari sistemi di riferimento e il calcolo dell’illuminazione, si è soliti chiamare l’unità preposta a tali compiti Transformation & Lighting unit.

Primitive Assembly (3) e Primitive Processing (4)

Nello stadio di Primitive Assembly, come il nome suggerisce, i vertici facen-ti parte del flusso uscente dall’unità di Trasformation & Lighting vengono ri-assemblati per comporre le primitive geometriche definite dal programma-tore. I punti richiedono un singolo vertice, le linee due, i triangoli, come è ovvio, tre, mentre un generico poligono, altrettanto ovviamente, sarà com-posto da un numero arbitrario di vertici. Compito dell’unità successiva, Primitive Processing, è quello di testare se la primitiva in esame ricada al-l’interno del volume di vista. Nel caso che solo una porzione della primitiva stessa viva all’interno del frustum predefinito, la pipeline si farà carico spez-zarla in due parti; ovviamente solo su quella appartente al volume suddetto verranno effettuate le restanti operazioni previste dal processo di rendering. Inoltre dovere dell’unità di Primitive Processing sarà quello di mappare i punti tridimensionali in oggetti 2D rappresentabili sul monitor di un calco-latore, coerentemente al tipo di proiezione (ortogonale o prospettica) che si sia scelto.

(25)

CAPITOLO 1. CONCETTI INTRODUTTIVI 22 Rasterizzazione (5)

Fino a questo momento le primitive geometriche sono ancora rappresentate solo dai vertici che ne delineano i punti estremi. Riempire lo spazio all’inter-no di tali confini con una serie di minuscoli frammenti delle stesse dimensione dei pixel componenti il frame buffer, è dovere dell’unità di rastering. Come già detto un vertice non si compone solo di un punto nello spazio ma an-che di attributi come colore, coordinate di texture e materiali. Compito del rasterizzatore è determinare tali valori per ogni frammento interpolando i corrispettivi attributi ai vertici della primitiva a cui il frammento appartie-ne. Nulla viene fatto per quanto riguarda la normale in quanto nella pipeline standard di OpenGL l’illuminazione ha luogo soltanto ai vertici (Goraud Sha-ding). Gli effetti della luce saranno estesi ai singoli frammenti semplicemente interpolando il colore dei vertici derivato dall’influsso delle fonti luminose. Fragment Processing (6)

L’operazione principale che avviene in questo stadio è l’accesso in memoria texture per ottenere la porzione dell’immagine destinata al singolo frammen-to. Il texel ottenuto potrà (dipendentemente dallo stato in cui si venga a trovare la pipeline) essere interpolato con il colore del framento per determi-narne l’aspetto definitivo o, altrimenti, ricoprirlo completamente. In realtà texturizzare un oggetto tridimensionale presenta molti più aspetti di quanto si sia precedentemente accenato. Il mip-mapping, ad esempio, in quanto cor-relato direttamente ad una delle problematiche della mia tesi, sarà introdotto al momento opportuno.

(26)

CAPITOLO 1. CONCETTI INTRODUTTIVI 23 Per-Fragment Operations (7)

Sebbene anche il texturing sia un’operazione che avviene per ogni singolo frammento per ragioni che saranno più chiare in seguito, tenderemo a tene-re separate le due unità. La Per-Fragment Operations è l’implementazione (generalmente e sperabilmente hardware) di una serie di test sullo stato di un frammento. Il più noto di questi è il depth test fondamentale per de-terminare se sullo schermo un fragment sia coperto da un altro. Se ciò dovesse avvenire due sono le possibilità: o il frammento viene scartato, o, nel caso di semitrasparenza, concorre alla determinazione del colore del pixel corrispondente.

Frame-Buffer Operations (8)

Nell’ultimo livello della nostra pipeline (semplificata) di OpenGL si eseguono tutti quei test che abbiano per oggetto aree di memoria all’interno del frame-buffer. Di solito l’unità di Frame-Buffer Operations è usata pesantemente per ottenere effetti grafici non banali (ombre, riflessioni speculari, segni cine-tici. . . ) non direttamente supportati da OpenGL. Completata anche questa fase l’immagine della scena tridimensionale è finalmente pronta per essere inviata sullo schermo.

1.4 Limiti imposti dalla pipeline statica

Fino a poco tempo fa OpenGL si presentava come un’interfaccia sufficien-temente flessibile per venire incontro a buona parte delle esigenze dei pro-grammatori di applicazioni grafiche tridimensionali; esigenze vincolate dai limiti oggettivi alla performance imposti dalle prime schede grafiche. Sebbe-ne vari parametri potessero essere settati per influenzare computazioni che

(27)

CAPITOLO 1. CONCETTI INTRODUTTIVI 24 avevano luogo in uno stadio della pipeline, fino alla versione 1.4 dell’API nè le operazioni fondamentali, nè l’ordine in cui queste avvenivano potevano essere modificate. Si supponga , ad esempio, che si voglia cambiare il mo-dello di illuminazione della scena, passando da quello di Phong (momo-dello di illuminazione stadard di OpenGL) a quello, ad esempio, di Cook-Torrence. Far questo con un processo di renderizzazione statico implica disabilitare il calcolo degli effetti della luce sui vertici (calcolo che, è bene sottolineare, avveniva su una periferica hardware specializzata) ed effettuare tale compu-tazione per ogni vertice sulla CPU; impiegando, cos`ı, un numero di cicli di clock proporzionale alla cardinalità degli elementi componenti lo stream di vertici. Il valore di colore ottenuto sarebbe poi stato inviato ad OpenGL tra-mite la funzione glColor. Ovviamente tutto questo può portare ad un rapido decadimento della performance.

1.5 Vertex Shader

Nel 2000-2001 con le versioni 3 e 4 della GeForce NVidia e con la ATI 8500, introducono (per la prima volta a livello di schede customer consumer) il concetto di programmabilità della pipeline di rendering, inserendo nelle pro-prie schede grafiche un per-vertex processor; un processore in grado, cioè, di interpretare una lista di comandi definiti dall’utente ed applicarli su ogni singola unità facente parte di uno stream di vertici. La pipeline veniva quindi ad assumere un’aspetto simile a quello riportato in figura 1.8.

Idealmente (in pratica non `e necessariamente detto che la cosa stia in questi termini) le operazioni previste dalla pipeline standard divengono es-se steses-se un programma che viene interpretato ed ees-seguito dal per-vertex

(28)

Figura 1.8: Pipeline con vertex processor

processor5. È importante notare come non sia possible modificare solo un sottoinsieme delle operazioni che avvengono per vertice; non è, ad esem-pio, possibile voler modificare solo il modello di illuminazione e sperare di mantenere il “codice” che implementi le varie trasformazioni da uno spazio vettoriale all’altro. Se si vuole una nuova formula per il calcolo della luce è necessario farsi carico anche dele funzionalità di mappatura fra i vari sistemi di riferimento. Operazioni tipiche che hanno luogo in un vertex shader com-prendono le trasformazioni dei vertici, delle normali e il calcolo dell’influenza delle fonti luminose, la generazione delle coordinate di texture ai vertici, la definizione di funzioni di distorsione della scena (si pensi ad esempio ada un vertex program che deformi un oggetto come se fosse visto attraverso una lente di ingrandimento) e l’uso di una tecnica nota come displacement map-ping che, rivestendo un ruolo centrale all’interno di questo lavoro di tesi, ci si riserva di introdurla con maggior grado di dettaglio in seguito.

`

E invece fondamentale notare immediatamente come sia impossibile

defi-5_{E infatti garantito che uno shader che simuli la pipeline pre-fissata di OpenGL abbia}_` la stessa performance della pipeline stessa.

(29)

CAPITOLO 1. CONCETTI INTRODUTTIVI 26 nire un vertex program il cui comportamento dipenda da un vertice diverso da quello elaborato in un dato istante sulla per-vertex unit. Non è possibile calcolare, ad esempio, il colore di un particolare vertice come media pesata di quelli a lui connessi. Questo perchè in uno stream-processor (come di fatto è una scheda grafica) non è predicibile l’ordine in cui gli elementi dello stream verranno processati; non e’ quindi detto che quando io calcoli il colore del vertice nell’esempio siano gia’ stati computati anche i rispettivi valori dei vertici che lo circondano. La ragione intrinseca di questa limitazione sulla classe degli algoritmi implementabili e’ nella struttura stessa che si è scelti per la definizione dell’architettura delle moderne schede grafiche. Struttura che sarà al centro della trattazione del secondo capitolo.

Con l’introduzione del vertex shader i device grafici passano dall’essere semplici acceleratori grafici a vere proprie Graphic Processor Unit (GPU).

1.5.1 Fragment Shader

Nel 2002 con la prima generazione di NVidia Fx e con la ATI 9000 anche lo stadio di fragment processing viene sostituito da una unit`a logica, il frag-ment shader, in grado di interpretare istruzioni da applicare ad ogni singolo frammento che fluisce attraverso la pipeline di rendering. Operazioni tipiche cha hanno luogo in un fragment shader definito dall’utente possono essere:

- Interpolazione dei valori calcolati ai vertici ed operazioni su tali valori - Calcolo di coordinate per l’accesso alla memoria texture

- Applicazione della texture

(30)

CAPITOLO 1. CONCETTI INTRODUTTIVI 27 Da un punto di vista prettamente grafico la scrittura di un fragment pro-gram presenta, indubbiamente, un maggior grado di libertà rispetto ad un programma operante per ogni singolo vertice. Come abbiamo visto nel para-grafo precedente gran parte tutti i vertex-program che si scrivono prevedono di ri-implementare buona porzione delle funzionalità già definite dalla pipe-line standard. Nel caso di un programma operante per frammento, invece, il numero di effetti grafici raggiungibili è sorprendentemente elevato e vario. La serie di figure rappresenta solo alcuni dei moltissimi effetti ottenibili tramite la definizione di fragment program corrispondenti. Si ritiene fondamenta-le ricordare ancora una volta che, sebbene la maggior parte di tali risultati potesse essere raggiunta tramite la scrittura un analogo programma esegui-bile sulla CPU, sfruttare appieno le potenzialità dell’unita dedicata presenta, perlomeno, il vantaggio di permettere di scaricare l’unità centrale da tale ope-razione, permettendogli cos`ı parallelemente di proseguire l’elaborazione dei dati non grafici dell’applicazione. Vedremo in seguito che i vantaggi effettivi non si limitano solo a questo.

Valgono anche per il fragment shader le stesse considerazioni espresse poc’anzi per il vertex shader. In particolare non è possibile sostituire solo una parte della funzionalità previste dalla pipeline standard di rendering per lo stadio di fragment processing e, più importante, non è possibile scrivere fragment program il cui funzionamento dipenda da frammenti diversi da quello che è in quel’istante oggetto di computazione. Questo per le stesse ragioni di efficienza precedentemente enunciate.

(31)

Figura 1.9: Pipeline con fragment processor

1.5.2 Ripercussioni dovute all’introduzione degli

sha-der

La definizione dei concetti di vertex e fragment processor ci permette di analizzare ad un alto livello di astrazione la struttura portante di una mo-derna scheda grafica. In figura e’ presentato uno spaccato della GeForce 6800 dell’NVidia. La caratteristica che salta immediatamente agli occhi e’ la possibilit`a di poter accedere anche dal vertex program alla memoria texture. Sebbene di primo acchito questo possa apparire un dettaglio non particolar-mente significativo, in realt`a come vedremo ampiamente in seguito questo a dato luogo ad un uso sorprendente ed imprevisto delle schede grafiche. Senza di quello lo stesso lavoro in esame non avrebbe avuto senso di essere. Nel prossimo capitolo torneremo ad osservare piu’ in dettaglio le caratteristiche tecniche in termini di struttura e performance delle attuali schede grafiche oggi sul mercato.

L’introduzione del vertex e del fragment shader non ha significato solo un cambiamento dal punto di vista hardware ma anche un ripensamento dell’ar-chitettura delle API sopra le quali le applicazioni grafiche vengono scritte. A

(32)

CAPITOLO 1. CONCETTI INTRODUTTIVI 29 titolo di sunto di quanto finora introdotto viene presentato in figura come si venga a modificare la pipeline grafica di OpenGL con l’aggiunta del concetto di programmabilit`a dell’hardware dedicato alla grafica tridimensionale.

1.6 Linguaggi di shading

Un po’ di storia

Il concetto di programmabilità dei device grafici è in realtà meno recente di quanto si possa credere. Già verso la fine degli anni ottanta su macchi-ne high-end specializzate si introdussero le prime GPU per il calcolo e il controllo della computazione. Il costo eccessivo di tali macchine restringeva notevolmente il bacino di utenza limitato in quegli anni praticamente alla sola industria cinematografica. E comunque il fine di tale hardware non era quello di fornire interazione real-time ma bens`ı, cosa naturale in un film, di elaborare in fase di post-processing le sequenze del film stesso. Parallela-mente alla definizione dello hardware nasce anche l’esigenza di definire un formalismo di alto livello che permetta una più confortevole interazione con il supporto fisico sottostante. Nasce cos`ı nel 1988 RenderMan nei laboratori della Pixar ( non a caso...) il primo linguaggio di shading universalmente riconosciuto come tale. Che l’utenza a cui è destinato RenderMan sia par-ticolare lo si capisce subito dalle caratteristiche più evidenti del linguaggio. . Invece dei semplici vertex e fragment shader tale linguaggio presenta light shader, displacement shader, surface shader, volume shader e image shader. Ciò ha come immediata conseguenza il fatto che il moderno hardware grafico mal si adatti a supportare le feature introdotto da tale linguaggio. Nonostan-te questo nell’ambito dell’industria cinematografica RenderMan è ancora uno

(33)

CAPITOLO 1. CONCETTI INTRODUTTIVI 30 strumento oggigiorno ampiamente usato (per esempio nelle trilogie di Lord of the Rings e di StarWars).

Caratteristiche simili a quelle di RenderMan presentava anche il primo linguaggio di shading costruito sopra OpenGL: Interactive Shading Language (ISL) che supportava light shader e volume shader. Ben pi`u interessanti per lo sviluppo del lavoro in esame sono i tre linguaggi successivi, filiazione diretta dell’architettura delle moderne schede grafiche:

- High Level Shading Language (HLSL), prodotto dalla Microsoft - C for graphic (Cg), introdotto dalla NVidia

- OpenGL Shading Language (OGLSL o anche GLSL), le cui specifiche sono definite dall’OpenGL consortium).

Concettualmente, a parte minime differenze di carattere sintattico, i tre idio-mi sono pressoch`e uguali. La vera differenza risiede nell’API (e di conse-guenza nella pipeline) su cui i programmi definiti in tali linguaggi saranno eseguiti. OGLSL avr`a ovviamente come base OpenGL, HLSL Direct3D, men-tre Cg presenta un livello di astrazione maggiore che gli permette di poter utilizzare entrambi le API 6_.

Coerentemente con quanto fatto finora si continuer`a ad assumere OpenGL come ambiente di sviluppo principe del lavoro in esame; scelta che ovviamente ci orienter`a nell’adottare OGLSL come linguaggio per la definizione degli shader implementati all’interno di questa tesi.

6_{Sebbene questo possa apparire come una importante nota a favore del linguaggio del} NVidia, la real`a dei fatti indica come sia proprio Cg quello che forse sar`a destinato a scomparire per primo.

(34)

1.7 Caratteristiche principali di OGLSL

OpenGL shading language è, innanzitutto, un linguaggio Turing-equivalente. Sebbene la precisazione possa apparire superflua, è invece necessario notare come tale condizione sia stata raggiunta recentemente. Per poter mantenere un grado di efficienza elevato, tramite la massimizzazione del parallelismo (su tale concetti ritorneremo diffusamente nel secondo capitolo), si era preferito nelle prime implementazioni hardware di evitare di esporre istruzioni per il controllo del flusso dell’elaborazione. Si costringeva cos`ı il programmatore a definire shader program che avessero lo stesso comportamento su tutti gli elementi dello stream; comportamento che doveva essere indipendente dallo stato di ogni singolo vertice o frammento. In altre parole si rendeva implicita la sincronizzazione di tali unità; stesso numero e stesso tipo di istruzioni su uno stesso tipo di dato implica, ovviamente, che ogni elemento dello stream impiegasse un quantità di tempo pari agli altri per terminare la propria computazione. Ovviamente ciò rappresentava un vincolo troppo forte sulla tipologia di algoritmi definibili all’interno degli shader. Per questo sono stati introdotte le usuali istruzioni di controllo del flusso presenti nella quasi totalità dei linguaggio di programmazione: if-then-else, while,for ed invocazione di funzioni.

OGLSL ha un paradigma di programmazione prettamente imperativo e sebbene stilisticamente possa apparire simile al C con l’aggiunta di alcune caratteristiche del C++ (overloading delle funzioni e costruttori) in realtà strutturalmente è, forse, più vicino alle prime implementazioni del Fortran che non facevano uso del concetto di stack delle chiamate. Inutile dire che ciò impedisca qualsiasi forma di ricorsione. Sono inoltre banditi anche i puntatori e l’allocazione dinamica della memoria. L’unico tipo di memoria disponibile per uno shader e’, dunque, quella statica che elargisce il compilatore del

(35)

CAPITOLO 1. CONCETTI INTRODUTTIVI 32 linguaggio. Oltre all’impossibilità della ricorsione ciò ha come conseguenza che esiste un tetto al numero massimo di istruzioni e alla profondità massima di chiamata delle funzioni.

Il supporto che OpenGL offre per il proprio linguaggio di shading e’ composto fondamentalmente di due parti:

- il linguaggio di shading vero e proprio (OGLSL)

- integrazioni all’API previa introduzione di funzioni per permettere di costruire un contesto in cui poter compilare e far eseguire gli shader scritti dall’utente.

OGLSL e’ supportata all’interno di OpenGL dalla versione 1.5 come esten-sione ARB, anticamera alla piena integrazione che avverr`a con la definizione delle specifiche di OGL 2.0.

1.7.1 Tipi pre-definiti e definibili

In ultima istanza un linguaggio di programmazione non `e altro che un al-gebra su un insieme di tipi. Anche i linguaggi di shading non sfuggono a questa caratteristica; `e, quindi, fondamentale soffermarsi su quali siano i tipi supportati e quali i qualificatori definibili sui tipi stessi.

Ovviamente sono presenti i soliti tipi scalari int e float e dal C++ sono ereditati i valori booleani. Una qualsiasi varibile di tipo T viene instanziata tramite il costruttore del tipo suddetto. Es. float a = float(1.0); int b = int(3); bool c = bool(true).

Gli interi sono entit`a particolari in un linguaggio di shading. La loro presenza serve principalmente per indirizzare array e per implementare in maniera efficiente i cicli. Essendo il loro uso limitato non `e infrequente che in maniera trasparente al programmatore questi vengano convertiti in float.

(36)

CAPITOLO 1. CONCETTI INTRODUTTIVI 33 Gli int sono sempre signed ed `e, altres`ı, garantito che abbiano un’ampiezza di almeno 16 bit.

Il float `e lo scalare per eccellenza dei linguaggi di shader e la loro imple-mentazione `e compatibile con quella definita dalla IEEE.

In OGLSL non è previsto il concetto di cast implicito ed il compilatore in questo è abbastanza pedante. Se l’argomento di una funzione è un float non vi sarà alcuna possibilità di accontentarlo passandogli un int. Esiste una sola deroga a questa regola: i costruttori. Scrivere una float c = float(1); e’ l’unica forma di cast concessa dal linguaggio.

Tipi caratteristici di un linguaggio di shading sono invece i vettori e le matrici:

- vec2, vec3, vec4 sono vettori di 2/3/4 float - ivec2, ivec3, ivec4 sono vettori di 2/3/4 int - bvec2, bvec3, bvec4 sono vettori di 2/3/4 bool

Per accedere ad una componente di un vettore `e disponibile l’usuale ope-razione di swizzle; per aiutare ad aggiungere semantica a quello che si sta selezionando sono presenti per una stessa coordinata pi`u modi di referenziar-la:

- .x, .y, .z, .w (coordinate) - .r, .g, .b, .a (colore) - .s, .t, ,p, .q (texture)

Ovviamente e’ sempre possible accedere alla coordinata x di un vec4 rappre-sentate un punto p dello spazio con p.r o con p.s. I suffissi sono solo per favorire leggibilit`a del codice.

(37)

CAPITOLO 1. CONCETTI INTRODUTTIVI 34 - mat2 matrice 2x2

- mat3 matrice 3x3 - mat4 matrice 4x4

Sono accessibili sia come colonna, restituendo vec corrispondente alla dimen-sione della matrice, sia per singolo elemento scalare.

E’ possibile definire array7 _{con una sintassi del tutto simile a quella del C:}

vec4 point[10] indica un’array contenente dieci vec4. Non esistendo alloca-zione dinamica della memoria e’sempre necessario specificare la dimensione dell’array stesso.

Sono presenti le struct ed e’ quindi possibile definire conglomerati di tipi. Supponiamo, ad esempio, di voler definire un punto luce identificato da una posizione e dal colore della luce emessa:

struct light { vec4 color; vec4 position; };

Per dichiarare una variabile di tipo light sara’ sufficiente scrivere light l = light(vec4(0.0),vec4(0.0)); che, senza che sia stato definito alcun costrut-tore per light da parte dell’utente, inizializza i membri della struct secondo l’ordine di passaggio dei parametri.

L’uso del tipo void e’ consentito per le sole funzioni che non prendono e/o non restituiscono valori.

7_{. . . ma non `}_{e consigliabile usarli. . . `}_{e stato spesso notato nello svolgimento del lavoro} in esame come il loro comportamento fosse alquanto aleatorio.

(38)

CAPITOLO 1. CONCETTI INTRODUTTIVI 35 `

E infine presente un ultimo tipo il cui scopo `e facilitare l’accesso in lettura ad una texture: sampler. Sono definiti:

- sampler1D, sampler2D, sampler3D funzioni per l’accesso ad una texture n-dimensionale

- samplerCube per l’accesso alle cube

- sampler1DShadow e sampler2DShadow per l’accesso ad una depth tex-ture

1.7.2 Attributi

Gli attribuiti sono parte fondamentale di qualsiasi linguaggio di shading. In OGLSL si riconoscono principalmente tre tipi di attributi: uniform, attribute e varying. Tutti e tre indicano fondamentalmente una classe di comunicazione o tra applicazione-shader o tra vertex shader-fragment shader. Una variabile dichiarata attribute e’ intesa come una variabile che conterra valori passati allo shader dalla applicazione e che tale valore e’ specifico di un particolare vertex o fragment.

Una variabile dichiarata uniform e’ intesa come una variabile che con-terrà valori passati allo shader dalla applicazione e che tale valore è comune ed immutato per tutti i vertici o frammenti di quella passata di rendering. Una variabile definita varying e’ una variabile contenente un valore passato dal vertex program al fragment program. Il fragment program ne riceverà un’interpolazione del valore calcolato ad ogni vertice del poligono a cui tale frammento appartiene8.

8_{E, invece, impossibile passare qualsiasi valore indietro dal fragment program al vertex}_` program.

(39)

CAPITOLO 1. CONCETTI INTRODUTTIVI 36 Una variabile attribute in realta’ non e’ altro che un parametro che un par-ticolare vertice o frammento passa ad uno shader per influenzarne il calcolo. In OGLSL si preferisce, per`o, scrivere funzioni che non prendano argomenti e che presentino, invece, una serie di dichiarazioni attribute in cima al file9 _Per

settare varibili di tipo uniform e attribute esistono funzioni ARB in OpenGL da invocare dentro l’applicazione. Le variabili di qualificatore varying non ne hanno bisogno in quanto sono sempre introdotte e definite. solo all’interno di un vertex shaderd.

`

E definito, infine, il qualificatore const, il cui significato e’ immediata-mente intuibile.

1.7.3 Variabili pre-definite

Esistono all’interno del linguaggio un certo numero di variabili pre-definite il cui significato ed utilizzo `e riservato per compiti speciali.

La pi`u riconoscibile di queste, gl Vertex, `e la variabile contenente la po-sizione di un vertice, passata alla scheda grafica tramite la funzione glVertex dell’API standard. Ovviamente questa non e’ altro che la variabile attribute destinata a contenere le coordinate del vertice in world-space cos`ı come sono state determinate dall’applicazione.

La gl Position e’ una variabile di tipo varying a cui deve essere necessaria-mente assegnato un valore in un vertex shader; pena la notifica di un errore

9_{Questo principalmente per ragioni di efficienza. Se si volesse, ad esempio, scrivere uno} shader che necessiti di un parametro e tale parametro fosse necessario passare ad un’altra funzione definita nello shader avrei bisogno di un’ulteriore copia del valore. Ci`o puo inficiare pesantemente le prestazioni in quanto, come si `e visto, non esistendo i puntatori tutti i passaggi di parametri avvengono per copia. Definendo tale parametro come globale sacrifico una dose ragionevole di pulizia programmativa in favore di un aumento della performance.

(40)

CAPITOLO 1. CONCETTI INTRODUTTIVI 37 da parte del compilatore. Essa conterr`a (di solito) le coordinate del vertice trasformate in eye-clip space. `E, fortunatamente, presente tra le procedure pre-definite dal linguaggio la funzione ftransform che modifica secondo le ma-trici di ModelView di Projection la posizione (gl Vertex) del vertice presente in un dato istante all’interno del vertex processor.

Altra variabile a cui `e necessario assegnare un valore e’ la gl FragColor nel fragment shader. Essa identifica il colore che il pixel dovra’ avere sullo scher-mo, gl FragColor = vec4(1.0) colorera’, ad esempio, ogni pixel rasterizzato di bianco.

Come queste sono presenti moltissime altre variabile (gl Color, gl Normal ,gl ModelViewMatrix. . . ) il cui significato `e sufficientemente intuitivo da non necessitare di alcun commento.

(41)

Capitolo 2

GPGPU

Nel capitolo precedente ci si è principalmente concentrati nel definire, per sommi capi, i concetti centrali che sono alla base della pipeline grafica e a mostrare come tali concetti abbiano trovato con il passare degli anni una adeguata controparte nell’evoluzione dell’hardware corrispondente. Moto-re, ragione e guida di ogni fase del suddetto sviluppo è stato sempre una sorta di circolo virtuoso auto-alimentante che ha come obbiettivo finale sia l’aumento del realismo nella renderizzazione della scena tridimensionale, sia un’interazione piu’ confortevole, in termini di FPS, tra l’utente con ciò che viene mostrato sullo schermo. Il raggiungimento di un adeguato grado di performance in una tecnica o in un effetto grafico rappresenta solo l’anti-camera del bisogno spasmodico di portare la simulazione verso il livello di realismo successivo. Ogni singolo frame per second guadagnato si trasforma immediatamente in un prezioso capitale da spendere sia in nuove tecniche di visualizzazione sia in un affinamento complessivo della simulazione stessa.

I produttori di hardware grafico hanno tentano di sopperire a questa con-tinua richiesta di aumento delle prestazioni con l’immissione sul mercato di nuovi device con una capacit`a computazionale enormemente superiore a

(42)

CAPITOLO 2. GPGPU 39 li che li hanno direttamente preceduti. Parallelamente l’introduzione di un livello programmativo all’interno della pipeline di rendering e la definizione di linguaggi di alto livello per lo sviluppo di nuovi shader, ha permesso di dominare più facilmente tale potenza di calcolo e di estenderne i confini di applicazione. Questo ha portato negli ultimissimi anni ad una nuova linea di sviluppo: il General Purpose computation on GPU. Usare, cioè la potenza di calcolo insita nelle moderne schede grafiche per finalità completamente diverse da quelle per cui sono state originariamente progettate. Simulazio-ni fisiche, numeriche e chimiche, che sottostiano a determinate condizioSimulazio-ni, possono avvantaggiarsi in maniera significativa delle prestazioni offerte dalle moderne GPU. Presentare le motivazioni che sono alla base di questa nuo-va offerta tecnologica e introdurne i concetti chiave sarà compito focale di questo capitolo.

2.1 CPU vs GPU: qualche numero

Sebbene vanti pioneristici quanto dimenticati tentativi nei tardi anni settanta [FHWZ04] il calcolo general-purpose sulla GPU `e disciplina estremamente recente che deve la sua origine al fascino indiscutibile esercitato dai valori di performance dichiarati dai produttori di hardware grafico.

Nel grafico sono riportati il numero di moltiplicazioni al secondo su float a 32 bit ottenibili con varie versioni di fragment processor e il corrisponden-te valore raggiungibile da un Pentium 4 a 3.0 GHz. Come si può notare il confronto tra CPU e GPU è impari non solo in termini di prestazioni asso-lute ma, soprattutto, anche in termini di incremento medio delle prestazioni stesse. Tra il Pentium 3 e il Pentium 4 si è passati, in quarantotto mesi, da 4 a 6 gigaflop(pari ad un incremento annuale di 0.5 gigaflop) , mentre in soli

(43)

CAPITOLO 2. GPGPU 40 sei mesi sulle schede grafiche si e’ partiti dagli 8 gigaflop fino a giungere ai 20 (con incremento annuale di 24 gigaflop). Tale gap `e, molto probabilmente, destinato ad allargarsi in futuro. La NVidia ha annunciato che il suo attuale modello di punta, la Geforce 7800, `e capace di raggiungere la ragguardevole cifra di 165 miliardi di moltiplicazioni al secondo!

Anche dal punto di vista dell’accesso sequenziale alla memoria l’hardware grafico presenta valori sorprendenti; mentre la banda di trasferimento1 della memoria principale `e di circa 6 Gbyte al secondo in un unit`a di tempo la memoria locale alla GPU riesce a trasferire 17 miliardi di byte. Vedremo, comunque, in seguito che l’accesso in memoria rappresenta uno dei limiti maggiori al pieno utilizzo della scheda grafica come supporto per il calcolo general purpose.

A questa potenza computazionale si aggiunge anche una forte attrattiva dal punto di vista economico: il costo di una scheda grafica appena immessa sul mercato si aggira sui 400-500 euro; ed il prezzo scende rapidamente nel giro di pochi mesi con l’emergere di nuove soluzioni hardware.

Dovrebbe essere gi`a chiaro come questa enorme intensit`a di calcolo unita ad una buona banda di trasferimento dei dati abbia rappresentato un’attrat-tiva stimolante per tentare di estendere verso nuovi orizzonti l’usuale dominio di computazione della GPU.

2.2 Linee guida nello sviluppo hardware

Come sottolineato nel paragrafo precedente esistono notevoli differenze negli indici di performance raggiungibili da una scheda grafica rispetto a quelli

1_{Indice della quantit`}_{a di dati trasferiti nell’unit`}_{a di tempo, si misura in byte al secondo.} In letteratura `e spesso riferita con il termine inglese di bandwidth.

(44)

CAPITOLO 2. GPGPU 41 riscontrati dall’usuale unità centrale di elaborazione; questo nonostante la tecnologia dei semiconduttori avanzi con pari grado di sviluppo su entrambe le piattaforme. Tale disparità ha origini più profonde che risiedono nelle differenti finalità per cui la CPU e la GPU sono disegnate e dalle scelte architetturali da queste conseguenti. Per meglio comprendere le ragioni che sottostanno a tali divergenze di prestazione si ritiene necessario fare un breve excursus sui trend tecnologici che hanno dominato lo sviluppo hardware degli ultimi decenni e sulle problematiche derivatene.

2.2.1 Very Large Scale Integration

Gli attuali processori, sia quelli dedicati alla grafica e sia le usuali CPU, sono composti da milioni di minuscole componenti interconnesse tra loro: i transistor. Nel 1965 Gordon Moore, analizzando i trend tecnologici che guidavano l’avanzamento hardware del decennio, profetizz`o che il numero di componenti integrabili per unit`a di spazio sarebbe aumentato del 100% ogni anno2 _{[Moo65]. Tale tesi si `}_{e dimostrata valida per i successivi quaranta anni}

tanto da essere divenuta universalmente nota come legge di Moore.

Non solo il numero di transistor aumenta constantemente ogni anno ma, con un percorso altrettanto virtuoso, diminuiscono le dimensioni del transi-stor stesso. Componenti più piccole implicano un tempo di attraversamento da parte del segnale elettrico minore, con conseguente incremento della ve-locità totale del chip. L’aumento concorrente del numero di componenti integrabili e della loro velocità fa si che, dal punto di vista teorico, la capa-cità di calcolo (capability ) di un processore sia soggetta ad un incremento annuale del 71% [Owe05].

2_{In realt`}_{a nel 1975 Moore, tenendo conto della crescente complessit`}_{a dei chip, riassest`}_o il tasso di sviluppo al 50% su base annua.

(45)

CAPITOLO 2. GPGPU 42

2.2.2 Banda di trasferimento e latenza

Sebbene ogni tre anni raddoppino di dimensione [Owe05], le memorie dina-miche (DRAM) presentano dal punto di vista della banda e della latenza (misura della quantità di tempo che intercorre tra una richiesta di un dato e l’effettiva disponibilità dello stesso) un incremento annuale di performan-ce molto più limitato rispetto alla capability del processore, il che presenta un vincolo fortissimo al pieno sfruttamento delle effettiva quantità di calcolo disponibile. L’accesso in memoria e, soprattutto, i tempi di comunicazione divengono cos`ı, sempre più, il collo di bottiglia dell’intero sistema. Ciò con-stringe i designer delle architetture hardware ad implementare soluzioni che permettano un maggiore grado di tolleranza sugli effetti negativi della laten-za stessa; principalmente facendo in modo di svolgere calcolo utile mentre si attende la disponibilità di un dato dalla memoria.

2.3 Indirizzi tecnologici per massimizzare la

computazione

In questa sezione si tenteranno di definire le caratteristiche che rendono un’ar-chitettura computational intensive, in modo da poter meglio comprendere perch`e dal punto di vista della nuda potenza di calcolo la GPU sovrasti le usuali unit`a centrali di elaborazione.

Privilegiare i transistor datapath

Come visto nella sezione la VLSI permette di integrare su un singolo chip un numero davvero ragguardevole di transistor; tuttavia `e, bene notare, come

(46)

CAPITOLO 2. GPGPU 43 le finalit`a cui siano destinati tali transistor non siano uniche e che anzi sia possibile riconoscere tre classi principali di componenti [Owe05]:

- i transistor effetivamente votati alla computazione vera e propria. In letteratura sono conosciuti con il termine di datapath.

- i transistor deputati al controllo dell’avanzamento della computazione (control ).

- i transistor che hanno funzione di immagazzinare i dati (storage). Dovrebbe essere ovvio che se il fine sia massimizzare la quantità di calcolo del processore, il chip dovrà contenere un numero il più elevato possibile di componenti datapath.

Avvantaggiarsi del parallelismo

Eseguire più computazioni in parallelo, ovviamente, non può che incremen-tare la quantità di calcolo totale effettuata dal processore.

In ultima istanza si riconoscono principalmente tre tipi differenti di pa-rellelismo:

- task parallelism; permettere, cioè, di compiere in uno stesso istante operazioni differenti su dati diversi. La pipeline ne è l’esempio più noto.

- data parallelism; eseguire contemporaneamente la stessa operazione su pi`u di un dato di input. L’architettura farm, in cui vengono replicate le risorse di calcolo, `e un’espressione di questo tipo di parallelismo. - instruction parallelism; all’interno dell’elaborazione di un singolo dato

si cerca di spezzare la computazione in sotto-operazioni che vengono eseguite concorrentemente.

(47)

CAPITOLO 2. GPGPU 44 Sar`a presto evidente come la GPU riesca in maniera efficace ad avvantag-giarsi di tutte queste forme di parallelismo, proprio per l’intrinseca natura del problema per cui `e stata originariamente progettata.

Comunicazioni efficienti

Come già visto in precedenza le comunicazioni rappresentano i vincoli più forti alla piena espressione della potenza di calcolo insita negli attuali chip. Un processore, che aspiri a raggiungere un alto livello di performance, non può far a meno di minimizzare il più possibile le comunicazioni al di fuori del chip in cui risiede il processore stesso (off-chip comunications). Negli anni uno dei metodi più efficaci per aggirare il problema si è dimostrato il caching dei dati; tentare, cioè, di mantenere in una struttura di memoria gerarchica prossima al processore, i dati caricati dalla memoria centrale, in modo di facilitarne e velocizzarne il riutilizzo. L’uso del caching, per certi versi, collide con l’obbiettivo di massimizzare il numero di transistor dedicati al calcolo effettivo (datapath), in quanto, per attenuare l’effetto degradante delle comunicazioni, si occupa una porzione di superficie del chip stesso con elementi di memoria.

Un’altra tecnica che si è dimostrata utile nel minimizzare il costo delle comunicazioni off-chip è la compressione dei dati. Solo una rappresentazio-ne compressa del dato vierappresentazio-ne ricevuta e spedita dal processore. Ciò impli-ca che, per attutire il degrado introdotto dallo simpli-cambio di informazioni tra un’unità di elaborazione e la memoria, si sacrifichi sia spazio sul chip per l’hardware dedicato alla compressione e alla decompressione, sia tempo per attuare effettivamente tali operazioni di manipolazione sui dati.

(48)

CAPITOLO 2. GPGPU 45

2.4 Considerazioni sulle scelte

architettoni-che della CPU

L’unità centrale di elaborazione, proprio per il suo essere programmaticamen-te general purpose, è progettata con lo scopo di soddisfare le richieste più diverse. In generale, un’applicazione che deve essere eseguita da una CPU può avere una natura prettamente sequenziale senza esporre alcun grado di parallelismo, oppure presentare la necessità di un monitoraggio più stringen-te sul flusso dell’esecuzione. Con la conseguenza di aumentare la porzione di chip destinata ai transistor di controllo a scapito di quelli di datapath. Se ne deduce, quindi, che due delle linee guida che abbiamo precedentemente enunciato per la massimizzazione del calcolo, siano rimaste sostanzialmente esterne allo sviluppo tecnologico delle moderne CPU.

Cosa diversa `e avvenuta, invece, per quanto riguarda la minimizzazione del costo delle comunicazioni. Proprio per la sua natura sequenziale la CPU presenta la necessit`a di riferirsi continuamente a delle locazioni di memoria. Si consideri il frammento di codice seguente:

a = b + c; d = a;

Si consideri la figura 2.1 in cui, in una architettura che espone task pa-rallelism, le operazioni di somma e di successivo assegnamento siano eseguite su due unit`a distinte di pipeline.

(49)

CAPITOLO 2. GPGPU 46 Il valore di a uscente dallo stadio di somma viene immediatamente dato in pasto al livello successivo ed il valore della variabile “vive” nel collegamen-to fisico esistente tra le due unità, favorendone implicitamente la località del dato. È evidente, invece, come nell’impostazione sequenziale della CPU la variabile a abbia bisogno di essere acceduta due volte durante l’esecuzione del programma, ed è altrettanto evidente, quindi, che la presenza di una cache, che mantenga la variabile stessa locale al processore, velocizzerebbe in ma-niera significativa il processo computazionale. Lo sviluppo tecnologico della CPU ha inseguito, negli anni, come obbiettivo prioritario la minimizzazione del tempo di latenza, non sorprende quindi che, al contrario di un processo-re grafico, una grande fetta della superficie del chip, su cui l’unità centrale risiede, sia devoluta ad ospitare una cache gerarchica fortemente strutturata.

2.5 La GPU come stream processor

I limiti maggiori in cui incorre la CPU per potersi affermare come architettura computational intensive sono dovuti principalmente, come appena visto, al moderato grado di parallelismo che le `e possibile esporre. Limite che invece non affligge tutta una classe di unit`a di elaborazione operanti su flussi di elementi dello stesso tipo: gli stream processor.

Ad ogni singolo elemento facente parte del flusso di input viene appli-cata una funzione descritta da una unità computazionale a cui, nel gergo degli stream processor, ci si riferisce con il termine di kernel. Tipicamente un processore operante su stream è composto da una serie di kernel posti in successione tra loro. L’intera pipeline di rendering non è altro che una particolare istanza di un stream processor che ha come flusso di input una serie di vertici tridimensionali.

(50)

CAPITOLO 2. GPGPU 47 La pipeline grafica per la sua stessa natura espone intrinsecamente task parallelism e, se si impone che il comportamento di ogni dato del flusso è indipendente da qualsiasi altro elemento del flusso stesso, è possibile avvan-taggiarsi facilmente del data parallelism replicando le risorse di calcolo. Sia la ATI X800 che l’Nvidia 6800 presentano sei vertex processor e ben sedici fragment shader che operano in concorrenza tra loro. È importante notare che l’indipendenza tra vertici o frammenti diversi è in realtà meno stringente di quanto posso apparire di primo acchito. In un dato istante t quel che si chiede è che il comportamento di un singolo elemento facente parte del flusso di input non sia influenzato dalle caratteristiche presentate da un altro ele-mento allo stesso tempo t. Nulla impone di calcolare il colore di framele-mento ad un istante t riferendosi al colore che un suo vicino aveva al tempo t - 1. Se ciò non fosse possibile l’utilizzo della GPU come processore general purpose sarebbe estremamente limitato e poco interessante.

Operando tipicamente su dati vettoriali (posizione, colore, coordinate di texture etc. . . ) molte delle istruzioni interpretabili dai processori di vertex e fragment shader possono essere scomposte in sotto computazioni che avven-gono in parallelo sulle singole componenti del vettore. Si prenda ad esempio il prodotto scalare tra due elementi vettoriali tetradimensionali:

dot(a, b) =Xai· bi (2.1)

Tale operazione pu`o essere tradotta immediatamente come nello pseudo-codice seguente:

float dot = 0.0;

for(i = 0; i < 4; ++i) dot = a[i]* b[i] + dot;