Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Merge tree”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 37 records · Page 2

In situ and in-transit analysis of cosmological simulations

Abstract Modern cosmological simulations have reached the trillion-element scale, rendering data storage and subsequent analysis formidable tasks. To address this circumstance, we present a new MPI-parallel approach for analysis of simulation data while the simulation runs, as an alternative to the traditional workflow consisting of periodically saving large data sets to disk for subsequent ‘offline’ analysis. We demonstrate this approach in the compressible gasdynamics/ N -body code Nyx, a hybrid $\mbox{MPI}+\mbox{OpenMP}$ MPI + OpenMP code based on the BoxLib framework, used for large-scale cosmological simulations. We have enabled on-the-fly workflows in two different ways: one is a straightforward approach consisting of all MPI processes periodically halting the main simulation and analyzing each component of data that they own (‘ in situ ’). The other consists of partitioning processes into disjoint MPI groups, with one performing the simulation and periodically sending data to the other ‘sidecar’ group, which post-processes it while the simulation continues (‘in-transit’). The two groups execute their tasks asynchronously, stopping only to synchronize when a new set of simulation data needs to be analyzed. For both the in situ and in-transit approaches, we experiment with two different analysis suites with distinct performance behavior: one which finds dark matter halos in the simulation using merge trees to calculate the mass contained within iso-density contours, and another which calculates probability distribution functions and power spectra of various fields in the simulation. Both are common analysis tasks for cosmology, and both result in summary statistics significantly smaller than the original data set. We study the behavior of each type of analysis in each workflow in order to determine the optimal configuration for the different data analysis algorithms.

79 ASTRONOMY AND ASTROPHYSICS↗

An analysis of image storage systems for scalable training of deep neural networks

This study presents a principled empirical evaluation of image storage systems for training deep neural networks. We employ the Caffe deep learning framework to train neural network models for three different data sets, MNIST, CIFAR-10, and ImageNet. While training the models, we evaluate five different options to retrieve training image data: (1) PNG-formatted image files on local file system; (2) pushing pixel arrays from image files into a single HDF5 file on local file system; (3) in-memory arrays to hold the pixel arrays in Python and C++; (4) loading the training data into LevelDB, a log-structured merge tree based key-value storage; and (5) loading the training data into LMDB, a B+tree based key-value storage. The experimental results quantitatively highlight the disadvantage of using normal image files on local file systems to train deep neural networks and demonstrate reliable performance with key-value storage based storage systems. When training a model on the ImageNet dataset, the image file option was more than 17 times slower than the key-value storage option. Along with measurements on training time, this study provides in-depth analysis on the cause of performance advantages/disadvantages of each back-end to train deep neural networks. We envision the provided measurements and analysis will shed light on the optimal way to architect systems for training neural networks in a scalable manner.

Lim, Seung-Hwan↗

Parallel peak pruning for scalable SMP contour tree computation

As data sets grow to exascale, automated data analysis and visualisation are increasingly important, to intermediate human understanding and to reduce demands on disk storage via in situ analysis. Trends in architecture of high performance computing systems necessitate analysis algorithms to make effective use of combinations of massively multicore and distributed systems. One of the principal analytic tools is the contour tree, which analyses relationships between contours to identify features of more than local importance. Unfortunately, the predominant algorithms for computing the contour tree are explicitly serial, and founded on serial metaphors, which has limited the scalability of this form of analysis. While there is some work on distributed contour tree computation, and separately on hybrid GPU-CPU computation, there is no efficient algorithm with strong formal guarantees on performance allied with fast practical performance. Here in this paper, we report the first shared SMP algorithm for fully parallel contour tree computation, withfor-mal guarantees of O(lgnlgt) parallel steps and O(n lgn) work, and implementations with up to 10x parallel speed up in OpenMP and up to 50x speed up in NVIDIA Thrust.

97 MATHEMATICS AND COMPUTING↗

A Study of QCD Radiation in VBF Higgs Production with Vincia and Pythia

We discuss and illustrate the properties of several parton-shower algorithms available in Pythia and Vincia, in the context of Higgs production via vector boson fusion (VBF). In particular, the distinctive colour topology of VBF processes allows to define observables sensitive to the coherent radiation pattern of additional jets. We study a set of such observables, using the Vincia sector-antenna shower as our main reference, and contrast it to Pythia's transverse-momentum-ordered DGLAP shower as well as Pythia's dipole-improved shower. We then investigate the robustness of these predictions as successive levels of higher-order perturbative matrix elements are incorporated, including next-to-leading-order matched and tree-level merged calculations, using Powheg Box and Sherpa respectively to generate the hard events.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

Stack Trace Analysis Tool (STAT)

STAT is a light weight debugging tool that gathers and merges stack traces from all of the processes in a parallel application. STAT uses the MRNet tree based overlay network to broadcast commands from the tool front-end to the STAT daemons and for the front-end to gather the traces from the STAT daemons. As the traces propagate through the MRNet network tree, they are merged across all tasks to fonn a single call prefix tree. The call prefix tree can be examined to identify tuks with similar function call patterns and to delineate a small set of equivalence classes. A representative task from each of these classes can then be fed into a full feature debugger like TotalView for root cause analysis.

ECP↗

Stack Trace Ahalysis Tool

STAT is a light weight debugging tool that gathers and merges stack traces from all of the processes in a parallel application. STAT uses the MRNet tree based overlay network to broadcast commands from the tool front-end to the STAT daemons and for the front-end to gather the traces from the STAT daemons. As the traces propagate through the MRNet network tree, they are merged across all tasks to form a similar function call patterns and to delineate a small set of equivalence classes. A representative task from each of these classes can then be fed into a full feature debugger like TolalView for root cause analysis.

Lee, Gregory L.↗

Multi-jet Merging with NLO Matrix Elements

In the algorithm presented here, the ME+PS approach to merge samples of tree-level matrix elements into inclusive event samples is combined with the POWHEG method, which includes exact next-to-leading order matrix elements in the parton shower. The advantages of the method are discussed and the quality of its implementation in SHERPA is exemplified by results for e{sup +}e{sup -} annihilation into hadrons at LEP, for deep-inelastic lepton-nucleon scattering at HERA, for Drell-Yan lepton-pair production at the Tevatron and for W{sup +}W{sup -}-production at LHC energies. The simulation of hard QCD radiation in parton-shower Monte Carlos has seen tremendous progress over the last years. It was largely stimulated by the need for more precise predictions at LHC energies where the large available phase space allows additional hard QCD radiation alongside known Standard Model processes or even signals from new physics. Two types of algorithms have been developed, which allow to improve upon the soft-collinear approximations made in the parton shower, such that hard radiation is simulated according to exact matrix elements. In the ME+PS approach [1] higher-order tree-level matrix elements for different final-state jet multiplicity are merged with each other and with subsequent parton shower emissions to generate an inclusive sample. Such a prescription is invaluable for analyses which are sensitive to final states with a large jet multiplicity. The only remaining deficiency of such tree-level calculations is the large uncertainty stemming from scale variations. The POWHEG method [2] solves this problem for the lowest multiplicity subprocess by combining full NLO matrix elements with the parton shower. While this leads to NLO accuracy in the inclusive cross section and the exact radiation pattern for the first emission, it fails to describe higher-order emissions with improved accuracy. Thus it is not sufficient if final states with high jet multiplicities are considered. With the complementary advantages of these two approaches, the question arises naturally whether it would be possible to combine them into an even more powerful one. Such a combined algorithm was independently developed in [5] and [6]. Here a summary of the algorithm is given and predictions from corresponding Monte-Carlo predictions are presented.

43 PARTICLE ACCELERATORS↗

Hybrid Parameter Search and Dynamic Model Selection for Mixed-Variable Bayesian Optimization

Herein this article presents a new type of hybrid model for Bayesian optimization (BO) adept at managing mixed variables, encompassing both quantitative (continuous and integer) and qualitative (categorical) types. Our proposed new hybrid models (named hybridM) merge the Monte Carlo Tree Search structure (MCTS) for categorical variables with Gaussian Processes (GP) for continuous ones. hybridM leverages the upper confidence bound tree search (UCTS) for MCTS strategy, showcasing the tree architecture’s integration into Bayesian optimization. Our innovations, including dynamic online kernel selection in the surrogate modeling phase and a unique UCTS search strategy, position our hybrid models as an advancement in mixed-variable surrogate models. Numerical experiments underscore the superiority of hybrid models, highlighting their potential in Bayesian optimization.

97 MATHEMATICS AND COMPUTING↗

The Influence of Concentration and Dynamical State on Scatter in the Galaxy Cluster Mass-Temperature Relation

Using a hydrodynamics plus N -body simulation of galaxy cluster formation within a large volume and mock Chandra X-ray observations, we study the form and evolution of the intrinsic scatter about the best-fit X-ray temperature-mass relation for clusters. We investigate the physical origin of the scatter by correlating it with quantities that are closely related to clusters' formation and merging histories. We also examine the distribution of the scatter for merging and non-merging populations, identified using halo merger trees derived from the simulation as well as X-ray substructure measures. We find a strong correlation between the scatter in the M-T X relation and the halo concentration, in the sense that more concentrated clusters tend to be cooler than clusters with similar masses. No bias is found between the merging and relaxed clusters, but merging clusters generally have greater scatter, which is related to the properties of the distribution of halo concentrations. We also detect a signature of non-lognormality in the distribution of scatter for our simulated clusters both at z = 0 and at z = 1. A detailed comparison of merging clusters identified by substructure measures and by halo merger trees is given in the discussion. Finally we conclude that, when cooling-related effects are neglected, the variation in halo concentrations is a more important factor for driving the intrinsic scatter in the M-T X relation, while departures from hydrostatic equilibrium due to cluster mergers have a minor effect.

79 ASTRONOMY AND ASTROPHYSICS↗

Convergence Rates for Empirical Estimation of Binary Classification Bounds

Bounding the best achievable error probability for binary classification problems is relevant to many applications including machine learning, signal processing, and information theory. Many bounds on the Bayes binary classification error rate depend on information divergences between the pair of class distributions. Recently, the Henze–Penrose (HP) divergence has been proposed for bounding classification error probability. We consider the problem of empirically estimating the HP-divergence from random samples. We derive a bound on the convergence rate for the Friedman–Rafsky (FR) estimator of the HP-divergence, which is related to a multivariate runs statistic for testing between two distributions. The FR estimator is derived from a multicolored Euclidean minimal spanning tree (MST) that spans the merged samples. We obtain a concentration inequality for the Friedman–Rafsky estimator of the Henze–Penrose divergence. We validate our results experimentally and illustrate their application to real datasets.

97 MATHEMATICS AND COMPUTING↗

Scalable Contour Tree Computation by Data Parallel Peak Pruning

As data sets grow to exascale, automated data analysis and visualization are increasingly important, to intermediate human understanding and to reduce demands on disk storage via in situ analysis. Trends in architecture of high performance computing systems necessitate analysis algorithms to make effective use of combinations of massively multicore and distributed systems. One of the principal analytic tools is the contour tree, which analyses relationships between contours to identify features of more than local importance. Unfortunately, the predominant algorithms for computing the contour tree are explicitly serial, and founded on serial metaphors, which has limited the scalability of this form of analysis. While there is some work on distributed contour tree computation, and separately on hybrid GPU-CPU computation, there is no efficient algorithm with strong formal guarantees on performance allied with fast practical performance. Furthermore, we report the first shared SMP algorithm for fully parallel contour tree computation, with formal guarantees of O(lg V lg t) parallel steps and O(V lg V) work for data with V samples and t contour tree supernodes, and implementations with more than 30× parallel speed up on both CPU using TBB and GPU using Thrust and up 70× speed up compared to the serial sweep and merge algorithm.

97 MATHEMATICS AND COMPUTING↗

A Mountaintop View Requires Minimal Sorting: A Faster Contour Tree Algorithm

Consider a scalar field f : M → R, where M is a triangulated simplicial mesh in R d . A level set, or contour, at value v is a connected component of f –1 (v). As v is changed, these contours change topology, merge into each other, or split. Contour trees are concise representations of f that track this contour behavior. The vertices of these trees are the critical points of f, where the gradient is zero. The edges represent changes in the topology of contours. It is a fundamental data structure in data analysis and visualization, and there is significant previous work (both theoretical and practical) on algorithms for constructing contour trees. Suppose M has n vertices, N facets, and t critical points. A classic result of Carr, Snoeyink, and Axen (2000) gives an algorithm that takes O(n log n+Nα(N)) time (where α(·) is the inverse Ackermann function). A further improvement to O(t log t + N) time was given by Chiang et al. All these algorithms involve a global sort of the critical points, a significant computational bottleneck. Unfortunately, lower bounds of Ω(t log t) also exist. We present the first algorithm that can avoid the global sort and has a refined time complexity that depends on the contour tree structure. Intuitively, if the tree is short and fat, we get significant improvements in running time. For a partition of the contour tree into a set of descending paths, P, our algorithm runs in O($\Sigma$ pϵP |p| log |p| + tα(t) + N). This is at most O(t log D + N), where D is the diameter of the contour tree. Moreover, it is O(tα(t) + N) for balanced trees, a significant improvement over the previous complexity. Our algorithm requires numerous ideas: partitioning the contour tree into join and split trees, a local growing procedure to iteratively build contour trees, and the use of heavy path decompositions for the time complexity analysis. There is a crucial use of a family of binomial heaps to maintain priorities, ensuring that any comparison made is between comparable nodes of the contour tree. We also prove lower bounds showing that the $\Sigma$ pϵP |p| log |p| complexity is inherent to computing contour trees.

97 MATHEMATICS AND COMPUTING↗

Extended Subadiabatic Layer in Simulations of Overshooting Convection

We present numerical simulations of hydrodynamic overshooting convection in local Cartesian domains. We find that a substantial fraction of the lower part of the convection zone (CZ) is stably stratified according to the Schwarzschild criterion while the enthalpy flux is outward directed. This occurs when the heat conduction profile at the bottom of the CZ is smoothly varying, based either on a Kramers-like opacity prescription as a function of temperature and density or a static profile of a similar shape. We show that the subadiabatic layer arises due to nonlocal energy transport by buoyantly driven downflows in the upper parts of the CZ. Analysis of the force balance of the upflows and downflows confirms that convection is driven by cooling at the surface. We find that the commonly used prescription for the convective enthalpy flux being proportional to the negative entropy gradient does not hold in the stably stratified layers where the flux is positive. We demonstrate the existence of a non-gradient contribution to the enthalpy flux, which is estimated to be important throughout the convective layer. A quantitative analysis of downflows indicates a transition from a tree-like structure where smaller downdrafts merge into larger ones in the upper parts to a structure in the deeper parts where a height-independent number of strong downdrafts persist. This change of flow topology occurs when a substantial subadiabatic layer is present in the lower part of the CZ.

79 ASTRONOMY AND ASTROPHYSICS↗

Man-made objects cuing in satellite imagery

We present a multi-scale framework for man-made structures cuing in satellite image regions. The approach is based on a hierarchical image segmentation followed by structural analysis. A hierarchical segmentation produces an image pyramid that contains a stack of irregular image partitions, represented as polygonized pixel patches, of successively reduced levels of detail (LOOs). We are jumping off from the over-segmented image represented by polygons attributed with spectral and texture information. The image is represented as a proximity graph with vertices corresponding to the polygons and edges reflecting polygon relations. This is followed by the iterative graph contraction based on Boruvka's Minimum Spanning Tree (MST) construction algorithm. The graph contractions merge the patches based on their pairwise spectral and texture differences. Concurrently with the construction of the irregular image pyramid, structural analysis is done on the agglomerated patches. Man-made object cuing is based on the analysis of shape properties of the constructed patches and their spatial relations. The presented framework can be used as pre-scanning tool for wide area monitoring to quickly guide the further analysis to regions of interest.

97 MATHEMATICS AND COMPUTING↗

The Global LAnd Surface Satellite (GLASS) evapotranspiration product Version 5.0: Algorithm development and preliminary validation

An accurate estimation of spatially and temporally continuous global terrestrial evapotranspiration (ET) is essential in the assessment of surface energy, water and carbon cycles. The Global LAnd Surface Satellite (GLASS) ET product Version 4.0 (v4.0) based on the Bayesian model averaging (BMA) method was generated to estimate global terrestrial ET. However, certain uncertainty for the GLASS ET product v4.0 limits its application. In this study, we introduced the deep neural networks (DNN) merging framework to improve terrestrial ET estimation for GLASS ET product Version 5.0 (v5.0) generation by integrating five satellite-derived ET products [Moderate Resolution Imaging Spectroradiometer (MODIS) ET product (MOD16), Shuttleworth–Wallace dual-source ET product (SW), Priestley–Taylor-based ET product (PT-JPL), modified satellite-based Priestley–Taylor ET product (MS-PT) and simple hybrid ET product (SIM)]. We compared the performance of DNN method against other merging methods, including GLASS ET algorithm v4.0 (BMA), the gradient boosting regression tree (GBRT) method and the random forest (RF) method, based on 195 global eddy covariance (EC) flux towers covering observations from 2000 through 2015. Validations indicated that the DNN had the highest accuracy among four merging methods across different land cover types, yielding the highest average determination coefficients (R 2 , 0.62), root-mean-squared-error (RMSE, 24.1 W/m 2 ) and Kling–Gupta efficiency (KGE, 0.77) with a of 99% confidence interval. Compared with GLASS ET algorithm v4.0, the DNN improved on the R 2 by approximately 7% (p < 0.01) and the KGE by 10%. Based on the DNN, we then generated 8-day GLASS ET product v5.0 globally with a 1 km spatial resolution from 2001 to 2015 driven by GLASS vegetation and surface net radiation (R n ) datasets and Modern-Era Retrospective Analysis for Research and Applications, Version 2 (MERRA2) datasets. Finally, this global terrestrial ET product provides a valuable dataset for monitoring regional and global water resources and environmental changes.

54 ENVIRONMENTAL SCIENCES↗

Evaluation of Programming Language-Aware Diffs for Improving Developer Productivity

As the number of supported platforms for SNL software increases, so do the testing requirements. This increases the total time spent between when a developer submits code for testing, and when tests are completed. This in turn leads developers to hold off submitting code for testing, meaning that when code is ready for testing there's a lot more of it. This increases the likelihood of merge conflicts which the developer must resolve by hand -- because someone else touched the files near the lines the developer touched. Current text-based diff tools often have trouble resolving conflicts in these cases. Work in Europe and Japan has demonstrated that, using programming language aware diff tools (e.g., using the abstract syntax tree (AST) a compiler might generate) can reduce the manual labor necessary to resolve merge conflicts. These techniques can detect code blocks which have moved, as opposed than current text-based diff tools, which only detect insertions / deletions of text blocks. In this study, we evaluate one such tool, GumTree, and see how effective it is as a replacement for traditional text-based diff approaches.

97 MATHEMATICS AND COMPUTING↗