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 163 records · Page 9

Correctness Proof of a Self-Stabilizing Distributed Clock Synchronization Protocol for Arbitrary Digraphs

This report presents a deductive proof of a self-stabilizing distributed clock synchronization protocol. It is focused on the distributed clock synchronization of an arbitrary, non-partitioned digraph ranging from fully connected to 1-connected networks of nodes while allowing for differences in the network elements. This protocol does not rely on assumptions about the initial state of the system, and no central clock or a centrally generated signal, pulse, or message is used. Nodes are anonymous, i.e., they do not have unique identities. There is no theoretical limit on the maximum number of participating nodes. The only constraint on the behavior of the node is that the interactions with other nodes are restricted to defined links and interfaces. We present a deductive proof of the correctness of the protocol as it applies to the networks with unidirectional and bidirectional links. We also confirm the claims of determinism and linear convergence.

Malekpour, Mahyar R.↗

A Self-Stabilizing Synchronization Protocol for Arbitrary Digraphs

This paper presents a self-stabilizing distributed clock synchronization protocol in the absence of faults in the system. It is focused on the distributed clock synchronization of an arbitrary, non-partitioned digraph ranging from fully connected to 1-connected networks of nodes while allowing for differences in the network elements. This protocol does not rely on assumptions about the initial state of the system, other than the presence of at least one node, and no central clock or a centrally generated signal, pulse, or message is used. Nodes are anonymous, i.e., they do not have unique identities. There is no theoretical limit on the maximum number of participating nodes. The only constraint on the behavior of the node is that the interactions with other nodes are restricted to defined links and interfaces. This protocol deterministically converges within a time bound that is a linear function of the self-stabilization period. We present an outline of a deductive proof of the correctness of the protocol. A bounded model of the protocol was mechanically verified for a variety of topologies. Results of the mechanical proof of the correctness of the protocol are provided. The model checking results have verified the correctness of the protocol as they apply to the networks with unidirectional and bidirectional links. In addition, the results confirm the claims of determinism and linear convergence. As a result, we conjecture that the protocol solves the general case of this problem. We also present several variations of the protocol and discuss that this synchronization protocol is indeed an emergent system.

Malekpour, Mahyar R.↗

Model Checking A Self-Stabilizing Synchronization Protocol for Arbitrary Digraphs

This report presents the mechanical verification of a self-stabilizing distributed clock synchronization protocol for arbitrary digraphs in the absence of faults. This protocol does not rely on assumptions about the initial state of the system, other than the presence of at least one node, and no central clock or a centrally generated signal, pulse, or message is used. The system under study is an arbitrary, non-partitioned digraph ranging from fully connected to 1-connected networks of nodes while allowing for differences in the network elements. Nodes are anonymous, i.e., they do not have unique identities. There is no theoretical limit on the maximum number of participating nodes. The only constraint on the behavior of the node is that the interactions with other nodes are restricted to defined links and interfaces. This protocol deterministically converges within a time bound that is a linear function of the self-stabilization period. A bounded model of the protocol is verified using the Symbolic Model Verifier (SMV) for a subset of digraphs. Modeling challenges of the protocol and the system are addressed. The model checking effort is focused on verifying correctness of the bounded model of the protocol as well as confirmation of claims of determinism and linear convergence with respect to the self-stabilization period.

Malekpour, Mahyar R.↗

Fault-Tolerant Self-Stabilizing Distributed Clock Synchronization Protocol for Arbitrary Digraphs

A self-stabilizing network in the form of an arbitrary, non-partitioned digraph includes K nodes having a synchronizer executing a protocol. K-1 monitors of each node may receive a Sync message transmitted from a directly connected node. When the Sync message is received, the logical clock value for the receiving node is set to between 0 and a communication latency value (gamma) if the clock value is less than a minimum event-response delay (D). A new Sync message is also transmitted to any directly connected nodes if the clock value is greater than or equal to both D and a graph threshold (T(sub S)). When the Sync message is not received the synchronizer increments the clock value if the clock value is less than a resynchronization period (P), and resets the clock value and transmits a new Sync message to all directly connected nodes when the clock value equals or exceeds P.

Malekpour, Mahyar R.↗

ADVERT: An Asynchronous Runtime for Fine-Grained Network Systems

The Data Vortex Network, a novel fine-grained high-radix interconnect, provides the performance and injection rates required by the fine-grained, unpredictable communication patterns of irregular applications. This paper presents ADVERT, an asynchronous runtime system that provides performance and productivity for the fine-grained Data Vortex Network. ADVERT integrates a lightweight memory manager (DVMem) for the user accessible SRAM integrated in the network interface, and a communication library (DVComm) that implements active messaging primitives (remote execution, and, based on this, get and put routines). ADVERT hides the complexity of controlling all the network hardware features through the low-level Data Vortex programming interface, while providing comparable performance. We discuss ADVERT's design and present an analysis of three exemplar irregular kernels (Triangle Count, Page Rank, and GUPS). ADVERT can provide the communication substrate required to build emerging higher level asynchronous many tasking runtimes and partitioned global address space libraries on top of the Data Vortex Network.

Friese, Ryan D.↗

Exploiting Geometric Partitioning in Task Mapping for Parallel Computes

We present a new method for mapping applications' MPI tasks to cores of a parallel computer such that applications' communication time is reduced. We address the case of sparse node allocation, where the nodes assigned to a job are not necessarily located in a contiguous block nor within close proximity to each other in the network, although our methods generalize to contiguous allocations as well. The goal is to assign tasks to cores so that interdependent tasks are performed by "nearby' cores, thus lowering the distance messages must travel, the amount of congestion in the network, and the overall cost of communication. Our new method applies a geometric partitioning algorithm to both the tasks and the processors, and assigns task parts to the corresponding processor parts. We also present a number of algorithmic optimizations that exploit specific features of the network or application. We show that, for the structured finite difference mini-application MiniGhost, our mapping methods reduced communication time up to 75% relative to MiniGhost's default mapping on 128K cores of a Cray XK7 with sparse allocation. For the atmospheric modeling code E3SM/HOMME, our methods reduced communication time up to 31% on 32K cores of an IBM BlueGene/Q with contiguous allocation.

97 MATHEMATICS AND COMPUTING↗

UCX: An Open Source Framework for HPC Network APIs and Beyond, In: 2015 IEEE 23rd Annual Symposium on High-Performance Interconnects

This paper presents Unified Communication X (UCX), a set of network APIs and their implementations for high throughput computing. UCX comes from the combined effort of national laboratories, industry, and academia to design and implement a high-performing and highly-scalable network stack for next generation applications and systems. UCX design provides the ability to tailor its APIs and network functionality to suit a wide variety of application domains and hardware. We envision these APIs to satisfy the networking needs of many programming models such as Message Passing Interface (MPI), OpenSHMEM, Partitioned Global Address Space (PGAS) languages, task-based paradigms and I/O bound applications. To evaluate the design we implement the APIs and protocols, and measure the performance of overhead-critical network primitives fundamental for implementing many parallel programming models and system libraries. Our results show that the latency, bandwidth, and message rate achieved by the portable UCX prototype is very close to that of the underlying driver. With UCX, we achieved a message exchange latency of 0.89 us, a bandwidth of 6138.5 MB/s, and a message rate of 14 million messages per second. As far as we know, this is the highest bandwidth and message rate achieved by any network stack (publicly known) on this hardware.

Computer Science↗

High-performance parallel analysis of coupled problems for aircraft propulsion

This research program deals with the application of high-performance computing methods to the numerical simulation of complete jet engines. The program was initiated in 1993 by applying two-dimensional parallel aeroelastic codes to the interior gas flow problem of a by-pass jet engine. The fluid mesh generation, domain decomposition and solution capabilities were successfully tested. Attention was then focused on methodology for the partitioned analysis of the interaction of the gas flow with a flexible structure and with the fluid mesh motion driven by these structural displacements. The latter is treated by an ALE technique that models the fluid mesh motion as that of a fictitious mechanical network laid along the edges of near-field fluid elements. New partitioned analysis procedures to treat this coupled 3-component problem were developed in 1994. These procedures involved delayed corrections and subcycling, and have been successfully tested on several massively parallel computers. For the global steady-state axisymmetric analysis of a complete engine we have decided to use the NASA-sponsored ENG10 program, which uses a regular FV-multiblock-grid discretization in conjunction with circumferential averaging to include effects of blade forces, loss, combustor heat addition, blockage, bleeds and convective mixing. A load-balancing preprocessor for parallel versions of ENG10 has been developed. It is planned to use the steady-state global solution provided by ENG10 as input to a localized three-dimensional FSI analysis for engine regions where aeroelastic effects may be important.

Felippa, C. A.↗

High-Performance Parallel Analysis of Coupled Problems for Aircraft Propulsion

This research program dealt with the application of high-performance computing methods to the numerical simulation of complete jet engines. The program was initiated in January 1993 by applying two-dimensional parallel aeroelastic codes to the interior gas flow problem of a bypass jet engine. The fluid mesh generation, domain decomposition and solution capabilities were successfully tested. Attention was then focused on methodology for the partitioned analysis of the interaction of the gas flow with a flexible structure and with the fluid mesh motion driven by these structural displacements. The latter is treated by a ALE technique that models the fluid mesh motion as that of a fictitious mechanical network laid along the edges of near-field fluid elements. New partitioned analysis procedures to treat this coupled three-component problem were developed during 1994 and 1995. These procedures involved delayed corrections and subcycling, and have been successfully tested on several massively parallel computers, including the iPSC-860, Paragon XP/S and the IBM SP2. For the global steady-state axisymmetric analysis of a complete engine we have decided to use the NASA-sponsored ENG10 program, which uses a regular FV-multiblock-grid discretization in conjunction with circumferential averaging to include effects of blade forces, loss, combustor heat addition, blockage, bleeds and convective mixing. A load-balancing preprocessor tor parallel versions of ENG10 was developed. During 1995 and 1996 we developed the capability tor the first full 3D aeroelastic simulation of a multirow engine stage. This capability was tested on the IBM SP2 parallel supercomputer at NASA Ames. Benchmark results were presented at the 1196 Computational Aeroscience meeting.

Felippa, C. A.↗

Irradiation of linear polyethylene - Partitioning between sol and gel.

Investigation of the importance of chain-scission processes and of the applicability of the general theory of network formation to polyethylene with respect to critical conditions for gelation, using molecular weight fractions of linear polyethylene irradiated at 133 C. The partitioning between sol and gel was found to adhere to the theory just beyond the gel point. Deviations from theory occurred as the irradiation dosage was increased. It was concluded that main-chain scission at the temperatures concerned is not a significant process.

Rijke, A. M.↗

Ecosystems and Networks Integrated with Genes and Molecular Assemblies (ENIGMA) (Final Scientific/Technical Report, Subcontract Award No. 6953691)

The overarching objective the Baliga lab is to develop a mechanistic understanding of the field relevant metabolic processes underlying community partitioning of respiration pathways and physiological state shifts. In order to dissect how environmental perturbations influence microbial regulatory networks, we have constructed data-driven models that capture the dynamic interplay between abiotic and biotic factors during laboratory simulations. Specifically, we have developed multiple computational models (i.e., cMonkey2, EGRIN 2.0, and multiple genome-scale metabolic models) connecting environmental influence to genome-encoded regulatory programs. In addition, we have generated new tools such as Live Anaerobic Cell Sorting (LAnCS) and Fluidized Bed Reactors (FBRs) to investigate the dynamics of community partitioning of metabolic processes supporting sulfate or nitrate respiration, which are two critical activities observed from the field site at Oak Ridge National Labs (ORNL). This framework of connecting field phenomena with laboratory simulations and computational modeling has created the Environmental Simulations and Modelling (EnvSim) campaign within ENIGMA. The campaign, which spans multiple laboratories across ENIGMA and is led by the Baliga group, has established synthetic communities (SynComs) to discover, characterize, and dissect key microbial processes relevant to field observations, such as emissions of the greenhouse gas nitrous oxide (N 2 O). For example, the EnvSim campaign so far has deduced four potential mechanisms that may account for the N 2 O emissions at the FRC and are currently being investigated by labs across ENIGMA. Denitrification may be driven by complete denitrifiers, however, their NosZ enzymes, which catalyze the final step in denitrification by converting N 2 O to N 2 , may be sensitive at a lower pH. Additionally, the denitrification process could be partitioned among organisms and some may have pH-sensitive NosZ genes. Another factor contributing to variable N 2 O emissions relates to the metal co-factors involved in the denitrification pathway. For instance, excess Cu, Al, Mn, U, Ni, Co, Cu, and/or Cd may have inhibitory effects on multiple enzymatic steps during denitrification, while the enzymatic production of nitrite, the precursor of N 2 O, can be limited by the essential metal Mo. Lastly, abiotic production of N 2 O may occur as a result of chemodenitrification, in which metals like Fe, Mn, and some organic compounds can drive redox reactions that convert nitrogen cycle intermediates to N 2 O under the right conditions. Current investigations and analyses have generated multiple transcriptomic profiles aiding the refinement of new metabolic and gene regulatory network model for our denitrifying SynCom. In sum, the previous funding cycle has generated 33 peer-reviewed publications spanning predictive network biology to co-operativity of mutualistic interspecies interactions of evolved communities. Our integration of multiple omics datasets and the development of new network modelling tools has revealed important insights that can explain field observed phenomenon and generated new hypotheses to be investigated in the field.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Quantifying Message Aggregation Optimisations for Energy Savings in PGAS Models

Upon breaking past the exascale barrier, HPC systems are facing their greatest challenge yet - a power wall that must be addressed through new methods in both hardware and software. While energy costs are becoming a major issue at all levels, of particular concern is that of the network, as the relative cost of moving data is increasing faster than ever. The partitioned global address space (PGAS) model is critical within certain HPC domains, but is known to suffer from the small message problem, where irregular many-to-many access patterns result in congesting the network with excessive numbers of small messages. To address this, the conveyor aggregation library was developed to defer individual messages and group them for subsequent bulk processing. In this paper, we investigate its impact on energy use related to the network, with a focus on the Slingshot 11 interconnect. We will demonstrate that this strategy is not only highly performant, but also crucial to reducing energy footprints to remain within target power envelopes.

Welch, Aaron [ORNL]↗

A learning-based measurement framework for traffic matrix inference in software defined networks

Here, we propose an intelligent framework for Traffic Matrix (TM) inference in Software Defined Networks (SDN) where the Ternary Content Addressable Memory (TCAM) entries of switches are partitioned into two parts to: (1) effectively aggregate part of incoming flows for aggregate measurements, and (2) de-aggregate and directly measure the most informative flows for per-flow measurements. These measurements are then processed to effectively estimate the size of network flows. Under hard resource constraints of limited TCAM sizes, we show how to design the optimal and efficient-compressed flow aggregation matrices. We propose an optimal Multi-Armed Bandit (MAB) based algorithm to adaptively measure the most rewarding flows. We evaluate the performance of our framework using real traffic traces from different network environments and by considering two main applications: TM estimation and Heavy Hitter (HH) detection. Moreover, we have implemented a prototype of our framework in Mininet to demonstrate its effectiveness.

42 ENGINEERING↗

OpenSHMEM Reference Implementation using UCCS-uGNI Transport Layer. In: PGAS '14 Proceedings of the 8th International Conference on Partitioned Global Address Space Programming Models, Article No. 18

OpenSHMEM is a library interface implementation and specification that enables the implementation of the Partitioned Global Address Space (PGAS) model. It exports modern RDMA network functionality and communication semantics to applications very efficiently. There are many closed source implementations of OpenSHMEM for modern RDMA interconnects such as InfiniBand and Cray's Gemini and Aries. Given the important role that Cray systems play in HPC, in this paper, we present an open source implementation of OpenSHMEM for Cray XE/XK/XC systems. To implement OpenSHMEM, we use the uGNI interface. uGNI is a generic interface that is designed for multiple programming models. The interface fits well the goal of UCCS. Having OpenSHMEM with UCCS-uGNI allows usage of the same implementation over multiple interconnects. This also translates into many advantages that come with common code such as resource sharing, increasing productivity because of less code maintenance, etc. Preliminary results show that OpenSHMEM-UCCS performs comparable to state-of-the-art Cray SHMEM for Put, Get, and AMO operations.

Janjusic, Tomislav↗

Reliability Modeling of Microelectromechanical Systems Using Neural Networks

Microelectromechanical systems (MEMS) are a broad and rapidly expanding field that is currently receiving a great deal of attention because of the potential to significantly improve the ability to sense, analyze, and control a variety of processes, such as heating and ventilation systems, automobiles, medicine, aeronautical flight, military surveillance, weather forecasting, and space exploration. MEMS are very small and are a blend of electrical and mechanical components, with electrical and mechanical systems on one chip. This research establishes reliability estimation and prediction for MEMS devices at the conceptual design phase using neural networks. At the conceptual design phase, before devices are built and tested, traditional methods of quantifying reliability are inadequate because the device is not in existence and cannot be tested to establish the reliability distributions. A novel approach using neural networks is created to predict the overall reliability of a MEMS device based on its components and each component's attributes. The methodology begins with collecting attribute data (fabrication process, physical specifications, operating environment, property characteristics, packaging, etc.) and reliability data for many types of microengines. The data are partitioned into training data (the majority) and validation data (the remainder). A neural network is applied to the training data (both attribute and reliability); the attributes become the system inputs and reliability data (cycles to failure), the system output. After the neural network is trained with sufficient data. the validation data are used to verify the neural networks provided accurate reliability estimates. Now, the reliability of a new proposed MEMS device can be estimated by using the appropriate trained neural networks developed in this work.

Perera. J. Sebastian↗

Patch-based image segmentation of satellite imagery using minimum spanning tree construction

We present a method for hierarchical image segmentation and feature extraction. This method builds upon the combination of the detection of image spectral discontinuities using Canny edge detection and the image Laplacian, followed by the construction of a hierarchy of segmented images of successively reduced levels of details. These images are represented as sets of polygonized pixel patches (polygons) attributed with spectral and structural characteristics. This hierarchy forms the basis for object-oriented image analysis. To build fine level-of-detail representation of the original image, seed partitions (polygons) are built upon a triangular mesh composed of irregular sized triangles, whose spatial arrangement is adapted to the image content. This is achieved by building the triangular mesh on the top of the detected spectral discontinuities that form a network of constraints for the Delaunay triangulation. A polygonized image is represented as a spatial network in the form of a graph with vertices which correspond to the polygonal partitions and graph edges reflecting pairwise partitions relations. Image graph partitioning is based on the iterative graph oontraction using Boruvka's Minimum Spanning Tree algorithm. An important characteristic of the approach is that the agglomeration of partitions is constrained by the detected spectral discontinuities; thus the shapes of agglomerated partitions are more likely to correspond to the outlines of real-world objects.

97 MATHEMATICS AND COMPUTING↗

Misfit dislocation networks in semi-coherent miscible phase boundaries: An example for U–Zr interfaces

Semi-coherent cube-on-cube miscible U–Zr interfaces were studied using molecular dynamics simulations. The misfit accommodation of such semi-coherent phase boundaries was characterized by a two-dimensional dislocation network model utilizing a combination of theoretical predictions and analysis of the atomic system. The dislocation networks were discussed for various stacking orientation of the adjoining phases in terms of the composition of the dislocation sets, the partitioning between edge and screw components and the associated residual elastic fields. Furthermore, these analyses showed that the patterning of the network of dislocations forming these phase boundaries results from the competition between a structurally-driven process (i.e., function of the lattice misfit) and a chemically-driven process (i.e., due to the miscibility between U and Zr).

36 MATERIALS SCIENCE↗

A Fast and Scalable Genetic Algorithm-Based Approach for Planning of Microgrids in Distribution Networks

As a result of climate change, extreme weather events are occurring more frequently and with increasing impact. This trend poses a significant challenge for distribution utilities and system operators to ensure that there is uninterrupted power supply to critical loads in their networks; thus, the level of proactive preparation of the distribution system to be able to handle severe impacts of extreme weather events represents the system's resilience. One method that distribution system planners can use to prepare for future extreme events is to plan multiple microgrids which can use local generation as much as possible to supply critical loads. But partitioning an existing distribution system such that multiple feasible islands are planned and which are capable of supporting critical loads is still challenging for distribution systems - first, because of the size of the network graph partitioning problem and, second, because of the difficulty in properly formulating the desired attributes of such islands or microgrids. Therefore, this paper presents a genetic algorithm based approach that facilitates incorporating multiple objectives for grid partitioning by formulating two types of problems - node allocation and edge elimination - and it considers multiple topological and resilience-enhancing objectives. The performance of the proposed genetic algorithm-based approach is numerically evaluated on multiple test systems as well as on a real distribution feeder in Colorado, United States.

genetic algorithm↗