SPGrid @ SIGGRAPH 2014
Table of Contents
Uniform grid is too costly for fluid simulation. How to design new hardware-friendly sparse-populated uniform grids data structures?
Prerequisite (OpenVDB)
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
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.
mmapissues a page fault and reserve a physical page when accessing a virtual page that has not been allocated.- 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
