Search NASA⌕ Search

SEARCH · Search NASA

Results for “Hashing”

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

Segmentation of computer-classified Landsat multispectral scanner data into spatially-connected regions of elk habitat components

Segmentation of computer-classified Landsat multispectral data into spatially-connected regions of ground cover is described. Sorting and hash addressing, techniques commonly used for ordering and searching data records keyed by attributes, are the basis for the region identification and extraction. An example based on the use of spatial regions for evaluating elk habitat components is outlined.

Murray, R.↗

Cross-fertilization between connectionist networks and highly parallel architectures

The theoretical and practical connections between connectionist schemes such as neural-network computers and traditional symbolic processing architectures involving a high degree of parallelism are explored, reviewing the results of recent investigations. Topics addressed include data flow, data structure, and control flow; conventional pointers; associative addressing; hashing and reduced representations; the problem of binding values to variables; and levels of parallelism. It is concluded that connectionism is more closely related to traditional computer science and technology than is generally admitted; more cooperation between followers of the two approaches is recommended.

Barnden, John↗

Massively parallel algorithms for trace-driven cache simulations

Trace driven cache simulation is central to computer design. A trace is a very long sequence of reference lines from main memory. At the t(exp th) instant, reference x sub t is hashed into a set of cache locations, the contents of which are then compared with x sub t. If at the t sup th instant x sub t is not present in the cache, then it is said to be a miss, and is loaded into the cache set, possibly forcing the replacement of some other memory line, and making x sub t present for the (t+1) sup st instant. The problem of parallel simulation of a subtrace of N references directed to a C line cache set is considered, with the aim of determining which references are misses and related statistics. A simulation method is presented for the Least Recently Used (LRU) policy, which regradless of the set size C runs in time O(log N) using N processors on the exclusive read, exclusive write (EREW) parallel model. A simpler LRU simulation algorithm is given that runs in O(C log N) time using N/log N processors. Timings are presented of the second algorithm's implementation on the MasPar MP-1, a machine with 16384 processors. A broad class of reference based line replacement policies are considered, which includes LRU as well as the Least Frequently Used and Random replacement policies. A simulation method is presented for any such policy that on any trace of length N directed to a C line set runs in the O(C log N) time with high probability using N processors on the EREW model. The algorithms are simple, have very little space overhead, and are well suited for SIMD implementation.

Nicol, David M.↗

Adding run history to CLIPS

To debug a C Language Integrated Production System (CLIPS) program, certain 'historical' information about a run is needed. It would be convenient for system builders to have the capability to request such information. We will discuss how historical Rete networks can be used for answering questions that help a system builder detect the cause of an error in a CLIPS program. Moreover, the cost of maintaining a historical Rete network is compared with that for a classical Rete network. We will demonstrate that the cost for assertions is only slightly higher for a historical Rete network. The cost for handling retraction could be significantly higher; however, we will show that by using special data structures that rely on hashing, it is also possible to implement retractions efficiently.

Tuttle, Sharon M.↗

Proposed data compression schemes for the Galileo S-band contingency mission

The Galileo spacecraft is currently on its way to Jupiter and its moons. In April 1991, the high gain antenna (HGA) failed to deploy as commanded. In case the current efforts to deploy the HGA fails, communications during the Jupiter encounters will be through one of two low gain antenna (LGA) on an S-band (2.3 GHz) carrier. A lot of effort has been and will be conducted to attempt to open the HGA. Also various options for improving Galileo's telemetry downlink performance are being evaluated in the event that the HGA will not open at Jupiter arrival. Among all viable options the most promising and powerful one is to perform image and non-image data compression in software onboard the spacecraft. This involves in-flight re-programming of the existing flight software of Galileo's Command and Data Subsystem processors and Attitude and Articulation Control System (AACS) processor, which have very limited computational and memory resources. In this article we describe the proposed data compression algorithms and give their respective compression performance. The planned image compression algorithm is a 4 x 4 or an 8 x 8 multiplication-free integer cosine transform (ICT) scheme, which can be viewed as an integer approximation of the popular discrete cosine transform (DCT) scheme. The implementation complexity of the ICT schemes is much lower than the DCT-based schemes, yet the performances of the two algorithms are indistinguishable. The proposed non-image compression algorith is a Lempel-Ziv-Welch (LZW) variant, which is a lossless universal compression algorithm based on a dynamic dictionary lookup table. We developed a simple and efficient hashing function to perform the string search.

Cheung, Kar-Ming↗

STARBASE: Database software for the automated plate scanner

The Automated Plate Scanner (APS) of the University of Minnesota, a unique high speed 'flying spot' laser scanner, is currently being used to scan and digitize the 936 O and E plate pairs of the first epoch Palomar Sky Survey. The resultant database will be used to produce a catalog of approximately a billion stars and several million galaxies. The authors describe the ongoing development of a dedicated APS database management system which will be made available to the astronomical community via INTERNET. A specialized DBMS called STARBASE has been written to provide fast access to the hundreds of millions of images collected by the APS. This system provides an initial reduction mode for parameterizing APS images and classifying image types using a novel set of neural network image classifiers. A second analysis mode, which will be that commonly used by the general user, provides for searches of the database which may be constrained by any combination of physical and positional parameters. Through the use of pointer hash trees, the system has been optimized for extremely fast positional searches using either right ascension and declination on the sky or linear X and Y positions on the POSS field. In addition to fast data retrieval, the system provides a graphical interface for displaying scatter plots or histograms of the collected data. In addition, a specialized image display system is being developed to allow the user to view densitometric data for all objects classified as extended by the neural network system. Finally, STARBASE has a flexible programmable interface which allows other programs to access information in the database. This allows users to write applications suited to their particular needs to process APS data.

Odewahn, S. C.↗

Investigation of aerodynamic design issues with regions of separated flow

Existing aerodynamic design methods have generally concentrated on the optimization of airfoil or wing shapes to produce a minimum drag while satisfying some basic constraints such as lift, pitching moment, or thickness. Since the minimization of drag almost always precludes the existence of separated flow, the evaluation and validation of these design methods for their robustness and accuracy when separated flow is present has not been aggressively pursued. However, two new applications for these design tools may be expected to include separated flow and the issues of aerodynamic design with this feature must be addressed. The first application of the aerodynamic design tools is the design of airfoils or wings to provide an optimal performance over a wide range of flight conditions (multipoint design). While the definition of 'optimal performance' in the multipoint setting is currently being hashed out, it is recognized that given a wide range of flight conditions, it will not be possible to ensure a minimum drag constraint at all conditions, and in fact some amount of separated flow (presumably small) may have to be allowed at the more demanding flight conditions. Thus a multipoint design method must be tolerant of the existence of separated flow and may include some controls upon its extent. The second application is in the design of wings with extended high speed buffet boundaries of their flight envelopes. Buffet occurs on a wing when regions of flow separation have grown to the extent that their time varying pressures induce possible destructive effects upon the wing structure or adversely effect either the aircraft controllability or passenger comfort. A conservative approach to the expansion of the buffet flight boundary is to simply expand the flight envelope of nonseparated flow under the assumption that buffet will also thus be alleviated. However, having the ability to design a wing with separated flow and thus to control the location, extent and severity of the separated flow regions may allow aircraft manufacturers to gain an advantage in the early design stages of an aircraft, when configuration changes are relatively inexpensive to make. The goal of the summer research at NASA Langley Research Center (LaRC) was twofold: first, to investigate a particular airfoil design problem observed under conditions of strong shock induced flow separation on the upper surface of an airfoil at transonic conditions; and second, to suggest and investigate design methodologies for the prediction (or detection) and control of flow separation. The context of both investigations was to use an existing two dimensional Navier-Stokes flow solver and the constrained direct/iterative surface curvature (CDISC) design algorithm developed at LaRC. As a lead in to the primary task, it was necessary to gain a familiarity with both the design method and the computational analysis and to perform the FORTRAN coding needed to couple them together.

Gally, Tom↗

Control of flow separation in airfoil/wing design applications

Existing aerodynamic design methods have generally concentrated on the optimization of airfoil or wing shapes to produce a minimum drag while satisfying some basic constraints such as lift, pitching moment, or thickness. Since the minimization of drag almost always precludes the existence of separated flow, the evaluation and validation of these design methods for their robustness and accuracy when separated flow is present has not been aggressively pursued. However, two new applications for these design tools may be expected to include separated flow and the issues of aerodynamic design with this feature must be addressed. The first application of the aerodynamic design tools is the design of airfoils or wings to provide an optimal performance over a wide range of flight conditions (multipoint design). While the definition of 'optimal performance' in the multipoint setting is currently being hashed out, it is recognized that given a wide enough range of flight conditions, it will not be possible to ensure a minimum drag constraint at all conditions, and in fact some amount of separated flow (presumably small) may have to be allowed at the more demanding flight conditions. Thus a multipoint design method must be tolerant of the existence of separated flow and may include some controls upon its extent. The second application is in the design of wings with extended high speed buffet boundaries of their flight envelopes. Buffet occurs on a wing when regions of flow separation have grown to the extent that their time varying pressures induce possible destructive effects upon the wing structure or adversely effect either the aircraft controllability or the passenger comfort. A conservative approach to the expansion of the buffet flight boundary is to simply expand the flight envelope of nonseparated flow under the assumption that buffet will also thus be alleviated. However, having the ability to design a wing with separated flow and thus to control the location, extent, and severity of the separated flow regions may allow aircraft manufacturers to gain an advantage in the early design stages of an aircraft, when configuration changes are relatively inexpensive to make. Continuing the work begun last year, an airfoil design package has been modified to provide some control over the existence and extent of flow separation. This package consists of a 2-D Navier-Stokes flow solver which is coupled to the CDISC (constrained direct/iterative surface curvature) design method. The first modification is a prediction method for determining whether separation is likely based solely upon a given pressure distribution. If separation is predicted but is undesirable, the new routines will modify the pressure distribution to alleviate the problem. This new pressure distribution is then used in the design method to generate a new aerodynamic shape. Since separation may be acceptable in some cases, particularly if the separation does not extend to the trailing edge, another added logic estimates the extent of separation based upon a correlation with calculated separated flow cases. If the flow behind a shock induced separation is not predicted to reattach before the trailing edge, the logic weakens the shock strength and otherwise alters the pressure distribution in order to promote reattachment. This later addition is as yet unreliable due to secondary separation effects, but additional work is being pursued to improve the method.

Gally, Thomas A.↗

NASA Tech Briefs, November 2008

Topics covered include: Digital Phase Meter for a Laser Heterodyne Interferometer; Vision System Measures Motions of Robot and External Objects; Advanced Precipitation Radar Antenna to Measure Rainfall From Space; Wide-Band Radar for Measuring Thickness of Sea Ice; Vertical Isolation for Photodiodes in CMOS Imagers; Wide-Band Microwave Receivers Using Photonic Processing; L-Band Transmit/Receive Module for Phase-Stable Array Antennas; Microwave Power Combiner/Switch Utilizing a Faraday Rotator; Compact Low-Loss Planar Magic-T; Using Pipelined XNOR Logic to Reduce SEU Risks in State Machines; Quasi-Optical Transmission Line for 94-GHz Radar; Next Generation Flight Controller Trainer System; Converting from DDOR SASF to APF; Converting from CVF to AAF; Documenting AUTOGEN and APGEN Model Files; Sequence History Update Tool; Extraction and Analysis of Display Data; MRO DKF Post-Processing Tool; Rig Diagnostic Tools; MRO Sequence Checking Tool; Science Activity Planner for the MER Mission; UAVSAR Flight-Planning System; Templates for Deposition of Microscopic Pointed Structures; Adjustable Membrane Mirrors Incorporating G-Elastomers; Hall-Effect Thruster Utilizing Bismuth as Propellant; High-Temperature Crystal-Growth Cartridge Tubes Made by VPS; Quench Crucibles Reinforced with Metal; Deep-Sea Hydrothermal-Vent Sampler; Mars Rocket Propulsion System; Two-Stage Passive Vibration Isolator; Improved Thermal Design of a Compression Mold; Enhanced Pseudo-Waypoint Guidance for Spacecraft Maneuvers; Altimetry Using GPS-Reflection/Occultation Interferometry; Thermally Driven Josephson Effect; Perturbation Effects on a Supercritical C7H16/N2 Mixing Layer; Gold Nanoparticle Labels Amplify Ellipsometric Signals; Phase Matching of Diverse Modes in a WGM Resonator; WGM Resonators for Terahertz-to-Optical Frequency Conversion; Determining Concentration of Nanoparticles from Ellipsometry; Microwave-to-Optical Conversion in WGM Resonators; Four-Pass Coupler for Laser-Diode-Pumped Solid-State Laser; Low-Resolution Raman-Spectroscopy Combustion Thermometry; Temperature Sensors Based on WGM Optical Resonators; Varying the Divergence of Multiple Parallel Laser Beams; Efficient Algorithm for Rectangular Spiral Search; Algorithm-Based Fault Tolerance Integrated with Replication; Targeting and Localization for Mars Rover Operations; Terrain-Adaptive Navigation Architecture; Self-Adjusting Hash Tables for Embedded Flight Applications; Schema for Spacecraft-Command Dictionary; Combined GMSK Communications and PN Ranging; System-Level Integration of Mass Memory; Network-Attached Solid-State Recorder Architecture; Method of Cross-Linking Aerogels Using a One-Pot Reaction Scheme; An Efficient Reachability Analysis Algorithm.

Source record↗

A Data Type for Efficient Representation of Other Data Types

A self-organizing, monomorphic data type denoted a sequence has been conceived to address certain concerns that arise in programming parallel computers. A sequence in the present sense can be regarded abstractly as a vector, set, bag, queue, or other construct. Heretofore, in programming a parallel computer, it has been necessary for the programmer to state explicitly, at the outset, what parts of the program and the underlying data structures must be represented in parallel form. Not only is this requirement not optimal from the perspective of implementation; it entails an additional requirement that the programmer have intimate understanding of the underlying parallel structure. The present sequence data type overcomes both the implementation and parallel structure obstacles. In so doing, the sequence data type provides unified means by which the programmer can represent a data structure for natural and automatic decomposition to a parallel computing architecture. Sequences exhibit the behavioral and structural characteristics of vectors, but the underlying representations are automatically synthesized from combinations of programmers advice and execution use metrics. Sequences can vary bidirectionally between sparseness and density, making them excellent choices for many kinds of algorithms. The novelty and benefit of this behavior lies in the fact that it can relieve programmers of the details of implementations. The creation of a sequence enables decoupling of a conceptual representation from an implementation. The underlying representation of a sequence is a hybrid of representations composed of vectors, linked lists, connected blocks, and hash tables. The internal structure of a sequence can automatically change from time to time on the basis of how it is being used. Those portions of a sequence where elements have not been added or removed can be as efficient as vectors. As elements are inserted and removed in a given portion, then different methods are utilized to provide both an access and memory strategy that is optimized for that portion and the use to which it is put.

James, Mark↗

NASA Tech Briefs, July 2010

Topics covered include: Wirelessly Interrogated Wear or Temperature Sensors; Processing Nanostructured Sensors Using Microfabrication Techniques; Optical Pointing Sensor; Radio-Frequency Tank Eigenmode Sensor for Propellant Quantity Gauging; High-Temperature Optical Sensor; Integral Battery Power Limiting Circuit for Intrinsically Safe Applications; Configurable Multi-Purpose Processor; Squeezing Alters Frequency Tuning of WGM Optical Resonator; Automated Computer Access Request System; Range Safety for an Autonomous Flight Safety System; Fast and Easy Searching of Files in Unisys 2200 Computers; Parachute Drag Model; Evolutionary Scheduler for the Deep Space Network; Modular Habitats Comprising Rigid and Inflatable Modules; More About N2O-Based Propulsion and Breathable-Gas Systems; Ultrasonic/Sonic Rotary-Hammer Drills; Miniature Piezoelectric Shaker for Distribution of Unconsolidated Samples to Instrument Cells; Lunar Soil Particle Separator; Advanced Aerobots for Scientific Exploration; Miniature Bioreactor System for Long-Term Cell Culture; Electrochemical Detection of Multiple Bioprocess Analytes; Fabrication and Modification of Nanoporous Silicon Particles; High-Altitude Hydration System; Photon Counting Using Edge-Detection Algorithm; Holographic Vortex Coronagraph; Optical Structural Health Monitoring Device; Fuel-Cell Power Source Based on Onboard Rocket Propellants; Polar Lunar Regions: Exploiting Natural and Augmented Thermal Environments; Simultaneous Spectral Temporal Adaptive Raman Spectrometer - SSTARS; Improved Speed and Functionality of a 580-GHz Imaging Radar; Bolometric Device Based on Fluxoid Quantization; Algorithms for Learning Preferences for Sets of Objects; Model for Simulating a Spiral Software-Development Process; Algorithm That Synthesizes Other Algorithms for Hashing; Algorithms for High-Speed Noninvasive Eye-Tracking System; and Adapting ASPEN for Orbital Express.

Source record↗

Distinguishing Provenance Equivalence of Earth Science Data

Reproducibility of scientific research relies on accurate and precise citation of data and the provenance of that data. Earth science data are often the result of applying complex data transformation and analysis workflows to vast quantities of data. Provenance information of data processing is used for a variety of purposes, including understanding the process and auditing as well as reproducibility. Certain provenance information is essential for producing scientifically equivalent data. Capturing and representing that provenance information and assigning identifiers suitable for precisely distinguishing data granules and datasets is needed for accurate comparisons. This paper discusses scientific equivalence and essential provenance for scientific reproducibility. We use the example of an operational earth science data processing system to illustrate the application of the technique of cascading digital signatures or hash chains to precisely identify sets of granules and as provenance equivalence identifiers to distinguish data made in an an equivalent manner.

Tilmes, Curt↗

High-Performance, Multi-Node File Copies and Checksums for Clustered File Systems

Modern parallel file systems achieve high performance using a variety of techniques, such as striping files across multiple disks to increase aggregate I/O bandwidth and spreading disks across multiple servers to increase aggregate interconnect bandwidth. To achieve peak performance from such systems, it is typically necessary to utilize multiple concurrent readers/writers from multiple systems to overcome various singlesystem limitations, such as number of processors and network bandwidth. The standard cp and md5sum tools of GNU coreutils found on every modern Unix/Linux system, however, utilize a single execution thread on a single CPU core of a single system, and hence cannot take full advantage of the increased performance of clustered file systems. Mcp and msum are drop-in replacements for the standard cp and md5sum programs that utilize multiple types of parallelism and other optimizations to achieve maximum copy and checksum performance on clustered file systems. Multi-threading is used to ensure that nodes are kept as busy as possible. Read/write parallelism allows individual operations of a single copy to be overlapped using asynchronous I/O. Multinode cooperation allows different nodes to take part in the same copy/checksum. Split-file processing allows multiple threads to operate concurrently on the same file. Finally, hash trees allow inherently serial checksums to be performed in parallel. Mcp and msum provide significant performance improvements over standard cp and md5sum using multiple types of parallelism and other optimizations. The total speed-ups from all improvements are significant. Mcp improves cp performance over 27x, msum improves md5sum performance almost 19x, and the combination of mcp and msum improves verified copies via cp and md5sum by almost 22x. These improvements come in the form of drop-in replacements for cp and md5sum, so are easily used and are available for download as open source software at http://mutil.sourceforge.net.

Kolano, Paul Z.↗

Parallel file system with metadata distributed across partitioned key-value store c

Improved techniques are provided for storing metadata associated with a plurality of sub-files associated with a single shared file in a parallel file system. The shared file is generated by a plurality of applications executing on a plurality of compute nodes. A compute node implements a Parallel Log Structured File System (PLFS) library to store at least one portion of the shared file generated by an application executing on the compute node and metadata for the at least one portion of the shared file on one or more object storage servers. The compute node is also configured to implement a partitioned data store for storing a partition of the metadata for the shared file, wherein the partitioned data store communicates with partitioned data stores on other compute nodes using a message passing interface. The partitioned data store can be implemented, for example, using Multidimensional Data Hashing Indexing Middleware (MDHIM).

97 MATHEMATICS AND COMPUTING↗

Multi-factor authentication using quantum communication

Multi-factor authentication using quantum communication ("QC") includes stages for enrollment and identification. For example, a user enrolls for multi-factor authentication that uses QC with a trusted authority. The trusted authority transmits device factor information associated with a user device (such as a hash function) and user factor information associated with the user (such as an encrypted version of a user password). The user device receives and stores the device factor information and user factor information. For multi-factor authentication that uses QC, the user device retrieves its stored device factor information and user factor information, then transmits the user factor information to the trusted authority, which also retrieves its stored device factor information. The user device and trusted authority use the device factor information and user factor information (more specifically, information such as a user password that is the basis of the user factor information) in multi-factor authentication that uses QC.

99 GENERAL AND MISCELLANEOUS↗

Method and apparatus for mitigating row hammer attacks

An integrated circuit includes an aggressor wordline cache and logic that determines a candidate upper adjacent address and a candidate lower adjacent address of a target memory row corresponding to a read request to memory. When at least one of the candidate upper adjacent address or the candidate lower adjacent address are determined to be a victim row, the logic checks the aggressor wordline cache for a cache hit for the target memory row. When there is a cache hit in the aggressor wordline cache, the logic sends a corresponding cache line as a response to the read request, otherwise the logic causes a read of content from the memory. In certain examples, the logic includes a stored bit array and a hash function-based filter, which determines whether any of the candidate upper adjacent address and the candidate lower adjacent address are victim rows represented in the stored bit array.

SeyedzadehDelcheh, SeyedMohammad↗

Athena: High-Performance Sparse Tensor Contraction Sequence on Heterogeneous Memory

Sparse tensor contraction sequence has been widely employed in many fields, such as chemistry and physics. However, how to efficiently implement the sequence faces multiple challenges, such as redundant computations and memory operations, massive memory consumption, and inefficient utilization of hardware. To address the above challenges, we introduce Athena, a high-performance framework for SpTC sequences. Athena introduces new data structures, leverages emerging Optane-based heterogeneous memory (HM) architecture, and stage parallelism. In particular, Athena introduces shared hash table-represented sparse accumulator to eliminate unnecessary input processing and data migration; Athena uses a novel data-semantic guided dynamic migration solution to make the best use of the Optane-based HM for high performance; Athena also co-runs execution phases with different characteristics to enable high hardware utilization. Evaluating with 12 datasets, we show that Athena brings 327-7362× speedup over the state-of-the-art SpTC algorithm. With the dynamic data placement guided by data semantics, Athena brings performance improvement on Optane-based HM over a state-of-the-art software-based data management solution, a hardware-based data management solution, and PMM-only by 1.58×, 1.82×, and 2.34× respectively.

Liu, Jiawen↗

Multimodal communication system

A multimodal communication system includes a vehicle controller that controls one or more systems or subsystems of an unmanned vehicle. The communication controller manages communication and logical access to the unmanned vehicle. One or more sensors in communication with the communication controller detects and measures physical properties in proximity to the unmanned vehicle. Transceivers receive the unmanned vehicle commands that are transmitted simultaneously or concurrently and a monotonic generator generates a monotonic object each time the unmanned vehicle's operating state changes. The communication controller executes the first unmanned vehicle command received that has the correct cryptographic hash validating knowledge of the unmanned vehicle's current operating state.

Duncan, Andrew M.↗