Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Scalable 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 397 records · Page 22

ISAVS: Interactive Scalable Analysis and Visualization System

Modern science is inundated with ever increasing data sizes as computational capabilities and image acquisition techniques continue to improve. For example, simulations are tackling ever larger domains with higher fidelity, and high-throughput microscopy techniques generate larger data that are fundamental to gather biologically and medically relevant insights. As the image sizes exceed memory, and even sometimes local disk space, each step in a scientific workflow is impacted. Current software solutions enable data exploration with limited interactivity for visualization and analytic tasks. Furthermore analysis on HPC systems often require complex hand-written parallel implementations of algorithms that suffer from poor portability and maintainability. We present a software infrastructure that simplifies end-to-end visualization and analysis of massive data. First, a hierarchical streaming data access layer enables interactive exploration of remote data, with fast data fetching to test analytics on subsets of the data. Second, a library simplifies the process of developing new analytics algorithms, allowing users to rapidly prototype new approaches and deploy them in an HPC setting. Third, a scalable runtime system automates mapping analysis algorithms to whatever computational hardware is available, reducing the complexity of developing scaling algorithms. Here, we demonstrate the usability and performance of our system using a use case from neuroscience: filtering, registration, and visualization of tera-scale microscopy data. We evaluate the performance of our system using a leadership-class supercomputer, Shaheen II.

97 MATHEMATICS AND COMPUTING↗

Machine and Application Aware Partitioning for Adaptive Mesh Refinement Applications. In: HPDC '17 Proceedings of the 26th International Symposium on High-Performance Parallel and Distributed Computing

Load balancing and partitioning are critical when it comes to parallel computations. Popular partitioning strategies based on space filling curves focus on equally dividing work. The partitions produced are independent of the architecture or the application. Given the ever-increasing relative cost of data movement and increasing heterogeneity of our architectures, it is no longer sufficient to only consider an equal partitioning of work. Minimizing communication costs are equally if not more important. Our hypothesis is that an unequal partitioning that minimizes communication costs significantly can scale and perform better than conventional equal-work partitioning schemes. This tradeoff is dependent on the architecture as well as the application. We validate our hypothesis in the context of a finite-element computation utilizing adaptive mesh-refinement. Our central contribution is a new partitioning scheme that minimizes the overall runtime of subsequent computations by performing architecture and application-aware non-uniform work assignment in order to decrease time to solution, primarily by minimizing data-movement. We evaluate our algorithm by comparing it against standard space-filling curve based partitioning algorithms and observing time-to-solution as well as energy-to-solution for solving Finite Element computations on adaptively refined meshes. We demonstrate excellent scalability of our new partition algorithm up to $262,144$ cores on ORNL's Titan and demonstrate that the proposed partitioning scheme reduces overall energy as well as time-to-solution for application codes by up to 22.0%.

Fernando, Milinda↗

Local convergence analysis of an inexact trust-region method for nonsmooth optimization

In Baraldi, we introduced an inexact trust-region algorithm for minimizing the sum of a smooth nonconvex function and a nonsmooth convex function in Hilbert space—a class of problems that is ubiquitous in data science, learning, optimal control, and inverse problems. Furthermore, this algorithm has demonstrated excellent performance and scalability with problem size. In this paper, we enrich the convergence analysis for this algorithm, proving strong convergence of the iterates with guaranteed rates. In particular, we demonstrate that the trust-region algorithm recovers superlinear, even quadratic, convergence rates when using a second-order Taylor approximation of the smooth objective function term.

97 MATHEMATICS AND COMPUTING↗

Multiscale/Multiphysics Modeling of Biomass Thermochemical Processes

Computational problems in simulating biomass thermochemical processes involve coupling processes that span several orders of magnitude in space and time. Computational difficulties arise from the multitude of the problem governing equations, each typically applying over a narrow range of spatiotemporal scales, thus making it necessary to represent the processes as the result of the interaction of multiple physics modules, termed here as multiscale/multiphysics (MSMP) coupling. Predictive simulations for such processes require algorithms that can efficiently integrate the underlying MSMP methods across the scales in order to achieve prescribed accuracy and control the computational cost. In addition, MSMP algorithms must scale to one hundred thousand processors or more in order to effectively harness the new computational resources and accelerate the scientific advances. In this chapter, we discuss the state-of-the-art in modeling the macro-scale phenomena in a biomass pyrolysis reactor along with details of the shortcomings and prospects in improving predictability. We also introduce the various multiphysics modules needed to model thermochemical conversion at lower spatiotemporal scales. Furthermore, we illustrate the need for MSMP coupling for thermochemical processes in biomass and provide an overview of the wavelet-based coupling techniques we have developed recently. In particular, we provide details about the compound wavelet matrix (CWM) and the dynamic CWM (dCWM) methods and show they are highly efficient in transferring information among multiphysics models across multiple temporal and spatial scales. The algorithmic gain is in addition to the parallel spatial scalability from traditional domain decomposition methods. The CWM algorithms are serial in time and limited by the smallest-system time-scales. In order to relax this algorithmic constraint, we have recently coupled time parallel (TP) algorithms to CWM, thus yielding a novel approach termed tpCWM. We present preliminary results from the tpCWM technique, indicating that we can accelerate time-to-solution by 2 to 3-orders of magnitude even on 20-processors and this can potentially constitute a new paradigm for MSMP simulations. If such improvements in simulation capability can be generalized, the tpCWM approach can lead the way to predictive simulations of biomass thermochemical processes.

09 BIOMASS FUELS↗

Bringing randomized algorithms to mainstream numerical linear algebra

Numerical linear algebra (NLA) underpins huge swaths of computational science and engineering. For scientists and engineers to make the most of the DOE’s computing resources, it is essential that they have access to high-performance implementations of algorithms with best-in-class scalability and reliability. Despite this, prevailing NLA libraries have little to no support for breakthrough algorithms from the field of randomized numerical linear algebra (RandNLA) that have been developed over the past twenty years. The goal of this LDRD was to break a log-jam that had prevented broad adoption of RandNLA. Our work had two thrusts. The first was to develop RandBLAS: a trustworthy and high-performance C++ library for randomized dimension reduction (an operation widely known as sketching). The second was the development of a novel randomized algorithm for computing a challenging type of matrix decomposition known as Householder QR with column pivoting (Householder QRCP). In this one-year late-start LDRD we successfully delivered RandBLAS 1.0 and new CPU and GPU codes for Householder QRCP. RandBLAS has extensive documentation at https://randblas.readthedocs.io/en/stable/. Papers on RandBLAS and and our high-performance QRCP codes are forthcoming.

97 MATHEMATICS AND COMPUTING↗

Approaching scalable VQE of interacting bosons with NISQ devices [Slides]

Scaling up variational quantum eigensolver (VQE) algorithms to practical applications utilizing quantum advantage with noisy intermediate-scale quantum (NISQ) devices is challenging. The expansive cost-function evaluation and demanding optimization quickly exhaust the precious quantum resource available on NISQ devices. In this work, we discuss the appropriate VQE strategy suitable for multi-site interacting boson systems, for example, the Holstein model and the Rabi lattice model. We investigate the cost-function setup and the optimization tactics to utilize the limited quantum resource efficiently. Our strategy illustrates that the scalable VQE algorithms of interacting bosons have a promising future.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

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↗

Diagnostic Models for Wind Turbine Gearbox Components Using SCADA Time Series Data: Preprint

This paper presents a scalable, autonomous framework for diagnostics of wind turbine gearbox failures using a multi-feature supervisory control and data acquisition data set spanning multiple years. Because of the size of the data set studied, all algorithms were constructed to be scalable using a Spark-Hadoop data framework. An unsupervised approach was used to detect significant failures based on predetermined criteria. The initial criteria selected were an abnormal spike in turbine component temperature followed by a turbine power off, which helps reduce the number of potential false alarms. To detect abnormal spikes in component temperature, a model was introduced to adjust the temperature data for effects caused by ambient temperature and normal temperature increases when loaded. This study evaluates methods for normalizing temperature sensor data to identify anomalies. The models that performed the best were a linear regression and a multivariate polynomial regression. The proposed process for finding failures has tunable parameters that can be adjusted to be more or less sensitive. The combination of sensor data normalization and application of these criteria is successful in finding turbine failures resulting in downtime. The proposed methods can operate without failure or maintenance logs and can be utilized for offline analysis of large high-resolution data sets.

17 WIND ENERGY↗

Exploring Applications of Random Walks on Spiking Neural Algorithms

Neuromorphic computing has many promises in the future of computing due to its energy efficient and scalable implementation. Here we extend a neural algorithm that is able to solve the diffusion equation PDE by implementing random walks on neuromorphic hardware. Additionally, we introduce four random walk applications that use this spiking neural algorithm. The four applications currently implemented are: generating a random walk to replicate an image, finding a path between two nodes, finding triangles in a graph, and partitioning a graph into two sections. We then made these four applications available to be implemented on software using a graphical user interface (GUI).

97 MATHEMATICS AND COMPUTING↗

A Parallel Ghosting Algorithm for The Flexible Distributed Mesh Database

Critical to the scalability of parallel adaptive simulations are parallel control functions including load balancing, reduced inter-process communication and optimal data decomposition. In distributed meshes, many mesh-based applications frequently access neighborhood information for computational purposes which must be transmitted efficiently to avoid parallel performance degradation when the neighbors are on different processors. This article presents a parallel algorithm of creating and deleting data copies, referred to as ghost copies, which localize neighborhood data for computation purposes while minimizing inter-process communication. The key characteristics of the algorithm are: (1) It can create ghost copies of any permissible topological order in a 1D, 2D or 3D mesh based on selected adjacencies. (2) It exploits neighborhood communication patterns during the ghost creation process thus eliminating all-to-all communication. (3) For applications that need neighbors of neighbors, the algorithm can create n number of ghost layers up to a point where the whole partitioned mesh can be ghosted. Strong and weak scaling results are presented for the IBM BG/P and Cray XE6 architectures up to a core count of 32,768 processors. The algorithm also leads to scalable results when used in a parallel super-convergent patch recovery error estimator, an application that frequently accesses neighborhood data to carry out computation.

Mubarak, Misbah↗

Homotopy Solver

This software implements parallel versions of an interior-point solver, based on the publicly available ipopt solver. Here we have full control over the linear solver and our algorithm is fully parallel thus enabling scalability to large-scale optimization problems. This package also has a parallel implementation of a homotopy solver developed under the scalable methods for contact LDRD project 23-ERD-017. This solver is an mfem-based implementation of algorithm described in ``A filter trust-region Newton continuation method for nonlinear complementarity problems''. Cosmin G. Petra, Nai-Yuan Chiang, Jingyi Wang, Tucker Hartland, and Michael Puso (submitted), LLNL-JRNL-869761.

Hartland, Tucker [Lawrence Livermore National Labo↗

Mining Large Heterogeneous Graphs using Cray s Urika

Pattern discovery and predictive modeling from seemingly related Big Data represented as massive, ad-hoc, heterogeneous networks (e.g., extremely large graphs with complex, possibly unknown structure) is an outstanding problem in many application domains. To address this problem, we are designing graph-mining algorithms capable of discovering relationship-patterns from such data and using those discovered patterns as features for classification and predictive modeling. Specifically, we are: (i) exploring statistical properties, mechanics and generative models of behavior patterns in heterogeneous information networks, (ii) developing novel, automated and scalable graph-pattern discovery algorithms and (iii) applying our relationship-analytics (data science + network science) expertise to domains spanning healthcare to homeland security.

fraud detection↗

Accelerating dissipative particle dynamics simulations on GPUs: Algorithms, numerics and applications

We present a scalable dissipative particle dynamics simulation code, fully implemented on the Graphics Processing Units (GPUs) using a hybrid CUDA/MPI programming model, which achieves 10-30 times speedup on a single GPU over 16 CPU cores and almost linear weak scaling across a thousand nodes. A unified framework is developed within which the efficient generation of the neighbor list and maintaining particle data locality are addressed. Our algorithm generates strictly ordered neighbor lists in parallel, while the construction is deterministic and makes no use of atomic operations or sorting. Such neighbor list leads to optimal data loading efficiency when combined with a two-level particle reordering scheme. A faster in situ generation scheme for Gaussian random numbers is proposed using precomputed binary signatures. We designed custom transcendental functions that are fast and accurate for evaluating the pairwise interaction. The correctness and accuracy of the code is verified through a set of test cases simulating Poiseuille flow and spontaneous vesicle formation. Computer benchmarks demonstrate the speedup of our implementation over the CPU implementation as well as strong and weak scalability. A large-scale simulation of spontaneous vesicle formation consisting of 128 million particles was conducted to further illustrate the practicality of our code in real-world applications.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

Quantum Dynamics at Scale: Ultrafast Control of Emergent Functional Materials

Confluence of extreme-scale quantum dynamics simulations (i.e. quantum@scale) and cutting-edge x-ray free-electron laser experiments are revolutionizing materials science. An archetypal example is the exciting concept of using picosecond light pulses to control emergent material properties on demand in atomically-thin layered materials. This paper describes efforts to scale our quantum molecular dynamics engine toward the United States' first exaflop/s computer, under an Aurora Early Science Program project named "Metascalable layered material genome". Key algorithmic and computing techniques incorporated are: (1) globally-scalable and locally-fast solvers within a linear-scaling divide-conquer-recombine algorithmic framework; (2) algebraic `BLASification' of computational kernels; and (3) data alignment and loop restructuring, along with register and cache blocking, for enhanced vectorization and efficient memory access. The resulting weak-scaling parallel efficiency was 0.93 on 131,072 Intel Xeon Phi cores for a 56.6 million atom (or 169 million valence-electron) system, whereas the various code transformations achieved 5-fold speedup. The optimized simulation engine allowed us for the first time to establish a significant effect of substrate on the dynamics of layered material upon electronic excitation.

Algebraic BLASification↗

Immersed Boundary Method Halo Exchange in a Hemodynamics Application

In recent years, highly parallelized simulations of blood flow resolving individual blood cells have been demonstrated. Simulating such dense suspensions of deformable particles in flow often involves a partitioned fluid-structure interaction (FSI) algorithm, with separate solvers for Eulerian fluid and Lagrangian cell grids, plus a solver - e.g., immersed boundary method - for their interaction. Managing data motion in parallel FSI implementations is increasingly important, particularly for inhomogeneous systems like vascular geometries. In this study, we evaluate the influence of Eulerian and Lagrangian halo exchanges on efficiency and scalability of a partitioned FSI algorithm for blood flow. We describe an MPI+OpenMP implementation of the immersed boundary method coupled with lattice Boltzmann and finite element methods. We consider how communication and recomputation costs influence the optimization of halo exchanges with respect to three factors: immersed boundary interaction distance, cell suspension density, and relative fluid/cell solver costs.

Gounley, John↗

Quantum Reinforcement Learning for Volt-VAR Control in Power Distribution Systems

Volt-VAR control (VVC) is crucial in active distribution networks for optimizing voltage profiles and minimizing network losses. While traditional deep reinforcement learning (DRL) algorithms exhibit promise for VVC, they often require extensive computational resources to handle such a high-dimensional problem. As a potential solution, quantum reinforcement learning (QRL) algorithms integrate the computational capabilities of quantum computing into the DRL framework. However, existing QRL algorithms struggle with complex VVC problems due to the limitations of current quantum hardware. To bridge this gap, this paper proposes an innovative QRL algorithm featuring an end-to-end architecture that integrates a classical autoencoder, variational quantum circuits (VQCs), and classical post-processing layers. This design efficiently compresses high-dimensional grid states, enabling VQCs to leverage quantum advantages while producing multiple control device outputs tailored for VVC tasks. Numerical studies on three representative distribution systems verify the effectiveness and scalability of the proposed QRL algorithm, and demonstrate its enhanced performance over classical approaches with only approximately 1% of the parameters. Additionally, the robustness of our developed algorithm is validated through noisy quantum environments.

97 MATHEMATICS AND COMPUTING↗

Impact Studies and Cooperative Voltage Control for High PV Penetration

The drastically increasing penetration of photovoltaic (PV) has posed tremendous challenges in operation, control, and protection in distribution networks. The over-voltage issue is one of major concerns for extremely high PV penetration (e.g. 100%). It is critical to identify the most sensitive locations to high PV penetration and apply effective methods to mitigate the over-voltage issue. This paper introduced a novel greedy search algorithm to locate worst-case scenarios of over-voltage in both distributed and centralized PV configurations, as well as a cooperative voltage control method to mitigate over-voltage. The search algorithm has the computational advantage over existing stochastic approach and provides more insights in impact studies. The cooperative control method relies upon reactive power compensation to converge system voltage to a predefined value within standard limits. Moreover, a clustering strategy is applied to divide the network into several clusters, within which all nodes share information with neighboring nodes following a scalable communication architecture. The control algorithms and communication hierarchies presented in this paper have been implemented into OpenDSS to form the Multi Agent (MA) OpenDSS package, which has been made available to the reader. The effectiveness of developed methods are demonstrated through simulation studies on the IEEE 123-node test feeder under four different load levels.

Cooperative control↗