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 721 records · Page 40
All sourcesNASA NTRSDOE OSTI
DOE OSTI2023

Refining Processing Engines from SAPHIRE: Initialization of Fault Tree/Event Tree Solver

SAPHIRE has been extensively employed for over 35 years to model risk-important systems and quantify risk models. As a well-established and thoroughly documented Probabilistic Risk Assessment (PRA) tool, SAPHIRE has continuously tracked computational trends and received regular updates. Despite its ongoing evolution, there remains a need for further enhancements, particularly in dealing with the quantification of exceptionally large models. These improvements could take the form of algorithmic advancements, harnessing the power of parallel computing, and exploring the potential benefits of cloud computing solutions. Considering these aspirations, the notion of a remote solve option was introduced and subsequently evolved into a dedicated project within the SAPHIRE development team. A significant outcome of this initiative is SAPHSOLVE, an engine extracted from the SageRisk API designed specifically for remote solving capabilities. The ongoing project is nearing its culmination, marked by a series of discoveries that have brought undocumented aspects to light. Among these revelations is the intricacy of the input and output format for the SAPHSOLVE engine. This document serves the crucial purpose of meticulously delineating the precise formats for both input and output, as they form an indispensable foundation. The importance of documenting these formats cannot be overstated, as it is a pivotal step in facilitating rigorous testing and comparison. Whether it involves scrutinizing SAPHSOLVE results against those of the internal integrated solver or other external solvers, the ability to construct models or transform existing ones into a compatible SAPHSOLVE format is imperative. Chapter 1 offers a succinct introduction to both SAPHIRE and SAPHSOLVE, followed by Chapter 2 which outlines the roadmap for enhancing SAPHSOLVE. The core of this report is Chapter 3, which intricately elucidates the intricacies of the input and output file formats. To provide a tangible illustration of these formats, a rudimentary example has been compiled and is available in Appendix. SAPHSOLVE represents a novel external solving mechanism developed by the SAPHIRE team, although it has not yet reached the full spectrum of capabilities possessed by SAPHIRE's internal solver. However, the SAPHIRE team has set a comprehensive course for incorporating the functionalities of SAPHSOLVE. A comprehensive outlook on the future of SAPHSOLVE is expounded upon in Chapter 4.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Adaptive Protection and Validated Models to Enable Deployment of High Penetrations of Solar PV (PV-MOD)

The availability and validation of various PV models in commercial tools differ, with some models not yet thoroughly validated for advanced inverter functionalities and reliable performance under weak system conditions. Many existing models do not fully incorporate new inverter control functions, which can affect system stability. The increasing deployment of solar PV and other inverter-based resources (IBRs), including distributed energy resources (DERs), is influencing the reliable operation of protection schemes in distribution systems and microgrids. Emerging adaptive protection schemes (APS) offer new opportunities for protecting these systems during varying configurations and DER operating conditions, though their demonstration and validation remain limited. Adaptive protection schemes face similar challenges, as they are typically designed for specific configurations. There is a growing need for tools and methodologies to streamline the deployment of adaptive protection for safe and reliable DER integration. The project main objective was to develop and validate high-fidelity generic models of solar PV facilities for stability, protection, EMT, and QSTS analyses. This objective was achieved, and these models can now be integrated into commercial software tools, enabling utilities, vendors, and developers to study high-penetration PV systems more confidently. The project also demonstrated advanced applications of these models, including the design and deployment of adaptive protection schemes in high-penetration field applications and microgrids, supporting grid safety and reliability. Several milestones were reached by the end of the project. A sophisticated inverter test plan was developed, and inverters representative of the North American marketplace were selected. EPRI and NREL tested various inverters, conforming to IEEE standards. Improvements were made to existing generic models of IBR units, IBR plants, and aggregated feeders for various analyses. The first generic electromagnetic transient (EMT) model for a solar PV plant was developed, conforming to IEEE Std 2800™-2022 and validated against laboratory measurements of a 2.2 MVA large-scale battery energy storage system (BESS) inverter. That model was then used to produce reference responses illustrating examples of validated and verified IBR plant models that pass or fail tests for technical minimum capability and performance as specified in the IEEE standard. The developed, tested, and validated generic models can be used for transmission planning, stability assessments, expansion planning, and evaluating potential future IBR interconnection requirements. They can also support interconnection screens and conformity assessments of IBR plants, including solar PV. The project significantly contributed to the ongoing standardization and model-based representation and verification of IBR responses. The project further addressed challenges of common distribution protection schemes with increasing deployment of DER by developing, validating, and demonstrating adaptive protection schemes (APS) that can improve the reliable and safe integration of DER into distribution systems. New APS were designed using improved DER models for three common distribution systems: a radial feeder, a meshed network, and a microgrid. Modeling and hardware-in-the-loop (HIL) testing of the APS were conducted, successfully showing their effectiveness and selectivity. Proof-of-concept field demonstration was achieved for two APS, i.e., one on a radial feeder and another one in a microgrid. Field demonstration could not be achieved for the APS on a meshed network, primarily due apprehension of one utility partner and also due to limited access to the protective algorithms in the network protectors. Guidelines developed from the lessons learned in the project lay out the general process followed in the design, installation, and commissioning of APS for various distribution systems. Distribution utility partners’ apprehension about field demonstration of the new APS were addressed—with varying success—by taking a stepped risk-management approach of modeling of a wide range of sensitivities first, performing in-depth proof-of-concept testing in the laboratory including HIL next, and finally deliberately implementing and commissioning the actual protection equipment and algorithms into parts of—or in parallel operation to—the three real distribution systems. Future work should include pilot projects that further show the acceptable performance of the developed APS before these schemes be rolled out more widely. Inclusion of both utility and original equipment manufacturers (OEMs) in future projects could increase chances of successful field demonstration. Despite challenges in achieving the field demonstration goal of the project for all three APS, the research significantly contributed to the innovation of adaptive protection solutions for scalable and reliable DER integration into distribution systems. This project significantly enhances the understanding of the impact of using appropriate inverter models on distribution and transmission (T&D) systems. By addressing the limitations of existing generic models, the project introduces high-fidelity models for stability, protection, electromagnetic transient (EMT), and quasi-static time series (QSTS) analyses. These models, integrated into commercial software tools, enable utilities, vendors, and developers to confidently study high-penetration PV systems. The project also demonstrates advanced applications, including adaptive protection schemes (APS) for distribution systems and microgrids, ensuring grid safety and reliability. The technical effectiveness and economic feasibility of the methods are evident through the development and validation of sophisticated inverter test plans and the selection of representative inverters. Testing by EPRI and NREL on retail, commercial, and utility-scale inverters, conforming to IEEE standards, underscores the robustness of the models. Improvements to existing generic models for various analyses further enhance their validity and applicability. The project also identifies gaps in common distribution protection schemes and designed new APS using improved DER models, demonstrating their effectiveness through modeling and hardware-in-the-loop (HIL) testing. The project’s benefits to the public are manifold. By advancing the standardization and model-based representation of IBR response, it supports transmission planning, stability assessments, and future IBR interconnection requirements. The generic models can facilitate better communication between transmission planners and developers, supporting expected IBR plant capability and performance. Additionally, the development of APS for radial feeders, meshed networks, and microgrids supports the integration of distributed energy resources (DERs) into distribution systems, enhancing grid reliability and safety. The project’s emphasis on thorough testing and simplicity in design ensures practical and scalable solutions for DER integration.

14 SOLAR ENERGY↗
DOE OSTI2018

nbodykit: An Open-source, Massively Parallel Toolkit for Large-scale Structure

We present nbodykit, an open-source, massively parallel Python toolkit for analyzing large-scale structure (LSS) data. Using Python bindings of the Message Passing Interface, we provide parallel implementations of many commonly used algorithms in LSS. nbodykit is both an interactive and scalable piece of scientific software, performing well in a supercomputing environment while still taking advantage of the interactive tools provided by the Python ecosystem. Existing functionality includes estimators of the power spectrum, two- and three-point correlation functions, a friends-of-friends grouping algorithm, mock catalog creation via the halo occupation distribution technique, and approximate N-body simulations via the FastPM scheme. The package also provides a set of distributed data containers, insulated from the algorithms themselves, that enables nbodykit to provide a unified treatment of both simulation and observational data sets. nbodykit can be easily deployed in a high-performance computing environment, overcoming some of the traditional difficulties of using Python on supercomputers. We provide performance benchmarks illustrating the scalability of the software. The modular, component-based approach of nbodykit allows researchers to easily build complex applications using its tools. The package is extensively documented at http://nbodykit.readthedocs.io, which also includes an interactive set of example recipes for new users to explore. As open-source software, we hope nbodykit provides a common framework for the community to use and develop in confronting the analysis challenges of future LSS surveys.

79 ASTRONOMY AND ASTROPHYSICS↗
DOE OSTI2019

Vectorization of Random Number Generation and Reproducibility of Concurrent Particle Transport Simulation

Efficient random number generation with high quality statistical properties and exact reproducibility of Monte Carlo simulations are important requirements in many areas of computational science. VecRNG is a package providing pseudo-random number generation (pRNG) in the context of a new library VecMath. This library bundles up several general-purpose mathematical utilities, data structures, and algorithms having both SIMD and SIMT (GPUs) support based on VecCore.~Several state-of-the-art RNG algorithms are implemented as kernels supporting parallel generation of random numbers in scalar, vector, and Cuda workflows. In this report, we will present design considerations, implementation details, and computing performance of parallel pRNG engines on both CPU and GPU. Reproducibility of propagating multiple particles in parallel for HEP event simulation is demonstrated, using GeantV-based examples, for both sequential and fine-grain track-level concurrent simulation wor kflows. Strategies for efficient uses of vectorized pRNG and non-overlapping streams of random number sequences in concurrent computing environments is discussed as well.

Jun, S. Y.↗
DOE OSTI2024

A new track finding algorithm based on a multi-dimensional extension of the Hough Transform

We introduce a new pattern recognition algorithm for track finding in High Energy Physics Experiments based on an extension of the Hough Transform to multiple dimensions. A remarkable property of this algorithm is that the execution time is simply proportional to the total number of the hits to be processed, making it particularly attractive for high occupancy situations. The algorithm needs to be trained using a sufficiently large set of simulated tracks. The same track finding algorithm can be used for very different detector geometries and only the set of simulated tracks used for training needs to be changed. The particular structure of the algorithm also lends itself naturally to parallel hardware implementations which, combined with its intrinsic flexibility, should provide a most powerful tool for triggering at future colliders.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2017

High Performance Computing Based Parallel HIearchical Modal Association Clustering (HPAR HMAC)

For many applications, clustering is a crucial step in order to gain insight into the makeup of a dataset. The best approach to a given problem often depends on a variety of factors, such as the size of the dataset, time restrictions, and soft clustering requirements. The HMAC algorithm seeks to combine the strengths of 2 particular clustering approaches: model-based and linkage-based clustering. One particular weakness of HMAC is its computational complexity. HMAC is not practical for mega-scale data clustering. For high-definition imagery, a user would have to wait months or years for a result; for a 16-megapixel image, the estimated runtime skyrockets to over a decade! To improve the execution time of HMAC, it is reasonable to consider an multi-core implementation that utilizes available system resources. An existing imple-mentation (Ray and Cheng 2014) divides the dataset into N partitions - one for each thread prior to executing the HMAC algorithm. This implementation benefits from 2 types of optimization: parallelization and divide-and-conquer. By running each partition in parallel, the program is able to accelerate computation by utilizing more system resources. Although the parallel implementation provides considerable improvement over the serial HMAC, it still suffers from poor computational complexity, O(N2). Once the maximum number of cores on a system is exhausted, the program exhibits slower behavior. We now consider a modification to HMAC that involves a recursive partitioning scheme. Our modification aims to exploit divide-and-conquer benefits seen by the parallel HMAC implementation. At each level in the recursion tree, partitions are divided into 2 sub-partitions until a threshold size is reached. When the partition can no longer be divided without falling below threshold size, the base HMAC algorithm is applied. This results in a significant speedup over the parallel HMAC.

Patlolla, Dilip R↗
DOE OSTI2020

Parallel Time Integration for Constrained Optimization

The number of transistors in an average processor continues to increase, but individual clock speeds have plateaued. Those transistors are instead going into additional cores, increasing the number of different things that a processor can do at once and placing an emphasis on parallel computation. Many problems in scientific computing follow a time-evolution model, and it can be difficult to solve such problems in parallel across the temporal domain. The Multi-Grid Reduction In Time (MGRIT) algorithm, developed at Lawrence Livermore National Laboratory (LLNL), solves differential equations with a method designed specifically to take advantage of extreme numbers of processors by parallelizing across time. The Tri-diagonal MGRIT (TriMGRIT) algorithm, also developed at LLNL, is a generalization of MGRIT which enables parallel-in-time solving of a greater number of problems. Constrained optimization problems, in particular, may be solved in parallel using TriMGRIT. These consist of choosing a control function such that an objective functional is minimized, constrained by a differential-equation. We consider two such problems: applying torque to a pendulum to bring it to a gentle stop and moving a crowd of people from one distribution into another. We also perform some miscellaneous theoretical and practical research, including investigating the use of a line-search subroutine to refine intermediate TriMGRIT results and preliminary work on strategies for choosing operators for TriMGRIT to use.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Scaled ILU Smoothers for Navier-Stokes Pressure Projection

Incomplete LU (ILU) smoothers are effective in the algebraic multigrid (AMG) V-cycle for reducing high-frequency components of the error. However, the requisite direct triangular solves are comparatively slow on GPUs. Previous work has demonstrated the advantages of Jacobi iteration as an alternative to direct solution of these systems. Depending on the threshold and fill-level parameters chosen, the factors can be highly nonnormal and Jacobi is unlikely to converge in a low number of iterations. We demonstrate that row scaling can reduce the departure from normality, allowing us to replace the inherently sequential solve with a rapidly converging Richardson iteration. There are several advantages beyond the lower compute time. Scaling is performed locally for a diagonal block of the global matrix because it is applied directly to the factor. Further, an ILUT Schur complement smoother maintains a constant GMRES iteration count as the number of MPI ranks increases, and thus parallel strong-scaling is improved. Our algorithms have been incorporated into hypre, and we demonstrate improved time to solution for linear systems arising in the Nalu-Wind and PeleLM pressure solvers. For large problem sizes, GMRES+AMG executes at least five times faster when using iterative triangular solves compared with direct solves on massively parallel GPUs.

algebraic multigrid↗
DOE OSTI2025

SAGIPS: a physics-inspired scalable asynchronous generative inverse-problem solver

Abstract Solving large-scale inverse problems using deep-learning algorithms have become an essential part of modern research and industrial applications. The complexity of the underlying inverse problem may require the utilization of high performance computing systems which poses a challenge on the algorithmic design of the inverse problem solver. Most deep learning algorithms require, due to their design, custom parallelization techniques in order to be resource efficient while showing a reasonable convergence. In this paper we introduce a S calable A synchronous G enerative I nverse P roblem S olver (SAGIPS) on high-performance computing systems. We present a workflow that utilizes an asynchronous ring-allreduce algorithm to transfer the gradients of the generator network across multiple GPUs. Experiments with a scientific proxy application demonstrate that SAGIPS shows near linear weak scaling, together with a convergence quality that is comparable to traditional methods. The approach presented here allows leveraging Generative Adverserial Network across multiple GPUs, promising advancements in solving complex inverse problems at scale.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2019

Reconstruction for Liquid Argon TPC Neutrino Detectors Using Parallel Architectures [Slides]

Neutrinos are particles that interact rarely, so identifying them requires large detectors which produce lots of data. Processing this data with the computing power available is becoming more difficult as the detectors increase in size to reach their physics goals. In liquid argon time projection chambers (TPCs) the charged particles from neutrino interactions produce ionization electrons which drift in an electric field towards a series of collection wires, and the signal on the wires is used to reconstruct the interaction. The MicroBooNE detector currently collecting data at Fermilab has 8000 wires, and planned future experiments like DUNE will have 100 times more, which means that the time required to reconstruct an event will scale accordingly. Modernization of liquid argon TPC reconstruction code, including vectorization, parallelization and code portability to GPUs, will help to mitigate these challenges. The liquid argon TPC hit finding algorithm within the L arSoft framework used across multiple experiments has been vectorized and parallelized. This increases the speed of the algorithm on the order of ten times within a stand alone version on Intel architectures. This new version has been incorporated back into LarSoft so that it can be generally used. These methods will also be applied to other low level reconstruction of the wire signals such as the deconvolution. The applications and performance of this modernized liquid argon TPC wire reconstruction will be presented.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2025

Massively parallel phase-field simulations targeting exascale

The interface thickness in the phase-field (PF) method limits its simulation scales. Consequently, large-scale PF simulations become prohibitively expensive for resolving the extremely fine microstructures that typically form during rapid solidification processing. This challenge is significant in predicting microstructure evolution in metal additive manufacturing and has been identified by the United States Department of Energy’s Exascale Computing Project. Here, to address this, we develop a multi-GPU and MPI-based massively parallel simulation code, utilizing state-of-the-art algorithms, software, and libraries, for large-scale three-dimensional (3D) PF simulations. We report the first GPU-parallel PF simulations on Frontier (currently the second TOP500 exascale cluster) and Summit machines, taking dendritic growth as an example problem. We evaluate the parallel performance of our implementation using scaling studies with more than 24 000 GPUs (among the largest known computations to date) and the acceleration performance using large-scale simulations of dendritic growth in 3D. Finally, massively parallel GPUs in these supercomputers enabled the first coupled multiscale simulations of laser melting and subsequent dendritic solidification on the scale of a full melt-pool, demonstrating the feasibility of performing PF simulations with a point total over 2 billion grid points within an acceptable time.

Exascale↗
DOE OSTI2017

Community Detection on the GPU

We present and evaluate a new GPU algorithm based on the Louvain method for community detection. Our algorithm is the first for this problem that parallelizes the access to individual edges. In this way we can fine tune the load balance when processing networks with nodes of highly varying degrees. This is achieved by scaling the number of threads assigned to each node according to its degree. Extensive experiments show that we obtain speedups up to a factor of 270 compared to the sequential algorithm. The algorithm consistently outperforms other recent shared memory implementations and is only one order of magnitude slower than the current fastest parallel Louvain method running on a Blue Gene/Q supercomputer using more than 500K threads.

community detection↗
DOE OSTI2025

Automatic Generation of Algorithms for High-Speed Reliable Lossy Data Compression (Final Report)

Fast reliable data compression is urgently needed for many leading-edge scientific instruments and for exascale high-performance computing applications because they produce vast amounts of data at extremely high rates. The goal of this project has been to develop a framework named LC that is able to automatically generate high-speed lossless and reliable lossy compression and decompression algorithms that can be customized for different kinds of data. The resulting LC framework is freely available on GitHub. To achieve high-speed operation, LC outputs optimized and parallelized CPU and GPU implementations of the generated algorithms. To ensure the quality of lossily compressed data, LC guarantees the user-provided error bound. To be able to customize the compression algorithm to various use cases, LC can synthesize millions of different algorithms and automatically search for the one that works best for the given data. We have already employed LC to create state-of-the-art lossless and lossy compressors for scientific data as well as leading lossless compressors for images. We hope that LC and the customized, fast, reliable, and CPU/GPU-compatible compression algorithms that it can generate will greatly benefit the many scientific applications that need not only high trustworthiness but also high performance.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

SQUARE: Strategic Quantum Ancilla Reuse for Modular Quantum Programs via Cost-Effective Uncomputation

Compiling high-level quantum programs to machines that are size constrained (i.e. limited number of quantum bits) and time constrained (i.e. limited number of quantum operations) is challenging. In this paper, we present SQUARE (Strategic QUantum Ancilla REuse), a compilation infrastructure that tackles allocation and reclamation of scratch qubits (called ancilla) in modular quantum programs. At its core, SQUARE strategically performs uncomputation to create opportunities for qubit reuse. Current Noisy Intermediate-Scale Quantum (NISQ) computers and forward-looking Fault-Tolerant (FT) quantum computers have fundamentally different constraints such as data locality, instruction parallelism, and communication overhead. Our heuristic-based ancilla-reuse algorithm balances these considerations and fits computations into resource-constrained NISQ or FT quantum machines, throttling parallelism when necessary. To precisely capture the workload of a program, we propose an improved metric, the "active quantum volume," and use this metric to evaluate the effectiveness of our algorithm. Furthermore, our results show that SQUARE improves the average success rate of NISQ applications by 1.47X. Surprisingly, the additional gates for uncomputation create ancilla with better locality, and result in substantially fewer swap gates and less gate noise overall. SQUARE also achieves an average reduction of 1.5X (and up to 9.6X) in active quantum volume for FT machines.

compiler optimization↗
DOE OSTI2015

A generalized reconstruction framework for unconventional PET systems

Purpose: Quantitative estimation of the radionuclide activity concentration in positron emission tomography (PET) requires precise modeling of PET physics. The authors are focused on designing unconventional PET geometries for specific applications. This work reports the creation of a generalized reconstruction framework, capable of reconstructing tomographic PET data for systems that use right cuboidal detector elements positioned at arbitrary geometry using a regular Cartesian grid of image voxels. Methods: The authors report on a variety of design choices and optimization for the creation of the generalized framework. The image reconstruction algorithm is maximum likelihood-expectation–maximization. System geometry can be specified using a simple script. Given the geometry, a symmetry seeking algorithm finds existing symmetry in the geometry with respect to the image grid to improve the memory usage/speed. Normalization is approached from a geometry independent perspective. The system matrix is computed using the Siddon’s algorithm and subcrystal approach. The program is parallelized through open multiprocessing and message passing interface libraries. A wide variety of systems can be modeled using the framework. This is made possible by modeling the underlying physics and data correction, while generalizing the geometry dependent features. Results: Application of the framework for three novel PET systems, each designed for a specific application, is presented to demonstrate the robustness of the framework in modeling PET systems of unconventional geometry. Three PET systems of unconventional geometry are studied. (1) Virtual-pinhole half-ring insert integrated into Biograph-40: although the insert device improves image quality over conventional whole-body scanner, the image quality varies depending on the position of the insert and the object. (2) Virtual-pinhole flat-panel insert integrated into Biograph-40: preliminary results from an investigation into a modular flat-panel insert are presented. (3) Plant PET system: a reconfigurable PET system for imaging plants, with resolution of greater than 3.3 mm, is shown. Using the automated symmetry seeking algorithm, the authors achieved a compression ratio of the storage and memory requirement by a factor of approximately 50 for the half-ring and flat-panel systems. For plant PET system, the compression ratio is approximately five. The ratio depends on the level of symmetry that exists in different geometries. Conclusions: This work brings the field closer to arbitrary geometry reconstruction. A generalized reconstruction framework can be used to validate multiple hypotheses and the effort required to investigate each system is reduced. Memory usage/speed can be improved with certain optimizations.

60 APPLIED LIFE SCIENCES↗
DOE OSTI2016

Exploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication

Sparse matrix-matrix multiplication (or SpGEMM) is a key primitive for many high-performance graph algorithms as well as for some linear solvers, such as algebraic multigrid. The scaling of existing parallel implementations of SpGEMM is heavily bound by communication. Even though 3D (or 2.5D) algorithms have been proposed and theoretically analyzed in the flat MPI model on Erdös-Rényi matrices, those algorithms had not been implemented in practice and their complexities had not been analyzed for the general case. In this work, we present the first implementation of the 3D SpGEMM formulation that exploits multiple (intranode and internode) levels of parallelism, achieving significant speedups over the state-of-the-art publicly available codes at all levels of concurrencies. We extensively evaluate our implementation and identify bottlenecks that should be subject to further research.

2.5D algorithms↗
DOE OSTI2017

HPC formulations of optimization algorithms for tensor completion

Tensor completion is a powerful tool used to estimate or recover missing values in multi-way data. It has seen great success in domains such as product recommendation and healthcare. Tensor completion is most often accomplished via low-rank sparse tensor factorization, a computationally expensive non-convex optimization problem which has only recently been studied in the context of parallel computing. In this work, we study three optimization algorithms that have been successfully applied to tensor completion: alternating least squares (ALS), stochastic gradient descent (SGD), and coordinate descent (CCD++). We explore opportunities for parallelism on shared- and distributed-memory systems and address challenges such as memory- and operation-efficiency, load balance, cache locality, and communication. Among our advancements are a communication-efficient CCD++ algorithm, an ALS algorithm rich in level-3 BLAS routines, and an SGD algorithm which combines stratification with asynchronous communication. Furthermore, we show that introducing randomization during ALS and CCD++ can accelerate convergence. We evaluate our parallel formulations on a variety of real datasets on a modern supercomputer and demonstrate speedups through 16384 cores. Further, these improvements reduce time-to-solution from hours to seconds on real-world datasets. We show that after our optimizations, ALS is advantageous on parallel systems of small-to-moderate scale, while both ALS and CCD++ provide the lowest time-to-solution on large-scale distributed systems.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Novel Solver Algorithms for Nearly Singular Linear Systems Arising in Combustion Modelling

Direct Numerical Simulations of realistic combustion devices are extremely challenging due to the wide separation of scales in the simulation, for example an internal combustion (IC) engine chamber, and the flame thickness of a high-pressure flame. The PeleLMeX solver uses adaptive mesh refinement (AMR) to evolve multi-species reacting flows in the low Mach number limit at the Exascale and relies on an embedded boundary (EB) approach to represent complex geometries. In that framework, the EB geometries often give rise to very small cut-cells along the boundary, which translate into extreme ill-conditioning of the pressure-projection, with eigenvalues that span 15-16 orders of magnitude. In this talk, we focus on the case of a typical IC piston bowl geometry for which we present on a novel approach towards solving these nearly singular linear systems with ILU-based, C-AMG smoothers on massively parallel architectures. In particular, we use scaling and equilibration algorithms to handle the non-normality of the upper triangular factors. This enables us to approximate the highly sequential triangular solve algorithm, embedded in the AMG smoothing-solve phase, with Jacobi iterations. This approximation can be written as a convergent Neumann series whose terms are composed of highly parallel sparse matrix vector multiplications. The result is an algorithm that substantially decreases setup and solve time, compared to state-of-the-art, for these challenging linear systems.

combustion modelling↗