Search NASA⌕ Search

SEARCH · Search NASA

Results for “parallel computing algorithms”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

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

At least 955 records · Page 53

ParNCL and ParGAL: Data-parallel Tools for Postprocessing of Large-scale Earth Science Data

Earth science high-performance applications often require extensive analysis of their output in order to complete the scien- tific goals or produce a visual image or animation. Often this analysis cannot be done in situ because it requires calculating time-series statistics from state sampled over the entire length of the run or analyzing the relationship between similar time series from previous simulations or observations. Many of the tools used for this postprocessing are not themselves high- performance applications, but the new Parallel Gridded Analysis Library (ParGAL) provides high-performance data-parallel versions of several common analysis algorithms for data from a structured or unstructured grid simulation. The library builds on several scalable systems, including the Mesh Oriented DataBase (MOAB), a library for representing mesh data that sup- ports structured, unstructured finite element, and polyhedral grids; the Parallel-NetCDF (PNetCDF) library; and Intrepid, an extensible library for computing operators (such as gradient, curl, and divergence) acting on discretized fields. We have used ParGAL to implement a parallel version of the NCAR Command Language (NCL) a scripting language widely used in the climate community for analysis and visualization. The data-parallel algorithms in ParGAL/ParNCL are both higher performing and more flexible than their serial counterparts.

97 MATHEMATICS AND COMPUTING↗

Virtual Time III, Part 2: Combining Conservative and Optimistic Synchronization

This is Part 2 of a trio of works intended to provide a unifying framework in which conservative and optimistic synchronization for parallel discrete event simulations can be freely and transparently combined in the same logical process on an event-by-event basis. Here, in this article, we continue the outline of an approach called Unified Virtual Time (UVT) that was introduced in Part 1, showing in detail via two extended examples how conservative synchronization can be refactored and combined with optimistic synchronization in the UVT framework. We describe UVT versions of both a basic time windowing algorithm called Unified Simple Time Windows and a refactored version of the Chandy-Misra-Bryant Null Message algorithm called Unified CMB.

97 MATHEMATICS AND COMPUTING↗

Time parallelization of plasma simulations using the parareal algorithm

Simulation of fusion plasmas involve a broad range of timescales. In magnetically confined plasmas, such as in ITER, the timescale associated with the microturbulence responsible for transport and confinement timescales vary by an order of 10^6 10^9. Simulating this entire range of timescales is currently impossible, even on the most powerful supercomputers available. Space parallelization has so far been the most common approach to solve partial differential equations. Space parallelization alone has led to computational saturation for fluid codes, which means that the walltime for computaion does not linearly decrease with the increasing number of processors used. The application of the parareal algorithm to simulations of fusion plasmas ushers in a new avenue of parallelization, namely temporal parallelization. The algorithm has been successfully applied to plasma turbulence simulations, prior to which it has been applied to other relatively simpler problems. This work explores the extension of the applicability of the parareal algorithm to ITER relevant problems, starting with a diffusion-convection model.

Samaddar, D.↗

Multithreaded Algorithms for Graph Coloring

Graph algorithms are challenging to parallelize when high performance and scalability are primary goals. Low concurrency, poor data locality, irregular access pattern, and high data access to computation ratio are among the chief reasons for the challenge. The performance implication of these features is exasperated on distributed memory machines. More success is being achieved on shared-memory, multi-core architectures supporting multithreading. We consider a prototypical graph problem, coloring, and show how a greedy algorithm for solving it can be e*ectively parallelized on multithreaded architectures. We present in particular two di*erent parallel algorithms. The first relies on speculation and iteration, and is suitable for any shared-memory, multithreaded system. The second uses data ow principles and is targeted at the massively multithreaded Cray XMT system. We benchmark the algorithms on three di*erent platforms and demonstrate scalable runtime performance. In terms of quality of solution, both algorithms use nearly the same number of colors as the serial algorithm.

Catalyurek, Umit V↗

Analysis of a parallelized nonlinear elliptic boundary value problem solver with application to reacting flows

A parallelized finite difference code based on the Newton method for systems of nonlinear elliptic boundary value problems in two dimensions is analyzed in terms of computational complexity and parallel efficiency. An approximate cost function depending on 15 dimensionless parameters is derived for algorithms based on stripwise and boxwise decompositions of the domain and a one-to-one assignment of the strip or box subdomains to processors. The sensitivity of the cost functions to the parameters is explored in regions of parameter space corresponding to model small-order systems with inexpensive function evaluations and also a coupled system of nineteen equations with very expensive function evaluations. The algorithm was implemented on the Intel Hypercube, and some experimental results for the model problems with stripwise decompositions are presented and compared with the theory. In the context of computational combustion problems, multiprocessors of either message-passing or shared-memory type may be employed with stripwise decompositions to realize speedup of O(n), where n is mesh resolution in one direction, for reasonable n.

Keyes, David E.↗

A parallelized elliptic solver for reacting flows

A modified Newton algorithm for the solution of nonlinear elliptic boundary value problems via finite discretization methods is presented. A serial implementation of this algorithm which has recently been applied successfully to the computation of an axisymmetric over-ventilated subsonic laminar methane-air jet diffusion flame is described. Parallel implementation issues and a complexity theory are presented. Included as well are actual performance data for model systems obtained on the Intel Hypercube and a discussion of its implications for modeling realistic systems.

Keyes, David E.↗

Algorithms for Efficient Reproducible Floating Point Summation

We define “reproducibility” as getting bitwise identical results from multiple runs of the same program, perhaps with different hardware resources or other changes that should not affect the answer. Many users depend on reproducibility for debugging or correctness. However, dynamic scheduling of parallel computing resources, combined with nonassociative floating point addition, makes reproducibility challenging even for summation, or operations like the BLAS. We describe a “reproducible accumulator” data structure (the “binned number”) and associated algorithms to reproducibly sum binary floating point numbers, independent of summation order. We use a subset of the IEEE Floating Point Standard 754-2008 and bitwise operations on the standard representations in memory. Our approach requires only one read-only pass over the data, and one reduction in parallel, using a 6-word reproducible accumulator (more words can be used for higher accuracy), enabling standard tiling optimization techniques. Summing n words with a 6-word reproducible accumulator requires approximately 9 n floating point operations (arithmetic, comparison, and absolute value) and approximately 3 n bitwise operations. The final error bound with a 6-word reproducible accumulator and our default settings can be up to 2 29 times smaller than the error bound for conventional (recursive) summation on ill-conditioned double-precision inputs.

Computer Science↗

Nonlinear Fourier analysis for discontinuous conductivities: Computational results

Two reconstruction methods of Electrical Impedance Tomography (EIT) are numerically compared for nonsmooth conductivities in the plane based on the use of complex geometrical optics (CGO) solutions to D-bar equations involving the global uniqueness proofs for Calderón problem exposed in Nachman (1996) [43] and Astala and Päivärinta (2006) [6]: the Astala–Päivärinta theory-based low-pass transport matrix method implemented in Astala et al. (2011) [3] and the shortcut method which considers ingredients of both theories. The latter method is formally similar to the Nachman theory-based regularized EIT reconstruction algorithm studied in Knudsen et al. (2009) [34] and several references from there. New numerical results are presented using parallel computation with size parameters larger than ever, leading mainly to two conclusions as follows. First, both methods can approximate piecewise constant conductivities better and better as the cutoff frequency increases, and there seems to be a Gibbs-like phenomenon producing ringing artifacts. Second, the transport matrix method loses accuracy away from a (freely chosen) pivot point located outside of the object to be studied, whereas the shortcut method produces reconstructions with more uniform quality.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Distributed non-negative matrix factorization with determination of the number of latent features

The holistic analysis and understanding of the latent (that is, not directly observable) variables and patterns buried in large datasets is crucial for data-driven science, decision making and emergency response. Such exploratory analyses require devising unsupervised learning methods for data mining and extraction of the latent features, and non-negative matrix factorization (NMF) is one of the prominent such methods. NMF is based on compute-intense non-convex constrained minimization, which, for large datasets requires fast and distributed algorithms. However, current parallel implementations of NMF fail to estimate the number of latent features. In practice, identifying these features is both difficult and significant for pattern recognition and latent feature analysis, especially for large dense matrices. Here, we introduce a distributed NMF algorithm coupled with distributed custom clustering followed by a stability analysis on dense data, which we call DnMFk, to determine the number of latent variables. The results on synthetic data and the classical Swimmer data set demonstrate the accuracy of model determination while scaling nearly linearly across multiple processors for large data. Further, we employ DnMFk to determine the number of hidden features from a terabyte matrix.

97 MATHEMATICS AND COMPUTING↗

A Monte Carlo neutron transport code for eigenvalue calculations on a dual-GPU system and CUDA environment

Monte Carlo (MC) method is able to accurately calculate eigenvalues in reactor analysis. Its lengthy computation time can be reduced by general-purpose computing on Graphics Processing Units (GPU), one of the latest parallel computing techniques under development. The method of porting a regular transport code to GPU is usually very straightforward due to the 'embarrassingly parallel' nature of MC code. However, the situation becomes different for eigenvalue calculation in that it will be performed on a generation-by-generation basis and the thread coordination should be explicitly taken care of. This paper presents our effort to develop such a GPU-based MC code in Compute Unified Device Architecture (CUDA) environment. The code is able to perform eigenvalue calculation under simple geometries on a multi-GPU system. The specifics of algorithm design, including thread organization and memory management were described in detail. The original CPU version of the code was tested on an Intel Xeon X5660 2.8 GHz CPU, and the adapted GPU version was tested on NVIDIA Tesla M2090 GPUs. Double-precision floating point format was used throughout the calculation. The result showed that a speedup of 7.0 and 33.3 were obtained for a bare spherical core and a binary slab system respectively. The speedup factor was further increased by a factor of {approx}2 on a dual GPU system. The upper limit of device-level parallelism was analyzed, and a possible method to enhance the thread-level parallelism was proposed. (authors)

22 GENERAL STUDIES OF NUCLEAR REACTORS↗

T RI M E ++: Multi-threaded triangular meshing in two dimensions

We present T RI M E ++, a multi-threaded software library designed for generating two-dimensional meshes for intricate geometric shapes using the Delaunay triangulation. Multi-threaded parallel computing is implemented throughout the meshing procedure, making it suitable for fast generation of large-scale meshes. Three iterative meshing algorithms are implemented: the DistMesh algorithm, the centroidal Voronoi diagram meshing, and a hybrid of the two. We compare the performance of the three meshing methods in T RI M E ++, and show that the hybrid method retains the advantages of the other two. The software library achieves significant parallel speedup when generating large-scale meshes containing between 10 4 to 10 7 points. T RI M E ++ can handle complicated geometries and generates adaptive meshes of high quality.

97 MATHEMATICS AND COMPUTING↗

Event recognition using signal spectrograms in long pulse experiments

As discharge duration increases, real-time complex analysis of the signal becomes more important. In this context, data acquisition and processing systems must provide models for designing experiments which use event oriented plasma control. One example of advanced data analysis is signal classification. The off-line statistical analysis of a large number of discharges provides information to develop algorithms for the determination of the plasma parameters from measurements of magnetohydrodinamic waves, for example, to detect density fluctuations induced by the Alfven cascades using morphological patterns. The need to apply different algorithms to the signals and to address different processing algorithms using the previous results necessitates the use of an event-based experiment. The Intelligent Test and Measurement System platform is an example of architecture designed to implement distributed data acquisition and real-time processing systems. The processing algorithm sequence is modeled using an event-based paradigm. The adaptive capacity of this model is based on the logic defined by the use of state machines in SCXML. The Intelligent Test and Measurement System platform mixes a local multiprocessing model with a distributed deployment of services based on Jini.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

An Explicitly Correlated Wavelet Method for the Electronic Schroedinger Equation

A discretization for an explicitly correlated formulation of the electronic Schroedinger equation based on hyperbolic wavelets and exponential sum approximations of potentials is described, covering mathematical results as well as algorithmic realization, and discussing in particular the potential of methods of this type for parallel computing.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Accurate quantum dynamics calculations using symmetrized Gaussians on a doubly dense Von Neumann lattice

In a series of earlier articles [B. Poirier, J. Theor. Comput. Chem. 2, 65 (2003); B. Poirier and A. Salam, J. Chem. Phys. 121, 1690 (2004); and ibid. 121, 1704 (2004)], a new method was introduced for performing exact quantum dynamics calculations. The method uses a 'weylet' basis set (orthogonalized Weyl-Heisenberg wavelets) combined with phase space truncation, to defeat the exponential scaling of CPU effort with system dimensionality-the first method ever able to achieve this long-standing goal. Here, we develop another such method, which uses a much more convenient basis of momentum-symmetrized Gaussians. Despite being non-orthogonal, symmetrized Gaussians are collectively local, allowing for effective phase space truncation. A dimension-independent code for computing energy eigenstates of both coupled and uncoupled systems has been created, exploiting massively parallel algorithms. Results are presented for model isotropic uncoupled harmonic oscillators and coupled anharmonic oscillators up to 27 dimensions. These are compared with the previous weylet calculations (uncoupled harmonic oscillators up to 15 dimensions), and found to be essentially just as efficient. Coupled system results are also compared to corresponding exact results obtained using a harmonic oscillator basis, and also to approximate results obtained using first-order perturbation theory up to the maximum dimensionality for which the latter may be feasibly obtained (four dimensions).

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Balanced Coloring for Parallel Computing Applications

Graph coloring is used to identify subsets of independent tasks in parallel scientific computing applications. Traditional coloring heuristics aim to reduce the number of colors used as that number also corresponds to the number of parallel steps in the application. However, if the color classes produced have a skew in their sizes, utilization of hardware resources becomes inefficient, especially for the smaller color classes. Equitable coloring is a theoretical formulation of coloring that guarantees a perfect balance among color classes, and its practical relaxation is referred to as balanced coloring. In this paper, we revisit the problem of balanced coloring in the context of parallel computing. The goal is to achieve a balanced coloring of an input graph without increasing the number of colors that an algorithm oblivious to balance would have used. We propose and study multiple heuristics that aim to achieve such a balanced coloring, present parallelization approaches for multi-core and manycore architectures, and cross-evaluate their effectiveness with respect to the quality of balance achieved and performance. Furthermore, we study the impact of the proposed balanced coloring heuristics on a concrete application - viz. parallel community detection, which is an example of an irregular application. The thorough treatment of balanced coloring presented in this paper from algorithms to application is expected to serve as a valuable resource to parallel application developers who seek to improve parallel performance of their applications using coloring.

Balanced coloring, Tilera manycore architecture, c↗

LCA

The Locally Competitive Algorithm (LCA) is a dynamical sparse solver that uses only local computations, allowing for massively parallel implementations on compatible neuromorphic architectures such as Intel's Loihi research chip. In this invention, we show how unsupervised dictionary learning with spiking LCA can be implemented on GPUs and Intel's Loihi research chip.

Parpart, Gavin↗

Modeling UV Radiation Feedback from Massive Stars. I. Implementation of Adaptive Ray-tracing Method and Tests [Modeling UV Radiation Feedback from Massive Stars: I. Implementation of Adaptive Ray Tracing Algorithm]

Here, we present an implementation of an adaptive ray-tracing (ART) module in the Athena hydrodynamics code that accurately and efficiently handles the radiative transfer involving multiple point sources on a three-dimensional Cartesian grid. We adopt a recently proposed parallel algorithm that uses nonblocking, asynchronous MPI communications to accelerate transport of rays across the computational domain. We validate our implementation through several standard test problems, including the propagation of radiation in vacuum and the expansions of various types of H II regions. Additionally, scaling tests show that the cost of a full ray trace per source remains comparable to that of the hydrodynamics update on up to $\sim {10}^{3}$ processors. To demonstrate application of our ART implementation, we perform a simulation of star cluster formation in a marginally bound, turbulent cloud, finding that its star formation efficiency is 12% when both radiation pressure forces and photoionization by UV radiation are treated. We directly compare the radiation forces computed from the ART scheme with those from the M 1 closure relation. Although the ART and M 1 schemes yield similar results on large scales, the latter is unable to resolve the radiation field accurately near individual point sources.

79 ASTRONOMY AND ASTROPHYSICS↗