Ebb: A DSL for Physical Simulation on CPUs and GPUs

Gilbert Louis Bernstein, Chinmayee Shah, Crystal Lemire, Zachary DeVito, Matthew Fisher, Philip Alexander Levis, Pat HanrahanACM Trans. Graphics 2016 · DOI

TL;DR

This paper introduces Ebb, a domain-specific language (DSL) designed to simplify the creation of high-performance physical simulations that can run efficiently on both CPUs and GPUs. Ebb achieves this by employing a novel three-layer architecture that separates simulation logic, geometric domain definitions, and hardware-specific runtimes, enabling greater code reusability and easier development.

What Problem Does This Paper Address?

Developing efficient physical simulations for computer graphics and animation is notoriously challenging. This difficulty stems from the need to handle diverse algorithms and geometric domains (like fluid grids, cloth meshes, or tetrahedral volumes), often requiring the coupling of multiple physical phenomena. Furthermore, achieving high performance necessitates expertise in parallel programming for heterogeneous architectures like CPUs and GPUs. This steep learning curve and the complexity of managing different domains and parallelization strategies make simulation code difficult and expensive to develop, leading to a scarcity of qualified experts. Existing solutions often either restrict themselves to a single geometric domain or result in large, unmanageable codebases with limited parallelization support.

Methods

Ebb tackles these challenges with a three-layer architecture:

  1. Simulation Code (Top Layer): Users write simulation logic in Ebb's kernel language, which is embedded within Lua. This layer focuses on the physics and algorithms, abstracting away the underlying geometric domain and hardware details. Kernels are data-parallel operations launched over sets of elements within a domain.
  2. Domain Libraries (Middle Layer): This layer defines various geometric domains (e.g., triangle meshes, regular grids, tetrahedral volumes) using a unified, relational data model. These libraries provide a familiar interface for common data structures and allow different domains to interoperate.
  3. Runtime (Bottom Layer): This layer implements the relational model and provides backends for targeting both CPU and GPU architectures. It handles memory management, data layout optimization, and efficient parallel code generation.

A key innovation is Ebb's use of a relational data model as the unifying abstraction for geometric domains. This model, inspired by database concepts, allows for expressive representation of topological relationships and efficient querying. Ebb provides three core relational modeling primitives: key-fields (for one-to-one relationships), query-loops (for one-to-many relationships), and affine-indices (for regular grids). This approach allows for the development of domain libraries that are independent of the runtime implementation, making the system extensible.

Datasets

The paper evaluates Ebb using several existing simulation benchmarks and datasets:

  • FluidsGL: An incompressible fluid flow simulation using regular grids.
  • Vega: A FEM simulation of elastically deformable solids using tetrahedral meshes.
  • FreeFem++: A FEM simulation of a Neo-Hookean elasticity model on tetrahedral meshes.
  • Lulesh: A benchmark for evaluating simulation code performance on hexahedral meshes.

The paper does not introduce new datasets but rather uses these established benchmarks to compare Ebb's performance and expressiveness against existing solutions.

Key Insights and Ideas

  • Relational Abstraction for Geometric Domains: Unifying diverse geometric domains under a single relational data model is a powerful way to achieve code reusability and extensibility in simulation frameworks. This abstraction hides the complexity of domain-specific data structures from the simulation programmer.
  • Three-Layer Architecture for Separation of Concerns: Decoupling simulation logic, domain definitions, and runtime implementation significantly simplifies development and maintenance. This allows programmers to focus on physics without worrying about low-level parallelization or data management.
  • Performance Portability: Ebb's design enables code written for one architecture (e.g., CPU) to be efficiently compiled and run on another (e.g., GPU) with minimal or no code changes, a significant advantage for modern hardware.
  • Interoperability with External Libraries: Ebb's ability to seamlessly integrate with external libraries (like CUFFT for FFTs) is crucial for real-world simulations that often rely on specialized, highly optimized components. This avoids the overhead of data marshaling.
  • Conciseness and Readability: Ebb's DSL, combined with its relational primitives and automatic memory management, leads to significantly more concise and readable simulation code compared to hand-written implementations.

Key Results

  • Performance: Ebb achieves performance comparable to hand-tuned GPU code in some cases (within 27% of FluidsGL's CUDA implementation) and significantly outperforms CPU implementations when GPU code is unavailable (up to 9x faster for Vega).
  • Code Size: Ebb implementations are substantially more concise. For Vega, the Ebb version was under 1.4K lines of code, compared to over 3.7K lines for the original C/C++ implementation.
  • Memory Usage: Ebb generally uses less memory than reference implementations, often half or less, due to its efficient memory management and avoidance of redundant data representations.
  • Extensibility: The relational primitives allow for the easy addition of new domain libraries without modifying the runtime.

Limitations and Future Work

  • Static Topology: The current implementation primarily supports simulations with static topology. Future work aims to incorporate support for dynamic topologies, including collision detection and adaptive remeshing operations, which will require handling geometric queries and acceleration structures (e.g., octrees).
  • CPU/GPU Co-execution: The current system runs either entirely on the CPU or entirely on the GPU. Future work will explore balancing computation between CPU and GPU for better integration with other tasks like rendering.
  • Data Layout Optimization: While Ebb uses column-store layout, future work may explore row-oriented storage for relations with sparsely accessed, but frequently used together fields.
  • Thread Cooperation: For complex intra-element operations, future work could explore allowing multiple threads to cooperate on a single element's computation to reduce register pressure.
  • Auto-tuning: The dynamic compilation nature of Ebb opens possibilities for auto-tuning layout and execution strategies by recompiling and timing kernels during runtime.

Summary updated

BibTeX
@article{bernstein2016ebb,
  author = {Gilbert Louis Bernstein and Chinmayee Shah and Crystal Lemire and Zachary DeVito and Matthew Fisher and Philip Alexander Levis and Pat Hanrahan},
  title = {{Ebb: A DSL for Physical Simulation on CPUs and GPUs}},
  journal = {ACM Trans. Graphics},
  year = {2016},
  doi = {10.1145/2892632},
}
Figure