“GPU optimization of material point methods” – ACM SIGGRAPH HISTORY ARCHIVES

“GPU optimization of material point methods”

  • 2018 SA Technical Papers_Gao_GPU optimization of material point methods

Conference:


Type(s):


Title:

    GPU optimization of material point methods

Session/Category Title:   Optimizing structures & materials

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    The Material Point Method (MPM) has been shown to facilitate effective simulations of physically complex and topologically challenging materials, with a wealth of emerging applications in computational engineering and visual computing. Borne out of the extreme importance of regularity, MPM is given attractive parallelization opportunities on high-performance modern multiprocessors. Parallelization of MPM that fully leverages computing resources presents challenges that require exploring an extensive design-space for favorable data structures and algorithms. Unlike the conceptually simple CPU parallelization, where the coarse partition of tasks can be easily applied, it takes greater effort to reach the GPU hardware saturation due to its many-core SIMT architecture. In this paper we introduce methods for addressing the computational challenges of MPM and extending the capabilities of general simulation systems based on MPM, particularly concentrating on GPU optimization. In addition to our open-source high-performance framework, we also conduct performance analyses and benchmark experiments to compare against alternative design choices which may superficially appear to be reasonable, but can suffer from suboptimal performance in practice. Our explicit and fully implicit GPU MPM solvers are further equipped with a Moving Least Squares MPM heat solver and a novel sand constitutive model to enable fast simulations of a wide range of materials. We demonstrate that more than an order of magnitude performance improvement can be achieved with our GPU solvers. Practical high-resolution examples with up to ten million particles run in less than one minute per frame.

References:


    1. M. Aanjaneya, M. Gao, H. Liu, C. Batty, and E. Sifakis. 2017. Power diagrams and sparse paged grids for high resolution adaptive liquids. ACM Trans Graph 36, 4 (2017), 140. Google ScholarDigital Library
    2. J. Brackbill. 1988. The ringing instability in Particle-In-Cell calculations of low-speed flow. J Comp Phys 75, 2 (1988), 469–492. Google ScholarDigital Library
    3. R. Bridson. 2007. Fast poisson disk sampling in arbitrary dimensions. In ACM SIGGRAPH 2007 Sketches. Article 22. Google ScholarDigital Library
    4. R. Bridson. 2008. Fluid simulation for computer graphics. Taylor & Francis. Google ScholarDigital Library
    5. W-F. Chiang, M. DeLisi, T. Hummel, T. Prete, K. Tew, M. Hall, P. Wallstedt, and J. Guilkey. 2009. GPU acceleration of the Generalized Interpolation Material Point method. Symp App Accel High Perf Comp (2009).Google Scholar
    6. J. Chu, N. B. Zafar, and X. Yang. 2017. A Schur complement preconditioner for scalable parallel fluid simulation. ACM Trans Graph 36, 5 (2017), 163:1–163:11. Google ScholarDigital Library
    7. G. Daviet and F. Bertails-Descoubes. 2016. A semi-implicit material point method for the continuum simulation of granular materials. ACM Trans Graph 35, 4 (2016), 102:1–102:13. Google ScholarDigital Library
    8. Y. Dong and J. Grabe. 2018. Large scale parallelisation of the material point method with multiple GPUs. Comp and Geo 101 (2018), 149–158.Google ScholarCross Ref
    9. Y. Dong, D. Wang, and M. F. Randolph. 2015. A GPU parallel computing strategy for the material point method. Comp and Geo 66 (2015), 31–38.Google ScholarCross Ref
    10. Y. Fang*, Y. Hu*, S. Hu, and C. Jiang. 2018. A Temporally Adaptive Material Point Method with Regional Time Stepping. In Proceedings of the ACM SIGGRAPH/EurographicsGoogle Scholar
    11. Symposium on Computer Animation (SCA ’18). Eurographics Association. (*Joint First Authors).Google Scholar
    12. M. Gao. 2018. Sparse Paged Grid and its Applications to Adaptivity and Material Point Method in Physics Based Simulations. Ph.D. Dissertation. University of Wisconsin, Madison.Google Scholar
    13. M. Gao, A.P. Tampubolon, X. Han, Q Guo, G. Kot, E. Sifakis, and C. Jiang. 2018a. Animating fluid sediment mixture in particle-laden flows. ACM Trans Graph 37, 4 (2018). Google ScholarDigital Library
    14. M. Gao, A. P. Tampubolon, C. Jiang, and E. Sifakis. 2017. An adaptive Generalized Interpolation Material Point method for simulating elastoplastic materials. ACM Trans Graph 36, 6 (2017). Google ScholarDigital Library
    15. M. Gao, X Wang, K Wu, A. Pradhana, E. Sifakis, C. Yuksel, and C. Jiang. 2018b. Supplemental Document: GPU Optimization of Material Point Methods. (2018).Google Scholar
    16. Theodore Gast, Chuyuan Fu, Chenfanfu Jiang, and Joseph Teran. 2016. Implicit-shifted Symmetric QR Singular Value Decomposition of 3×3 Matrices. Technical Report. University of California Los Angeles.Google Scholar
    17. N. K. Govindaraju, I. Kabul, M. C. Lin, and D. Manocha. 2007. Fast continuous collision detection among deformable models using graphics processors. Comp Graph 31, 1 (2007), 5–14. Google ScholarDigital Library
    18. N. K. Govindaraju, D. Knott, N. Jain, I. Kabul, R. Tamstorf, R. Gayle, M. C. Lin, and D. Manocha. 2005. Interactive Collision Detection Between Deformable Models Using Chromatic Decomposition. ACM Trans Graph 24, 3 (2005), 991–999. Google ScholarDigital Library
    19. Q. Guo, X. Han, C. Fu, T. Gast, R. Tamstorf, and J. Teran. 2018. A Material Point Method for thin shells with frictional contact. ACM Trans Graph 37, 4 (2018). Google ScholarDigital Library
    20. T. Harada, S. Koshizuka, and Y. Kawaguchi. 2007. Smoothed particle hydrodynamics on GPUs. In Comp Graph Int, Vol. 40. SBC Petropolis, 63–70.Google Scholar
    21. R. K. Hoetzlein. 2016. GVDB: Raytracing sparse voxel database structures on the GPU. In Proc of High Perf Graph. Eurographics Association, 109–117. Google ScholarDigital Library
    22. C. Horvath and W. Geiger. 2009. Directable, high-resolution simulation of fire on the GPU. ACM Trans Graph 28, 3 (2009), 41:1–41:8. Google ScholarDigital Library
    23. Y. Hu, Y. Fang, Z. Ge, Z. Qu, Y. Zhu, A. Pradhana, and C. Jiang. 2018. A moving least squares material point method with displacement discontinuity and two-way rigid body coupling. ACM Trans Graph 37, 4 (2018). Google ScholarDigital Library
    24. P. Huang, X. Zhang, S. Ma, and H. K. Wang. 2008. Shared memory OpenMP parallelization of explicit MPM and its application to hypervelocity impact. Comp Mod in Eng and Sci 38 (2008), 119–148.Google Scholar
    25. C. Jiang, T. Gast, and J. Teran. 2017a. Anisotropic elastoplasticity for cloth, knit and hair frictional contact. ACM Trans Graph 36, 4 (2017). Google ScholarDigital Library
    26. C. Jiang, C. Schroeder, A. Selle, J. Teran, and A. Stomakhin. 2015. The affine particle-in-cell method. ACM Trans Graph 34, 4 (2015), 51:1–51:10. Google ScholarDigital Library
    27. C. Jiang, C. Schroeder, and J. Teran. 2017b. An angular momentum conserving affine-particle-in-cell method. J Comp Phys 338 (2017), 137–164. Google ScholarDigital Library
    28. G. Klár. 2014. Speculative Atomics: A Case-Study of the GPU Optimization of the Material Point Method for Graphics. In GPU Technology Conference.Google Scholar
    29. G. Klár. 2017. Blasting Sand with CUDA: MPM Sand Simulation for VFX. In GPU Technology Conference.Google Scholar
    30. G. Klár, J. Budsberg, M. Titus, S. Jones, and K. Museth. 2017. Production ready MPM simulations. In ACM SIGGRAPH 2017 Talks. Article 42, 42:1–42:2 pages. Google ScholarDigital Library
    31. G. Klár, T. Gast, A. Pradhana, C. Fu, C. Schroeder, C. Jiang, and J. Teran. 2016. Drucker-prager elastoplasticity for sand animation. ACM Trans Graph 35, 4 (2016), 103:1–103:12. Google ScholarDigital Library
    32. H. Liu, N. Mitchell, M. Aanjaneya, and E. Sifakis. 2016. A scalable schur-complement fluids solver for heterogeneous compute platforms. ACM Trans Graph 35, 6 (2016). Google ScholarDigital Library
    33. Justin Luitjens. 2014. Faster parallel reductions on Kepler. Nvidia (2014).Google Scholar
    34. A. McAdams, A. Selle, R. Tamstorf, J. Teran, and E. Sifakis. 2011. Computing the singular value decomposition of 3× 3 matrices with minimal branching and elementary floating point operations. University of Wisconsin Madison (2011).Google Scholar
    35. K. Museth. 2013. VDB: High-resolution sparse volumes with dynamic topology. ACM Trans Graph 32, 3 (2013), 27. Google ScholarDigital Library
    36. S. G. Parker. 2006. A component-based architecture for parallel multi-physics PDE simulation. Fut Gen Comp Sys 22, 1 (2006), 204 — 216. Google ScholarDigital Library
    37. D. Ram, T. Gast, C. Jiang, C. Schroeder, A. Stomakhin, J. Teran, and P. Kavehpour. 2015. A Material Point Method for viscoelastic fluids, foams and sponges. In In Proc Symp Comp Anim. 157–163. Google ScholarDigital Library
    38. K. P Ruggirello and S. C. Schumacher. 2014. A comparison of parallelization strategies for the material point method. In 11th World Cong on Comp Mech. 20–25.Google Scholar
    39. R. Setaluri, M. Aanjaneya, S. Bauer, and E. Sifakis. 2014. SPGrid: A Sparse Paged Grid structure applied to adaptive smoke simulation. ACM Trans Graph 33, 6, Article 205 (2014), 205:1–205:12 pages. Google ScholarDigital Library
    40. G. Stantchev, D. Dorland, and N. Gumerov. 2008. Fast parallel Particle-To-Grid interpolation for plasma PIC simulations on the GPU. J Par Dis Comp 68, 10 (2008), 1339 — 1349. Google ScholarDigital Library
    41. A. Stomakhin, R. Howes, C. Schroeder, and J. Teran. 2012. Energetically consistent invertible elasticity. In In Proc Symp Comp Anim. 25–32. Google ScholarDigital Library
    42. A. Stomakhin, C. Schroeder, L. Chai, J. Teran, and A. Selle. 2013. A material point method for snow simulation. ACM Trans Graph 32, 4 (2013), 102:1–102:10. Google ScholarDigital Library
    43. A. Stomakhin, C. Schroeder, C. Jiang, L. Chai, J. Teran, and A. Selle. 2014. Augmented MPM for phase-change and varied materials. ACM Trans Graph 33, 4 (2014), 138:1–138:11. Google ScholarDigital Library
    44. D. Sulsky, S. Zhou, and H. Schreyer. 1995. Application of a particle-in-cell method to solid mechanics. Comp Phys Comm 87, 1 (1995), 236–252.Google ScholarCross Ref
    45. A. P. Tampubolon, T. Gast, G. Klár, C. Fu, J. Teran, C. Jiang, and K. Museth. 2017. Multi-species simulation of porous sand and water mixtures. ACM Trans Graph 36, 4 (2017). Google ScholarDigital Library
    46. M. Tang, Z. Liu, R. Tong, and D. Manocha. 2018. PSCC: Parallel Self-Collision Culling with spatial hashing on GPUs. Proc ACM on Comp Graph Int Techn 1, 1 (2018), 18:1–18. Google ScholarDigital Library
    47. M. Tang, R. Tong, R. Narain, C. Meng, and D. Manocha. 2013. A GPU-based streaming algorithm for high-resolution cloth simulation. Comp Graph Forum 32, 7 (2013), 21–30.Google ScholarCross Ref
    48. M. Tang, H. Wang, L. Tang, R. Tong, and D. Manocha. 2016. CAMA: Contact-Aware Matrix Assembly with unified collision handling for GPU-based cloth simulation. Comp Graph Forum 35, 2 (2016), 511–521.Google ScholarCross Ref
    49. H. Wang. 2018. Rule-free sewing pattern adjustment with precision. ACM Trans Graph 37, 4 (2018). Google ScholarDigital Library
    50. X. Wang, M. Tang, D. Manocha, and R. Tong. 2018. Efficient BVH-based collision detection scheme with ordering and restructuring. In Comp Graph Forum, Vol. 37. Wiley Online Library, 227–237.Google Scholar
    51. R. Weller, N. Debowski, and G. Zachmann. 2017. kDet: Parallel constant time collision detection for polygonal objects. In Comp Graph Forum, Vol. 36. 131–141. Google ScholarDigital Library
    52. J. Wretborn, R. Armiento, and K. Museth. 2017. Animation of crack propagation by means of an extended multi-body solver for the material point method. Comp and Graph (2017). Google ScholarDigital Library
    53. K. Wu, N. Truong, Yuksel C., and Hoetzlein R. 2018. Fast fluid simulations with sparse volumes on the GPU. Comp Graph Forum (2018).Google Scholar
    54. Y. Yue, B. Smith, C. Batty, C. Zheng, and E. Grinspun. 2015. Continuum foam: a material point method for shear-dependent flows. ACM Trans Graph 34, 5 (2015), 160:1–160:20. Google ScholarDigital Library
    55. Y. Zhang, B. Solenthaler, and R. Pajarola. 2008. Adaptive sampling and rendering of fluids on the GPU. In Proc of the Fifth Eurographics / IEEE VGTC Conf on Point-Based Graph. 137–146. Google ScholarDigital Library
    56. Y. Zhang, X. Zhang, and Y. Liu. 2010. An alternated grid updating parallel algorithm for material point method using OpenMP. Comp Modeling in Eng and Sci 69, 2 (2010), 143–165.Google Scholar
    57. Y. Zhu and R. Bridson. 2005. Animating sand as a fluid. ACM Trans Graph 24, 3 (2005), 965–972. Google ScholarDigital Library

ACM Digital Library Publication:


Overview Page:


Submit a story:

If you would like to submit a story about this presentation, please contact us: historyarchives@siggraph.org