“Automatic quantization for physics-based simulation” by Liu, Shi, Zhang, Yang, Ma, et al. …

  • ©Jiafeng Liu, Haoyang Shi, Siyuan Zhang, Yin Yang, Chongyang Ma, and Weiwei Xu

Conference:


Type:


Title:

    Automatic quantization for physics-based simulation

Presenter(s)/Author(s):



Abstract:


    Quantization has proven effective in high-resolution and large-scale simulations, which benefit from bit-level memory saving. However, identifying a quantization scheme that meets the requirement of both precision and memory efficiency requires trial and error. In this paper, we propose a novel framework to allow users to obtain a quantization scheme by simply specifying either an error bound or a memory compression rate. Based on the error propagation theory, our method takes advantage of auto-diff to estimate the contributions of each quantization operation to the total error. We formulate the task as a constrained optimization problem, which can be efficiently solved with analytical formulas derived for the linearized objective function. Our workflow extends the Taichi compiler and introduces dithering to improve the precision of quantized simulations. We demonstrate the generality and efficiency of our method via several challenging examples of physics-based simulation, which achieves up to 2.5× memory compression without noticeable degradation of visual quality in the results. Our code and data are available at https://github.com/Hanke98/AutoQantizer.

References:


    1. Mridul Aanjaneya, Ming Gao, Haixiang Liu, Christopher Batty, and Eftychios Sifakis. 2017. Power diagrams and sparse paged grids for high resolution adaptive liquids. ACM Trans. Graph. 36, 4, Article 140 (2017), 12 pages.Google ScholarDigital Library
    2. Sai Praveen Bangaru, Jesse Michel, Kevin Mu, Gilbert Bernstein, Tzu-Mao Li, and Jonathan Ragan-Kelley. 2021. Systematically differentiating parametric discontinuities. ACM Trans. Graph. 40, 4, Article 107 (2021), 18 pages.Google ScholarDigital Library
    3. Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. 2016. Interaction networks for learning about objects, relations and physics. In Advances in Neural Information Processing Systems. 4509–4517.Google ScholarDigital Library
    4. Sofien Bouaziz, Sebastian Martin, Tiantian Liu, Ladislav Kavan, and Mark Pauly. 2014. Projective dynamics: Fusing constraint projections for fast simulation. ACM Trans. Graph. 33, 4, Article 154 (2014), 11 pages.Google ScholarDigital Library
    5. Thierry Braconnier and Philippe Langlois. 2002. From rounding error estimation to automatic correction with automatic differentiation. In Automatic Differentiation of Algorithms: From Simulation to Optimization. 351–357.Google Scholar
    6. Francky Catthoor, Hugo De Man, and Joos Vandewalle. 1988. Simulated-annealing-based optimization of coefficient and data word-lengths in digital filters. International Journal of Circuit Theory and Applications 16, 4 (1988), 371–390.Google ScholarCross Ref
    7. E Richard Cohen. 1998. An introduction to error analysis: The study of uncertainties in physical measurements.Google Scholar
    8. George A Constantinides. 2003. Perturbation analysis for word-length optimization. In 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, 2003. FCCM 2003. IEEE, 81–90.Google ScholarCross Ref
    9. George A Constantinides. 2006. Word-length optimization for differentiable nonlinear systems. ACM Transactions on Design Automation of Electronic Systems (TODAES) 11, 1 (2006), 26–43.Google ScholarDigital Library
    10. George A Constantinides, Peter YK Cheung, and Wayne Luk. 2001. The multiple wordlength paradigm. In The 9th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM’01). IEEE, 51–60.Google ScholarDigital Library
    11. Filipe de Avila Belbute-Peres, Kevin Smith, Kelsey Allen, Josh Tenenbaum, and J Zico Kolter. 2018. End-to-end differentiable physics for learning and control. In Advances in Neural Information Processing Systems. 7178–7189.Google Scholar
    12. Fernando De Goes, Corentin Wallez, Jin Huang, Dmitry Pavlov, and Mathieu Desbrun. 2015. Power particles: an incompressible fluid solver based on power diagrams. ACM Trans. Graph. 34, 4, Article 50 (2015), 11 pages.Google Scholar
    13. Jonas Degrave, Michiel Hermans, Joni Dambre, et al. 2019. A differentiable physics engine for deep learning in robotics. Frontiers in Neurorobotics 13 (2019), 6.Google ScholarCross Ref
    14. Tao Du, Kui Wu, Pingchuan Ma, Sebastien Wah, Andrew Spielberg, Daniela Rus, and Wojciech Matusik. 2021. Diffpd: Differentiable projective dynamics. ACM Trans. Graph. 41, 2, Article 13 (2021), 21 pages.Google Scholar
    15. Florian Ferstl, Rüdiger Westermann, and Christian Dick. 2014. Large-scale liquid simulation on adaptive hexahedral grids. IEEE Transactions on Visualization and Computer Graphics 20, 10 (2014), 1405–1417.Google ScholarCross Ref
    16. Ming Gao, Xinlei Wang, Kui Wu, Andre Pradhana, Eftychios Sifakis, Cem Yuksel, and Chenfanfu Jiang. 2018. GPU optimization of material point methods. ACM Trans. Graph. 37, 6, Article 254 (2018), 12 pages.Google ScholarDigital Library
    17. Moritz Geilinger, David Hahn, Jonas Zehnder, Moritz Bächer, Bernhard Thomaszewski, and Stelian Coros. 2020. ADD: analytically differentiable dynamics for multi-body systems with frictional contact. ACM Trans. Graph. 39, 6, Article 190 (2020), 15 pages.Google ScholarDigital Library
    18. Robert M Gray. 1990. Quantization noise spectra. IEEE Transactions on Information Theory 36, 6 (1990), 1220–1244.Google ScholarDigital Library
    19. Andreas Griewank. 1992. Achieving logarithmic growth of temporal and spatial complexity in reverse automatic differentiation. Optimization Methods and Software 1, 1 (1992), 35–54.Google ScholarCross Ref
    20. David Hahn and Chris Wojtan. 2015. High-resolution brittle fracture simulation with boundary elements. ACM Trans. Graph. 34, 4, Article 151 (2015), 12 pages.Google ScholarDigital Library
    21. Konrad Hejn and Andrzej Pacut. 1996. Generalized model of the quantization error-a unified approach. IEEE Transactions on Instrumentation and Measurement 45, 1 (1996), 41–44.Google ScholarCross Ref
    22. Yuanming Hu, Luke Anderson, Tzu-Mao Li, Qi Sun, Nathan Carr, Jonathan Ragan-Kelley, and Frédo Durand. 2020. Diff Taichi: Differentiable Programming for Physical Simulation. In International Conference on Learning Representations (ICLR).Google Scholar
    23. Yuanming Hu, Yu Fang, Ziheng Ge, Ziyin Qu, Yixin Zhu, Andre Pradhana, and Chenfanfu Jiang. 2018. A moving least squares material point method with displacement discontinuity and two-way rigid body coupling. ACM Trans. Graph. 37, 4, Article 150 (2018), 14 pages.Google ScholarDigital Library
    24. Yuanming Hu, Tzu-Mao Li, Luke Anderson, Jonathan Ragan-Kelley, and Frédo Durand. 2019a. Taichi: a language for high-performance computation on spatially sparse data structures. ACM Trans. Graph. 38, 6, Article 201 (2019), 16 pages.Google ScholarDigital Library
    25. Yuanming Hu, Jiancheng Liu, Andrew Spielberg, Joshua B Tenenbaum, William T Freeman, Jiajun Wu, Daniela Rus, and Wojciech Matusik. 2019b. Chainqueen: A realtime differentiable physical simulator for soft robotics. In International Conference on Robotics and Automation (ICRA). IEEE, 6265–6271.Google ScholarDigital Library
    26. Yuanming Hu, Jiafeng Liu, Xuanda Yang, Mingkuan Xu, Ye Kuang, Weiwei Xu, Qiang Dai, William T. Freeman, and Frédo Durand. 2021. QuanTaichi: A Compiler for Quantized Simulations. ACM Trans. Graph. 40, 4, Article 182 (2021), 16 pages.Google ScholarDigital Library
    27. Libo Huang, Ziyin Qu, Xun Tan, Xinxin Zhang, Dominik L. Michels, and Chenfanfu Jiang. 2021. Ships, splashes, and waves on a vast ocean. ACM Trans. Graph. 40, 6 (2021), 203:1–203:15.Google ScholarDigital Library
    28. Doug L James and Dinesh K Pai. 1999. Artdefo: accurate real time deformable objects. In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques. 65–72.Google ScholarDigital Library
    29. Nuggehally S. Jayant and P. Noll. 1990. Digital Coding of Waveforms: Principles and Applications to Speech and Video. Prentice Hall Professional Technical Reference.Google Scholar
    30. Todd Keeler and Robert Bridson. 2015. Ocean Waves Animation Using Boundary Integral Equations and Explicit Mesh Tracking. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 11–19.Google Scholar
    31. D-U Lee, Altaf Abdul Gaffar, Ray CC Cheung, Oskar Mencer, Wayne Luk, and George A Constantinides. 2006. Accuracy-guaranteed bit-width optimization. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 25, 10 (2006), 1990–2000.Google ScholarDigital Library
    32. Yunzhu Li, Jiajun Wu, Russ Tedrake, Joshua B Tenenbaum, and Antonio Torralba. 2019. Learning Particle Dynamics for Manipulating Rigid Bodies, Deformable Objects, and Fluids. In International Conference on Learning Representations (ICLR).Google Scholar
    33. Junbang Liang, Ming C. Lin, and Vladlen Koltun. 2019. Differentiable Cloth Simulation for Inverse Problems. In Advances in Neural Information Processing Systems. 771–780.Google Scholar
    34. Haixiang Liu, Nathan Mitchell, Mridul Aanjaneya, and Eftychios Sifakis. 2016. A scalable schur-complement fluids solver for heterogeneous compute platforms. ACM Trans. Graph. 35, 6, Article 201 (2016), 12 pages.Google ScholarDigital Library
    35. Antoine McNamara, Adrien Treuille, Zoran Popović, and Jos Stam. 2004. Fluid control using the adjoint method. ACM Trans. Graph. 23, 3 (2004), 449–456.Google ScholarDigital Library
    36. Ramon E Moore and CT Yang. 1996. Interval analysis. Vol. 2. Prentice-Hall Englewood Cliffs, NJ.Google Scholar
    37. Ken Museth. 2013. VDB: High-resolution sparse volumes with dynamic topology. ACM Trans. Graph. 32, 3, Article 27 (2013), 22 pages.Google ScholarDigital Library
    38. Yi-Ling Qiao, Junbang Liang, Vladlen Koltun, and Ming C. Lin. 2020. Scalable Differentiable Physics for Learning and Control. In International Conference on Machine Learning (ICML). 7847–7856.Google Scholar
    39. Alvaro Sanchez-Gonzalez, Jonathan Godwin, Tobias Pfaff, Rex Ying, Jure Leskovec, and Peter Battaglia. 2020. Learning to simulate complex physics with graph networks. In International Conference on Machine Learning. 8459–8468.Google Scholar
    40. Leonard Schuchman. 1964. Dither signals and their effect on quantization noise. IEEE Transactions on Communication Technology 12, 4 (1964), 162–165.Google ScholarCross Ref
    41. Rajsekhar Setaluri, Mridul Aanjaneya, Sean Bauer, and Eftychios Sifakis. 2014. SPGrid: A sparse paged grid structure applied to adaptive smoke simulation. ACM Trans. Graph. 33, 6, Article 205 (2014), 12 pages.Google ScholarDigital Library
    42. Changchun Shi and Robert W Brodersen. 2004. A perturbation theory on statistical quantization effects in fixed-point DSP with non-stationary inputs. In 2004 IEEE International Symposium on Circuits and Systems (IEEE Cat. No. 04CH37512), Vol. 3. IEEE, III–373.Google Scholar
    43. Barbara Solenthaler and Markus Gross. 2011. Two-Scale Particle Simulation. ACM Trans. Graph. 30, 4, Article 81 (2011), 8 pages.Google ScholarDigital Library
    44. Wonyong Sung and Ki-Il Kum. 1995. Simulation-based word-length optimization method for fixed-point digital signal processing systems. IEEE Transactions on Signal Processing 43, 12 (1995), 3087–3090.Google ScholarDigital Library
    45. Andre Pradhana Tampubolon, Theodore Gast, Gergely Klár, Chuyuan Fu, Joseph Teran, Chenfanfu Jiang, and Ken Museth. 2017. Multi-species simulation of porous sand and water mixtures. ACM Trans. Graph. 36, 4, Article 105 (2017), 11 pages.Google ScholarDigital Library
    46. Shervin Vakili, JM Pierre Langlois, and Guy Bois. 2013. Enhanced precision analysis for accuracy-aware bit-width optimization using affine arithmetic. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 32, 12 (2013), 1853–1865.Google ScholarDigital Library
    47. Xinlei Wang, Yuxing Qiu, Stuart R Slattery, Yu Fang, Minchen Li, Song-Chun Zhu, Yixin Zhu, Min Tang, Dinesh Manocha, and Chenfanfu Jiang. 2020. A massively parallel and scalable multi-GPU material point method. ACM Trans. Graph. 39, 4, Article 30 (2020), 15 pages.Google ScholarDigital Library
    48. Zhendong Wang, Longhua Wu, Marco Fratarcangeli, Min Tang, and Huamin Wang. 2018. Parallel multigrid for nonlinear cloth simulation. Computer Graphics Forum 37, 7 (2018), 131–141.Google ScholarCross Ref
    49. Rob Wannamaker, Stanley Lipshitz, John Vanderkooy, and J. Wright. 2000. A theory of nonsubtractive dither. IEEE Transactions on Signal Processing 48 (2000), 499–516.Google ScholarDigital Library
    50. B. Widrow. 1961. Statistical analysis of amplitude-quantized sampled-data systems. Transactions of the American Institute of Electrical Engineers, Part II: Applications and Industry 79, 6 (1961), 555–568.Google ScholarCross Ref
    51. Jun Wu, Christian Dick, and Rüdiger Westermann. 2015. A system for high-resolution topology optimization. IEEE Transactions on Visualization and Computer Graphics 22, 3 (2015), 1195–1208.Google ScholarDigital Library
    52. Kui Wu, Nghia Truong, Cem Yuksel, and Rama Hoetzlein. 2018. Fast fluid simulations with sparse volumes on the GPU. Computer Graphics Forum 37, 2 (2018), 157–167.Google ScholarCross Ref
    53. Jonas Zehnder, Rahul Narain, and Bernhard Thomaszewski. 2018. An advection-reflection solver for detail-preserving fluid simulation. ACM Trans. Graph. 37, 4, Article 85 (2018), 8 pages.Google ScholarDigital Library


ACM Digital Library Publication: