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
DOE OSTI2019

Parallel accelerated Custom Correlation Coefficient calculations for genomics applications

The massive quantities of genomic data being made available through gene sequencing techniques are enabling breakthroughs in genomic science in many areas such as medical advances in the diagnosis and treatment of diseases. Analyzing this data, however, is a computational challenge insofar as the computational costs of the relevant algorithms can grow with quadratic, cubic or higher complexity—leading to the need for leadership scale computing. In this paper we describe a new approach to calculations of the Custom Correlation Coefficient (CCC) between Single Nucleotide Polymorphisms (SNPs) across a population, suitable for parallel systems equipped with graphics processing units (GPUs) or Intel Xeon Phi processors. We describe the mapping of the algorithms to accelerated processors, techniques used for eliminating redundant calculations due to symmetries, and strategies for efficient mapping of the calculations to many-node parallel systems. Results are presented demonstrating high per-node performance and near-ideal parallel scalability with rates of more than nine quadrillion (9 × 10 15 ) elementwise comparisons achieved per second with the latest optimized code on the ORNL Titan system, this being orders of magnitude faster than rates achieved using other codes and platforms as reported in the literature. Also it is estimated that as many as 90 quadrillion (90 × 10 15 ) comparisons per second may be achievable on the upcoming ORNL Summit system, an additional 10X performance increase. Finally, in a companion paper we describe corresponding techniques applied to calculations of the Proportional Similarity metric for comparative genomics applications.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2018

Parallel accelerated vector similarity calculations for genomics applications

The surge in availability of genomic data holds promise for enabling determination of genetic causes of observed individual traits, with applications to problems such as discovery of the genetic roots of phenotypes, be they molecular phenotypes such as gene expression or metabolite concentrations, or complex phenotypes such as diseases. However, the growing sizes of these datasets and the quadratic, cubic or higher scaling characteristics of the relevant algorithms pose a serious computational challenge necessitating use of leadership scale computing. In this study we describe a new approach to performing vector similarity metrics calculations, suitable for parallel systems equipped with graphics processing units (GPUs) or Intel Xeon Phi processors. Our primary focus is the Proportional Similarity metric applied to Genome Wide Association Studies (GWAS) and Phenome Wide Association Studies (PheWAS). We describe the implementation of the algorithms on accelerated processors, methods used for eliminating redundant calculations due to symmetries, and techniques for efficient mapping of the calculations to many-node parallel systems. Finally, results are presented demonstrating high per-node performance and parallel scalability with rates of more than five quadrillion (5 × 10 15 ) elementwise comparisons achieved per second on the ORNL Titan system. In a companion paper we describe corresponding techniques applied to calculations of the Custom Correlation Coefficient for comparative genomics applications.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2014

A novel adaptive time stepping variant of the Boris–Buneman integrator for the simulation of particle accelerators with space charge

We show that adaptive time stepping in particle accelerator simulation is an enhancement for certain problems. The new algorithm has been implemented in the OPAL (Object Oriented Parallel Accelerator Library) framework. The idea is to adjust the frequency of costly self-field calculations, which are needed to model Coulomb interaction (space charge) effects. In analogy to a Kepler orbit simulation that requires a higher time step resolution at the close encounter, we propose to choose the time step based on the magnitude of the space charge forces. Inspired by geometric integration techniques, our algorithm chooses the time step proportional to a function of the current phase space state instead of calculating a local error estimate like a conventional adaptive procedure. Building on recent work, a more profound argument is given on how exactly the time step should be chosen. An intermediate algorithm, initially built to allow a clearer analysis by introducing separate time steps for external field and self-field integration, turned out to be useful by its own, for a large class of problems.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2015

Balanced Coloring for Parallel Computing Applications

Graph coloring is used to identify subsets of independent tasks in parallel scientific computing applications. Traditional coloring heuristics aim to reduce the number of colors used as that number also corresponds to the number of parallel steps in the application. However, if the color classes produced have a skew in their sizes, utilization of hardware resources becomes inefficient, especially for the smaller color classes. Equitable coloring is a theoretical formulation of coloring that guarantees a perfect balance among color classes, and its practical relaxation is referred to as balanced coloring. In this paper, we revisit the problem of balanced coloring in the context of parallel computing. The goal is to achieve a balanced coloring of an input graph without increasing the number of colors that an algorithm oblivious to balance would have used. We propose and study multiple heuristics that aim to achieve such a balanced coloring, present parallelization approaches for multi-core and manycore architectures, and cross-evaluate their effectiveness with respect to the quality of balance achieved and performance. Furthermore, we study the impact of the proposed balanced coloring heuristics on a concrete application - viz. parallel community detection, which is an example of an irregular application. The thorough treatment of balanced coloring presented in this paper from algorithms to application is expected to serve as a valuable resource to parallel application developers who seek to improve parallel performance of their applications using coloring.

Balanced coloring, Tilera manycore architecture, c↗
DOE OSTI2015

Accelerating k-NN Algorithm with Hybrid MPI and OpenSHMEM

Machine Learning algorithms are benefiting from the continuous improvement of programming models, including MPI, MapReduce and PGAS. k-Nearest Neighbors (k-NN) algorithm is a widely used machine learning algorithm, applied to supervised learning tasks such as classification. Several parallel implementations of k-NN have been proposed in the literature and practice. However, on high-performance computing systems with high-speed interconnects, it is important to further accelerate existing designs of the k-NN algorithm through taking advantage of scalable programming models. To improve the performance of k-NN on large-scale environment with InfiniBand network, this paper proposes several alternative hybrid MPI+OpenSHMEM designs and performs a systemic evaluation and analysis on typical workloads. The hybrid designs leverage the one-sided memory access to better overlap communication with computation than the existing pure MPI design, and propose better schemes for efficient buffer management. The implementation based on k-NN program from MaTEx with MVAPICH2-X (Unified MPI+PGAS Communication Runtime over InfiniBand) shows up to 9.0% time reduction for training KDD Cup 2010 workload over 512 cores, and 27.6% time reduction for small workload with balanced communication and computation. Experiments of running with varied number of cores show that our design can maintain good scalability.

Lin, Jian↗
DOE OSTI2023

Comparing Top-Down Proteoform Identification: Deconvolution, PrSM Overlap, and PTM Detection

Generating top-down tandem mass spectra (MS/MS) for complex mixtures of proteoforms has become possible through improvements in fractionation, on-line separation, dissociation, and mass analysis. The algorithms to match tandem mass spectra to sequences have undergone a parallel evolution, with both spectral alignment and peak matching being paired with diverse methods for scoring proteoform-spectral matches (PrSMs). This study assesses state-of-the-art algorithms for top-down identification through three distinct challenges. The first is identifying a large yield of PrSMs while controlling false discovery rate (FDR) in identifying thousands of proteoforms from complex cell lysates via four software workflows: ProSight Proteome Discoverer, TopPIC, Informed Proteomics, and pTop. The second is the deconvolution of data from both Thermo Orbitrap-class and Bruker maXis Q-TOF instruments to produce consistent precursor charge and mass determinations while generating fragment mass lists to optimize identification. The third attempts to detect diverse post-translational modifications (PTMs) in proteoforms from cow milk and human ovarian tissue. The data demonstrate that existing software suites produce admirable sensitivity, in some cases identifying a third of collected tandem mass spectra with FDR controlled below 2%; the overlap in these PrSMs, however, illustrates real value in searching data with multiple search engines. Differences among identification workflows seem to result from each search algorithm incorporating its own deconvolution algorithm. By transmitting deconvolution data from multiple deconvolution routes (Thermo Xtract, Bruker Auto MSn, Mascot Distiller, TopFD, and FLASHDeconv) to the downstream TopPIC search algorithm, we were able to detect common causes of deconvolution disagreement. The detection of PTMs was very inconsistent among search algorithms, with some workflows suggesting as little as 1% of PrSMs from cow’s milk were singly-phosphorylated while other workflows found that 18% of PrSMs were singly-phosphorylated. Taken together, these results make a strong argument for top-down researchers to adopt a standard practice of analyzing each MS/MS experiment with at least two different search engines.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2022

Receptance coupling substructure analysis and chatter frequency-informed machine learning for milling stability

This paper describes a milling stability identification approach that simultaneously considers: physics-based models for the tool tip frequency response functions and stability predictions; the binary result from a milling test (automatically labeled as stable or unstable based on frequency content); chatter frequency when an unstable result is obtained; and user risk tolerance. The algorithm applies probabilistic Bayesian machine learning with adaptive, parallelized Markov Chain Monte Carlo sampling to update the probability of stability with each milling test. Furthermore, the result is a robust solution for rapid convergence to optimized milling parameters for maximum metal removal rate using all available information.

42 ENGINEERING↗
DOE OSTI2025

In situ multi-tier auto-ignition detection applied to dual-fuel combustion simulations

Here we use an anomaly detection methodology that is centered on analyzing fourth-order joint moments (co-kurtosis), particularly focusing on its application in auto-ignition of combustion problems with large numbers of species. Unsupervised anomaly detection is challenging to generalize across problem types and domains. A recent technique, centered on analyzing information in the fourth-order joint moment co-kurtosis, has shown promise, especially for high-dimensional scientific data. In this work we present developments to the co-kurtosis based anomaly detection method needed to make it effective and scalable for large-scale distributed scientific data, such as those generated by massively parallel simulations. An in situ co-kurtosis algorithm is employed as the anomaly detection method for identifying ignition kernels in simulations of turbulent combustion. Here, we extend an existing methodology which identifies regions of the domain where anomalies are present, and add another tier of anomaly detection where the individual samples contributing to the anomaly are identified. We apply this algorithm on-the-fly to a variety of turbulent reacting flow problems and compare it to the widely used (but significantly more expensive) chemical explosive mode analysis (CEMA). We demonstrate the ability of the method to detect and identify the onset of low and high temperature ignition which can be used for computational steering, as chemical and combustion anomalies occur intermittently at spatio-temporal locations unknown a priori. Finally, we apply our lightweight in situ algorithm to an exascale high-fidelity simulation with a total of 2.4 Trillion degrees of freedom, performed using an adaptive mesh refinement solver. Furthermore, through a scalability analysis, we show that the relative computational cost of this in-situ anomaly detection algorithm compared to an iteration of the reacting flow solver is negligible.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Machine learning-based optimization of air-cooled heat sinks

Machine learning-based models using Artificial Neural Network (ANN) and greedy search algorithm are used to optimize air-cooled parallel plate-finned heat sinks (PPFHSs) subjected to laminar flow over an extensive range of design parameters. Here, the thermal and hydraulic performances of PPFHSs are represented by heat transfer coefficient (h) and pressure drop (ΔP), respectively. Optimization objectives for PPFHS designs can vary from industry to industry depending on their design priorities. The present study proposes a novel and generalized optimization method that defines practical optimization objectives and provides an accurate optimization process to design effective PPFHSs for a wide range of industrial applications with different design requirements. Three optimization objectives are presented in this study: (i) the largest h PΔ, (ii) the largest h within a specified maximum allowed flow rate, and (iii) the lowest weight that maximizes h for operation within the maximum allowed flow rate. While the shortcoming of the first objective is demonstrated, the other two objectives are found to be suitable for designing effective heat sinks (HSs) across different applications. Results suggest a promising trend from the third objective to develop HSs with ~ 37-68% lower weight, 80-85% reduced ΔP, and negligible penalty in h compared with optimized HSs obtained from the second objective. However, since the third objective leads to HSs with thinner fins, structural analysis should be performed to ensure reliable operation of the HSs.

42 ENGINEERING↗
DOE OSTI2015

First results of the silicon telescope using an 'artificial retina' for fast track finding

We present the first results of the prototype of a silicon tracker with trigger capabilities based on a novel approach for fast track finding. The working principle of the 'artificial retina' is inspired by the processing of visual images by the brain and it is based on extensive parallelization of data distribution and pattern recognition. The algorithm has been implemented in commercial FPGAs in three main logic modules: a switch for the routing of the detector hits, a pool of engines for the digital processing of the hits, and a block for the calculation of the track parameters. The architecture is fully pipelined and allows the reconstruction of real-time tracks with a latency less then 100 clock cycles, corresponding to 0.25 microsecond at 400 MHz clock. The silicon telescope consists of 8 layers of single-sided silicon strip detectors with 512 strips each. The detector size is about 10 cm x 10 cm and the strip pitch is 183 μm. The detectors are read out by the Beetle chip, a custom ASICs developed for LHCb, which provides the measurement of the hit position and pulse height of 128 channels. The 'artificial retina' algorithm has been implemented on custom data acquisition boards based on FPGAs Xilinx Kintex 7 lx160. The parameters of the tracks detected are finally transferred to host PC via USB 3.0. The boards manage the read-out ASICs and the sampling of the analog channels. The read-out is performed at 40 MHz on 4 channels for each ASIC that corresponds to a decoding of the telescope information at 1.1 MHz. We report on the first results of the fast tracking device and compare with simulations. (authors)

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2026

Efficient Probabilistic Visualization of Local Divergence of 2D Vector Fields with Independent Gaussian Uncertainty

This work focuses on visualizing uncertainty of local divergence of two-dimensional vector fields. Divergence is one of the fundamental attributes of fluid flows, as it can help domain scientists analyze potential positions of sources (positive divergence) and sinks (negative divergence) in the flow. However, uncertainty inherent in vector field data can lead to erroneous divergence computations, adversely impacting downstream analysis. While Monte Carlo (MC) sampling is a classical approach for estimating divergence uncertainty, it suffers from slow convergence and poor scalability with increasing data size and sample counts. Thus, we present a two-fold contribution that tackles the challenges of slow convergence and limited scalability of the MC approach. (1) We derive a closed-form approach for highly efficient and accurate uncertainty visualization of local divergence, assuming independently Gaussian-distributed vector uncertainties. (2) We further integrate our approach into Viskores, a platform-portable parallel library, to accelerate uncertainty visualization. In our results, we demonstrate significantly enhanced efficiency and accuracy of our serial analytical (speed-up up to 1946×) and parallel Viskores (speed-up up to 19698×) algorithms over the classical serial MC approach. We also demonstrate qualitative improvements of our probabilistic divergence visualizations over traditional mean-field visualization, which disregards uncertainty. We validate the accuracy and efficiency of our methods on wind forecast and ocean simulation datasets.

Ouermi, Timbwaoga [University of Utah]↗
DOE OSTI2015

TADSim: Discrete Event-based Performance Prediction for Temperature Accelerated Dynamics

Next-generation high-performance computing will require more scalable and flexible performance prediction tools to evaluate software--hardware co-design choices relevant to scientific applications and hardware architectures. Here, we present a new class of tools called application simulators—parameterized fast-running proxies of large-scale scientific applications using parallel discrete event simulation. Parameterized choices for the algorithmic method and hardware options provide a rich space for design exploration and allow us to quickly find well-performing software--hardware combinations. We demonstrate our approach with a TADSim simulator that models the temperature-accelerated dynamics (TAD) method, an algorithmically complex and parameter-rich member of the accelerated molecular dynamics (AMD) family of molecular dynamics methods. The essence of the TAD application is captured without the computational expense and resource usage of the full code. We accomplish this by identifying the time-intensive elements, quantifying algorithm steps in terms of those elements, abstracting them out, and replacing them by the passage of time. We use TADSim to quickly characterize the runtime performance and algorithmic behavior for the otherwise long-running simulation code. We extend TADSim to model algorithm extensions, such as speculative spawning of the compute-bound stages, and predict performance improvements without having to implement such a method. Validation against the actual TAD code shows close agreement for the evolution of an example physical system, a silver surface. Finally, focused parameter scans have allowed us to study algorithm parameter choices over far more scenarios than would be possible with the actual simulation. This has led to interesting performance-related insights and suggested extensions.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2018

minilosurface

The miniIsosurface package provides a collection of reference implementations for finding a representation for a contour of a scalar field in a volume. Contouring is a well-studied algorithm in scientific visualization and there are many algorithm variations to solve it. The miniIsosurface package provides a convenient collection of the most popular variations of the contour algorithm and some variations to run in different parallel environments.

Borgeois, Daniel↗
DOE OSTI2023

JSAC

JSAC is a Java implementation of the Seismic Analysis Code (SAC2000, https://github.com/LLNL/SAC2000). It is intended to bring the most commonly used features of SAC2000 up to date with modern standards, support parallelized computation where possible, and implement improvements in algorithms and numerics.

Dodge, Douglas↗
DOE OSTI2024

SPARC-X: Quantum simulations at extreme scale - reactive dynamics from first principles

We have developed the massively parallel electronic structure code SPARC-X: a computational framework for performing Kohn-Sham Density Functional Theory (DFT) calculations that can scale linearly with the number of atoms in the system, while being able to leverage petascale and emerging exascale parallel computers to study chemical phenomena at unprecedented length and time scales. SPARC-X exploits a recent breakthrough in electronic structure methodologies: systematically improvable, strictly local, orthonormal, discontinuous real-space bases that efficiently and systematically capture the local chemistry of the system. With further adaptation using new machine-learning techniques and the use of the massively parallel Spectral Quadrature (SQ) electronic structure method, the algorithmic complexity and prefactor associated with DFT calculations involving semilocal as well as hybrid functionals are dramatically reduced. Using petascale computational resources, SPARC-X enables quantum mechanical simulations at length and time scales previously accessible only by empirical approaches, e.g., 1,000,000 atoms for a few picoseconds using semilocal functionals or 1,000 atoms for a few picoseconds using hybrid functionals. Using exascale resources, the sizes and times targeted are two orders of magnitude larger. Such a capability has applications in a wide variety of chemical sciences, including reactive interfaces where large length- and/or long time-scales are needed and traditional force fields fail. This is particularly important in dynamic catalysis, where bond breaking and formation must be understood in detail. We developed, tested, and employed the SPARC-X framework to understand the photocatalytic properties of TiO 2 nanoparticles, revealing finite size effects that cannot be captured with standard model systems or functionals. This integrated development and application strategy ensures that SPARC-X remains a robust, efficient, and scalable software package for quantum simulations on current petascale and emerging exascale computing resources.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2019

HyperSpace

Machine learning (ML) models often contain numerous hyperparameters, free parameters that must be set before the models can be trained. As the number of model hyperparameters increases, their optimization becomes significantly more challenging as we face a combinatorial increase in potential model configurations. Similarly, there is an increased chance that our models’ hyperparameters interact in complex ways. HyperSpace allows a user to optimize complex machine learning algorithms based on their hyperparameters. HyperSpace works by parallelizing parameter search spaces, running Bayesian model based optimization (SMBO) over each of these spaces in parallel. It was designed to be as minimally invasive as possible such that very little change to existing code will be needed to get a user started.

Ramanathan, Arvind↗
DOE OSTI2023

Combining machine-learned and empirical force fields with the parareal algorithm: application to the diffusion of atomistic defects

We numerically investigate an adaptive version of the parareal algorithm in the context of molecular dynamics. This adaptive variant has been originally introduced in [1]. We focus here on test cases of physical interest where the dynamics of the system is modelled by the Langevin equation and is simulated using the molecular dynamics software LAMMPS. In this work, the parareal algorithm uses a family of machine-learning spectral neighbor analysis potentials (SNAP) as fine, reference, potentials and embedded-atom method potentials (EAM) as coarse potentials. We consider a self-interstitial atom in a tungsten lattice and compute the average residence time of the system in metastable states. Our numerical results demonstrate significant computational gains using the adaptive parareal algorithm in comparison to a sequential integration of the Langevin dynamics. We also identify a large regime of numerical parameters for which statistical accuracy is reached without being a consequence of trajectorial accuracy.

36 MATERIALS SCIENCE↗
NASA NTRS1989

Parallel solution of sparse one-dimensional dynamic programming problems

Parallel computation offers the potential for quickly solving large computational problems. However, it is often a non-trivial task to effectively use parallel computers. Solution methods must sometimes be reformulated to exploit parallelism; the reformulations are often more complex than their slower serial counterparts. We illustrate these points by studying the parallelization of sparse one-dimensional dynamic programming problems, those which do not obviously admit substantial parallelization. We propose a new method for parallelizing such problems, develop analytic models which help us to identify problems which parallelize well, and compare the performance of our algorithm with existing algorithms on a multiprocessor.

Nicol, David M.↗