Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Parallel 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.

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

At least 1,549 records · Page 86
All sourcesNASA NTRSDOE OSTI
NASA NTRS2013

Monitoring and Acquisition Real-time System (MARS)

MARS is a graphical user interface (GUI) written in MATLAB and Java, allowing the user to configure and control the Scalable Parallel Architecture for Real-Time Acquisition and Analysis (SPARTAA) data acquisition system. SPARTAA not only acquires data, but also allows for complex algorithms to be applied to the acquired data in real time. The MARS client allows the user to set up and configure all settings regarding the data channels attached to the system, as well as have complete control over starting and stopping data acquisition. It provides a unique "Test" programming environment, allowing the user to create tests consisting of a series of alarms, each of which contains any number of data channels. Each alarm is configured with a particular algorithm, determining the type of processing that will be applied on each data channel and tested against a defined threshold. Tests can be uploaded to SPARTAA, thereby teaching it how to process the data. The uniqueness of MARS is in its capability to be adaptable easily to many test configurations. MARS sends and receives protocols via TCP/IP, which allows for quick integration into almost any test environment. The use of MATLAB and Java as the programming languages allows for developers to integrate the software across multiple operating platforms.

Holland, Corbin↗
NASA NTRS1994

Accelerated panel methods using the fast multipole method

Panel methods are commonly used in computational fluid dynamics for the solution of potential flow problems. The methods are a numerical technique based on the surface distribution of singularity elements. The solution is the process of finding the strength of the singularity elements distributed over the body's surface. This process involves the solution of the matrix problem Pq = p' for a set of unknowns q. The Fast Multipole Method is used to directly compute q without using matrix solvers. The algorithm works in O(N) time for N points, a great improvement over standard matrix solvers. In panel methods, the surface of a body is divided into a series of quadrilateral panels. The methods involve the computation of the influence of all other panels on each individual panel. The influence is based on the surface distribution, though this can be approximated by the area for distant panels. An alternative approximation, though with arbitrary accuracy, is to develop a multipole expansion about the center of the panel to describe the effect of a given panel on distant points in space. The expansion is based on the moments of the panel, thus allow the use of various surface distributions without changing the basic algorithm, just the computation of the various moments. The expansions are then manipulated in a tree walk to develop Taylor series expansions about a point in space which describe the effect of all distant panels on any point within a volume of convergence. The effect of near panels then needs to be computed directly, but the effect of all distant panels can be computed by simply evaluating the resulting expansion. The Fast Multipole Method has been applied to panel methods for the solution of source and doublet distributions. A major feature of the algorithm is that the algorithm does not change to derive the potential and velocity for sources and doublets. The same expansions can be used for both sources and doublets. Since the velocity is related to the potential, and the doublet potential is related to the z-component of the source velocity, all values can be derived from the same expansion by taking a series of partial derivatives. This requires more expansion terms to be kept since terms are lost in the process of taking partial derivatives. Thus to maintain accuracy for the doublet computation, more terms are required than if just evaluating for sources. The resulting Fast Multipole code should then parallelize better than classical panel methods due to the locality of data dependencies found in the Fast Multipole Method. Theoretically the parallelized code should execute in O(log N) time with O(N) processors, though this is not practical. Ongoing work includes implementing the parallel accelerated panel method, including methods to improve the load balancing of the problem by taking advantage of the known geometry of panels, and to encorporate sensitivity analysis into the algorithm.

Leathrum, James F., Jr.↗
DOE OSTI2023

ExTreeM: Scalable Augmented Merge Tree Computation via Extremum Graphs

Over the last decade merge trees have been proven to support a plethora of visualization and analysis tasks since they effectively abstract complex datasets. Here, this paper describes the ExTreeM-Algorithm: A scalable algorithm for the computation of merge trees via extremum graphs. The core idea of ExTreeM is to first derive the extremum graph G of an input scalar field f defined on a cell complex K, and subsequently compute the unaugmented merge tree of f on G instead of K; which are equivalent. Any merge tree algorithm can be carried out significantly faster on G, since K in general contains substantially more cells than G. To further speed up computation, ExTreeM includes a tailored procedure to derive merge trees of extremum graphs. The computation of the fully augmented merge tree, i.e., a merge tree domain segmentation of K, can then be performed in an optional post-processing step. All steps of ExTreeM consist of procedures with high parallel efficiency, and we provide a formal proof of its correctness. Our experiments, performed on publicly available datasets, report a speedup of up to one order of magnitude over the state-of-the-art algorithms included in the TTK and VTK-m software libraries, while also requiring significantly less memory and exhibiting excellent scaling behavior.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Plastic Parallel Pathways Platform - 4P Model

Global momentum is building towards a circular economy capable of keeping plastics in use and out of waste streams. Given that 79% of all plastic produced since 1950 has accumulated in landfills or the natural environment,rapid implementation of various end-of-life (EoL) management technologies will be needed to reach this target. However, it can be challenging to develop an effective plastic EoL strategy when the available options - chemical or molecular recycling, energy recovery, upcycling, downcycling, closed-loop (plastic-to-plastic) or open-loop (plastic-to-x) recycling, among others - can generate products ranging from low-grade to virgin-quality plastic and from fuels to value-added chemicals. We present a flexible material flow model capable of analyzing the effects of both plastic-to-plastic and plastic-to-x EoL management strategies on the U.S. PET economy. This Plastic Parallel Pathways Platform (4P) assesses the environmental impacts, costs, and circularity of a PET system in which waste is managed through six potential EoL pathways: landfill, incineration with energy recovery, pyrolysis to fuel oil, upcycling to glass fiber reinforced plastic (GFRP), mechanical recycling to low-grade PET, and chemical recycling (glycolysis) to bottle-grade PET. We compare the pathways across multiple metrics using multi-criteria decision analysis (MCDA) and then use a brute force algorithm to predict an optimal combination of EoL pathways to minimize greenhouse gas (GHG) emissions and costs and maximize circularity. This work highlights the need to implement a diverse portfolio of EoL strategies in parallel to enable a PET economy that meets environmental, economic, and circularity requirements simultaneously.

downcycling↗
DOE OSTI2022

Profiling the BLAST bioinformatics application for load balancing on high-performance computing clusters

Abstract Background The Basic Local Alignment Search Tool (BLAST) is a suite of commonly used algorithms for identifying matches between biological sequences. The user supplies a database file and query file of sequences for BLAST to find identical sequences between the two. The typical millions of database and query sequences make BLAST computationally challenging but also well suited for parallelization on high-performance computing clusters. The efficacy of parallelization depends on the data partitioning, where the optimal data partitioning relies on an accurate performance model. In previous studies, a BLAST job was sped up by 27 times by partitioning the database and query among thousands of processor nodes. However, the optimality of the partitioning method was not studied. Unlike BLAST performance models proposed in the literature that usually have problem size and hardware configuration as the only variables, the execution time of a BLAST job is a function of database size, query size, and hardware capability. In this work, the nucleotide BLAST application BLASTN was profiled using three methods: shell-level profiling with the Unix “time” command, code-level profiling with the built-in “profiler” module, and system-level profiling with the Unix “gprof” program. The runtimes were measured for six node types, using six different database files and 15 query files, on a heterogeneous HPC cluster with 500+ nodes. The empirical measurement data were fitted with quadratic functions to develop performance models that were used to guide the data parallelization for BLASTN jobs. Results Profiling results showed that BLASTN contains more than 34,500 different functions, but a single function, RunMTBySplitDB, takes 99.12% of the total runtime. Among its 53 child functions, five core functions were identified to make up 92.12% of the overall BLASTN runtime. Based on the performance models, static load balancing algorithms can be applied to the BLASTN input data to minimize the runtime of the longest job on an HPC cluster. Four test cases being run on homogeneous and heterogeneous clusters were tested. Experiment results showed that the runtime can be reduced by 81% on a homogeneous cluster and by 20% on a heterogeneous cluster by re-distributing the workload. Discussion Optimal data partitioning can improve BLASTN’s overall runtime 5.4-fold in comparison with dividing the database and query into the same number of fragments. The proposed methodology can be used in the other applications in the BLAST+ suite or any other application as long as source code is available.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2021

cuTS: Scaling Subgraph Isomorphism on Distributed Multi-GPUSystems Using Trie Based Data Structure

Subgraph isomorphism is a pattern-matching algorithm widely used in many domains such as chem-informatics, bioinformatics, databases, and social network analysis. It is computationally expensive and is a proven NP-hard problem. The massive parallelism offered by the GPU hardware is well suited for solving the subgraph isomorphism. However, current GPU implementations are far from the achievable performance. Moreover, the enormous memory requirement of current approaches limits the problem size that can be handled. This work analyzes the fundamental challenges associated with processing the subgraph isomorphism on GPUs and develops an efficient GPU hardware-aware implementation. We also develop a new GPU-friendly trie-based data structure to drastically reduce the intermediate storage space requirement. Hence, our approach runs larger benchmarks than the competitors. We also develop the first distributed sub-graph isomorphism algorithm for GPUs. Our experimental evaluation section demonstrates the efficacy of our approach by comparing the execution time and number of cases that we can handle against the state-of-the-art GPU implementations.

Xiang, Lizhi↗
DOE OSTI2026

Linear complexity

We present factorization and solution phases for a new linear complexity direct solver designed for concurrent batch operations on fine-grained parallel architectures, for matrices amenable to hierarchical representation. We focus on the strong-admissibility-based $\mathscr{H}^{2}$ format, where strong recursive skeletonization factorization compresses remote interactions. We build upon previous implementations of $\mathscr{H}^{2}$ matrix construction for efficient factorization and solution algorithm design, which are illustrated graphically in stepwise detail. The algorithms are ‘blackbox’ in the sense that the only inputs are the matrix and right-hand side, without analytical or geometrical information about the origin of the system. We demonstrate linear complexity scaling in both time and memory on four representative families of dense matrices up to one million in size. Parallel scaling up to 16 threads is enabled by a multi-level matrix graph coloring and avoidance of dynamic memory allocations thanks to prefix-sum memory management. An experimental backward error analysis is included. We break down the timings of different phases, identify phases that are memory-bandwidth limited, and discuss alternatives for phases that may be sensitive to the trend to employ lower precisions for performance.

Boukaram, Wajih↗
DOE OSTI2025

Fragme∩t: An Open‐Source Framework for Multiscale Quantum Chemistry Based on Fragmentation

Fragment-based quantum chemistry offers a means to circumvent the nonlinear computational scaling of conventional electronic structure calculations, by partitioning a large calculation into smaller subsystems then considering the many-body interactions between them. Variants of this approach have been used to parameterize classical force fields and machine learning potentials, applications that benefit from interoperability between quantum chemistry codes. However, there is a dearth of software that provides interoperability yet is purpose-built to handle the combinatorial complexity of fragment-based calculations. To fill this void we introduce “Fragme∩t”, an open-source software application that provides a tool for community validation of fragment-based methods, a platform for developing new approximations, and a framework for analyzing many-body interactions. Fragme∩t includes algorithms for automatic fragment generation and structure modification, and for distance- and energy-based screening of the requisite subsystems. Checkpointing, database management, and parallelization are handled internally and results are archived in a portable database. Interfaces to various quantum chemistry engines are easy to write and exist already for Q-Chem, PySCF, xTB, Orca, CP2K, MRCC, Psi4, NWChem, GAMESS, and MOPAC. Applications reported here demonstrate parallel efficiencies around 96% on more than 1000 processors but also showcase that the code can handle large-scale protein fragmentation using only workstation hardware, all with a codebase that is designed to be usable by non-experts. Fragme∩t conforms to modern software engineering best practices and is built upon well established technologies including Python, SQLite, and Ray. The source code is available under the Apache 2.0 license.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2021

Phoenix: A Scalable Streaming Hypergraph Analysis Framework

We present Phoenix, a scalable hypergraph analytics framework for data analytics and knowledge discovery that was implemented on the leadership class computing platforms at Oak Ridge National Laboratory (ORNL). Our software framework comprises a distributed implementation of a streaming server architecture which acts as a gateway for various hypergraph generators/external sources to connect. Phoenix has the capability to utilize diverse hypergraph generators, including HyGen, a very large-scale hypergraph generator developed by ORNL. Phoenix incorporates specific algorithms for efficient data representation by exploiting hidden structures of the hypergraphs. Our experimental results demonstrate Phoenix’s scalable and stable performance on massively parallel computing platforms. Phoenix’s superior performance is due to the merging of high-performance computing with data analytic.

Kurte, Kuldeep↗
DOE OSTI2023

Overcoming the field-of-view to diameter trade-off in microendoscopy via computational optrode-array microscopy

High-resolution microscopy of deep tissue with large field-of-view (FOV) is critical for elucidating organization of cellular structures in plant biology. Microscopy with an implanted probe offers an effective solution. However, there exists a fundamental trade-off between the FOV and probe diameter arising from aberrations inherent in conventional imaging optics (typically, FOV < 30% of diameter). Here, we demonstrate the use of microfabricated non-imaging probes (optrodes) that when combined with a trained machine-learning algorithm is able to achieve FOV of 1x to 5x the probe diameter. Further increase in FOV is achieved by using multiple optrodes in parallel. With a 1 × 2 optrode array, we demonstrate imaging of fluorescent beads (including 30 FPS video), stained plant stem sections and stained living stems. Our demonstration lays the foundation for fast, high-resolution microscopy with large FOV in deep tissue via microfabricated non-imaging probes and advanced machine learning.

59 BASIC BIOLOGICAL SCIENCES↗
NASA NTRS1975

Operation of the Institute for Computer Applications in Science and Engineering

The ICASE research program is described in detail; it consists of four major categories: (1) efficient use of vector and parallel computers, with particular emphasis on the CDC STAR-100; (2) numerical analysis, with particular emphasis on the development and analysis of basic numerical algorithms; (3) analysis and planning of large-scale software systems; and (4) computational research in engineering and the natural sciences, with particular emphasis on fluid dynamics. The work in each of these areas is described in detail; other activities are discussed, a prognosis of future activities are included.

Source record↗
NASA NTRS1978

Feasibility of a special-purpose computer to solve the Navier-Stokes equations

Orders-of-magnitude improvements in computer performance can be realized with a parallel array of thousands of fast microprocessors. In this architecture, wiring congestion is minimized by limiting processor communication to nearest neighbors. When certain standard algorithms are applied to a viscous flow problem and existing LSI technology is used, performance estimates of this conceptual design show a dramatic decrease in computational time when compared to the CDC 7600.

Gritton, E. C.↗
NASA NTRS1985

A Uniform Subdivision Method for Triangular Bezier Patches

A subdivision method for Bezier triangles is presented that parallels the development of Lane-Riesenfeld for Bezier Curves. The method is developed from the mathematical description of the patch, and the resulting algorithm does not require evaluation of the blending functions. This method subdivides the triangle uniformly so that the lengths of the sides of the subtriangles are uniformly reduced. This method is a member of the class of methods first presented by Goldman, which contain subdivision methods that arise from degenerate subdivision of Bezier tetrahedra. It is shown that a certain method is a natural extension of the Lane-Riesenfeld results for Bezier curves.

Joy, K. I.↗
NASA NTRS2012

Airborne Precision Spacing for Dependent Parallel Operations Interface Study

This paper describes a usability study of proposed cockpit interfaces to support Airborne Precision Spacing (APS) operations for aircraft performing dependent parallel approaches (DPA). NASA has proposed an airborne system called Pair Dependent Speed (PDS) which uses their Airborne Spacing for Terminal Arrival Routes (ASTAR) algorithm to manage spacing intervals. Interface elements were designed to facilitate the input of APS-DPA spacing parameters to ASTAR, and to convey PDS system information to the crew deemed necessary and/or helpful to conduct the operation, including: target speed, guidance mode, target aircraft depiction, and spacing trend indication. In the study, subject pilots observed recorded simulations using the proposed interface elements in which the ownship managed assigned spacing intervals from two other arriving aircraft. Simulations were recorded using the Aircraft Simulation for Traffic Operations Research (ASTOR) platform, a medium-fidelity simulator based on a modern Boeing commercial glass cockpit. Various combinations of the interface elements were presented to subject pilots, and feedback was collected via structured questionnaires. The results of subject pilot evaluations show that the proposed design elements were acceptable, and that preferable combinations exist within this set of elements. The results also point to potential improvements to be considered for implementation in future experiments.

Volk, Paul M.↗
DOE OSTI2020

Grid-based minimization at scale: Feldman-Cousins corrections for SBN

We present a computational model for the construction of Feldman-Cousins (FC) corrections frequently used in High Energy Physics (HEP) analysis. The program contains a grid-based minimization and is written in C++. Our algorithms exploit vectorization through Eigen3, yielding a single-core speed-up of 350 compared to the original implementation, and achieve MPI data parallelism by using DIY. We demonstrate the application to scale very well at High Performance Computing (HPC) sites. We use HDF5 in conjunction with HighFive to write results of the calculation to file.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
NASA NTRS1991

A contention-based bus-control scheme for multiprocessor systems

The authors study contention-based bus-control schemes for scheduling processors in using a bit-parallel shared bus. The protocol is designed under the requirements that each processor exhibit a random access behavior, that there be no centralized bus control in the system, and that access be granted in real time. The proposed scheme is based on splitting algorithms used in conventional contention-resolution schemes, and utilizes two-state information obtained from collision detection. Two versions of the bus-control scheme are studied. The static one resolves contentions of N requesting processors in an average of O(logW/2N) iterations, where W is the number of bits in the bit-parallel bus. An adaptive version resolves contentions in an average time that is independent of N.

Juang, Jie-Yong↗
DOE OSTI2026

Parallel-in-Time Solution of Allen-Cahn Equations by Integrating Operator Learning into the Parareal Method

While recent advances in deep learning have shown promising efficiency gains in solving time-dependent partial differential equations (PDEs), matching the accuracy of conventional numerical solvers still remains a challenge. One strategy to improve the accuracy of deep learning-based solutions for time-dependent PDEs is to use the learned model as the coarse propagator in the Parareal method and a traditional numerical method as the fine solver. However, successful integration of deep learning into the Parareal method requires consistency between the coarse and fine solvers, particularly for PDEs exhibiting rapid changes such as sharp transitions. Here, to ensure this consistency, we propose using convolutional neural networks (CNNs) to learn the fully discrete time-stepping operator defined by the same numerical scheme employed as the fine solver. We demonstrate the effectiveness of the proposed method in solving the classical and mass-conservative Allen–Cahn (AC) equations. Through iterative updates in the Parareal algorithm, our approach achieves a significant computational speedup compared to traditional fine solvers while converging to high-accuracy solutions. Our results highlight that the proposed hybrid Parareal algorithm effectively accelerates simulations, particularly when implemented on multiple GPUs, and converges to the desired accuracy in only a few iterations. Another advantage of our method is that the CNN model is trained on trajectory-based data generated from random initial conditions, such that the trained model can be used to solve the AC equations with various initial conditions without retraining. This work demonstrates the potential of integrating neural network methods into parallel-in-time frameworks for efficient and accurate simulations of time-dependent PDEs.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS2006

LDCM Grid Prototype (LGP)

The LGP successfully demonstrated that grid technology could be used to create a collaboration among research scientists, their science development machines, and distributed data to create a science production system in a nationally distributed environment. Grid technology provides a low cost and effective method of enabling production of science products by the science community. To demonstrate this, the LGP partnered with NASA GSFC scientists and used their existing science algorithms to generate virtual Landsat-like data products using distributed data resources. LGP created 48 output composite scenes with 4 input scenes each for a total of 192 scienes processed in parallel. The demonstration took 12 hours, which beat the requirement by almost 50 percent, well within the LDCM requirement to process 250 scenes per day. The LGP project also showed the successful use of workflow tools to automate the processing. Investing in this technology has led to funding for a ROSES ACCESS proposal. The proposal intends to enable an expert science user to produce products from a number of similar distributed instrument data sets using the Land Cover Change Community-based Processing and Analysis System (LC-ComPS) Toolbox. The LC-ComPS Toolbox is a collection of science algorithms that enable the generation of data with ground resolution on the order of Landsat-class instruments.

Weinstein, Beth↗