SEARCH · Search NASA

Results for “Arithmetic”

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.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 145 records · Page 8

All sources NASA NTRS DOE OSTI

DOE OSTI2017

A Work-Efficient Parallel Sparse Matrix-Sparse Vector Multiplication Algorithm

We design and develop a work-efficient multithreaded algorithm for sparse matrix-sparse vector multiplication (SpMSpV) where the matrix, the input vector, and the output vector are all sparse. SpMSpV is an important primitive in the emerging GraphBLAS standard and is the workhorse of many graph algorithms including breadth-first search, bipartite graph matching, and maximal independent set. As thread counts increase, existing multithreaded SpMSpV algorithms can spend more time accessing the sparse matrix data structure than doing arithmetic. Our shared-memory parallel SpMSpV algorithm is work efficient in the sense that its total work is proportional to the number of arithmetic operations required. The key insight is to avoid each thread individually scan the list of matrix columns. Our algorithm is simple to implement and operates on existing column-based sparse matrix formats. It performs well on diverse matrices and vectors with heterogeneous sparsity patterns. A high-performance implementation of the algorithm attains up to 15x speedup on a 24-core Intel Ivy Bridge processor and up to 49x speedup on a 64-core Intel KNL manycore processor. In contrast to implementations of existing algorithms, the performance of our algorithm is sustained on a variety of different input types include matrices representing scale-free and high-diameter graphs.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2020

Reducing Communication in Graph Neural Network Training

Graph Neural Networks (GNNs) are powerful and flexible neural networks that use the naturally sparse connectivity information of the data. GNNs represent this connectivity as sparse matrices, which have lower arithmetic intensity and thus higher communication costs compared to dense matrices, making GNNs harder to scale to high concurrencies than convolutional or fully-connected neural networks. Here, we introduce a family of parallel algorithms for training GNNs and show that they can asymptotically reduce communication compared to previous parallel GNN training methods. We implement these algorithms, which are based on 1D, 1. 5D, 2D, and 3D sparse-dense matrix multiplication, using torch.distributed on GPU-equipped clusters. Our algorithms optimize communication across the full GNN training pipeline. We train GNNs on over a hundred GPUs on multiple datasets, including a protein network with over a billion edges.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2016

SU-D-206-02: Evaluation of Partial Storage of the System Matrix for Cone Beam Computed Tomography Using a GPU Platform

Purpose: Iterative reconstruction algorithms in computed tomography (CT) require a fast method for computing the intersections between the photons’ trajectories and the object, also called ray-tracing or system matrix computation. This work evaluates different ways to store the system matrix, aiming to reconstruct dense image grids in reasonable time. Methods: We propose an optimized implementation of the Siddon’s algorithm using graphics processing units (GPUs) with a novel data storage scheme. The algorithm computes a part of the system matrix on demand, typically, for one projection angle. The proposed method was enhanced with accelerating options: storage of larger subsets of the system matrix, systematic reuse of data via geometric symmetries, an arithmetic-rich parallel code and code configuration via machine learning. It was tested on geometries mimicking a cone beam CT acquisition of a human head. To realistically assess the execution time, the ray-tracing routines were integrated into a regularized Poisson-based reconstruction algorithm. The proposed scheme was also compared to a different approach, where the system matrix is fully pre-computed and loaded at reconstruction time. Results: Fast ray-tracing of realistic acquisition geometries, which often lack spatial symmetry properties, was enabled via the proposed method. Ray-tracing interleaved with projection and backprojection operations required significant additional time. In most cases, ray-tracing was shown to use about 66 % of the total reconstruction time. In absolute terms, tracing times varied from 3.6 s to 7.5 min, depending on the problem size. The presence of geometrical symmetries allowed for non-negligible ray-tracing and reconstruction time reduction. Arithmetic-rich parallel code and machine learning permitted a modest reconstruction time reduction, in the order of 1 %. Conclusion: Partial system matrix storage permitted the reconstruction of higher 3D image grid sizes and larger projection datasets at the cost of additional time, when compared to the fully pre-computed approach. This work was supported in part by the Fonds de recherche du Quebec - Nature et technologies (FRQ-NT). The authors acknowledge partial support by the CREATE Medical Physics Research Training Network grant of the Natural Sciences and Engineering Research Council of Canada (Grant No. 432290).

60 APPLIED LIFE SCIENCES↗

DOE OSTI2016

SU-F-T-571: Objective Assessment of 3D Dosimetry for Flattened and Flattened Filter Free Stereotactic Rotational Delivery Using 729-Array Detector with Octavius 4D Phantom

Purpose: The purpose of this study was to assess the potential of 3D dosimetry for flattened and flattened filter free stereotactic rotational delivery in high definition MLC using 729-detector array with Octavius 4D phantom Methods: Twenty rapid arc plans were assessed for this study. For each patient two plans for 6X and 6FFF photon beams were generated with same prescription and critical organ constraints in Eclipse TPS version 13.0 using high definition MLC. Verification plans were generated in scanned Octavius 4D phantom in TPS. 3D dose measurements were collected from 729-ion chamber detector array in Octavius 4D phantom using verisoft software v 6.0. TPS calculated dose was compared with measured 3D dose in verisoft using the following gamma analysis parameters such as 3D volumetric, 3D planar and 2D global gamma in transverse, sagittal and coronal planes for 3mm/3% and 2mm/2% distance to agreement criteria.Passing rate and arithmetic mean of global gamma were analysed for 2D and 3D global gamma in all planes. Results: The average number of dose points passing rate for 2D global gamma with 3mm/3% criteria in transverse, sagittal and coronal planes was 99.06%±2.89%, 98.8%±0.88% and 99.06%±91%, respectively. For 2mm/2% criteria 97.86%±2.26%, 94.49± 2.64% and 94.34%±2.9% was observed. In 3D planar global gamma with 3mm/3% was 99.53%±0.49%, 98.93%±1.03% and 99.29%±1.29%, for 2mm 2% criteria was 97.50%±2.24%, 94.5%±2.5% and 95.38%±4.5%. The maximum arithmetic mean gamma deviation of 0.505%±0.13% was observed in coronal plane for 2D global gamma with 2mm/2% criteria. The 3D volumetric gamma passing rate was observed as 99.61%±0.433% for 3mm /3% and 95.91%±2.51% for 2mm/2%. Conclusion: The objective assessment of 3D dosimetry have demonstrated that the rotational delivery accuracy for flattened and flattened filter free stereotactic plans can be verified by using Octavius system comprising with 729 ion chamber array and Octavius 4D phantom.

60 APPLIED LIFE SCIENCES↗

DOE OSTI2019

Manycore Parallel Computing for a Hybridizable Discontinuous Galerkin Nested Multigrid Method

In this work, we present a parallel computing strategy for a hybridizable discontinuous Galerkin (HDG) nested geometric multigrid (GMG) solver. Parallel GMG solvers require a combination of coarse-grain and fine-grain parallelism to improve time-to-solution performance. In this work we focus on fine-grain parallelism. We use Intel's second generation Xeon Phi (Knights Landing) manycore processor. The GMG method achieves ideal convergence rates of 0.2 or less, for high polynomial orders. A matrix free (assembly free) technique is exploited to save considerable memory usage and increase arithmetic intensity. HDG enables static condensation, and due to the discontinuous nature of the discretization, we developed a matrix vector multiply routine that does not require any costly synchronizations or barriers. Our algorithm is able to attain 80% of peak bandwidth performance for higher order polynomials. This is possible due to the data locality inherent in the HDG method. Very high performance is realized for high order schemes, due to good arithmetic intensity, which declines as the order is reduced.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2021

Rounding Error Analysis of Mixed Precision Block Householder QR Algorithms

Although mixed precision arithmetic has recently garnered interest for training dense neural networks, many other applications could benefit from the speedups and lower storage cost if applied appropriately. The growing interest in employing mixed precision computations motivates the need for rounding error analysis that properly handles behavior from mixed precision arithmetic. We develop mixed precision variants of existing Householder QR algorithms and show error analyses supported by numerical experiments.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2024

Robust Iterative Method for Symmetric Quantum Signal Processing in All Parameter Regimes

Here, this paper addresses the problem of solving nonlinear systems in the context of symmetric quantum signal processing (QSP), a powerful technique for implementing matrix functions on quantum computers. Symmetric QSP focuses on representing target polynomials as products of matrices in SU(2) that possess symmetry properties. We present a novel Newton’s method tailored for efficiently solving the nonlinear system involved in determining the phase factors within the symmetric QSP framework. Our method demonstrates rapid and robust convergence in all parameter regimes, including the challenging scenario with ill-conditioned Jacobian matrices, using standard double precision arithmetic operations. For instance, solving symmetric QSP for a highly oscillatory target function α cos(1000x) (polynomial degree ≈ 1433) takes 6 iterations to converge to machine precision when α = 0.9, and the number of iterations only increases to 18 iterations when α = 1 – 10 -9 with a highly ill-conditioned Jacobian matrix. Leveraging the matrix product state structure of symmetric QSP, the computation of the Jacobian matrix incurs a computational cost comparable to a single function evaluation. Moreover, we introduce a reformulation of symmetric QSP using real-number arithmetics, further enhancing the method’s efficiency. Extensive numerical tests validate the effectiveness and robustness of our approach, which has been implemented in the QSPPACK software package.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2017

Spatio-Temporal Data Analysis at Scale Using Models Based on Gaussian Processes

Gaussian processes are the most commonly used statistical model for spatial and spatio-temporal processes that vary continuously. They are broadly applicable in the physical sciences and engineering and are also frequently used to approximate the output of complex computer models, deterministic or stochastic. We undertook research related to theory, computation, and applications of Gaussian processes as well as some work on estimating extremes of distributions for which a Gaussian process assumption might be inappropriate. Our theoretical contributions include the development of new classes of spatial-temporal covariance functions with desirable properties and new results showing that certain covariance models lead to predictions with undesirable properties. To understand how Gaussian process models behave when applied to deterministic computer models, we derived what we believe to be the first significant results on the large sample properties of estimators of parameters of Gaussian processes when the actual process is a simple deterministic function. Finally, we investigated some theoretical issues related to maxima of observations with varying upper bounds and found that, depending on the circumstances, standard large sample results for maxima may or may not hold. Our computational innovations include methods for analyzing large spatial datasets when observations fall on a partially observed grid and methods for estimating parameters of a Gaussian process model from observations taken by a polar-orbiting satellite. In our application of Gaussian process models to deterministic computer experiments, we carried out some matrix computations that would have been infeasible using even extended precision arithmetic by focusing on special cases in which all elements of the matrices under study are rational and using exact arithmetic. The applications we studied include total column ozone as measured from a polar-orbiting satellite, sea surface temperatures over the Pacific Ocean, and annual temperature extremes at a site in New York City. In each of these applications, our theoretical and computational innovations were directly motivated by the challenges posed by analyzing these and similar types of data.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2018

Simulated Half-Precision Implementation of Blocked QR Factorization and Graph Clustering Applications

We explored half-precision implementation of blocked QR algorithms with the following motivations: 1. New GPUs perform fast half-precision arithmetic (4 to 16 times as fast as doubleprecision). 2. QR factorization is a basic linear algebra tool useful for many physics and data analysis applications. 3. Communication-avoiding, parallelizable QR algorithms already exist for talland- skinny matrices. While the standard QR algorithms are highly unstable in half-precision, our numerical simulations show that the Tall-and-Skinny QR (TSQR) algorithm can improve the backward error of QR factorization. When using subspace iteration for graph clustering applications, half-precision accuracy in forming the eigenspace is sufficient for clustering with high precision and recall for some medium-scale benchmark problems. Note that all half-precision arithmetic were simulated with conversions to single-precision floats. Therefore, the results from this work are somewhat optimistic.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2020

Completely Positive, Simple, and Possibly Highly Accurate Approximation of the Redfield Equation

Here we present a Lindblad master equation that approximates the Redfield equation, a well known master equation derived from first principles, without significantly compromising the range of applicability of the Redfield equation. Instead of full-scale coarse-graining, this approximation only truncates terms in the Redfield equation that average out over a time-scale typical of the quantum system. The first step in this approximation is to properly renormalize the system Hamiltonian, to symmetrize the gains and losses of the state due to the environmental coupling. In the second step, we swap out an arithmetic mean of the spectral density with a geometric one, in these gains and losses, thereby restoring complete positivity. This completely positive approximation, GAME (geometric-arithmetic master equation), is adaptable between its time-independent, time-dependent, and Floquet form. In the exactly solvable, three-level, Jaynes-Cummings model, we find that the error of the approximate state is almost an order of magnitude lower than that obtained by solving the coarse-grained stochastic master equation. As a test-bed, we use a ferromagnetic Heisenberg spin-chain with long-range dipole-dipole coupling between up to 25-spins, and study the differences between various master equations. We find that GAME has the highest accuracy per computational resource.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗

DOE OSTI2016

PROPERTIES OF CARBON–OXYGEN WHITE DWARFS FROM MONTE CARLO STELLAR MODELS

We investigate properties of carbon–oxygen white dwarfs with respect to the composite uncertainties in the reaction rates using the stellar evolution toolkit, Modules for Experiments in Stellar Astrophysics (MESA) and the probability density functions in the reaction rate library STARLIB. These are the first Monte Carlo stellar evolution studies that use complete stellar models. Focusing on 3 M{sub ⊙} models evolved from the pre main-sequence to the first thermal pulse, we survey the remnant core mass, composition, and structure properties as a function of 26 STARLIB reaction rates covering hydrogen and helium burning using a Principal Component Analysis and Spearman Rank-Order Correlation. Relative to the arithmetic mean value, we find the width of the 95% confidence interval to be ΔM{sub 1TP} ≈ 0.019 M{sub ⊙} for the core mass at the first thermal pulse, Δt{sub 1TP} ≈ 12.50 Myr for the age, Δlog(T{sub c}/K) ≈ 0.013 for the central temperature, Δlog(ρ{sub c}/g cm{sup −3}) ≈ 0.060 for the central density, ΔY{sub e,c} ≈ 2.6 × 10{sup −5} for the central electron fraction, ΔX{sub c}({sup 22}Ne) ≈ 5.8 × 10{sup −4}, ΔX{sub c}({sup 12}C) ≈ 0.392, and ΔX{sub c}({sup 16}O) ≈ 0.392. Uncertainties in the experimental {sup 12}C(α,γ){sup 16}O, triple-α, and {sup 14}N(p,γ){sup 15}O reaction rates dominate these variations. We also consider a grid of 1–6 M{sub ⊙} models evolved from the pre main-sequence to the final white dwarf to probe the sensitivity of the initial–final mass relation to experimental uncertainties in the hydrogen and helium reaction rates.

79 ASTRONOMY AND ASTROPHYSICS↗

DOE OSTI2018

Fault Diagnosis of Hybrid Computing Systems Using Chaotic-Map Method

Computing systems are becoming increasingly complex with nodes consisting of a combination of multi-core central processing units (CPUs), many integrated core (MIC) and graphics processing unit (GPU) accelerators. These computing units and their interconnections are subject to different classes of hardware and software faults, which should be detected to support mitigation measures. We present the chaotic-map method that uses the exponential divergence and wide Fourier properties of the trajectories, combined with memory allocations and assignments to diagnose component-level faults in these hybrid computing systems. We propose lightweight codes that utilize highly parallel chaotic-map computations tailored to isolate faults in arithmetic units, memory elements and interconnects. The diagnosis module on a node utilizes pthreads to place chaotic-map threads on CPU and MIC cores, and CUDA C and OpenCL kernels on GPU blocks. We present experimental diagnosis results on five multi-core CPUs; one MIC; and, seven GPUs with typical diagnosis run-times under a minute.

Rao, Nageswara↗

NASA NTRS1972

Extended precision software packages

A description of three extended precision packages is presented along with three small conversion subroutines which can be used in conjunction with the extended precision packages. These extended packages represent software packages written in FORTRAN 4. They contain normalized or unnormalized floating point arithmetic with symmetric rounding and arbitrary mantissa lengths, and normalized floating point interval arithmetic with appropriate rounding. The purpose of an extended precision package is to enable the user to use and manipulate numbers with large decimal places as well as those with small decimal places where precision beyond double precision is required.

Phillips, E. J.↗

NASA NTRS1973

Low-cost coding techniques for digital fault diagnosis

Published report discusses fault location properties of arithmetic codes. Criterion for effectiveness of given code is detection probability of local fault by application of checking algorithm to results of entire set of algorithms of processor. Report also presents analysis of arithmetic codes with low-cost check algorithm which possesses partial fault-location properties.

Avizienis, A. A.↗

NASA NTRS1973

Some observed seasonal changes in extratropical general circulation: A study in terms of vorticity

Extratropical eddy distributions in four months typical of the four seasons are treated in terms of temporal mean and temporal r.m.s. values of the geostrophic relative vorticity. The geographical distributions of these parameters at the 300 mb level show that the arithmetic mean fields are highly biased representatives of the extratropical eddy distributions. The zonal arithmetic means of these parameters are also presented. These show that the zonal-and-time mean relative vorticity is but a small fraction of the zonal mean of the temporal r.m.s. relative vorticity, K. The reasons for considering the r.m.s. values as the temporal normal values of vorticity in the extratropics are given in considerable detail. The parameter K is shown to be of considerable importance in locating the extratropical frontal jet streams (EFJ) in time-and-zonal average distributions. The study leads to an understanding of the seasonal migrations of the EFJ which have not been explored until now.

Srivatsangam, S.↗

NASA NTRS1976

Architecture and data processing alternatives for the TSE computer. Volume 2: Extraction of topological information from an image by the Tse computer

A simple programmable Tse processor organization and arithmetic operations necessary for extraction of the desired topological information are described. Hardware additions to this organization are discussed along with trade-offs peculiar to the tse computing concept. An improved organization is presented along with the complementary software for the various arithmetic operations. The performance of the two organizations is compared in terms of speed, power, and cost. Software routines developed to extract the desired information from an image are included.

Jones, J. R.↗

NASA NTRS1976

Applications of satellite technology for regional organizations (Project ASTRO)

The direct arithmetic processing of adaptive delta modulation (ADM) encoded signals, conversion from ADM encoded signals to pulse code modulation (PCM) encoded signals, and conversion from PCM to ADM encoded signals are discussed. It is shown that signals which are ADM encoded can be arithmetically processed directly, without first decoding. Operating on the DM bit stream, and employing only standard digital hardware, the sum, difference and product can be obtained in PCM and ADM format.

Schilling, D. L.↗

NASA NTRS1978

Suggested architecture for a specialized fluid dynamics computer

Future flow simulations in 3-D will require computers with extremely large main memories and an advantageous ratio between computer cost and arithmetic speed. Since random access memories are very expensive, a pipeline design is proposed which allows the use of much cheaper sequential devices without any sacrifice in speed for vector references (even with arbitrary spacing between successive elements). Also scalar arithmetic can be performed efficiently. The comparatively low speed of the proposed machine (about 10 to the 7th power operations per second) would be offset by a very low price per unit, making mass production possible.

Fornberg, B.↗