SIMULAZIONE DI FLUIDI IN TEMPO REALE BASATA SU SMOOTHED PARTICLE HYDRODYNAMICS ACCELERATA CON HARDWARE GRAFICO

Testo completo

(1)SOMMARIO Indice delle Figure ......................................................................................................... 3 Indice degli Acronimi .................................................................................................... 4 1. INTRODUZIONE ................................................................................................... 5. 2. STATO DELL’ARTE ................................................................................................ 7 2.1. Simulazioni di Fluidi in tempo reale ................................................................ 7. 2.1.1. Simulazioni basate su spazio delle coordinate Euleriano e Lagrangiano 10. 2.2. Simulazioni basate su sistemi di particelle.................................................... 12. 2.2.1. Integrazione Euleriana .......................................................................... 13. 2.2.2. Collision detection e Space partitioning ............................................... 15. 2.3. Modellazione di fenomeni fisici .................................................................... 25. 2.3.1 2.4. Equazioni di Navier-Stokes.................................................................... 25. Smoothed Particle Hydrodynamics ............................................................... 27. 2.4.1. Grandezze fisiche utilizzate nelle simulazioni ....................................... 28. 2.4.2. Smoothing Kernels ................................................................................ 30. 2.5. La tecnologia CUDA ....................................................................................... 31. 2.5.2 3. CUDA in simulazioni Physics-oriented .................................................. 38. PROGETTAZIONE ............................................................................................... 40 3.1. Ambiente di lavoro........................................................................................ 41. 3.2. Scelte Progettuali .......................................................................................... 41. 3.3. Architettura Software ................................................................................... 42. 3.3.1. Particle System ...................................................................................... 43. 3.3.2. Configuration Manager ......................................................................... 45. 3.3.3. Interfaccia Utente ................................................................................. 46. 3.3.4. Space Partitioning ................................................................................. 51. 1.

(2) 3.3.5. Collision Detection ................................................................................ 53. 3.3.6. Funzioni MEX......................................................................................... 54. 3.3.7. Integrazione di GPUmat e CUDA nel simulatore .................................. 56. 3.3.8. Caricamento automatizzato moduli CUDA ........................................... 59. 3.3.9. Generazione Benchmark e Statistiche .................................................. 59. 4. IMPLEMENTAZIONE .......................................................................................... 62 4.1. L’implementazione del core.......................................................................... 62. 4.1.1. Formattazione e allocazione dei dati .................................................... 62. 4.1.2. Calcolo delle forze nel sistema.............................................................. 63. 4.1.3. Calcolo dei vincoli spaziali ..................................................................... 66. 4.1.4. Integrazione temporale ........................................................................ 67. 4.1.5. Aggiornamento della grafica ................................................................. 67. 4.1.6. Aggiornamento dei dati provenienti dalla scheda grafica .................... 68. 4.2. Implementazione e integrazione delle funzioni MEX ................................... 68. 4.3. L’utilizzo di GPUmat ...................................................................................... 69. 4.4. Implementazione e integrazione di codice CUDA......................................... 72. 5. ANALISI .............................................................................................................. 74 5.1. Confronto tra simulazioni basate su CPU e GPU........................................... 74. 5.2. Confronto tra simulazioni con differenti Space Partitioner .......................... 77. 6. CONCLUSIONI E SVILUPPI FUTURI..................................................................... 79. 7. Bibliografia ........................................................................................................ 80. 2.

(3) INDICE DELLE FIGURE Figura 1 - Evoluzione delle prestazioni di CPU e GPU ................................................... 9 Figura 2 - Moto di un fluido in spazio delle coordinate Euleriano al tempo t0 e t1 (1) 10 Figura 3 - Moto di un fluido in spazio delle coordinate Lagrangiano al tempo t0 e t1 (1) ...................................................................................................................................... 11 Figura 4 - Particelle all'interno del Bounding Box....................................................... 18 Figura 5 - Esempio di 3D Tree (Wikipedia).................................................................. 21 Figura 6 - Esempio di Spatial Hashing nel caso bidimensionale (8) ............................ 24 Figura 7 - Smoothing Kernels (13)............................................................................... 31 Figura 8 - Confronto fra l'architettura di una CPU e di una GPU (14)......................... 33 Figura 9 – Struttura dei blocchi di thread e delle griglie (14) ..................................... 35 Figura 10 - Gerarchia di memoria della GPU (14) ....................................................... 36 Figura 11 - Sottosistemi del simulatore ...................................................................... 43 Figura 12 - Gerarchia di classi Particle System........................................................... 44 Figura 13 - Classi del Configuration Manager ............................................................ 45 Figura 14 - Relazione tra la GUI e il Particle System ................................................... 47 Figura 15 – Interfaccia grafica all’avvio dell’applicazione .......................................... 48 Figura 16 - Dettaglio dell’interfaccia utente: pannello di controllo per la modifica dei parametri di simulazione .................................................................................................. 49 Figura 17 - Tipi di visualizzazioni: particles, surface, all map, volumetric .................. 50 Figura 18 - Menù dei comandi della GUI .................................................................... 51 Figura 19 - Classi dello Space Partitioner.................................................................... 52 Figura 20 - Collision Detection del Particle System .................................................... 54 Figura 21 - Interazione tra moduli Matlab e librerie CUDA ........................................ 57 Figura 22 - Struttura del sottosistema per Benchmark e Statistiche.......................... 60 Figura 23 - Esempio di grafici generati dal modulo delle Statistiche.......................... 61 Figura 24 - Confronto tempo per passo di simulazione.............................................. 75 Figura 25 - Incremento delle prestazioni tra CPU e GPU al variare del numero di particelle ........................................................................................................................... 76 Figura 26 - Confronto tra tempo per passo di simulazione degli space partitioner al variare del numero di particelle........................................................................................ 77. 3.

(4) INDICE DEGLI ACRONIMI SPH. Smoothed-particle hydrodynamics. CUDA. Compute Unified Device Architecture. GPU. Graphics Processing Unit. GPGPU. General Purpose computing on Graphics Processing Unit. ODE. Ordinary Differential Equation. MBB. Minimum Bounding Box. AABB. Axis-Aligned Bounding Box. UML. Unified Modeling Lanaguage). 4.

(5) 1 INTRODUZIONE Il lavoro di tesi ha riguardato la progettazione e lo sviluppo di un simulatore di fluidi basato su SPH (Smoothed Particle Hydrodynamics), una tecnica mediante la quale, il fluido simulato viene rappresentato come un sistema di particelle che interagiscono tra loro in modo fisicamente realistico. Ogni particella ha delle proprietà fisiche intrinseche, quali densità, pressione, viscosità, che vengono influenzate nel tempo dalle particelle vicine e dalle forze che agiscono nel sistema stesso, quali la gravità. Il lavoro svolto ha come target principale l’utilizzo in ambienti virtuali e in computer games ma data la sua modellazione, potrebbe essere semplicemente adattato e trovare applicazione anche in altri contesti. Durante questo lavoro, si è cercato di ottenere un buon compromesso tra realismo dal punto di vista fisico, e prestazioni in termini di tempo di calcolo, mirando al real-time. Il realismo è stato raggiunto mediante l’applicazione del paradigma SPH, un metodo di interpolazione per sistemi di particelle che opera a livello locale, ovvero, che permette di calcolare con ottima approssimazione un insieme di proprietà fisiche in qualsiasi punto dello spazio preso in considerazione durante una simulazione. Per ottenere delle prestazioni che tendessero al real-time è stato necessario utilizzare strutture dati e algoritmi studiati appositamente per questo tipo di problemi, che ottimizzassero rispettivamente la rappresentazione compatta dei dati e lo sfruttamento di proprietà specifiche del sistema, per ottenere costi computazionali inferiori ai casi generali. Un ulteriore aumento della performance è stato possibile grazie all’uso intensivo della potenza di calcolo dalla scheda grafica. Le moderne schede grafiche hanno un numero di unità d’elaborazione e una potenza di calcolo ben maggiore delle CPU general-purpose. Lo sfruttamento di tali risorse ha consentito un significativo speed-up nelle prestazioni, dato dalla parallelizzazione del calcolo, specialmente nei punti di calcolo data-intensive (in particolare nel calcolo della fisica della simulazione). In questo lavoro di tesi, si è adoperata la tecnologia CUDA, basata su schede grafiche Nvidia. L’aumento di performance dato dall’utilizzo di questa tecnologia è stato particolarmente evidente prendendo in considerazione il numero di particelle del sistema.. 5.

(6) Durante la realizzazione di tale lavoro sono state combinate una serie di tecniche e paradigmi già esistenti in letteratura, quali SPH, tecniche di space-partitioning efficienti, ecc, con tecnologie nuove e di grande interesse, in particolare l’uso di CUDA per accelerare i calcoli più onerosi. Una nota peculiare è che l’intero lavoro utilizza come piattaforma Matlab, il che lo rende particolarmente adatto per simulazioni in campo scientifico e accademico, data la grande diffusione e utilizzo di tale strumento. Questo lavoro di Tesi è così organizzato: •. Capitolo 1 – INTRODUZIONE: viene presentato il lavoro svolto, menzionando gli obiettivi, i contributi, il tipo di lavoro svolto, le tecniche e tecnologie utilizzate, al fine di fornire una visione d’insieme del lavoro nel suo complesso.. •. Capitolo 2 – STATO DELL’ARTE: fornisce una panoramica dei concetti di base e delle tecniche utilizzate già note in letteratura. Particolare rilevanza viene data allo studio dei fenomeni fisici di un simulatore particellare dal punto di vista fisico-matematico prima, e algoritmico poi. Oltre a tale aspetto, vengono presentati le principali strutture dati e tecniche utilizzate in punti sensibili del simulatore, come varie soluzioni per la collision detection e lo space partitioning. Viene inoltre definito il modello SPH, e i principi di funzionamento di CUDA.. •. Capitolo 3 – PROGETTAZIONE: offre i dettagli delle fasi di sviluppo e della progettazione del software in tutte le sue parti. Sono riportati i modelli utilizzati nella progettazione e dettagli sull’architettura del software, oltre a dettagli su come librerie esterne siano state integrate nell’applicazione sviluppata.. •. Capitolo 4 – IMPLEMENTAZIONE: una descrizione dettagliata delle strutture dati utilizzate per realizzare i componenti principali dell’applicazione, e gli algoritmi più importanti per il suo funzionamento.. •. Capitolo 5 – ANALISI: uno studio delle performance e dei risultati ottenuti dall’applicazione, con particolare attenzione al confronto fra la versione CPUbased e quella GPU-based.. •. Capitolo 6 – CONCLUSIONI E SVILUPPI FUTURI: un rendiconto dei risultati ottenuti a fronte degli obiettivi che si volevano ottenere, e considerazioni sugli utilizzi e gli sviluppi futuri dell’applicazione realizzata.. 6.

(7) 2 STATO DELL’ARTE La simulazione di fluidi trova oggi applicazione in molteplici campi, e viene utilizzata per vari fini, da quello scientifico, a quello dell’intrattenimento: •. Nel settore medico è particolarmente interessante studiare il comportamento di fluidi corporei (sangue ed altri) in un organismo vivente.. •. Nel settore della climatologia le simulazioni di fluidi vengono utilizzate per studiare le maree oceaniche e per modelli di predizione di evoluzione climatica.. •. Nel settore dell’intrattenimento, particolare importanza rivestono gli ambiti cinematografico (si vedano gli effetti grafici dei più recenti film d’animazione o gli effetti speciali delle pellicole Hollywoodiane), e video ludico (i videogiochi più recenti hanno raggiunto un livello di realismo che rasenta la perfezione).. A seconda del campo d’applicazione, ci sono esigenze differenti, quindi anche i simulatori utilizzati hanno caratteristiche differenti e adoperano particolari tecniche per far fronte allo specifico problema da affrontare. Ad esempio, ai simulatori utilizzati per i film di animazione (come quelli prodotti dalla Pixar), sono richiesti la massima resa grafica e massimo realismo percepito, quindi tipicamente questo genere di software lavora offline, e, dopo aver eseguito tutti i calcoli necessari, si provvede in un secondo momento con la fase di rendering. Al contrario, in un videogioco ad esempio, dove il real-time è un’esigenza fondamentale, sono utilizzati simulatori che compiono calcoli con un livello d’approssimazione minore, ma che riescono a dare una resa quasi realistica in tempi molto stretti. Durante il lavoro di tesi, si è cercato di trovare il migliore trade-off tra realismo e prestazioni che tendono al tempo reale. Infatti, SPH è un metodo che offre un alto livello di realismo, ma che, settando opportunamente alcuni parametri, permette di alleggerire notevolmente i calcoli da compiere per ogni passo della simulazione.. 2.1 Simulazioni di Fluidi in tempo reale L’aumento della potenza di calcolo dei moderni processori, e ancora di più delle unità per l’elaborazione delle schede grafiche, che ha caratterizzato gli ultimi anni, ha permesso di ottenere simulazioni sempre più realistiche con performance che tendono. 7.

(8) sempre più al tempo reale. La tendenza dei principali produttori di processori, fino all’inizio degli anni 2000 è stata quella di aumentare la frequenza delle CPU, per far eseguire ad un singolo processore un numero sempre maggiore di operazioni nell’unità di tempo, fin quando ci si è resi conto che forse l’aumento delle prestazioni dovuto all’incremento della frequenza di clock (e all’applicazione di paradigmi superscalari sempre più raffinati), presentava un limite superiore, ponendo dubbi sulla validità della nota Legge di Moore, secondo la quale, il numero di transistor di un processore dovrebbe raddoppiare ogni 18 mesi circa, generando un miglioramento di performance, non necessariamente proporzionale, che fino a quel momento si era rivelata abbastanza corretta. La nuova tendenza quindi è diventata quella di non avere più un singolo processore superveloce, ma più processori, magari anche meno potenti, ma che globalmente comportano un aumento di performance, sfruttando varie tecniche di parallelizzazione. Lo stesso tipo di evoluzione c’è stata anche nel campo delle schede grafiche, sospinte dalle sempre maggiori richieste del settore video ludico. Parallelamente allo sviluppo delle CPU, anche i videogiochi sono diventati sempre più esosi come requisiti di sistema, tanto che le sole CPU non erano più sufficienti a far fronte alla enorme quantità di calcoli richiesti. Ecco quindi che anche le schede grafiche si sono via via trasformate, diventando oggi dei dispositivi ben più complessi e raffinati delle CPU, che sfruttano massicciamente vari paradigmi di parallelizzazione (soluzioni stream-parallel per ottimizzare la pipeline di rendering, e data-parallel per aumentare la banda di vari stadi della pipeline stessa). Le ultime schede grafiche montano un numero di processori ottimizzati per il calcolo vettoriale che varia da 8 (per le schede entry-level) fino a 512 (per quelle high-end level), garantendo prestazioni inimmaginabili fino a pochi anni fa. Questa evoluzione è particolarmente evidente, se si confrontano il numero di operazioni in virgola mobile eseguite nell’unità di tempo. Analizzando l’evoluzione delle CPU, e delle GPU, si nota come il divario diventi col tempo sempre più evidente. Dal grafico seguente emerge come il numero di GFLOPs (ovvero miliardi di Floating Point Operations Per Second) delle CPU cresca in modo pressoché lineare nel tempo, mentre quello delle schede grafiche mostra una crescita esponenziale.. 8.

(9) Figura 1 - Evoluzione delle prestazioni di CPU e GPU. Altro interessante aspetto da considerare nell’evoluzione di tali componenti, è la possibilità di sfruttare il cosiddetto GPGPU-computing (GPGPU sta per General Purpose GPU). Questo significa che la potenza di calcolo delle GPU non viene utilizzata solo per il calcolo orientato alla grafica, ma anche per eseguire calcolo general-purpose. Degli esempi in tal proposito sono PhysX, motore fisico supportato in modo nativo nelle ultime schede grafiche della Nvidia o il fatto che anche algoritmi di illuminazione globale particolarmente onerosi, come il ray tracing vengono realizzati ormai in real-time. Le simulazioni di fluidi, per loro natura, devono necessariamente contenere una certa componente fisica. Pertanto, indipendentemente dal modo in cui sono realizzate, e dall’utilizzo che se ne vuole fare, è inevitabile notare che esiste una proporzionalità abbastanza marcata tra il livello di realismo richiesto, e il numero di calcoli dedicati alla fisica da effettuare. Tutti i calcoli fisici comportano delle approssimazioni, e tale livello di approssimazione è fortemente discriminante sul livello finale di realismo che si ottiene. Se non ci sono i presupposti hardware per eseguire una massiccia quantità di calcoli pur ottenendo un risultato in real-time, allora le approssimazioni dovranno essere maggiori. L’aumento delle prestazioni dell’hardware degli ultimi anni ha permesso di implementare simulazioni piuttosto complesse in real-time con un livello di approssimazione molto basso.. 9.

(10) 2.1.1. Simulazioni basate su spazio delle coordinate Euleriano e Lagrangiano. I simulatori di fluidi e le applicazioni grafiche in generale, necessitano di un sistema di coordinate per poter rappresentare e gestire gli oggetti nello spazio. A tal fine, i sistemi di riferimento adoperati principalmente nel campo della fluidodinamica sono fondamentalmente quello Euleriano e quello Lagrangiano (1): •. Sistema delle coordinate Euleriano: secondo questo tipo di specificazione del moto del fluido, le proprietà di un flusso (densità, velocità, pressione), sono definite come funzione dello spazio, ossia del vettore posizione , e del tempo .. Una generica proprietà del flusso si esprime tramite una funzione del tipo = (, ). In questo modo, l’osservatore è solidale ad un punto di. osservazione fisso e ha la visione dell’intero campo di velocità (o densità, o pressione) in ogni istante, senza però avere alcun tipo di informazione sul moto della singola particella fluida. Tale approccio è generalmente utilizzato per simulazioni di oggetti rappresentati mediante mesh (vedere paragrafo successivo).. Figura 2 - Moto di un fluido in spazio delle coordinate Euleriano al tempo t0 e t1 (1). •. Sistema delle coordinate Lagrangiano: la descrizione Lagrangiana del moto focalizza l’attenzione non sul volume di controllo, ma sulla singola particella fluida. Le proprietà del flusso sono quindi funzioni della scelta del particolare. elemento fluido, oltre che del tempo . Pertanto, una generica proprietà di un elemento del fluido, si esprime tramite una funzione del tipo = ( , ), dove. denota la posizione nello spazio della singola particella al tempo iniziale . 10.

(11) Figura 3 - Moto di un fluido in spazio delle coordinate Lagrangiano al tempo t0 e t1 (1). Questi due modelli, si differenziano soprattutto per il calcolo della derivata sostanziale, ovvero l’operazione di derivazione che serve per valutare la variazione nel tempo di una grandezza scalare o vettoriale. Si prenda come esempio una proprietà del fluido, quale la velocità. La sua variazione nel tempo è numericamente uguale nelle due descrizioni, ma viene espressa in modo differente. Con il metodo Euleriano, l’accelerazione viene calcolata applicando la semplice derivata parziale rispetto al tempo di (, ). =. (, ) = + + + = + ( ∙ ∇). . Con il metodo Lagrangiano, l’accelerazione viene calcolata per ogni singola particella del fluido, quindi la sua formulazione è =. ( , ) ( , ) = . . Sebbene l’approccio Euleriano si riveli efficace per descrivere il moto di un fluido descritto dalle Equazioni di Navier-Stokes, l’approccio Lagrangiano ha il pregio di permettere il bilanciamento delle forze su una singola particella. Nel lavoro di tesi è stato utilizzato l’approccio Lagrangiano che ben si adatta a rappresentare il comportamento di singole particelle che compongono un fluido, ciascuna con una propria posizione nello spazio e proprietà indipendenti che le fanno evolvere nel tempo indipendentemente dal contesto generale. Il comportamento delle. 11.

(12) singole particelle è più o meno indipendente da quello delle altre, e non è dato solo da un insieme di funzioni dipendenti dal tempo, ma il comportamento è profondamente influenzato anche dalle proprietà delle particelle “vicine”, intendendo come vicine l’insieme di particelle in un certo intorno nello spazio tridimensionale.. 2.2 Simulazioni basate su sistemi di particelle Volendo rappresentare un fluido che abbia un comportamento fisicamente realistico, è naturale immaginare tale fluido come composto da un certo numero di elementi di base, proprio come le gocce che compongono ad esempio una massa d’acqua. La naturale proiezione dal modello fisico reale a quello simulato porta a rappresentare i singoli componenti reali di un fluido con una controparte simulata, detta in gergo “particella”, un’unità atomica a livello microscopico, parte di un contesto più ampio, che interviene nella descrizione di fenomeno di livello macroscopico. In particolare, un fluido a livello macroscopico, composto da un insieme di particelle, viene riferito mediante il nome di “Sistema di Particelle”. Le singole particelle del sistema, non sono in relazione 1:1 con le particelle che compongono un fluido reale (cioè, non rappresentano molecole, o addirittura gli atomi del fluido in esame, dato il numero di elementi incredibilmente grande di elementi da gestire), ma costituiscono delle approssimazioni, più o meno precise, in base al numero di elementi che compongono il sistema. È quindi chiaro che, se si sta modellando una superficie di fluido molto estesa, come ad esempio la superficie di un oceano, ogni particelle potrebbe rappresentare ad esempio l’equivalente di un litro d’acqua, mentre, se si vuole rappresentare la caduta di un fluido in un recipiente, a parità di numero di particelle utilizzate, ogni particella rappresenterebbe quindi l’equivalente di poche gocce d’acqua, ottenendo così anche effetti suggestivi, quali le increspature e il rimescolamento del fluido nel momento in cui viene fatto cadere nel recipiente. Modellare un fluido in questo modo, è il modo che garantisce la massima espressività e fedeltà al modello reale, ma chiaramente un maggiore costo in termini di calcoli da effettuare. Come già detto, tale costo è proporzionale al numero di oggetti da gestire, in quanto, generalmente, ad ogni particella (o gruppi di esse), viene associata una struttura dati a se stante. Oltre all’overhead per la gestione delle strutture dati, poiché ogni particella è un’entità a se stante, essa sarà sottoposta a forze derivanti. 12.

(13) dall’ambiente (gravità, attrito viscoso, ecc) e dall’interazione con le altre particelle, in particolare con quelle in un certo intorno (la densità, la pressione, la viscosità di particelle vicine influenzano le stesse proprietà di un’altra particella). Per strutturare il problema, è possibile sfruttare i paradigmi della programmazione orientata agli oggetti, che permettono un’immediata e naturale modellazione di tali fenomeni, permettendo di attribuire ad ogni elemento simulato, un proprio stato, e una serie di funzionalità per modificarlo.. 2.2.1. Integrazione Euleriana. Il metodo di Eulero è un una procedura numerica del primo ordine per risolvere equazioni differenziali ordinarie (ODE) in forma normale con un valore iniziale noto. Nelle simulazioni di fluidodinamica, e nel campo dell’animazione in generale, il metodo di Eulero è utilizzato per approssimare il comportamento di un oggetto che, sottoposto a delle forze, compie uno spostamento in uno spazio tridimensionale (o bidimensionale) secondo delle leggi. Tipicamente il movimento di una particella in un Sistema di Particelle è descritto da una curva, generalmente non nota a priori, che è possibile approssimare mediante il Metodo di Eulero, con une errore commesso calcolabile, dipendente dal passo di integrazione, ovvero dalla quantità di cui ci si sposta da un passo all’altro, mentre si “percorre” la curva (2). Per funzioni dipendenti dal tempo, tale passo è rappresentato dall’unità di tempo presa in esame. In generale, più piccolo è l’intervallo temporale, e migliore è l’approssimazione calcolata del moto di una particella. Il metodo di Eulero è utilizzato per risolvere problemi nella forma () = , (), ( ) = . Per approssimare ( + ∆), si utilizza la serie di Taylor, per la quale, tale quantità. per una funziona infinitamente derivabile è esprimibile come ( + ∆) = () + (∆) () +. (∆) (∆) () + () + … 2! 3!. Utilizzando tale approccio, e conoscendo il valore di ( ), applicando. iterativamente lo sviluppo di Taylor ad ogni passo, è possibile approssimare una funzione incognita nella variabile .. 13.

(14) L’errore che si commette nell’applicazione di tale metodo, dipende dal numero di addendi che si considerano nel polinomio appena costruito. Ad esempio, fermando lo. sviluppo del polinomio al termine con derivata di grado , l’errore sarà esprimibile come. la differenza tra il valore ottenuto dallo sviluppo di Taylor con ordine + 1, e il. polinomio preso in esame, quindi sarà dell’ordine di (ℎ!"# ), poiché tale valore è dominante sugli addendi successivi dello sviluppo di Taylor. Il metodo di integrazione che si viene a definire consta quindi dei seguenti passi:. 1. Definizione dello stato iniziale, ovvero valutazione di = ( ) e scelta di un passo di integrazione ∆, nel nostro caso.. 2. Valutazione di !"# = (!"# ), = 0 … + ∞ mediante lo sviluppo di Taylor.. 2.2.1.1 Metodi di Eulero Esplicito e Implicito Il metodo di Eulero appena descritto viene detto Metodo di Eulero in Avanti o Esplicito (Forward Euler Method). Questa variante viene detta “in avanti” o “esplicito”,. poiché ogni termine !"# è definito in funzione di termini già noti. In generale, questo. termine si può definire come. !"# = ! + ∆( ! , ! ) Una tecnica alternativa a quella descritta è chiamata Metodo di Eulero all’Indietro (Backward Euler Method) o Implicito (3). Questa tecnica si differenzia dalla precedente, in quanto il termine !"# è definito dall’equazione. !"# = ! + ∆( !"# , !"# ). quindi per la sua valutazione è necessario risolvere implicitamente un’equazione non lineare. Questa tecnica permette di ottenere una maggiore stabilità, ma anche un costo computazionale maggiore. Per la soluzione di tale equazione, viene generalmente utilizzato il Metodo di Newton-Raphson. 2.2.1.2 Metodo di Eulero Migliorato Una versione particolare del Metodo di Eulero che prende in considerazione termini oltre quello di primo grado, viene detta Metodo di Eulero Migliorato (2), che permette un migliore livello di approssimazione nella valutazione della funzione in esame.. 14.

(15) Nel caso del simulatore sviluppato per questo lavoro di tesi, è stato utilizzato tale metodo di integrazione. Ogni particella del fluido simulato, ha una propria posizione che varia nel tempo, calcolata in base alla velocità e all’accelerazione in ogni istante temporale. Come noto, la derivata prima dello spazio rispetto al tempo è la velocità, mentre la derivata prima della velocità rispetto al tempo (ovvero la derivata seconda dello spazio rispetto dal tempo) è l’accelerazione. Quest’ultima grandezza, viene calcolata attraverso il calcolo di tutte le forze agenti su una particella, e dividendo tale quantità per la massa della particella. Sfruttando questo metodo, quindi, ogni passo della simulazione diviene quindi: 1. Calcolo forze del sistema: Si calcolano le forze che agiscono sull’intero sistema di particelle, quali la gravità, la forza di pressione e quella viscosa. 2. Integrazione temporale, nella quale si aggiornano le velocità, le accelerazioni delle particelle, e le loro posizioni nello spazio.. a. Si inizializza la velocità per il passo + 1 &!"# = &!. b. Calcolo delle accelerazioni delle particelle, date dalle forze diviso la massa delle particelle !"# =. ' (. c. Integrazione temporale, con la quale si calcolano le differenze di velocità e accelerazione delle particelle, tenendo conto del passo di integrazione, e si aggiornano quindi le posizioni e le velocità per il passo + 1 della simulazione. ∆& = &! ∆. ∆ = ! ∆. )!"# = )! + ∆& &!"# = &! + ∆. 2.2.2. Collision detection e Space partitioning. Particelle che si muovono in uno spazio tridimensionale (o bidimensionale), sono sottoposte a vincoli nei loro movimenti, ed è quindi necessario rilevare gli ostacoli. 15.

(16) presenti nello spazio, e far si che le particelle interagiscano con essi. Il problema di rilevare contatti tra le particelle e una qualsiasi superficie dell’ambiente, prende il nome di Collision Detection, ovvero rilevazione delle collisioni. Per questo motivo è necessario, ad ogni passo della simulazione, conoscere la distanza di ogni particella del fluido da tutte le superfici che rappresentano un ostacolo al loro moto attuale. Generalmente si assume che una particella, in quanto unità fondamentale, non abbia una dimensione fisica apprezzabile, ma viene assimilata ad un punto, parte di una isosuperficie. È la isosuperficie stessa, di dimensioni macroscopiche, che gode di un volume, dato dalla somma delle distanze tra le particelle che la compongono. In questo lavoro di tesi, si è assunto che l’intera simulazione avvenga all’interno di un parallelepipedo rettangolo con dimensioni modificabili (anche a tempo d’esecuzione). Tale poliedro che funge da contenitore, viene indicato con il termine di Bounding Box (BB), che è a tutti gli effetti una Minimum Bounding Box (MBB). Tale struttura può essere rappresentata efficientemente come una matrice del tipo: * ∈ ℝ-×/. Tale matrice ha 4 righe, poiché ogni sua colonna definisce i parametri di un piano, (. rappresenta invece il numero di piani del contenitore, quindi, nel caso più semplice, di un parallelepipedo rettangolo, tale matrice sarà del tipo * ∈ ℝ-×0 avendo tale poliedro appunto sei facce, quindi sei piani che lo definiscono parametricamente. Una matrice così definita sarà formattata nel seguente modo: # 2 * = 1 4# #. #. 2 4. . 2 4. . 24 -. 3 23 43. 3. 0 20 40 5. 0. Dove il primo piano sarà definito dai parametri della prima colonna, quindi 6# = # + 2# + 4# + # Lo stesso dicasi vale per gli altri piani.. 16.

(17) Ogni particella invece, è rappresentata come un vettore di 4 scalari. I primi 3. definiscono la sua posizione nello spazio (componenti , , ), mentre il quarto contiene. un valore costante, in questo caso 1, utilizzato per motivi d’efficienza nei calcoli. La presenza di tale valore aggiuntivo risiede nel fatto che, rappresentando anche i piani del bounding box come un vettore di lunghezza 4, risulta immediato effettuare calcoli specifici che coinvolgono piani e particelle, effettuando calcoli vettore-vettore (o più propriamente matrice-matrice). Quindi, la generica particella i-esima avrà una struttura del tipo )7 = (7 , 7 , 7 , 1) Le particelle non sono rappresentate indipendentemente, ma a livello di strutture dati, vengono organizzate come elementi di un vettore colonna. Dal momento che ogni particella è definita da 4 valori scalari, allora il vettore che rappresenta le posizioni delle particelle è in realtà una matrice del tipo 8 ∈ ℝ!×-. Dove ogni riga di tale matrice rappresenta una delle particelle del sistema, quindi,. S avrà il seguente aspetto. # 8=9 ⋮ !. # ⋮ !. # ⋮ !. 1 ⋮; 1. Una volta noti i piani che compongono il bounding box, e le posizioni delle particelle è necessario calcolare ad ogni passo della simulazione la distanza di tutte le particelle da tutti i piani del bounding box. La formula generale per calcolare la distanza di un punto da un piano è. () , 6) =. | + 2 + 4 + | √ + 2 + 4 . Dal momento che, nel nostro caso tutti i piani sono ortogonali tra loro, le loro equazioni sono definite da vettori con i primi 3 elementi tutti nulli tranne uno, e il quarto elemento uguale al parametro dell’equazione, che definisce la distanza di tale. piano dall’origine delle coordinate cartesiane utilizzate nella rappresentazione. Fatta questa assunzione, e applicando la formula per il calcolo della distanza di un punto da un. 17.

(18) piano, si nota che il denominatore di tale formula vale sempre 1, pertanto, ai fini del calcolo, esso può essere trascurato, quindi, il calcolo di tale distanza si riduce ad essere. () , 6) = | + 2 + 4 + | Tale quantità può essere ottenuta moltiplicando un vettore riga contenente la posizione di una particella, per un vettore colonna, rappresentante l’equazione di un. piano. Espandendo questo ragionamento a particelle ed ( = 6 piani, si può. moltiplicare la matrice 8 delle posizioni delle particelle, e la matrice * dei piani del. Bounding Box, ottenendo una matrice. ? = * ∙ 8, ? ∈ ℝ!×0 che indica la distanza di ogni particella (in riga i-esima) da ogni piano (in colonna jesima).. Figura 4 - Particelle all'interno del Bounding Box. Il costo computazionale per la costruzione della matrice ? è pari a quello di un. prodotto tra matrici rettangolari, di dimensioni ( × @ e @ × , quindi è dell’ordine di. (( ∙ @ ∙ ). Nel caso preso in esame, @ e sono due costanti molto piccole (4 e 6. rispettivamente), quindi, ai fini del costo computazionale, @ ∙ può essere considerato. come una costante moltiplicativa, quindi la complessità di tale operazione prodotto si riduce quindi a ().. In questo lavoro si è adoperato un tipo di bounding box nel quale i piani delle facce non sono arbitrari, ma sono ortogonali tra loro e paralleli agli assi del sistema di coordinate. Tale tipo di bounding box prende il nome di Axis Aligned Bounding Box (AABB). Quindi i bounding box presi in esame definiscono dei parallelepipedi rettangoli. 18.

(19) Questa scelta ha ripercussioni non banali sulla strutturazione del problema, infatti la matrice che lo rappresenta diventa. 1 0 0 0 1 0 *=1 0 0 1 . # . 1 0 0 0 1 0 5 0 0 1 . - 3 0. La sottomatrice-matrice superiore comprendente le righe da 1 a 3, è strutturata come due matrici identità affiancate orizzontalmente, mentre l’ultima riga indica le distanze dei piani rispetto al punto d’origine delle coordinate cartesiane. Grazie a questa particolare configurazione, il calcolo delle distanze tra le particelle e i piani del bounding box, può essere ricondotto ad una semplice sottrazione tra una componente della posizione delle particella, e il parametro 7 del piano in esame. Di fatto, la matrice del bounding box potrebbe essere compressa in un semplice vettore delle componenti 7 degli piani. 2 = ( # , , … , ! ). Quindi, data una particella )7 = (7 , 7 , 7 ), la distanza dal piano 6- : = - , ad. esempio, si valuta come. ()7 , 6- ) = |7 − - | Tale semplificazione comporta anche una notevole guadagno in termini computazionali, e, quando possibile, questo metodo è stato per la costruzione della. matrice ? mediante prodotto matrice-matrice. Dati = 6 piani del bounding box, sono. necessarie solo 6 sottrazioni per ottenere un vettore di dimensione 1 × 6, che. rappresenta la distanza di una singola particella da tutti i piani del bounding box. Tale. vettore costituisce una riga della matrice delle distanze che si vuole costruire, e va costruito un vettore per ogni particella del sistema. Il costo computazionale è quindi. dell’ordine di (). Il motivo per il quale questo metodo viene preferito al calcolo del. prodotto matrice-matrice, risiede nel fatto che, a parità di ordine di grandezza, la costante moltiplicativa è molto più piccola, ed inoltre, ad ogni passo iterativo di tale metodo, sono richieste 6 sottrazioni, mentre nel caso precedente, erano richiesti 4 prodotti scalari e una somma per ogni elemento della matrice costruita. La sottrazione è. 19.

(20) una operazione intrinsecamente più veloce della moltiplicazione al livello della macchina, e quindi fornisce un ulteriore speed-up nelle performance. Una volta ottenuta la matrice delle distanze (mediante una delle due tecniche. esposte), è possibile ricercare al suo interno le particelle con una distanza ()7 , 6) ≤ D,. con D fissato a priori, che indica la distanza al di sotto del quale, una particella si. considera collidente con un piano. In caso di collisione, si procede a modificare opportunamente le componenti del moto della particella (ovvero verso di una componente del suo vettore velocità). Prendendo in considerazione questo ulteriore procedimento, il generico passo della simulazione si arricchisce di un nuovo passaggio: 1. Calcolo forze del sistema. 2. Calcolo dei vincoli spaziali, ovvero rilevazione delle collisioni tra particelle e piani e modifica del moto delle particelle collidenti 3. Integrazione temporale Oltre a gestire le collisioni delle particelle con i piani, è necessario conoscere anche le distanze reciproche tra di esse. In questo modello, non vengono gestiti gli urti tra particelle, poiché, si vuole simulare un fluido. L’importanza di conoscere le distanze tra le particelle, risiede nel fatto che, secondo il modello SPH, le proprietà di una particella influenzano quelle delle particelle vicine. In modo rigoroso, sarebbe corretto affermare che le proprietà di ogni particella del sistema, influiscono su quelle di tutte le altre particelle. Poiché tale effetto tende ad attenuarsi molto velocemente con l’aumentare delle distanze, in relazione a masse relativamente piccole, ha perfettamente senso prendere in considerazione una approssimazione data dalla valutazione delle (. particelle più vicine, con ( definito a priori (tale parametro può variare anche in base al numero delle particelle che costituiscono il sistema). 2.2.2.1 Space Partitioning mediante KD Tree Una nota tecnica per il partizionamento dello spazio è il KD-Tree, che permette di definire con un minimo sforzo computazionale, data una particella, quali sono le sue vicine. K-D Tree sta per albero a K dimensioni, strutturato come un albero binario che partiziona uno spazio a @ dimensioni, in una serie di sottospazi con lo stesso numero di. dimensioni, ma di volumi inferiori (4). Questa suddivisione in sottospazi avviene. 20.

(21) scegliendo un punto nello spazio da partizionare, e definendo un piano opportunamente allineato (alternando la dimensione di riferimento ad ogni passo) passante per tale punto all’interno dello spazio. Il piano creato, detto piano di taglio, biseca uno spazio in due sottospazi, ed è ortogonale o parallelo a tutti gli altri piani di taglio generati ai passi precedenti. La scelta della dimensione rispetto alla quale creare un piano secante, dipende dall’algoritmo e dallo stato del partizionamento in un dato istante (5). Questa procedura viene eseguita ricorsivamente tagliando sottospazi sempre più piccoli, finché non viene verificata una condizione di arresto. La procedura di partizionamento termina quando ogni sottospazio generato contiene al massimo un numero fissato di particelle (1 nel nostro caso). La scelta del punto in cui effettuare un taglio, nell’algoritmo avviene scegliendo il mediano tra gli indici dei punti rispetto ad una certa dimensione. Le dimensioni sono alternate ciclicamente (round-robin).. Figura 5 - Esempio di 3D Tree (Wikipedia). La procedura più costosa e rilevante dal punto di vista delle performance quando si effettueranno delle query, nell’utilizzo di queste struttura dati è la costruzione. 21.

(22) dell’albero, che costa ( log ) operazioni, in quanto al suo interno, viene eseguito l’algoritmo di ordinamento heapsort, per ordinare gli indici dei punti rispetto ad ogni dimensione, ed inoltre, vengono generati nodi (che incapsulano informazioni sui piani di taglio) mediante una procedura ricorsiva che lavora ad ogni passo su un numero di nodi che è la metà del passo precedente. Particolare importanza ricoprono in fase di costruzione dell’albero, la scelta della dimensione rispetto alla quale effettuare un taglio, e del punto in corrispondenza del quale effettuare tale operazione. Tutte le query hanno costo al più logaritmico rispetto al numero di punti, quindi dell’ordine di (log ). In particolare, questa struttura dati permette di trovare in modo efficiente le @ particelle più vicine dato un punto dello spazio.. 2.2.2.2 Space Partitioning mediante Spatial Hashing L’hashing spaziale è un processo mediante il quale un dominio spaziale in 2D o 3D viene proiettato in una tabella hash ad una dimensione (6). In questo modo, è possibile riferire determinati punti dello spazio con accesso casuale effettuato in tempo costante, tramite una funzione di hash. Per realizzare questa tecnica, sono necessari una griglia 2D o 3D, una funzione di hash e una tabella hash. Questa tecnica si compone di vari passi: innanzi tutto, è necessario decomporre uniformemente il volume dello spazio in elementi più piccoli, detti celle, di dimensione fissa. Ogni cella accoglierà un certo numero di elementi del volume, nel caso in esame, un certo numero di particelle. A livello di strutture dati, si associa ad ogni cella un bucket, una struttura contenente una lista di tutte le particelle che si trovano all’interno di una cella. A partire da un insieme di particelle, è possibile trovare per ognuna, il bucket d’appartenenza mediante una funzione di hash, che mappa le coordinate tridimensionali della particella in un punto in uno spazio 1D. La scelta della funzione di hash è un aspetto fondamentale. La bontà di tale scelta dipende da vari fattori (7). La funzione di hash scelta dovrebbe essere: •. Univocamente determinata, ovvero, dato un certo input, deve restituire uno e un solo output. •. Deve essere “semplice”, ovvero, dato che si vuole realizzare un’applicazione real-time, sono preferibili funzioni che non utilizzino operazioni “lunghe”, come divisioni in virgola mobile, radici quadrate, funzioni trigonometriche. L’ideale è utilizzare operazioni “brevi”, come somme e prodotti.. 22.

(23) •. Dovrebbe distribuire gli elementi in modo più uniforme possibile, così da non avere bucket eccessivamente pieni, e altri vuoti (questi ultimi si traducono anche in un inutile spreco di memoria, che, in casi limite, potrebbe essere non trascurabile).. Una funzione di hash semplice, veloce e che garantisce una buona uniformità dei valori restituiti consiste nell’associare ad ogni particella un valore hash uguale alla posizione data dall’enumerazione della cella (bucket) nella quale si trova. Vale a dire,. che se la particella ) di coordinate H , H , H si trova nella cella con con indice I, allora. si fa in modo che ℎH , H , H = I, dove ℎ rappresenta la funzione di hash. Per. ottenere questo risultato, si tiene conto di vari elementi: • •. Si definisce una unità di riferimento usata come dimensione di una cella. Sia . tale unità. Pertanto, una cella dello spazio è un cubo di volume .. Si conoscono le dimensioni dello spazio da suddividere, ovvero del bounding box: WIDTH, HEIGHT, DEPTH. In termini di celle quindi, il bounding box è formato da. JKLMN NPKQNM LPRMN ∙ O ∙ O O. = SI ℎ ∙ ℎTIUℎ ∙ T)ℎ celle.. Tenendo conto di tali elementi, una funzione hash di semplice ed efficiente è ℎH , H , H = V. H H H W + XV W ∙ SI ℎY + XV W ∙ SI ℎ ∙ ℎTIUℎY . Questa funzione restituisce l’indice della cella/bucket d’appartenenza della particella.. 23.

(24) Figura 6 - Esempio di Spatial Hashing nel caso bidimensionale (8). Utilizzando una funzione di hash siffatta, si produce una corrispondenza topologica 1:1 tra l’indice di una cella e la sua posizione nello spazio. Tale proprietà può essere sfruttata per calcolare in tempo costante e in una sola volta, gli indici delle 26 celle dell’intorno nello spazio tridimensionale. Fissando opportunamente la dimensione delle celle (il parametro ), è possibile. calcolare le particelle più vicine a quella di riferimento, entro un raggio definito,. semplicemente confrontando le distanze delle particelle contenute nella cella d’appartenenza, e nelle celle adiacenti. Tale procedura, ha un costo computazionale. dell’ordine (1). Per l’esattezza, il costo di tale procedura è dell’ordine di () nel caso. in cui tutte le particelle del sistema siano contenute tra la cella di riferimento e le sue 26 vicine. Dal momento che le celle e la funzione hash sono concepite per distribuire le particelle tra un alto numero di celle, tale costo può essere espresso più propriamente da Z(), che, per un numero molto piccolo di particelle per cella (caso tipico), può. essere a sua volta approssimato con (1). Data questa premessa, nel caso si cerchino le. prime @ vicine di tutte le particelle del sistema, l’intera procedura di ricerca ha quindi. un costo complessivo dell’ordine di ().. Per lo spatial hashing esistono anche funzioni di hash alternative, e più complesse, che garantiscono una maggiore uniformità dei risultati, utilizzando prodotti tra numeri primi grandi, elevamenti a potenze con esponenti molto grandi, e calcoli modulari. Tale vantaggio, evidente soprattutto dal punto di vista del complessità computazionale (diminuisce potenzialmente la costante moltiplicativa nel calcolo di tale complessità),. 24.

(25) comporta però un sforzo computazionale molto maggiore in fase di calcolo della funzione hash per un singolo punto. In più, dato un indice di cella calcolato con una funzione siffatta, l’unico modo per conoscere l’indice delle celle limitrofe, è applicare la stessa funzione ad un insieme di punti appartenenti a celle contigue. Questo porta quindi al calcolo di 27 funzioni di hash per ogni punto da elaborare, più i calcoli necessari alla ricerca dei vicini all’interno delle celle trovate.. Trovare i vicini di ogni particella del sistema, permette un raffinamento del primo punto del generico passo della simulazione: 1. Calcolo forze del sistema. Trovando i vicini di ogni particella del sistema, è possibile definire come le proprietà di ogni particella influenzano (e sono influenzate) (da)i vicini. 2. Calcolo dei vincoli spaziali 3. Integrazione temporale. 2.3 Modellazione di fenomeni fisici Per ottenere un simulatore di fluidi fisicamente realistico, è necessario tenere conto delle leggi fisiche che governano il sistema che si vuole modellare, e definire quindi delle approssimazioni accettabili dal punto di vista computazionale. In fisica, e in particolare in fluidodinamica, il comportamento di un fluido dal punto di vista macroscopico è descritto mediante le equazioni di Navier-Stokes.. 2.3.1. Equazioni di Navier-Stokes. Le equazioni di Navier-Stokes sono un sistema di equazioni differenziali alle derivate parziali che descrive il comportamento di un fluido a livello macroscopico (9). Esse sono valide sotto l’ipotesi della continuità del fluido in esame. Quindi, tali equazioni non sono più valide nel caso di un gas rarefatto, ad esempio. Esse fanno parte dei 7 problemi del millennio, e a tutt’ora, non esiste ancora una soluzione analitica, tranne che per pochi casi particolari. Nella loro forma generale, esse coinvolgono 5 equazioni scalari differenziali alle derivate parziali e 20 variabili. Il bilancio. 25.

(26) tra equazioni e incognite avviene con la definizione delle proprietà del fluido considerato, delle eventuali forze di campo in gioco e con considerazioni matematiche. Inoltre, a causa della loro non linearità, le equazioni di Navier-Stokes non ammettono quasi mai una soluzione analitica, ma esclusivamente numerica. Le equazioni di NavierStokes sono in grado di descrivere qualsiasi tipo di fluido, anche turbolento (ovvero un fluido nel quale le traiettorie delle particelle di flusso non sono costanti nel tempo). Le equazioni vengono completate da condizioni al contorno e dalle condizioni iniziali. La soluzione delle equazioni fornisce il campo delle velocità del fluido. Da questo sarà poi possibile risalire a tutte le grandezze che caratterizzano il flusso. Per il simulatore oggetto della tesi, e per la simulazione di fluidi in generale, si tiene conto delle equazioni di Navier-Stokes per fluidi incomprimibili, che sono: [\ 1 = [\ ∙ ∇ [\ + ∇) = U\ + ^∇ ∙ ∇ [\ ] ∇∙ [\ = 0. Dove: • • • • •. [\ è utilizzato per indicare la velocità del fluido.. ] indica la densità del fluido.. ) indica la pressione, la forza che il fluido esercita in ogni unità di volume.. U\ indica l’accelerazione di gravità. ^ è tecnicamente chiamato viscosità cinematica, e misura quanto è viscoso un fluido.. La prima equazione è chiamata “Momentum Equation”, o “Equazione del Bilancio della Quantità di Moto”. Essa è rappresentata in forma vettoriale, quindi può essere. scomposta in 3 equazioni distinte per ognuna delle componenti dello spazio , , . Essa. non è altro che una forma alternativa per rappresentare la ben nota equazione di. Newton '\ = ( \, e permette di calcolare l’accelerazione di un fluido sottoposto a varie. forze.. La seconda equazione invece è la cosiddetta “Condizione di Incompressibilità”, e garantisce appunto questa caratteristica del fluido nella sua modellazione.. 26.

(27) 2.4 Smoothed Particle Hydrodynamics Smoothed Particle Hydrodynamics (SPH) è un metodo computazionale per la simulazione di fluidi basati su particelle. Nato nel campo dell’astrofisica per studiare la formazione e l’evoluzione di ammassi stellari, ha poi trovato applicazione in vari altri campi, come la vulcanologia, la balistica, l’oceanografia e la simulazione di fluidi (10) (11). Questo approccio suddivide un fluido in un insieme di elementi discreti, detti particelle, che possono muoversi nello spazio secondo le leggi descritte in precedenza. È un metodo di interpolazione che adotta un approccio Lagrangiano, nel quale, definendo il valore di una proprietà (ad esempio la densità) in alcuni punti dello spazio (le particelle possono essere considerate come punti dello spazio con densità maggiore di 0), è possibile valutare il valore di tale proprietà in qualunque punto dello spazio, mediante interpolazione. Le particelle del sistema, godono di caratteristiche e proprietà fisiche, quali massa, posizione,. velocità,. densità,. ecc.. ed. interagiscono. fra. loro. influenzandosi. reciprocamente. Per modellare le interazioni tra particelle, è necessario definire alcuni concetti. Innanzitutto, si definisce una distanza detta raggio o supporto SPH, indicata. generalmente con il simbolo ℎ; tale quantità indica l’ampiezza dell’intorno entro il quale. una particella interagisce con le sue vicine. Data una particella )7 , quindi, le sue vicine si definiscono come. TIUℎ2Z_`()7 ) = a)b : ()7 , )b ) ≤ ℎc. Dove indica la distanza in modulo tra le posizioni delle due particelle nello spazio.. Generalmente si indica con il simbolo _ la posizione nello spazio della particella )7 , e con. _b quella della particella )b , pertanto, la definizione precedente diviene TIUℎ2Z_`()7 ) = a)b : d_ − _b d ≤ ℎc. Altro punto fondamentale in SPH è il modo in cui le particelle si influenzano a. vicenda, quando sono vicine. In generale, si indica con e(_) una generica proprietà della. 27.

(28) particella in posizione _. I contributi di ogni vicina ad una proprietà, sono pesate rispetto alla distanza e alla densità dalla particella di riferimento secondo l’equazione e(_) = f (b b. eb gd_ − _b d, ℎ ]b. Dove: _ indica, come detto, la posizione della particella di riferimento, l’indice h denota la. generica particella vicina a quella di riferimento, di cui, _b ne indica la posizione, (b la. massa, ]b la densità e eb il valore della proprietà che si sta valutando. Altro. fondamentale componente dell’equazione è la funzione g, detta smoothing kernel. (vedi paragrafo successivo), che definisce esplicitamente il modo in cui delle particelle. vicine interagiscono. Per qualsiasi proprietà, l’equazione di riferimento è sempre la. stessa. Gli unici elementi che cambiano, sono ovviamente eb , e lo smoothing kernel, infatti si utilizza una funzione differente a seconda della proprietà che si vuole calcolare. Una aspetto importante da notare è che il termine. /i ji. presente nell’equazione,. rappresenta il volume della particella in esame, quindi si può affermare che tutti i calcoli delle proprietà SPH vengono effettuati rispetto al volume.. 2.4.1. Grandezze fisiche utilizzate nelle simulazioni. Il fluido che è stato modellato in questo lavoro, prende in considerazione varie grandezze fisiche (12) che, agendo sulle singole particelle, concorrono a definire il comportamento del fluido stesso a livello macroscopico. Potrebbe sembrare anti intuitivo associare delle proprietà fisiche a unità fondamentali come le particelle, ma, come già detto, le particelle oggetto di questo lavoro, non sono equivalenti a quelle considerate in fisica, ma si possono considerare elementi sufficientemente complessi e “voluminosi” da poter godere di proprietà tipiche di oggetti di tipo macroscopico. Le principali proprietà prese in considerazione sono: •. Densità. La densità è la proprietà fondamentale delle particelle di un fluido, in quanto da essa dipende la maggior parte delle altre. All’inizio della simulazione, viene assegnata a tutte le particelle del sistema una determinata densità di. 28.

(29) base, coerentemente con il fluido in esame. Tale densità di base varia a seconda del tipo di fluido preso in esame. •. Pressione. Le particelle del sistema, in quanto dotate di una massa e di un volume, hanno una propria pressione. Il calcolo di tale proprietà, utilizzando anche la densità, concorre al calcolo della forza di pressione, che, contribuisce insieme alle altre forze a variare il moto e il comportamento delle particelle stesse.. •. Viscosità. La viscosità delle particelle è costante, in quanto è definita dal coefficiente di attrito viscoso, tipico di ogni fluido. Tale proprietà viene utilizzata, insieme alla densità per determinare la forza di viscosità, che varia nel tempo in base alla densità delle particelle e al coefficiente d’attrito, appunto.. Oltre alle forze di pressione e di viscosità, nel sistema agisce anche la forza di gravità. Essa varia in base alla densità della particella in esame, e non alla sua massa, come avviene per corpi solidi. Partendo dall’equazione generica per il calcolo di una proprietà SPH, e(_) = f (b b. eb gd_ − _b d, ℎ ]b. e sostituendo le proprietà prese in esame con il termine generico eb , si hanno quindi. le equazioni che definiscono il calcolo delle proprietà rilevanti per le particelle. L’equazione per il calcolo della densità è quindi ](_) = f (b gd_ − _b d, ℎ b. poiché il rapporto fra le densità è costante e pari a 1. Per il calcolo di grandezze relative ai fluidi, è spesso necessario calcolare il gradiente e il laplaciano di tale equazione. Tali funzioni si riducono al calcolo del gradiente e del laplaciano dei kernel. Quindi il gradiente di e è definito come ∇e(_) = f (b b. eb ∇gd_ − _b d, ℎ ]b. Mentre il laplaciano è calcolato come. 29.

(30) eb ∇ gd_ − _b d, ℎ ]b. ∇ e(_) = f (b b. Partendo da questi presupposti, e applicando le equazioni di Navier-Stokes, è quindi possibile definire delle equazioni per il calcolo delle forze che governano il sistema di particelle. La forza di gravità esercitata su una generica particella sarà 7. klmn7op. = ]7 U. dove U rappresenta l’accelerazione di gravità. La forza di pressione è rappresentata da 7. HlqrrOlq. = − f (b b. Mentre la forza viscosa è data da 7. n7rstr7op. = u f (b b. )7 + )b ∇gd_ − _b d, ℎ 2]b. &b − &7 ∇ gd_ − _b d, ℎ ]b. Dove u indica il coefficiente di attrito viscoso. 2.4.2. Smoothing Kernels. Una funzione del tipo g(_, ℎ) viene detta smoothing kernel con supporto h, ed è. una funzione che gode di varie proprietà: è simmetrica radiale, quindi g(_, ℎ) =. g(−_, ℎ), è una funzione liscia, cioè ammette derivate parziali di qualsiasi ordine, e. normalizzata con supporto finito, ovvero v g(_, ℎ) _ = 1 e g(_, ℎ) = 0 per _ ≥ ℎ. Per calcolare forze diverse, sono utilizzati kernel differenti, opportunamente progettati per modellare il comportamento che si attende per il particolare tipo di forza. Per il calcolo della densità, viene utilizzato il kernel gHtxp0 definito come gHtxp0 (_, ℎ) =. 315 (ℎ − _ ) 0 ≤ _ ≤ ℎ~ | 646ℎ{ 0 }_I(TI. 30.

(31) Per la pressione viene utilizzato il kernel grH7p definito come grH7p (_, ℎ) =. 15 (ℎ − _) 0 ≤ _ ≤ ℎ~ | 6ℎ0 0 }_I(TI. Per il calcolo della viscosità viene utilizzato il kernel gn7rstr7op definito come 15 − _ + _ + ℎ 0 ≤ _ ≤ ℎ~ gn7rstr7op (_, ℎ) = 2ℎ ℎ 2_ 26ℎ 0 }_I(TI. Nella figura sotto sono mostrati gli smoothing kernel elencati, rispettivamente. gHtxp0 , grH7p , gn7rstr7op . Le linee continue rappresentano i kernel, le linee sottili. rappresentano i loro gradienti in direzione dei centri, e le linee tratteggiate rappresentano i laplaciani. Le funzioni cambiano al variare del supporto ℎ.. Figura 7 - Smoothing Kernels (13). 2.5 La tecnologia CUDA CUDA, acronimo di Compute Unified Device Architecture, è un framework sviluppato da nVidia attorno al 2007 per sfruttare l’architettura di elaborazione in parallelo delle GPU. Essa rende possibile sfruttare la potenza di calcolo della GPU mediante la scrittura di codice che viene eseguito direttamente sui core della scheda grafica, sfruttandone il massiccio parallelismo (in particolare in quelle di ultima generazione). Questo framework (14) offre agli sviluppatori un set di istruzioni native per la computazione parallela di elementi delle GPU. CUDA si basa su un linguaggio che è. 31.

(32) un’estensione del C++, e ne conserva molte caratteristiche, salvo alcune eccezioni che dipendono anche dalle funzionalità dell’hardware sottostante. Altre tecnologie grafiche sono OpenCL e Direct Compute di Microsoft, che combinano l’uso di CPU e GPU per accelerare il rendering di scene complesse. Inoltre, CUDA trova applicazione anche in frame work come Matlab, tramite l’utilizzo sottoforma di libreria. Per lo sviluppo di questo lavoro di tesi, CUDA è stata utilizzata sia in forma pura, sia tramite una libreria per Matlab, dal nome GPUmat, che consente di eseguire calcoli su vettori Matlab sfruttando la tecnologia CUDA. Si è scelto di adoperare una soluzione basata su Matlab e CUDA, poiché è risultata la migliore combinazione tra flessibilità di programmazione e performance. Un ulteriore vantaggio di questa combinazione è rappresentata dal fatto che sia Matlab che CUDA sono ambienti di sviluppo multipiattaforma, ed un eventuale conversione per un sistema operativo differente, sarebbe praticamente immediato. Recentemente Mathworks ha rilasciato una versione di Matlab con il supporto nativo per il calcolo basato su GPU. Questa nuova feature permetterà anche agli utenti non specializzati in questo ramo della programmazione di sfruttare la potenza di calcolo dell’hardware grafico. Tale feature non è stata sfruttata in questo lavoro, poiché la libreria GPUmat ha rappresentato un valido strumento per ottenere ottimi risultati, e perché il rilascio di tale versione è avvenuto quando questo lavoro era già in fase conclusiva di sviluppo. Direct Compute è una libreria parte di DirectX e permette di eseguire calcoli su GPU in ambienti operativi Microsoft, ma presenta come svantaggi il fatto di non essere portabile verso altri sistemi operativi, e l’intrinseca complessità del codice DirectX. La tecnica di utilizzare la GPU come una normale CPU, quindi per scopi diversi dalla creazione di un’immagine tridimensionale, prende il nome di GPGPU, ovvero General Purpose computing on GPU, e sta riscuotendo un notevolissimo successo soprattutto nei settori del calcolo scientifico e nello scenario video ludico, poiché fornisce all’utilizzatore una potenza di calcolo supplementare per l’elaborazione di dati, precedentemente ricercata nella sola CPU. Oltre ad aumentare la potenza di calcolo di una macchina, l’utilizzo del GPGPU, offre il vantaggio di alleggerire, anche notevolmente il carico di lavoro della CPU, che potenzialmente, può eseguire operazioni di natura diversa mentre. 32.

(33) la GPU lavora sul suo stream di dati. Questa caratteristica è fortemente dipendente dall’algoritmo che si vuole eseguire.. Figura 8 - Confronto fra l'architettura di una CPU e di una GPU (14). Confrontando l’architettura di una CPU e quella di una GPU che supporta CUDA, si nota quanto siano differenti: una CPU ha un’interfaccia verso la memoria principale, una cache e un’unità di controllo condivise tra tutti i core di elaborazione che vi risiedono. Ciò significa che, a parte il parallelismo indotto dal fatto che si tratti di una CPU superscalare, questa unità funziona in modo sostanzialmente sequenziale, poiché un singolo processo non può essere eseguito su più di una unità di elaborazione alla volta. Una GPU è strutturata invece per essere orientata al calcolo parallelo, in particolare sfruttando il paradigma data-parallel che ha permesso di accelerare notevolmente le varie fasi della pipeline grafica. Come una CPU, anch’essa ha un’interfaccia verso la memoria principale (con la quale deve scambiarsi dati), ma a differenza della prima, la GPU ha un numero molto maggiore di core di elaborazione. Tali core sono topologicamente disposti in modo da implementare la forma di parallelismo dataparallel, e sono suddivisi in gruppi, ognuno dei quali detiene una propria unità di controllo e una propria cache. Questo permette di parallelizzare il flusso di dati sia in ingresso che in uscita dei core di elaborazione. Le prime versioni di Graphic Processing Unit consentivano una flessibilità a livello di specifiche operazioni della pipeline grafica come vertex e pixel shaders realizzate con unità dedicate. Il passo seguente è stato proprio quello di ottenere delle unità di calcolo flessibili da applicare alle varie fasi della pipeline ovvero a calcoli generici.. 33.

(34) L’elaborazione data-parallel, mappa gli elementi dei dati da elaborare in threads d’esecuzione parallela. Pertanto, il principio sul quale si basa il funzionamento di tali architetture, consiste nello scomporre i dati in ingresso (ad esempio un vettore o una matrice) in parti più piccole che vanno date in pasto ai singoli core che eseguono tutti le stesse operazioni sui dati in input. CUDA si basa su tre astrazioni fondamentali: una gerarchia nei gruppi di thread, memorie condivise, e sincronizzazione. Un thread è unità d’esecuzione elementare eseguita in un ambiente parallelo. Un input di dimensioni arbitrarie viene partizionato in un certo numero di elementi più piccoli. Ognuno di tali elementi viene dato in pasto ad un core d’elaborazione del sistema data-parallel, che lo esegue come thread, e, una volta terminati i calcoli, è pronto ad eseguire la stessa funzione su un nuovo elemento dello stesso tipo. Tutti i core del sistema, eseguono la medesima funzione su tutti gli elementi di input, finché non è sono elaborati tutti gli elementi in input. Questo approccio ottimizza il fattore di sfruttamento e minimizza i tempi morti della GPU. L’efficienza di tale approccio, dipende molto dalla strutturazione dell’algoritmo, che, per essere efficiente, deve generare un input che si presti bene ad essere partizionato per un calcolo parallelo di questo tipo. I thread in esame sono concettualmente e strutturalmente differenti dai thread dei sistemi operativi. La funzione eseguita in un thread è detta funzione kernel, e viene eseguita sui core d’elaborazione della GPU. Una funzione kernel è una funzione in linguaggio C, ma che sfrutta le estensioni di CUDA mediante alcune istruzioni aggiuntive. La definizione di un kernel, richiede un prefisso, generalmente __global__, che ne definisce la visibilità e il contesto all’interno del quale può essere invocato (esistono anche altri prefissi, che definiscono diversi livelli di accessibilità e visibilità). Le funzioni marcate con __global__ sono direttamente invocabili anche dall’esterno, quando il codice venisse compilato, non come eseguibile, ma in formato cubin. Altra peculiarità di tali funzioni, è il modo in cui sono invocate: quando i thread sono eseguiti per una computazione parallela, essi vengono organizzati secondo una ben determinata gerarchia, che ne definisce il livello d’accessibilità alla gerarchia delle memorie condivise. I punti fondamentali sui quali si basa tale organizzazione sono: quello di blocco, insieme. 34.

(35) ordinato di thread, e griglia, insieme ordinato di blocchi, che a loro volta condividono una memoria di livello più alto (quindi con latenza per gli accessi più alta).. Figura 9 – Struttura dei blocchi di thread e delle griglie (14). Ogni thread dispone di una propria memoria privata, di dimensioni abbastanza limitate, accessibile solo dal thread stesso, e di una memoria condivisa a livello di blocco. Tale memoria condivisa, è simile ad una cache di primo livello, quindi garantisce tempi d’accesso molto bassi, e quindi comunicazioni tra thread efficienti. Un blocco può essere organizzato come una struttura di thread monodimensionale, bidimensionale, o tridimensionale. Questo approccio si adatta molto bene alle computazioni orientate alla grafica tridimensionale, e al calcolo scientifico in generale. Ogni thread, è identificato mediante un proprio ID, che è una tripla che ne definisce le “coordinate” all’interno del blocco d’appartenenza. I thread di uno stesso blocco sono allocati su un unico core, per minimizzare le comunicazioni tra core diversi. I blocchi sono a loro volta raggruppati in griglie, strutture bidimensionali che raggruppano in modo ordinato i blocchi di thread. Le. 35.

(36) griglie poi, sono strutture che comunicano tra loro mediante accessi alla memoria globale, quindi più onerosi, ma poco frequenti.. Figura 10 - Gerarchia di memoria della GPU (14). A runtime è inoltre possibile eseguire trasferimenti di dati dalla device memory (ovvero la memoria della GPU) verso la host memory (la memoria della CPU) e viceversa, mediante le API messe a disposizione da CUDA. Quindi, potenzialmente, un programma CUDA può consistere nell’alternanza di sequenze di calcolo eseguite su GPU e su CPU, o eventualmente in parallelo. Quando si vuole invocare una funzione kernel, si deve tenere conto della strutturazione di memoria. CUDA permette di astrarre dall’architettura fisica della GPU sottostante, ma per funzionare al meglio, è richiesto all’utente di specificare come ripartire i thread tra blocchi e griglie. Quindi, al momento dell’invocazione di un kernel, l’utente non dovrà solo indicare il nome della funzione e i suoi parametri, ma anche il numero di thread per blocco e il numero di blocchi per griglia. È poi il runtime a ripartire e scalare opportunamente il carico dei thread per bilanciare il funzionamento.. 36.

(37) Si consideri come esempio uno dei kernel realizzati in questo lavoro, che calcola i vincoli spaziali ai quali sono sottoposte le particelle direttamente su GPU: __global__ void APPLYCONSTRAINTS(float4 *pout, float4 *vout, const float4 *pin, const float4 *vin, const float4 *planes) {. …. }. La definizione di tale kernel ha il prefisso __global__, che indica che questo kernel, una volta compilato, è direttamente invocabile dall’esterno. Tra i suoi parametri non compaiono riferimenti al modo in cui dovrà essere ripartito il carico a runtime. Al momento della chiamata invece, è necessario indicare tali parametri: … int threadsPerBlock = 32; int blocksPerGrid = PARTICLES_NUM/threadsPerBlock + (PARTICLES_NUM%threadsPerBlock == 0 ? 0:1); APPLYCONSTRAINTS <<< blocksPerGrid, threadsPerBlock >>>(float4 *pout, float4 *vout, const float4 *pin, const float4 *vin, const float4 *planes); … Il passaggio dei parametri blocksPerGrid e threadsPerBlock al kernel indicano come partizionare il carico di lavoro sui cores a runtime, indipendentemente dal loro numero e dell’architettura sottostante della GPU. Altra caratteristica è che, essendo due unità di elaborazione distinte, CPU e GPU lavorano in modo essenzialmente indipendente, ma è possibile, da software, realizzare vari tipi di sincronizzazione. In modo nativo, è possibile sincronizzare i thread d’esecuzione durante i calcoli compiuti dalla GPU. Si può far in modo che l’algoritmo rimanga in attesa che tutti i thread siano eseguiti prima di passare alle istruzioni successive. Inoltre, è possibile eseguire la sincronizzazione tra GPU e CPU, ovvero, si può far in modo che la CPU rimanga in stato idle, e attenda la fine dell’esecuzione dei calcoli della GPU prima di proseguire con istruzioni successive. Questo tipo di sincronizzazione è talvolta necessario per garantire la coerenza dei dati generati dalla GPU quando devono essere processati dalla CPU. Durante l’attesa, la CPU può potenzialmente. 37.

(38) eseguire altro lavoro utile, anche non necessariamente dipendente dall’applicazione corrente. Sfruttando opportunamente questi due tipi di sincronizzazione, è possibile massimizzare l’utilizzo delle risorse, e ottenere un aumento di prestazioni facendole lavorare in parallelo quando possibile, e sequenzialmente quando necessario. Nello sviluppo di questo progetto, si sono utilizzate entrambe le forme di sincronizzazione, sia in modo implicito (quando si effettuano calcoli su input di grana grossa, prima di restituire alla CPU il risultato finale, è necessario attendere che tutti i dati di input siano stati correttamente elaborati), sia in modo esplicito (invocando l’attesa della GPU da parte della CPU, tipicamente mediante una chiamata della libreria GPUmat). 2.5.1.1 Esempi di utilizzo di CUDA La tecnologia CUDA trova ormai applicazione nella maggior parte della applicazioni scientifiche di un certo spessore, e praticamente in qualsiasi campo: dalla medicina alla meccanica, dalla matematica all’astrofisica. Alcuni famosi esempi di applicazioni di questo genere sono quelle della famiglia di BOINC (Berkeley Open Infrastructure for Network Computing), della quale, i più noti esponenti sono SETI@Home, PrimeGrid, ClimatePrediction, MilkyWay @Home, Enstein @Home e molti altri.. 2.5.2. CUDA in simulazioni Physics-oriented. Le GPU sono ottimizzate per il calcolo vettoriale, quindi, dato che le particelle sono organizzate come vettori o matrici, i calcoli su di esse si prestano bene ad essere effettuati sulla GPU. Inoltre, sfruttando il paradigma CUDA, basato su thread distinti, la parallelizzazione dei calcoli su singole particelle diviene particolarmente efficiente. Per i motivi già esposti, è palese che il paradigma GPGPU si presta ottimamente per la simulazione di fluidi, se i dati vengono opportunamente rappresentati, e gli algoritmi progettati per sfruttare il parallelismo. Per loro natura, le GPU sono progettate per eseguire calcoli vettoriali, quindi, per sfruttare questa caratteristica, le particelle, come già detto, sono organizzate in una matrice, che ha sostanzialmente due pregi dal punto di vista computazionale: •. Compatta al massimo l’occupazione di memoria per tali elementi (implementare le particelle come una lista di oggetti, avrebbe causato un notevole spreco di. 38.