The Euclid Project

The Euclid project is developing the capability to perform physical simulations by computing directly on databases. All steps of the process, including mesh generation, solving, and visualization, work by directly querying and updating databases. With this database approach, the size of simulations is limited by disk capacity rather than by memory capacity, allowing scientists and engineers to run much larger simulations on their desktop systems than is currently possible.

Our current approach is based on performing finite difference and finite element simulations using octrees stored in database structures called etrees. Each octree is stored on disk as a sequence of fixed sized octant records sorted by a locational code order that is equivalent to a preorder traversal of the tree and a space-filling Z-order traversal through the domain. The sorted records are indexed by a conventional file-resident B-tree index and queried using fixed-length locational code keys.

We have developed a system for manipulating etrees called the etree library. The library is written in C and provides a couple dozen functions for creating, modifying, and searching octrees, including efficient mechanisms for appending octants and iterating over octants in Z-order. Complete sources and documentation are available free of charge to researchers.

The Euclid Project is supported in part by the NSF-sponsored Community Modeling Environment Project at the Southern California Earthquake Center, and in part by the National Science Foundation.

Etree library software available for downloading

• The etree library and example programs (tar file, gzipped tar file, bzipped tar file). Contents:
  • Source code for the etree library.
  • Example C code.
  • Example application program that builds and queries an etree representation
    of the SCEC 3D Velocity Model of Southern California.
• Technical report that documents the etree library
  • Tiankai Tu, David O'Hallaron, Julio Lopez, The Etree Library: A System for Manipulating Large Octrees on Disk, Technical Report CMU-CS-03-174, School of Computer Science, Carnegie Mellon University, July, 2003 (pdf).

Papers and presentations

• Volkan Akcelik, Jacobo Bielak, George Biros, Ioannis Epanomeritakis, Antonio Fernandez, Omar Ghattas, Eui Joong Kim, Julio Lopez, David O'Hallaron, Tiankai Tu, and John Urbanic. High Resolution Forward and Inverse Earthquake Modeling on Terasacale Computers , SC2003, Phoenix, AZ, 2003. ( pdf, bib )
  MPEG animation of the simulation result
  
  Winner, 2003 Gordon Bell Award for Special Achievement

  The milestone calculations for the award included:

  • The generation of a record unstructured hex mesh
    (3.7 billion elements, 4 billion nodes)
  • The largest unstructured mesh wave propagation simulation
    (900 million elements, 3.2 billion DOF)
  • The largest acoustic wave propagation inverse problem
    (17 million inversion parameters, 70 billion total unknowns)
  • The largest elastic wave propagation inverse problem
    (275,000 inversion parameters, something like a billion total unknowns).
• Tiankai Tu, David R. O'Hallaron, and Julio Lopez The Etree Library: A System for Manipulating Large Octrees on Disk. Technical Report CMU-CS-03-174, School of Computer Science, Carnegie Mellon University, July, 2003. ( ps, pdf, ppt, bib ).
• Tiankai Tu, David R. O'Hallaron, and Julio Lopez, Etree: A Database-Oriented Method for Generating Large Octree Meshes. In Proceedings of the Eleventh International Meshing Roundtable (Ithaca, NY, Sept. 2002), pp. 127-138. ( ps, pdf, ppt, bib )
• David R. O'Hallaron, Database Methods for Scientific Computing, Northwestern University, Feb, 2003. This is an overview of the Euclid project. ( ppt, MPEG animation on title slide )

Applications

• Etree Mesh Generator: The program converts a physical model, stored as an etree, into an octree mesh whose nodes and elements are also stored as etrees. We are using our mesh generator to build octree meshes of the LA basin with over 100M grid points. The meshes are being used by Jacobo Bielak and Omar Ghattas and their students to perform forward and inverse earthquake ground motion modeling on the terascale system at Pittsburgh Supercomputing Center. (See the pdf working document.)
• Etree Finite Element Solver: This program uses the octree-based finite element technique developed by Jacobo Bielak, Omar Ghattas, and Eui Jun Kim. The prototype solver saves the output of each simulated timestep in a separate three-dimensional etree. Later versions will save all simulation results in a single compressed four-dimensional etree.
• LA Community Velocity Model (CVM) Service: The CVM service is an interactive Web service that models the density of the ground underneath Los Angeles as an etree, and then allows you to visualize the density of arbitrary slices of the ground using your Web browser. The etree data is provided by the SCEC 3D Velocity Model for Southern California, which was developed by geologists and seismologists at the Southern California Earthquake Center (SCEC).

People

• Tiankai Tu
• Julio Lopez
• Dave O'Hallaron
• Jacobo Bielak
• Omar Ghattas