“A scalable schur-complement fluids solver for heterogeneous compute platforms” by Liu, Mitchell, Aanjaneya and Sifakis
Conference:
Type(s):
Title:
- A scalable schur-complement fluids solver for heterogeneous compute platforms
Session/Category Title: Smash & Splash
Presenter(s)/Author(s):
Abstract:
We present a scalable parallel solver for the pressure Poisson equation in fluids simulation which can accommodate complex irregular domains in the order of a billion degrees of freedom, using a single server or workstation fitted with GPU or Many-Core accelerators. The design of our numerical technique is attuned to the subtleties of heterogeneous computing, and allows us to benefit from the high memory and compute bandwidth of GPU accelerators even for problems that are too large to fit entirely on GPU memory. This is achieved via algebraic formulations that adequately increase the density of the GPU-hosted computation as to hide the overhead of offloading from the CPU, in exchange for accelerated convergence. Our solver follows the principles of Domain Decomposition techniques, and is based on the Schur complement method for elliptic partial differential equations. A large uniform grid is partitioned in non-overlapping subdomains, and bandwidth-optimized (GPU or Many-Core) accelerator cards are used to efficiently and concurrently solve independent Poisson problems on each resulting subdomain. Our novel contributions are centered on the careful steps necessary to assemble an accurate global solver from these constituent blocks, while avoiding excessive communication or dense linear algebra. We ultimately produce a highly effective Conjugate Gradients preconditioner, and demonstrate scalable and accurate performance on high-resolution simulations of water and smoke flow.
References:
1. Adalsteinsson, D., and Sethian, J. 1999. The fast construction of extension velocities in level set methods. Journal of Computational Physics 148, 1, 2 — 22.
2. Adams, B., Pauly, M., Keiser, R., and Guibas, L. J. 2007. Adaptively sampled particle fluids. In ACM SIGGRAPH 2007 Papers, ACM, New York, NY, USA, SIGGRAPH ’07.
3. Ament, M., Knittel, G., Weiskopf, D., and Strasser, W. 2010. A parallel preconditioned conjugate gradient solver for the poisson problem on a multi-gpu platform. In Proceedings of the 18th Euromicro Conference on Parallel, Distributed and Network-based Processing, 583–592.
4. Ando, R., Thürey, N., and Wojtan, C. 2013. Highly adaptive liquid simulations on tetrahedral meshes. ACM Trans. Graph. 32, 4 (July), 103:1–103:10.
5. Ando, R., Thuerey, N., and Wojtan, C. 2015. A stream function solver for liquid simulations. ACM Trans. Graph. 34, 4, 53:1–53:9.
6. Ando, R., Thürey, N., and Wojtan, C. 2015. A dimension-reduced pressure solver for liquid simulations. EUROGRAPHICS 2015.
7. Bailey, D., Biddle, H., Avramoussis, N., and Warner, M. 2015. Distributing liquids using OpenVDB. In ACM SIGGRAPH 2015 Talks, SIGGRAPH ’15.
8. Bender, J., and Koschier, D. 2015. Divergence-free smoothed particle hydrodynamics. SCA ’15, 147–155.
9. Bro-nielsen, M., and Cotin, S. 1996. Real-time volumetric deformable models for surgery simulation using finite elements and condensation. In Computer Graphics Forum, 57–66.
10. Chen, Z., Kim, B., Ito, D., and Wang, H. 2015. Wetbrush: Gpu-based 3d painting simulation at the bristle level. ACM Trans. Graph. 34, 6, 200:1–200:11.
11. Chentanez, N., and Müller, M. 2011. Real-time Eulerian water simulation using a restricted tall cell grid. SIGGRAPH ’11, 82:1–82:10.
12. Chentanez, N., Feldman, B. E., Labelle, F., O’Brien, J. F., and Shewchuk, J. R. 2007. Liquid simulation on lattice-based tetrahedral meshes. SCA ’07, 219–228.
13. Cohen, J., Tariq, S., and Green, S. 2010. Interactive fluid-particle simulation using translating Eulerian grids. In ACM SIGGRAPH Symp. on Interactive 3D Graphics and Games, 15–22.
14. Da, F., Batty, C., Wojtan, C., and Grinspun, E. 2015. Double bubbles sans toil and trouble: Discrete circulation-preserving vortex sheets for soap films and foams. ACM Trans. Graph. 34, 4, 149:1–149:9.
15. de Goes, F., Wallez, C., Huang, J., Pavlov, D., and Desbrun, M. 2015. Power particles: An incompressible fluid solver based on power diagrams. ACM Trans. Graph. 34, 4, 50:1–50:11.
16. Dick, C., Georgii, J., and Westermann, R. 2011. A real-time multigrid finite hexahedra method for elasticity simulation using CUDA. Simulation Modelling Practice and Theory 19, 2, 801 — 816. Cross Ref
17. Dick, C., Rogowsky, M., and Westermann, R. 2016. Solving the fluid pressure poisson equation using multigrid – evaluation and improvements. IEEE Trans. Visualization & Computer Graphics (to appear). Cross Ref
18. Dobashi, Y., Matsuda, Y., Yamamoto, T., and Nishita, T. 2008. A fast simulation method using overlapping grids for interactions between smoke and rigid objects. Computer Graphics Forum 27, 2, 477–486. Cross Ref
19. Edwards, E., and Bridson, R. 2015. The discretely-discontinuous Galerkin coarse grid for domain decomposition. CoRR abs/1504.00907.
20. English, R. E., Qiu, L., Yu, Y., and Fedkiw, R. 2013. Chimera grids for water simulation. SCA ’13, 85–94.
21. Enright, D., Marschner, S., and Fedkiw, R. 2002. Animation and rendering of complex water surfaces. ACM Trans. Graph. 21, 3, 736–744.
22. Enright, D., Nguyen, D., Gibou, F., and Fedkiw, R. 2003. Using the particle level set method and a second order accurate pressure boundary condition for free surface flows. In Proc. 4th ASME-JSME Joint Fluids Eng. Conf.
23. Enright, D., Losasso, F., and Fedkiw, R. 2005. A fast and accurate semi-Lagrangian particle level set method. Comput. Struct. 83, 6–7, 479–490.
24. Ferstl, F., Westermann, R., and Dick, C. 2014. Large-scale liquid simulation on adaptive hexahedral grids. IEEE Trans. Visualization & Computer Graphics 20, 10 (Oct), 1405–1417. Cross Ref
25. Foster, N., and Fedkiw, R. 2001. Practical animation of liquids. In Proc. of ACM SIGGRAPH 2001, 23–30.
26. Foster, N., and Metaxas, D. 1996. Realistic animation of liquids. Graph. Models Image Process. 58, 5, 471–483.
27. Froemling, E., Goktekin, T., and Peachey, D. 2007. Simulating whitewater rapids in Ratatouille. In ACM SIGGRAPH 2007 Sketches, SIGGRAPH ’07.
28. Gao, M., Mitchell, N., and Sifakis, E. 2014. Steklov-poincareé skinning. SCA ’14, 139–148.
29. Geiger, W., Leo, M., Rasmussen, N., Losasso, F., and Fedkiw, R. 2006. So real it’ll make you wet. In ACM SIGGRAPH 2006 Sketches, SIGGRAPH ’06.
30. Golas, A., Narain, R., Sewall, J., Krajcevski, P., Dubey, P., and Lin, M. 2012. Large-scale fluid simulation using velocity-vorticity domain decomposition. ACM Trans. Graph. 31, 6, 148:1–148:9.
31. Hecht, F., Lee, Y. J., Shewchuk, J. R., and O’Brien, J. F. 2012. Updated sparse cholesky factors for corotational elastodynamics. ACM Trans. Graph. 31, 5, 123:1–123:13.
32. Horvath, C., and Geiger, W. 2009. Directable, high-resolution simulation of fire on the gpu. In ACM SIGGRAPH 2009 Papers, ACM, New York, NY, USA, SIGGRAPH ’09, 41:1–41:8.
33. Houston, B., Nielsen, M. B., Batty, C., Nilsson, O., and Museth, K. 2006. Hierarchical RLE level set: A compact and versatile deformable surface representation. ACM Trans. Graph. 25, 1, 151–175.
34. Ihmsen, M., Cornelis, J., Solenthaler, B., Horvath, C., and Teschner, M. 2014. Implicit incompressible SPH. IEEE Transactions on Visualization and Computer Graphics 20, 3, 426–435.
35. Irving, G., Guendelman, E., Losasso, F., and Fedkiw, R. 2006. Efficient simulation of large bodies of water by coupling two and three dimensional techniques. SIGGRAPH ’06, 805–811.
36. Jiang, C., Schroeder, C., Selle, A., Teran, J., and Stomakhin, A. 2015. The affine particle-in-cell method. ACM Trans. Graph. 34, 4, 51:1–51:10.
37. Jung, H.-R., Kim, S.-T., Noh, J., and Hong, J.-M. 2013. A heterogeneous CPU-GPU parallel approach to a multigrid poisson solver for incompressible fluid simulation. Computer Animation and Virtual Worlds 24, 3–4, 185–193. Cross Ref
38. Klingner, B., Feldman, B., Chentanez, N., and O’Brien, J. 2006. Fluid animation with dynamic meshes. SIGGRAPH ’06, 820–825.
39. Ladický, L., Jeong, S., Solenthaler, B., Pollefeys, M., and Gross, M. 2015. Data-driven fluid simulations using regression forests. ACM Trans. Graph. 34, 6, 199:1–199:9.
40. Lentine, M., Zheng, W., and Fedkiw, R. 2010. A novel algorithm for incompressible flow using only a coarse grid projection. ACM Trans. Graph. 29, 4, 114:1–114:9.
41. Liu, B., Mason, G., Hodgson, J., Tong, Y., and Desbrun, M. 2015. Model-reduced variational fluid simulation. ACM Trans. Graph. 34, 6, 244:1–244:12.
42. Long, B., and Reinhard, E. 2009. Real-time fluid simulation using discrete sine/cosine transforms. In Proceedings of the 2009 Symposium on Interactive 3D Graphics and Games, I3D ’09, 99–106.
43. Losasso, F., Gibou, F., and Fedkiw, R. 2004. Simulating water and smoke with an octree data structure. SIGGRAPH ’04, 457–462.
44. Losasso, F., Fedkiw, R., and Osher, S. 2005. Spatially adaptive techniques for level set methods and incompressible flow. Computers and Fluids 35, 2006.
45. Losasso, F., Talton, J., Kwatra, N., and Fedkiw, R. 2008. Two-way coupled SPH and particle level set fluid simulation. IEEE Transactions on Visualization and Computer Graphics 14, 4, 797–804.
46. Macklin, M., and Müller, M. 2013. Position based fluids. ACM Trans. Graph. 32, 4, 104:1–104:12.
47. Macklin, M., Müller, M., Chentanez, N., and Kim, T.-Y. 2014. Unified particle physics for real-time applications. ACM Trans. Graph. 33, 4, 153:1–153:12.
48. McAdams, A., Sifakis, E., and Teran, J. 2010. A parallel multigrid poisson solver for fluids simulation on large grids. SCA ’10, 65–74.
49. Molemaker, J., Cohen, J. M., Patel, S., and Noh, J. 2008. Low viscosity flow simulations for animation. In Proceedings of the 2008 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Eurographics Association, Aire-la-Ville, Switzerland, SCA ’08, 9–18.
50. Museth, K. 2013. VDB: High-resolution sparse volumes with dynamic topology. ACM Trans. Graph. 32, 3 (July), 27:1–27:22.
51. Quarteroni, A., and Valli, A. 1999. Domain decomposition methods for partial differential equations, vol. 10. Clarendon Press.
52. Rasmussen, N., Nguyen, D. Q., Geiger, W., and Fedkiw, R. 2003. Smoke simulation for large scale phenomena. ACM Trans. Graph. 22, 3, 703–707.
53. Raveendran, K., Wojtan, C., and Turk, G. 2011. Hybrid smoothed particle hydrodynamics. SCA ’11, 33–42.
54. Raveendran, K., Thuerey, N., Wojtan, C., and Turk, G. 2012. Controlling liquids using meshes. SCA ’12, 255–264.
55. Selle, A., Fedkiw, R., Kim, B., Liu, Y., and Rossignac, J. 2008. An unconditionally stable MacCormack method. J. Sci. Comput. 35, 2–3 (June), 350–371.
56. Setaluri, R., Aanjaneya, M., Bauer, S., and Sifakis, E. 2014. SPGrid: A sparse paged grid structure applied to adaptive smoke simulation. ACM Trans. Graph. 33, 6, 205:1–205:12.
57. Smith, B. F., Bjørstad, P. E., and Gropp, W. D. 1996. Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations. Cambridge University Press.
58. Solenthaler, B., and Gross, M. 2011. Two-scale particle simulation. SIGGRAPH ’11, 81:1–81:8.
59. Stam, J. 1999. Stable fluids. SIGGRAPH ’99, 121–128.
60. Stam, J. 2002. A simple fluid solver based on the FFT. J. Graph. Tools 6, 2, 43–52.
61. Tan, J., Yang, X., Zhao, X., and Yang, Z. 2008. Fluid animation with multi-layer grids. In SCA ’08 Posters.
62. Teng, Y., Meyer, M., DeRose, T., and Kim, T. 2015. Subspace condensation: Full space adaptivity for subspace deformations. ACM Trans. Graph. 34, 4, 76:1–76:9.
63. Thürey, N., Wojtan, C., Gross, M., and Turk, G. 2010. A multiscale approach to mesh-based surface tension flows. ACM Trans. Graph. 29, 4, 48:1–48:10.
64. Trottenberg, U., Oosterlee, C. W., and Schuller, A. 2001. Multigrid. Academic Press.
65. Van Opstal, B., Janin, L., Museth, K., and Aldén, M. 2014. Large scale simulation and surfacing of water and ice effects in Dragons 2. In ACM SIGGRAPH 2014 Talks, SIGGRAPH ’14.
66. Wojtan, C., Thürey, N., Gross, M., and Turk, G. 2010. Physics-inspired topology changes for thin fluid features. ACM Trans. Graph. 29, 4, 1–8.
67. Wu, X., Mukherjee, R., and Wang, H. 2015. A unified approach for subspace simulation of deformable bodies in multiple domains. ACM Trans. Graph. 34, 6, 241:1–241:9.
68. Wu, J., Dick, C., and Westermann, R. 2016. A system for high-resolution topology optimization. IEEE Transactions on Visualization and Computer Graphics 22, 3, 1195–1208.
69. Zhang, X., and Bridson, R. 2014. A PPPM fast summation method for fluids and beyond. ACM Trans. Graph. 33, 6, 206:1–206:11.
70. Zhu, Y., and Bridson, R. 2005. Animating sand as a fluid. SIGGRAPH ’05, 965–972.
71. Zhu, B., Yang, X., and Fan, Y. 2010. Creating and Preserving Vortical Details in SPH Fluid. Computer Graphics Forum.
72. Zhu, B., Lu, W., Cong, M., Kim, B., and Fedkiw, R. 2013. A new grid structure for domain extension. ACM Trans. Graph. 32, 4, 63:1–63:12.
73. Zhu, B., Quigley, E., Cong, M., Solomon, J., and Fedkiw, R. 2014. Codimensional surface tension flow on simplicial complexes. ACM Trans. Graph. 33, 4, 111:1–111:11.
