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 91 records · Page 5

System and method of storing and analyzing information

A system and method of storing and analyzing information is disclosed. The system includes a compiler layer to convert user queries to data parallel executable code. The system further includes a library of multithreaded algorithms, processes, and data structures. The system also includes a multithreaded runtime library for implementing compiled code at runtime. The executable code is dynamically loaded on computing elements and contains calls to the library of multithreaded algorithms, processes, and data structures and the multithreaded runtime library.

97 MATHEMATICS AND COMPUTING↗

System and method of storing and analyzing information

A system and method of storing and analyzing information is disclosed. The system includes a compiler layer to convert user queries to data parallel executable code. The system further includes a library of multithreaded algorithms, processes, and data structures. The system also includes a multithreaded runtime library for implementing compiled code at runtime. The executable code is dynamically loaded on computing elements and contains calls to the library of multithreaded algorithms, processes, and data structures and the multithreaded runtime library.

Feo, John T.↗

Experiences with string matching on the Fermi Architecture

String matching is at the core of many real-world applications, such as security, bioinformatic, data mining. All these applications requires the ability to match always growing data sets against large dictionaries effectively, fastly and possibly in real time. Unfortunately, string matching is a computationally intensive procedure which poses significant challenges on current software and hardware implementations. Graphic Processing Units (GPU) have become an interesting target for such high-throughput applications, but the algorithms and the data structures need to be redesigned to be parallelized and adapted to the underlining hardware, coping with the limitations imposed by these architectures. In this paper we present an efficient implementation of the Aho-Corasick string matching algorithm on GPU, showing how we progressively redesigned the algorithm and the data structures to fit on the architecture. We then evaluate the implementation on single and multiple Tesla C2050 (T20 ``Fermi'' based) boards, comparing them to the previous Tesla C1060 (T10 based) solutions and equivalent multicore implementations on x86 CPUs. We discuss the various tradeoffs of the different architectures.

99 GENERAL AND MISCELLANEOUS↗

Calculating the grain boundary inclination of voxelated grain structures using a smoothing algorithm

We have developed a flexible method for calculating the grain boundary (GB) inclinations of voxelated grain structure data using smoothing algorithms. We compared the performance of four algorithms: the linear interpolation, Allen–Cahn, level-set, and vertex algorithms. We assessed their accuracy using 2D and 3D cases with known inclinations. The vertex algorithm provided the best balance between accuracy and efficiency for 2D structures while the linear interpolation algorithm provided the best balance for 3D structures. We compared the GB inclinations calculated using our smoothing method on a 3D high energy X-ray diffraction microscopy (HEDM) dataset to those determined by meshing the GBs. The two approaches determined similar GB plane distributions, though they varied significantly at triple junctions. In conclusion, the smoothing method was demonstrated for two sources of 3D voxelated grain structures: HEDM data and results from Monte Carlo Potts grain growth simulations.

36 MATERIALS SCIENCE↗

Assembly planning for large truss structures in space

The approach is based on a graph search algorithm. A relational data structure is used to represent a truss structure. There are four types of entities: units, faces, edges, and vertices. There are contain/contained relationships for every pair of entity types, as well as in-contact relationships between faces. A best-first algorithm constitutes the core of the planner. The cost function in the current implementation corresponds to a combination of the rigidity of the intermediate structures and the total distance to be traversed by the agent executing the assembly tasks.

Homem De Mello, L. S.↗

Structural algorithm to reservoir reconstruction using passive seismic data (synthetic example)

Using of passive seismic observations to detect a reservoir is a new direction of prospecting and exploration of hydrocarbons. In order to identify thin reservoir model we applied the modification of Gaussian elimination method in conditions of incomplete synthetic data. Because of the singularity of a matrix conventional method does not work. Therefore structural algorithm has been developed by analyzing the given model as a complex model. Numerical results demonstrate of its advantage compared with usual way of solution. We conclude that the gas reservoir is reconstructed by retrieving of the image of encasing shale beneath it.

58 GEOSCIENCES↗

A real-time robot arm collision avoidance system

A data structure and update algorithm are presented for a prototype real-time collision avoidance safety system simulating a multirobot workspace. The data structure is a variant of the octree, which serves as a spatial index. An octree recursively decomposes 3D space into eight equal cubic octants until each octant meets some decomposition criteria. The N-objects octree, which indexes a collection of 3D primitive solids is used. These primitives make up the two (seven-degrees-of-freedom) robot arms and workspace modeled by the system. As robot arms move, the octree is updated to reflect their changed positions. During most update cycles, any given primitive does not change which octree nodes it is in. Thus, modification to the octree is rarely required. Cycle time for interpreting current arm joint angles, updating the octree to reflect new positions, and detecting/reporting imminent collisions averages 30 ms on an Intel 80386 processor running at 20 MHz.

Shaffer, Clifford A.↗

A real-time robot arm collision detection system

A data structure and update algorithm are presented for a prototype real time collision detection safety system for a multi-robot environment. The data structure is a variant of the octree, which serves as a spatial index. An octree recursively decomposes 3-D space into eight equal cubic octants until each octant meets some decomposition criteria. The octree stores cylspheres (cylinders with spheres on each end) and rectangular solids as primitives (other primitives can easily be added as required). These primitives make up the two seven degrees-of-freedom robot arms and environment modeled by the system. Octree nodes containing more than a predetermined number N of primitives are decomposed. This rule keeps the octree small, as the entire environment for the application can be modeled using a few dozen primitives. As robot arms move, the octree is updated to reflect their changed positions. During most update cycles, any given primitive does not change which octree nodes it is in. Thus, modification to the octree is rarely required. Incidents in which one robot arm comes too close to another arm or an object are reported. Cycle time for interpreting current joint angles, updating the octree, and detecting/reporting imminent collisions averages 30 milliseconds on an Intel 80386 processor running at 20 MHz.

Shaffer, Clifford A.↗

Parallel processors and nonlinear structural dynamics algorithms and software

The adaptation of a finite element program with explicit time integration to a massively parallel SIMD (single instruction multiple data) computer, the CONNECTION Machine is described. The adaptation required the development of a new algorithm, called the exchange algorithm, in which all nodal variables are allocated to the element with an exchange of nodal forces at each time step. The architectural and C* programming language features of the CONNECTION Machine are also summarized. Various alternate data structures and associated algorithms for nonlinear finite element analysis are discussed and compared. Results are presented which demonstrate that the CONNECTION Machine is capable of outperforming the CRAY XMP/14.

Belytschko, Ted↗

ECP Milestone Report WBS 2.3.4.13 ECP/VTK-m FY18Q1 [MS-18/01-03] Multiblock / Gradients / Release STDA05-5.

The FY18Q1 milestone of the ECP/VTK-m project includes the implementation of a multiblock data set, the completion of a gradients filtering operation, and the release of version 1.1 of the VTK-m software. With the completion of this milestone, the new multiblock data set allows us to iteratively schedule algorithms on composite data structures such as assemblies or hierarchies like AMR. The new gradient algorithms approximate derivatives of fields in 3D structures with finite differences. Finally, the release of VTK-m version 1.1 tags a stable release of the software that can more easily be incorporated into external projects.

97 MATHEMATICS AND COMPUTING↗

Mesh-free data transfer algorithms for partitioned multiphysics problems: Conservation, accuracy, and parallelism

In this study we analyze and extend mesh-free algorithms for three-dimensional data transfer problems in partitioned multiphysics simulations. We first provide a direct comparison between a mesh-based weighted residual method using the common-refinement scheme and two mesh-free algorithms leveraging compactly supported radial basis functions: one using a spline interpolation and one using a moving least square reconstruction. Through the comparison we assess both the conservation and accuracy of the data transfer obtained from each of the methods. We do so for a varying set of geometries with and without curvature and sharp features and for functions with and without smoothness and with varying gradients. Our results show that the mesh-based and mesh-free algorithms are complementary with cases where each was demonstrated to perform better than the other. We then focus on the mesh-free methods by developing a set of algorithms to parallelize them based on sparse linear algebra techniques. This includes a discussion of fast parallel radius searching in point clouds and restructuring the interpolation algorithms to leverage data structures and linear algebra services designed for large distributed computing environments. The scalability of our new algorithms is demonstrated on a leadership class computing facility using a set of basic scaling studies. Finally, these scaling studies show that for problems with reasonable load balance, our new algorithms for both spline interpolation and moving least square reconstruction demonstrate both strong and weak scalability using more than 100,000 MPI processes with billions of degrees of freedom in the data transfer operation.

97 MATHEMATICS AND COMPUTING↗

Direct structural retrieval from gas-phase ultrafast diffraction data using a genetic algorithm

Ultrafast scattering techniques such as ultrafast electron diffraction and ultrafast x-ray diffraction have been utilized to elucidate the structural dynamics, reaction intermediates, and final products in molecular reactions following photoexcitation. The time-dependent structures are typically not directly retrieved from the experimental data, but they rely on comparison with calculations. The genetic algorithm (GA), a global optimization strategy, can be used to retrieve the molecular structures directly from diffraction patterns without any theoretical input. However, the robustness of the GA with respect to real experimental conditions such as a limited momentum transfer range, noise, and artifacts has not been studied in detail. In this work, we characterize the performance of the GA with simulated data that mimic realistic experimental conditions. We have developed and implemented a variant of the GA specific to diffraction measurements which performs better in the presence of imperfect data compared to the standard implementation of the GA. We demonstrate this method with both synthetic data and experimental ultrafast electron diffraction data on the UV-induced photodissociation of trifluoroiodomethane (C⁢F 3⁡ I) molecules.

74 ATOMIC AND MOLECULAR PHYSICS↗

FLUT - A program for aeroelastic stability analysis

A computer program (FLUT) that can be used to evaluate the aeroelastic stability of aircraft structures in subsonic flow is described. The algorithm synthesizes data from a structural vibration analysis with an unsteady aerodynamics analysis and then performs a complex eigenvalue analysis to assess the system stability. The theoretical basis of the program is discussed with special emphasis placed on some innovative techniques which improve the efficiency of the analysis. User information needed to efficiently and successfully utilize the program is provided. In addition to identifying the required input, the flow of the program execution and some possible sources of difficulty are included. The use of the program is demonstrated with a listing of the input and output for a simple example.

Johnson, E. H.↗

Cabana: A Performance Portable Library for Particle-Based Simulations

Particle-based simulations are ubiquitous throughout many fields of computational science and engineering, spanning the atomistic level with molecular dynamics (MD), to mesoscale particle-in-cell (PIC) simulations for solid mechanics, device-scale modeling with PIC methods for plasma physics, and massive N-body cosmology simulations of galaxy structures, with many other methods in between (Hockney & Eastwood, 1989). While these methods use particles to represent significantly different entities with completely different physical models, many low-level details are shared including performant algorithms for short- and/or long-range particle interactions, multi-node particle communication patterns, and other data management tasks such as particle sorting and neighbor list construction. Cabana is a performance portable library for particle-based simulations, developed as part of the Co-Design Center for Particle Applications (CoPA) within the Exascale Computing Project (ECP) (Alexander et al., 2020). The CoPA project and its full development scope, including ECP partner applications, algorithm development, and similar software libraries for quantum MD, is described in (Mniszewski et al., 2021). Cabana uses the Kokkos library for on-node parallelism (Edwards et al., 2014; Trott et al., 2022), enabling simulation on multi-core CPU and GPU architectures, and MPI for GPU-aware, multi-node communication. Cabana provides particle simulation capabilities on almost all current Kokkos backends, including serial execution, OpenMP (including OpenMP-Target for GPUs), CUDA (NVIDIA GPUs), HIP (AMD GPUs), and SYCL (Intel GPUs), providing a clear path for the coming generation of accelerator-based exascale hardware. Cabana builds on Kokkos by providing new particle data structures and particle algorithms resulting in a similar execution policy-based, node-level programming model that is intended to be used in addition to the core Kokkos library within an application. Cabana is designed as an application and physics agnostic, but particle-specific toolkit which can either be used to generate a new application, or to be used as needed in existing applications at various levels of invasiveness including through interfaces that wrap user memory in existing data structures.

97 MATHEMATICS AND COMPUTING↗

An efficient and portable SIMD algorithm for charge/current deposition in Particle-In-Cell codes

In current computer architectures, data movement (from die to network) is by far the most energy consuming part of an algorithm (≈20pJ/word on-die to ≈10,000 pJ/word on the network). To increase memory locality at the hardware level and reduce energy consumption related to data movement, future exascale computers tend to use many-core processors on each compute nodes that will have a reduced clock speed to allow for efficient cooling. To compensate for frequency decrease, machine vendors are making use of long SIMD instruction registers that are able to process multiple data with one arithmetic operator in one clock cycle. SIMD register length is expected to double every four years. As a consequence, Particle-In-Cell (PIC) codes will have to achieve good vectorization to fully take advantage of these upcoming architectures. In this paper, we present a new algorithm that allows for efficient and portable SIMD vectorization of current/charge deposition routines that are, along with the field gathering routines, among the most time consuming parts of the PIC algorithm. Our new algorithm uses a particular data structure that takes into account memory alignment constraints and avoids gather/scat;ter instructions that can significantly affect vectorization performances on current CPUs. The new algorithm was successfully implemented in the 3D skeleton PIC code PICSAR and tested on Haswell Xeon processors (AVX2-256 bits wide data registers). Results show a factor of ×2 to ×2.5 speed-up in double precision for particle shape factor of orders 1–3. The new algorithm can be applied as is on future KNL (Knights Landing) architectures that will include AVX-512 instruction sets with 512 bits register lengths (8 doubles/16 singles). Program summary Program Title: vec_deposition Program Files doi:http://dx.doi.org/10.17632/nh77fv9k8c.1 Licensing provisions: BSD 3-Clause Programming language: Fortran 90 External routines/libraries: OpenMP > 4.0 Nature of problem: Exascale architectures will have many-core processors per node with long vector data registers capable of performing one single instruction on multiple data during one clock cycle. Data register lengths are expected to double every four years and this pushes for new portable solutions for efficiently vectorizing Particle-In-Cell codes on these future many-core architectures. One of the main hotspot routines of the PIC algorithm is the current/charge deposition for which there is no efficient and portable vector algorithm. Solution method: Here we provide an efficient and portable vector algorithm of current/charge deposition routines that uses a new data structure, which significantly reduces gather/scatter operations. Vectorization is controlled using OpenMP 4.0 compiler directives for vectorization which ensures portability across different architectures. Restrictions: Here we do not provide the full PIC algorithm with an executable but only vector routines for current/charge deposition. These scalar/vector routines can be used as library routines in your 3D Particle-In-Cell code. However, to get the best performances out of vector routines you have to satisfy the two following requirements: (1) Your code should implement particle tiling (as explained in the manuscript) to allow for maximized cache reuse and reduce memory accesses that can hinder vector performances. The routines can be used directly on each particle tile. (2) You should compile your code with a Fortran 90 compiler (e.g Intel, gnu or cray) and provide proper alignment flags and compiler alignment directives (more details in README file).

97 MATHEMATICS AND COMPUTING↗

Global parallel unification for large question-answering systems

An efficient means of storing data in a first-order predicate calculus theorem-proving system is described. The data structure is oriented for large scale question-answering (QA) systems. An algorithm is outlined which uses the data structure to unify a given literal in parallel against all literals in all clauses in the data base. The data structure permits a compact representation of data within a QA system. Some suggestions are made for heuristics which can be used to speed-up the unification algorithm in systems.

Auguston, J. G.↗

Aspherical particle models for molecular dynamics simulation

In traditional molecular dynamics (MD) simulations, atoms and coarse-grained particles are modeled as point masses interacting via isotropic potentials. For studies where particle shape plays a vital role, more complex models are required. Here, we describe a spectrum of approaches for modeling aspherical particles, all of which are now available (some recently) as options within the LAMMPS MD package. Broadly these include two classes of models. In the first, individual particles are aspherical, either via a pairwise anisotropic potential which implicitly assigns a simple geometric shape to each particle, or in a more general way where particles store internal state which can explicitly define a complex geometric shape. In the second class of models, individual particles are simple points or spheres, but rigid body constraints are used to create composite aspherical particles in a variety of complex shapes. This work discusses parallel algorithms and associated data structures for both kinds of models, which enable dynamics simulations of aspherical particle systems across a wide range of length and time scales. We also highlight parallel performance and scalability and give a few illustrative examples of aspherical models in different contexts.

74 ATOMIC AND MOLECULAR PHYSICS↗

Towards Superior Software Portability with SHAD and HPX C++ Libraries

As hardware architectures and software stacks complexity grows, development productivity, performance and software portability, quickly evolve from desirable features to actual needs. SHAD, the Scalable High-performance Algorithms and Data-structures C++ library is designed to mitigate these issues: it provides general purpose building blocks as well as high-level custom utilities, and offers a shared-memory programming abstraction which facilitates the programming of complex systems, scaling up to High Performance Computing clusters. SHAD’s portability is achieved through an abstract runtime interface, which decouples the upper layers of the library and hides the low level details of the underlying architecture. This layer enables SHAD to interface with different runtime/threading systems, e.g. Intel TBB and Global Memory and Threading (GMT). However, current backends targeting distributed systems, rely on a centralized controller which may possibly limit scalability up to hundreds of nodes and creates a network hot spot due to all to one communication for synchronization, and possibly resulting in degraded performance at high process counts. In this research, we explore HPX, the C++ standard library for parallelism and concurrency, as an additional backend in support of the SHAD library, and present the methodologies in support of local and remote task executions in SHAD with respect to HPX. Finally, we evaluate the proposed system by comparing against existing backends of SHAD and analyzing their performance on C++ Standard Template Library algorithms.

Wu, Nanmiao↗