SEARCH · Search NASA

Results for “parallel algorithm”

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 343 records · Page 19

All sources NASA NTRS DOE OSTI

DOE OSTI2019

Nonconforming Mesh Refinement for High-Order Finite Elements

In this study, we propose a general algorithm for nonconforming adaptive mesh refinement (AMR) of unstructured meshes in high-order finite element codes. Our focus is on $h$-refinement with a fixed polynomial order. The algorithm handles triangular, quadrilateral, hexahedral, and prismatic meshes of arbitrarily high-order curvature, for any order finite element space in the de Rham sequence. We present a flexible data structure for meshes with hanging nodes and a general procedure to construct the conforming interpolation operator, both in serial and in parallel. The algorithm and data structure allow anisotropic refinement of tensor product elements in two and three dimensions and support unlimited refinement ratios of adjacent elements. We report numerical experiments verifying the correctness of the algorithms and perform a parallel scaling study to show that we can adapt meshes containing billions of elements and run efficiently on 393,000 parallel tasks. Finally, we illustrate the integration of dynamic AMR into a high-order Lagrangian hydrodynamics solver.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2015

Update on Development of Mesh Generation Algorithms in MeshKit

MeshKit uses a graph-based design for coding all its meshing algorithms, which includes the Reactor Geometry (and mesh) Generation (RGG) algorithms. This report highlights the developmental updates of all the algorithms, results and future work. Parallel versions of algorithms, documentation and performance results are reported. RGG GUI design was updated to incorporate new features requested by the users; boundary layer generation and parallel RGG support were added to the GUI. Key contributions to the release, upgrade and maintenance of other SIGMA1 libraries (CGM and MOAB) were made. Several fundamental meshing algorithms for creating a robust parallel meshing pipeline in MeshKit are under development. Results and current status of automated, open-source and high quality nuclear reactor assembly mesh generation algorithms such as trimesher, quadmesher, interval matching and multi-sweeper are reported.

Jain, Rajeev↗

DOE OSTI2012

Integrated Network Decompositions and Dynamic Programming for Graph Optimization (INDDGO)

The INDDGO software package offers a set of tools for finding exact solutions to graph optimization problems via tree decompositions and dynamic programming algorithms. Currently the framework offers serial and parallel (distributed memory) algorithms for finding tree decompositions and solving the maximum weighted independent set problem. The parallel dynamic programming algorithm is implemented on top of the MADNESS task-based runtime.

Source record↗

DOE OSTI2012

Integrated Network Decompositions and Dynamic Programming for Graph Optimization (INDDGO)

Source record↗

DOE OSTI2018

Asynchronously parallel optimization solver for finding multiple minima

This paper proposes and analyzes an asynchronously parallel optimization algorithm for finding multiple, high-quality minima of nonlinear optimization problems. Our multistart algorithm considers all previously evaluated points when determining where to start or continue a local optimization run. Theoretical results show that, under certain assumptions, the algorithm almost surely starts a finite number of local optimization runs and identifies, or has a single local optimization run converging to, every minimum. The algorithm is applicable to general optimization settings, but our numerical results focus on the case when derivatives are unavailable. In numerical tests, a PYTHON implementation of the algorithm is shown to yield good approximations of many minima (including a global minimum), and this ability scales well with additional resources. Our implementation’s time to solution is shown also to scale well even when the time to evaluate the function evaluation is highly variable.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2010

PV output variability modeling using satellite imagery.

High frequency irradiance variability measured on the ground is caused by the formation, dissipation, and passage of clouds in the sky. If we can identify and associate different cloud types/patterns from satellite imagery, we may be able to predict irradiance variability in areas lacking sensors. With satellite imagery covering the entire U.S., this allows for more accurate integration planning and power flow modeling over wide areas. Satellite imagery from southern Nevada was analyzed at 15 minute intervals over a year. Methods for image stabilization, cloud detection, and textural classification of clouds were developed and tested. High Performance Computing parallel processing algorithms were also investigated and tested. Artificial Neural Networks using imagery as inputs were trained on ground-based measurements of irradiance to model the variability and were tested to show some promise as a means for predicting irradiance variability.

99 GENERAL AND MISCELLANEOUS↗

DOE OSTI2015

Implementation of Parallel Dynamic Simulation on Shared-Memory vs. Distributed-Memory Environments

Power system dynamic simulation computes the system response to a sequence of large disturbance, such as sudden changes in generation or load, or a network short circuit followed by protective branch switching operation. It consists of a large set of differential and algebraic equations, which is computational intensive and challenging to solve using single-processor based dynamic simulation solution. High-performance computing (HPC) based parallel computing is a very promising technology to speed up the computation and facilitate the simulation process. This paper presents two different parallel implementations of power grid dynamic simulation using Open Multi-processing (OpenMP) on shared-memory platform, and Message Passing Interface (MPI) on distributed-memory clusters, respectively. The difference of the parallel simulation algorithms and architectures of the two HPC technologies are illustrated, and their performances for running parallel dynamic simulation are compared and demonstrated.

dynamic simulation↗

DOE OSTI2019

A Scalable Hybrid Scheme for Ray-Casting of Unstructured Volume Data

We present an algorithm for parallel volume rendering that is a hybrid between classical object order and image order techniques. The algorithm operates on unstructured grids (and structured ones), and thus can deal with block boundaries interleaving in complex ways. It also deals effectively with cases that are prone to load imbalance, i.e., cases where cell sizes differ dramatically, either because of the nature of the input data, or because of the effects of the camera transformation. The algorithm divides work over resources such that each phase of its processing is bounded in the amount of computation it can perform. We demonstrate its efficacy through a series of studies, varying over camera position, data set size, transfer function, image size, and processor count. At its biggest, our experiments scaled up to 8,192 processors and operated on data sets with more than one billion cells. In total, we find that our hybrid algorithm performs well in all cases. This is because our algorithm naturally adapts its computation based on workload, and can operate like either an object order technique or an image order technique in scenarios where those techniques are efficient.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2016

Computing Maximum Cardinality Matchings in Parallel on Bipartite Graphs via Tree-Grafting

It is difficult to obtain high performance when computing matchings on parallel processors because matching algorithms explicitly or implicitly search for paths in the graph, and when these paths become long, there is little concurrency. In spite of this limitation, we present a new algorithm and its shared-memory parallelization that achieves good performance and scalability in computing maximum cardinality matchings in bipartite graphs. This algorithm searches for augmenting paths via specialized breadth-first searches (BFS) from multiple source vertices, hence creating more parallelism than single source algorithms. Algorithms that employ multiple-source searches cannot discard a search tree once no augmenting path is discovered from the tree, unlike algorithms that rely on single-source searches. We describe a novel tree-grafting method that eliminates most of the redundant edge traversals resulting from this property of multiple-source searches. We also employ the recent direction-optimizing BFS algorithm as a subroutine to discover augmenting paths faster. Our algorithm compares favorably with the current best algorithms in terms of the number of edges traversed, the average augmenting path length, and the number of iterations. Here, we provide a proof of correctness for our algorithm. Our NUMA-aware implementation is scalable to 80 threads of an Intel multiprocessor and to 240 threads on an Intel Knights Corner coprocessor. On average, our parallel algorithm runs an order of magnitude faster than the fastest algorithms available. The performance improvement is more significant on graphs with small matching number.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2012

Optimization of multigrid based elliptic solver for large scale simulations in the FLASH code: OPTIMIZATION OF MULTIGRID BASED ELLIPTIC SOLVER IN THE FLASH CODE

FLASH is a multiphysics multiscale adaptive mesh refinement (AMR) code originally designed for simulation of reactive flows often found in Astrophysics. With its wide user base and flexible applications configuration capability, FLASH has a dual task of maintaining scalability and portability in all its solvers. The scalability of fully explicit solvers in the code is tied very closely to that of the underlying mesh. Others such as the Poisson solver based on a multigrid method have more complex scaling behavior. Multigrid methods suffer from processor starvation and dominating communication costs at coarser grids with increase in the number of processors. In this paper, we propose a combination of uniform grid mesh with AMR mesh, and the merger of two different sets of solvers to overcome the scalability limitation of the Poisson solver in FLASH. The principal challenge in the proposed merger is the efficiency of the communication algorithm to map the mesh back and forth between uniform grid and AMR. We present two different parallel mapping algorithms and also discuss results from performance studies of the two implementations. Copyright © 2012 John Wiley & Sons, Ltd.

Computer Science↗

DOE OSTI2020

Machine Committee Framework for Power Grid Disturbances Analysis Using Synchrophasors Data

Events detection is a key challenge in power grid frequency disturbances analysis. Accurate detection of events is crucial for situational awareness of the power system. In this paper, we study the problem of events detection in power grid frequency disturbance analysis using synchrophasors data streams. Current events detection approaches for power grid rely on individual detection algorithm. This study integrates some of the existing detection algorithms using the concept of machine committee to develop improved detection approaches for grid disturbance analysis. Specifically, we propose two algorithms—an Event Detection Machine Committee (EDMC) algorithm and a Change-Point Detection Machine Committee (CPDMC) algorithm. Both algorithms use parallel architecture to fuse detection knowledge of its individual methods to arrive at an overall output. The EDMC algorithm combines five individual event detection methods, while the CPDMC algorithm combines two change-point detection methods. Each method performs the detection task separately. The overall output of each algorithm is then computed using a voting strategy. The proposed algorithms are evaluated using three case studies of actual power grid disturbances. Compared with the individual results of the various detection methods, we found that the EDMC algorithm is a better fit for analyzing synchrophasors data; it improves the detection accuracy; and it is suitable for practical scenarios.

24 POWER TRANSMISSION AND DISTRIBUTION↗

DOE OSTI2022

CEAZ: Accelerating Parallel I/O Via Hardware-Algorithm Co-Designed Adaptive Lossy Compression

As supercomputers continue to grow to exa-scale, the amount of data that needs to be saved or transmitted is exploding. To this end, many previous works have studied using error-bounded lossy compressors to reduce the data size and improve the I/O performance. However, little work has been done for effectively offloading lossy compression onto FPGA-based SmartNICs to reduce the compression overhead. In this paper, we propose a hardware-algorithm co-design of efficient and adaptive lossy compressor for scientific data on FPGAs (called CEAZ) to accelerate parallel I/O. Our contribution is fourfold: (1) We propose an efficient Huffman coding approach that can adaptively update Huffman codewords online based on codewords generated offline (from a variety of representative scientific datasets). (2) We derive a theoretical analysis to support a precise control of compression ratio under an error-bounded compression mode, enabling accurate offline Huffman codewords generation. This also help us create a fixed-ratio compression mode for consistent throughput. (3) We develop an efficient compression pipeline by adopting cuSZ’s dual-quantization algorithm to our hardware use case. (4) We evaluate CEAC on five real-world datasets with both a single FPGA board and 256 nodes from Bridges2 supercomputer. Experiments show that CEAZ outperforms the second-best FPGA-based lossy compressor by 2× of throughput and 9.6× of compression ratio. It also improves MPI_File_write and MPI_Gather throughputs by up to 32.7× and 31.4×, respectively.

Zhang, Chengming↗

DOE OSTI2025

TorchBraid: High-Performance Layer-Parallel Training of Deep Neural Networks with MPI and GPU Acceleration

TorchBraid is a high-performance implementation of layer-parallel training for deep neural networks (DNNs) supporting MPI-based parallelism and GPU acceleration. Layer-parallel training has been developed to overcome the serialization inherent in forward and backward propagation of DNNs that limits utilization of computational resources in the strong scaling limit. To achieve this, TorchBraid integrates the PyTorch neural network framework with the state-of-the-art XBraid time-parallel library. Furthermore, this article presents the use and performance of TorchBraid, in addition to solutions for overcoming the algorithmic challenges inherent in combining automatic differentiation with layer-parallel. Results are presented with and without GPU acceleration for the Tiny ImageNet and MNIST image classification data sets, as well as recurrent neural networks. Overall, TorchBraid enables fast training of DNNs, both in a strong and weak scaling context. In addition to the TorchBraid software, several new advances in applying layer-parallel algorithms are detailed. Integration of layer-parallel with data-parallel algorithms is presented for the first time, showing the computational advantages of the combination. Standard deep learning techniques, like batch-normalization, are developed for layer-parallel training. Finally, a new approach combining layer-parallel with spatial coarsening in order to accelerate training for 3D image classification shows roughly a 10× speedup over serial execution.

Layer-parallel↗

DOE OSTI2023

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↗

DOE OSTI2012

A Self Consistent Multiprocessor Space Charge Algorithm that is Almost Embarrassingly Parallel

We present a space charge code that is self consistent, massively parallelizeable, and requires very little communication between computer nodes; making the calculation almost embarrassingly parallel. This method is implemented in the code COSY Infinity where the differential algebras used in this code are important to the algorithm's proper functioning. The method works by calculating the self consistent space charge distribution using the statistical moments of the test particles, and converting them into polynomial series coefficients. These coefficients are combined with differential algebraic integrals to form the potential, and electric fields. The result is a map which contains the effects of space charge. This method allows for massive parallelization since its statistics based solver doesn't require any binning of particles, and only requires a vector containing the partial sums of the statistical moments for the different nodes to be passed. All other calculations are done independently. The resulting maps can be used to analyze the system using normal form analysis, as well as advance particles in numbers and at speeds that were previously impossible.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

DOE OSTI2015

ASC-ATDM Performance Portability Requirements for 2015-2019

This report outlines the research, development, and support requirements for the Advanced Simulation and Computing (ASC ) Advanced Technology, Development, and Mitigation (ATDM) Performance Portability (a.k.a., Kokkos) project for 2015 - 2019 . The research and development (R&D) goal for Kokkos (v2) has been to create and demonstrate a thread - parallel programming model a nd standard C++ library - based implementation that enables performance portability across diverse manycore architectures such as multicore CPU, Intel Xeon Phi, and NVIDIA Kepler GPU. This R&D goal has been achieved for algorithms that use data parallel pat terns including parallel - for, parallel - reduce, and parallel - scan. Current R&D is focusing on hierarchical parallel patterns such as a directed acyclic graph (DAG) of asynchronous tasks where each task contain s nested data parallel algorithms. This five y ear plan includes R&D required to f ully and performance portably exploit thread parallelism across current and anticipated next generation platforms (NGP). The Kokkos library is being evaluated by many projects exploring algorithm s and code design for NGP. Some production libraries and applications such as Trilinos and LAMMPS have already committed to Kokkos as their foundation for manycore parallelism an d performance portability. These five year requirements includes support required for current and antic ipated ASC projects to be effective and productive in their use of Kokkos on NGP. The greatest risk to the success of Kokkos and ASC projects relying upon Kokkos is a lack of staffing resources to support Kokkos to the degree needed by these ASC projects. This support includes up - to - date tutorials, documentation, multi - platform (hardware and software stack) testing, minor feature enhancements, thread - scalable algorithm consulting, and managing collaborative R&D.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2014

redMaPPer. I. Algorithm and SDSS DR8 catalog

We describe redMaPPer, a new red sequence cluster finder specifically designed to make optimal use of ongoing and near-future large photometric surveys. The algorithm has multiple attractive features: (1) it can iteratively self-train the red sequence model based on a minimal spectroscopic training sample, an important feature for high-redshift surveys. (2) It can handle complex masks with varying depth. (3) It produces cluster-appropriate random points to enable large-scale structure studies. (4) All clusters are assigned a full redshift probability distribution P(z). (5) Similarly, clusters can have multiple candidate central galaxies, each with corresponding centering probabilities. (6) The algorithm is parallel and numerically efficient: it can run a Dark Energy Survey-like catalog in ∼500 CPU hours. (7) The algorithm exhibits excellent photometric redshift performance, the richness estimates are tightly correlated with external mass proxies, and the completeness and purity of the corresponding catalogs are superb. We apply the redMaPPer algorithm to ∼10, 000 deg{sup 2} of SDSS DR8 data and present the resulting catalog of ∼25,000 clusters over the redshift range z in [0.08, 0.55]. The redMaPPer photometric redshifts are nearly Gaussian, with a scatter σ {sub z} ≈ 0.006 at z ≈ 0.1, increasing to σ {sub z} ≈ 0.02 at z ≈ 0.5 due to increased photometric noise near the survey limit. The median value for |Δz|/(1 + z) for the full sample is 0.006. The incidence of projection effects is low (≤5%). Detailed performance comparisons of the redMaPPer DR8 cluster catalog to X-ray and Sunyaev-Zel'dovich catalogs are presented in a companion paper.

79 ASTRONOMY AND ASTROPHYSICS↗

DOE OSTI2016

VTK-m: Accelerating the Visualization Toolkit for Massively Threaded Architectures

Execution on massively threaded processors is one of the most critical challenges for high-performance computing (HPC) scientific visualization. Of the many fundamental changes we are seeing in HPC systems, one of the most profound is a reliance on new processor types optimized for execution bandwidth over latency hiding. Moreover, our current production scientific visualization software is not designed for these new types of architectures. In order to address this issue, the VTK-m framework serves as a container for algorithms, provides flexible data representation, and simplifies the design of visualization algorithms on new and future computer architecture.

97 MATHEMATICS AND COMPUTING↗