Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “algorithms scalability”

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 73 records · Page 4

A Scalable Space-Time Domain Decomposition Approach for Solving Large Scale Nonlinear Regularized Inverse Ill Posed Problems in 4D Variational Data Assimilation

We address the development of innovative algorithms designed to solve the strong-constraint Four Dimensional Variational Data Assimilation (4DVar DA) problems in large scale applications. We present a space-time decomposition approach which employs the whole domain decomposition, i.e. both along the spacial and temporal direction in the overlapping case, and the partitioning of both the solution and the operator. Starting from the global functional defined on the entire domain, we get to a sort of regularized local functionals on the set of sub domains providing the order reduction of both the predictive and the Data Assimilation models. The algorithm convergence is developed. Performance in terms of reduction of time complexity and algorithmic scalability is discussed on the Shallow Water Equations on the sphere. The number of state variables in the model, the number of observations in an assimilation cycle, as well as numerical parameters as the discretization step in time and in space domain are defined on the basis of discretization grid used by data available at repository Ocean Synthesis/Reanalysis Directory of Hamburg University.

97 MATHEMATICS AND COMPUTING↗

Hard scaling challenges for ab initio molecular dynamics capabilities in NWChem: Using 100,000 CPUs per second

An overview of the parallel algorithms for ab initio molecular dynamics (AIMD) used in the NWChem program package is presented, including recent developments for computing exact exchange. These algorithms make use of a two-dimensional processor geometry proposed by Gygi et al for use in AIMD algorithms. Using this strategy, a highly scalable algorithm for exact exchange has been developed and incorporated it into AIMD. This new algorithm for exact exchange employs an incomplete butterfly to overcome the bottleneck associated with exact exchange term, and it makes judicious use of data replication. Initial testing has shown that this algorithm can scale to over 20,000 CPUs even for modest size simulation.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Particle Communication and Domain Neighbor Coupling: Scalable Domain Decomposed Algorithms for Monte Carlo Particle Transport

In order to run Monte Carlo particle transport calculations on new supercomputers with hundreds of thousands or millions of processors, care must be taken to implement scalable algorithms. This means that the algorithms must continue to perform well as the processor count increases. In this paper, we examine the scalability of:(1) globally resolving the particle locations on the correct processor, (2) deciding that particle streaming communication has finished, and (3) efficiently coupling neighbor domains together with different replication levels. We have run domain decomposed Monte Carlo particle transport on up to 2 21 = 2,097,152 MPI processes on the IBM BG/Q Sequoia supercomputer and observed scalable results that agree with our theoretical predictions. These calculations were carefully constructed to have the same amount of work on every processor, i.e. the calculation is already load balanced. We also examine load imbalanced calculations where each domain’s replication level is proportional to its particle workload. In this case we show how to efficiently couple together adjacent domains to maintain within workgroup load balance and minimize memory usage.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

Multi-jagged: A scalable parallel spatial partitioning algorithm

Geometric partitioning is fast and effective for load-balancing dynamic applications, particularly those requiring geometric locality of data (particle methods, crash simulations). We present, to our knowledge, the first parallel implementation of a multidimensional-jagged geometric partitioner. In contrast to the traditional recursive coordinate bisection algorithm (RCB), which recursively bisects subdomains perpendicular to their longest dimension until the desired number of parts is obtained, our algorithm does recursive multi-section with a given number of parts in each dimension. By computing multiple cut lines concurrently and intelligently deciding when to migrate data while computing the partition, we minimize data movement compared to efficient implementations of recursive bisection. We demonstrate the algorithm's scalability and quality relative to the RCB implementation in Zoltan on both real and synthetic datasets. Our experiments show that the proposed algorithm performs and scales better than RCB in terms of run-time without degrading the load balance. Lastly, our implementation partitions 24 billion points into 65,536 parts within a few seconds and exhibits near perfect weak scaling up to 6K cores.

97 MATHEMATICS AND COMPUTING↗

Parallel Climate Data Assimilation PSAS Package

We have designed and implemented a set of highly efficient and highly scalable algorithms for an unstructured computational package, the PSAS data assimilation package, as demonstrated by detailed performance analysis of systematic runs on up to 512node Intel Paragon. The equation solver achieves a sustained 18 Gflops performance. As the results, we achieved an unprecedented 100-fold solution time reduction on the Intel Paragon parallel platform over the Cray C90. This not only meets and exceeds the DAO time requirements, but also significantly enlarges the window of exploration in climate data assimilations.

PSAS data scalable algorithms Intel Paragon 512nod↗

Early Career Award: An Enabling Computational Framework for Uncertainty Assimilation and Propagation in Complex PDE Systems: Sparse and Low-rank Techniques (Final Report)

This project aims to develop a set of new theories, algorithms, and computational tools that enable ultra-scalable representation and propagation of high-dimensional uncertainties to circumvent the issue of curse-of-dimensionality. The research components are motivated by the fact that highly scalable algorithms are needed to achieve exascale performance for uncertainty quantification and predictive simulation at extreme scales. Although these developments are generic and applicable to a wide range of high-dimensional, complex, stochastic, partial-differential-equation (PDE) systems, this research effort will focus on predictive simulation of high-energy-density lithium batteries. To create knowledge about the precise failure mechanisms of these batteries and ultimately predict their performance and reliability, a truly data-driven, multi-scale, multi-physics framework is needed that allows studying (i) dominant sources of uncertainty in the governing physical models at all scales of relevance and (ii) the interface between the interchanging physics and scales. The impact of the planned mathematical and numerical advancements in prediction of high-dimensional uncertain systems will be broad across areas of engineering and science such as climate modeling, fusion energy, combustion, and nanoscience, among others.

97 MATHEMATICS AND COMPUTING↗

Low-Cost Parallel Algorithms for 2:1 Octree Balance

The logical structure of a forest of octrees can be used to create scalable algorithms for parallel adaptive mesh refinement (AMR), which has recently been demonstrated for several petascale applications. Among various frequently used octree-based mesh operations, including refinement, coarsening, partitioning, and enumerating nodes, ensuring a 2:1 size balance between neighboring elements has historically been the most expensive in terms of CPU time and communication volume. The 2:1 balance operation is thus a primary target to optimize. One important component of a parallel balance algorithm is the ability to determine whether any two given octants have a consistent distance/size relation. Based on new logical concepts we propose fast algorithms for making this decision for all types of 2:1 balance conditions in 2D and 3D. Since we are able to achieve this without constructing any parent nodes in the tree that would otherwise need to be sorted and communicated, we can significantly reduce the required memory and communication volume. In addition, we propose a lightweight collective algorithm for reversing the asymmetric communication pattern induced by non-local octant interactions. We have implemented our improvements as part of the opensource “p4est” software. Benchmarking this code with both synthetic and simulation-driven adapted meshes we are able to demonstrate much reduced runtime and excellent weak and strong scalability. On our largest benchmark problem with 5.13 × 10 11 octants the new 2:1 balance algorithm executes in less than 8 seconds on 112,128 CPU cores of the Jaguar Cray XT5 supercomputer.

Computer Science↗

Assessing the Performance and Scalability of a Novel Multilevel K-Nomial Allgather on CORE-Direct Systems

In this paper, we propose a novel allgather algorithm, Reindexed Recursive K-ing (RRK), which leverages flexibility in the algorithm’s tree topology and ability to make asynchronous progress coupled with Core-Direct communication offload capability to optimize the MPI_Allgather for Core-Direct enabled systems. In particular, the RRK introduces a reindexing scheme which ensures contiguous data transfers while adding only a single additional send and receive operation for any radix, k, or communicator size, N. This allows us to improve algorithm scalability by avoiding the use of a scatter/gather elements (SGE) list on InfiniBand networks. The implementations of the RRK algorithm and its evaluation shows that it performs and scales well on Core-Direct systems for a wide range of message sizes and various communicator configurations.

Allgather↗

Assessing the Performance and Scalability of a Novel Multilevel K-Nomial Allgather on CORE-Direct Systems

In this paper, we propose a novel allgather algorithm, Reindexed Recursive K-ing (RRK), which leverages flexibility in the algorithm's tree topology and ability to make asynchronous progress coupled with Core-Direct communication offload capability to optimize the MPI-Allgather for Core-Direct enabled systems. In particular, the RRK introduces a reindexing scheme which ensures contiguous data transfers while adding only a single additional send and receive operation for any radix, k, or communicator size, N. This allows us to improve algorithm scalability by avoiding the use of a scatter/gather elements (SGE) list on InfiniBand networks. The implementations of the RRK algorithm and its evaluation shows that it performs and scales well on Core-Direct systems for a wide range of message sizes and various communicator configurations.

99 GENERAL AND MISCELLANEOUS↗

PMU Placement for Dynamic State Tracking of Power Systems

Accurately tracking the state variables (rotor angle and speed) is a necessity for monitoring system stability conditions and assessing the risks of large-scale system collapse. This paper explores how the number and locations of PMUs installed in the system are determined to ensure satisfactory state tracking performance. A search algorithm is presented for determining PMU placement (location and quantity). The algorithm determines a placement that gives small tracking error in polynomial time. A modified, scalable algorithm is also presented. Observability in the presence of faults is considered. Simulation results for a 16-machine and a 50-machine system are provided.

24 POWER TRANSMISSION AND DISTRIBUTION↗

A Scalable Interior‐Point Gauss–Newton Method for PDE‐Constrained Optimization With Bound Constraints

Here, we present a scalable approach to solve a class of partial differential equation (PDE)‐constrained optimization problems with bound constraints. This approach utilizes a robust full‐space interior‐point (IP)‐Gauss–Newton optimization method. To cope with the poorly‐conditioned IP‐Gauss–Newton saddle‐point linear systems that need to be solved approximately, once per optimization step, we propose two spectrally related preconditioners. These preconditioners leverage the limited informativeness of data in regularized PDE‐constrained optimization problems. A block Gauss–Seidel preconditioner is proposed for the GMRES‐based solution of the IP‐Gauss–Newton linear systems. It is shown, for a large‐class of PDE‐ and bound‐constrained optimization problems, that the spectrum of the block Gauss–Seidel preconditioned IP‐Gauss–Newton matrix is asymptotically independent of discretization and is not impacted by the ill‐conditioning that notoriously plagues interior‐point methods. We exploit symmetry of the IP‐Gauss–Newton linear systems and propose a regularization and log‐barrier Hessian preconditioner for the preconditioned conjugate gradient (PCG)‐based solution of the equivalent IP‐Gauss–Newton–Schur complement linear systems. The eigenvalues of the block Gauss–Seidel preconditioned IP‐Gauss–Newton matrix, that are not equal to one, are identical to the eigenvalues of the regularization and log‐barrier Hessian preconditioned Schur complement matrix. The scalability of the approach is demonstrated on two example problems. The numerical solution of these optimization problems is shown to require a discretization independent number of IP‐Gauss–Newton linear solves. Furthermore, the linear systems are solved in a discretization and IP ill‐conditioning independent number of preconditioned Krylov subspace iterations. The parallel scalability of the preconditioner, achieved via algebraic multigrid component solvers when applicable, and the aforementioned algorithmic scalability permits a parallel scalable means to compute solutions of a large class of PDE‐ and bound‐constrained problems.

PDE-constrained optimization↗

Multilevel Hierarchical Decomposition of Finite Element White Noise with Application to Multilevel Markov Chain Monte Carlo

In this work we develop a new hierarchical multilevel approach to generate Gaussian random field realizations in an algorithmically scalable manner that is well suited to incorporating into multilevel Markov chain Monte Carlo (MCMC) algorithms. This approach builds off of other partial differential equation (PDE) approaches for generating Gaussian random field realizations; in particular, a single field realization may be formed by solving a reaction-diffusion PDE with a spatial white noise source function as the right-hand side. While these approaches have been explored to accelerate forward uncertainty quantification tasks, e.g., multilevel Monte Carlo, the previous constructions are not directly applicable to multilevel MCMC frameworks which build fine-scale random fields in a hierarchical fashion from coarse-scale random fields. Our new hierarchical multilevel method relies on a hierarchical decomposition of the white noise source function in $L^2$ which allows us to form Gaussian random field realizations across multiple levels of discretization in a way that fits into multilevel MCMC algorithmic frameworks. After presenting our main theoretical results and numerical scaling results to showcase the utility of this new hierarchical PDE method for generating Gaussian random field realizations, this method is tested on a four-level MCMC algorithm to explore its feasibility.

algebraic multigrid↗

Integral Kernel Methods for Nonlinear Parabolic-Elliptic Systems

Nonlinear parabolic-elliptic systems arise in many physical, biological, and chemical phenomena such as chemotaxis, ion transport, self-gravitating particles, and Brownian vortices. Existing methods struggle with the strong coupling and high nonlinearity and nonlocality of some of these systems, especially the ill-conditioned, convection-dominated problems. To overcome numerical difficulties, current approaches rely on initial guesses, preconditioning, or iterative techniques with no convergence guarantees. They might suffer from poor scalability, large memory usage, and difficulty to parallelize. Inspired by the connection of parabolic-elliptic systems to stochastic processes, we introduce a novel meshless, monolithic, and fully explicit method that naturally encapsulates the elliptic and parabolic operators into a single step which updates each node deterministically with global information. By being fully quadrature-based, it avoids solving systems of discretized equations and does not utilize initial guesses or preconditioning, while requiring little memory and being easy to parallelize. We first derive the method in an integral kernel formulation with quadratic complexity in the number of integration nodes and then leverage kernel-independent fast multipole methods (FMM) to present a scalable algorithm with linear complexity. We provide numerical examples for the Poisson-Nernst-Planck equations in one, two, and three dimensions, together with the derivation of the integral kernel for each case. Furthermore, the examples demonstrate the fast convergence and scalability of the FMM-accelerated algorithm, as well as its suitability for convection-dominated problems, making it competitive against traditional PDE solvers.

PDE systems↗

Massively parallel solvers for elliptic partial differential equations in numerical weather and climate prediction

The demand for substantial increases in the spatial resolution of global weather and climate prediction models makes it essential to use numerically efficient and highly scalable algorithms to solve the equations of large-scale atmospheric fluid dynamics. For stability and efficiency reasons, several of the operational forecasting centres, in particular the Met Office and the European Centre for Medium-Range Weather Forecasts (ECMWF) in the UK, use semi-implicit semi-Lagrangian time-stepping in the dynamical core of the model. The additional burden with this method is that a three-dimensional elliptic partial differential equation (PDE) for the pressure correction has to be solved at every model time step and this often constitutes a significant proportion of the time spent in the dynamical core. In global models, this PDE must be solved in a thin spherical shell. To run within tight operational time-scales, the solver has to be parallelized and there seems to be a (perceived) misconception that elliptic solvers do not scale to large processor counts and hence implicit time-stepping cannot be used in very high-resolution global models. After reviewing several methods for solving the elliptic PDE for the pressure correction and their application in atmospheric models, we demonstrate the performance and very good scalability of Krylov subspace solvers and multigrid algorithms for a representative model equation with more than 1010 unknowns on 65 536 cores on the High-End Computing Terascale Resource (HECToR), the UK's national supercomputer. Here, we tested and optimized solvers from two existing numerical libraries (the Distributed and Unified Numerics Environment (DUNE) and Parallel High Performance Preconditioners (hypre)) and implemented both a conjugate gradient solver and a geometric multigrid algorithm based on a tensor-product approach, which exploits the strong vertical anisotropy of the discretized equation. We study both weak and strong scalability and compare the absolute solution times for all methods; in contrast to one-level methods, the multigrid solver is robust with respect to parameter variations.

58 GEOSCIENCES↗

SORA: Scalable Overlap-graph Reduction Algorithms for Genome Assembly using Apache Spark in the Cloud

The advent of high-throughput DNA sequencing techniques has permitted very high quality de novo assemblies of genomes, but raise an issue of requiring large amounts of computer memory to resolve the large genome graphs generated by most overlap graph de novo assemblers. To address these limitations, we present a novel algorithmic approach; Scalable Overlap-graph Reduction Algorithms (SORA). SORA adapts string graph reduction algorithms for the genome assembly using a distributed computing platform. To efficiently compute coverage for enormous paths in the graphs, SORA uses Apache Spark which is a cluster-based engine designed on top of Hadoop to handle very large datasets in the cloud. The experimental results show that SORA can process a nearly one billion edge graph in a distributed cloud cluster as well as smaller graphs on a local cluster with a short turnaround time. Moreover, our algorithms scale almost linearly with increasing numbers of virtual instances in the cloud. SORA is freely available for download at https://github.com/BioHPC/SORA/.

Paul, Alexander↗

Potential Demand Reduction from Buildings in a Simulated Utility

The availability of large-area sensing, scalable algorithms, and high-performance computing has enabled the possibility of urban-scale building energy modeling using new methods not limited to the scalability of manual building energy model creation or retrieval of county-by-county tax assessor’s data. Automatic Building detection and Energy Model creation (AutoBEM) has created 178,368 building energy models for the Electric Power Board (EPB) of Chattanooga, TN, and compared simulation performance to 15-minute data from each building. These models leverage several data sources (e.g. imagery, GIS, utility), software tools to extract building properties (e.g. footprint, height, façade type, window-to-wall ratio, occupancy, building type), simulate at scale on two of the world’s #1 fastest supercomputers, and provide web-based visual analytics.Grid-interactive efficient buildings offer the potential to reduce utility and rate-payer energy costs during each calendar month’s hour of critical generation – when the least efficient, most costly, and often dirtiest generation assets must be brought online. In this paper, EnergyPlus is used to simulate over 150,000 buildings to assess the technical potential of utility-controlled smart thermostats. This is analyzed under a couple scenarios leveraging buildings as thermal batteries via pre-conditioning to coast through peak hours. Results are provided in box and whisker plots assessing the distribution of peak demand reduction at the utility-scale along with breakouts of energy and demand savings by building type and vintage.

Bass, Brett↗

Final report for “Extreme-scale Algorithms and Solver Resilience”

This is a joint project with principal investigators at Oak Ridge National Laboratory, Sandia National Laboratories, the University of California at Berkeley, and the University of Tennessee. Our part of the project involves developing performance models for highly scalable algorithms and the development of latency tolerant iterative methods. During this project, we extended our performance models for the Multigrid method for solving large systems of linear equations and conducted experiments with highly scalable variants of conjugate gradient methods that avoid blocking synchronization. In addition, we worked with the other members of the project on alternative techniques for resilience and reproducibility. We also presented an alternative approach for reproducible dot-products in parallel computations that performs almost as well as the conventional approach by separating the order of computation from the details of the decomposition of vectors across the processes.

97 MATHEMATICS AND COMPUTING↗

A scalable variational inequality approach for flow through porous media models with pressure-dependent viscosity

Mathematical models for flow through porous media typically enjoy the so-called maximum principles, which place bounds on the pressure field. It is highly desirable to preserve these bounds on the pressure field in predictive numerical simulations, that is, one needs to satisfy discrete maximum principles (DMP). Unfortunately, many of the existing formulations for flow through porous media models do not satisfy DMP. This paper presents a robust, scalable numerical formulation based on variational inequalities (VI), to model non-linear flows through heterogeneous, anisotropic porous media without violating DMP. VI is an optimization technique that places bounds on the numerical solutions of partial differential equations. To crystallize the ideas, a modification to Darcy equations by taking into account pressure-dependent viscosity will be discretized using the lowest-order Raviart–Thomas (RT0) and Variational Multi-scale (VMS) finite element formulations. It will be shown that these formulations violate DMP, and, in fact, these violations increase with an increase in anisotropy. It will be shown that the proposed VI-based formulation provides a viable route to enforce DMP. Moreover, it will be shown that the proposed formulation is scalable, and can work with any numerical discretization and weak form. Aseriesof numerical benchmark problems are solved to demonstrate the effects of heterogeneity, anisotropy and non-linearity on DMP violations under the two chosen formulations (RT0 and VMS), and that of non-linearity on solver convergence for the proposed VI-based formulation. Parallel scalability on modern computational platforms will be illustrated through strong-scaling studies, which will prove the efficiency of the proposed formulation in a parallel setting. Algorithmic scalability as the problem size is scaled up will be demonstrated through novel static-scaling studies. The performed static-scaling studies can serve as a guide for users to be able to select an appropriate discretization for a given problem size.

42 ENGINEERING↗