Search NASA⌕ Search

SEARCH · Search NASA

Results for “algorithm timings”

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 397 records · Page 22

Synchronization Of Parallel Discrete Event Simulations

Adaptive, parallel, discrete-event-simulation-synchronization algorithm, Breathing Time Buckets, developed in Synchronous Parallel Environment for Emulation and Discrete Event Simulation (SPEEDES) operating system. Algorithm allows parallel simulations to process events optimistically in fluctuating time cycles that naturally adapt while simulation in progress. Combines best of optimistic and conservative synchronization strategies while avoiding major disadvantages. Algorithm processes events optimistically in time cycles adapting while simulation in progress. Well suited for modeling communication networks, for large-scale war games, for simulated flights of aircraft, for simulations of computer equipment, for mathematical modeling, for interactive engineering simulations, and for depictions of flows of information.

Steinman, Jeffrey S.↗

Parallel-In-Time Multigrid with Adaptive Spatial Coarsening for The Linear Advection and Inviscid Burgers Equations

We apply a multigrid reduction-in-time (MGRIT) algorithm to hyperbolic partial differential equations in one spatial dimension. This study is motivated by the observation that sequential time-stepping is a computational bottleneck when attempting to implement highly concurrent algorithms; thus parallel-in-time methods are desirable. MGRIT adds parallelism by using a hierarchy of successively coarser temporal levels to accelerate the solution on the finest level. In the case of explicit time-stepping, spatial coarsening is a suitable approach to ensure that stability conditions are satisfied on all levels, and it may be useful for implicit time-stepping by producing cheaper multigrid cycles. Unfortunately, uniform spatial coarsening results in extremely slow convergence when the wave speed is near zero, even if only locally. We present an adaptive spatial coarsening strategy that addresses this issue for the variable coefficient linear advection equation and the inviscid Burgers equation using first-order explicit or implicit time-stepping methods. Serial numerical results show this method offers significant improvements over uniform coarsening and is convergent for the inviscid Burgers equation with and without shocks. Parallel scaling tests on up to 128K cores indicate that run-time improvements over serial time-stepping strategies are possible when spatial parallelism alone saturates, and that scalability is robust for oscillatory solutions which change on the scale of the grid spacing.

97 MATHEMATICS AND COMPUTING↗

An algorithm for the space shuttle scheduling problem

The problem of determining launch times for a set of missions is considered. Launch times must satisfy early start time and resource constraints. The investigation reported is concerned with the minimization of the number of missions which are launched after specified late start times. An algorithm is presented which, under certain restrictive assumptions, provides an optimal solution. If the restrictive assumptions are not satisfied, the algorithm may be used to obtain a lower bound on the number of missions flown late.

Fisher, M. L.↗

Concurrent algorithms for transient nonlinear FE analysis

A two-parameter class of time-stepping algorithms for nonlinear structural dynamics is investigated. What sets the present method apart from other concurrent algorithms is the fact that it can be used to some advantage in sequential machines as well. Thus, substantial speed-ups are obtained on a single processor as the number of subdomains is increased. An additional O(p) speed-up is obtained when p processors are utilized. The test case discussed is being repeated for a mesh comprising four times as many elements, in an effort to understand how the large scale asymptotic speed-ups are attained. A three dimensional example involving finite deformations and free body motions is also being pursued. A code optimized for concurrency in the Alliant FX8 computer is being finalized. This will provide the means for testing the performance of the algorithm in a multiprocessor environment.

Ortiz, M.↗

Higher-Order, Space-Time Adaptive Finite Volume Methods: Algorithms, Analysis and Applications

The four main goals outlined in the proposal for this project were: 1. Investigate the use of higher-order (in space and time) finite-volume methods for fluid flow problems. 2. Explore the embedding of iterative temporal methods within traditional block-structured AMR algorithms. 3. Develop parallel in time methods for ODEs and PDEs. 4. Work collaboratively with the Center for Computational Sciences and Engineering (CCSE) at Lawrence Berkeley National Lab towards incorporating new algorithms within existing DOE application codes.

97 MATHEMATICS AND COMPUTING↗

Time Evolution with the DMRG Algorithm: A Generic Implementation for Strongly Correlated Electronic Systems

A detailed description of the time-step-targeting time evolution method within the density-matrix renormalization-group algorithm is presented. The focus of this publication is on the implementation of the algorithm and its generic application. The case of one-site excitations within a Hubbard model is analyzed as a test for the algorithm, using open chains and two-leg ladder geometries. The accuracy of the procedure in the case of the recently discussed holon-doublon photo excitations of Mott insulators is also analyzed. Performance and parallelization issues are discussed. In addition, the full open-source code is provided as supplementary material.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Solving constrained minimum-time robot problems using the sequential gradient restoration algorithm

Three constrained minimum-time control problems of a two-link manipulator are solved using the Sequential Gradient and Restoration Algorithm (SGRA). The inequality constraints considered are reduced via Valentine-type transformations to nondifferential path equality constraints. The SGRA is then used to solve these transformed problems with equality constraints. The results obtained indicate that at least one of the two controls is at its limits at any instant in time. The remaining control then adjusts itself so that none of the system constraints is violated. Hence, the minimum-time control is either a pure bang-bang control or a combined bang-bang/singular control.

Lee, Allan Y.↗

Local flow management/profile descent algorithm. Fuel-efficient, time-controlled profiles for the NASA TSRV airplane

The Local Flow Management/Profile Descent (LFM/PD) algorithm designed for the NASA Transport System Research Vehicle program is described. The algorithm provides fuel-efficient altitude and airspeed profiles consistent with ATC restrictions in a time-based metering environment over a fixed ground track. The model design constraints include accommodation of both published profile descent procedures and unpublished profile descents, incorporation of fuel efficiency as a flight profile criterion, operation within the performance capabilities of the Boeing 737-100 airplane with JT8D-7 engines, and conformity to standard air traffic navigation and control procedures. Holding and path stretching capabilities are included for long delay situations.

Groce, J. L.↗

mesoflow [SWR-22-56]

Mesoflow is a continuum scale simulation tool developed specifically for modeling transport and chemistry at the mesoscale. Our solver utilizes Cartesian block-structured adaptive mesh refinement to resolve complex surface morphologies (of catalysts/biomass particles among others) directly obtained from X-ray tomography data. An immersed boundary based formulation enables rapid representation of complex geometries prevalent in most mesoporous interfaces. The solver is developed on top of open-source performance portable library, AMReX, providing parallel execution capabilities on current and upcoming high-performance-computing (HPC) architectures. Our flexible software framework enables integration of complex chemical mechanisms at heterogenous interfaces and time-split algorithms for circumventing highly disparate reaction and flow time-scales. Our current studies indicate a ten-fold performance gain by using graphics-processing-units (GPU) compared to a single processor for representative problem sizes (2 million cell mesh).

Sitaraman, Hariswaran↗

Mesoflow: An Open-Source Reacting Flow Solver for Catalysis at Mesoscale

We present the capabilities and software performance metrics of our open-source continuum solver for catalysis, Mesoflow, developed specifically for modeling transport and chemistry at the mesoscale. Our solver utilizes Cartesian block-structured adaptive mesh refinement to resolve complex catalyst surface morphologies directly obtained from X-ray tomography data. An immersed boundary based formulation enables rapid representation of complex geometries prevalent in most mesoporous catalyst interfaces. The solver is developed on top of open-source performance portable library, AMReX, providing parallel execution capabilities on current and upcoming high-performance-computing (HPC) architectures. Our flexible software framework enables integration of complex chemical mechanisms at heterogenous interfaces and time-split algorithms for circumventing highly disparate reaction and flow time-scales. Our current studies indicate a ten-fold performance gain by using graphics-processing-units (GPUs) compared to a single processor for representative problem sizes (2 million cell mesh). We will also present a brief introduction on how to build and use this software for application problems pertaining to catalytic upgrading and gas transport within porous catalyst particles.

adaptive meshing↗

Localized Exponential Time Differencing Method for Shallow Water Equations: Algorithms and Numerical Study

Here, we explore the performance of the exponential time differencing (ETD) method applied to the rotating shallow water equations. Comparing with explicit time stepping of the same order accuracy in time, the ETD algorithms could reduce the computational time in many cases by allowing the use of large time step sizes while still maintaining numerical stability. To accelerate the ETD simulations, we propose a localized approach that synthesizes the ETD method and overlapping domain decomposition. By dividing the original problem into many subdomain problems of smaller sizes and solving them locally, the proposed approach could speed up the calculation of matrix exponential vector products. Several standard test cases for shallow water equations of one or multiple layers are considered. The results show great potential of the localized ETD method for high-performance computing because each subdomain problem can be naturally solved in parallel at every time step.

58 GEOSCIENCES↗

Examination of Semi-Analytical Solution Methods in the Coarse Operator of Parareal Algorithm for Power System Simulation

With continuing advances in high-performance parallel computing platforms, parallel algorithms have become powerful tools for development of faster than real-time power system dynamic simulations. In particular, it has been demonstrated in recent years that parallel-in-time (Parareal) algorithms have the potential to achieve such an ambitious goal. Here, the selection of a fast and reasonably accurate coarse operator of the Parareal algorithm is crucial for its effective utilization and performance. This paper examines semi-analytical solution (SAS) methods as the coarse operators of the Parareal algorithm and explores performance of the SAS methods to the standard numerical time integration methods. Two promising time-power series-based SAS methods were considered; Adomian decomposition method and Homotopy analysis method with a windowing approach for improving the convergence. Numerical performance case studies on 10-generator 39-bus system and 327-generator 2383-bus system were performed for these coarse operators over different disturbances, evaluating the number of Parareal iterations, computational time, and stability of convergence. All the coarse operators tested with different scenarios have converged to the same corresponding true solution (if they are convergent) and the SAS methods provide comparable computational speed, while having more stable convergence to the true solution in many cases.

97 MATHEMATICS AND COMPUTING↗

Portable and Transparent Message Compression in MPI Libraries to Improve the Performance and Scalability of Parallel Applications

The goal of this project has been to develop a lossless compression algorithm for message-passing libraries that can accelerate HPC systems by reducing the communication time. Because both compression and decompression have to be performed in software in real time, the algorithm has to be extremely fast while still delivering a good compression ratio. During the first half of this project, they designed a new compression algorithm called FPC for scientific double-precision data, made the source code available on the web, and published two papers describing its operation, the first in the proceedings of the Data Compression Conference and the second in the IEEE Transactions on Computers. At comparable average compression ratios, this algorithm compresses and decompresses 10 to 100 times faster than BZIP2, DFCM, FSD, GZIP, and PLMI on the three architectures tested. With prediction tables that fit into the CPU's L1 data acache, FPC delivers a guaranteed throughput of six gigabits per second on a 1.6 GHz Itanium 2 system. The C source code and documentation of FPC are posted on-line and have already been downloaded hundreds of times. To evaluate FPC, they gathered 13 real-world scientific datasets from around the globe, including satellite data, crash-simulation data, and messages from HPC systems. Based on the large number of requests they received, they also made these datasets available to the community (with permission of the original sources). While FPC represents a great step forward, it soon became clear that its throughput was too slow for the emerging 10 gigabits per second networks. Hence, no speedup can be gained by including this algorithm in an MPI library. They therefore changed the aim of the second half of the project. Instead of implementing FPC in an MPI library, they refocused their efforts to develop a parallel compression algorithm to further boost the throughput. After all, all modern high-end microprocessors contain multiple CPUs on a single die and will undoubtedly contain even larger numbers of CPUs in the future. Hence, a compute node in a parallel system is likely to have multiple processors per interconnection link. Thus, they investigated how to best exploit multiple CPUs to compress and decompress data for a single link, i.e., they developed a parallel version of the FPC algorithm called pFPC. On a 4-core 3 GHz Xeon system, pFPC exceeds 10 gigabits per second both in compression and decompression throughput while still reaching a compression ratio of 18%, which is reasonable for their double-precision floating-point datasets. At half this throughput, it achieves a 41% compression ratio. Moreover, the algorithm scales well to four cores and promises even higher throughputs on larger machines. Additional results and a description of the pFPC algorithm have recently been published in the proceedings of the Data Compression Conference. The C source code of pFPC is also publicly available.

97 MATHEMATICS AND COMPUTING↗

Implementation and Initial Testing of Advanced Processing and Analysis Algorithms for Correlated Neutron Counting

In order to improve the accuracy and capabilities of neutron multiplicity counting, additional quantifiable information is needed in order to address the assumptions that are present in the point model. Extracting and utilizing higher order moments (Quads and Pents) from the neutron pulse train represents the most direct way of extracting additional information from the measurement data to allow for an improved determination of the physical properties of the item of interest. The extraction of higher order moments from a neutron pulse train required the development of advanced dead time correction algorithms which could correct for dead time effects in all of the measurement moments in a self-consistent manner. In addition, advanced analysis algorithms have been developed to address specific assumptions that are made within the current analysis model, namely that all neutrons are created at a single point within the item of interest, and that all neutrons that are produced within an item are created with the same energy distribution. This report will discuss the current status of implementation and initial testing of the advanced dead time correction and analysis algorithms that have been developed in an attempt to utilize higher order moments to improve the capabilities of correlated neutron measurement techniques.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

A distributed scheduling algorithm for heterogeneous real-time systems

Much of the previous work on load balancing and scheduling in distributed environments was concerned with homogeneous systems and homogeneous loads. Several of the results indicated that random policies are as effective as other more complex load allocation policies. The effects of heterogeneity on scheduling algorithms for hard real time systems is examined. A distributed scheduler specifically to handle heterogeneities in both nodes and node traffic is proposed. The performance of the algorithm is measured in terms of the percentage of jobs discarded. While a random task allocation is very sensitive to heterogeneities, the algorithm is shown to be robust to such non-uniformities in system components and load.

Zeineldine, Osman↗

Mapping Snow Grain Size over Greenland from MODIS

This paper presents a new automatic algorithm to derive optical snow grain size (SGS) at 1 km resolution using Moderate Resolution Imaging Spectroradiometer (MODIS) measurements. Differently from previous approaches, snow grains are not assumed to be spherical but a fractal approach is used to account for their irregular shape. The retrieval is conceptually based on an analytical asymptotic radiative transfer model which predicts spectral bidirectional snow reflectance as a function of the grain size and ice absorption. The analytical form of solution leads to an explicit and fast retrieval algorithm. The time series analysis of derived SGS shows a good sensitivity to snow metamorphism, including melting and snow precipitation events. Preprocessing is performed by a Multi-Angle Implementation of Atmospheric Correction (MAIAC) algorithm, which includes gridding MODIS data to 1 km resolution, water vapor retrieval, cloud masking and an atmospheric correction. MAIAC cloud mask (CM) is a new algorithm based on a time series of gridded MODIS measurements and an image-based rather than pixel-based processing. Extensive processing of MODIS TERRA data over Greenland shows a robust performance of CM algorithm in discrimination of clouds over bright snow and ice. As part of the validation analysis, SGS derived from MODIS over selected sites in 2004 was compared to the microwave brightness temperature measurements of SSM\I radiometer, which is sensitive to the amount of liquid water in the snowpack. The comparison showed a good qualitative agreement, with both datasets detecting two main periods of snowmelt. Additionally, MODIS SGS was compared with predictions of the snow model CROCUS driven by measurements of the automatic whether stations of the Greenland Climate Network. We found that CROCUS grain size is on average a factor of two larger than MODIS-derived SGS. Overall, the agreement between CROCUS and MODIS results was satisfactory, in particular before and during the first melting period in mid-June. Following detailed time series analysis of SGS for four permanent sites, the paper presents SGS maps over the Greenland ice sheet for the March-September period of 2004.

Lyapustin, Alexei↗

Second-order time evolution of P{sub N} equations for radiation transport

Using polynomials to represent the angular variation of the radiation intensity is usually referred to as the P{sub N} or spherical harmonics method. For infinite order, the representation is an exact solution of the radiation transport solution. For finite N, in some physical situations there are oscillations in the solution that can make the radiation energy density be negative. For small N, the oscillations may be large enough to force the material temperature to numerically have non-physical negative values. The second-order time evolution algorithm presented here allows for more accurate solutions with larger time steps; however, it also can resolve the negativities that first-order time solutions smear out. Therefore, artificial scattering is studied to see how it can be used to decrease the oscillations in low-order solutions and prevent negativities. Small amounts of arbitrary, non-physical scattering can significantly improve the accuracy of the solution to test problems. Flux-limited diffusion solutions can also be improved by including artificial scattering. One- and two-dimensional test results are presented.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Synchronized Wireless Measurement of High-Voltage Power System Frequency Using Mobile Embedded Systems

This paper focuses on synchronized wireless measurement of high-voltage (HV) power system frequency using mobile embedded systems (MESs) integrated with a wireless electric field sensor (WEFS). Unlike traditional synchronized frequency measurement devices, which rely on potential transformers and current transformers physically connected to system elements, a WEFS is used to realize wireless signal acquisition in the vicinity of any HV apparatus. The MES performs real-time frequency estimation using a recursive discrete Fourier transform based algorithm. Network time protocol (NTP) is used for time synchronization, increasing the system flexibility by eliminating global positioning system reliance. An NTP-based synchronized sampling control method is proposed and implemented in MES to compensate the sampling time error caused by local time drift and division residue. The proposed system has the advantages of portability and lower cost, making it highly accessible and useful for a wide array of synchronized frequency measurement applications. Experiment results verify the accuracy and effectiveness of the proposed system.

24 POWER TRANSMISSION AND DISTRIBUTION↗