Results for “parallel algorithm” — Page 88

NASA NTRS1996

Scaling Properties of Algorithms in Nanotechnology

At the present time, several technologies are pressing the limits of microminiature manufacturing. In semiconductor technology, for example, the Intel Pentium Pro (which is used in the Department of Energy's ASCI 'red' parallel supercomputer system) and the DEC Alpha 21164 (which is used in the CRAY T3E) both are fabricated using 0.35 micron process technology. Recently Texas Instruments (TI) announced the availability of 0.25 micron technology chips by the end of 1996 and plans to have 0.18 micron devices in production within two years. However, some significant challenges lie down the road. These include the skyrocketing cost of manufacturing plants, the 0.1 micron foreseeable limit of the photolithography process, quantum effects, data communication bandwidth limitations, heat dissipation, and others. Some related microminiature technologies include micro-electromechanical systems (MEMS), opto-electronic devices, quantum computing, biological computing, and others. All of these technologies require the fabrication of devices whose sizes are approaching the nanometer level. As such they are often collectively referred to with the name 'nanotechnology'. Clearly nanotechnology in this general sense is destined to be a very important technology of the 21st century. The ultimate dream in this arena is 'molecular nanotechnology', in other words the fabrication of devices and materials with most or all atoms and molecules in a pre-programmed position, possibly placed there by 'nano-robots'. This futuristic capability will probably not be achieved for at least two decades. However, it appears that somewhat less ambitious variations of molecular nanotechnology, such as devices and materials based on 'buckyballs' and 'nanotubes' may be realized significantly sooner, possibly within ten years or so. Even at the present time, semiconductor devices are approaching the regime where quantum chemical effects must be considered in design.

Saini, Subhash↗

NASA NTRS1996

Satellite Angular Rate Estimation From Vector Measurements

This paper presents an algorithm for estimating the angular rate vector of a satellite which is based on the time derivatives of vector measurements expressed in a reference and body coordinate. The computed derivatives are fed into a spacial Kalman filter which yields an estimate of the spacecraft angular velocity. The filter, named Extended Interlaced Kalman Filter (EIKF), is an extension of the Kalman filter which, although being linear, estimates the state of a nonlinear dynamic system. It consists of two or three parallel Kalman filters whose individual estimates are fed to one another and are considered as known inputs by the other parallel filter(s). The nonlinear dynamics stem from the nonlinear differential equation that describes the rotation of a three dimensional body. Initial results, using simulated data, and real Rossi X ray Timing Explorer (RXTE) data indicate that the algorithm is efficient and robust.

Azor, Ruth↗

DOE OSTI2023

Multigrid Reduction in Time for Chaotic Dynamical Systems

As CPU clock speeds have stagnated and high performance computers continue to have ever higher core counts, increased parallelism is needed to take advantage of these new architectures. Traditional serial time-marching schemes can be a significant bottleneck, as many types of simulations require large numbers of time-steps which must be computed sequentially. Parallel-in-time schemes, such as the Multigrid Reduction in Time (MGRIT) method, remedy this by parallelizing across time-steps and have shown promising results for parabolic problems. However, chaotic problems have proved more difficult, since chaotic initial value problems (IVPs) are inherently ill-conditioned. MGRIT relies on a hierarchy of successively coarser time-grids to iteratively correct the solution on the finest time-grid, but due to the nature of chaotic systems, small inaccuracies on the coarser levels can be greatly magnified and lead to poor coarse-grid corrections. Here we introduce a modified MGRIT algorithm based on an existing quadratically converging nonlinear extension to the multigrid Full Approximation Scheme (FAS), as well as a novel time-coarsening scheme. Together, these approaches better capture long-term chaotic behavior on coarse-grids and greatly improve convergence of MGRIT for chaotic IVPs. Further, we introduce a novel low-memory variant of the algorithm for solving chaotic PDEs with MGRIT which not only solves the IVP, but also provides estimates for the unstable Lyapunov vectors of the system. Finally, we provide supporting numerical results for the Lorenz system and demonstrate parallel speedup for the chaotic Kuramoto–Sivashinsky PDE over a significantly longer time-domain than in previous works.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS2020

A ROS-based Simulator for Testing the Enhanced Autonomous Navigation of the Mars 2020 Rover

In order to achieve the ambitious objectives of the Mars 2020 (M2020) mission, in particular the ability to autonomously traverse more challenging terrains more efficiently, new surface mobility software was developed for Enhanced Navigation (ENav). That decision was made early in the project, before most of the new surface flight software (FSW) existed, which created a need for a separate framework where the new navigation algorithms could be quickly prototyped and tested, before more realistic FSW-based testbeds became available. The JPL robotics team chose the Robot Operating System [1] (ROS) as the environment in which to test the new ENav algorithms. This made it possible to write the algorithms in the C language required by the FSW, so they could be directly ported over to the flight module later on, while leveraging all the C++ libraries and tools provided by ROS for simulation and testing. The ENav algorithms were developed as a separate C library, and stubs were used to replace any FSW-specific code, such as Event Reporting (EVRs) and data products (DPs). A ROS simulator was developed to generate a rich set of varied 3D terrains representative of the candidate Mars landing sites and simulate the physics of the rover motion, the point cloud perceived by the rover’s stereo vision system, and the new thinking-while-driving (TWD) navigation logic which directs the rover to drive autonomously to user-specified waypoints. To simulate the rover motion and perception, a ROS node was developed that uses a software library called HyperDrive Sim (HDSim), which is a wrapper for the Rover Sequencing and Visualization Program [2] (RSVP). That library provides roverterrain settling, realistic slip modelling, and camera rendering capability based on the rover’s NavCam machine vision models. To simulate the navigation logic, a ROS node was created that initializes and runs the ENav algorithms in a way that mimics the FSW execution, while also providing the capability to load and replay data products, including re-running the recorded inputs through the ENav algorithms for testing. An engineering Graphical User Interface (GUI) was also developed to visualize various elements, such as the rover pose during the drive, the simulated and perceived terrain, the selected local and global paths to the goal, the evaluated candidate paths and the reasons why they were rejected, the keep-in and keep-out zones (KIOZs), etc. Finally, an advanced Monte Carlo (MC) framework that can run many simulations in parallel on the Cloud and automatically generate reports that capture the key ENav performance metrics was developed to evaluate the system in a statisticallymeaningful way. This paper provides an overview of the ROSbased simulator used for testing the M2020 ENav algorithms.

Toupet, Olivier↗

NASA NTRS1999

Scheduling for Parallel Supercomputing: A Historical Perspective of Achievable Utilization

The NAS facility has operated parallel supercomputers for the past 11 years, including the Intel iPSC/860, Intel Paragon, Thinking Machines CM-5, IBM SP-2, and Cray Origin 2000. Across this wide variety of machine architectures, across a span of 10 years, across a large number of different users, and through thousands of minor configuration and policy changes, the utilization of these machines shows three general trends: (1) scheduling using a naive FIFO first-fit policy results in 40-60% utilization, (2) switching to the more sophisticated dynamic backfilling scheduling algorithm improves utilization by about 15 percentage points (yielding about 70% utilization), and (3) reducing the maximum allowable job size further increases utilization. Most surprising is the consistency of these trends. Over the lifetime of the NAS parallel systems, we made hundreds, perhaps thousands, of small changes to hardware, software, and policy, yet, utilization was affected little. In particular these results show that the goal of achieving near 100% utilization while supporting a real parallel supercomputing workload is unrealistic.

Jones, James Patton↗

DOE OSTI2024

Quantum simulation of excited states from parallel contracted quantum eigensolvers

Abstract Computing excited-state properties of molecules and solids is considered one of the most important near-term applications of quantum computers. While many of the current excited-state quantum algorithms differ in circuit architecture, specific exploitation of quantum advantage, or result quality, one common feature is their rooting in the Schrödinger equation. However, through contracting (or projecting) the eigenvalue equation, more efficient strategies can be designed for near-term quantum devices. Here we demonstrate that when combined with the Rayleigh–Ritz variational principle for mixed quantum states, the ground-state contracted quantum eigensolver (CQE) can be generalized to compute any number of quantum eigenstates simultaneously. We introduce two excited-state (anti-Hermitian) CQEs that perform the excited-state calculation while inheriting many of the remarkable features of the original ground-state version of the algorithm, such as its scalability. To showcase our approach, we study several model and chemical Hamiltonians and investigate the performance of different implementations.

Physics↗

DOE OSTI2020

Dakota A Multilevel Parallel Object-Oriented Framework for Design Optimization Parameter Estimation Uncertainty Quantification and Sensitivity Analysis: Version 6.12 Theory Manual

The Dakota toolkit provides a flexible and extensible interface between simulation codes and iterative analysis methods. Dakota contains algorithms for optimization with gradient and nongradient-based methods; uncertainty quantification with sampling, reliability, and stochastic expansion methods; parameter estimation with nonlinear least squares methods; and sensitivity/variance analysis with design of experiments and parameter study methods. These capabilities may be used on their own or as components within advanced strategies such as surrogate-based optimization, mixed integer nonlinear programming, or optimization under uncertainty. By employing object-oriented design to implement abstractions of the key components required for iterative systems analyses, the Dakota toolkit provides a flexible and extensible problem-solving environment for design and performance analysis of computational models on high performance computers. This report serves as a theoretical manual for selected algorithms implemented within the Dakota software. It is not intended as a comprehensive theoretical treatment, since a number of existing texts cover general optimization theory, statistical analysis, and other introductory topics. Rather, this manual is intended to summarize a set of Dakota-related research publications in the areas of surrogate-based optimization, uncertainty quantification, and optimization under uncertainty that provide the foundation for many of Dakota's iterative analysis capabilities.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2021

Dakota A Multilevel Parallel Object-Oriented Framework for Design Optimization Parameter Estimation Uncertainty Quantification and Sensitivity Analysis (V.6.14) (User's Manual)

The Dakota toolkit provides a flexible and extensible interface between simulation codes and iterative analysis methods. Dakota contains algorithms for optimization with gradient and nongradient-based methods; uncertainty quantification with sampling, reliability, and stochastic expansion methods; parameter estimation with nonlinear least squares methods; and sensitivity/variance analysis with design of experiments and parameter study methods. These capabilities may be used on their own or as components within advanced strategies such as surrogate-based optimization, mixed integer nonlinear programming, or optimization under uncertainty. By employing object-oriented design to implement abstractions of the key components required for iterative systems analyses, the Dakota toolkit provides a flexible and extensible problem-solving environment for design and performance analysis of computational models on high performance computers. This report serves as a users manual for the Dakota software and provides capability overviews and procedures for software execution, as well as a variety of example studies.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2020

Dakota, A Multilevel Parallel Object-Oriented Framework for Design Optimization, Parameter Estimation, Uncertainty Quantification, and Sensitivity Analysis: Version 6.13 Theory Manual

The Dakota toolkit provides a flexible and extensible interface between simulation codes and iterative analysis methods. Dakota contains algorithms for optimization with gradient and nongradient-based methods; uncertainty quantification with sampling, reliability, and stochastic expansion methods; parameter estimation with nonlinear least squares methods; and sensitivity/variance analysis with design of experiments and parameter study methods. These capabilities may be used on their own or as components within advanced strategies such as surrogate-based optimization, mixed integer nonlinear programming, or optimization under uncertainty. By employing object-oriented design to implement abstractions of the key components required for iterative systems analyses, the Dakota toolkit provides a flexible and extensible problem-solving environment for design and performance analysis of computational models on high performance computers. This report serves as a theoretical manual for selected algorithms implemented within the Dakota software. It is not intended as a comprehensive theoretical treatment, since a number of existing texts cover general optimization theory, statistical analysis, and other introductory topics. Rather, this manual is intended to summarize a set of Dakota-related research publications in the areas of surrogate-based optimization, uncertainty quantification, and optimization under uncertainty that provide the foundation for many of Dakota's iterative analysis capabilities.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2021

Dakota, A Multilevel Parallel Object-Oriented Framework for Design Optimization, Parameter Estimation, Uncertainty Quantification, and Sensitivity Analysis (V.6.16 User's Manual)

The Dakota toolkit provides a flexible and extensible interface between simulation codes and iterative analysis methods. Dakota contains algorithms for optimization with gradient and nongradient-based methods; uncertainty quantification with sampling, reliability, and stochastic expansion methods; parameter estimation with nonlinear least squares methods; and sensitivity/variance analysis with design of experiments and parameter study methods. These capabilities may be used on their own or as components within advanced strategies such as surrogate-based optimization, mixed integer nonlinear programming, or optimization under uncertainty. By employing object-oriented design to implement abstractions of the key components required for iterative systems analyses, the Dakota toolkit provides a flexible and extensible problem-solving environment for design and performance analysis of computational models on high performance computers. This report serves as a user's manual for the Dakota software and provides capability overviews and procedures for software execution, as well as a variety of example studies.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2021

Dakota, A Multilevel Parallel Object-Oriented Framework for Design Optimization, Parameter Estimation, Uncertainty Quantification, and Sensitivity Analysis: Version 6.16 Theory Manual

The Dakota toolkit provides a flexible and extensible interface between simulation codes and iterative analysis methods. Dakota contains algorithms for optimization with gradient and nongradient-based methods; uncertainty quantification with sampling, reliability, and stochastic expansion methods; parameter estimation with nonlinear least squares methods; and sensitivity/variance analysis with design of experiments and parameter study methods. These capabilities may be used on their own or as components within advanced strategies such as surrogate-based optimization, mixed integer nonlinear programming, or optimization under uncertainty. By employing object-oriented design to implement abstractions of the key components required for iterative systems analyses, the Dakota toolkit provides a flexible and extensible problem-solving environment for design and performance analysis of computational models on high performance computers. This report serves as a theoretical manual for selected algorithms implemented within the Dakota software. It is not intended as a comprehensive theoretical treatment, since a number of existing texts cover general optimization theory, statistical analysis, and other introductory topics. Rather, this manual is intended to summarize a set of Dakota-related research publications in the areas of surrogate-based optimization, uncertainty quantification, and optimization under uncertainty that provide the foundation for many of Dakota’s iterative analysis capabilities.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS1995

Field lines and magnetic surfaces in a two-component slab/2D model of interplanetary magnetic fluctuations

A two-component model for the spectrum of interplanetary magnetic fluctuations was proposed on the basis of ISEE observations, and has found an intriguing level of application in other solar wind studies. The model fluctuations consist of a fraction of 'slab' fluctuations, varying only in the direction parallel to the locally uniform mean magnetic field B(0) and a complement of 2D (two-dimensional) fluctuations that vary in the directions transverse to B(0). We have developed an spectral method computational algorithm for computing the magnetic flux surfaces (flux tubes) associated with the composite model, based upon a precise analogy with equations for ideal transport of a passive scalar in planar two dimensional geometry. Visualization of various composite models will be presented, including the 80 percent 2D/ 20 percent slab model with delta B/B(0) approximately equals 1 and a minus 5/3 spectral law, that is thought to approximately represent a snapshot of solar wind turbulence. Characteristically, the visualizations show that flux tubes, even when defined as regular on some plane, shred and disperse rapidly as they are viewed along the parallel direction. This diffusive process, which generalizes the standard picture of field line random walk, will be discussed in detail. Evidently, the traditional picture that flux tubes randomize like strands of spaghetti with a uniform tangle along the axial direction is in need of modification.

Matthaeus, W. H.↗

DOE OSTI2024

Computing the QRPA level density with the finite amplitude method

Here, we describe a new algorithm to calculate the vibrational nuclear level density of an atomic nucleus. Fictitious perturbation operators that probe the response of the system are generated by drawing their matrix elements from some probability distribution function. We use the Finite Amplitude Method to explicitly compute the response for each such sample. With the help of the Kernel Polynomial Method, we build an estimator of the vibrational level density and provide the upper bound of the relative error in the limit of infinitely many random samples. The new algorithm can give accurate estimates of the vibrational level density. Since it is based on drawing multiple samples of perturbation operators, its computational implementation is naturally parallel and scales like the number of available processing units.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

DOE OSTI2025

Contextual subspace variational quantum eigensolver calculation of the dissociation curve of molecular nitrogen on a superconducting quantum computer

Abstract We present an experimental demonstration of the Contextual Subspace Variational Quantum Eigensolver on superconducting hardware. Calculating the potential energy curve of molecular nitrogen proves challenging for many conventional quantum chemistry techniques, since static correlation dominates in the dissociation limit. Our quantum simulations retain good agreement with the Full Configuration Interaction energy, outperforming all benchmarked single-reference wavefunction techniques in capturing the bond-breaking appropriately. Moreover, our methodology is competitive with multiconfigurational approaches but at a saving of quantum resource, meaning larger active spaces can be treated for a fixed qubit allowance. To achieve this result, we deploy an error mitigation/suppression strategy comprised of Dynamical Decoupling, Measurement-Error Mitigation and Zero-Noise Extrapolation. Circuit parallelization also provides passive noise-averaging and improves the effective shot yield to reduce the measurement overhead. Furthermore, we introduce a modified adaptive ansatz construction algorithm that incorporates hardware awareness into our variational circuits, minimizing the transpilation cost for the target qubit topology.

Physics↗

DOE OSTI2021

Grid-based minimization at scale: Feldman-Cousins corrections for light sterile neutrino search

High Energy Physics (HEP) experiments generally employ sophisticated statistical methods to present results in searches of new physics. In the problem of searching for sterile neutrinos, likelihood ratio tests are applied to short-baseline neutrino oscillation experiments to construct confidence intervals for the parameters of interest. The test statistics of the form Δχ2 is often used to form the confidence intervals, however, this approach can lead to statistical inaccuracies due to the small signal rate in the region-of-interest. In this paper, we present a computational model for the computationally expensive Feldman-Cousins corrections to construct a statistically accurate confidence interval for neutrino oscillation analysis. The program performs a grid-based minimization over oscillation parameters and is written in C++. Our algorithms make use of vectorization through Eigen3, yielding a single-core speed-up of 350 compared to the original implementation, and achieve MPI data parallelism by employing DIY. We demonstrate the strong scaling of the application at High-Performance Computing (HPC) sites. We utilize HDF5 along with HighFive to write the results of the calculation to file.

Wospakrik, Marianette↗

NASA NTRS1989

Asynchronous multilevel adaptive methods for solving partial differential equations on multiprocessors - Performance results

The fast adaptive composite grid method (FAC) is an algorithm that uses various levels of uniform grids (global and local) to provide adaptive resolution and fast solution of PDEs. Like all such methods, it offers parallelism by using possibly many disconnected patches per level, but is hindered by the need to handle these levels sequentially. The finest levels must therefore wait for processing to be essentially completed on all the coarser ones. A recently developed asynchronous version of FAC, called AFAC, completely eliminates this bottleneck to parallelism. This paper describes timing results for AFAC, coupled with a simple load balancing scheme, applied to the solution of elliptic PDEs on an Intel iPSC hypercube. These tests include performance of certain processes necessary in adaptive methods, including moving grids and changing refinement. A companion paper reports on numerical and analytical results for estimating convergence factors of AFAC applied to very large scale examples.

Mccormick, S.↗

NASA NTRS1992

Unsteady turbomachinery flow simulations on massively parallel architectures

The accurate numerical simulation of unsteady, three-dimensional viscous flow in turbomachines is computationally very intensive, requiring prohibitively large amounts of computer time on current vector supercomputers. In recent years, computer systems based on massively parallel architectures have been developed that offer the promise of meeting the computational power requirements of such large-scale simulations. However, a rethinking of existing algorithms and methodology is required in order to fully harness the computational power of such architectures. In this paper the capabilities of the Connection Machine (CM-2) in predicting unsteady flows in turbomachines are evaluated. The implementation on the CM-2 of an implicit, time-accurate, zonal algorithm for the Navier-Stokes equations in two dimensions is described. Programming issues and modifications made to the original algorithm (developed for vector, pipelined supercomputers) in order to improve performance on the CM-2 are outlined. Algorithm performance is evaluated and compared with a functionally equivalent code for the CRAY-YMP.

Madavan, N. K.↗

NASA NTRS2004

On Improving Efficiency of Differential Evolution for Aerodynamic Shape Optimization Applications

Differential Evolution (DE) is a simple and robust evolutionary strategy that has been provEn effective in determining the global optimum for several difficult optimization problems. Although DE offers several advantages over traditional optimization approaches, its use in applications such as aerodynamic shape optimization where the objective function evaluations are computationally expensive is limited by the large number of function evaluations often required. In this paper various approaches for improving the efficiency of DE are reviewed and discussed. Several approaches that have proven effective for other evolutionary algorithms are modified and implemented in a DE-based aerodynamic shape optimization method that uses a Navier-Stokes solver for the objective function evaluations. Parallelization techniques on distributed computers are used to reduce turnaround times. Results are presented for standard test optimization problems and for the inverse design of a turbine airfoil. The efficiency improvements achieved by the different approaches are evaluated and compared.

Madavan, Nateri K.↗