Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Network partitioning”

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 109 records · Page 6

Partitioning net carbon dioxide fluxes into photosynthesis and respiration using neural networks

The eddy covariance (EC) technique is used to measure the net ecosystem exchange (NEE) of CO 2 between ecosystems and the atmosphere, offering a unique opportunity to study ecosystem responses to climate change. NEE is the difference between the total CO 2 release due to all respiration processes (RECO), and the gross carbon uptake by photosynthesis (GPP). These two gross CO 2 fluxes are derived from EC measurements by applying partitioning methods that rely on physiologically based functional relationships with a limited number of environmental drivers. However, the partitioning methods applied in the global FLUXNET network of EC observations do not account for the multiple co-acting factors that modulate GPP and RECO flux dynamics. To overcome this limitation, we developed a hybrid data-driven approach based on combined neural networks (NN C-part ). NN C-part incorporates process knowledge by introducing a photosynthetic response based on the light-use efficiency (LUE) concept, and uses a comprehensive dataset of soil and micrometeorological variables as fluxes drivers. We applied the method to 36 sites from the FLUXNET2015 dataset and found a high consistency in the results with those derived from other standard partitioning methods for both GPP (R 2 > .94) and RECO (R 2 > .8). High consistency was also found for (a) the diurnal and seasonal patterns of fluxes and (b) the ecosystem functional responses. NNC-part performed more realistic than the traditional methods for predicting additional patterns of gross CO 2 fluxes, such as: (a) the GPP response to VPD, (b) direct effects of air temperature on GPP dynamics, (c) hysteresis in the diel cycle of gross CO 2 fluxes, (d) the sensitivity of LUE to the diffuse to direct radiation ratio, and (e) the post rain respiration pulse after a long dry period. In conclusion, NN C-part is a valid data-driven approach to provide GPP and RECO estimates and complementary to the existing partitioning methods.

54 ENVIRONMENTAL SCIENCES↗

Distributed Louvain Algorithm for Graph Community Detection

In most real-world networks, the nodes/vertices tend to be organized into tightly-knit modules known as communities or clusters, such that nodes within a community are more likely to be “related” to one another than they are to the rest of the network. The goodness of partitioning into communities is typically measured using a well known measure called modularity. However, modularity optimization is an NP-complete problem. In 2008, Blondel, et al. introduced a multi-phase, iterative heuristic for modularity optimization, called the Louvain method. Owing to its speed and ability to yield high quality communities, the Louvain method continues to be one of the most widely used tools for serial community detection. In this paper, we present the design of a distributed memory implementation of the Louvain algorithm for parallel community detection. Our approach begins with an arbitrarily partitioned distributed graph input, and employs several heuristics to speedup the computation of the different steps of the Louvain algorithm. We evaluate our implementation and its different variants using real-world networks from various application domains (including internet, biology, social networks). Our MPI+OpenMP implementation yields about 7x speedup (on 4K processes) for soc-friendster network (1.8B edges) over a state-of-the-art shared-memory multicore implementation (on 64 threads), without compromising output quality. Furthermore, our distributed implementation was able to process a larger graph (uk-2007; 3.3B edges) in 32 seconds on 1K cores (64 nodes) of NERSC Cori, when the state-of-the-art shared-memory implementation failed to run due to insufficient memory on a single Cori node containing 128 GB.

High performance computing, graph algorithms, Dist↗

Influences on Discharge Partitioning on a Large River Delta: Case Study of the Mississippi-Atchafalaya Diversion, 1926-1950

The modern Mississippi River (M.R.) Delta is plumbed by the Mississippi and Atchafalaya rivers, setting water and sediment dispersal pathways for Earth’s fifth-largest river system. The Atchafalaya River’s (A.R.) partial annexation of discharge from the M.R., particularly between 1926 and 1950, prompted warnings of a rapid river avulsion and the construction of the Old River Control Structure to regulate flow. Natural and anthropogenic causes of this discharge annexation are difficult to disentangle. Here, we develop and validate a hydrodynamic model of flow partitioning through the historic channel network. We then isolate how several key changes to the system affected discharge partitioning and stage at the A.R.-M.R. diversion. Simulations show that erosion of the upper A.R. can account for 73% of the water discharge increase. Dredging in the lower A.R. between 1932 and 1950 can account for 35% of the water discharge increase, and was also an important control on shear stress distribution. The lower M.R. was slightly erosional during this period, and therefore hindered the A.R. discharge increase. Significant lacustrine delta deposition in A.R. had little effect on partitioning. These findings highlight the importance of A.R. enlargement processes on avulsion dynamics at this site. Given the essential nature of this river junction to the society, transportation, and commerce of the United States, improved attribution of discharge increases may lead to future management strategies that are broadly impactful.

54 ENVIRONMENTAL SCIENCES↗

Using the D-Wave 2X Quantum Computer to Explore the Formation of Global Terrorist Networks

Social networks with signed edges (+/-) play an important role in an area of social network theory called structural balance. In these networks, edges represent relationships that are labeled as either friendly (+) or hostile (-). A signed social network is balanced only if all cycles of three or more nodes in the graph have an odd number of hostile edges. A fundamental property of a balanced network is that it can be cleanly divided into 2 factions, where all relationships within each faction are friendly, and all relationships between members of different factions are hostile. The more unbalanced a network is, the more edges will fail to adhere to this rule, making factions more ambiguous. Social theory suggests unbalanced networks should be unstable, a finding that has been supported by research on gangs, which shows that unbalanced relationships are associated with greater violence, possibly due to this increased ambiguity about factional allegiances (Nakamura et al). One way to estimate the imbalance in a network, if only edge relationships are known, is to assign nodes to factions that minimize the number of violations of the edge rule described above. This problem is known to be computationally NP-hard. However, Facchetti et al. have pointed out that it is equivalent to an Ising model with a Hamiltonian that effectively counts the number of edge rule violations. Therefore, finding the assignment of factions that minimizes energy of the equivalent Ising system yields an estimate of the imbalance in the network. Based on the Ising model equivalence of the signed-social network balance problem, we have used the D-Wave 2X quantum annealing computer to explore some aspects of signed social networks. Because connectivity in the D-Wave computer is limited to its particular native topology, arbitrary networks cannot be represented directly. Rather, they must be “embedded” using a technique in which multiple qubits are chained together with special weights to simulate a collection of nodes with the required connectivity. This limits the size of a fully connected network in the D-Wave to about 50 simulated nodes, using all of the approximately 1150 qubits in the machine. In order to keep within this limitation, while exploring a problem of potential social relevance, we constructed time series of historical network snapshots from Stanford’s Mapping Militants Project, where nodes represent militant organizations, and edges represent either alliances or rivalries between organizations. We constructed two series from different theaters – Iraq and Syria – spanning timelines from about 2000 to 2016, each with networks whose maximum size was in the 20-30 node range. Computationally, our experience suggests D-Wave technology is promising, providing fast, nearly constant scaling of computational effort in the main part of the calculation that relies on the quantum annealing cycle. However, the cost of embedding an arbitrary network of interest in the D-Wave native topology scales poorly. If the embedding cost can be amortized relative to the annealing cycle, it may be possible to gain a substantial advantage over classical computing methods, provided a large enough network can be accommodated by partitioning into subnetworks or some similar strategy. In terms of our application to networks of militant organizations, we found a rise in network imbalance in the Syrian theater that appears to correspond roughly with the entrance of the Islamic State into a milieu already populated with other groups, a phenomenon we plan to explore in more detail. In these very preliminary results, we also noticed that during at least one period where both the size and imbalance of the network increased substantially, the imbalance per edge seemed to remain fairly steady. This may suggest some adaptive behavior among the participating factions, which may also warrant further exploration.

97 MATHEMATICS AND COMPUTING↗

Community detection in sequence similarity networks based on attribute clustering

Networks are powerful tools for the presentation and analysis of interactions in multi-component systems. A commonly studied mesoscopic feature of networks is their community structure, which arises from grouping together similar nodes into one community and dissimilar nodes into separate communities. Here in this paper, the community structure of protein sequence similarity networks is determined with a new method: Attribute Clustering Dependent Communities (ACDC). Sequence similarity has hitherto typically been quantified by the alignment score or its expectation value. However, pair alignments with the same score or expectation value cannot thus be differentiated. To overcome this deficiency, the method constructs, for pair alignments, an extended alignment metric, the link attribute vector, which includes the score and other alignment characteristics. Rescaling components of the attribute vectors qualitatively identifies a systematic variation of sequence similarity within protein superfamilies. The problem of community detection is then mapped to clustering the link attribute vectors, selection of an optimal subset of links and community structure refinement based on the partition density of the network. ACDC-predicted communities are found to be in good agreement with gold standard sequence databases for which the "ground truth" community structures (or families) are known. ACDC is therefore a community detection method for sequence similarity networks based entirely on pair similarity information. A serial implementation of ACDC is available from https://cmb.ornl.gov/resources/developments

59 BASIC BIOLOGICAL SCIENCES↗

Wireless Avionics Packet to Support Fault Tolerance for Flight Applications

In this protocol and packet format, data traffic is monitored by all network interfaces to determine the health of transmitter and subsystems. When failures are detected, the network inter face applies its recover y policies to provide continued service despite the presence of faults. The protocol, packet format, and inter face are independent of the data link technology used. The current demonstration system supports both commercial off-the-shelf wireless connections and wired Ethernet connections. Other technologies such as 1553 or serial data links can be used for the network backbone. The Wireless Avionics packet is divided into three parts: a header, a data payload, and a checksum. The header has the following components: magic number, version, quality of service, time to live, sending transceiver, function code, payload length, source Application Data Interface (ADI) address, destination ADI address, sending node address, target node address, and a sequence number. The magic number is used to identify WAV packets, and allows the packet format to be updated in the future. The quality of service field allows routing decisions to be made based on this value and can be used to route critical management data over a dedicated channel. The time to live value is used to discard misrouted packets while the source transceiver is updated at each hop. This information is used to monitor the health of each transceiver in the network. To identify the packet type, the function code is used. Besides having a regular data packet, the system supports diagnostic packets for fault detection and isolation. The payload length specifies the number of data bytes in the payload, and this supports variable-length packets in the network. The source ADI is the address of the originating interface. This can be used by the destination application to identify the originating source of the packet where the address consists of a subnet, subsystem class within the subnet, a subsystem unit, and the local ADI number. The destination ADI is used to route the packet to its ultimate destination. At each hop, the sending interface uses the destination address to determine the next node for the data. The sending node is the node address of the interface that is broadcasting the packet. This field is used to determine the health of the subsystem that is sending the packet. In the case of a packet that traverses several intermediate nodes, it may be the node address of the intermediate node. The target node is the node address of the next hop for the packet. It may be an intermediate node, or the final destination for the packet. The sequence number is used to identify duplicate packets. Because each interface has multiple transceivers, the same packet will appear at both receivers. The sequence number allows the interface to correlate the reception and forward a single, unique packet for additional processing. The subnet field allows data traffic to be partitioned into segregated local networks to support large networks while keeping each subnet at a manageable size. This also keeps the routing table small enough so routing can be done by a simple table lookup in an FPGA device. The subsystem class identifies members of a set of redundant subsystems, and, in a hot standby configuration, all members of the subsystem class will receive the data packets. Only the active subsystem will generate data traffic. Specific units in a class of redundant units can be identified and, if the hot standby configuration is not used, packets will be directed to a specific subsystem unit.

Block, Gary L.↗

Notified access in coarray-based hydrodynamics applications on many-core architectures: Design and performance

With the increasing availability of the Remote Direct Memory Access (RDMA) support in computer networks, the so called Partitioned Global Address Space (PGAS) model has evolved in the last few years. Although there are several cases where a PGAS approach can easily solve difficult message passing situations, like in particle tracking and adaptive mesh refinement applications, the producer-consumer pattern, usually adopted in task-based parallelism, can only be implemented inefficiently because of the separation between data transfer and synchronization (which is usually unified in message passing programming models). Here, in this paper, we provide two contributions: (1) we propose an extension for the Fortran language that provides the concept of Notified Access by associating regular coarray variables with event variables. (2) We demonstrate that the MPI extension proposed by foMPI for Notified Access can be used effectively to implement the same concept in a PGAS run-time library like OpenCoarrays. Moreover, for a hydrodynamics mini-application, we found that Fortran 2018 events perform always better than Fortran 2008 sync statements on many-core processors. We finally show how the proposed Notified Access can improve the performance even more.

97 MATHEMATICS AND COMPUTING↗

A Parallel Solver for Graph Laplacians

Problems from graph drawing, spectral clustering, network flow and graph partitioning can all be expressed in terms of graph Laplacian matrices. There are a variety of practical approaches to solving these problems in serial. However, as problem sizes increase and single core speeds stagnate, parallelism is essential to solve such problems quickly. We present an unsmoothed aggregation multigrid method for solving graph Laplacians in a distributed memory setting. We introduce new parallel aggregation and low degree elimination algorithms targeted specifically at irregular degree graphs. These algorithms are expressed in terms of sparse matrix-vector products using generalized sum and product operations. This formulation is amenable to linear algebra using arbitrary distributions and allows us to operate on a 2D sparse matrix distribution, which is necessary for parallel scalability. Our solver outperforms the natural parallel extension of the current state of the art in an algorithmic comparison. We demonstrate scalability to 576 processes and graphs with up to 1.7 billion edges.

Konolige, Tristan↗

Global Aerodynamic Modeling Using Automated Local Model Networks in Real Time

A novel method is presented for automated real-time global aerodynamic modeling using local model networks, known as Smoothed Partitioning with Localized Trees in Real Time (SPLITR), as part of NASA’s Learn-to-Fly technology development initiative. The global nonlinear aerodynamics are partitioned into several local regions known as cells, with the dimension, location, and timing of each partition automatically selected based on a residual characterization procedure, under the constraints of real-time operation. Regression trees represent the successive partitioning of the global flight envelope and describe the evolution of the cell structure. Recursive equation-error least-squares parameter estimation in the time domain is used to estimate a model that represents the local aerodynamics in each region, so that it can be updated independently with non-contiguous data in the range of each cell over time. A weighted superposition of these piecewise local models across the flight envelope forms a global nonlinear model that also accurately captures the local aerodynamics. The SPLITR approach is demonstrated using both simulation and flight data, and the results are analyzed in terms of model predictive capabilities as well as interpretability. The results show that SPLITR can be used to automatically partition complex nonlinear aerodynamic behavior, produce an accurate model, and provide valuable physical insight into the local and global aerodynamics.

Weinstein, Rose↗

Machine Learning Applications to Metal-Silicate Equilibria and their Insights into Core Formation

An extensive number of studies have experimentally investigated how elements distribute between metal and silicate phases, to better constrain core-mantle chemical equilibrium. Here, we present a new database compiling all (to our knowledge) experimental data on liquid metal-silicate partitioning from 118 peer-reviewed publications. We applied various machine learning techniques to gain further insights into these partitioning equilibria and their dependencies. We performed a network analysis to investigate the relationship between experiments and partition coefficients, which enables visualizing gaps in the experimental dataset and biases related to varying experimental conditions and analytical setup. In addition, semi-empirical thermodynamic models are commonly used to extrapolate these chemical reactions to the wide range of pressure, temperature and compositional conditions of planetary differentiation. These models are based on linear regressions that assume continuous relationship between partition coefficients and experimental variables. Here, we considered random forest regressions, which are algorithms based on ensembles of decision trees and does not consider continuous effects of each variable. The application of this regression significantly improves the prediction of metal-silicate partitioning for several elements including Ni, Si and Cr. We will show how this new approach improves our understanding of elemental exchange between metal and silicate and their implications for the Earth’s core formation.

siderophile element↗

Algorithms for parallel flow solvers on message passing architectures

The purpose of this project has been to identify and test suitable technologies for implementation of fluid flow solvers -- possibly coupled with structures and heat equation solvers -- on MIMD parallel computers. In the course of this investigation much attention has been paid to efficient domain decomposition strategies for ADI-type algorithms. Multi-partitioning derives its efficiency from the assignment of several blocks of grid points to each processor in the parallel computer. A coarse-grain parallelism is obtained, and a near-perfect load balance results. In uni-partitioning every processor receives responsibility for exactly one block of grid points instead of several. This necessitates fine-grain pipelined program execution in order to obtain a reasonable load balance. Although fine-grain parallelism is less desirable on many systems, especially high-latency networks of workstations, uni-partition methods are still in wide use in production codes for flow problems. Consequently, it remains important to achieve good efficiency with this technique that has essentially been superseded by multi-partitioning for parallel ADI-type algorithms. Another reason for the concentration on improving the performance of pipeline methods is their applicability in other types of flow solver kernels with stronger implied data dependence. Analytical expressions can be derived for the size of the dynamic load imbalance incurred in traditional pipelines. From these it can be determined what is the optimal first-processor retardation that leads to the shortest total completion time for the pipeline process. Theoretical predictions of pipeline performance with and without optimization match experimental observations on the iPSC/860 very well. Analysis of pipeline performance also highlights the effect of uncareful grid partitioning in flow solvers that employ pipeline algorithms. If grid blocks at boundaries are not at least as large in the wall-normal direction as those immediately adjacent to them, then the first processor in the pipeline will receive a computational load that is less than that of subsequent processors, magnifying the pipeline slowdown effect. Extra compensation is needed for grid boundary effects, even if all grid blocks are equally sized.

Vanderwijngaart, Rob F.↗

Randomized Cholesky Preconditioning for Graph Partitioning Applications

A graph is a mathematical representation of a network; we say it consists of a set of vertices, which are connected by edges. Graphs have numerous applications in various fields, as they can model all sorts of connections, processes, or relations. For example, graphs can model intricate transit systems or the human nervous system. However, graphs that are large or complicated become difficult to analyze. This is why there is an increased interest in the area of graph partitioning, reducing the size of the graph into multiple partitions. For example, partitions of a graph representing a social network might help identify clusters of friends or colleagues. Graph partitioning is also a widely used approach to load balancing in parallel computing. The partitioning of a graph is extremely useful to decompose the graph into smaller parts and allow for easier analysis. There are different ways to solve graph partitioning problems. For this work, we focus on a spectral partitioning method which forms a partition based upon the eigenvectors of the graph Laplacian (details presented in Acer, et. al.). This method uses the LOBPCG algorithm to compute these eigenvectors. LOBPCG can be accelerated by an operator called a preconditioner. For this internship, we evaluate a randomized Cholesky (rchol) preconditioner for its effectiveness on graph partitioning problems with LOBPCG. We compare it with two standard preconditioners: Jacobi and Incomplete Cholesky (ichol). This research was conducted from August to December 2021 in conjunction with Sandia National Laboratories.

97 MATHEMATICS AND COMPUTING↗

Method for Constructing Composite Response Surfaces by Combining Neural Networks with Polynominal Interpolation or Estimation Techniques

A method and system for data modeling that incorporates the advantages of both traditional response surface methodology (RSM) and neural networks is disclosed. The invention partitions the parameters into a first set of s simple parameters, where observable data are expressible as low order polynomials, and c complex parameters that reflect more complicated variation of the observed data. Variation of the data with the simple parameters is modeled using polynomials; and variation of the data with the complex parameters at each vertex is analyzed using a neural network. Variations with the simple parameters and with the complex parameters are expressed using a first sequence of shape functions and a second sequence of neural network functions. The first and second sequences are multiplicatively combined to form a composite response surface, dependent upon the parameter values, that can be used to identify an accurate mode

Rai, Man Mohan↗

A novel approach to partitioning evapotranspiration into evaporation and transpiration in flooded ecosystems

Reliable partitioning of micrometeorologically measured evapotranspiration (ET) into evaporation (E) and transpiration (T) would greatly enhance our understanding of the water cycle and its response to climate change related shifts in local-to-regional climate conditions and rising global levels of vapor pressure deficit (VPD). While some methods on ET partitioning have been developed, their underlying assumptions make them difficult to apply more generally, especially in sites with large contributions of E. Here, we report a novel ET partitioning method using artificial neural networks (ANNs) in combination with a range of environmental input variables to predict daytime E from nighttime ET measurements. The study uses eddy covariance data from four restored wetlands in the Sacramento-San Joaquin Delta, California, USA, as well as leaf-level T data for validation. The four wetlands vary in their vegetation make-up and structure, representing a range of ET conditions. The ANNs were built with increasing complexity by adding the input variable that resulted in the next highest average value of model testing R 2 across all sites. The order of variable inclusion (and importance) was: VPD > gap-filled sensible heat flux (H_gf) > air temperature (T air ) > friction velocity (u * ) > other variables. The model using VPD, H_gf, T air , and u * showed the best performance during validation with independent data and had a mean testing R 2 value of 0.853 (averaged across all sites, range from 0.728 to 0.910). In comparison to other methods, our ANN method generated T/ET partitioning results which were more consistent with CO 2 exchange data especially for more heterogeneous sites with large E contributions. Further, our method improves the understanding of T/ET partitioning. While it may be particularly suited to flooded ecosystems, it can also improve T/ET partitioning in other systems, increasing our knowledge of the global water cycle and ecosystem functioning.

59 BASIC BIOLOGICAL SCIENCES↗

Decentralizing Network Inference Problems With Multiple-Description Fusion Estimation (MDFE)

Network inference (or tomography) problems, such as traffic matrix estimation or completion and link loss inference, have been studied rigorously in different networking applications. These problems are often posed as under-determined linear inverse (UDLI) problems and solved in a centralized manner, where all the measurements are collected at a central node, which then applies a variety of inference techniques to estimate the attributes of interest. This paper proposes a novel framework for decentralizing these large-scale under-determined network inference problems by intelligently partitioning it into smaller subproblems and solving them independently and in parallel. The resulting estimates, referred to as multiple descriptions, can then be fused together to compute the global estimate. We apply this Multiple Description and Fusion Estimation (MDFE) framework to three classical problems: traffic matrix estimation, traffic matrix completion, and loss inference. Using real topologies and traces, we demonstrate how MDFE can speed up computation while maintaining (even improving) the estimation accuracy and how it enhances robustness against noise and failures. In conclusion, we also show that our MDFE framework is compatible with a variety of existing inference techniques used to solve the UDLI problems.

97 MATHEMATICS AND COMPUTING↗

Electrostatic limits on charge selectivity in ultrahigh charge density polymer membranes

Ion-exchange membranes (IEMs) with ultrahigh charge densities offer the promise of enhanced ion transport for electrochemical technologies, yet the fundamental limits of this membrane design strategy are not yet understood. In this work, we present a systematic study of bis(1-vinyl-3-imidazolium) cross-linked polymer membranes with fixed charge contents ranging from 6 to 9 mol/L[dry polymer], synthesized to isolate the effects of charge density at constant membrane water content. While ionic conductivity increases monotonically with increasing charge density, a sharp decline in charge selectivity is observed for the most densely charged membranes, defying conventional expectations. Structural, thermal, and mechanical analyses reveal a critical onset of network disruption and anomalous ion partitioning behavior in these densely charged membranes. With proper consideration of cross-linker geometry, these results are interpreted using Manning's counter-ion condensation theory, which suggests that closely packed charged cross-linkers amplify inter-chain electrostatic interactions and trigger excess counter-ion condensation. Our findings suggest that, beyond a threshold spacing between fixed charges, increased functionalization may harm rather than help charge selectivity of IEMs.

36 MATERIALS SCIENCE↗