Nearest Neighbour Search Algorithms for Spatial Data Mapping in Numerical Simulations

Stel je een wereld voor waarin ingenieurs precies kunnen voorspellen hoe warmte zich door een complex machineonderdeel beweegt, van het verzengende gas binnenin een motor tot de metalen behuizing die het vasthoudt. Dit is het domein van computational fluid dynamics (computational vloeistofdynamica), een vakgebied dat krachtige computers gebruikt om het gedrag van vloeistoffen en warmte te simuleren. Om dit nauwkeurig te doen, moeten wetenschappers vaak twee verschillende soorten computermodellen combineren: één die de fijne, gedetailleerde stroming van heet gas in kaart brengt, en een andere die de grovere structuur van het vaste metaal in kaart brengt. De uitdaging ligt in het verbinden van deze twee kaarten. De computer moet voor elk punt op de metalen kaart het dichtstbijzijnde punt op de gaskaart vinden om de juiste temperatuur- en drukgegevens over te dragen. Als de computer elk punt tegen elk ander punt moet controleren om de dichtstbijzijnde match te vinden, wordt het proces ongelooflijk traag, vooral voor grote en gedetailleerde simulaties. Deze flessenhals kan een berekening die uren zou moeten duren, veranderen in een proces dat dagen in beslag neemt, wat de complexiteit van de machines die ingenieurs kunnen ontwerpen, beperkt.

Een team onderzoekers aan de Linköping Universiteit in Zweden zette zich af om dit specifieke probleem van het efficiënt verbinden van deze digitale kaarten op te lossen. Ze richtten zich op een methode genaamd de 'nearest-neighbor search' (naburige zoekmethode), wat simpelweg het act van het vinden van het dichtstbijzijnde punt in een grote dataset is. In hun werk testten ze verschillende manieren om deze zoekopdracht te versnellen binnen een populaire engineeringsoftware genaamd ABAQUS, die breed wordt gebruikt om te simuleren hoe structuren reageren op hitte en spanning. De onderzoekers vergeleken een traditionele, eenvoudige methode met nieuwere, meer georganiseerde benaderingen die zij hadden ontwikkeld met behulp van aangepaste datastructuren. Hun doel was om te zien of ze de data op een manier konden organiseren waardoor de computer onnodige controles kon overslaan en de juiste match veel sneller kon vinden, zonder aan nauwkeurigheid in te boeten.

De onderzoekers begonnen met het testen van een basismethode die bekend staat als 'brute force'. Bij deze aanpak gedraagt de computer zich als een persoon die elk item in een kamer controleert om te vinden welk item het dichtst bij een specifieke plek ligt. Het meet de afstand tussen elk punt in de gasdata en elk punt in de vaste structuurdata. Hoewel deze methode gegarandeerd het juiste antwoord vindt, is het computationeel duur en traag omdat het aantal controles snel toeneemt naarmate de data groter wordt. Om dit te verbeteren, ontwikkelde het team twee nieuwe strategieën. De eerste, de 'Bin approach' genoemd, verdeelt de data in een reeks verticale segmenten of secties langs één as. In plaats van de volledige dataset te doorzoeken, hoeft de computer alleen binnen het specifieke segment te kijken waar het punt zich bevindt. De tweede strategie, de 'L1 Octree approach', gaat nog een stap verder door de ruimte te verdelen in acht afzonderlijke blokken, of octanten, en de data binnen deze blokken te organiseren. Dit stelt de computer in staat om snel grote gebieden van de dataset te elimineren die te ver weg zijn om de dichtstbijzijnde match te zijn.

Om deze methoden te testen, voerden de onderzoekers simulaties uit op twee verschillende vormen: een holle cilinder met gaten en een complexe uitlaatklep die wordt gebruikt in automotive toepassingen. Ze brachten gedetailleerde hitedata van een fijn mesh in kaart op een grover mesh, wat het werkelijke proces nabootst van het overdragen van data van een vloeistofsimulatie naar een structurele simulatie. De resultaten toonden aan dat beide nieuwe methoden de brute force-aanpak aanzienlijk overtroffen. Op een enkele computerkern verminderde de L1 Octree-methode de tijd die nodig was om de zoekopdracht te voltooien met bijna 88 procent vergeleken met de traditionele methode, terwijl de Bin-aanpak deze met ongeveer 61 procent verminderde. Wanneer de onderzoekers deze methoden testten op een grotere dataset met meer dan twee miljoen punten, bleven de verbeteringen consistent. De nieuwe methoden bespaarden niet alleen tijd, maar verwerkten de data ook efficiënter naarmig de hoeveelheid computerkernen die voor de berekening werd gebruikt toenam, mits de dataset groot genoeg was om de overhead van het beheren van meerdere processors te rechtvaardigen.

De studie onthulde ook enkele belangrijke nuances over hoe deze algoritmen zich gedragen. De onderzoekers ontdekten dat het sorteren van de data vóór het zoeken het proces in hun specifieke programmeeromgeving juist trager maakte, in tegenstelling tot wat men zou verwachten. Ze ontdekten dat de tijd die besteed werd aan het organiseren van de data zo aanzienlijk was dat het de voordelen van een snellere zoekopdracht tenietdeed. Bijgevolg vermeden hun meest succesvolle methoden het vooraf sorteren van de data volledig. Bovendien bepaalden zij dat deze geavanceerde methoden het meest voordelig zijn voor simulaties met meer dan 100.000 punten. Voor kleinere simulaties is de tijd die wordt bespaard door de nieuwe methoden niet voldoende om de extra inspanning die nodig is voor de opzet te compenseren, en blijft de traditionele brute force-methode een levensvatbare optie. Echter, voor de grote, complexe simulaties die de moderne techniek vereist, bieden de nieuwe benaderingen een duidelijke weg naar snellere resultaten.

Door deze aangepaste datastructuren te implementeren binnen de FORTRAN-programmeertaal, die standaard is voor high-performance engineeringsoftware, hebben de onderzoekers aangetoond dat het mogelijk is om snelle datamapping te bereiken zonder afhankelijk te zijn van moderne, vooraf gebouwde bibliotheken die vaak niet beschikbaar zijn in deze gespecialiseerde omgevingen. De studie concludeert dat voor grootschalige thermische simulaties, zoals die waarbij 'conjugate heat transfer' (gekoppelde warmteoverdracht) waarbij de uitwisseling van warmte tussen vloeistof en vaste stof cruciaal is, het gebruik van deze geoptimaliseerde zoekalgoritmen de tijd die ingenieurs moeten wachten op resultaten drastisch kan verkorten. Deze efficiëntie maakt meer gedetailleerde simulaties en snellere ontwerpcycli mogelijk, wat uiteindelijk helpt bij het creëren van betere, efficiëntere machines. Het werk is een praktische demonstratie dat zelfs in gevestigde vakgebieden, het heroverwegen van hoe data wordt georganiseerd, kan leiden tot substantiële winsten in prestaties.