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 361 records · Page 20

Towards Superior Software Portability with SHAD and HPX C++ Libraries

As hardware architectures and software stacks complexity grows, development productivity, performance and software portability, quickly evolve from desirable features to actual needs. SHAD, the Scalable High-performance Algorithms and Data-structures C++ library is designed to mitigate these issues: it provides general purpose building blocks as well as high-level custom utilities, and offers a shared-memory programming abstraction which facilitates the programming of complex systems, scaling up to High Performance Computing clusters. SHAD’s portability is achieved through an abstract runtime interface, which decouples the upper layers of the library and hides the low level details of the underlying architecture. This layer enables SHAD to interface with different runtime/threading systems, e.g. Intel TBB and Global Memory and Threading (GMT). However, current backends targeting distributed systems, rely on a centralized controller which may possibly limit scalability up to hundreds of nodes and creates a network hot spot due to all to one communication for synchronization, and possibly resulting in degraded performance at high process counts. In this research, we explore HPX, the C++ standard library for parallelism and concurrency, as an additional backend in support of the SHAD library, and present the methodologies in support of local and remote task executions in SHAD with respect to HPX. Finally, we evaluate the proposed system by comparing against existing backends of SHAD and analyzing their performance on C++ Standard Template Library algorithms.

Wu, Nanmiao↗

Predicting and Detecting Emerging Cyberattack Patterns Using StreamWorks

The number and sophistication of cyberattacks on industries and governments have dramatically grown in recent years. To counter this movement, new advanced tools and techniques are needed to detect cyberattacks in their early stages such that defensive actions may be taken to avert or mitigate potential damage. From a cybersecurity analysis perspective, detecting cyberattacks may be cast as a problem of identifying patterns in computer network traffic. Logically and intuitively, these patterns may take on the form of a directed graph that conveys how an attack or intrusion propagates through the computers of a network. Such cyberattack graphs could provide cybersecurity analysts with powerful conceptual representations that are natural to express and analyze. We have been researching and developing graph-centric approaches and algorithms for dynamic cyberattack detection. The advanced dynamic graph algorithms we are developing will be packaged into a streaming network analysis framework known as StreamWorks. With StreamWorks, a scientist or analyst may detect and identify precursor events and patterns as they emerge in complex networks. This analysis framework is intended to be used in a dynamic environment where network data is streamed in and is appended to a large-scale dynamic graph. Specific graphical query patterns are decomposed and collected into a graph query library. The individual decomposed subpatterns in the library are continuously and efficiently matched against the dynamic graph as it evolves to identify and detect early, partial subgraph patterns. The scalable emerging subgraph pattern algorithms will match on both structural and semantic network properties.

Chin, George↗

Marker ReDistancing/Level Set Method for High-Fidelity Implicit Interface Tracking

A hybrid of the Front-Tracking (FT) and the Level-Set (LS) methods is introduced, combining advantages and removing drawbacks of both methods. The kinematics of the interface is treated in a Lagrangian (FT) manner, by tracking markers placed at the interface. The markers are not connected – instead, the interface topology is resolved in an Eulerian (LS) framework, by wrapping a signed distance function around Lagrangian markers each time the markers move. For accuracy and efficiency, we have developed a high-order “anchoring” algorithm and an implicit PDE-based re-distancing. We have demonstrated that the method is 3rd-order accurate in space, near the markers, and therefore 1st-order convergent in curvature; in contrast to traditional PDE-based re-initialization algorithms, which tend to slightly relocate the zero Level Set and can be shown to be non-convergent in curvature. The implicit pseudo-time discretization of the re-distancing equation is implemented within the Jacobian-Free Newton Krylov (JFNK) framework combined with ILU(k) preconditioning. We have demonstrated that the steady-state solutions in pseudo-time can be achieved very efficiently, with iterations (CFL ), in contrast to the explicit re-distancing which requires 100s of iterations with CFL . The most cost-effective algorithm is found to be a hybrid of explicit and implicit discretizations, in which we apply first 10-15 iterations with explicit discretization (to bring the initial guess to the ball of convergence for the Newton’s method) and then finishing with 2-3 implicit steps, bringing the re-distancing equation to a complete steady-state. The eigenscopy of the JFNK-ILU(k) demonstrates the efficiency of the ILU(k) preconditioner, which effectively cluster eigenvalues of the otherwise extremely ill-conditioned Jacobian matrices, thereby enabling the Krylov (GMRES) method to converge with iterations, with only a few levels of ILU fill-ins. Importantly, due to the Level Set localization, the bandwidth of the Jacobian matrix is nearly constant, and the ILU preconditioning scales as , which implies efficiency and good scalability of the overall algorithm. The numerical examples include the well-established tests for interface kinematics under translational, rotational and tearing/stretching motion. We have shown that the mass conservation is not an issue anymore, as demonstrated using the Rider&Kothe’s time-reversed tests with extreme deformation. We are able to stretch interface structures to the under-resolved/subgrid (on the chosen Eulerian mesh) scales, and recover them back without any change in shape/loss of mass.

99 GENERAL AND MISCELLANEOUS↗

Services + Components = Data Intensive Scientific Workflow Applications with MeDICi

Scientific applications are often structured as workflows that execute a series of distributed software modules to analyze large data sets. Such workflows are typically constructed using general-purpose scripting languages to coordinate the execution of the various modules and to exchange data sets between them. While such scripts provide a cost-effective approach for simple workflows, as the workflow structure becomes complex and evolves, the scripts quickly become complex and difficult to modify. This makes them a major barrier to easily and quickly deploying new algorithms and exploiting new, scalable hardware platforms. In this paper, we describe the MeDICi Workflow technology that is specifically designed to reduce the complexity of workflow application development, and to efficiently handle data intensive workflow applications. MeDICi integrates standard component-based and service-based technologies, and employs an efficient integration mechanism to ensure large data sets can be efficiently processed. We illustrate the use of MeDICi with a climate data processing example that we have built, and describe some of the new features

99 GENERAL AND MISCELLANEOUS↗

Optimizing High Performance Markov Clustering for Pre-Exascale Architectures

HipMCL is a high-performance distributed memory implementation of the popular Markov Cluster Algorithm (MCL) and can cluster large-scale networks within hours using a few thousand CPU-equipped nodes. It relies on sparse matrix computations and heavily makes use of the sparse matrix-sparse matrix multiplication kernel (SpGEMM). The existing parallel algorithms in HipMCL are not scalable to Exascale architectures, both due to their communication costs dominating the runtime at large concurrencies and also due to their inability to take advantage of accelerators that are increasingly popular. In this work, we systematically remove scalability and performance bottlenecks of HipMCL. We enable GPUs by performing the expensive expansion phase of the MCL algorithm on GPU. Additionally, we propose a CPU-GPU joint distributed SpGEMM algorithm called pipelined Sparse SUMMA and integrate a probabilistic memory requirement estimator that is fast and accurate. Furthermore, we develop a new merging algorithm for the incremental processing of partial results produced by the GPUs, which improves the overlap efficiency and the peak memory usage. We also integrate a recent and faster algorithm for performing SpGEMM on CPUs. We validate our new algorithms and optimizations with extensive evaluations. With the enabling of the GPUs and integration of new algorithms, HipMCL is up to 12.4x faster, being able to cluster a network with 70 million proteins and 68 billion connections just under 15 minutes using 1024 nodes of ORNL's Summit supercomputer.

97 MATHEMATICS AND COMPUTING↗

Distributed Sensor Coordination for Advanced Energy Systems

The ability to collect key system level information is critical to the safe, efficient and reliable operation of advanced energy systems. With recent advances in sensor development, it is now possible to push some level of decision making directly to computationally sophisticated sensors, rather than wait for data to arrive to a massive centralized location before a decision is made. This type of approach relies on networked sensors (called “agents” from here on) to actively collect and process data, and provide key control decisions to significantly improve both the quality/relevance of the collected data and the associating decision making. The technological bottlenecks for such sensor networks stem from a lack of mathematics and algorithms to manage the systems, rather than difficulties associated with building and deploying them. Indeed, traditional sensor coordination strategies do not provide adequate solutions for this problem. Passive data collection methods (e.g., large sensor webs) can scale to large systems, but are generally not suited to highly dynamic environments, such as advanced energy systems, where crucial decisions may need to be reached quickly and locally. Approaches based on local decisions on the other hand cannot guarantee that each agent performing its task (maximize an agent objective) will lead to good network wide solution (maximize a network objective) without invoking cumbersome coordination routines. There is currently a lack of algorithms that will enable self-organization and blend the efficiency of local decision making with the system level guarantees of global decision making, particularly when the systems operate in dynamic and stochastic environments. In this work we addressed this critical gap and provided a comprehensive solution to the problem of sensor coordination to ensure the safe, reliable, and robust operation of advanced energy systems. The differentiating aspect of the proposed work is in shifting the focus towards “what to observe” rather than “how to observe” in large sensor networks, allowing the agents to actively determine both the structure of the network and the relevance of the information they are seeking to collect. In addition to providing an implicit coordination mechanism, this approach allows the system to be reconfigured in response to changing needs (e.g., sudden external events requiring new responses) or changing sensor network characteristics (e.g., sudden changes to plant condition). Outcome Summary: All milestones associated with this project have been completed. In particular, private sensor objective functions were developed which are aligned with the global objective function, sensor effectiveness has been improved by using “sensor teams,” system efficiency has been improved by 30% using difference evaluation functions, we have demonstrated system reconfigurability for 20% changes in system conditions, we have demonstrated extreme scalability of our proposed algorithm, we have demonstrated that sensor networks can overcome disruptions of up to 20% in network conditions, and have demonstrated system reconfigurability to 20% changes in system conditions in hardware-based simulations. This final report summarizes how each of these milestones was achieved, and gives insight into future research possibilities past the work which has been completed. The following publications support these milestones [6, 8, 9, 10, 16, 18, 19].

97 MATHEMATICS AND COMPUTING↗

Distributed-memory Parallel Algorithms for Matching and Coloring

Graph matching and coloring constitute two fundamental classes of combinatorial problems having numerous established as well as emerging applications in computational science and engineering, high-performance computing, and informatics. We provide a snapshot of an on-going work on the design and implementation of new highly-scalable distributed-memory parallel algorithms for two prototypical problems from these classes, edge-weighted matching and distance-1 vertex coloring. Graph algorithms in general have low concurrency and poor data locality, making it challenging to achieve scalability on massively parallel machines. We overcome this challenge by employing a variety of techniques, including approximation, speculation and iteration, optimized communication, and randomization, in concert. We present preliminary results on weak and strong scalability studies conducted on an IBM Blue Gene/P machine employing up to tens of thousands of processors. The results show that the algorithms hold strong potential for computing at petascale.

Combinatorial scientific computing↗

A Scalable PDC Placement Technique for Fast and Resilient Monitoring of Large Power Grids

The wide-area measurement system (WAMS) is a key enabler of real-time monitoring of power grids. The essential goals of WAMS design are fast and resilient data transfer from phasor measurement units (PMU) to phasor data concentrators (PDC). We propose a scalable two-stage PDC placement technique for minimizing the end-to-end delay while maintaining resiliency. In the prescreening stage, the plausible candidates of PDC configurations are identified based on a graph theory-based multi-median function (MMF). Here, in this article, a computationally efficient meta-heuristic algorithm is used to address scalability. In the candidate selection stage, two different algorithms, namely, Suurballe's and Dijkstra's, are employed to identify the best of those plausible PDC configurations as the final design. This technique not only minimizes the hop paths between PMUs and PDCs, but also ensures network resiliency against single PMU, PDC, or communication link failure by incorporating the roles of PMUs in power grid observability into routing policy. Simulation results on the IEEE 57-bus test power system and the 2000-bus test power system demonstrate the effectiveness and scalability of the proposed technique.

24 POWER TRANSMISSION AND DISTRIBUTION↗

GVT Algorithms and Discrete Event Dynamics on 128K+ Processor Cores

Parallel discrete event simulation (PDES) represents a class of codes that are challenging to scale to large number of processors due to tight global timestamp-ordering and fine-grained event execution. One of the critical factors in scaling PDES is the efficiency of the underlying global virtual time (GVT) algorithm needed for correctness of parallel execution and speed of progress. Although many GVT algorithms have been proposed previously, few have been proposed for scalable asynchronous execution and none customized to exploit one-sided communication. Moreover, the detailed performance effects of actual GVT algorithm implementations on large platforms are unknown. Here, three major GVT algorithms intended for scalable execution on high-performance systems are studied: (1) a synchronous GVT algorithm that affords ease of implementation, (2) an asynchronous GVT algorithm that is more complex to implement but can relieve blocking latencies, and (3) a variant of the asynchronous GVT algorithm, proposed and studied for the first time here, to exploit one-sided communication in extant supercomputing platforms. Performance results are presented of implementations of these algorithms on over 64,000 cores of a Cray XT5 system, exercised on a range of parameters: optimistic and conservative synchronization, fine- to medium-grained event computation, synthetic and non-synthetic applications, and different lookahead values. Performance of tens of billions of events executed per second are registered, exceeding the speeds of any known PDES engine, and showing asynchronous GVT algorithms to outperform state-of-the-art synchronous GVT algorithms. Detailed PDES-specific runtime metrics are presented to further the understanding of tightly-coupled discrete event execution dynamics on massively parallel platforms.

99 GENERAL AND MISCELLANEOUS↗

Proximal Galerkin: A Structure-Preserving Finite Element Method for Pointwise Bound Constraints

The proximal Galerkin finite element method is a high-order, low iteration complexity, nonlinear numerical method that preserves the geometric and algebraic structure of pointwise bound constraints in infinite-dimensional function spaces. This paper introduces the proximal Galerkin method and applies it to solve free boundary problems, enforce discrete maximum principles, and develop a scalable, mesh-independent algorithm for optimal design with pointwise bound constraints. This paper also introduces the latent variable proximal point (LVPP) algorithm, from which the proximal Galerkin method derives. When analyzing the classical obstacle problem, we discover that the underlying variational inequality can be replaced by a sequence of second-order partial differential equations (PDEs) that are readily discretized and solved with, e.g., the proximal Galerkin method. Throughout this work, we arrive at several contributions that may be of independent interest. These include (1) a semilinear PDE we refer to as the entropic Poisson equation; (2) an algebraic/geometric connection between high-order positivity-preserving discretizations and certain infinite-dimensional Lie groups; and (3) a gradient-based, bound-preserving algorithm for two-field, density-based topology optimization. The complete proximal Galerkin methodology combines ideas from nonlinear programming, functional analysis, tropical algebra, and differential geometry and can potentially lead to new synergies among these areas as well as within variational and numerical analysis. Open-source implementations of our methods accompany this work to facilitate reproduction and broader adoption.

97 MATHEMATICS AND COMPUTING↗

Stochastic AC optimal power flow: A data-driven approach

There is an emerging need for efficient solutions to stochastic AC Optimal Power Flow (AC-OPF) to ensure optimal and reliable grid operations in the presence of increasing demand and generation uncertainty. Herein this paper presents a highly scalable data-driven algorithm for stochastic AC-OPF that has extremely low sample requirement. The novelty behind the algorithm’s performance involves an iterative scenario design approach that merges information regarding constraint violations in the system with data-driven sparse regression. Compared to conventional methods with random scenario sampling, our approach is able to provide feasible operating points for realistic systems with much lower sample requirements. Furthermore, multiple sub-tasks in our approach can be easily paralleled and based on historical data to enhance its performance and application. We demonstrate the computational improvements of our approach through simulations on different test cases in the IEEE PES PGLib-OPF benchmark library.

42 ENGINEERING↗

Modern Approaches to Exact Diagonalization and Selected Configuration Interaction with the Adaptive Sampling CI Method

Recent advances in selected configuration interaction methods have made them competitive with the most accurate techniques available and, hence, creating an increasingly powerful tool for solving quantum Hamiltonians. In this work, we build on recent advances from the adaptive sampling configuration interaction (ASCI) algorithm. We show that a useful paradigm for generating efficient selected CI/exact diagonalization algorithms is driven by fast sorting algorithms, much in the same way iterative diagonalization is based on the paradigm of matrix vector multiplication. We present several new algorithms for all parts of performing a selected CI, which includes new ASCI search, dynamic bit masking, fast orbital rotations, fast diagonal matrix elements, and residue arrays. The ASCI search algorithm can be used in several different modes, which includes an integral driven search and a coefficient driven search. The algorithms presented here are fast and scalable, and we find that because they are built on fast sorting algorithms they are more efficient than all other approaches we considered. After introducing these techniques, we present ASCI results applied to a large range of systems and basis sets to demonstrate the types of simulations that can be practically treated at the full-CI level with modern methods and hardware, presenting double- and triple-ζ benchmark data for the G1 data set. The largest of these calculations is Si$_2$H$_6$ which is a simulation of 34 electrons in 152 orbitals. We also present some preliminary results for fast deterministic perturbation theory simulations that use hash functions to maintain high efficiency for treating large basis sets.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Quantum simulation of excited states from parallel contracted quantum eigensolvers

Abstract Computing excited-state properties of molecules and solids is considered one of the most important near-term applications of quantum computers. While many of the current excited-state quantum algorithms differ in circuit architecture, specific exploitation of quantum advantage, or result quality, one common feature is their rooting in the Schrödinger equation. However, through contracting (or projecting) the eigenvalue equation, more efficient strategies can be designed for near-term quantum devices. Here we demonstrate that when combined with the Rayleigh–Ritz variational principle for mixed quantum states, the ground-state contracted quantum eigensolver (CQE) can be generalized to compute any number of quantum eigenstates simultaneously. We introduce two excited-state (anti-Hermitian) CQEs that perform the excited-state calculation while inheriting many of the remarkable features of the original ground-state version of the algorithm, such as its scalability. To showcase our approach, we study several model and chemical Hamiltonians and investigate the performance of different implementations.

Physics↗

Validation of Power Distribution Models using Load Flow Analysis in an ADMS Environment

Electric utilities are facing the need for better monitoring, analysis, and control of their distribution systems. An accurate mathematical model is a key to both the development of cutting-edge, scalable model-based algorithms and the assessment of emerging technologies such as distributed energy resources (DER) for grid planning and operation. However, the constantly evolving nature of power distribution systems poses challenges to maintaining accurate models. In this paper, we propose a novel load flow based approach to validate power distribution models. Networked equipment models described according to the Common Information Model (CIM) standard and a measurement model are used to formulate the distribution load flow problem. First, a system admittance matrix (Ybus) is derived from device-level CIM parameters. Next, the operational parameters (dynamic Ybus and nodal injections) are extracted from the measurement model using sensor configuration and equipment state. An iterative power flow method is then used to compute nodal voltages and branch flows that are compared against the measurement data to find any inconsistencies in the networked equipment model. This approach is implemented within GridAPPS-D, an open-source standards-based platform for advanced distribution management system (ADMS) application development, and demonstrated on the IEEE 13-bus, 123-bus, and 8500-node test feeders.

Common information model, model validation, power ↗

167-PFlops Deep Learning for Electron Microscopy: From Learning Physics to Atomic Manipulation

An artificial intelligence system called MENNDL, which used 25,200 Nvidia Volta GPUs on Oak Ridge National Laboratory’s Summit machine, automatically designed an optimal deep learning network in order to extract structural information from raw atomic-resolution microscopy data. In a few hours, MENNDL creates and evaluates millions of networks using a scalable, parallel, asynchronous genetic algorithm augmented with a support vector machine to automatically find a superior deep learning network topology and hyper-parameter set than a human expert can find in months. For the application of electron microscopy, the system furthers the goal of improving our understanding of the electron-beam-matter interactions and real-time image-based feedback, which enables a huge step beyond human capacity toward nanofabricating materials automatically. Finally, MENNDL has been scaled to the 4,200 available nodes of Summit achieving a measured 152.5 PFlops, with an estimated sustained performance of 167 PFlops when the entire machine is available.

97 MATHEMATICS AND COMPUTING↗

The Case for Strong Scaling in Deep Learning: Training Large 3D CNNs with Hybrid Parallelism

Here, we present scalable hybrid-parallel algorithms for training large-scale 3D convolutional neural networks. Deep learning-based emerging scientific workflows often require model training with large, high-dimensional samples, which can make training much more costly and even infeasible due to excessive memory usage. We solve these challenges by extensively applying hybrid parallelism throughout the end-to-end training pipeline, including both computations and I/O. Our hybrid-parallel algorithm extends the standard data parallelism with spatial parallelism, which partitions a single sample in the spatial domain, realizing strong scaling beyond the mini-batch dimension with a larger aggregated memory capacity. We evaluate our proposed training algorithms with two challenging 3D CNNs, CosmoFlow and 3D U-Net. Our comprehensive performance studies show that good weak and strong scaling can be achieved for both networks using up to 2K GPUs. More importantly, we enable training of CosmoFlow with much larger samples than previously possible, realizing an order-of-magnitude improvement in prediction accuracy.

97 MATHEMATICS AND COMPUTING↗

Multiobjective Hyperparameter Optimization for Deep Learning Interatomic Potential Training Using NSGA-II

Deep neural network (DNN) potentials are an emerging tool for simulation of dynamical atomistic systems, with the promise of quantum mechanical accuracy at speedups of 10000$\times$. As with other DNN methods, hyperparameters used during training can make a substantial difference in model accuracy, and optimal settings vary with dataset. To enable rapid tuning of hyperparameters for DNN potential training, we developed a scalable multiobjective optimization evolutionary algorithm for supercomputers and tested it on the Summit system at the Oak Ridge Leadership Computing Facility (OLCF). The multiobjective approach is required due to the coupling of two learned values defining the potential: the energy and force. Using a large-scale implementation of the NSGA-II algorithm adapted for training DNN potentials, we discovered several optimal multiobjective combinations, including best choices of activation functions, learning rate scaling scheme, and pairing of the two radial cutoffs used in the three dimensional descriptor function.

Coletti, Mark↗

Machine Learning Toolkit for Extreme Scale

Support Vector Machines (SVM) is a popular machine learning technique, which has been applied to a wide range of domains such as science, finance, and social networks for supervised learning. MaTEx undertakes the challenge of designing a scalable parallel SVM training algorithm for large scale systems, which includes commodity multi-core machines, tightly connected supercomputers and cloud computing systems. Several techniques are proposed for improved speed and memory space usage including adaptive and aggressive elimination of samples for faster convergence , and sparse format representation of data samples. Several heuristics for earliest possible to lazy elimination of non-contributing samples are considered in MaTEx. In many cases, where an early sample elimination might result in a false positive, low overhead mechanisms for reconstruction of key data structures are proposed. The proposed algorithm and heuristics are implemented and evaluated on various publicly available datasets

Source record↗