Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “algorithmic efficiency”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 1,603 records · Page 89

A Parallel Multi-Domain Solution Methodology Applied to Nonlinear Thermal Transport Problems in Nuclear Fuel Pins

This paper describes an efficient and nonlinearly consistent parallel solution methodology for solving coupled nonlinear thermal transport problems that occur in nuclear reactor applications over hundreds of individual 3D physical subdomains. Efficiency is obtained by leveraging knowledge of the physical domains, the physics on individual domains, and the couplings between them for preconditioning within a Jacobian Free Newton Krylov method. Details of the computational infrastructure that enabled this work, namely the open source Advanced Multi-Physics (AMP) package developed by the authors is described. Details of verification and validation experiments, and parallel performance analysis in weak and strong scaling studies demonstrating the achieved efficiency of the algorithm are presented. Furthermore, numerical experiments demonstrate that the preconditioner developed is independent of the number of fuel subdomains in a fuel rod, which is particularly important when simulating different types of fuel rods. Finally, we demonstrate the power of the coupling methodology by considering problems with couplings between surface and volume physics and coupling of nonlinear thermal transport in fuel rods to an external radiation transport code.

11 NUCLEAR FUEL CYCLE AND FUEL MATERIALS↗

shiftNMFk 1.1: Robust Nonnegative matrix factorization with kmeans clustering and signal shift, for allocation of unknown physical sources, toy version for open sourcing with publications

This code is a toy (short) version of CODE-2016-83. From a general perspective, the code represents an unsupervised adaptive machine learning algorithm that allows efficient and high performance de-mixing and feature extraction of a multitude of non-negative signals mixed and recorded by a network of uncorrelated sensor arrays. The code identifies the number of the mixed original signals and their locations. Further, the code also allows deciphering of signals that have been delayed in regards to the mixing process in each sensor. This code is high customizable and it can be efficiently used for a fast macro-analyses of data. The code is applicable to a plethora of distinct problems: chemical decomposition, pressure transient decomposition, unknown sources/signal allocation, EM signal decomposition. An additional procedure for allocation of the unknown sources is incorporated in the code.

Alexandrov, Boian S.↗

Dimensionality Reduction Library v 0.2

Dimensionality Reduction Library is a C++ library for dimensionality reduction. In the context of this library, dimensionality reduction is considered to consist of 1)estimation of the intrinsic dimensionality using sampled data, 2) Finding maps that reduce the diemsionality of data (forward map) or increase the dimensionality of data (reverse map) and 3) mapping arbitray coordiantes to high and low dimensionalities. The library is intended toprovide a consistent interface to multiple dimensionality reduction algorithms with an efficient C++ interface that runs efficiently on multicore architectures. A few routines have been optimized with an option for GPU acceleration or distributed computation. Currently the library offers intrinsic dimensionality estimation using point-PCA reconstruction error and/ residual variance. The following dimensionality reduction methods have been implemented: Principal Component Analysis Multidimensional Scaling Locally Linear Embedding IsoMap Autoencoder Neutral Networks An executable is also supplied that can be built to allow for command-line access to the library routines. A description for an applciation of the library for molecular structure analysis has been published.

BROWN, WILLIAM↗

APHiD: Hierarchical Task Placement to Enable a Tapered Fat Tree Topology for Lower Power and Cost in HPC Networks

The power and procurement cost of bandwidth in system-wide networks has forced a steady drop in the byte/flop ratio. This trend of computation becoming faster relative to the network is expected to hold. In this paper, we explore how cost-oriented task placement enables reducing the cost of system-wide networks by enabling high performance even on tapered topologies where more bandwidth is provisioned at lower levels. We describe APHiD, an efficient hierarchical placement algorithm that uses new techniques to improve the quality of heuristic solutions and reduces the demand on high-level, expensive bandwidth in hierarchical topologies. We apply APHiD to a tapered fat-tree, demonstrating that APHiD maintains application scalability even for severely tapered network configurations. Using simulation, we show that for tapered networks APHiD improves performance by more than 50% over random placement and even 15% in some cases over costlier, state-of-the-art placement algorithms.

Michelogiannakis, George↗

Blazing Signature Filter

BSF is a highly efficient pairwise similarity algorithm enabling extensive data mining.

Source record↗

Automated Proton Track Identification in MicroBooNE Using Gradient Boosted Decision Trees

MicroBooNE is a liquid argon time projection chamber (LArTPC) neutrino experiment that is currently running in the Booster Neutrino Beam at Fermilab. LArTPC technology allows for high-resolution, three-dimensional representations of neutrino interactions. A wide variety of software tools for automated reconstruction and selection of particle tracks in LArTPCs are actively being developed. Short, isolated proton tracks, the signal for low- momentum-transfer neutral current (NC) elastic events, are easily hidden in a large cosmic background. Detecting these low-energy tracks will allow us to probe interesting regions of the proton's spin structure. An effective method for selecting NC elastic events is to combine a highly efficient track reconstruction algorithm to find all candidate tracks with highly accurate particle identification using a machine learning algorithm. We present our work on particle track classification using gradient tree boosting software (XGBoost) and the performance on simulated neutrino data.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

Influence of Ionization and Beam Quality on Interaction of TW-Peak CO2 Laser with Hydrogen Plasma

3D numerical simulations of the interaction of a powerful CO2 laser with hydrogen jets demonstrating the role of ionization and laser beam quality are presented. Simulations are performed in support of the plasma wakefield accelerator experiments being conducted at the BNL Accelerator Test Facility (ATF). The CO2 laser at BNL ATF has several potential advantages for laser wakefield acceleration compared to widely used solid-state lasers. SPACE, a parallel relativistic Particle-in-Cell code, developed at SBU and BNL, has been used in these studies. A novelty of the code is its set of efficient atomic physics algorithms that compute ionization and recombination rates on the grid and transfer them to particles. The primary goal of the initial BNL experiments was to characterize the plasma density by measuring the sidebands in the spectrum of the probe laser. Simulations, that resolve hydrogen ionization and laser spectra, help explain several trends that were observed in the experiments.

97 MATHEMATICS AND COMPUTING↗

Developing an Operational Testing Ground for Autonomous and Connected Vehicles

This paper provides a framework for developing a connected vehicle “sandbox” environment where connected vehicles equipped with Dedicated Short-Range Communication (DSRC) radios can interface with sensors that operate on a range of software architectures using open-source tools. In control system design, rapid prototyping for connected vehicle applications can be a challenge when the subsystems operate with different communication protocols, at different data rates, and with changing connectivity between subsystems. In this work, we showcase the use of open-source software tools, specifically the Robot Operating System (ROS), to facilitate connecting DSRC radios with embedded systems in both vehicle and infrastructure applications. Here, this integration helps in the rapid field testing of algorithms in an efficient manner in both hardware-in-the-loop applications as well as prototype deployments. Two examples are presented that demonstrate the use of this framework: 1) the use of DSRC systems for emergency responders in crash situations, and 2) using DSRC systems to reduce the fuel consumption of connected commercial trucks.

33 ADVANCED PROPULSION SYSTEMS↗

Partially Collapsed Gibbs Samplers for Linear Inverse Problems and Applications to X-ray Imaging

Deblurring is one of the most common linear inverse problems in imaging, and most methods for deblurring an image assume that the convolution kernel, the so-called point spread function (PSF), is known or attempt to reconstruct the PSF simultaneously with the image. For many experimental imaging systems, like high energy X-ray radiography systems, the PSF must be computed from calibration imagery. The associated inverse problem is large-scale, so, in order to compute meaningful uncertainties with the reconstruction, it is common to use hierarchical Bayesian models and Markov chain Monte Carlo methods for sampling from the posterior. Classical Gibbs samplers can suffer from long autocorrelation lengths in the Markov chain when the reconstructed quantity in the inverse problem is finely discretized, resulting in poor computational efficiency of the Markov chain. In this work we present partially collapsed Gibbs samplers for linear inverse problems that greatly decrease correlations in the Markov chain, thus increasing the computational efficiency of the algorithms, and we present the results of the enhanced samplers on the problem of reconstructing the point spread function for an X-ray imaging system at the U.S. Department of Energy's Nevada National Security Site.

97 MATHEMATICS AND COMPUTING↗

TriC: Distributed-memory Triangle Counting by Exploiting the Graph Structure

Graph analytics has emerged as an important tool in the analysis of large scale data from diverse application domains such as social networks, cyber security and bioinformatics. Counting the number of triangles in a graph is a fundamental kernel with several applications such as detecting the community structure of a graph or in identifying important vertices in a graph. The ubiquity of massive datasets is driving the need to scale graph analytics on parallel systems. However, numerous challenges exist in efficiently parallelizing graph algorithms, especially on distributed-memory systems. Irregular memory accesses and communication patterns, low computation to communication ratios, and the need for frequent synchronization are some of the leading challenges. In this paper, we present TriC, our distributed-memory implementation of triangle counting in graphs using the Message Passing Interface (MPI), as a submission to the 2020 GraphChallenge competition. Using a set of synthetic and real-world inputs from the challenge, we demonstrate a speedup of up to 90x relative to previous work on 32 processor-cores of a NERSC Cori node. We also provide details from distributed runs with up to8192 processes along with strong scaling results. The observations presented in this work provide an understanding of the system-level bottlenecks at scale that specifically impact sparse-irregular workloads and will therefore benefit other efforts to parallelize graph algorithms.

Halappanavar, Mahantesh↗

Parallelizing the Unpacking and Clustering of Detector Data for Reconstruction of Charged Particle Tracks on Multi-core CPUs and Many-core GPUs

We present results from parallelizing the unpacking and clustering steps of the raw data from the silicon strip modules for reconstruction of charged particle tracks. Throughput is further improved by concurrently processing multiple events using nested OpenMP parallelism on CPU or CUDA streams on GPU. The new implementation along with earlier work in developing a parallelized and vectorized implementation of the combinatoric Kalman filter algorithm has enabled efficient global reconstruction of the entire event on modern computer architectures. We demonstrate the performance of the new implementation on Intel Xeon and NVIDIA GPU architectures.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

Faster approximate subgraph counts with privacy

One of the most common problems studied in the context of differential privacy for graph data is counting the number of non-induced embeddings of a subgraph in a given graph. These counts have very high global sensitivity. Therefore, adding noise based on powerful alternative techniques, such as smooth sensitivity and higher-order local sensitivity have been shown to give significantly better accuracy. However, all these alternatives to global sensitivity become computationally very expensive, and to date efficient polynomial time algorithms are known only for few selected subgraphs, such as triangles, k-triangles, and k-stars. In this paper, we show that good approximations to these sensitivity metrics can be still used to get private algorithms. Using this approach, we much faster algorithms for privately counting the number of triangles in real-world social networks, which can be easily parallelized. We also give a private polynomial time algorithm for counting any constant size subgraph using less noise than the global sensitivity; we show this can be improved significantly for counting paths in special classes of graphs

Nguyen, Dung↗

Scalable All-pairs Shortest Paths for Huge Graphs on Multi-GPU Clusters

We present an optimized Floyd-Warshall (Floyd-Warshall) algorithm that computes the All-pairs shortest path (APSP) for GPU accelerated clusters. The Floyd-Warshall algorithm due to its structural similarities to matrix-multiplication is well suited for highly parallel GPU architectures. To achieve high parallel efficiency, we address two key algorithmic challenges: reducing high communication overhead and addressing limited GPU memory. To reduce high communication costs, we redesign the parallel (a) to expose more parallelism, (b) aggressively overlap communication and computation with pipelined and asynchronous scheduling of operations, and (c) tailored MPI-collective. To cope with limited GPU memory, we employ an offload model, where the data resides on the host and is transferred to GPU on-demand. The proposed optimizations are supported with detailed performance models for tuning. Our optimized parallel Floyd-Warshall implementation is up to 5x faster than a strong baseline and achieves 8.1 PetaFLOPS/sec on 256~nodes of the Summit supercomputer at Oak Ridge National Laboratory. This performance represents 70% of the theoretical peak and 80% parallel efficiency. The offload algorithm can handle 2.5x larger graphs with a 20% increase in overall running time.

Sao, Piyush↗

Quantum simulation of exact electron dynamics can be more efficient than classical mean-field methods

Quantum algorithms for simulating electronic ground states are slower than popular classical mean-field algorithms such as Hartree–Fock and density functional theory but offer higher accuracy. Accordingly, quantum computers have been predominantly regarded as competitors to only the most accurate and costly classical methods for treating electron correlation. However, here we tighten bounds showing that certain first-quantized quantum algorithms enable exact time evolution of electronic systems with exponentially less space and polynomially fewer operations in basis set size than conventional real-time time-dependent Hartree–Fock and density functional theory. Although the need to sample observables in the quantum algorithm reduces the speedup, we show that one can estimate all elements of the k-particle reduced density matrix with a number of samples scaling only polylogarithmically in basis set size. We also introduce a more efficient quantum algorithm for first-quantized mean-field state preparation that is likely cheaper than the cost of time evolution. We conclude that quantum speedup is most pronounced for finite-temperature simulations and suggest several practically important electron dynamics problems with potential quantum advantage.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Tusas: A fully implicit parallel approach for coupled phase-field equations

In this study, we develop a fully-coupled, fully-implicit approach for phase-field modeling of solidification in metals and alloys. Predictive simulation of solidification in pure metals and metal alloys remains a significant challenge in the field of materials science, as microstructure formation during the solidification process plays a critical role in the properties and performance of the solid material. Our simulation approach consists of a finite element spatial discretization of the fully-coupled nonlinear system of partial differential equations at the microscale, which is treated implicitly in time with a preconditioned Jacobian-free Newton-Krylov method. The approach is algorithmically scalable as well as efficient due to an effective preconditioning strategy based on algebraic multigrid and block factorization. We implement this approach in the open-source Tusas framework, which is a general, flexible tool developed in C++ for solving coupled systems of nonlinear partial differential equations. The performance of our approach is analyzed in terms of algorithmic scalability and efficiency, while the computational performance of Tusas is presented in terms of parallel scalability and efficiency on emerging heterogeneous architectures. We demonstrate that modern algorithms, discretizations, and computational science, and heterogeneous hardware provide a robust route for predictive phase-field simulation of microstructure evolution during additive manufacturing.

97 MATHEMATICS AND COMPUTING↗

Petascale Computing Enabling Technologies Project Final Report

The Petascale Computing Enabling Technologies (PCET) project addressed challenges arising from current trends in computer architecture that will lead to large-scale systems with many more nodes, each of which uses multicore chips. These factors will soon lead to systems that have over one million processors. Also, the use of multicore chips will lead to less memory and less memory bandwidth per core. We need fundamentally new algorithmic approaches to cope with these memory constraints and the huge number of processors. Further, correct, efficient code development is difficult even with the number of processors in current systems; more processors will only make it harder. The goal of PCET was to overcome these challenges by developing the computer science and mathematical underpinnings needed to realize the full potential of our future large-scale systems. Our research results will significantly increase the scientific output obtained from LLNL large-scale computing resources by improving application scientist productivity and system utilization. Our successes include scalable mathematical algorithms that adapt to these emerging architecture trends and through code correctness and performance methodologies that automate critical aspects of application development as well as the foundations for application-level fault tolerance techniques. PCET's scope encompassed several research thrusts in computer science and mathematics: code correctness and performance methodologies, scalable mathematics algorithms appropriate for multicore systems, and application-level fault tolerance techniques. Due to funding limitations, we focused primarily on the first three thrusts although our work also lays the foundation for the needed advances in fault tolerance. In the area of scalable mathematics algorithms, our preliminary work established that OpenMP performance of the AMG linear solver benchmark and important individual kernels on Atlas did not match the predictions of our simple initial model. Our investigations demonstrated that a poor default memory allocation mechanism degraded performance. We developed a prototype NUMA library to provide generic mechanisms to overcome these issues, resulting in significantly improved OpenMP performance. After additional testing, we will make this library available to all users, providing a simple means to improve threading on LLNL's production Linux platforms. We also made progress on developing new scalable algorithms that target multicore nodes. We designed and implemented a new AMG interpolation operator with improved convergence properties for very low complexity coarsening schemes. This implementation will also soon be available to LLNL's application teams as part of the hypre library. We presented results for both topics in an invited plenary talk entitled 'Efficient Sparse Linear Solvers for Multi-Core Architectures' at the 2009 HPCMP Institutes Annual Meeting/CREATE Annual All-Hands Meeting. The interpolation work was summarized in a talk entitled 'Improving Interpolation for Aggressive Coarsening' at the 14th Copper Mountain Conference on Multigrid Methods and in a research paper that will appear in Numerical Linear Algebra with Applications. In the area of code correctness, we significantly extended our behavior equivalence class identification mechanism. Specifically, we not only demonstrated it works well at very large scales but we also added the ability to classify MPI tasks not only by function call traces, but also by specific call sites (source code line numbers) being executed by tasks. More importantly, we developed a new technique to determine relative logical execution progress of tasks in the equivalence classes by combining static analysis with our original dynamic approach. We applied this technique to a correctness issue that arose at 4096 tasks during the development of the new AMG interpolation operator discussed above. This scale isat the limit of effectiveness of production tools, but our technique quickly located the erroneous source code, demonstrating the power of understanding relationships between behavioral equivalence classes. This work is the subject of a paper recently accepted to SC09, as well as a presentation entitled 'Providing Order to Extreme Scale Debugging Chaos' given at the ParaDyn Week annual conference in College Park, MD. In addition to this theoretical extension, we have made significant progress in developing a front end for this tool set, and the front-end is now available on several of LLNL's largescale computing resources. In addition, we explored mechanisms to identify exact locations of erroneous MPI usage in application source code. In this work, we developed a new model that led to a highly efficient algorithm for detecting deadlock during dynamic software testing. This work was the subject of a well-received paper at ICS 2009 [4].

99 GENERAL AND MISCELLANEOUS↗

Optimization of stepwise clustering algorithm in backward trajectory analysis

In recent years, the backward trajectory model has been widely used in the research of meteorological and atmospheric environmental quality. This paper presents a comprehensive study on a stepwise clustering analysis algorithm in the clustering process of backward trajectory model and an application of the clustering analysis of single-particle backward trajectory in 2016 in Changchun City. This study starts with an analysis of the original stepwise clustering algorithm and its application to a clustering process of 8784 backward trajectories during 48 h in Changchun City as a benchmark test case. Then, two improvements are made in the algorithm: First, in the process of finding the optimal classification, the algorithm complexity is improved from original O(n 3 ) to O(log(n)*n 2 ) through algorithm improvement. The algorithm performance is enhanced by log(n) times. Next, in the process of re-establishing the classification, the algorithm complexity is improved from the original O(m*n 2 ) to O(m*log(n)*n), that is another algorithm performance improvement by a factor of log(n). Therefore, the accumulative execution efficiency improvement through the algorithm optimization is 2*log(n) times, which has been further verified in the practical application in Changchun City.

97 MATHEMATICS AND COMPUTING↗

Correspondence between open bosonic systems and stochastic differential equations

Bosonic mean-field theories can approximate the dynamics of systems of $n$ bosons provided that $n \gg 1$. Here, we show that there can also be an exact correspondence at finite $n$ when the bosonic system is generalized to include interactions with the environment and the mean-field theory is replaced by a stochastic differential equation. When the $n \to \infty$ limit is taken, the stochastic terms in this differential equation vanish, and a mean-field theory is recovered. Besides providing insight into the differences between the behavior of finite quantum systems and their classical limits given by $n \to \infty$, the developed mathematics can provide a basis for quantum algorithms that solve some stochastic nonlinear differential equations. We discuss conditions on the efficiency of these quantum algorithms, with a focus on the possibility for the complexity to be polynomial in the log of the stochastic system size. A particular system with the form of a stochastic discrete nonlinear Schrödinger equation is analyzed in more detail.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗