Nearest Neighbour Search Algorithms for Spatial Data Mapping in Numerical Simulations

Immaginate un mondo in cui gli ingegneri possano prevedere esattamente come il calore si muove attraverso un componente meccanico complesso, dal gas rovente all'interno di un motore fino al rivestimento metallico che lo contiene. Questo è il regno della fluidodinamica computazionale, un campo che utilizza computer potenti per simulare il comportamento di fluidi e calore. Per farlo accuratamente, gli scienziati devono spesso combinare due diversi tipi di modelli informatici: uno che mappa il flusso dettagliato e fine del gas caldo, e un altro che mappa la struttura più grossolana del metallo solido. La sfida consiste nel connettere queste due mappe. Il computer deve trovare il punto più vicino sulla mappa del gas per ogni singolo punto della mappa del metallo per trasferire i dati corretti di temperatura e pressione. Se il computer dovesse controllare ogni singolo punto contro ogni altro punto per trovare la corrispondenza più vicina, il processo diventerebbe incredibilmente lento, specialmente per simulazioni grandi e dettagliate. Questo collo di bottiglia può trasformare un calcolo che dovrebbe richiedere ore in uno che richiede giorni, limitando la complessità delle macchine che gli ingegneri possono progettare.

Un team di ricercatori dell'Università di Linköping, in Svezia, si è posto l'obiettivo di risolvere questo specifico problema del collegamento efficiente di queste mappe digitali. Si sono concentrati su un metodo chiamato ricerca del vicino più prossimo (nearest-neighbor search), che è semplicemente l'atto di trovare il punto più vicino in un grande insieme di dati. Nel loro lavoro, hanno testato diversi modi per velocizzare questa ricerca all'interno di un popolare software di ingegneria chiamato ABAQUS, ampiamente utilizzato per simulare come le strutture rispondono al calore e allo stress. I ricercatori hanno confrontato un metodo tradizionale e diretto con approcci più organizzati da loro sviluppati utilizzando strutture dati personalizzate. Il loro obiettivo era vedere se potevano organizzare i dati in modo da permettere al computer di saltare controlli non necessari e trovare la corrispondenza giusta molto più velocemente, senza perdere accuratezza.

I ricercatori hanno iniziato testando un metodo di base noto come forza bruta (brute force). In questo approccio, il computer agisce come una persona che controlla ogni singolo oggetto in una stanza per trovare quello più vicino a un punto specifico. Misura la distanza tra ogni punto dei dati del gas e ogni punto dei dati della struttura solida. Sebbene questo metodo garantisca di trovare la risposta corretta, è computazionalmente costoso e lento perché il numero di controlli cresce rapidamente man mano che i dati diventano più grandi. Per migliorare questo aspetto, il team ha sviluppato due nuove strategie. La prima, chiamata approccio Bin (a contenitori), divide i dati in una serie di fette o sezioni verticali lungo un asse. Invece di cercare l'intero insieme di dati, il computer deve solo guardare all'interno della specifica fetta in cui si trova il punto. La seconda strategia, l'approccio L1 Octree, va oltre, dividendo lo spazio in otto blocchi distinti, o ottanti, e organizzando i dati all'interno di questi blocchi. Ciò consente al computer di eliminare rapidamente vaste aree del dataset che sono troppo lontane per essere la corrispondenza più vicina.

Per testare questi metodi, i ricercatori hanno eseguito simulazioni su due diverse forme: un cilindro cavo con fori e una complessa valvola di scarico utilizzata nelle applicazioni automobilistiche. Hanno mappato dati termici dettagliati da una mesh fine su una mesh più grossolana, imitando il processo reale di trasferimento dei dati da una simulazione di fluido a una strutturale. I risultati hanno mostrato che entrambi i nuovi metodi superavano significativamente l'approccio della forza bruta. Su un singolo core del computer, il metodo L1 Octree ha ridotto il tempo necessario per completare la ricerca di quasi l'88 percento rispetto al metodo tradizionale, mentre l'approccio Bin lo ha ridotto di circa il 61 percento. Quando i ricercatori hanno testato questi metodi su un dataset più grande con oltre due milioni di punti, i miglioramenti sono rimasti costanti. I nuovi metodi non solo hanno risparmiato tempo, ma hanno gestito i dati in modo più efficiente all'aumentare del numero di core del computer utilizzati per il calcolo, a condizione che il dataset fosse abbastanza grande da giustificare l'overhead della gestione di più processori.

Lo studio ha anche rivelato alcune sfumature importanti su come si comportano questi algoritmi. I ricercatori hanno scoperto che ordinare i dati prima della ricerca rendeva in realtà il processo più lento nel loro specifico ambiente di programmazione, contrariamente a quanto ci si potrebbe aspettare. Hanno scoperto che il tempo impiegato per organizzare i dati era così significativo da annullare i benefici di una ricerca più veloce. Di conseguenza, i loro metodi più efficaci evitavano completamente l'ordinamento preventivo dei dati. Inoltre, hanno determinato che questi metodi avanzati sono più vantaggiosi per simulazioni con più di 100.000 punti. Per simulazioni più piccole, il tempo risparmiato dai nuovi metodi non è sufficiente a compensare l'ulteriore sforzo richiesto per la loro configurazione, e il tradizionale metodo della forza bruta rimane un'opzione valida. Tuttavia, per le simulazioni grandi e complesse che l'ingegneria moderna richiede, i nuovi approcci offrono una via chiara verso risultati più rapidi.

Implementando queste strutture dati personalizzate nel linguaggio di programmazione FORTRAN, che è lo standard per il software di ingegneria ad alte prestazioni, i ricercatori hanno dimostrato che è possibile ottenere una mappatura dei dati ad alta velocità senza fare affidamento su librerie moderne e pre-costruite, che sono spesso non disponibili in questi ambienti specializzati. Lo studio conclude che, per le simulazioni termiche su larga scala, come quelle che coinvolgono il trasferimento di calore congiunto dove lo scambio di calore tra fluido e solido è critico, l'uso di questi algoritmi di ricerca ottimizzati può ridurre drasticamente il tempo che gli ingegneri trascorrono in attesa dei risultati. Questa efficienza permette simulazioni più dettagliate e cicli di progettazione più rapidi, aiutando infine a creare macchine migliori ed efficienti. Il lavoro è una dimostrazione pratica del fatto che, anche in campi consolidati, ripensare il modo in cui i dati sono organizzati può portare a sostanziali guadagni di prestazioni.