Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Algorithms and data structure”

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 109 records · Page 6

Implementing a neural network interatomic model with performance portability for emerging exascale architectures

The two main thrusts of computational science are increasingly accurate predictions and faster calculations; to this end, the zeitgeist in molecular dynamics (MD) simulations is pursuing machine learned and data driven interatomic models, e.g. neural network potentials, and novel hardware architectures, e.g. GPUs. Current implementations of neural network potentials are orders of magnitude slower than traditional interatomic models and while looming exascale computing offers the ability to run large, accurate simulations with these models, achieving portable performance for MD with new and varied exascale hardware requires rethinking traditional algorithms, using novel data structures, and library solutions. We re-implement a neural network interatomic model in CabanaMD, an MD proxy application, built on libraries developed for performance portability. Our implementation shows significantly improved thread scaling in this complex kernel as compared to a current LAMMPS implementation, across both strong and weak scaling. Our single-source solution enables simulations up to 20 million atoms on a single CPU node and 4 million atoms with improved performance on a single GPU. Furthermore, we also explore parallelism and data layout choices (using flexible data structures called AoSoAs) and their effect on performance, seeing up to ~50% and ~5% improvements in performance on a GPU by choosing the right level of parallelism and data layout respectively.

97 MATHEMATICS AND COMPUTING↗

MemFriend: Understanding Memory Performance with Spatial-Temporal Affinity

In HPC applications, memory access behavior is one of the main factors affecting performance. Improving an application’s memory access behavior involves optimizing data layout and/or restructuring code, and requires studying spatial-temporal data locality. Existing data locality analyses focus on single-location metrics and are restricted to evaluating temporal locality. We introduce spatial-temporal affinity metrics that quantify temporal access proximity, forward access correlation, and nearby access correlation between pairs of memory locations. We describe methods for distinguishing between potential vs. realized affinity and for reasoning about affinity at multiple resolutions (3D, 2D, 1D). Finally, we construct spatial-temporal affinity signatures that classify memory behavior and that be used to reason about changes in software (data relayout, code refactoring) or hardware (caching, prefetching). We describe methods for signature visualization, interpretation, and quantitative comparison of signatures. We evaluate our methodology using applications with variants that contrast data structures, data layouts and algorithms. We show that spatial-temporal affinity analysis provides novel insights and enables predictive reasoning about application performance when contrasted with reuse distance analysis.

Suriyakumar, Yasodhadevi↗

Parallel Programming Models and Systems for High Performance Computing. In: Emerging Research in Cloud Distributed Computing Systems

A parallel programming model is an abstraction of a parallel system that allows expression of both algorithms and shared data structures. To accommodate the diversity in parallel system architectures and user requirements, there are a variety of programming models including the models providing a shared memory view or a distributed memory view of the system. The programming models are implemented as libraries, language extensions, or compiler directives. This chapter provides a discussion on programming models and its implementations aimed at application developers, system software researchers, and hardware architects. The first part provides an overview of the programming models. The second part is an in-depth discussion on high-performance networking interface to implement the programming model. The last part of the chapter discusses implementation of a programming model with a case study. Each part of the chapter concludes with a discussion on current research trends and its impact on future architectures.

Venkata, Manjunath Gorentia↗

Unstructured mesh methods for CFD

Mesh generation methods for Computational Fluid Dynamics (CFD) are outlined. Geometric modeling is discussed. An advancing front method is described. Flow past a two engine Falcon aeroplane is studied. An algorithm and associated data structure called the alternating digital tree, which efficiently solves the geometric searching problem is described. The computation of an initial approximation to the steady state solution of a given poblem is described. Mesh generation for transient flows is described.

Peraire, J.↗

Object-Oriented Design for Sparse Direct Solvers

We discuss the object-oriented design of a software package for solving sparse, symmetric systems of equations (positive definite and indefinite) by direct methods. At the highest layers, we decouple data structure classes from algorithmic classes for flexibility. We describe the important structural and algorithmic classes in our design, and discuss the trade-offs we made for high performance. The kernels at the lower layers were optimized by hand. Our results show no performance loss from our object-oriented design, while providing flexibility, case of use, and extensibility over solvers using procedural design.

Dobrian, Florin↗

Fast Particle Methods for Multiscale Phenomena Simulations

We are developing particle methods oriented at improving computational modeling capabilities of multiscale physical phenomena in : (i) high Reynolds number unsteady vortical flows, (ii) particle laden and interfacial flows, (iii)molecular dynamics studies of nanoscale droplets and studies of the structure, functions, and evolution of the earliest living cell. The unifying computational approach involves particle methods implemented in parallel computer architectures. The inherent adaptivity, robustness and efficiency of particle methods makes them a multidisciplinary computational tool capable of bridging the gap of micro-scale and continuum flow simulations. Using efficient tree data structures, multipole expansion algorithms, and improved particle-grid interpolation, particle methods allow for simulations using millions of computational elements, making possible the resolution of a wide range of length and time scales of these important physical phenomena.The current challenges in these simulations are in : [i] the proper formulation of particle methods in the molecular and continuous level for the discretization of the governing equations [ii] the resolution of the wide range of time and length scales governing the phenomena under investigation. [iii] the minimization of numerical artifacts that may interfere with the physics of the systems under consideration. [iv] the parallelization of processes such as tree traversal and grid-particle interpolations We are conducting simulations using vortex methods, molecular dynamics and smooth particle hydrodynamics, exploiting their unifying concepts such as : the solution of the N-body problem in parallel computers, highly accurate particle-particle and grid-particle interpolations, parallel FFT's and the formulation of processes such as diffusion in the context of particle methods. This approach enables us to transcend among seemingly unrelated areas of research.

Koumoutsakos, P.↗

A PARALLEL MONTE CARLO CODE FOR SIMULATING COLLISIONAL N-BODY SYSTEMS

We present a new parallel code for computing the dynamical evolution of collisional N-body systems with up to N {approx} 10{sup 7} particles. Our code is based on the Henon Monte Carlo method for solving the Fokker-Planck equation, and makes assumptions of spherical symmetry and dynamical equilibrium. The principal algorithmic developments involve optimizing data structures and the introduction of a parallel random number generation scheme as well as a parallel sorting algorithm required to find nearest neighbors for interactions and to compute the gravitational potential. The new algorithms we introduce along with our choice of decomposition scheme minimize communication costs and ensure optimal distribution of data and workload among the processing units. Our implementation uses the Message Passing Interface library for communication, which makes it portable to many different supercomputing architectures. We validate the code by calculating the evolution of clusters with initial Plummer distribution functions up to core collapse with the number of stars, N, spanning three orders of magnitude from 10{sup 5} to 10{sup 7}. We find that our results are in good agreement with self-similar core-collapse solutions, and the core-collapse times generally agree with expectations from the literature. Also, we observe good total energy conservation, within {approx}< 0.04% throughout all simulations. We analyze the performance of the code, and demonstrate near-linear scaling of the runtime with the number of processors up to 64 processors for N = 10{sup 5}, 128 for N = 10{sup 6} and 256 for N = 10{sup 7}. The runtime reaches saturation with the addition of processors beyond these limits, which is a characteristic of the parallel sorting algorithm. The resulting maximum speedups we achieve are approximately 60 Multiplication-Sign , 100 Multiplication-Sign , and 220 Multiplication-Sign , respectively.

79 ASTRONOMY AND ASTROPHYSICS↗

Correlated Anion Disorder in Heteroanionic Cubic TiOF 2

Resolving anion configurations in heteroanionic materials is crucial for understanding and controlling their properties. For anion-disordered oxyfluorides, conventional Bragg diffraction cannot fully resolve the anionic structure, necessitating alternative structure determination methods. We have investigated the anionic structure of anion-disordered cubic (ReO 3 -type) TiOF 2 using X-ray pair distribution function (PDF), 19 F MAS NMR analysis, density functional theory (DFT), cluster expansion modeling, and genetic-algorithm structure prediction. Our computational data predict short-range anion ordering in TiOF 2 , characterized by predominant cis-[O 2 F 4 ] titanium coordination, resulting in correlated anion disorder at longer ranges. To validate our predictions, we generated partially disordered supercells using genetic-algorithm structure prediction and computed simulated X-ray PDF data and 19 F MAS NMR spectra, which we compared directly to experimental data. To construct our simulated 19 F NMR spectra, we derived new transformation functions for mapping calculated magnetic shieldings to predicted magnetic chemical shifts in titanium (oxy)fluorides, obtained by fitting DFT-calculated magnetic shieldings to previously published experimental chemical shift data for TiF 4 . We find good agreement between our simulated and experimental data, which supports our computationally predicted structural model and demonstrates the effectiveness of complementary experimental and computational techniques in resolving anionic structure in anion-disordered oxyfluorides. From additional DFT calculations, we predict that increasing anion disorder makes lithium intercalation more favorable by, on average, up to 2 eV, highlighting the significant effect of variations in short-range order on the intercalation properties of anion-disordered materials.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

An affinity-structure database of helix-turn-helix: DNA complexes with a universal coordinate system

Molecular interactions between proteins and DNA molecules underlie many cellular processes, including transcriptional regulation, chromosome replication, and nucleosome positioning. Computational analyses of protein-DNA interactions rely on experimental data characterizing known protein-DNA interactions structurally and biochemically. While many databases exist that contain either structural or biochemical data, few integrate these two data sources in a unified fashion. Such integration is becoming increasingly critical with the rapid growth of structural and biochemical data, and the emergence of algorithms that rely on the synthesis of multiple data types to derive computational models of molecular interactions. We have developed an integrated affinity-structure database in which the experimental and quantitative DNA binding affinities of helix-turn-helix proteins are mapped onto the crystal structures of the corresponding protein-DNA complexes. This database provides access to: (i) protein-DNA structures, (ii) quantitative summaries of protein-DNA binding affinities using position weight matrices, and (iii) raw experimental data of protein-DNA binding instances. Critically, this database establishes a correspondence between experimental structural data and quantitative binding affinity data at the single basepair level. Furthermore, we present a novel alignment algorithm that structurally aligns the protein-DNA complexes in the database and creates a unified residue-level coordinate system for comparing the physico-chemical environments at the interface between complexes. Using this unified coordinate system, we compute the statistics of atomic interactions at the protein-DNA interface of helix-turn-helix proteins. We provide an interactive website for visualization, querying, and analyzing this database, and a downloadable version to facilitate programmatic analysis. Lastly, this database will facilitate the analysis of protein-DNA interactions and the development of programmatic computational methods that capitalize on integration of structural and biochemical datasets. The database can be accessed at http://ProteinDNA.hms.harvard.edu.

59 BASIC BIOLOGICAL SCIENCES↗

GBS 1.0

The Umbra gbs (Graph-Based Search) library provides implementations of graph-based search/planning algorithms that can be applied to legacy graph data structures. Unlike some other graph algorithm libraries, this one does not require your graph class to inherit from a specific base class. Implementations of Dijkstra's Algorithm and A-Star search are included and can be used with graphs that are lazily-constructed.

Source record↗

Algorithms and file structures to extend and enhance liquid chromatography and ion mobility mass spectrometry workflows (CRADA Final Report)

The purpose of this project was to continue supporting customizations of algorithms and raw data file structures to enhance software workflows for liquid chromatography (LC), mass spectrometry (MS) and ion mobility mass spectrometry (IM-MS)-based protein and metabolite characterization. PNNL worked with Agilent to design, implement, evaluate, and demonstrate new algorithms and integrated them as functionalities into the PNNL-PreProcessor software. The project augmented PNNL’s capabilities to analyze complex proteomics and metabolomics samples. These capabilities are directly beneficial to DOE and PNNL efforts to characterize and analyze these compounds in microbial and plant communities. The project assisted Agilent in further developing improved instrument-software solutions combining liquid chromatography and ion mobility with mass spectrometry for widespread applications in life sciences and other fields.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Multiple-Instance Regression with Structured Data

We present a multiple-instance regression algorithm that models internal bag structure to identify the items most relevant to the bag labels. Multiple-instance regression (MIR) operates on a set of bags with real-valued labels, each containing a set of unlabeled items, in which the relevance of each item to its bag label is unknown. The goal is to predict the labels of new bags from their contents. Unlike previous MIR methods, MI-ClusterRegress can operate on bags that are structured in that they contain items drawn from a number of distinct (but unknown) distributions. MI-ClusterRegress simultaneously learns a model of the bag's internal structure, the relevance of each item, and a regression model that accurately predicts labels for new bags. We evaluated this approach on the challenging MIR problem of crop yield prediction from remote sensing data. MI-ClusterRegress provided predictions that were more accurate than those obtained with non-multiple-instance approaches or MIR methods that do not model the bag structure.

learning↗

Algorithms and file structures to enhance software workflows for ion mobility mass spectrometry (IM-MS)

Support customizations of algorithms and raw data file structures to enhance software workflows for liquid chromatography (LC), mass spectrometry (MS) and ion mobility mass spectrometry (IM-MS)-based metabolite characterization. Evaluate and improve the integration of ion mobility to existing MS analysis methods of the Mass Profiler Professional workflow (Mass Profiler, ID Browser and Mass Profiler Professional).

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

Discrete Data Transfer Technique for Fluid-Structure Interaction

This paper presents a general three-dimensional algorithm for data transfer between dissimilar meshes. The algorithm is suitable for applications of fluid-structure interaction and other high-fidelity multidisciplinary analysis and optimization. Because the algorithm is independent of the mesh topology, we can treat structured and unstructured meshes in the same manner. The algorithm is fast and accurate for transfer of scalar or vector fields between dissimilar surface meshes. The algorithm is also applicable for the integration of a scalar field (e.g., coefficients of pressure) on one mesh and injection of the resulting vectors (e.g., force vectors) onto another mesh. The author has implemented the algorithm in a C++ computer code. This paper contains a complete formulation of the algorithm with a few selected results.

Samareh, Jamshid A.↗

Some practicable applications of quadtree data structures/representation in astronomy

Development of quadtree as hierarchical data structuring technique for representing spatial data (like points, regions, surfaces, lines, curves, volumes, etc.) has been motivated to a large extent by storage requirements of images, maps, and other multidimensional (spatially structured) data. For many spatial algorithms, time-efficiency of quadtrees in terms of execution may be as important as their space-efficiency concerning storage conditions. Briefly, the quadtree is a class of hierarchical data structures which is based on the recursive partition of a square region into quadrants and sub-quadrants until a predefined limit. Beyond the wide applicability of quadtrees in image processing, spatial information analysis, and building digital databases (processes becoming ordinary for the astronomical community), there may be numerous further applications in astronomy. Some of these practicable applications based on quadtree representation of astronomical data are presented and suggested for further considerations. Examples are shown for use of point as well as region quadtrees. Statistics of different leaf and non-leaf nodes (homogeneous and heterogeneous sub-quadrants respectively) at different levels may provide useful information on spatial structure of astronomical data in question. By altering the principle guiding the decomposition process, different types of spatial data may be focused on. Finally, a sampling method based on quadtree representation of an image is proposed which may prove to be efficient in the elaboration of sampling strategy in a region where observations were carried out previously either with different resolution or/and in different bands.

Pasztor, L.↗

Algorithms and file structures to enhance software workflows for ion mobility mass spectrometry (IM-MS): CRADA 410 (Final Report)

This document is the final report for CRADA 410 (Project No. 72496). The purpose of this project was supporting customizations of algorithms and raw data file structures to enhance software workflows for liquid chromatography (LC), mass spectrometry (MS) and ion mobility mass spectrometry (IM-MS)-based metabolite characterization. PNNL worked with Agilent to evaluate and improve the integration of ion mobility into existing MS data analysis methods of Agilent software tools. The project augmented PNNL’s capabilities to analyze complex omics samples. These capabilities are directly beneficial to DOE and PNNL efforts to characterize and analyze compounds in microbial and plant communities. The project assisted Agilent in further developing improved instrument-software solutions combining ion mobility with mass spectrometry for widespread applications in life sciences and other fields.

97 MATHEMATICS AND COMPUTING↗