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 1,675 records · Page 93

Fast synchronization-free algorithms for parallel sparse triangular solves with multiple right-hand sides

The sparse triangular solve kernels, SpTRSV and SpTRSM, are important building blocks for a number of numerical linear algebra routines. Parallelizing SpTRSV and SpTRSM on today's many-core platforms, such as GPUs, is not an easy task since computing a component of the solution may depend on previously computed components, enforcing a degree of sequential processing. As a consequence, most existing work introduces a preprocessing stage to partition the components into a group of level-sets or colour-sets so that components within a set are independent and can be processed simultaneously during the subsequent solution stage. However, this class of methods requires a long preprocessing time as well as significant runtime synchronization over-heads between the sets. To address this, we

HPC↗

MiniApp for Density Matrix Renormalization Group Hamiltonian Application Kernel

We present two miniapps that implement the core computational kernel of the DMRG++ application, a generic C++ code that implements the Density Matrix Renormalization Group (DMRG) algorithm. The DMRG++ core Kronecker multiplication kernel is formulated using a batched BLAS approach, with implementation that targets both multi-core CPUs using OpenMP and GPGPU using the MAGMA library. The kernel evaluates the matrix-vector multiplication of the target Hamiltonian matrix used in Lanczos algorithm for computing the lowest eigenvalue and eigenvector. The Hamiltonian matrix is expressed compactly as sums of Kronecker products of small dense matrices. We demonstrate improved performance of the miniapp on synthetic problem, and show the performance of the DMRG++ application using a plugin based on the miniapp. We also present an OpenMP miniapp that explores the use of nested parallel constructs to implement the Kronecker multiplication kernel, exploring the use of nested OpenMP worksharing and tasking abstractions to implement the multi-level parallel multiplication algorithm. The miniapp has been used as a co-design vehicle for evaluating features in the OpenMP-4.5 and upcoming OpenMP-5.0 standards.

Elwasif, Wael↗

Report on local data recovery approaches suitable for weather and climate prediction (Deliverable 1.3) (V.1.0)

Numerical weather and climate prediction rates as one of the scientific applications whose accuracy improvements greatly depend on the growth of the available computing power. As the number of cores in top computing facilities pushes into the millions, increasing average frequency of hardware and software failures forces users to review their algorithms and systems in order to protect simulations from breakdown. This report surveys approaches for fault-tolerance in numerical algorithms and system resilience in parallel simulations from the perspective of numerical weather and climate prediction systems. A selection of existing strategies is analyzed, featuring interpolation-restart and compressed checkpointing for the numerics, in-memory checkpointing, user-level failure mitigation-based and backup-based methods for the systems. Numerical examples showcase the performance of the techniques in addressing faults, with particular emphasis on iterative solvers for linear systems, a staple of atmospheric fluid flow solvers. The potential impact of these strategies is discussed in relation to current development of numerical weather prediction algorithms and systems towards the exascale. Trade-offs between performance, efficiency and effectiveness of resiliency strategies are analyzed and some recommendations outlined for future developments.

97 MATHEMATICS AND COMPUTING↗

Software Synthesis for High Productivity Exascale Computing

Over the three years of our project, we accomplished three key milestones: We demonstrated how ideas from generative programming and software synthesis can help support the development of bulk-synchronous distributed memory kernels. These ideas are realized in a new language called MSL, a C-like language that combines synthesis features with high level notations for array manipulation and bulk-synchronous parallelism to simplify the semantic analysis required for synthesis. We also demonstrated that these high level notations map easily to low level C code and show that the performance of this generated code matches that of handwritten Fortran. Second, we introduced the idea of solver-aided domain-specific languages (SDSLs), which are an emerging class of computer-aided programming systems. SDSLs ease the construction of programs by automating tasks such as verification, debugging, synthesis, and non-deterministic execution. SDSLs are implemented by translating the DSL program into logical constraints. Next, we developed a symbolic virtual machine called Rosette, which simplifies the construction of such SDSLs and their compilers. We have used Rosette to build SynthCL, a subset of OpenCL that supports synthesis. Third, we developed novel numeric algorithms that move as little data as possible, either between levels of a memory hierarchy or between parallel processors over a network. We achieved progress in three aspects of this problem. First we determined lower bounds on communication. Second, we compared these lower bounds to widely used versions of these algorithms, and noted that these widely used algorithms usually communicate asymptotically more than is necessary. Third, we identified or invented new algorithms for most linear algebra problems that do attain these lower bounds, and demonstrated large speed-ups in theory and practice.

97 MATHEMATICS AND COMPUTING↗

Reinforcement Learning for Load-balanced Parallel Particle Tracing

We explore an online reinforcement learning (RL) paradigm to dynamically optimize parallel particle tracing performance in distributed-memory systems. Our method combines three novel components: (1) a work donation algorithm, (2) a high-order workload estimation model, and (3) a communication cost model. First, we design an RL-based work donation algorithm. Our algorithm monitors workloads of processes and creates RL agents to donate data blocks and particles from high-workload processes to low-workload processes to minimize program execution time. The agents learn the donation strategy on the fly based on reward and cost functions designed to consider processes' workload changes and data transfer costs of donation actions. Second, we propose a workload estimation model, helping RL agents estimate the workload distribution of processes in future computations. Third, we design a communication cost model that considers both block and particle data exchange costs, helping RL agents make effective decisions with minimized communication costs. We demonstrate that our algorithm adapts to different flow behaviors in large-scale fluid dynamics, ocean, and weather simulation data. Our algorithm improves parallel particle tracing performance in terms of parallel efficiency, load balance, and costs of I/O and communication for evaluations with up to 16,384 processors.

Distributed and parallel particle tracing↗

ExaSGD: 2022 Kernel Thrust Activities

The Kernel Thrust milestone ADSE22-407 covers the development of device-capable optimization algorithms and solvers technologies required by the ExaSGD project’s software stack in order to solve security-constrained alternating current optimal power flow (SC-ACOPF) problems on emerging exascale architectures. To this extent, in FY22 the main objective of the Kernel Thrust was (i) provide sparse optimization solver that runs efficiently on hardware accelerator devices (i.e., NVIDIA and AMD GPUs) to perform intra-node computations, (ii) strengthen the reliability and increase the performance of the mixed-dense sparse (MDS) solver of HiOp for deployment on the FY22 target architectures, Summit and Crusher, and (iii) increase performance by improving the mathematical algorithm and refining the parallel MPI-based implementation of the coarse-grain parallel solver HiOp-PriDec for capabilities deployment on the FY22 target architectures, Summit and Crusher. This document presents the developments and contributions done by the Kernels Thrust Team in FY22 toward completion of the above-mentioned objectives. These contributions progressed along four main development (sub)thrusts: (1) Design and implementation of a sparse optimization solver for use on hardware accelerators; (2) Improvement of the mathematical algorithm and of the parallel implementation of HiOp-PriDec to ensure readiness and efficient coarse-grain parallelism for FY23 target exascale machine; and (3) Support Software and Application Development Thrusts of the exaSGD project in their deployment of the project’s software stack on AMD- and NVIDIA-based architectures. The development of the sparse optimization solver (thrust 1 above) was new in FY22 and resulted in a new sparse solver in HiOp (available as of version 0.6). The second development thrust was a continuation of the efforts from FY21 and improved the mathematical algorithm and the communication strategy of the HiOp-PriDec solver. The last developement thrust is a large collaborative effort. Namely, the project’s teams from multiple labs (LLNL, PNNL, ORNL, and NREL) performed large-scale demonstration of the ExaSGD software stack, namely the optimization solvers of HiOp interfaced with the modeling front-end ExaGO and the stochastic sampler PowerScenarios. These demonstration efforts solved large-scale instances of the SC-ACOPF challenge problem of medium network sizes (10, 000-bus system) and large number of contingencies on Summit (NVIDIA accelerators) and Crusher (AMD accelerators) systems at ORNL.

97 MATHEMATICS AND COMPUTING↗

Algorithm 1028: VTMOP: Solver for Blackbox Multiobjective Optimization Problems

VTMOP is a Fortran 2008 software package containing two Fortran modules for solving computationally expensive bound-constrained blackbox multiobjective optimization problems. VTMOP implements the algorithm of [32], which handles two or more objectives, does not require any derivatives, and produces well-distributed points over the Pareto front. The first module contains a general framework for solving multiobjective optimization problems by combining response surface methodology, trust region methodology, and an adaptive weighting scheme. The second module features a driver subroutine that implements this framework when the objective functions can be wrapped as a Fortran subroutine. Lastly, support is provided for both serial and parallel execution paradigms, and VTMOP is demonstrated on several test problems as well as one real-world problem in the area of particle accelerator optimization.

97 MATHEMATICS AND COMPUTING↗

MASSIVE HYBRID PARALLELISM FOR FULLY IMPLICIT MULTIPHYSICS

As hardware advances continue to modify the supercomputing landscape, traditional scientific software development practices will become more outdated, ineffective, and inefficient. The process of rewriting/retooling existing software for new architectures is a Sisyphean task, and results in substantial hours of development time, effort, and money. Software libraries which provide an abstraction of the resources provided by such architectures are therefore essential if the computational engineering and science communities are to continue to flourish in this modern computing environment. The Multiphysics Object Oriented Simulation Environment (MOOSE) framework enables complex multiphysics analysis tools to be built rapidly by scientists, engineers, and domain specialists, while also allowing them to both take advantage of current HPC architectures, and efficiently prepare for future supercomputer designs. MOOSE employs a hybrid shared-memory and distributed-memory parallel model and provides a complete and consistent interface for creating multiphysics analysis tools. In this paper, a brief discussion of the mathematical algorithms underlying the framework and the internal object-oriented hybrid parallel design are given. Representative massively parallel results from several applications areas are presented, and a brief discussion of future areas of research for the framework are provided.

97 MATHEMATICS AND COMPUTING↗

Parallel Multivariate Spatio-Temporal Clustering of Large Ecological Datasets on Hybrid Supercomputers

A proliferation of data from vast networks of remote sensing platforms (satellites, unmanned aircraft systems (UAS), airborne etc.), observational facilities (meteorological, eddy covariance etc.), state-of-the-art sensors, and simulation models offer unprecedented opportunities for scientific discovery. Unsupervised classification is a widely applied data mining approach to derive insights from such data. However, classification of very large data sets is a complex computational problem that requires efficient numerical algorithms and implementations on high performance computing (HPC) platforms. Additionally, increasing power, space, cooling and efficiency requirements has led to the deployment of hybrid supercomputing platforms with complex architectures and memory hierarchies like the Titan system at Oak Ridge National Laboratory. The advent of such accelerated computing architectures offers new challenges and opportunities for big data analytics in general and specifically, large scale cluster analysis in our case. Although there is an existing body of work on parallel cluster analysis, those approaches do not fully meet the needs imposed by the nature and size of our large data sets. Moreover, they had scaling limitations and were mostly limited to traditional distributed memory computing platforms. We present a parallel Multivariate Spatio-Temporal Clustering (MSTC) technique based on k-means cluster analysis that can target hybrid supercomputers like Titan. We developed a hybrid MPI, CUDA and OpenACC implementation that can utilize both CPU and GPU resources on computational nodes. We describe performance results on Titan that demonstrate the scalability and efficacy of our approach in processing large ecological data sets.

Sreepathi, Sarat↗

How to estimate the 3D power spectrum of the Lyman-α forest

Here, we derive and numerically implement an algorithm for estimating the 3D power spectrum of the Lyman-α (Lyα) forest flux fluctuations. The algorithm exploits the unique geometry of Lyα forest data to efficiently measure the cross-spectrum between lines of sight as a function of parallel wavenumber, transverse separation and redshift. We start by approximating the global covariance matrix as block-diagonal, where only pixels from the same spectrum are correlated. We then compute the eigenvectors of the derivative of the signal covariance with respect to cross-spectrum parameters, and project the inverse-covariance-weighted spectra onto them. This acts much like a radial Fourier transform over redshift windows. The resulting cross-spectrum inference is then converted into our final product, an approximation of the likelihood for the 3D power spectrum expressed as second order Taylor expansion around a fiducial model. We demonstrate the accuracy and scalability of the algorithm and comment on possible extensions. Our algorithm will allow efficient analysis of the upcoming Dark Energy Spectroscopic Instrument dataset.

79 ASTRONOMY AND ASTROPHYSICS↗

Distributed-Memory Parallel Symmetric Nonnegative Matrix Factorization

We develop the first distributed-memory parallel implementation of Symmetric Nonnegative Matrix Factorization (SymNMF), a key data analytics kernel for clustering and dimensionality reduction. Our implementation includes two different algorithms for SymNMF, which give comparable results in terms of time and accuracy. The first algorithm is a parallelization of an existing sequential approach that uses solvers for non symmetric NMF. The second algorithm is a novel approach based on the Gauss-Newton method. It exploits second-order information without incurring large computational and memory costs. We evaluate the scalability of our algorithms on the Summit system at Oak Ridge National Laboratory, scaling up to 128 nodes (4,096 cores) with 70% efficiency. Additionally, we demonstrate our software on an image segmentation task.

Eswar, Srinivas↗

A New Class of AMG Interpolation Methods Based on Matrix-Matrix Multiplications

A new class of distance-two interpolation methods for algebraic multigrid (AMG) that can be formulated in terms of sparse matrix-matrix multiplications is presented and analyzed. Compared with similar distance-two prolongation operators, the proposed algorithms exhibit improved efficiency and portability to various computing platforms, since they allow one to easily exploit existing high-performance sparse matrix kernels. The new interpolation methods have been implemented in hypre, a widely used parallel multigrid solver library. With the proposed interpolations, the overall time of hypre's BoomerAMG setup can be considerably reduced, while sustaining equivalent, sometimes improved, convergence rates. Numerical results for a variety of test problems on parallel machines are presented that support the superiority of the proposed interpolation operators over the existing ones in hypre.

97 MATHEMATICS AND COMPUTING↗

Pairwise Sequence Alignment Library

Vector extensions, such as SSE, have been part of the x86 CPU since the 1990s, with applications in graphics, signal processing, and scientific applications. Although many algorithms and applications can naturally benefit from automatic vectorization techniques, there are still many that are difficult to vectorize due to their dependence on irregular data structures, dense branch operations, or data dependencies. Sequence alignment, one of the most widely used operations in bioinformatics workflows, has a computational footprint that features complex data dependencies. The trend of widening vector registers adversely affects the state-of-the-art sequence alignment algorithm based on striped data layouts. Therefore, a novel SIMD implementation of a parallel scan-based sequence alignment algorithm that can better exploit wider SIMD units was implemented as part of the Parallel Sequence Alignment Library (parasail). Parasail features: Reference implementations of all known vectorized sequence alignment approaches. Implementations of Smith Waterman (SW), semi-global (SG), and Needleman Wunsch (NW) sequence alignment algorithms. Implementations across all modern CPU instruction sets including AVX2 and KNC. Language interfaces for C/C++ and Python.

Jeff Daily, PNNL↗

PyJMAK: An Open-Source Python Toolkit for Modeling Solid-State Metallurgical Phase Transformations

Accurate prediction of metallurgical phase transformations is an essential basis for autonomous optimization and rapid part qualification. Several methods can be used to estimate the evolution of phase fractions such as JMAK kinetics-based models, phase-field models, thermodynamic models, and data-driven machine learning models. Thermodynamic and phase-field-based methodologies solve multiphysics equations requiring numerous calibration parameters and significant computational resources. As a result, the computation domain is limited to a point or on order of micron-meters. The data-driven models rely on large datasets from experiments and simulations. While the JMAK model only provides information about phase fraction evolution, it can predict this evolution in near real-time using thermal history and thermodynamic data without restriction on the domain. JMAK models have been popularly used by researchers to model phase transformations occuring during additive manufacturing or over arbitrary temperature profiles. Commercial proprietary software such as Abaqus and Ansys or closed-source in-house implementations offer the ability to model JMAK based kinetics to predict phase transformation. However, these software packages are not open-source or freely available for use and development in conjunction with manufacturing machines, sensors, and machine learning algorithms. In addition, the use of the model is restricted by a license token. In contrast, given temperature profiles at multiple points in the domain, this Python-based PyJMAK model can compute phase evolution in parallel due to its stand-alone modular, voxel-based structure, and it can be executed on high-performance computing resources without any license restrictions.

Prabhune, Bhagya [Oak Ridge National Laboratory (O↗

Collaborative Research: Continuous Dynamic Grid Adaptation in a Global Atmospheric Model - Application and Refinement

This project had goals of advancing the performance capabilities of the numerical general circulation model EULAG and using it to produce a fully operational atmospheric global climate model (AGCM) that can employ either static or dynamic grid stretching for targeted phenomena. The resulting AGCM combined EULAG's advanced dynamics core with the "physics" of the NCAR Community Atmospheric Model (CAM). Effort discussed below shows how we improved model performance and tested both EULAG and the coupled CAM-EULAG in several ways to demonstrate the grid stretching and ability to simulate very well a wide range of scales, that is, multi-scale capability. We leveraged our effort through interaction with an international EULAG community that has collectively developed new features and applications of EULAG, which we exploited for our own work summarized here. Overall, the work contributed to over 40 peer-reviewed publications and over 70 conference/workshop/seminar presentations, many of them invited. 3a. EULAG Advances EULAG is a non-hydrostatic, parallel computational model for all-scale geophysical flows. EULAG's name derives from its two computational options: EULerian (flux form) or semi-LAGrangian (advective form). The model combines nonoscillatory forward-in-time (NFT) numerical algorithms with a robust elliptic Krylov solver. A signature feature of EULAG is that it is formulated in generalized time-dependent curvilinear coordinates. In particular, this enables grid adaptivity. In total, these features give EULAG novel advantages over many existing dynamical cores. For EULAG itself, numerical advances included refining boundary conditions and filters for optimizing model performance in polar regions. We also added flexibility to the model's underlying formulation, allowing it to work with the pseudo-compressible equation set of Durran in addition to EULAG's standard anelastic formulation. Work in collaboration with others also extended the demonstrated range of validity of soundproof models, showing that they are more broadly applicable than some had previously thought. Substantial testing of EULAG included application and extension of the Jablonowski-Williamson baroclinic wave test - an archetype of planetary weather - and further analysis of multi-scale interactions arising from collapse of temperature fronts in both the baroclinic wave test and simulations of the Held-Suarez idealized climate. These analyses revealed properties of atmospheric gravity waves not seen in previous work and further demonstrated the ability of EULAG to simulate realistic behavior over several orders of magnitude of length scales. Additional collaborative work enhanced capability for modeling atmospheric flows with adaptive moving meshes and demonstrated the ability of EULAG to move into petascale computing. 3b. CAM-EULAG Advances We have developed CAM-EULAG in collaboration with former project postdoc, now University of Cape Town Assistant Professor, Babatunde Abiodun. Initial study documented good model performance in aqua-planet simulations. In particular, we showed that the grid adaptivity (stretching) implemented in CAM-EULAG allows higher resolution in selected regions without causing anomalous behavior such as spurious wave reflection. We then used the stretched-grid version to analyze simulated extreme precipitation events in West Africa, comparing the precipitation and event environment with observed behavior. The model simulates fairly well the spatial scale and the interannual and intraseasonal variability of the extreme events, although its extreme precipitation intensity is weaker than observed. In addition, both observations and the simulations show possible forcing of extreme events by African easterly waves. 3c. Other Contributions Through our collaborations, we have made contributions to a wide range of outcomes. For research focused on terrestrial behavior, these have included (1) upwind schemes for gas dynamics, (2) a nonlinear perspective on the dynamics of the Madden-Julian Oscillation, (3) numerical realism of thermal convection, (4) extreme precipitation processes, (5) unstructured meshes, (6) porous-media analogies for simulating flow in urban environments, (7) Monge-Ampere enhancements of semi-Lagrangian methods and (8) further extensions of the generality of EULAG applications to geophysical problems. The generality of EULAG for multi-scale flow was also demonstrated through solar applications. Simulations of solar magnetohydrodynamics showed that EULAG produces the solar cycle fairly well. Although the model's solar cycle is significantly longer than observed, it shows remarkable agreement with observations in features of spatial evolution. These efforts in environments that are extreme from a geophysical perspective have helped to establish the robustness of EULAG as an all-scale code for geophysical applications.

54 ENVIRONMENTAL SCIENCES↗

Developing new architectures for the Block 2 VLBI correlator system

The overall LSI (large-scale integrated circuits) architecture design and current status of the VBLI (very long baseline interferometry) block 2 correlator is addressed. The VBLI correlator algorithms demand a computing system that provides a throughput of hundreds of millions of instructions per second to perform cross-correlation detection for six baselines. The LSI technology lights the way for the computation of complex parallel process and is raising the upper bound of computerization.

Peterson, J. C.↗

On the inversion of block tridiagonals without storage constraints

A strategy was developed to permit trade-offs between the number of floating point operations required and the storage requirements for the solution of certain difference problems, such as block tridiagonal systems of equations. This is done by recomputing some intermediate results instead of storing them. Reducing the storage to the square root of the current requirement roughly doubles the number of computations. Reducing the storage more than this tends to make the number of computations prohibitively large. In theory, if m is the order of each sub-matrix in the block tridiagonal matrix, one can solve any linear system with only 5m(2) + 1 temporary storage cells. In many cases m is a constant and quite small. For example, in solving a factored form of the three-dimensional Navier-Stokes equations, the size m of the block tridiagonals is 5. This method lends itself to efficient use on computers with parallel processing or vector processing architectures. On these computers the larger number of floating point operations is more than offset by the decrease in I/O and the increased percentage of vector operations made possible by this algorithm.

Merriam, M. L.↗

On the factorization of block-tridiagonals without storage constraints

In many programs solving difference equations, problem size is restricted by the number of available memory cells. A strategy has been developed to permit trade-offs between the number of floating point operations required and storage requirements for the solution of certain problems such as block tridiagonal systems of equations. This is done by recomputing some intermediate results instead of storing them. Reducing the storage to the square root of the current requirement will roughly double the number of computations. In theory, if m is the order of each sub-matrix in the block tridiagonal matrix, one can solve any linear system with only 5 sq m + 1 temporary storage cells. This method lends itself to efficient use on computers with parallel processing or vector processing architectures. On these computers the larger number of floating point operations is more than offset by the decrease in I/O and the increased percentage of vector operations made possible by this algorithm.

Merriam, M. L.↗