Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “parallel 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 451 records · Page 25
All sourcesNASA NTRSDOE OSTI
DOE OSTI2022

GSoFa: Scalable Sparse Symbolic LU Factorization on GPUs

Decomposing a matrix $\mathbf {A}$ into a lower matrix $\mathbf {L}$ and an upper matrix $\mathbf {U}$, which is also known as LU decomposition, is an essential operation in numerical linear algebra. For a sparse matrix, LU decomposition often introduces more nonzero entries in the $\mathbf {L}$ and $\mathbf {U}$ factors than in the original matrix. A symbolic factorization step is needed to identify the nonzero structures of $\mathbf {L}$ and $\mathbf {U}$ matrices. Attracted by the enormous potentials of the Graphics Processing Units (GPUs), an array of efforts have surged to deploy various LU factorization steps except for the symbolic factorization, to the best of our knowledge, on GPUs. This article introduces gSoFa, the first GPU-based symbolic factorization design with the following three optimizations to enable scalable LU symbolic factorization for nonsymmetric pattern sparse matrices on GPUs. First, here we introduce a novel fine-grained parallel symbolic factorization algorithm that is well suited for the Single Instruction Multiple Thread (SIMT) architecture of GPUs. Second, we tailor supernode detection into a SIMT friendly process and strive to balance the workload, minimize the communication and saturate the GPU computing resources during supernode detection. Third, we introduce a three-pronged optimization to reduce the excessive space consumption problem faced by multi-source concurrent symbolic factorization. Taken together, gSoFa achieves up to 31× speedup from 1 to 44 Summit nodes (6 to 264 GPUs) and outperforms the state-of-the-art CPU project, on average, by 5×. Notably, gSoFa also achieves up to 47 percent of the peak memory throughput of a V100 GPU in the Summit Supercomputer.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2018

Exploiting Internal Parallelism for Address Translation in Solid-State Drives

Solid-state Drives (SSDs) have changed the landscape of storage systems and present a promising storage solution for data-intensive applications due to their low latency, high bandwidth, and low power consumption compared to traditional hard disk drives. SSDs achieve these desirable characteristics using internal parallelism—parallel access to multiple internal flash memory chips—and a Flash Translation Layer (FTL) that determines where data are stored on those chips so that they do not wear out prematurely. However, current state-of-the-art cache-based FTLs like the Demand-based Flash Translation Layer (DFTL) do not allow IO schedulers to take full advantage of internal parallelism, because they impose a tight coupling between the logical-to-physical address translation and the data access. In this study to address this limitation, we introduce a new FTL design called Parallel-DFTL that works with the DFTL to decouple address translation operations from data accesses. Parallel-DFTL separates address translation and data access operations into different queues, allowing the SSD to use concurrent flash accesses for both types of operations. We also present a Parallel-LRU cache replacement algorithm to improve the concurrency of address translation operations. To compare Parallel-DFTL against existing FTL approaches, we present a Parallel-DFTL performance model and compare its predictions against those for DFTL and an ideal page-mapping approach. We also implemented the Parallel-DFTL approach in an SSD simulator using real device parameters, and used trace-driven simulation to evaluate Parallel-DFTL’s efficacy. Our evaluation results show that Parallel-DFTL improved the overall performance by up to 32% for the real IO workloads we tested, and by up to two orders of magnitude with synthetic test workloads. Finally, we also found that Parallel-DFTL is able to achieve reasonable performance with a very small cache size and that it provides the best benefit for those workloads with large request size or with high write ratio.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2015

Using Coarrays to Parallelize Legacy Fortran Applications: Strategy and Case Study

This paper summarizes a strategy for parallelizing a legacy Fortran 77 program using the object-oriented (OO) and coarray features that entered Fortran in the 2003 and 2008 standards, respectively. OO programming (OOP) facilitates the construction of an extensible suite of model-verification and performance tests that drive the development. Coarray parallel programming facilitates a rapid evolution from a serial application to a parallel application capable of running on multicore processors and many-core accelerators in shared and distributed memory. We delineate 17 code modernization steps used to refactor and parallelize the program and study the resulting performance. Our initial studies were done using the Intel Fortran compiler on a 32-core shared memory server. Scaling behavior was very poor, and profile analysis using TAU showed that the bottleneck in the performance was due to our implementation of a collective, sequential summation procedure. We were able to improve the scalability and achieve nearly linear speedup by replacing the sequential summation with a parallel, binary tree algorithm. We also tested the Cray compiler, which provides its own collective summation procedure. Intel provides no collective reductions. With Cray, the program shows linear speedup even in distributed-memory execution. We anticipate similar results with other compilers once they support the new collective procedures proposed for Fortran 2015.

Radhakrishnan, Hari↗
DOE OSTI2014

Machine Learning Toolkit for Extreme Scale

Support Vector Machines (SVM) is a popular machine learning technique, which has been applied to a wide range of domains such as science, finance, and social networks for supervised learning. MaTEx undertakes the challenge of designing a scalable parallel SVM training algorithm for large scale systems, which includes commodity multi-core machines, tightly connected supercomputers and cloud computing systems. Several techniques are proposed for improved speed and memory space usage including adaptive and aggressive elimination of samples for faster convergence , and sparse format representation of data samples. Several heuristics for earliest possible to lazy elimination of non-contributing samples are considered in MaTEx. In many cases, where an early sample elimination might result in a false positive, low overhead mechanisms for reconstruction of key data structures are proposed. The proposed algorithm and heuristics are implemented and evaluated on various publicly available datasets

Source record↗
DOE OSTI2018

Parallel Markov Random Fields for Image Segmentation (PMRF-IS) v1.0

This software performs multi-label segmentation of 2D/3D images. It is highly accurate, results rely on use of an Markov random field (MRF) formulation. It runs in both shared and distributed memory parallel modes. MRF algorithms are powerful tools in image analysis to explore contextual information of data.

Heinemann, Colleen↗
DOE OSTI2023

Contributions to MoDELib SOFTWARE

The purpose of the current request is to enable LANL employees to contribute computer source code to the existing public repository of the MoDELib software package. This software implements discrete dislocation dynamics (DDD) and finite element (FEM) methods and is currently a vital component of an ongoing DR project at LANL, in collaboration with its original author and maintainer Giacomo Po. Contributions from LANL employees would aim to enhance the reliability, accuracy, and performance of MoDELib simulations using LANL's high performance computing platforms through bug fixes, algorithmic refinements, and parallelization.

Julian, Nicholas↗
DOE OSTI2020

PASTA

PASTA: A Parallel Sparse Tensor Algorithm Benchmark Suite.

Li, Jiajia↗
DOE OSTI2018

GPU Acceleration of Volume Fraction and Centroid Computation from General Shapes on Unstructured Mesh

One important requirement for coupling multi-physics models is a means to remap fields between meshes in an accurate and conservative manner. Since the remapping algorithm is embarrassingly parallel, this motivates the use of Graphical Processing Units (GPU) for such routine. However, since our remapping code, portage, is fairly complex, we explore the use of GPUs through a simpler problem of generating material’s volume fraction and centroid inside each cell of the mesh. We use the same programming structure that is used in portage, namely, on-node parallelism via NVIDIA’s thrust library. Using a similar programming structure enables us to draw lessons from this study that can be applied to the more complex problem. We have found that while the speed-up is pronounced (10-100 times), significant effort is required to re-factor the code so that thrust can be used with a CUDA backend. Moreover, thrust takes away the fine grain control that vanilla CUDA programming gives us.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2019

Properties of the Graph Modularity Matrix and its Applications

We study the popular modularity matrix and respective functional used in connection with graph clustering and derive some properties useful when performing vertex aggregation of the associated graph. These properties are employed in the derivation of a multilevel parallel pairwise aggregation algorithm. Some illustrative examples which include algebraic multigrid (AMG) coarsening that follows strong direction of anisotropy in finite element problems as well as comparative performance results of the studied algorithm are presented.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Experience of Migrating a Parallel Graph Coloring Program from CUDA to SYCL

We describe the experience of converting a CUDA implementation of a parallel graph coloring algorithm to SYCL. The goals are for our work to be useful to application and compiler developers by providing a detailed description of migration paths between CUDA and SYCL. We will describe how CUDA functions are mapped to SYCL functions. Evaluating the CUDA and SYCL implementations of the algorithm shows that the performance of SYCL and CUDA kernels are comparable over the test graph set on NVIDIA P100 and V100 GPUs. The SYCL program also allows for performance evaluation with the OpenCL and Level Zero interfaces and power profiling on an Intel GPU computing platform.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Development of a New Fixed-source Sensitivity Tally Capability in the MCNP ® Code [Slides]

Current work includes FSEN capability development, continued verification of adjoint-weighted sensitivity method, and improvement of algorithm speed and parallelism capability. Future work is forecasted to include extensions to non-Boltzmann responses, adding more responses and particle types, and connection to new MCNP6.3 tally backend.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗
DOE OSTI2014

Machine Learning Toolkit for Extreme Scale

Support Vector Machines (SVM) is a popular machine learning technique, which has been applied to a wide range of domains such as science, finance, and social networks for supervised learning. MaTEx undertakes the challenge of designing a scalable parallel SVM training algorithm for large scale systems, which includes commodity multi-core machines, tightly connected supercomputers and cloud computing systems. Several techniques are proposed for improved speed and memory space usage including adaptive and aggressive elimination of samples for faster convergence , and sparse format representation of data samples. Several heuristics for earliest possible to lazy elimination of non-contributing samples are considered in MaTEx. In many cases, where an early sample elimination might result in a false positive, low overhead mechanisms for reconstruction of key data structures are proposed. The proposed algorithm and heuristics are implemented and evaluated on various publicly available datasets

Source record↗
DOE OSTI2018

167-PFlops deep learning for electron microscopy: from learning physics to atomic manipulation

An artificial intelligence system called MENNDL, which used 25,200 NVIDIA Volta GPUs on Oak Ridge National Laboratory's Summit machine, automatically designed an optimal deep learning network in order to extract structural information from raw atomic-resolution microscopy data. In a few hours, MENNDL creates and evaluates millions of networks using a scalable, parallel, asynchronous genetic algorithm augmented with a support vector machine to automatically find a superior deep learning network topology and hyper-parameter set than a human expert can find in months. For the application of electron microscopy, the system furthers the goal of improving our understanding of the electron-beam-matter interactions and real-time image-based feedback, which enables a huge step beyond human capacity towards nanofabricating materials automatically. MENNDL has been scaled to the 4,200 available nodes of Summit achieving a measured 152.5 PFlops, with an estimated sustained performance of 167 PFlops when the entire machine is available.

Patton, Robert↗
DOE OSTI2016

Sensitivity Analysis of Passive Heat Removal Capability of FHR Based on Efficient Surrogate Model and GenFlow

Code Scaling, Applicability and Uncertainty Evaluation Methodology (CSAU) is used for quantifying reactor safety margins and works as an alternative method for licensing nuclear power plant. In the framework of CSAU, sensitivity and uncertainty analysis (SA and UA) should be performed. However, for large-scale complicated thermal hydraulics analysis simulated by code (e.g. RELAP5, CFD and subchannel analysis, the sensitivity and uncertainty analysis is really time-consuming. Furthermore, sometimes it is not feasible to perform SA and UA. Specifically, the computation time for Monte Carlo sampling or advanced LHS sampling can be neglected, but the computation time for thermal hydraulics code makes up main part of time during SA and UA process. In order to accelerate the speed of SA and UA, thermal hydraulics code can be improved based on advanced mathematic algorithm or using parallel method. However, the development for new mathematic method needs long time and strict verification and validation process is needed for a new code, which usually takes a couple of years or even longer time to have an approved code that can be used in nuclear industry. An alternative way to improve the speed of SA and UA is using surrogate model. The surrogate model is derived from the input as well as output data of the original code, assuming the code as a black box. The most common method is using response surface method (RSM) as a surrogate for the code, the input parameters are then sampled from their assumed distribution and the corresponding value of the response surface function is calculated. However, a couple of input parameters need hundreds or even thousands of original code calculations. The large number of runs is an obvious disadvantage of this method. Besides, the second disadvantage is an appropriate response surface function must be selected (e.g. quadratic, cubic, quartic, with or without cross product terms, or using a non-polynomial form) to avoid the overfit and underfit problem. This process is time consuming and expensive. Polynomial chaos expansion method is a reasonably fast and attractive alternative, stochastic model. The chaos expansion provides an efficient high-order method of including non-linear effects in stochastic analysis. Usually, the information about the model parameters and their probability distribution is limited and the dependence between them is not known. However, if arbitrary polynomial chaos is used, instead of assuming probability distribution for input parameters which may introduces additional subjectivity into the analysis, the available information can directly and most purely be used in stochastic analysis based on arbitrary data distribution. Thus, it is not necessary to know the exact probability density functions to perform SA and UA based on arbitrary polynomial chaos (aPC). The aPC has been applied for uncertainty quantification in many fields (e.g. in solid mechanics, fluid flows, thermal sciences), and become widely used in nuclear industry recently. Mk1 PB-FHR is a small modular fluoride-salt-cooled, high-temperature reactors (FHRs) that is a concept design by University of California, Berkeley (UCB). It has inherently safe features like natural-circulation-driven systems (e.g. direct reactor auxiliary cooling system (DRACS)) to passively remove decay heat from the reactor core during design basis and beyond design. It is necessary to perform SA and UA, since the licensing process of this new kind of reactor is under way and there are many design parameters that have not been fixed. Current nuclear commercial codes, such as RELAP5, have mainly been developed for light water reactors, which require the use of comprehensive two-phase flow models. This capability is not required to simulate single-phase flow phenomena in FHRs, whose baseline coolant, flibe, remains liquid up to 1430 deg. C at atmospheric pressure. The FHR advanced natural circulation analysis (FANCY) code has been developed specifically for FHR technology modeling and validation work has been performed by using CIET data in UCB. The code has been renamed General Flow (GenFlow) because it has been further developed to have the capability to model complicated pipework system based on object-oriented concept for user friendly purpose. Besides, it can be used to simulate both the force circulation as well as natural circulation. (authors)

21 SPECIFIC NUCLEAR REACTORS AND ASSOCIATED PLANTS↗
DOE OSTI2022

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↗