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 1,279 records · Page 71

Dynamically Reconfigurable Systolic Array Accelerator

A polymorphic systolic array framework has been developed that works in conjunction with an embedded microprocessor on a field-programmable gate array (FPGA), which allows for dynamic and complimentary scaling of acceleration levels of two algorithms active concurrently on the FPGA. Use is made of systolic arrays and a hardware-software co-design to obtain an efficient multi-application acceleration system. The flexible and simple framework allows hosting of a broader range of algorithms, and is extendable to more complex applications in the area of aerospace embedded systems. FPGA chips can be responsive to realtime demands for changing applications needs, but only if the electronic fabric can respond fast enough. This systolic array framework allows for rapid partial and dynamic reconfiguration of the chip in response to the real-time needs of scalability, and adaptability of executables.

Dasu, Aravind↗

Ion Coulomb Crystals in Storage Rings for Quantum Information Science

Quantum information science is a growing field that promises to take computing into a new age of higher performance and larger scale computing as well as being capable of solving problems classical computers are incapable of solving. The outstanding issue in practical quantum computing today is scaling up the system while maintaining interconnectivity of the qubits and low error rates in qubit operations to be able to implement error correction and fault-tolerant operations. Trapped ion qubits offer long coherence times that allow error correction. However, error correction algorithms require large numbers of qubits to work properly. We can potentially create many thousands (or more) of qubits with long coherence states in a storage ring. For example, a circular radio-frequency quadrupole, which acts as a large circular ion trap and could enable larger scale quantum computing. Such a Storage Ring Quantum Computer (SRQC) would be a scalable and fault tolerant quantum information system, composed of qubits with very long coherence lifetimes. With computing demands potentially outpacing the supply of high-performance systems, quantum computing could bring innovation and scientific advances to particle physics and other DOE supported programs. Increased support of R$\&$D in large scale ion trap quantum computers would allow the timely exploration of this exciting new scalable quantum computer. The R$\&$D program could start immediately at existing facilities and would include the design and construction of a prototype SRQC. We invite feedback from and collaboration with the particle physics and quantum information science communities.

43 PARTICLE ACCELERATORS↗

Optimization of Thermal Conductance at Interfaces Using Machine Learning Algorithms

We report optimization of thermal transport across the interface of two different materials is critical to micro-/nanoscale electronic, photonic, and phononic devices. Although several examples of compositional intermixing at the interfaces having a positive effect on interfacial thermal conductance (ITC) have been reported, an optimum arrangement has not yet been determined because of the large number of potential atomic configurations and the significant computational cost of evaluation. On the other hand, computation-driven materials design efforts are rising in popularity and importance. Yet, the scalability and transferability of machine learning models remain as challenges in creating a complete pipeline for the simulation and analysis of large molecular systems. In this work we present a scalable Bayesian optimization framework, which leverages dynamic spawning of jobs through the Message Passing Interface (MPI) to run multiple parallel molecular dynamics simulations within a parent MPI job to optimize heat transfer at the silicon and aluminum (Si/Al) interface. We found a maximum of 50% increase in the ITC when introducing a two-layer intermixed region that consists of a higher percentage of Si. Because of the random nature of the intermixing, the magnitude of increase in the ITC varies. We observed that both homogeneity/heterogeneity of the intermixing and the intrinsic stochastic nature of molecular dynamics simulations account for the variance in ITC.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Scalable Distributed Memory Community Detection Using Vite

Graph clustering, popularly known as community detection, is a fundamental graph operation used in several applications of relevance for network analysis and cybersecurity. Community detection is an operation of partitioning a network into an arbitrary number of “communities” such that each com munity represents a tightly-knit group of nodes with relatively sparser connections to the rest of the nodes in the network. The need to compute clustering on large-scale networks necessitates the development of efficient parallel algorithms capable of exploiting modern parallel architectures. However, due to their irregular and inherently sequential nature, many of the current algorithms for community detection are challenging to parallelize. In response to the 2018 Graph Challenge, we present Vite which is a distributed-memory parallel community detection method. Vite is a parallelization of the algorithmic template provided by a widely-used serial method (Louvain). Alongside, it uses several heuristics aimed at significantly improving parallelism and performance, while preserving output quality. Using the inputs from the 2018 Graph Challenge (static and streaming), we demonstrate superior performance and high quality solutions based on four parallelization heuristics.

community detection↗

Providing Geospatial Intelligence through a Scalable Imagery Pipeline

This chapter describes ORNL’s (Oak Ridge National Laboratory’s) contributions to imagery preprocessing for geospatial intelligence research and development (R&D) in four sections. First, we discuss challenges involved in building an effective imagery preprocessing workflow and the world-class high-performance computing (HPC) resources at ORNL available to process petabytes of imagery data. Second, we highlight how we developed imagery preprocessing tools over three decades while paving the way for our current cutting-edge machine learning and computer vision algorithms that are impacting humanitarian and disaster response efforts. Third, we discuss how PIPE modules work together to turn raw images into analysis-ready datasets. Fourth, we look toward the future and discuss planned advancements to PIPE and computing trends that will affect geospatial intelligence R&D.

Reith, Andrew↗

The Heuristic Static Load-Balancing Algorithm Applied to the Community Earth System Model

We propose to use the heuristic static loadbalancing (HSLB) algorithm for solving load-balancing problems in the Community Earth System Model (CESM), a climate model, using fitted benchmark data as an alternative to the current manual approach. The problem of allocating the optimal number of CPU cores to CESM components is formulated as a mixed-integer nonlinear optimization problem which is solved by using an optimization branch-and-bound solver implemented in the MINLP package MINOTAUR. The key feature of the branch-and- bound method is that it guarantees to provide an optimal solution or show that none exists. Our algorithm was tested for the 1 degrees and 1/8 degrees resolution simulations on 32,768 nodes (131,072 cores) of IBM Blue Gene/P where we consistently achieved well load-balanced results. This work is a part of a broader effort to eliminate the need for manual tuning of the code for each platform and simulation type, improve the performance and scalability of CESM, and develop automated tools to achieve these goals.

Alekseev, Yury↗

Improving large-scale storage system performance via topology-aware and balanced data placement

With the advent of big data, the I/O subsystems of large-scale compute clusters are becoming a center of focus. More applications are putting greater demands on end-to-end I/O performance. These subsystems are often complex in design. They comprise of multiple hardware and software layers to cope with the increasing capacity, capability, and scalability requirements of data intensive applications. However, the sharing nature of storage resources and the intrinsic interactions across these layers make it a great challenge to realize end-to-end performance gains. This paper proposes a topology-aware strategy to balance the load across resources, to improve the per-application I/O performance. We demonstrate the effectiveness of our algorithm on an extreme-scale compute cluster, Titan, at the Oak Ridge Leadership Computing Facility (OLCF). Our experiments with both synthetic benchmarks and a real-world application show that, even under congestion, our proposed algorithm can improve large-scale application I/O performance significantly, resulting in both a reduction in application run time as well as a higher resolution of simulation run.

Wang, Feiyi↗

A single-tree algorithm to compute the Euclidean minimum spanning tree on GPUs

Computing the Euclidean minimum spanning tree (Emst) is a computationally demanding step of many algorithms. While work-efficient serial and multithreaded algorithms for computing Emst are known, designing an efficient GPU algorithm is challenging due to a complex branching structure, data dependencies, and load imbalances. In this paper, we propose a single-tree $Bor\mathring{u}vka$-based algorithm for computing Emst on GPUs. We use an efficient nearest neighbor algorithm and reduce the number of the required distance calculations by avoiding traversing subtrees with leaf nodes in the same component. The developed algorithms are implemented in a performance portable way using ArborX, an open-source geometric search library based on the Kokkos framework. We evaluate the proposed algorithm on various 2D and 3D datasets, show and compare it with the current state-of-the-art open-source CPU implementations. We demonstrate 4-24 × speedup over the fastest multi-threaded implementation. We prove the portability of our implementation by providing results on a variety of hardware: AMD EPYC 7763, Nvidia A100 and AMD MI250X. We show scalability of the implementation, computing Emst for 37 million 3D cosmological dataset in under a 0.5 second on a single A100 Nvidia GPU.

Prokopenko, Andrey↗

Highly Scalable, UDP-Based Network Transport Protocols for Lambda Grids and 10 GE Routed Networks

Summary of Report In work prior to this grant, NCDM developed a high performance data transport protocol called SABUL. During this grant, we refined SABUL’s functionality, and then extended both the capabilities and functionality and incorporated them into a new protocol called UDP-based Data transport Protocol, or UDT. We also began preliminary work on Composable UDT, a version of UDT that allows the user to choose among different congestion control algorithms and implement the algorithm of his choice at the time he compiles the code. Specifically, we: · Investigated the theoretical foundations of protocols similar to SABUL and UDT. · Performed design and development work of UDT, a protocol that uses UDP in both the data and control channels. · Began design and development work of Composable UDT, a protocol that supports the use of different congestion control algorithms by simply including the appropriate library when compiling the code. · Performed experimental studies using UDT and Composable UDT using real world applications such as the Sloan Digital Sky Survey (SDSS) astronomical data sets. · Released several versions of UDT and Composable, the most recent being v3.1.

97 MATHEMATICS AND COMPUTING↗

Scalable Distributed Automation System: Scalable Real-time Decentralized Volt/VAR Control

GENI Project: Caltech is developing a distributed automation system that allows distributed generators—solar panels, wind farms, thermal co-generation systems—to effectively manage their own power. To date, the main stumbling block for distributed automation systems has been the inability to develop software that can handle more than 100,000 distributed generators and be implemented in real time. Caltech’s software could allow millions of generators to self-manage through local sensing, computation, and communication. Taken together, localized algorithms can support certain global objectives, such as maintaining the balance of energy supply and demand, regulating voltage and frequency, and minimizing cost. An automated, grid-wide power control system would ease the integration of renewable energy sources like solar power into the grid by quickly transmitting power when it is created, eliminating the energy loss associated with the lack of renewable energy storage capacity of the grid.

ARPA-E↗

Simultaneous inversion of shear modulus and traction boundary conditions in biomechanical imaging

We present a formulation to simultaneously invert for a heterogeneous shear modulus field and traction boundary conditions in an incompressible linear elastic plane stress model. Our approach utilizes scalable deterministic methods, including adjoint-based sensitivities and quasi-Newton optimization, to reduce the computational requirements for large-scale inversion with partial differential equation (PDE) constraints. Here, we address the use of regularization for such formulations and explore the use of different types of regularization for the shear modulus and boundary traction. We apply this PDE-constrained optimization algorithm to a synthetic dataset to verify the accuracy in the reconstructed parameters, and to experimental data from a tissue-mimicking ultrasound phantom. In all of these examples, we compare inversion results from full-field and sparse data measurements.

42 ENGINEERING↗

Optimizing blocking and nonblocking reduction operations for multicore systems: Hierarchical design and implementation

Many scientific simulations, using the Message Passing Interface (MPI) programming model, are sensitive to the performance and scalability of reduction collective operations such as MPI_Allreduce and MPI_Reduce. These operations are the most widely used abstractions to perform mathematical operations over all processes that are part of the simulation. In this work, we propose a hierarchical design to implement the reduction operations on multicore systems. This design aims to improve the efficiency of reductions by 1) tailoring the algorithms and customizing the implementations for various communication mechanisms in the system 2) providing the ability to configure the depth of hierarchy to match the system architecture, and 3) providing the ability to independently progress each of this hierarchy. Using this design, we implement MPI_Allreduce and MPI_Reduce operations (and its nonblocking variants MPI_Iallreduce and MPI_Ireduce) for all message sizes, and evaluate on multiple architectures including InfiniBand and Cray XT5. We leverage and enhance our existing infrastructure, Cheetah, which is a framework for implementing hierarchical collective operations to implement these reductions. The experimental results show that the Cheetah reduction operations outperform the production-grade MPI implementations such as Open MPI default, Cray MPI, and MVAPICH2, demonstrating its efficiency, flexibility and portability. On Infini-Band systems, with a microbenchmark, a 512-process Cheetah nonblocking Allreduce and Reduce achieves a speedup of 23x and 10x, respectively, compared to the default Open MPI reductions. The blocking variants of the reduction operations also show similar performance benefits. A 512-process nonblocking Cheetah Allreduce achieves a speedup of 3x, compared to the default MVAPICH2 Allreduce implementation. On a Cray XT5 system, a 6144-process Cheetah Allreduce outperforms the Cray MPI by 145%. The evaluation with an application kernel, Conjugate Gradient solver, shows that the Cheetah reductions speeds up total time to solution by 195%, demonstrating the potential benefits for scientific simulations.

Venkata, Manjunath Gorentla↗

A Domain-Decomposed Multilevel Method for Adaptively Refined Cartesian Grids with Embedded Boundaries

Preliminary verification and validation of an efficient Euler solver for adaptively refined Cartesian meshes with embedded boundaries is presented. The parallel, multilevel method makes use of a new on-the-fly parallel domain decomposition strategy based upon the use of space-filling curves, and automatically generates a sequence of coarse meshes for processing by the multigrid smoother. The coarse mesh generation algorithm produces grids which completely cover the computational domain at every level in the mesh hierarchy. A series of examples on realistically complex three-dimensional configurations demonstrate that this new coarsening algorithm reliably achieves mesh coarsening ratios in excess of 7 on adaptively refined meshes. Numerical investigations of the scheme's local truncation error demonstrate an achieved order of accuracy between 1.82 and 1.88. Convergence results for the multigrid scheme are presented for both subsonic and transonic test cases and demonstrate W-cycle multigrid convergence rates between 0.84 and 0.94. Preliminary parallel scalability tests on both simple wing and complex complete aircraft geometries shows a computational speedup of 52 on 64 processors using the run-time mesh partitioner.

Aftosmis, M. J.↗

Optimizing Blocking and Nonblocking Reduction Operations for Multicore Systems: Hierarchical Design and Implementation

Many scientific simulations, using the Message Passing Interface (MPI) programming model, are sensitive to the performance and scalability of reduction collective operations such as MPI Allreduce and MPI Reduce. These operations are the most widely used abstractions to perform mathematical operations over all processes that are part of the simulation. In this work, we propose a hierarchical design to implement the reduction operations on multicore systems. This design aims to improve the efficiency of reductions by 1) tailoring the algorithms and customizing the implementations for various communication mechanisms in the system 2) providing the ability to configure the depth of hierarchy to match the system architecture, and 3) providing the ability to independently progress each of this hierarchy. Using this design, we implement MPI Allreduce and MPI Reduce operations (and its nonblocking variants MPI Iallreduce and MPI Ireduce) for all message sizes, and evaluate on multiple architectures including InfiniBand and Cray XT5. We leverage and enhance our existing infrastructure, Cheetah, which is a framework for implementing hierarchical collective operations to implement these reductions. The experimental results show that the Cheetah reduction operations outperform the production-grade MPI implementations such as Open MPI default, Cray MPI, and MVAPICH2, demonstrating its efficiency, flexibility and portability. On Infini- Band systems, with a microbenchmark, a 512-process Cheetah nonblocking Allreduce and Reduce achieves a speedup of 23x and 10x, respectively, compared to the default Open MPI reductions. The blocking variants of the reduction operations also show similar performance benefits. A 512-process nonblocking Cheetah Allreduce achieves a speedup of 3x, compared to the default MVAPICH2 Allreduce implementation. On a Cray XT5 system, a 6144-process Cheetah Allreduce outperforms the Cray MPI by 145%. The evaluation with an application kernel, Conjugate Gradient solver, shows that the Cheetah reductions speeds up total time to solution by 195%, demonstrating the potential benefits for scientific simulations.

Gorentla Venkata, Manjunath↗

Scalable 3D reconstruction for X-ray single particle imaging with online machine learning

X-ray free-electron lasers offer unique capabilities for measuring the structure and dynamics of biomolecules, helping us understand the basic building blocks of life. Notably, high-repetition-rate free-electron lasers enable single particle imaging, where individual, weakly scattering biomolecules are imaged under near-physiological conditions with the opportunity to access fleeting states that cannot be captured in cryogenic or crystallized conditions. Existing X-ray single particle reconstruction algorithms, which estimate the particle orientation for each image independently, are slow and memory-intensive when handling the massive datasets generated by emerging free-electron lasers. Here, we introduce X-RAI (X-Ray single particle imaging with Amortized Inference), an online reconstruction framework that estimates the structure of 3D macromolecules from large X-ray single particle datasets. X-RAI consists of a convolutional encoder, which amortizes pose estimation over large datasets, as well as a physics-based decoder, which employs an implicit neural representation to enable high-quality 3D reconstruction in an end-to-end, self-supervised manner. We demonstrate that X-RAI achieves state-of-the-art performance for small-scale datasets in simulation and challenging experimental settings and demonstrate its unprecedented ability to process large datasets containing millions of diffraction images in an online fashion. These abilities signify a paradigm shift in X-ray single particle imaging towards real-time reconstruction.

Computer science↗

Locality-Aware Scheduling for Scalable Heterogeneous Environments

Heterogeneous computing promise boost performance of scientific applications by allowing massively parallel execution of computational tasks. However, manually managing extremely heterogeneous, multi-device systems is complicated and may result in sub-optimal performance. Specifically, data management is an extremely challenging problem on multi-device systems. In this work, we introduce two locality-aware schedulers for the Minos Computing Library (MCL), an asynchronous, task-based programming model and runtime for extremely heterogeneous systems. The first scheduler implements a pure locality-aware algorithm to maximize data reuse, though it might incur in ”hot-spots” that limit system utilization. The second scheduler mitigates this drawback by dynamically targeting between locality-awareness and system utilization based on the current workload and available computing devices. Our results show that locality-awareness greatly benefit applications that exhibit data reuse, providing up to 6.9x and 7.9x over the original MCL scheduler and equivalent OpenCL implementations, respectively. Moreover, our schedulers introduce negligible overhead compared with the original MCL scheduler and achieve similar performance for applications that don’t benefit from data locality.

Architecture, co-design, Task-based programming mo↗

Soil moisture estimation using tomographic ground penetrating radar in a MCMC–Bayesian framework

In this paper, we focus on a hydrogeological inverse problem specifically targeting monitoring soil moisture variations using tomographic ground penetrating radar (GPR) travel time data. Technical challenges exist in the inversion of GPR tomographic data for handling non-uniqueness, nonlinearity and high-dimensionality of unknowns. We have developed a new method for estimating soil moisture fields from crosshole GPR data. It uses a pilot-point method to provide a low-dimensional representation of the relative dielectric permittivity field of the soil, which is the primary object of inference: the field can be converted to soil moisture using a petrophysical model. We integrate a multi-chain Markov chain Monte Carlo (MCMC)–Bayesian inversion framework with the pilot point concept, a curved-ray GPR travel time model, and a sequential Gaussian simulation algorithm, for estimating the dielectric permittivity at pilot point locations distributed within the tomogram, as well as the corresponding geostatistical parameters (i.e., spatial correlation range). We infer the dielectric permittivity as a probability density function, thus capturing the uncertainty in the inference. The multi-chain MCMC enables addressing high-dimensional inverse problems as required in the inversion setup. The method is scalable in terms of number of chains and processors, and is useful for computationally demanding Bayesian model calibration in scientific and engineering problems. The proposed inversion approach can successfully approximate the posterior density distributions of the pilot points, and capture the true values. The computational efficiency, accuracy, and convergence behaviors of the inversion approach were also systematically evaluated, by comparing the inversion results obtained with different levels of noises in the observations, increased observational data, as well as increased number of pilot points.

54 ENVIRONMENTAL SCIENCES↗

Multilevel Graph Partitioning for Three-Dimensional Discrete Fracture Network Flow Simulations

We present a topology-based method for mesh-partitioning in three-dimensional discrete fracture network (DFN) simulations that takes advantage of the intrinsic multi-level nature of a DFN. DFN models are used to simulate flow and transport through low-permeability fractured media in the subsurface by explicitly representing fractures as discrete entities. The governing equations for flow and transport are numerically integrated on computational meshes generated on the interconnected fracture networks. Modern high-fidelity DFN simulations require high-performance computing on multiple processors where performance and scalability depends partially on obtaining a high-quality partition of the mesh to balance work-loads and minimize communication across all processors. The discrete structure of a DFN naturally lends itself to various graph representations, which can be thought of as coarse-scale representations of the computational mesh. Using this concept, we develop two applications of the multilevel graph partitioning algorithm to partition the mesh of a DFN. In the first, we project a partition of the graph based on the DFN topology onto the mesh of the DFN and in the second, this DFN-based projection is used as the initial condition for further partitioning refinement of the mesh. We compare the performance of these methods with standard multi-level graph partitioning using graph-based metrics (cut, imbalance, partitioning time), computational-based metrics (FLOPS, iterations, solver time), and total run time. The DFN-based and the mesh-based partitioning methods are comparable in terms of the graph-based metrics, but the time required to obtain the partition is several orders of magnitude faster using the DFN-based partitions. The computation-based metrics show comparable performance between both methods so, in combination, the DFN-based partitions are several orders of magnitude faster than the mesh-based partition. Furthermore, the method which uses the DFN-partition solution as the initial condition of the mesh partition provided cut and imbalance values that were close to the mesh-based partition but in a fraction of the time. In turn, this hybrid method outperformed both of the other methods in terms of the total run time.

58 GEOSCIENCES↗