Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “linked data structures”

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 19 records

Global Trees: A Framework for Linked Data Structures on Distributed Memory Parallel Systems

This paper describes the Global Trees (GT) system that provides a multi-layered interface to a global address space view of distributed tree data structures, while providing scalable performance on distributed memory systems. The Global Trees system utilizes coarse-grained data movement to enhance locality and communication efficiency. We describe the design and implementation of GT, illustrate its use in the context of a gravitational simulation application, and provide experimental results that demonstrate the effectiveness of the approach. The key benefits of using this system include efficient sharedmemory style programming of distributed trees, tree-specific optimizations for data access and computation, and the ability to customize many aspects of GT to optimize application performance.

97 MATHEMATICS AND COMPUTING↗

Simit: A Language for Physical Simulation

With existing programming tools, writing high-performance simulation code is labor intensive and requires sacrificing readability and portability. Here, the alternative is to prototype simulations in a high-level language like Matlab, thereby sacrificing performance. The Matlab programming model naturally describes the behavior of an entire physical system using the language of linear algebra. However, simulations also manipulate individual geometric elements, which are best represented using linked data structures like meshes. Translating between the linked data structures and linear algebra comes at significant cost, both to the programmer and to the machine. High-performance implementations avoid the cost by rephrasing the computation in terms of linked or index data structures, leaving the code complicated and monolithic, often increasing its size by an order of magnitude. In this article, we present Simit, a new language for physical simulations that lets the programmer view the system both as a linked data structure in the form of a hypergraph and as a set of global vectors, matrices, and tensors depending on what is convenient at any given time. Simit provides a novel assembly construct that makes it conceptually easy and computationally efficient to move between the two abstractions. Using the information provided by the assembly construct, the compiler generates efficient in-place computation on the graph. We demonstrate that Simit is easy to use: a Simit program is typically shorter than a Matlab program; that it is high performance: a Simit program running sequentially on a CPU performs comparably to hand-optimized simulations; and that it is portable: Simit programs can be compiled for GPUs with no change to the program, delivering 4 to 20× speedups over our optimized CPU code.

97 MATHEMATICS AND COMPUTING↗

Local concurrent error detection and correction in data structures using virtual backpointers

A new technique, based on virtual backpointers, for local concurrent error detection and correction in linked data structures is presented. Two new data structures, the Virtual Double Linked List, and the B-tree with Virtual Backpointers, are described. For these structures, double errors can be detected in 0(1) time and errors detected during forward moves can be corrected in 0(1) time. The application of a concurrent auditor process to data structure error detection and correction is analyzed, and an implementation is described, to determine the effect on mean time to failure of a multi-user shared database system. The implementation utilizes a Sequent shared memory multiprocessor system operating on a shared databased of Virtual Double Linked Lists.

Li, C. C.↗

Inspection and Verification of Domain Models with PlanWorks and Aver

When developing a domain model, it seems natural to bring the traditional informal tools of inspection and verification, debuggers and automated test suites, to bear upon the problems that will inevitably arise. Debuggers that allow inspection of registers and memory and stepwise execution have been a staple of software development of all sorts from the very beginning. Automated testing has repeatedly proven its considerable worth, to the extent that an entire design philosophy (Test Driven Development) has been developed around the writing of tests. Unfortunately, while not entirely without their uses, the limitations of these tools and the nature of the complexity of models and the underlying planning systems make the diagnosis of certain classes of problems and the verification of their solutions difficult or impossible. Debuggers provide a good local view of executing code, allowing a fine-grained look at algorithms and data. This view is, however, usually only at the level of the current scope in the implementation language, and the data-inspection capabilities of most debuggers usually consist of on-line print statements. More modem graphical debuggers offer a sort of tree view of data structures, but even this is too low-level and is often inappropriate for the kinds of structures created by planning systems. For instance, god or constraint networks are at best awkward when visualized as trees. Any any non-structural link between data structures, as through a lookup table, isn't captured at all. Further, while debuggers have powerful breakpointing facilities that are suitable for finding specific algorithmic errors, they have little use in the diagnosis of modeling errors.

Bedrax-Weiss, Tania↗

Scaling Irregular Applications through Data Aggregation and Software Multithreading

Bioinformatics, data analytics, semantic databases, knowledge discovery are emerging high performance application areas that exploit dynamic, linked data structures such as graphs, unbalanced trees or unstructured grids. These data structures usually are very large, requiring significantly more memory than available on single shared memory systems. Additionally, these data structures are difficult to partition on distributed memory systems. They also present poor spatial and temporal locality, thus generating unpredictable memory and network accesses. The Partitioned Global Address Space (PGAS) programming model seems suitable for these applications, because it allows using a shared memory abstraction across distributed-memory clusters. However, current PGAS languages and libraries are built to target regular remote data accesses and block transfers. Furthermore, they usually rely on the Single Program Multiple Data (SPMD) parallel control model, which is not well suited to the fine grained, dynamic and unbalanced parallelism of irregular applications. In this paper we present {\bf GMT} (Global Memory and Threading library), a custom runtime library that enables efficient execution of irregular applications on commodity clusters. GMT integrates a PGAS data substrate with simple fork/join parallelism and provides automatic load balancing on a per node basis. It implements multi-level aggregation and lightweight multithreading to maximize memory and network bandwidth with fine-grained data accesses and tolerate long data access latencies. A key innovation in the GMT runtime is its thread specialization (workers, helpers and communication threads) that realize the overall functionality. We compare our approach with other PGAS models, such as UPC running using GASNet, and hand-optimized MPI code on a set of typical large-scale irregular applications, demonstrating speedups of an order of magnitude.

Aggregation↗

Proving Correctness for Pointer Programs in a Verifying Compiler

This research describes a component-based approach to proving the correctness of programs involving pointer behavior. The approach supports modular reasoning and is designed to be used within the larger context of a verifying compiler. The approach consists of two parts. When a system component requires the direct manipulation of pointer operations in its implementation, we implement it using a built-in component specifically designed to capture the functional and performance behavior of pointers. When a system component requires pointer behavior via a linked data structure, we ensure that the complexities of the pointer operations are encapsulated within the data structure and are hidden to the client component. In this way, programs that rely on pointers can be verified modularly, without requiring special rules for pointers. The ultimate objective of a verifying compiler is to prove-with as little human intervention as possible-that proposed program code is correct with respect to a full behavioral specification. Full verification for software is especially important for an agency like NASA that is routinely involved in the development of mission critical systems.

Kulczycki, Gregory↗

Modeling the Formation and Eruption of Coronal Structures by Linking Data-Driven Magnetofrictional and MHD Simulations for AR 12673

Context .The data-driven and time-dependent modeling of coronal magnetic fields is crucial for understanding solar eruptions. These efforts are complicated by the challenges of finding a balance between physical realism and computing efficiency. One possible technique is to couple two modeling approaches. Aims . Our aim here is to showcase our progress in using time-dependent magnetofrictional model (TMFM) results as input to dynamical magnetohydrodynamic (MHD) simulations. However, due to the different evolution processes in these two models, using TMFM snapshots in an MHD simulation is nontrivial. We address these issues, both physically and numerically, discuss the incompatibility of the TMFM output to serve as the initial condition in MHD simulations, and show our methods of mitigating this. The evolution of the flux systems and the cause of the eruption are investigated. Methods . TMFM is a prevalent approach that has proven to be a very useful tool in the study of the formation of unstable structures in the solar corona. In particular, it is capable of incorporating observational data as initial and boundary conditions and requires shorter computational time compared to MHD simulations. To leverage the efficiency of data-driven TMFM and also to simulate eruptive events in the MHD framework, one can apply TMFM up to a certain time before the expected eruption(s) and then proceed with the simulation in the full or ideal MHD regime in order to more accurately capture the eruption process. Results . We show the results of a benchmark test case with a linked TMFM and MHD simulation to study the evolution of NOAA active region 12673. A rise of a twisted flux bundle through the MHD simulation domain is observed, but we find that the rate of the rise and the altitude reached depends on the time of the TMFM snapshot that was used to initialize the MHD simulation and the helicity injected into the system. The analysis suggested that torus instability and slip-running reconnection could play an important role in the eruption. Conclusions . The results show that the linkage of TMFM and zero-β MHD models can be successfully used to model the eruptive coronal magnetic fields.

F. Daei↗

Link prediction on evolving graphs using matrix and tensor factorizations.

The data in many disciplines such as social networks, web analysis, etc. is link-based, and the link structure can be exploited for many different data mining tasks. In this paper, we consider the problem of temporal link prediction: Given link data for time periods 1 through T, can we predict the links in time period T + 1? Specifically, we look at bipartite graphs changing over time and consider matrix- and tensor-based methods for predicting links. We present a weight-based method for collapsing multi-year data into a single matrix. We show how the well-known Katz method for link prediction can be extended to bipartite graphs and, moreover, approximated in a scalable way using a truncated singular value decomposition. Using a CANDECOMP/PARAFAC tensor decomposition of the data, we illustrate the usefulness of exploiting the natural three-dimensional structure of temporal link data. Through several numerical experiments, we demonstrate that both matrix- and tensor-based techniques are effective for temporal link prediction despite the inherent difficulty of the problem.

99 GENERAL AND MISCELLANEOUS↗

Collaborative Systems Engineering in the Ascent Abort-2 Crew Module/Separation Ring Project

Generally speaking, systems engineering (SE) tool-sets face a dilemma balancing power and accessibility. High-powered SE tools (MagicDraw, Cradle, Core, etc.) tend to be specialized and are available only to highly trained Systems Engineers, and/or through the use of a 'back room' developer team making the output products available to the broader team. On the other hand, highly accessible tools (MS Word, Excel, etc.) do not have the power to implement SE in a rigorous manner. NASA has to test all aspects of the new human-rated Orion Multi-Purpose Crew Vehicle spacecraft prior to its first crewed mission. The test program includes uncrewed launch abort flight tests to demonstrate the capability to save the crew in the event that a launch failure occurs. Orion's second abort flight test will be a low-altitude flight test known as "Ascent Abort 2 (AA-2)." This test is currently scheduled to be carried out at Cape Canaveral Air Force Station's Space Launch Complex 46 (SLC-46) in Florida in 2019. NASA's in-house AA-2 Crew Module and Separation Ring (CSR) Team is producing the crew module and separation ring. Operating jointly as both an Advanced Exploration Systems (AES) Project and an Orion Project, the CSR project charter includes development of innovative, streamlined and generally more efficient practices for creation of flight hardware and software. One result of this tasking has been development of a collaborative and data-centric systems engineering environment within the team's shared web environment (Microsoft SharePoint). Through the use of built-in, 'out of the box capabilities' present in MS SharePoint, the CSR Systems Engineering team has created (with some limited developer support) a data-centric architecture for the project's SE implementation, including functional and interface analysis, requirements development and management, risk management, verification planning and management, test results, and end item management. Data elements are linked between data structures so as to define and control relationships between item types, link requirements to parents and children, and link tests to the requirements that they verify. The overall project team integration is increased by also linking SE content to project management content over the project life cycle, including team communication, action items, configuration management, decisional and meeting materials, and life cycle reviews. This presentation will provide an overview of the collaborative SE environment, showing how it provides the power for a number of SE tasks while still providing the accessibility and transparency to allow the full project team to collaborate and succeed. Given the project phase, we'll be able to present a nearly full lifecycle discussion, from concept through verification and approaching delivery.

Systems Engineering environments↗

Protocol Sensing Across Multiple Space Missions

In this work, we present sensing performance using an architecture for a reconfigurable protocol chip for spacebased applications. Toward utilizing the IP packet architecture, utilizing data link layer framing structures for multiplexed data on a channel are the targeted application considered for demonstration purposes. Specifically, we examine three common framing standards and present the sensing performance of these standards and their relative de-correlation metrics. Some analysis is performed to investigate the impact of lossy links and on the number of packets required to perform a decision with some probability. Finally, we present results on a demonstration platform that integrated reconfigurable sensing technology into the Ground Station Interface Device (GRID) for End-to-End IP demonstrations in space.

Ground Station Interface Device (GRID)↗

Reconfigurable Protocol Sensing in an End-to-End Demonstration

In this work, we present sensing performance using an architecture for a reconfigurable protocol chip for spacebased applications. Toward utilizing the IP packet architecture, utilizing data link layer framing structures for multiplexed data on a channel are the targeted application considered for demonstration purposes. Specifically, we examine three common framing standards and present the sensing performance of these standards and their relative de-correlation metrics. Some analysis is performed to investigate the impact of lossy links. Finally, we present results on a demonstration platform that integrated reconfigurable sensing technology into the Ground Station Interface Device (GRID) for End-to-End IP demonstrations in space.

space based applications↗

Dynamic mesh adaption for triangular and tetrahedral grids

The following topics are discussed: requirements for dynamic mesh adaption; linked-list data structure; edge-based data structure; adaptive-grid data structure; three types of element subdivision; mesh refinement; mesh coarsening; additional constraints for coarsening; anisotropic error indicator for edges; unstructured-grid Euler solver; inviscid 3-D wing; and mesh quality for solution-adaptive grids. The discussion is presented in viewgraph form.

Rupak Biswas↗

[Development and Use of Hidrosig]

The NASA portion of this joint NSF-NASA grant consists of objective 2 and a part of objective 3. A major effort was made on objective 2, and it consisted of developing a numerical GIs environment called Hidrosig. This major research tool is being developed by the University of Colorado for conducting river-network-based scaling analyses of coupled water-energy-landform-vegetation interactions including water and energy balances, and floods and droughts, at multiple space-time scales.Objective 2: To analyze the relevant remotely sensed products from satellites, radars and ground measurements to compute the transported water mass for each complete Strahler stream using an 'assimilated water balance equation' at daily and other appropriate time scales. This objective requires analysis of concurrent data sets for Precipitation (PPT), Evapotranspiration (ET) and stream flows (Q) on river networks. To solve this major problem, our decision was to develop Hidrosig, a new Open-Source GIs software. A research group in Colombia, South America, developed the first version of Hidrosig, and Ricardo Mantilla was part of this effort as an undergraduate student before joining the graduate program at the University of Colorado in 2001. Hydrosig automatically extracts river networks from large DEMs and creates a "link-based" data structure, which is required to conduct a variety of analyses under objective 2. It is programmed in Java, which is a multi-platform programming language freely distributed by SUN under a GPL license. Some existent commercial tools like Arc-Info, RiverTools and others are not suitable for our purpose for two reasons. First, the source code is not available that is needed to build on the network data structure. Second, these tools use different programming languages that are not most versatile for our purposes. For example, RiverTools uses an IDL platform that is not very efficient for organizing diverse data sets on river networks. Hidrosig establishes a clear data organization framework that allows a simultaneous analysis of spatial fields along river network structures involving Horton- Strahler framework. Software tools for network extraction from DEMs and network-based analysis of geomorphologic and topologic variables were developed during the first year and a part of second year.

Gupta, Vijay K.↗

Local concurrent error detection and correction in data structures using virtual backpointers

A new technique, based on virtual backpointers, for local concurrent error detection and correction in linked data strutures is presented. Two new data structures, the Virtual Double Linked List, and the B-tree with Virtual Backpointers, are described. For these structures, double errors can be detected in 0(1) time and errors detected during forward moves can be corrected in 0(1) time. The application of a concurrent auditor process to data structure error detection and correction is analyzed, and an implementation is described, to determine the effect on mean time to failure of a multi-user shared database system. The implementation utilizes a Sequent shared memory multiprocessor system operating on a shared database of Virtual Double Linked Lists.

Li, Chung-Chi Jim↗

Adjustable lossless image compression based on a natural splitting of an image into drawing, shading, and fine-grained components

The compression, or efficient coding, of single band or multispectral still images is becoming an increasingly important topic. While lossy compression approaches can produce reconstructions that are visually close to the original, many scientific and engineering applications require exact (lossless) reconstructions. However, the most popular and efficient lossless compression techniques do not fully exploit the two-dimensional structural links existing in the image data. We describe here a general approach to lossless data compression that effectively exploits two-dimensional structural links of any length. After describing in detail two main variants on this scheme, we discuss experimental results.

Novik, Dmitry A.↗

Geocoded data structures and their applications to Earth science investigations

A geocoded data structure is a means for digitally representing a geographically referenced map or image. The characteristics of representative cellular, linked, and hybrid geocoded data structures are reviewed. The data processing requirements of Earth science projects at the Goddard Space Flight Center and the basic tools of geographic data processing are described. Specific ways that new geocoded data structures can be used to adapt these tools to scientists' needs are presented. These include: expanding analysis and modeling capabilities; simplifying the merging of data sets from diverse sources; and saving computer storage space.

Goldberg, M.↗

Developing a distributed data dictionary service

This paper will explore the use of the Lightweight Directory Access Protocol (LDAP) using the ISO 11179 Data Dictionary Schema as a mechanism for standardizing the structure and communication links between data dictionaries.

datasets data dictionaries Lightweight Directory A↗