DAG Based Construction for Global Sparse Grids

Scaling of Tasmanian DAG construction.
Scaling of Tasmanian DAG construction.


  • Developed a DAG based algorithm for dynamic sparse grid construction.
  • Updated the Tasmanian interface to accommodate the mode flexible sampling approach.
  • Implemented the internal data-structures needed to construct a desired sub-set of the infinite DAG and to weigh the nodes according to inferred model properties.

Significance and Impact

  • The DAG based algorithms will allow Tasmanian to better utilize the extreme concurrency available in the modern supercomputers.
  • The dynamic construction procedure will simplify future interfaces between models and the Tasmanian library.
  • Parallelization of the sampling procedure is now possible beyond the basic embarrassingly parallel paradigm.

Research Details

  • The most efficient adaptive surrogate construction methods compute model samples in sequential samples.
  • Even if the batch is parallelized, the overall procedure cannot advance faster than the slowest sample per batch.
  • Sampling approach based on Directed Acyclic Graph (DAG) is needed to alleviate the batch bottleneck, but the DAG has to be constructed on the fly, while the grid is adapted to the target model.


The most efficient surrogate construction algorithms are carefully tailored towards the specific target model. The tailoring is commonly done on two levels, first selecting the general class of the model and then finding a set of specific tuning constants that aim at optimal accuracy. Adaptive sparse grids algorithms aim at inferring the tuning constants in an iterative procedure, collect samples from the model, infer constant, collect more samples, etc. The samples are computed in batches and each batch is embarrassingly parallelizable, but the refinement procedure cannot advance faster than the slowest sample in each batch. Complex model usually produce samples with dramatically different execution time, which bottle-necks the process and leads to waste of human and computer resources. A dynamic construction procedure is needed where samples are organized in a DAG as opposed to discrete batches. Furthermore, the DAG has to be constructed and updated on the fly, as samples are computed and more accurate tuning constants are inferred from the data.