SPGrid @ SIGGRAPH 2014

Table of Contents

paper link
https://dl.acm.org/doi/pdf/10.1145/2661229.2661269

Uniform grid is too costly for fluid simulation. How to design new hardware-friendly sparse-populated uniform grids data structures?

Prerequisite (OpenVDB)

paper link
http://www.museth.org/Ken/OpenVDB_files/Museth_TOG13.pdf

OpenVDB is hierarchical data structure for storing grid data:

2022-11-16_16-38-57_screenshot.png

2022-11-16_16-39-38_screenshot.png

SpGrid

SpGrid leverages established hardware acceleration mechanisms of the virtual memory subsystem.

  • competitive performance to dense uniform grids.
  • stencil operations can be performed natively with linearized (encoded) address without translating them into geometric coordinates.

Comparison w/ VDB

  • Cache mechanisms
    • VDB uses software cache to store address translations of tree nodes.
    • SPGrid uses Translation Lookaside Buffer (TLB) for this purpose.
  • Storage
    • SPGrid only stores sparse subsets of a single uniform grid.
    • VDB also store values at coarser tree nodes.
  • Capacity
    • VDB supports out-of-core processing.
    • SPGrid only stores data in main memory.
  • Resolution
    • VDB's resolution is only limited by available space.
    • SPGrid has finite maximum grid size.

Design

Random access in fluid simulation exhibit spatial conherence (a.k.a. spatial sparsity). Managing a sparse subset of dense storage is similar to the concept of Virtual Memory.

SPGrid propose a locality-preserving mapping from 2D/3D grid locations to 1D memory span, and use Virtual Memory mechanisms to avoid allocation of unused regions.

Morgan ordering

2022-11-16_17-01-15_screenshot.png

Morgan ordering is locality promoting map: w/ high probability, geometrically proximate array entries will be stored in nearby memory locations.

SPGrid allocates a virtual memory address span for the entire array, but lazy evaluated until contents being accessed, this is feasible with mmap system call.

  1. mmap issues a page fault and reserve a physical page when accessing a virtual page that has not been allocated.
  2. If the accessed virtual page has already been mapped, the address translation is entirely handled by hardware (TLB), no operating system intervention is required.

TODO Address Computation

Access Modes

2022-11-16_17-20-18_screenshot.png

Author: expye(Zihao YE)

Email: expye@outlook.com

Date: 2022-11-16 Wed 00:00

Last modified: 2022-12-04 Sun 02:08

Licensed under CC BY-NC 4.0