Search NASA⌕ Search

SEARCH · Search NASA

Results for “parallel algorithm”

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,027 records · Page 57
All sourcesNASA NTRSDOE OSTI
DOE OSTI2019

Efficient Distributed Optimization of Wind Farms Using Proximal Primal-Dual Algorithms: Preprint

This paper presents a distributed approach to perform real-time optimization of large wind farms. Wind turbines in a wind farm typically operate individually to maximize their own performance regardless of the impact of aerodynamic interactions on neighboring turbines. This paper optimizes the overall power produced by a wind farm by formulating and solving a nonconvex optimization problem where the yaw angles are optimized to allow some turbines to operate in misaligned conditions and shape the aerodynamic interactions in a favorable way. The solution of the nonconvex smooth problem is tackled using a proximal primal-dual gradient method, which provably identifies a first-order stationary solution in a global sublinear manner. By adding auxiliary optimization variables for every pair of turbines that are coupled aerodynamically and properly adding consensus constraints into the underlying problem, a distributed algorithm with turbine-to-turbine message passing is obtained; this allows for turbines to be optimized in parallel using local information rather than information from the whole wind farm. This algorithm is computationally light, as it involves closed-form updates. This approach is demonstrated on a large wind farm with 60 turbines. The results indicate that similar performance can be achieved as with finite-difference gradient-based optimization at a fraction of the computational time and thus approach real-time control/optimization.

17 WIND ENERGY↗
DOE OSTI2019

Efficient Distributed Optimization of Wind Farms Using Proximal Primal-Dual Algorithms

This paper presents a distributed approach to performing real-time optimization of large wind farms. Wind turbines in a wind farm typically operate individually to maximize their own performance regardless of the impact of aerodynamic interactions on neighboring turbines. This paper optimizes the overall power produced by a wind farm by formulating and solving a nonconvex optimization problem where the yaw angles are optimized to allow some turbines to operate in misaligned conditions and shape the aerodynamic interactions in a favorable way. The solution of the nonconvex smooth problem is tackled using a proximal primal-dual gradient method, which provably identifies a first-order stationary solution in a global sublinear manner. By adding auxiliary optimization variables for every pair of turbines that are coupled aerodynamically, and properly adding consensus constraints into the underlying problem, a distributed algorithm with turbine-to-turbine message passing is obtained; this allows for turbines to be optimized in parallel using local information rather than information from the whole wind farm. This algorithm is computationally light, as it involves closed-form updates. This approach is demonstrated on a large wind farm with 60 turbines. The results indicate that similar performance can be achieved as with finite-difference gradient-based optimization at a fraction of the computational time and thus approaching real-time control/optimization.

17 WIND ENERGY↗
DOE OSTI2026

ZEUS: An Efficient GPU Optimization Method Integrating PSO, BFGS, and Automatic Differentiation

We introduce a novel, efficient computational method, ZEUS, for numerical optimization, and provide an open-source implementation. It has four key ingredients: (1) particle swarm optimization (PSO), (2) the use of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method, (3) automatic differentiation (AD), and (4) GPUs. Our approach addresses the computational challenges inherent in high-dimensional, non-convex optimization problems. In the first phase of the algorithm, we get a potentially good set of starting points using PSO. Thereafter, we run BFGS independently in parallel from these starting points. BFGS is one of the best-performing algorithms for numerical optimization. However, it requires the gradient of the function being optimized. ZEUS integrates automatic differentiation into BFGS thus avoiding the need for the user to calculate derivatives explicitly. The use of GPUs allows ZEUS to speed up the calculations substantially. We carry out systematic studies to explore the trade-offs between the number of PSO iterations taken, starting points, and BFGS iteration depth. We show that a handful of iterations of PSO can improve global convergence when combined with BFGS. We also present performance studies using common test functions. The source code can be found at https://github.com/fnal-numerics/global-optimizer-gpu.

Soos, Dominik [Old Dominion U.]↗
DOE OSTI2016

Bayesian inference of nonlinear unsteady aerodynamics from aeroelastic limit cycle oscillations

A Bayesian model selection and parameter estimation algorithm is applied to investigate the influence of nonlinear and unsteady aerodynamic loads on the limit cycle oscillation (LCO) of a pitching airfoil in the transitional Reynolds number regime. At small angles of attack, laminar boundary layer trailing edge separation causes negative aerodynamic damping leading to the LCO. The fluid–structure interaction of the rigid, but elastically mounted, airfoil and nonlinear unsteady aerodynamics is represented by two coupled nonlinear stochastic ordinary differential equations containing uncertain parameters and model approximation errors. Several plausible aerodynamic models with increasing complexity are proposed to describe the aeroelastic system leading to LCO. The likelihood in the posterior parameter probability density function (pdf) is available semi-analytically using the extended Kalman filter for the state estimation of the coupled nonlinear structural and unsteady aerodynamic model. The posterior parameter pdf is sampled using a parallel and adaptive Markov Chain Monte Carlo (MCMC) algorithm. The posterior probability of each model is estimated using the Chib–Jeliazkov method that directly uses the posterior MCMC samples for evidence (marginal likelihood) computation. The Bayesian algorithm is validated through a numerical study and then applied to model the nonlinear unsteady aerodynamic loads using wind-tunnel test data at various Reynolds numbers.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2012

Improving the Performance Scalability of the Community Atmosphere Model

The Community Atmosphere Model (CAM), which serves as the atmosphere component of the Community Climate System Model (CCSM), is the most computationally expensive CCSM component in typical configurations. On current and next-generation leadership class computing systems, the performance of CAM is tied to its parallel scalability. Improving performance scalability in CAM has been a challenge, due largely to algorithmic restrictions necessitated by the polar singularities in its latitude-longitude computational grid. Nevertheless, through a combination of exploiting additional parallelism, implementing improved communication protocols, and eliminating scalability bottlenecks, we have been able to more than double the maximum throughput rate of CAM on production platforms. We describe these improvements and present results on the Cray XT5 and IBM BG/P. The approaches taken are not specific to CAM and may inform similar scalability enhancement activities for other codes.

99 GENERAL AND MISCELLANEOUS↗
DOE OSTI2025

Optimizing temperature distributions for training neural quantum states using parallel tempering

Parametrized artificial neural networks (ANNs) can be very expressive ansatzes for variational algorithms, reaching state-of-the-art energies on many quantum many-body Hamiltonians. Nevertheless, the training of the ANN can be slow and stymied by the presence of local minima in the parameter landscape. One approach to mitigate this issue is to use parallel tempering methods, and in this work, we focus on the role played by the temperature distribution of the parallel tempering replicas. Using an adaptive method that adjusts the temperatures in order to equate the exchange probability between neighboring replicas, we show that this temperature optimization can significantly increase the success rate of the variational algorithm with negligible computational cost by eliminating bottlenecks in the replicas' random walk. Furthermore, we demonstrate this using two different neural networks, a restricted Boltzmann machine and a feedforward network, which we use to study a toy problem based on a permutation invariant Hamiltonian with a pernicious local minimum and the 𝐽 1 −𝐽 2 model on a rectangular lattice.

Neural network simulations↗
DOE OSTI2018

Prediction of perovskite and other ternary oxide multilayers as mirrors for soft X-rays

Highlights: • Theoretical framework to identify optimal multilayers for high x-ray reflectivity. • Perovskite oxide multilayers are proposed as soft x-ray mirrors. • High soft x-ray reflectivity up to 33% are expected in perovskite multilayers. - Abstract: We propose multilayers of perovskite and related ternary oxides with a general formula of ABO{sub 3} as high reflectivity mirrors, especially for use in water window region (2.3–4.4 nm). The high reflectivity combinations of oxide multilayers were deduced using evolutionary search algorithms such as genetic algorithms, and the calculation speed was accelerated via parallel computing methods We also propose a figure of merit for X-ray reflectivity in periodic multilayers systems, which can simplify the future efforts on identifying material combinations, and the search through this multi-dimensional parameter space. The highest reflectivity value was found to be over 33% at 3.1 nm in the water window region. The effect of interface roughness was simulated and the decrease in reflectivity was found to be modest for practically achievable roughness values. This work establishes the foundation for future experimental and theoretical studies towards achieving high reflectivity x-ray mirrors of complex oxide multilayers.

36 MATERIALS SCIENCE↗
DOE OSTI2015

SU-E-T-765: Treatment Planning Comparison of SFUD Proton and 4Ï€ Radiotherapy for Prostate Cases

Purpose: Single-Field Uniform Dose (SFUD) proton scanning beams and non-coplanar 4π intensity-modulated radiation therapy (IMRT) represent the most advanced treatment methods based on heavy ion and X-rays, respectively. Here we compare their performance for prostate treatment. Methods: Five prostate patients were planned using 4π radiotherapy and SFUD to an initial dose of 54Gy to a planning target volume (PTV) that encompassed the prostate and seminal vesicles, then a boost prescription dose of 25.2Gy to the prostate for a total dose of 79.2 Gy. 4π plans were created by inversely selecting and optimizing 30 beams from 1162 candidate non-coplanar beams using a greedy column generation algorithm. The SFUD plans utilized two coplanar, parallel-opposing lateral scanning beams. The SFUD plan PTV was modified to account for range uncertainties while keeping an evaluation PTV identical to that of the X-ray plans for comparison. PTV doses, bladder and rectum dose volumes (V40, V45, V60, V70, V75.6, and V80), R50, and PTV homogeneity index (D95/D5) were evaluated. Results: Compared to SFUD, 4π resulted in 6.8% lower high dose spillage as indicated by R50. Bladder and rectum mean doses were 38.3% and 28.2% lower for SFUD, respectively. However, bladder and rectum volumes receiving >70Gy were 13.1% and 12% greater using proton SFUD. Due to the parallel-opposing beam arrangement, SFUD resulted in greater femoral head (87.8%) and penile bulb doses (43.7%). 4π PTV doses were slightly more homogeneous (HI 0.99 vs. 0.98) than the SFUD dose. Conclusion: Proton is physically advantageous to reduce the irradiated normal volume and mean doses to the rectum and bladder but it is also limited in the beam orientations and entrance dose, which resulted in greater doses to the femoral heads and penile bulb, and larger volumes of rectum and bladder exposed to high dose due to the required robust PTV definition. This project is supported by Varian Medical Systems.

60 APPLIED LIFE SCIENCES↗
DOE OSTI2023

Alignment of the CLAS12 central hybrid tracker with a Kalman Filter

Several factors can contribute to the difficulty of aligning the sensors of tracking detectors, including a large number of modules, multiple types of detector technologies, and non-linear strip patterns on the sensors. All three of these factors apply to the CLAS12 CVT, which is a hybrid detector consisting of planar silicon sensors with non-parallel strips, and cylindrical micromegas sensors with longitudinal and arc-shaped strips located within a 5 T superconducting solenoid. To align this detector, we used the Kalman Alignment Algorithm, which accounts for correlations between the alignment parameters without requiring the time-consuming inversion of large matrices. This is the first time that this algorithm has been adapted for use with hybrid technologies, non-parallel strips, and curved sensors. We present the results for the first alignment of the CLAS12 CVT using straight tracks from cosmic rays and from a target with the magnetic field turned off. After running this procedure, we achieved alignment at the level of 10 µm, and the widths of the residual spectra were greatly reduced. These results attest to the flexibility of this algorithm and its applicability to future use in the CLAS12 CVT and other hybrid or curved trackers, such as those proposed for the future Electron-Ion Collider.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2014

The Metropolis Monte Carlo method with CUDA enabled Graphic Processing Units

We present a CPU–GPU system for runtime acceleration of large molecular simulations using GPU computation and memory swaps. The memory architecture of the GPU can be used both as container for simulation data stored on the graphics card and as floating-point code target, providing an effective means for the manipulation of atomistic or molecular data on the GPU. To fully take advantage of this mechanism, efficient GPU realizations of algorithms used to perform atomistic and molecular simulations are essential. Our system implements a versatile molecular engine, including inter-molecule interactions and orientational variables for performing the Metropolis Monte Carlo (MMC) algorithm, which is one type of Markov chain Monte Carlo. By combining memory objects with floating-point code fragments we have implemented an MMC parallel engine that entirely avoids the communication time of molecular data at runtime. Our runtime acceleration system is a forerunner of a new class of CPU–GPU algorithms exploiting memory concepts combined with threading for avoiding bus bandwidth and communication. The testbed molecular system used here is a condensed phase system of oligopyrrole chains. A benchmark shows a size scaling speedup of 60 for systems with 210,000 pyrrole monomers. Our implementation can easily be combined with MPI to connect in parallel several CPU–GPU duets. -- Highlights: •We parallelize the Metropolis Monte Carlo (MMC) algorithm on one CPU—GPU duet. •The Adaptive Tempering Monte Carlo employs MMC and profits from this CPU—GPU implementation. •Our benchmark shows a size scaling-up speedup of 62 for systems with 225,000 particles. •The testbed involves a polymeric system of oligopyrroles in the condensed phase. •The CPU—GPU parallelization includes dipole—dipole and Mie—Jones classic potentials.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2026

Rasterization with Data-Parallel Primitives

Parallel rasterization can suffer from race conditions during fragment generation, which is traditionally addressed by using specialized hardware accessible via vendor graphics APIs. Unfortunately, graphics APIs are increasingly problematic on high-performance computers, either because they are not provided or because of concerns about dependencies with in situ visualization. In response, we present a hardware-agnostic rasterization algorithm that handles race conditions using only data-parallel primitives (DPPs), enabling efficient rendering on HPC systems without graphics API dependencies and aligning with recent efforts to deliver visualization software with DPPs. Our evaluation consists of three phases: (1) evaluating portability across different CPU and GPU architectures, (2) evaluating competitiveness with a community standard, and (3) evaluating performance across varying workloads and available parallelism. The supporting experiments run on both AMD and NVIDIA GPUs, considering data sets as large as 460 million triangles and 160 million pixels. While performance generally falls short of graphics API baselines, it achieves interactive frame rates on most workloads. As a result, we conclude our approach is a viable solution for rasterization on high-performance computers since our approach is portably performant across different architectures without the need for specialized vendor support.

Buckley, Makani [University of Oregon] (ORCID:0009↗
DOE OSTI2018

Runtime Scheduling Policies for Distributed Graph Algorithms

In this paper we explore scheduling and runtime system support for unordered distributed graph computations that rely on optimistic (speculative) execution. Performance of such algorithms is impacted by two competing trends: the higher degree of parallelism enabled by optimistic execution in turn requires substantial runtime support. To address the potentially high overhead and scheduling complexity introduced by the runtime, we investigate customizable scheduling policies that augment the scheduler of the underlying runtime to adapt it to a specific graph application. We present several implementations of Distributed Control (DC), a data-driven unordered approach with work prioritization and demonstrate that customizable scheduling policies result in the most efficient implementation, outperforming the well-known -stepping Single-Source Shortest Paths (SSSP) and Jones-Plassmann vertex-coloring algorithms. We apply two scheduling techniques, flow control and adaptive frequency of network progress, which allow application-level control over the balance of domain work and the runtime work. Experimental results show the benefit of such application-aware scheduling for irregular distributed graph algorithms.

Firoz, Jesun S.↗
DOE OSTI2013

Domain-Specific Languages For Developing and Deploying Signature Discovery Workflows

Domain-agnostic Signature Discovery entails scientific investigation across multiple domains through the re-use of existing algorithms into workflows. The existing algorithms may be written in any programming language for various hardware architectures (e.g., desktops, commodity clusters, and specialized parallel hardware platforms). This raises an engineering issue in generating Web services for heterogeneous algorithms so that they can be composed into a scientific workflow environment (e.g., Taverna). In this paper, we present our software tool that defines two simple Domain-Specific Languages (DSLs) to automate these processes: SDL and WDL. Our Service Description Language (SDL) describes key elements of a signature discovery algorithm and generates the service code. The Workflow Description Language (WDL) describes the pipeline of services and generates deployable artifacts for the Taverna workflow management system. We demonstrate our tool with a landscape classification example that is represented by BLAST workflows composed of services that wrap original scripts.

Jacob, Ferosh↗
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↗