Improving Parallel SPH for Snow Simulations: Neighborhood Search and Kernel Derivatives

Abstract

Bruk av GPUar for HPC er allereie veletablert. SPH (“smoothed-particle hydrodynamics”) er ein Lagrange teknikk for numerisk simulasjon av væsker som nylig har demonstrert gode resultat for simulasjon av snø på grunn av dens evne til å representere komplekse deformasjonar. Med ein tilstrekkelig modell av elastisitet kan SPH fange aspekter ved utløysing av snøskred. Likevel gjenstår vesentlige utfordringer for å implementere SPH effektivt på GPU, fordi det krever løysing av eit søkeproblem: FRNN (“fixed radius near neighbors”). Implementasjonar på GPU er vanlegvis begrensa til eit endeleg simulasjonsområde for å muliggjere fullstendig sortering av partikkelane basert på posisjon. Dette medfører spesialtilfeller som må handterast i simulasjonskoden. Andre teknikkar har vist seg å vere vanskeleg å videreføre til GPU.

Oppstartskostnaden nabo-beregninga medfører kvar iterasjon gjer numerisk stabilitet viktig for å presse steglengda. Noværande formulasjoner av SPH gir en Laplace-operator med en singularitet. Viskositet må derfor håndterast som eit spesialtilfelle ved hjelp av ufysiske approksimasjoner for å oppnå stabilitet. I dette arbeidet forsøker vi å redusere behovet for å håndtere spesialtilfeller. Ein ny teknikk for å derivere SPH-konvolusjonskjærner blir introdusert. Denne bevarer polynomgraden av splinene den er sammensatt av, og gir gode approksimasjoner sjølv for Laplace-operatorar. Ei ny tilnærming til romlig hashing blir presentert, som påfører ekvivalensklasser i simulasjonsområde og hash-tabell, og fjerner hash-kollisjonar internt i eit nabolag. Dette løyser ei fundamental utfordring i å videreføre romlig hashing for løysing av FRNN til GPU.

Vår formulering fjerner singulariteten fra Laplace-operatoren, og muliggjer implementasjon av viskositet med numerisk stabilitet på nivå med den kunstige tilnærminga mange må ty til. Vi viser at får tilnærming til romlig hashing forbedrer ytelsen i ein enkel simulasjon med to størrelsesordener, målt 183.9× auka ytelse. Vår analyse indikerer at bedre ytelse kan oppnåast.

Implementasjonar og benchmark er gitt i programmeringsspråket Julia, som lover brukervennlighet uten å kompromisse på ytelse. Nokre av våre misnøyer med C/C++ er beskrevet som begrunnelse for å utforske nye språk. Våre nye erfaringer med Julia for GPU-beregninger antyder at det bør vurderes for fremtidige prosjekter, men at det ikkje kan fullstendig erstatte C/C++. Idéar for framtidig arbeid er også inkludert.

The use of GPUs for HPC is already well-established and successful. Smoothed-particle hydrodynamics (SPH) is a Lagrangian technique for the numerical simulation of fluids which has seen a lot of recent success in several numerical simulations, including the NTNU HPC Lab Snow Simulator. With the right elasticity model, SPH can capture complex deformations, including aspects of avalanche formation. However, practical challenges remain regarding efficient GPU implementation, which requires solving the Fixed-Radius Near-Neighbor (FRNN) search problem. Simulations are typically restricted to a finite simulation domain to make a complete sort based on position work. This imposes handling of special cases in the simulation code. Other approaches have proven difficult to adapt to GPU architectures.

The cost of computing neighbors every iteration pushes for longer steps, which makes stability more important. Current formulations of SPH produce Laplacians with singularities forcing, for instance, viscosity to be handled as a special case using non-physical alternatives to achieve stability. In this work, we aim to reduce the need for SPH to handle these special cases. Our novel approach to differentiating SPH kernels preserves the polynomial order of splines that comprise it, retaining good approximation quality even for Laplacians. Our novel spatial hashing scheme, which imposes corresponding equivalence classes in the simulation domain and hash table, removes hash conflicts in particle neighborhoods. This solves a fundamental challenge in adapting spatial hashing schemes for solving FRNN on GPUs.

Our formulation removes the singularity and enables implementing the viscosity with numerical stability at least on par with the common artificial approach. We also show that our neighborhood search algorithm based on locally perfect spatial hashing improves performance over the naive algorithm by two orders of magnitude, with a measured 183.9× average speedup. Our analysis indicates that even better performance may be achieved.

Our implementations and benchmarks were done in the Julia programming language, a language that promises usability without compromising performance. Some of our grievances with C/C++ are outlined as a rationale for investigating new languages. Our new experience using Julia for GPU programming suggests that it should be considered for future research projects but cannot replace C/C++. Additional ideas for future work are also included.