Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Parallel Optimization 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 307 records · Page 17
All sourcesNASA NTRSDOE OSTI
DOE OSTI2019

Mixed Integer Nonlinear Programming Approaches to Enhance Resiliency and Response Strategies in Critical Infrastructure

Motivation. Critical infrastructures are large, complex engineered systems that must be operated robustly under abnormal conditions resulting from natural hazards or intentional acts. For example, electric power systems must be robust to line faults, water utilities must rapidly mitigate contamination incidents, and computing networks must adapt to adversarial intrusions to protect critical information. Problem. It is difficult for decision-makers within resiliency analysis in critical infrastructure to optimize designs and develop effective response strategies that can account for uncertainties. Facing incomplete information and the sheer scope that a natural hazard or attack vector may incorporate, response can be ineffective without reliable, scalable decision support tools. These problems are intrinsically nonlinear and involve discrete decisions, and unfortunately, existing off-the-shelf mathematical programming methods cannot support optimization-based decision-making of these nonlinear at scale. Method/Approach and Results. This project emphasized development of fundamental optimization strategies that supported real- time mitigation and response for critical infrastructures. In particular, the project developed multi- tree approaches based on piecewise outer-approximations for solution of mixed-integer nonlinear programming (MINLP) problems. These techniques alternate between an MILP or MISOCP relaxation to obtain a lower bound and candidate discrete solutions and an NLP subproblem to obtain upper bounds. Using tailored relaxations based on problem structure, these methods were used to solve several key applications in resilience and response of critical infrastructure. This work resulted in two open-source, copyrighted software packages: CORAMIN (https://github.com/Coramin/Coramin) -- an object-oriented mathematical programming framework that supports tailored multi-tree algorithms for solution of large- scale mixed-integer nonlinear programming; and EGRET (Electrical Grid Research and Engineering Toolkit) (https://github.com/grid- parity-exchange/Egret) -- a declarative mathematical programming framework built upon CORAMIN and Pyomo for formulation and solution of resilience and operations problems in power grid systems. Furthermore, these tools resulted in several important published results, including the following: The first known global optimization approach that could solve the unit-commitment problem with nonlinear power flow constraints on medium-sized test problems; Improved parallel optimization-based bounds tightening and strengthening of relaxations of AC power flow constraints; and, Optimization-based approaches for improved grid resilience and use of demand response to improve grid resilience with reduction in capital requirements. Result Implications. This project developed first-of-a-kind algorithms for decision-making in critical infrastructure resilience operations and planning, as well as a next-generation toolkit for MINLP researchers. These approaches leveraged high-performance computing architectures to solve some of the largest, most challenging nonlinear discrete optimization problems to global optimality, and these successes were captured in open-source software to enable optimization-based decision-making, and efficient solution of MINLP formulations for electric power transmission grids.

24 POWER TRANSMISSION AND DISTRIBUTION↗
NASA NTRS2000

Optimization of Microelectronic Devices for Sensor Applications

The NASA/JPL goal to reduce payload in future space missions while increasing mission capability demands miniaturization of active and passive sensors, analytical instruments and communication systems among others. Currently, typical system requirements include the detection of particular spectral lines, associated data processing, and communication of the acquired data to other systems. Advances in lithography and deposition methods result in more advanced devices for space application, while the sub-micron resolution currently available opens a vast design space. Though an experimental exploration of this widening design space-searching for optimized performance by repeated fabrication efforts-is unfeasible, it does motivate the development of reliable software design tools. These tools necessitate models based on fundamental physics and mathematics of the device to accurately model effects such as diffraction and scattering in opto-electronic devices, or bandstructure and scattering in heterostructure devices. The software tools must have convenient turn-around times and interfaces that allow effective usage. The first issue is addressed by the application of high-performance computers and the second by the development of graphical user interfaces driven by properly developed data structures. These tools can then be integrated into an optimization environment, and with the available memory capacity and computational speed of high performance parallel platforms, simulation of optimized components can proceed. In this paper, specific applications of the electromagnetic modeling of infrared filtering, as well as heterostructure device design will be presented using genetic algorithm global optimization methods.

Cwik, Tom↗
DOE OSTI2018

Communication-avoiding optimization methods for distributed massive-scale sparse inverse covariance estimation

Across a variety of scientific disciplines, sparse inverse covariance estimation is a popular tool for capturing the underlying dependency relationships in multivariate data. Unfortunately, most estimators are not scalable enough to handle the sizes of modern high-dimensional data sets (often on the order of terabytes), and assume Gaussian samples. To address these deficiencies, we introduce HP-CONCORD, a highly scalable optimization method for estimating a sparse inverse covariance matrix based on a regularized pseudolikelihood framework, without assuming Gaussianity. Our parallel proximal gradient method uses a novel communication-avoiding linear algebra algorithm and runs across a multi-node cluster with up to 1k nodes (24k cores), achieving parallel scalability on problems with up to ≈819 billion parameters (1.28 million dimensions); even on a single node, HP-CONCORD demonstrates scalability, outperforming a state-of-the-art method. We also use HP-CONCORD to estimate the underlying dependency structure of the brain from fMRI data, and use the result to identify functional regions automatically. The results show good agreement with a clustering from the neuroscience literature.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2018

Communication-Avoiding Optimization Methods for Distributed Massive-Scale Sparse Inverse Covariance Estimation.

Across a variety of scientific disciplines, sparse inverse covariance estimation is a popular tool for capturing the underlying dependency relationships in multivariate data. Unfortunately, most estimators are not scalable enough to handle the sizes of modern high-dimensional data sets (often on the order of terabytes), and assume Gaussian samples. To address these deficiencies, we introduce HP-CONCORD, a highly scalable optimization method for estimating a sparse inverse covariance matrix based on a regularized pseudolikelihood framework, without assuming Gaussianity. Our parallel proximal gradient method uses a novel communication-avoiding linear algebra algorithm and runs across a multi-node cluster with up to 1k nodes (24k cores), achieving parallel scalability on problems with up to ~819 billion parameters (1.28 million dimensions); even on a single node, HP-CONCORD demonstrates scalability, outperforming a state-of-the-art method. We also use HP-CONCORD to estimate the underlying dependency structure of the brain from fMRI data, and use the result to identify functional regions automatically. The results show good agreement with a clustering from the neuroscience literature.

Koanantakool, Penporn↗
DOE OSTI2026

Memory-Aware External Facelist Calculation: A Data-Parallel Atomic Hash Counting Approach

Unstructured volumetric meshes serve as fundamental data representations in various scientific simulations and analyses. They play a crucial role in representing complex computational domains and are essential for important numerical techniques, such as finite element analysis. Whenever such a mesh is read from a file, streamed in-situ, or generated by algorithms, scientific visualization libraries rely on calculating the external surface of a geometry, named “external facelist”, to produce a polygonal mesh for rendering. Consequently, external facelist calculation has become one of the most widely used algorithms in the scientific visualization domain, necessitating optimal performance. In this paper, we explore relevant work on external facelist calculation algorithms in two common visualization libraries, VTK and Viskores, assess their performance and memory constraints, and introduce a novel memory-aware external facelist calculation algorithm employing an atomic hash counting approach. This algorithm fully leverages Viskores' data-parallel primitive operations, facilitating its execution across diverse many-core architectures. Our algorithm features the lowest memory footprint on the GPU and the second-lowest on the CPU among all evaluated methods, and it also delivers the fastest performance on both CPU and GPU. It has been made available under an open-source license in the VTK and Viskores visualization systems.

Tsalikis, Spiros [Kitware] (ORCID:0000000151137195↗
DOE OSTI2019

GUNDAM: a toolkit for fast spatial correlation functions in galaxy surveys

ABSTRACT We describe the capabilities of a new software package to calculate two-point correlation functions (2PCFs) of large galaxy samples. The code can efficiently estimate 3D/projected/angular 2PCFs with a variety of statistical estimators and bootstrap errors, and is intended to provide a complete framework (including calculation, storage, manipulation, and plotting) to perform this type of spatial analysis with large redshift surveys. Gundam implements a very fast skip list/linked list algorithm that efficiently counts galaxy pairs and avoids the computation of unnecessary distances. It is several orders of magnitude faster than a naive pair counter, and matches or even surpass other advanced algorithms. The implementation is also embarrassingly parallel, making full use of multicore processors or large computational clusters when available. The software is designed to be flexible, user friendly and easily extensible, integrating optimized, well-tested packages already available in the astronomy community. Out of the box, it already provides advanced features such as custom weighting schemes, fibre collision corrections and 2D correlations. Gundam will ultimately provide an efficient toolkit to analyse the large-scale structure ‘buried’ in upcoming extremely large data sets generated by future surveys.

Donoso, E.↗
NASA NTRS1991

Problem solving with genetic algorithms and Splicer

Genetic algorithms are highly parallel, adaptive search procedures (i.e., problem-solving methods) loosely based on the processes of population genetics and Darwinian survival of the fittest. Genetic algorithms have proven useful in domains where other optimization techniques perform poorly. The main purpose of the paper is to discuss a NASA-sponsored software development project to develop a general-purpose tool for using genetic algorithms. The tool, called Splicer, can be used to solve a wide variety of optimization problems and is currently available from NASA and COSMIC. This discussion is preceded by an introduction to basic genetic algorithm concepts and a discussion of genetic algorithm applications.

Bayer, Steven E.↗
NASA NTRS1998

Multidisciplinary Design Optimization (MDO) Methods: Their Synergy with Computer Technology in Design Process

The paper identifies speed, agility, human interface, generation of sensitivity information, task decomposition, and data transmission (including storage) as important attributes for a computer environment to have in order to support engineering design effectively. It is argued that when examined in terms of these attributes the presently available environment can be shown to be inadequate a radical improvement is needed, and it may be achieved by combining new methods that have recently emerged from multidisciplinary design optimization (MDO) with massively parallel processing computer technology. The caveat is that, for successful use of that technology in engineering computing, new paradigms for computing will have to be developed - specifically, innovative algorithms that are intrinsically parallel so that their performance scales up linearly with the number of processors. It may be speculated that the idea of simulating a complex behavior by interaction of a large number of very simple models may be an inspiration for the above algorithms, the cellular automata are an example. Because of the long lead time needed to develop and mature new paradigms, development should be now, even though the widespread availability of massively parallel processing is still a few years away.

Sobieszczanski-Sobieski, Jaroslaw↗
DOE OSTI2018

Performance-Portable Particle Advection with VTK-m

Particle advection is the fundamental kernel behind most vector field visualization methods. Yet, the efficient parallel computation of large amounts of particle traces remains challenging. This is exacerbated by the variety of hardware trends in today's HPC arena, including increasing core counts in classical CPUs, many-core designs such as the Intel Xeon Phi, and massively parallel GPUs. The dedicated optimization of a particle advection kernel for each individual target architecture is both time-consuming and error prone. In this paper, we propose a performance-portable algorithm for particle advection. Our algorithm is based on the recently introduced VTK-m system and chiefly relies on its device adapter abstraction. We demonstrate the general portability of our implementation across a wide variety of hardware. Finally, our evaluation shows that our hardware-agnostic algorithm has comparable performance to hardware-specific algorithms.

Pugmire, Dave↗
NASA NTRS1988

A multistage linear array assignment problem

The implementation of certain algorithms on parallel processing computing architectures can involve partitioning contiguous elements into a fixed number of groups, each of which is to be handled by a single processor. It is desired to find an assignment of elements to processors that minimizes the sum of the maximum workloads experienced at each stage. This problem can be viewed as a multi-objective network optimization problem. Polynomially-bounded algorithms are developed for the case of two stages, whereas the associated decision problem (for an arbitrary number of stages) is shown to be NP-complete. Heuristic procedures are therefore proposed and analyzed for the general problem. Computational experience with one of the exact problems, incorporating certain pruning rules, is presented with one of the exact problems. Empirical results also demonstrate that one of the heuristic procedures is especially effective in practice.

Nicol, David M.↗
NASA NTRS2002

Turbopump Performance Improved by Evolutionary Algorithms

The development of design optimization technology for turbomachinery has been initiated using the multiobjective evolutionary algorithm under NASA's Intelligent Synthesis Environment and Revolutionary Aeropropulsion Concepts programs. As an alternative to the traditional gradient-based methods, evolutionary algorithms (EA's) are emergent design-optimization algorithms modeled after the mechanisms found in natural evolution. EA's search from multiple points, instead of moving from a single point. In addition, they require no derivatives or gradients of the objective function, leading to robustness and simplicity in coupling any evaluation codes. Parallel efficiency also becomes very high by using a simple master-slave concept for function evaluations, since such evaluations often consume the most CPU time, such as computational fluid dynamics. Application of EA's to multiobjective design problems is also straightforward because EA's maintain a population of design candidates in parallel. Because of these advantages, EA's are a unique and attractive approach to real-world design optimization problems.

Oyama, Akira↗
NASA NTRS2000

Performance of the OVERFLOW-MLP and LAURA-MLP CFD Codes on the NASA Ames 512 CPU Origin System

The shared memory Multi-Level Parallelism (MLP) technique, developed last year at NASA Ames has been very successful in dramatically improving the performance of important NASA CFD codes. This new and very simple parallel programming technique was first inserted into the OVERFLOW production CFD code in FY 1998. The OVERFLOW-MLP code's parallel performance scaled linearly to 256 CPUs on the NASA Ames 256 CPU Origin 2000 system (steger). Overall performance exceeded 20.1 GFLOP/s, or about 4.5x the performance of a dedicated 16 CPU C90 system. All of this was achieved without any major modification to the original vector based code. The OVERFLOW-MLP code is now in production on the inhouse Origin systems as well as being used offsite at commercial aerospace companies. Partially as a result of this work, NASA Ames has purchased a new 512 CPU Origin 2000 system to further test the limits of parallel performance for NASA codes of interest. This paper presents the performance obtained from the latest optimization efforts on this machine for the LAURA-MLP and OVERFLOW-MLP codes. The Langley Aerothermodynamics Upwind Relaxation Algorithm (LAURA) code is a key simulation tool in the development of the next generation shuttle, interplanetary reentry vehicles, and nearly all "X" plane development. This code sustains about 4-5 GFLOP/s on a dedicated 16 CPU C90. At this rate, expected workloads would require over 100 C90 CPU years of computing over the next few calendar years. It is not feasible to expect that this would be affordable or available to the user community. Dramatic performance gains on cheaper systems are needed. This code is expected to be perhaps the largest consumer of NASA Ames compute cycles per run in the coming year.The OVERFLOW CFD code is extensively used in the government and commercial aerospace communities to evaluate new aircraft designs. It is one of the largest consumers of NASA supercomputing cycles and large simulations of highly resolved full aircraft are routinely undertaken. Typical large problems might require 100s of Cray C90 CPU hours to complete. The dramatic performance gains with the 256 CPU steger system are exciting. Obtaining results in hours instead of months is revolutionizing the way in which aircraft manufacturers are looking at future aircraft simulation work. Figure 2 below is a current state of the art plot of OVERFLOW-MLP performance on the 512 CPU Lomax system. As can be seen, the chart indicates that OVERFLOW-MLP continues to scale linearly with CPU count up to 512 CPUs on a large 35 million point full aircraft RANS simulation. At this point performance is such that a fully converged simulation of 2500 time steps is completed in less than 2 hours of elapsed time. Further work over the next few weeks will improve the performance of this code even further.The LAURA code has been converted to the MLP format as well. This code is currently being optimized for the 512 CPU system. Performance statistics indicate that the goal of 100 GFLOP/s will be achieved by year's end. This amounts to 20x the 16 CPU C90 result and strongly demonstrates the viability of the new parallel systems rapidly solving very large simulations in a production environment.

Taft, James R.↗
NASA NTRS1990

Large scale nonlinear numerical optimal control for finite element models of flexible structures

This paper discusses the development of large scale numerical optimal control algorithms for nonlinear systems and their application to finite element models of structures. This work is based on our expansion of the optimal control algorithm (DDP) in the following steps: improvement of convergence for initial policies in non-convex regions, development of a numerically accurate penalty function method approach for constrained DDP problems, and parallel processing on supercomputers. The expanded constrained DDP algorithm was applied to the control of a four-bay, two dimensional truss with 12 soft members, which generates geometric nonlinearities. Using an explicit finite element model to describe the structural system requires 32 state variables and 10,000 time steps. Our numerical results indicate that for constrained or unconstrained structural problems with nonlinear dynamics, the results obtained by our expanded constrained DDP are significantly better than those obtained using linear-quadratic feedback control.

Shoemaker, Christine A.↗
NASA NTRS2008

MACOS Version 3.31

Version 3.31 of Modeling and Analysis for Controlled Optical Systems (MACOS) has been released. MACOS is an easy-to-use computer program for modeling and analyzing the behaviors of a variety of optical systems, including systems that have large, segmented apertures and are aligned with the technology of wavefront sensing and control. Two previous versions were described in "Improved Software for Modeling Controlled Optical Systems" (NPO-19841) NASA Tech Briefs, Vol. 21, No. 12 (December 1997), page 42 and "Optics Program Modified for Multithreaded Parallel Computing" (NPO-40572) NASA Tech Briefs, Vol. 30, No. 1 (January 2006) page 13a. The present version incorporates the following enhancements over prior versions: a) A powerful system-optimization facility includes algorithms for linear, nonlinear, unconstrained, and constrained optimization of optical systems under a variety of settings. b) There is now enhanced capability to perturb optical components individually and on subsystem levels, and to optimize system performance by adjusting selected individual components as well as subsystems. c) Capabilities for modeling a variety of new optical aperture types have been added. d) Effects of multilayer thin-film coats on optical surfaces can now be taken into account when tracing polarized rays. e) Major software-engineering work was performed to make MACOS more reliable, flexible, and manageable for purposes of maintenance and further development.

Redding, David↗
NASA NTRS2010

Data Acquisition System for Multi-Frequency Radar Flight Operations Preparation

A three-channel data acquisition system was developed for the NASA Multi-Frequency Radar (MFR) system. The system is based on a commercial-off-the-shelf (COTS) industrial PC (personal computer) and two dual-channel 14-bit digital receiver cards. The decimated complex envelope representations of the three radar signals are passed to the host PC via the PCI bus, and then processed in parallel by multiple cores of the PC CPU (central processing unit). The innovation is this parallelization of the radar data processing using multiple cores of a standard COTS multi-core CPU. The data processing portion of the data acquisition software was built using autonomous program modules or threads, which can run simultaneously on different cores. A master program module calculates the optimal number of processing threads, launches them, and continually supplies each with data. The benefit of this new parallel software architecture is that COTS PCs can be used to implement increasingly complex processing algorithms on an increasing number of radar range gates and data rates. As new PCs become available with higher numbers of CPU cores, the software will automatically utilize the additional computational capacity.

Leachman, Jonathan↗
NASA NTRS2019

InSight's Reconstructed Aerothermal Environments

The InSight Mars Lander successfully landed on the surface on November 26, 2018. This poster will describe the methodologies and margins used in developing the aerothermal environments for design of the thermal protection systems (TPS), as well as a prediction of as-flown environments based on the best estimated trajectory. The InSight mission spacecraft design approach included the effects of radiant heat flux to the aft body from the wake for the first time on a US Mars Mission, due to overwhelming evidence in ground testing for the European ExoMars mission (2009/2010) [1] and 2010 tests in the Electric Arc Shock Tube (EAST) facility [2]. The radiant energy on an aftbody was also recently confirmed via measurement on the Schiaparelli mission [3]. In addition, the InSight mission expected to enter the Mars atmosphere during the dust storm season, so the heatshield TPS was designed to accommodate the extra recession due to the potential dust impact. This poster will compare the predicted aerothermal environments using the reconstructed best estimated trajectory to the design environments. Design Approach: The InSight spacecraft was planned to be a near-design-to-print copy of the Phoenix spacecraft. The determination of the heatshield TPS requirements was approached as if it was a new design due to the new requirement of flying through a dust storm. The baseline for aftbody was build-to-print, and all analyses focused on ensuring adequate margin. This proved to be a challenge because the Phoenix aftbody was designed to withstand only convective heating and the InSight aftbody was evaluated for both convective and radiative heating. Aerothermal environments were predicted using the Langley Aerothermodynamic Upwind Relaxation Algorithm (LAURA) and the Data Parallel Line Relaxation (DPLR) CFD codes, and the Nonequilibrium Radiative Transport and Spectra Program (NEQAIR) utilizing bounding design trajectories derived from Monte Carlo analyses from the Program to Optimize Simulated Trajectories II (POST2). In all cases, super-catalytic flowfields were assigned to ensure the most conservative heating results. Two trajectories were evaluated: 1) the trajectory with the maximum heat flux was utilized to determine the flowfield characteristics and the viability of the selection of TPS materials; and 2) the trajectory with the maximum heat load was used to determine the required thicknesses of the TPS materials. Evaluation of the MEDLI data [4], along with ground test data [5] led to the determination of whether or not the flow would transition from laminar to turbulent on the heatshield, which also determined the TPS sizing location for the heatshield. Aerothermal margins were added for the convective heating and developed for the radiative heating. TPS material sizing was determined with the Reaction Kinetic Ablation Program (REKAP) and the Fully Implicit Ablation and Thermal Analysis program (FIAT) using a three-branched approach to account for aerothermal, material response, and material properties uncertainties. In addition, the heatshield recession was augmented by an analysis of the effect of entry through a potential dusty atmosphere using a methodology developed in References [6] and [7]. These analyses resulted in an increase to the Phoenix heatshield TPS thickness. Reconstruction Efforts: Once the best estimated trajectory is reconstructed by the team, the LAURA/HARA (High-Temperature Aerothermo-dynamic Radiation model) and DPLR/NEQAIR code pairs will be used to predict the as-flown aerothermal conditions. In these runs, fully-catalytic flowfields will be assigned because it is a more physically accurate description of the chemistry in the flow. Once again, determination of the onset of turbulence on the heatshield will be evaluated. The as-flown aerothermal environments will then be compared to the design environments.

Beck, R. A.↗
DOE OSTI2024

Accelerated Constrained Sparse Tensor Factorization on Massively Parallel Architectures

This study presents the first constrained sparse tensor factorization (cSTF) framework that optimizes and fully offloads computation to massively parallel GPU architectures, and the first performance characterization of cSTF on GPU architectures. In contrast to prior work on tensor factorization, where the matricized tensor times Khatri-Rao product (MTTKRP) is the primary performance bottleneck, our systematic analysis of the cSTF algorithm on GPUs reveals that adding constraints creates an additional bottleneck in the update operation for many real-world sparse tensors. While executing the update operation on the GPU brings significant speedup over its CPU counterpart, it remains a significant bottleneck. To further accelerate the update operation, we propose cuADMM, a new update algorithm that leverages algorithmic and code optimization strategies to minimize both computation and data movement on GPUs. As a result, our framework delivers significantly improved performance compared to prior state-of-the-art. On 10 real-world sparse tensors, our framework achieves geometric mean speedup of 5.1 × (max 41.59 ×) and 7.01 × (max 58.05 ×) on the NIVIDA A100 and H100 GPUs, respectively, over the state-of-the-art SPLATT library running on a 26-core Intel Ice Lake Xeon CPU.

Soh, Yongseok↗
NASA NTRS1992

Learning and optimization with cascaded VLSI neural network building-block chips

To demonstrate the versatility of the building-block approach, two neural network applications were implemented on cascaded analog VLSI chips. Weights were implemented using 7-b multiplying digital-to-analog converter (MDAC) synapse circuits, with 31 x 32 and 32 x 32 synapses per chip. A novel learning algorithm compatible with analog VLSI was applied to the two-input parity problem. The algorithm combines dynamically evolving architecture with limited gradient-descent backpropagation for efficient and versatile supervised learning. To implement the learning algorithm in hardware, synapse circuits were paralleled for additional quantization levels. The hardware-in-the-loop learning system allocated 2-5 hidden neurons for parity problems. Also, a 7 x 7 assignment problem was mapped onto a cascaded 64-neuron fully connected feedback network. In 100 randomly selected problems, the network found optimal or good solutions in most cases, with settling times in the range of 7-100 microseconds.

Duong, T.↗