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 199 records · Page 11

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 ↗

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↗

Three-Dimensional Microwave Imaging of Detonation Fronts

Microwave signals provide high penetration and favorable resolution in high-explosive materials, and as a result microwave interferometry has previously been studied for the characterization of propagating detonation fronts during explosive events. This work expands on previous 1-dimensional experimental work by investigating the feasibility of detonation front imaging using a non-iterative time reversal algorithm. The results of this computational study indicate that microwave time reversal imaging can successfully resolve the shape and location of detonation fronts within the interior of high explosive materials. These results pave the way for the development of a new microwave-based diagnostic that will help to answer important questions related to HE properties.

42 ENGINEERING↗

Alignment of leading-edge and peak-picking time of arrival methods to obtain accurate source locations

The location of a radiating source can be determined by time-tagging the arrival of the radiated signal at a network of spatially distributed sensors. The accuracy of this approach depends strongly on the particular time-tagging algorithm employed at each of the sensors. If different techniques are used across the network, then the time tags must be referenced to a common fiducial for maximum location accuracy. In this report we derive the time corrections needed to temporally align leading-edge, time-tagging techniques with peak-picking algorithms. We focus on broadband radio frequency (RF) sources, an ionospheric propagation channel, and narrowband receivers, but the final results can be generalized to apply to any source, propagation environment, and sensor. Our analytic results are checked against numerical simulations for a number of representative cases and agree with the specific leading-edge algorithm studied independently by Kim and Eng (1995) and Pongratz (2005 and 2007).

97 MATHEMATICS AND COMPUTING↗

Parallel Time Integration for Constrained Optimization

The number of transistors in an average processor continues to increase, but individual clock speeds have plateaued. Those transistors are instead going into additional cores, increasing the number of different things that a processor can do at once and placing an emphasis on parallel computation. Many problems in scientific computing follow a time-evolution model, and it can be difficult to solve such problems in parallel across the temporal domain. The Multi-Grid Reduction In Time (MGRIT) algorithm, developed at Lawrence Livermore National Laboratory (LLNL), solves differential equations with a method designed specifically to take advantage of extreme numbers of processors by parallelizing across time. The Tri-diagonal MGRIT (TriMGRIT) algorithm, also developed at LLNL, is a generalization of MGRIT which enables parallel-in-time solving of a greater number of problems. Constrained optimization problems, in particular, may be solved in parallel using TriMGRIT. These consist of choosing a control function such that an objective functional is minimized, constrained by a differential-equation. We consider two such problems: applying torque to a pendulum to bring it to a gentle stop and moving a crowd of people from one distribution into another. We also perform some miscellaneous theoretical and practical research, including investigating the use of a line-search subroutine to refine intermediate TriMGRIT results and preliminary work on strategies for choosing operators for TriMGRIT to use.

97 MATHEMATICS AND COMPUTING↗

Towards physics-inspired data-driven weather forecasting: integrating data assimilation with a deep spatial-transformer-based U-NET in a case study with ERA5

Abstract. There is growing interest in data-driven weather prediction (DDWP), e.g., using convolutional neural networks such as U-NET that are trained on data from models or reanalysis. Here, we propose three components, inspired by physics, to integrate with commonly used DDWP models in order to improve their forecast accuracy. These components are (1) a deep spatial transformer added to the latent space of U-NET to capture rotation and scaling transformation in the latent space for spatiotemporal data, (2) a data-assimilation (DA) algorithm to ingest noisy observations and improve the initial conditions for next forecasts, and (3) a multi-time-step algorithm, which combines forecasts from DDWP models with different time steps through DA, improving the accuracy of forecasts at short intervals. To show the benefit and feasibility of each component, we use geopotential height at 500 hPa (Z500) from ERA5 reanalysis and examine the short-term forecast accuracy of specific setups of the DDWP framework. Results show that the spatial-transformer-based U-NET (U-STN) clearly outperforms the U-NET, e.g., improving the forecast skill by 45 %. Using a sigma-point ensemble Kalman (SPEnKF) algorithm for DA and U-STN as the forward model, we show that stable, accurate DA cycles are achieved even with high observation noise. This DDWP+DA framework substantially benefits from large (O(1000)) ensembles that are inexpensively generated with the data-driven forward model in each DA cycle. The multi-time-step DDWP+DA framework also shows promise; for example, it reduces the average error by factors of 2–3. These results show the benefits and feasibility of these three components, which are flexible and can be used in a variety of DDWP setups. Furthermore, while here we focus on weather forecasting, the three components can be readily adopted for other parts of the Earth system, such as ocean and land, for which there is a rapid growth of data and need for forecast and assimilation.

54 ENVIRONMENTAL SCIENCES↗

Analyzing and Minimizing Capacity Fade through Optimal Model-Based Control - Theory and Experimental Validation

In order to significantly expand the BEV market, and to increase the use of lithium-ion batteries in electric grids, there is a need to develop optimal charging strategies to utilize the batteries more efficiently and enable longer life. Advanced battery management systems that can calculate and implement such strategies in real time are expected to play a critical role for this purpose. This article investigates different approaches for determining model-based optimal charging profiles for batteries, and experimentally validates the gain obtained using such profiles. Optimal profiles that maximize the cycle life of the cells are implemented on 16 Ah NMC cells for 30 minutes of charge followed by 5C discharge, and the cycle life is compared to a standard 2C CC-CV charge and 5C discharge. An improvement of more than 100% in cycle life is observed experimentally, for our test conditions on this cell design. This study is the first to experimentally demonstrate that the improved extra knowledge obtained by sophisticated physics-based models results in significant improvements in battery performance when employed in a real time control algorithm.

25 ENERGY STORAGE↗

High-Purity Germanium Spectroscopy at Rates in Excess of 10^{6} Events/s

Abstract—In gamma spectroscopy, a compromise must be made between energy resolution and event-rate capability. Some foreseen nuclear material safeguards applications require a spectrometer with energy resolution typical of high purity germanium (HPGe) detectors, operated at rates up to and exceeding 106 events per second. We report the performance of an HPGe spectrometer adapted to run at such rates. Our system consists of a commercial semi-coaxial HPGe detector, a modified high-voltagerail, resistive-feedback, charge-sensitive preamplifier and a continuous waveform digitizer. Digitized waveforms are analyzed offline with a novel time-variant trapezoidal filter algorithm. Several time-invariant trapezoidal filters are run in parallel and the slowest one not rejected by instantaneous pileup conditions is used to measure each pulse height. We have attained full-widthat- half-maximum energy resolution of less than 8 keV measured at 662 keV with 1:08*106 per second incoming event rate and 38% throughput. An additional constraint on the width of the fast trigger filter removes a significant amount of edge pileup that passes the first pileup cut, reducing throughput to 26%. While better resolution has been reported by other authors, our throughput is over an order of magnitude higher than any other reported HPGe system operated at such an event rate.

germanium, semiconductor radiation detectors, gamm↗

Plaster: An Integration, Benchmark and Development Framework for Heterogeneous Metadata Normalization Methods

The recent advances in the automation of metadata normalization and the invention of a unified schema — Brick — alleviate the metadata normalization challenge for deploying portable applications across buildings. Yet, the lack of compatibility between existing metadata normalization methods precludes the possibility of comparing and combining them. While generic machine learning (ML) frameworks, such as MLJAR and OpenML, provide versatile interfaces for standard ML problems, they cannot easily accommodate the metadata normalization tasks for buildings due to the heterogeneity in the inference scope, type of data required as input, evaluation metric, and the building-specific human-in-the-loop learning procedure. We propose Plaster, an open and modular framework that incorporates existing advances in building metadata normalization. It provides unified programming interfaces for various types of learning methods for metadata normalization and defines standardized data models for building metadata and timeseries data. Thus, it enables the integration of different methods via a workflow, benchmarking of different methods via unified interfaces, and rapid prototyping of new algorithms. With Plaster, we 1) show three examples of the workflow integration, delivering better performance than individual algorithms, 2) benchmark/analyze five algorithms over five common buildings, and 3) exemplify the process of developing a new algorithm involving time series features. We believe Plaster will facilitate the development of new algorithms and expedite the adoption of standard metadata schema such as Brick, in order to enable seamless smart building applications in the future.

99 GENERAL AND MISCELLANEOUS↗

An extended trajectory-mechanics approach for calculating the path of a pressure transient: travel-time tomography

The application of a technique from quantum dynamics to the governing equation for hydraulic head leads to a trajectory-based solution that is valid for a general porous medium. The semi-analytic expressions for propagation path and velocity of a change in hydraulic head form the basis of a travel-time tomographic imaging algorithm. An application of the imaging algorithm to synthetic arrival times reveals that a cross-well inversion based upon the extended trajectories correctly reproduces the magnitude of a reference model, improving upon an existing asymptotic approach. An inversion of hydraulic head arrival times from cross-well slug tests at the Widen field site in northern Switzerland captures a general decrease in permeability with depth, which is in agreement with previous studies, but also indicates the presence of a high-permeability feature in the upper portion of the cross-well plane.

58 GEOSCIENCES↗

A Framework for Lattice QCD Calculations on GPUs

Efficient calculation of the greatest common divisor (GCD) for big integers each whose number of bits is greater than or equal to 1024 has drawn a considerable amount of attention because it can be used to detect a weakness of the RSA security infrastructure. This paper presents a parallel binary GCD algorithm and its implementation for big integers on the Intel Xeon Phi coprocessor. This algorithm is capable of computing GCDs efficiently on many pairs of big integers in parallel by utilizing all cores on a Xeon Phi coprocessor as well as taking advantage of all vector processing units of the coprocessor to speed up critical integer operations within the algorithm. Using 240 threads on a Xeon Phi coprocessor to carry out GCD calculations for a large amount of 2048-bit integers, the implementation achieves the speedup of 30 times over a sequential binary GCD algorithm implementation on a single CPU core, and it delivers twice amount of performance in comparison to the same sequential binary GCD implementation running on 240 threads of the Xeon Phi.

Winter, F. T.↗

GVT Algorithms and Discrete Event Dynamics on 128K+ Processor Cores

Parallel discrete event simulation (PDES) represents a class of codes that are challenging to scale to large number of processors due to tight global timestamp-ordering and fine-grained event execution. One of the critical factors in scaling PDES is the efficiency of the underlying global virtual time (GVT) algorithm needed for correctness of parallel execution and speed of progress. Although many GVT algorithms have been proposed previously, few have been proposed for scalable asynchronous execution and none customized to exploit one-sided communication. Moreover, the detailed performance effects of actual GVT algorithm implementations on large platforms are unknown. Here, three major GVT algorithms intended for scalable execution on high-performance systems are studied: (1) a synchronous GVT algorithm that affords ease of implementation, (2) an asynchronous GVT algorithm that is more complex to implement but can relieve blocking latencies, and (3) a variant of the asynchronous GVT algorithm, proposed and studied for the first time here, to exploit one-sided communication in extant supercomputing platforms. Performance results are presented of implementations of these algorithms on over 64,000 cores of a Cray XT5 system, exercised on a range of parameters: optimistic and conservative synchronization, fine- to medium-grained event computation, synthetic and non-synthetic applications, and different lookahead values. Performance of tens of billions of events executed per second are registered, exceeding the speeds of any known PDES engine, and showing asynchronous GVT algorithms to outperform state-of-the-art synchronous GVT algorithms. Detailed PDES-specific runtime metrics are presented to further the understanding of tightly-coupled discrete event execution dynamics on massively parallel platforms.

99 GENERAL AND MISCELLANEOUS↗

Pairwise alignment for very long nucleic acid sequences

Highlights: • The PAAVLS algorithm can be employed for alignment of very long sequences. • The PAAVLS algorithm largely reduces memory demand as the Smith–Waterman algorithm. • The running times of the PAAVLS and Smith–Waterman algorithms are comparable. Sequence alignment is one of the fundamental problems in computational biology and has numerous applications. The Smith–Waterman algorithm generates optimal local alignment for pairwise alignment task and has become a standard algorithm in its field. However, the current version of the Smith–Waterman algorithm demands a significant amount of memory and is not suitable for alignment of very long sequences. On the hand, the recent DNA sequencing technologies have produced vast amounts of biological sequences. Some nucleic acid sequences are very long and cannot employ the Smith–Waterman algorithm. To this end, this study proposes the PAAVLS algorithm that follows the dynamic programming technique employed by the Smith–Waterman algorithm and largely reduces the demand of memory. The proposed PAAVLS algorithm can be employed for alignment of very long sequences, i.e., sequences contain more than 100,000,000 nucleotides, on a personal computer. Additionally, the running time of the proposed PAAVLS algorithm is comparable with the running time of the standard Smith–Waterman algorithm.

60 APPLIED LIFE SCIENCES↗

Quantum Optimization and Approximation Algorithms

Shor's groundbreaking quantum algorithm for integer factoring provides an exponential speedup over the best-known classical algorithms. In the 20 years since Shor's algorithm was conceived, only a handful of fundamental quantum algorithmic kernels, generally providing modest polynomial speedups over classical algorithms, have been invented. To better understand the potential advantage quantum resources provide over their classical counterparts, one may consider other resources than execution time of algorithms. Quantum Approximation Algorithms direct the power of quantum computing towards optimization problems where quantum resources provide higher-quality solutions instead of faster execution times. We provide a new rigorous analysis of the recent Quantum Approximate Optimization Algorithm, demonstrating that it provably outperforms the best known classical approximation algorithm for special hard cases of the fundamental Maximum Cut graph-partitioning problem. We also develop new types of classical approximation algorithms for finding near-optimal low-energy states of physical systems arising in condensed matter by extending seminal discrete optimization techniques. Our interdisciplinary work seeks to unearth new connections between discrete optimization and quantum information science.

97 MATHEMATICS AND COMPUTING↗