SEARCH · Engineering Papers

Results for “Data Structures and Algorithms”

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.

SourceResearch connectionFrom yearThrough year

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

At least 37 records · Page 2

All sources NASA NTRS DOE OSTI

DOE OSTI2021

PUMIPic: A mesh-based approach to unstructured mesh Particle-In-Cell on GPUs

Unstructured mesh particle-in-cell, PIC, simulations executing on the current and next generation of massively parallel systems require new methods for both the mesh and particles to achieve performance and scalability on GPUs. The traditional approach to implementing PIC simulations defines data structures and algorithms in terms of particles with a full copy of the unstructured mesh on every process. To effectively scale the unstructured mesh and particles, mesh-based PIC uses the unstructured mesh as the predominant data structure with the particles stored in terms of the mesh entities. Here, this paper details the PUMIPic library, a framework for developing efficient and performance-portable mesh-based PIC simulations on GPU systems. A pseudo physics simulation based on a five-dimensional gyro-kinetic code for modeling plasma physics is used to examine the performance of PUMIPic. Scaling studies of the unstructured mesh partition and number of particles are performed up to 4096 nodes of the Summit system at Oak Ridge National Laboratory. The studies show that mesh-based PIC can utilize a partitioned mesh and maintain scaling up to system limitations.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS1992

DecisionMaker software and extracting fuzzy rules under uncertainty

Knowledge acquisition under uncertainty is examined. Theories proposed in deKorvin's paper 'Extracting Fuzzy Rules Under Uncertainty and Measuring Definability Using Rough Sets' are discussed as they relate to rule calculation algorithms. A data structure for holding an arbitrary number of data fields is described. Limitations of Pascal for loops in the generation of combinations are also discussed. Finally, recursive algorithms for generating all possible combination of attributes and for calculating the intersection of an arbitrary number of fuzzy sets are presented.

Walker, Kevin B.↗

DOE OSTI2023

Extending PETSc's Composable Hierarchical Solvers (Final Technical Report)

This report documents research activities conducted at CU Boulder as part of Extending PETSc’s Composable Hierarchical Solvers, which has been part of a collaboration with Argonne National Laboratory (separate award). Our work has focused on performance-portable end-to-end GPU solvers demonstrated via exemplary applications in nonlinear fluid and structural mechanics. We describe advances in algorithmic composition and analysis in the context of these applications, but the implementations are fully documented and decoupled, and in use by other projects. We believe the vertical integration achieved through collaboration with ECP’s CEED and the PSAAP center at CU was necessary to take risks with data structures and algorithms.

42 ENGINEERING↗

NASA NTRS2011

TPSAS-NF1676L-12354-DND

This work deals with performance properties of a dynamic traffic model, the Air Traffic Monotonic Lagrangian Grid (ATMLG), which can be used to evaluate new control strategies for conflict avoidance, separation assurance, and traffic management. The model is based on an algorithm and data structure called the Monotonic Lagrangian Grid (MLG), originally developed at NRL in the mid 1980s and since then used as an underpinning for various particle dynamics simulations. The MLG stores positions and other data needed to describe N moving objects, where N can be very large. The MLG algorithm involves sorting and ordering objects. A stationary grid is an alternative to the dynamic grid of MLG. Stationary grids can be attractive in that they do not require sorting. We investigate and report on the relative performances of air traffic simulations based on dynamic (MLG) and static (lat-long) grids.

C Kaplan↗

NASA NTRS2011

TPSAS-NF1676L-12301-DND

Carolyn Kaplan↗

NASA NTRS1992

The explicit computation of integration algorithms and first integrals for ordinary differential equations with polynomials coefficients using trees

This note is concerned with the explicit symbolic computation of expressions involving differential operators and their actions on functions. The derivation of specialized numerical algorithms, the explicit symbolic computation of integrals of motion, and the explicit computation of normal forms for nonlinear systems all require such computations. More precisely, if R = k(x(sub 1),...,x(sub N)), where k = R or C, F denotes a differential operator with coefficients from R, and g member of R, we describe data structures and algorithms for efficiently computing g. The basic idea is to impose a multiplicative structure on the vector space with basis the set of finite rooted trees and whose nodes are labeled with the coefficients of the differential operators. Cancellations of two trees with r + 1 nodes translates into cancellation of O(N(exp r)) expressions involving the coefficient functions and their derivatives.

Crouch, P. E.↗

DOE OSTI2020

Tracktable

Tracktable is a toolkit for analysis and visualization of the trajectories of moving objects. Its main focus is on air and sea traffic. It can also work with more abstract trajectories such as eye tracking data. We supply a set of core data structures, input/output routines, math and machine learning algorithms that operate on those data structures, and visualization algorithms to produce movies and still images of the results.

Wilson, Andrew↗

NASA NTRS1990

SIAM Conference on Parallel Processing for Scientific Computing, 4th, Chicago, IL, Dec. 11-13, 1989, Proceedings

Attention is given to such topics as an evaluation of block algorithm variants in LAPACK and presents a large-grain parallel sparse system solver, a multiprocessor method for the solution of the generalized Eigenvalue problem on an interval, and a parallel QR algorithm for iterative subspace methods on the CM2. A discussion of numerical methods includes the topics of asynchronous numerical solutions of PDEs on parallel computers, parallel homotopy curve tracking on a hypercube, and solving Navier-Stokes equations on the Cedar Multi-Cluster system. A section on differential equations includes a discussion of a six-color procedure for the parallel solution of elliptic systems using the finite quadtree structure, data parallel algorithms for the finite element method, and domain decomposition methods in aerodynamics. Topics dealing with massively parallel computing include hypercube vs. 2-dimensional meshes and massively parallel computation of conservation laws. Performance and tools are also discussed.

Dongarra, Jack↗

DOE OSTI2022

MemGaze: Rapid and Effective Load-Level Memory Trace Analysis

A major challenge of memory analysis tools is combining high-resolution analysis and low overhead measurement. Currently, hardware/software-based analysis of load-level sequences incurs time slowdowns of O(100×). We present MemGaze, a tool for low-overhead, high-resolution memory analysis. MemGaze uses Intel’s Processor Tracing (PT) instruction ptwrite to collect sampled and compressed memory address traces for load-level, sequence-aware analysis of data reuse. We describe multi-resolution analysis for locations vs. operations, accesses vs. spatio-temporal reuse, and reuse (distance, rate, volume) vs. access patterns. Both trace size and resolution are controllable. We use MemGaze to elucidate the memory effects of different data structures and algorithms. For sampled traces that are ˜1% of a full one, analysis metrics have 1-25% MAPE for histograms of varying dynamic sequence lengths. With current suboptimal kernel support (PT runs continuously), MemGaze’s time overhead is typically 10–95%; 7× at worst. However, when PT runs only during samples, overhead is 10–35% on memory intensive regions and correlates with executed ptwrites.

Kilic, Ozgur O.↗

DOE OSTI2022

MetallData

MetallData is an HPC platform for interactive data science applications at HPC-scales. It provides an ecosystem for persistent distributed data structures, including algorithms, interactivity and storage.

Pearce, RogerA↗

DOE OSTI2026

Fortran mimetic abstraction language (Formal) v0.1.

The Fortran mimetic abstraction language ("Formal") is a domain-specific language (DSL) embedded in Fortran 202Y [1]. Formal provides novel software abstractions for simulating phenomena governed by the partial differential equations (PDEs) of vector and tensor calculus. Such equations model an extremely broad set of physical phenomena, ranging from atmospheric winds to light propagation. Formal's data structures and algorithms mimic in form and behavior continuous functions and operators. Formal supports these mathematical constructs using mimetic discretizations that define a discrete calculus satisfying various tensor calculus theorems, thereby ensuring high-fidelity representations of the physics being modeled. [2] Formal 0.1.0 also lays a foundation for the future use of Fortran 202Y type-safe templates to facilitate the formal verification of tensor contractions in computational physics and artificial intelligence [3]. [1] "Fortran 202Y" is Fortran standard committee's informal designation for the next Fortran revision, which will likely be "Fortran 2028". [2] Corbino, J. and Castillo, J. (2020) Journal of Computational and Applied Mathematics, https://doi.org/10.1016/j.cam.2019.06.042. [3] Haveraaen, M., Järvi, J., & Rouson, D. (2019). Reflecting on Generics for Fortran. https://j3-fortran.org/doc/year/19/19-188.pdf.

Rouson, Damian [Lawrence Berkeley National Laborat↗

DOE OSTI2021

Position Papers for the ASCR Workshop on the Science of Scientific-Software Development and Use

Software is an increasingly important component in the pursuit of scientific discovery. Both its development and use are essential activities for many scientific teams. At the same time, very little scientific study has been conducted to understand, characterize, and improve the development and use of software for science. Computational science teams have diversified over time to include contributions from domain scientists who provide expertise in scientific and engineering disciplines, applied mathematicians and computer scientists who provide optimal algorithms and data structures, and software and data engineers who provide methodologies and tools adapted and adopted from other software domains. These diverse contributions have enabled tremendous advances in the pursuit of scientific discovery, even as models, computer architectures, and software environments have become more complicated. With this increasing diversity, we believe the next opportunity for qualitative improvement comes from applying the scientific method to understanding, characterizing, and improving how scientific software is developed and used. We believe that this pursuit requires expertise from computational scientists themselves, and from the cognitive and social sciences as well as the software engineering research community. As we look to increase the productivity and sustainability of the scientific-software-development-and-use cycle, a more systematic application of the scientific method to understand processes for software development and use will be a valuable tool to guide future work and result in more usable and sustainable software. This workshop will bring together computer scientists, software engineering researchers, computational scientists, applied mathematicians, social scientists, cognitive scientists, and others, to explore how we can conduct such systematic investigations, what can be learned, and how doing so will benefit the scientific enterprise. The workshop will be structured around a set of breakout sessions, with every attendee expected to participate actively in the discussions. Afterward, workshop attendees — from DOE, industry, and academia — will produce a report for ASCR that summarizes the findings of the workshop.

42 ENGINEERING↗

NASA NTRS1989

Configuration space representation in parallel coordinates

By means of a system of parallel coordinates, a nonprojective mapping from R exp N to R squared is obtained for any positive integer N. In this way multivariate data and relations can be represented in the Euclidean plane (embedded in the projective plane). Basically, R squared with Cartesian coordinates is augmented by N parallel axes, one for each variable. The N joint variables of a robotic device can be represented graphically by using parallel coordinates. It is pointed out that some properties of the relation are better perceived visually from the parallel coordinate representation, and that new algorithms and data structures can be obtained from this representation. The main features of parallel coordinates are described, and an example is presented of their use for configuration space representation of a mechanical arm (where Cartesian coordinates cannot be used).

Fiorini, Paolo↗

NASA NTRS1993

Architecture-driven reuse of code in KASE

In order to support the synthesis of large, complex software systems, we need to focus on issues pertaining to the architectural design of a system in addition to algorithm and data structure design. An approach that is based on abstracting the architectural design of a set of problems in the form of a generic architecture, and providing tools that can be used to instantiate the generic architecture for specific problem instances is presented. Such an approach also facilitates reuse of code between different systems belonging to the same problem class. An application of our approach on a realistic problem is described; the results of the exercise are presented; and how our approach compares to other work in this area is discussed.

Bhansali, Sanjay↗

NASA NTRS1995

Distributed and collaborative synthetic environments

Fast graphics workstations and increased computing power, together with improved interface technologies, have created new and diverse possibilities for developing and interacting with synthetic environments. A synthetic environment system is generally characterized by input/output devices that constitute the interface between the human senses and the synthetic environment generated by the computer; and a computation system running a real-time simulation of the environment. A basic need of a synthetic environment system is that of giving the user a plausible reproduction of the visual aspect of the objects with which he is interacting. The goal of our Shastra research project is to provide a substrate of geometric data structures and algorithms which allow the distributed construction and modification of the environment, efficient querying of objects attributes, collaborative interaction with the environment, fast computation of collision detection and visibility information for efficient dynamic simulation and real-time scene display. In particular, we address the following issues: (1) A geometric framework for modeling and visualizing synthetic environments and interacting with them. We highlight the functions required for the geometric engine of a synthetic environment system. (2) A distribution and collaboration substrate that supports construction, modification, and interaction with synthetic environments on networked desktop machines.

Bajaj, Chandrajit L.↗

NASA NTRS2002

Memory-Intensive Benchmarks: IRAM vs. Cache-Based Machines

The increasing gap between processor and memory performance has lead to new architectural models for memory-intensive applications. In this paper, we explore the performance of a set of memory-intensive benchmarks and use them to compare the performance of conventional cache-based microprocessors to a mixed logic and DRAM processor called VIRAM. The benchmarks are based on problem statements, rather than specific implementations, and in each case we explore the fundamental hardware requirements of the problem, as well as alternative algorithms and data structures that can help expose fine-grained parallelism or simplify memory access patterns. The benchmarks are characterized by their memory access patterns, their basic control structures, and the ratio of computation to memory operation.

Biswas, Rupak↗

NASA NTRS2010

A Machine-Checked Proof of A State-Space Construction Algorithm

This paper presents the correctness proof of Saturation, an algorithm for generating state spaces of concurrent systems, implemented in the SMART tool. Unlike the Breadth First Search exploration algorithm, which is easy to understand and formalise, Saturation is a complex algorithm, employing a mutually-recursive pair of procedures that compute a series of non-trivial, nested local fixed points, corresponding to a chaotic fixed point strategy. A pencil-and-paper proof of Saturation exists, but a machine checked proof had never been attempted. The key element of the proof is the characterisation theorem of saturated nodes in decision diagrams, stating that a saturated node represents a set of states encoding a local fixed-point with respect to firing all events affecting only the node s level and levels below. For our purpose, we have employed the Prototype Verification System (PVS) for formalising the Saturation algorithm, its data structures, and for conducting the proofs.

Catano, Nestor↗

NASA NTRS2010

Multiscale Simulations of Magnetic Island Coalescence

We describe a new interactive parallel Adaptive Mesh Refinement (AMR) framework written in the Python programming language. This new framework, PyAMR, hides the details of parallel AMR data structures and algorithms (e.g., domain decomposition, grid partition, and inter-process communication), allowing the user to focus on the development of algorithms for advancing the solution of a systems of partial differential equations on a single uniform mesh. We demonstrate the use of PyAMR by simulating the pairwise coalescence of magnetic islands using the resistive Hall MHD equations. Techniques for coupling different physics models on different levels of the AMR grid hierarchy are discussed.

Dorelli, John C.↗