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 685 records · Page 38
All sourcesNASA NTRSDOE OSTI
NASA NTRS1996

Design and implementation of scalable tape archiver

In order to reduce costs, computer manufacturers try to use commodity parts as much as possible. Mainframes using proprietary processors are being replaced by high performance RISC microprocessor-based workstations, which are further being replaced by the commodity microprocessor used in personal computers. Highly reliable disks for mainframes are also being replaced by disk arrays, which are complexes of disk drives. In this paper we try to clarify the feasibility of a large scale tertiary storage system composed of 8-mm tape archivers utilizing robotics. In the near future, the 8-mm tape archiver will be widely used and become a commodity part, since recent rapid growth of multimedia applications requires much larger storage than disk drives can provide. We designed a scalable tape archiver which connects as many 8-mm tape archivers (element archivers) as possible. In the scalable archiver, robotics can exchange a cassette tape between two adjacent element archivers mechanically. Thus, we can build a large scalable archiver inexpensively. In addition, a sophisticated migration mechanism distributes frequently accessed tapes (hot tapes) evenly among all of the element archivers, which improves the throughput considerably. Even with the failures of some tape drives, the system dynamically redistributes hot tapes to the other element archivers which have live tape drives. Several kinds of specially tailored huge archivers are on the market, however, the 8-mm tape scalable archiver could replace them. To maintain high performance in spite of high access locality when a large number of archivers are attached to the scalable archiver, it is necessary to scatter frequently accessed cassettes among the element archivers and to use the tape drives efficiently. For this purpose, we introduce two cassette migration algorithms, foreground migration and background migration. Background migration transfers cassettes between element archivers to redistribute frequently accessed cassettes, thus balancing the load of each archiver. Background migration occurs the robotics are idle. Both migration algorithms are based on access frequency and space utility of each element archiver. To normalize these parameters according to the number of drives in each element archiver, it is possible to maintain high performance even if some tape drives fail. We found that the foreground migration is efficient at reducing access response time. Beside the foreground migration, the background migration makes it possible to track the transition of spatial access locality quickly.

Nemoto, Toshihiro↗
NASA NTRS1997

A Comparison of PETSC Library and HPF Implementations of an Archetypal PDE Computation

Two paradigms for distributed-memory parallel computation that free the application programmer from the details of message passing are compared for an archetypal structured scientific computation a nonlinear, structured-grid partial differential equation boundary value problem using the same algorithm on the same hardware. Both paradigms, parallel libraries represented by Argonne's PETSC, and parallel languages represented by the Portland Group's HPF, are found to be easy to use for this problem class, and both are reasonably effective in exploiting concurrency after a short learning curve. The level of involvement required by the application programmer under either paradigm includes specification of the data partitioning (corresponding to a geometrically simple decomposition of the domain of the PDE). Programming in SPAM style for the PETSC library requires writing the routines that discretize the PDE and its Jacobian, managing subdomain-to-processor mappings (affine global- to-local index mappings), and interfacing to library solver routines. Programming for HPF requires a complete sequential implementation of the same algorithm, introducing concurrency through subdomain blocking (an effort similar to the index mapping), and modest experimentation with rewriting loops to elucidate to the compiler the latent concurrency. Correctness and scalability are cross-validated on up to 32 nodes of an IBM SP2.

Hayder, M. Ehtesham↗
NASA NTRS2000

HTMT-class Latency Tolerant Parallel Architecture for Petaflops Scale Computation

Computational Aero Sciences and other numeric intensive computation disciplines demand computing throughputs substantially greater than the Teraflops scale systems only now becoming available. The related fields of fluids, structures, thermal, combustion, and dynamic controls are among the interdisciplinary areas that in combination with sufficient resolution and advanced adaptive techniques may force performance requirements towards Petaflops. This will be especially true for compute intensive models such as Navier-Stokes are or when such system models are only part of a larger design optimization computation involving many design points. Yet recent experience with conventional MPP configurations comprising commodity processing and memory components has shown that larger scale frequently results in higher programming difficulty and lower system efficiency. While important advances in system software and algorithms techniques have had some impact on efficiency and programmability for certain classes of problems, in general it is unlikely that software alone will resolve the challenges to higher scalability. As in the past, future generations of high-end computers may require a combination of hardware architecture and system software advances to enable efficient operation at a Petaflops level. The NASA led HTMT project has engaged the talents of a broad interdisciplinary team to develop a new strategy in high-end system architecture to deliver petaflops scale computing in the 2004/5 timeframe. The Hybrid-Technology, MultiThreaded parallel computer architecture incorporates several advanced technologies in combination with an innovative dynamic adaptive scheduling mechanism to provide unprecedented performance and efficiency within practical constraints of cost, complexity, and power consumption. The emerging superconductor Rapid Single Flux Quantum electronics can operate at 100 GHz (the record is 770 GHz) and one percent of the power required by convention semiconductor logic. Wave Division Multiplexing optical communications can approach a peak per fiber bandwidth of 1 Tbps and the new Data Vortex network topology employing this technology can connect tens of thousands of ports providing a bi-section bandwidth on the order of a Petabyte per second with latencies well below 100 nanoseconds, even under heavy loads. Processor-in-Memory (PIM) technology combines logic and memory on the same chip exposing the internal bandwidth of the memory row buffers at low latency. And holographic storage photorefractive storage technologies provide high-density memory with access a thousand times faster than conventional disk technologies. Together these technologies enable a new class of shared memory system architecture with a peak performance in the range of a Petaflops but size and power requirements comparable to today's largest Teraflops scale systems. To achieve high-sustained performance, HTMT combines an advanced multithreading processor architecture with a memory-driven coarse-grained latency management strategy called "percolation", yielding high efficiency while reducing the much of the parallel programming burden. This paper will present the basic system architecture characteristics made possible through this series of advanced technologies and then give a detailed description of the new percolation approach to runtime latency management.

Sterling, Thomas↗
DOE OSTI2021

Nonlinear Matrix Approximation with Radial Basis Function Components

We introduce and investigate matrix approximation by decomposition into a sum of radial basis function (RBF) components. An RBF component is a generalization of the outer product between a pair of vectors, where an RBF function replaces the scalar multiplication between individual vector elements. Even though the RBF functions are positive definite, the summation across components is not restricted to convex combinations and allows us to compute the decomposition for any real matrix that is not necessarily symmetric or positive definite. We formulate the problem of seeking such a decomposition as an optimization problem with a nonlinear and non-convex loss function. Several modern versions of the gradient descent method, including their scalable stochastic counterparts, are used to solve this problem. We provide extensive empirical evidence of the effectiveness of the RBF decomposition and that of the gradient-based fitting algorithm. While being conceptually motivated by singular value decomposition (SVD), our proposed nonlinear counterpart outperforms SVD by drastically reducing the memory required to approximate a data matrix with the same L2 error for a wide range of matrix types. For example, it leads to 2 to 6 times memory save for Gaussian noise, graph adjacency matrices, and kernel matrices. Moreover, this proximity-based decomposition can offer additional interpretability in applications that involve, e.g., capturing the inner low-dimensional structure of the data, retaining graph connectivity structure, and preserving the acutance of images.

Rebrova, Elizaveta↗
DOE OSTI2023

Distributed approximate minimal Steiner trees with millions of seed vertices on billion-edge graphs

In this report, we present a parallel 2-approximation Steiner minimal tree algorithm and its MPI-based distributed implementation. In place of expensive distance computations between all pairs of seed vertices, the solution we employ exploits a cheaper Voronoi cell computation. Our design leverages asynchronous processing and message prioritization to accelerate convergence of distance computations, and harnesses vertex and edge centric processing to offer fast time-to-solution. We demonstrate scalability and performance using real-world graphs with up to 128 billion edges and 512 compute nodes, and show the ability to find Steiner trees with up to one million seed vertices. Using 12 data instances, we present comparison with the state-of-the-art exact solver, SCIP-Jack, and two sequential 2-approximate algorithms. We empirically show that, on average, the total distance of the Steiner tree identified by our solution is 1.1290 times greater than the Steiner minimal tree – well within the theoretical approximation bound of 2.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2019

Using Graph Partitioning for Scalable Distributed Quantum Molecular Dynamics

The simulation of the physical movement of multi-body systems at an atomistic level, with forces calculated from a quantum mechanical description of the electrons, motivates a graph partitioning problem studied in this article. Several advanced algorithms relying on evaluations of matrix polynomials have been published in the literature for such simulations. We aim to use a special type of graph partitioning to efficiently parallelize these computations. For this, we create a graph representing the zero–nonzero structure of a thresholded density matrix, and partition that graph into several components. Each separate submatrix (corresponding to each subgraph) is then substituted into the matrix polynomial, and the result for the full matrix polynomial is reassembled at the end from the individual polynomials. This paper starts by introducing a rigorous definition as well as a mathematical justification of this partitioning problem. We assess the performance of several methods to compute graph partitions with respect to both the quality of the partitioning and their runtime.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Enhancing scalability of a matrix-free eigensolver for studying many-body localization

We propose several techniques to enhance the parallel scalability of a matrix-free eigensolver designed for studying many-body localization (MBL) of quantum spin chain models with nearest-neighbor interactions and on-site disorder. This type of problem is computationally challenging because the dimension of the associated Hamiltonian matrix grows exponentially with respect to the number of spins L, and we need to average over different realizations of the random disorder to obtain relevant statistical behavior. For each disorder realization, we need to compute eigenvalues from different regions of the spectrum and their corresponding eigenvectors. In previous work, the interior eigenstates for a single eigenvalue problem are computed via the shift-and-invert Lanczos algorithm. Due to the extremely high memory footprint of the LU factorizations, this technique is not well suited for large L’s. For example, we need thousands of compute nodes on modern high performance computing infrastructures to go beyond L = 24. The matrix-free approach does not suffer from this memory bottleneck, however, its scalability is limited by a computation and communication load imbalance. To reduce this imbalance and to significantly enhance the scalability of the matrix-free eigensolver, we reorder the matrix and leverage the consistent space runtime, CSPACER. We also show its efficiency in managing irregular communication patterns at scale compared to optimized MPI non-blocking two-sided and one-sided RMA implementation variants. This effort enables us to study MBL for spin chains with a larger number of spins. The efficiency and effectiveness of the proposed algorithm is demonstrated by computing eigenstates on a massively parallel many-core high performance computer.

METIS↗
DOE OSTI2022

PWR loading pattern optimization with reinforcement learning

The core loading pattern optimization problem belongs to the class of combinatorial optimization problem and has been studied since the dawn of commercial nuclear energy industry. It is characterized by multiple objectives and constraints, with a very high number of candidate patterns, which makes it impossible to solve explicitly. Stochastic optimization methodologies including Genetic Algorithms and Simulated Annealing are used by different nuclear utilities and vendors to perform fuel cycle reload design. Nevertheless, hand-designed solutions continue to be the prevalent method in the industry. To improve the state-of-the-art core reload patterns, we aim to create a method as scalable as possible, that agrees with the designer's goal of performance and safety. To help in this task Deep Reinforcement Learning (DRL), in particular Proximal Policy Optimization is leveraged. DRL has recently experienced a strong impetus from its successes applied to games, sometimes even reaching 'super-human' performances. This paper lays out the foundation of this method and proposes to study the behavior of several hyper-parameters that influence the DRL algorithm. The algorithm is highly dependent on multiple factors such as an exploration/exploitation trade-off that manifests through different parameters such as the number of loading patterns seen and the number of samples collected before a policy update, but also the shape of the objective function derived for the core design. Experimental results also demonstrate the effectiveness of the method in finding high-quality solutions from scratch within a reasonable amount of time. (authors)

21 SPECIFIC NUCLEAR REACTORS AND ASSOCIATED PLANTS↗
DOE OSTI2017

Chance-Constrained AC Optimal Power Flow: Reformulations and Efficient Algorithms

Higher levels of renewable electricity generation increase uncertainty in power system operation. To ensure secure system operation, new tools that account for this uncertainty are required. Here, in this paper, we adopt a chance-constrained AC optimal power flow formulation, which guarantees that generation, power flows and voltages remain within their bounds with a pre-defined probability. We then discuss different chance-constraint reformulations and solution approaches for the problem. Additionally, we first discuss an analytical reformulation based on partial linearization, which enables us to obtain a tractable representation of the optimization problem. We then provide an efficient algorithm based on an iterative solution scheme which alternates between solving a deterministic AC OPF problem and assessing the impact of uncertainty. This more flexible computational framework enables not only scalable implementations, but also alternative chance-constraint reformulations. In particular, we suggest two sample based reformulations that do not require any approximation or relaxation of the AC power flow equations.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2023

ActiveBAS: A Low-cost, Scalable Control Solution for Grid-Interactive Small and Medium Sized Commercial Buildings

This project aims to develop and enhance a low-cost, highly scalable control solution for Small and Medium-Sized Commercial Buildings (SMCB), assess the business potential at multiple sites, and perform commercialization efforts. The technology can be applied to any buildings served by multiple units, with the benefits being greatest for open-spaced buildings, such as banks, retail stores, restaurants, and factories. This project aims to develop an affordable control solution for: 1) SMCB grid responsiveness, 2) reduction of GHG by changing unit operations, 3) greater reduction in utility costs, and 4) rapid adoption in the marketplace. The proposed technology will be built on a previously developed and demonstrated MPC solution. The minimal sensor requirement and less need of control expertise are the unique feature of the algorithm that leads to low capital and maintenance costs, and short installation and implementation time. These attributes contribute to low capital and maintenance costs, as well as a short installation and implementation time. However, these advantages come with a trade-off: increased difficulties and unreliability when applying traditional modeling and MPC control approaches due to limited information. This final report describes the modeling approaches developed and tested to overcome these challenges. It begins by outlining the modeling challenge posed by minimal sensor requirements, then delves into the proposed modeling approaches, which primarily involve system identification. Finally, preliminary test results for a simulation case study are presented.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2023

Quantifying uncertainty for deep learning based forecasting and flow-reconstruction using neural architecture search ensembles

Classical problems in computational physics such as data-driven forecasting and signal reconstruction from sparse sensors have recently seen an explosion in deep neural network (DNN) based algorithmic approaches. However, most DNN models do not provide uncertainty estimates, which are crucial for establishing the trustworthiness of these techniques in downstream decision making tasks and scenarios. In recent years, ensemble-based methods have achieved significant success for the uncertainty quantification in DNNs on a number of benchmark problems. However, their performance on real-world applications remains under-explored. In this work, we present an automated approach to DNN discovery and demonstrate how this may also be utilized for ensemble-based uncertainty quantification. Specifically, we propose the use of a scalable neural and hyperparameter architecture search for discovering an ensemble of DNN models for complex dynamical systems. We highlight how the proposed method not only discovers high-performing neural network ensembles for our tasks, but also quantifies uncertainty seamlessly. This is achieved by using genetic algorithms and Bayesian optimization for sampling the search space of neural network architectures and hyperparameters. Subsequently, a model selection approach is used to identify candidate models for an ensemble set construction. Afterwards, a variance decomposition approach is used to estimate the uncertainty of the predictions from the ensemble. We demonstrate the feasibility of this framework for two tasks — forecasting from historical data and flow reconstruction from sparse sensors for the sea-surface temperature. In conclusion, we demonstrate superior performance from the ensemble in contrast with individual high-performing models and other benchmarks.

Deep ensembles↗
DOE OSTI2023

Two-fluid physical modeling of superconducting resonators in the ARTEMIS framework

In this work, we implement a new London equation module for superconductivity in the GPU-enabled ARTEMIS framework, and couple it to a finite-difference time-domain solver for Maxwell's equations. We apply this two-fluid approach to model a superconducting coplanar waveguide (CPW) resonator. We validate our implementation by verifying that the theoretical skin depth and reflection coefficients can be obtained for several superconductive materials, with different London penetration depths, over a range of frequencies. Our convergence studies show that the algorithm is second-order accurate in both space and time, except at superconducting interfaces where the approach is spatially first-order. In our CPW simulations, we leverage the GPU scalability of our code to compare the two-fluid model to more traditional approaches that approximate superconducting behavior and demonstrate that superconducting physics can show comparable performance to the assumption of quasi-infinite conductivity as measured by the Q-factor.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗
DOE OSTI2017

Application-Specific Graph Sampling for Frequent Subgraph Mining and Community Detection

Graph mining is an important data analysis methodology, but struggles as the input graph size increases. The scalability and usability challenges posed by such large graphs make it imperative to sample the input graph and reduce its size. The critical challenge in sampling is to identify the appropriate algorithm to insure the resulting analysis does not suffer heavily from the data reduction. Predicting the expected performance degradation for a given graph and sampling algorithm is also useful. In this paper, we present different sampling approaches for graph mining applications such as Frequent Subgrpah Mining (FSM), and Community Detection (CD). We explore graph metrics such as PageRank, Triangles, and Diversity to sample a graph and conclude that for heterogeneous graphs Triangles and Diversity perform better than degree based metrics. We also present two new sampling variations for targeted graph mining applications. We present empirical results to show that knowledge of the target application, along with input graph properties can be used to select the best sampling algorithm. We also conclude that performance degradation is an abrupt, rather than gradual phenomena, as the sample size decreases. We present the empirical results to show that the performance degradation follows a logistic function.

Purohit, Sumit↗
NASA NTRS2004

A Scalable Nonuniform Pointer Analysis for Embedded Program

In this paper we present a scalable pointer analysis for embedded applications that is able to distinguish between instances of recursively defined data structures and elements of arrays. The main contribution consists of an efficient yet precise algorithm that can handle multithreaded programs. We first perform an inexpensive flow-sensitive analysis of each function in the program that generates semantic equations describing the effect of the function on the memory graph. These equations bear numerical constraints that describe nonuniform points-to relationships. We then iteratively solve these equations in order to obtain an abstract storage graph that describes the shape of data structures at every point of the program for all possible thread interleavings. We bring experimental evidence that this approach is tractable and precise for real-size embedded applications.

Venet, Arnaud↗
NASA NTRS2014

Distributed Prognostics based on Structural Model Decomposition

Within systems health management, prognostics focuses on predicting the remaining useful life of a system. In the model-based prognostics paradigm, physics-based models are constructed that describe the operation of a system and how it fails. Such approaches consist of an estimation phase, in which the health state of the system is first identified, and a prediction phase, in which the health state is projected forward in time to determine the end of life. Centralized solutions to these problems are often computationally expensive, do not scale well as the size of the system grows, and introduce a single point of failure. In this paper, we propose a novel distributed model-based prognostics scheme that formally describes how to decompose both the estimation and prediction problems into independent local subproblems whose solutions may be easily composed into a global solution. The decomposition of the prognostics problem is achieved through structural decomposition of the underlying models. The decomposition algorithm creates from the global system model a set of local submodels suitable for prognostics. Independent local estimation and prediction problems are formed based on these local submodels, resulting in a scalable distributed prognostics approach that allows the local subproblems to be solved in parallel, thus offering increases in computational efficiency. Using a centrifugal pump as a case study, we perform a number of simulation-based experiments to demonstrate the distributed approach, compare the performance with a centralized approach, and establish its scalability. Index Terms-model-based prognostics, distributed prognostics, structural model decomposition ABBREVIATIONS

centrifugal pump↗
NASA NTRS2022

Towards the Development of a Multi-Agent Cognitive Networking System for the Lunar Environment

This paper details the development of a multi-agent cognitive system intended to optimize networking performance in the lunar environment. One concept of the future of lunar communication, LunaNet, outlines a complex network of networks. Challenges such as scalability, interoperability, and reliability must first be addressed to successfully fulfill this vision. Machine intelligence can greatly reduce the reliance on human operators and enable efficient operations for tasks such as scheduling and network management. Machine learning, artificial intelligence, and other automated decision-making techniques can be used to allow network nodes to intelligently sense and adapt to changes in the environment such as link disruptions, new nodes joining the network, and support for a diverse range of protocols. Cognitive networking seeks to evolve these technologies into an autonomous system with improved science data return, reliability, and scalability. In this paper, we study four main areas as a means to further develop cognitive networking capabilities: networking protocol development, analysis of wireless data for modeling and simulation, development of algorithms for a multi-agent system, and spectrum sensing technology.

cognitive networking↗
DOE OSTI2023

"Enabling Mixed Autonomy Traffic Control"

We demonstrate a new capability of automated vehicles: mixed autonomy traffic control. With this new capability, automated vehicles can shape the traffic flows composed of other non-automated vehicles, which has the promise to improve safety, efficiency, and energy outcomes in transportation systems at a societal scale. Investigating mixed autonomy mobile traffic control must be done in situ given that the complex dynamics of other drivers and their response to a team of automated vehicles cannot be effectively modeled. This capability has been blocked because there is no existing scalable and affordable platform for experimental control. This paper introduces an extensible open-source hardware and software platform, enabling a team of 100 vehicles to execute several different vehicular control algorithms as a collaborative fleet, composed of three different makes and models, which drove 22752 miles in a combined 1022 hours, over 5 days in Nashville, TN in November 2022.

Nice, Matthew↗
DOE OSTI2024

Pan-tropical daily L-band microwave land surface emissivity retrieval from GNSS-R observations

The uncertainties in microwave land surface emissivity (MLSE) measurements have long limited the use of spaceborne microwave radiometer data. As an emerging observation method, Global Navigation Satellite System Reflectometry (GNSS-R) has demonstrated great potential in several land and ocean applications. In this study, a method for obtaining daily MLSE dataset in the pan-tropical region from Cyclone GNSS (CYGNSS) observations is presented and evaluated. The CYGNSS observations are first aggregated into the Equal-Area-Scalable-Earth (EASE) 2.0 36 km grid by a combined weight function of distance, time, and signal-to-noise ratio variance. Then, the method employs a pixel-by-pixel regression algorithm to conduct the daily MLSE retrieval using reference emissivity derived from the Soil Moisture Active Passive (SMAP) brightness temperature. The CYGNSS MLSE shows good agreement with SMAP MLSE, delivering an overall root-mean-square error (RMSE) of 0.022 and 0.017 for horizontal and vertical polarization, respectively, during the training set spanning the whole year of 2018. Furthermore, on the test set from January 2019 to May 2019, the RMSE values amounted to 0.030 and 0.023 for horizontal and vertical polarization, respectively. Temperature records from the International Soil Moisture Network are employed to calculate the emissivity and for in-situ validation, which yield an RMSE of 0.034 and 0.026 for the two polarizations, respectively. The proposed algorithm provides an encouraging approach to obtain accurate daily MLSE dataset for microwave remote sensing. Compared to the SMAP MLSE, the CYGNSS MLSE has a remarkable improvement of 86% in temporal resolution, greatly complementing the existing microwave emissivity datasets.

54 ENVIRONMENTAL SCIENCES↗