Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “priority queue”

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 37 records · Page 2

Efficient Merge and Insert Operations for Binary Heaps and Trees

Binary heaps and binary search trees merge efficiently. We introduce a new amortized analysis that allows us to prove the cost of merging either binary heaps or balanced binary trees is O(l), in the amortized sense. The standard set of other operations (create, insert, delete, extract minimum, in the case of binary heaps, and balanced binary trees, as well as a search operation for balanced binary trees) remain with a cost of O(log n). For binary heaps implemented as arrays, we show a new merge algorithm that has a single operation cost for merging two heaps, a and b, of O(absolute value of a + min(log absolute value of b log log absolute value of b. log absolute value of a log absolute value of b). This is an improvement over O(absolute value of a + log absolute value of a log absolute value of b). The cost of the new merge is so low that it can be used in a new structure which we call shadow heaps. to implement the insert operation to a tunable efficiency. Shadow heaps support the insert operation for simple priority queues in an amortized time of O(f(n)) and other operations in time O((log n log log n)/f (n)), where 1 less than or equal to f (n) less than or equal to log log n. More generally, the results here show that any data structure with operations that change its size by at most one, with the exception of a merge (aka meld) operation, can efficiently amortize the cost of the merge under conditions that are true for most implementations of binary heaps and search trees.

Kuszmaul, Christopher Lee↗

Automatic Generation of CFD-Ready Surface Triangulations from CAD Geometry

This paper presents an approach for the generation of closed manifold surface triangulations from CAD geometry. CAD parts and assemblies are used in their native format, without translation, and a part's native geometry engine is accessed through a modeler-independent application programming interface (API). In seeking a robust and fully automated procedure, the algorithm is based on a new physical space manifold triangulation technique which was developed to avoid robustness issues associated with poorly conditioned mappings. In addition, this approach avoids the usual ambiguities associated with floating-point predicate evaluation on constructed coordinate geometry in a mapped space, The technique is incremental, so that each new site improves the triangulation by some well defined quality measure. Sites are inserted using a variety of priority queues to ensure that new insertions will address the worst triangles first, As a result of this strategy, the algorithm will return its 'best' mesh for a given (prespecified) number of sites. Alternatively, the algorithm may be allowed to terminate naturally after achieving a prespecified measure of mesh quality. The resulting triangulations are 'CFD-ready' in that: (1) Edges match the underlying part model to within a specified tolerance. (2) Triangles on disjoint surfaces in close proximity have matching length-scales. (3) The algorithm produces a triangulation such that no angle is less than a given angle bound, alpha, or greater than Pi - 2alpha This result also sets bounds on the maximum vertex degree, triangle aspect-ratio and maximum stretching rate for the triangulation. In addition to tile output triangulations for a variety of CAD parts, tile discussion presents related theoretical results which assert the existence of such all angle bound, and demonstrate that maximum bounds of between 25 deg and 30 deg may be achieved in practice.

Aftosmis, M. J.↗

Soft Real-Time PID Control on a VME Computer

microPID (uPID) is a computer program for real-time proportional + integral + derivative (PID) control of a translation stage in a Fourier-transform ultraviolet spectrometer. microPID implements a PID control loop over a position profile at sampling rate of 8 kHz (sampling period 125microseconds). The software runs in a strippeddown Linux operating system on a VersaModule Eurocard (VME) computer operating in real-time priority queue using an embedded controller, a 16-bit digital-to-analog converter (D/A) board, and a laser-positioning board (LPB). microPID consists of three main parts: (1) VME device-driver routines, (2) software that administers a custom protocol for serial communication with a control computer, and (3) a loop section that obtains the current position from an LPB-driver routine, calculates the ideal position from the profile, and calculates a new voltage command by use of an embedded PID routine all within each sampling period. The voltage command is sent to the D/A board to control the stage. microPID uses special kernel headers to obtain microsecond timing resolution. Inasmuch as microPID implements a single-threaded process and all other processes are disabled, the Linux operating system acts as a soft real-time system.

Karayan, Vahag↗

Learning Extended Finite State Machines

We present an active learning algorithm for inferring extended finite state machines (EFSM)s, combining data flow and control behavior. Key to our learning technique is a novel learning model based on so-called tree queries. The learning algorithm uses the tree queries to infer symbolic data constraints on parameters, e.g., sequence numbers, time stamps, identifiers, or even simple arithmetic. We describe sufficient conditions for the properties that the symbolic constraints provided by a tree query in general must have to be usable in our learning model. We have evaluated our algorithm in a black-box scenario, where tree queries are realized through (black-box) testing. Our case studies include connection establishment in TCP and a priority queue from the Java Class Library.

Register Automata↗

Priority-Based Dispatching Algorithm

Tasks assigned to different queues based on priority. Proposed algorithm controls execution of transient tasks of different priorities in real-time computation.

Ouzts, G.↗

Commercial SNF Pickup Queue Under the Standard Contact and Analysis of Hypothetical Alternate Acceptance Strategies

The Standard Contract for Disposal of Spent Nuclear Fuel and/or High-Level Radioactive Waste (Standard Contract) (10 CFR Part 961) establishes the terms and conditions under which the U.S. Department of Energy (DOE) will make available nuclear waste disposal services to the owners and generators of spent nuclear fuel (SNF) and high-level radioactive waste (HLW), as provided in section 302 of the Nuclear Waste Policy Act of 1982 (NWPA) as amended, and by which DOE will take title to, transport, and dispose of SNF and/or HLW delivered to DOE by those owners or generators who execute the contract. The Standard Contract establishes the process for allocating the federal government’s finite waste acceptance capacity among those various owners/generators. This acceptance allocation, also known as the acceptance queue, orders acceptance and transportation priority in accordance with the principle of “oldest fuel first” (OFF). Under the OFF methodology, the oldest SNF, as measured from the date of permanent discharge from the reactor, is given the highest priority in the acceptance queue. While the date of discharge of spent fuel forms the basis of allocations, the owner/generator can send an equivalent Metric Tons of Uranium (MTU) of SNF that the owner/generator owns in its place, as long as it meets the “Standard Fuel” specifications in Appendix E of the Standard Contract. This is a technical paper that does not take into account the contractual limitations under the Standard Contract. This paper also does not specify the party or parties responsible for any costs discussed herein. This paper provides analysis of hypothetical strategies for accepting SNF and no inferences should be drawn from this paper regarding future actions by DOE. To the extent that discussions or recommendations in this paper conflict with the provisions of the Standard Contract, the Standard Contract provisions prevail.

Joseph III, Robby↗

Fast simulation of packet loss rates in a shared buffer communications switch

This paper describes an efficient technique for estimating, via simulation, the probability of buffer overflows in a queueing model that arises in the analysis of ATM (Asynchronous Transfer Mode) communication switches. There are multiple streams of (autocorrelated) traffic feeding the switch that has a buffer of finite capacity. Each stream is designated as either being of high or low priority. When the queue length reaches a certain threshold, only high priority packets are admitted to the switch's buffer. The problem is to estimate the loss rate of high priority packets. An asymptotically optimal importance sampling approach is developed for this rare event simulation problem. In this approach, the importance sampling is done in two distinct phases. In the first phase, an importance sampling change of measure is used to bring the queue length up to the threshold at which low priority packets get rejected. In the second phase, a different importance sampling change of measure is used to move the queue length from the threshold to the buffer capacity.

Chang, Cheng-Shang↗

Enhanced atomics for workgroup synchronization

A technique for synchronizing workgroups is provided. The techniques comprise detecting that one or more non-executing workgroups are ready to execute, placing the one or more non-executing workgroups into one or more ready queues based on the synchronization status of the one or more workgroups, detecting that computing resources are available for execution of one or more ready workgroups, and scheduling for execution one or more ready workgroups from the one or more ready queues in an order that is based on the relative priority of the ready queues.

Dutu, Alexandru↗

INL HPC Overview and CASL Computing Collaboration

October 2019 – INL is increasing the upper limit on Falcon’s high priority “dedicated” CASL queue to 10,000 cores January 2019 – INL will give CASL early-access to the Lemhi system for MAMBA calibration work. The system will likely still be in commission/test mode (subject to reconfiguration/reboots). This early-access to Lemhi should support the required MAMBA calibration runs FY19 -- INL will provide proactive user support for CASL users/jobs and code debugging. INL will specifically focus on helping industry users getting access to Falcon and running their jobs. FY19 CASL costs = $500k vs. $1.2M for a purchased dedicated machine.

11 NUCLEAR FUEL CYCLE AND FUEL MATERIALS↗

Development of the NASA MCAT Auxiliary Telescope for Orbital Debris Research

The National Aeronautical Space Administration has deployed the Meter Class Autonomous Telescope (MCAT) to Ascension Island with plans for it to become fully operational by summer 2016. This telescope will be providing data in support of research being conducted by the Orbital Debris Program Office at the Johnson Space Center. In addition to the main observatory, a smaller, auxiliary telescope is being deployed to the same location to augment and support observations generated by MCAT. It will provide near-simultaneous photometry and astrometry of debris objects, independent measurements of the seeing conditions, and offload low priority targets from MCAT's observing queue. Its hardware and software designs are presented here The National Aeronautical and Space Administration (NASA) has recently deployed the Meter Class Autonomous Telescope (MCAT) to Ascension Island. MCAT will provide NASA with a dedicated optical sensor for observations of orbital debris with the goal of statistically sampling the orbital and photometric characteristics of the population from low Earth to Geosynchronous orbits. Additionally, a small auxiliary telescope, co-located with MCAT, is being deployed to augment its observations by providing near-simultaneous photometry and astrometry, as well as offloading low priority targets from MCAT's observing queue. It will also serve to provide an independent measurement of the seeing conditions to help monitor the quality of the data being produced by the larger telescope. Comprised of off-the-shelf-components, the MCAT Auxiliary Telescope will have a 16-inch optical tube assembly, Sloan g'r'i'z' and Johnson/Cousins BVRI filters, and a fast tracking mount to help facilitate the tracking of objects in low Earth orbit. Tracking modes and tasking will be similar to MCAT except an emphasis will be placed on observations that provide more accurate initial orbit determination for the objects detected by MCAT. The near-simultaneous observations will also provide the opportunity for multi-filter color information of the debris objects to be obtained. Color information can further distinguish the individual objects within the population and provide insight into the reflectance properties of their surface material. The specific hardware, software, and tasking methodology of the MCAT Auxiliary Telescope is presented here..

Frith, James↗

Development of the NASA MCAT Auxiliary Telescope for Orbital Debris Research

The National Aeronautical and Space Administration (NASA) has recently deployed the Meter Class Autonomous Telescope (MCAT) to Ascension Island. MCAT will provide NASA with a dedicated optical sensor for observations of orbital debris with the goal of statistically sampling the orbital and photometric characteristics of the population from low Earth to Geosynchronous orbits. Additionally, a small auxiliary telescope, co-located with MCAT, is being deployed to augment its observations by providing near-simultaneous photometry and astrometry, as well as offloading low priority targets from MCAT's observing queue. It will also be available to provide observational measurements to the Space Surveillance Network for the United States Air Force.

Frith, James↗

NASA Deep Space Network Operations Scheduling

The functioning of the Deep Space Network Operations Scheduling, Jet Propulsion Laboratory, CA is reviewed. The primary objectives of the Operations Scheduling are: to schedule the worldwide global allocation of ground communications, tracking facilities, and equipment; and to provide deep space telecommunications for command, tracking, telemetry, and control in support of flight mission operations and tests. Elements of the earth set are Deep Space Stations (DSS) which provide the telecommunications link between the earth and spacecraft; NASA Communications Network; Network Data Processing Area; Network Operations Control Area which provides operational direction to the DSS; Mission Control and Computing systems; and Mission Support areas which provide flight control of the spacecraft. Elements of the space set include mission priorities and requirements which determine the spacecraft queue for allocating network resources. Scheduling is discussed in terms of long-range (3 years), mid-range (8 weeks), and short-range (2 weeks).

Enari, D. M.↗

Preliminary Findings: Issues in Surface Movement

The final report for the grant is presented. The recent goals for this project have been: (1) To identify common surface movement challenges which affect the airlines and Air Traffic Control; (2) To map out possible solutions to these challenges; (3) To start generalizing about the information we are receiving so that major, abstract categories of challenges and potential solutions will begin to emerge. In particular, there are several areas of opportunity which are beginning to emerge from the data, dealing with the need for: (1) Tools to support information exchange regarding priorities (both within an individual airline and between the ATC tower and airlines). Such priorities include both concerns affecting departure throughput as well as the ordering of departures to accommodate other airline considerations; (2) Planning tools to help ATC and airline Ramp staff deal with information about priorities; (3) Implementation of strategies to enable greater flexibility in queueing flights for departures; (4) Tools to provide better coordination and situation awareness during taxiing (within an airline as well as between airlines and between the airlines); (5) Tools to support planning and to deal with the interactions between departures and arrivals. Thus far, the initial interviews and observations at three airlines and two ATC facilities have been completed.

Smith, Philip J.↗

Queueing models for token and slotted ring networks

Currently the end-to-end delay characteristics of very high speed local area networks are not well understood. The transmission speed of computer networks is increasing, and local area networks especially are finding increasing use in real time systems. Ring networks operation is generally well understood for both token rings and slotted rings. There is, however, a severe lack of queueing models for high layer operation. There are several factors which contribute to the processing delay of a packet, as opposed to the transmission delay, e.g., packet priority, its length, the user load, the processor load, the use of priority preemption, the use of preemption at packet reception, the number of processors, the number of protocol processing layers, the speed of each processor, and queue length limitations. Currently existing medium access queueing models are extended by adding modeling techniques which will handle exhaustive limited service both with and without priority traffic, and modeling capabilities are extended into the upper layers of the OSI model. Some of the model are parameterized solution methods, since it is shown that certain models do not exist as parameterized solutions, but rather as solution methods.

Peden, Jeffery H.↗

Contact Graph Routing

Contact Graph Routing (CGR) is a dynamic routing system that computes routes through a time-varying topology of scheduled communication contacts in a network based on the DTN (Delay-Tolerant Networking) architecture. It is designed to enable dynamic selection of data transmission routes in a space network based on DTN. This dynamic responsiveness in route computation should be significantly more effective and less expensive than static routing, increasing total data return while at the same time reducing mission operations cost and risk. The basic strategy of CGR is to take advantage of the fact that, since flight mission communication operations are planned in detail, the communication routes between any pair of bundle agents in a population of nodes that have all been informed of one another's plans can be inferred from those plans rather than discovered via dialogue (which is impractical over long one-way-light-time space links). Messages that convey this planning information are used to construct contact graphs (time-varying models of network connectivity) from which CGR automatically computes efficient routes for bundles. Automatic route selection increases the flexibility and resilience of the space network, simplifying cross-support and reducing mission management costs. Note that there are no routing tables in Contact Graph Routing. The best route for a bundle destined for a given node may routinely be different from the best route for a different bundle destined for the same node, depending on bundle priority, bundle expiration time, and changes in the current lengths of transmission queues for neighboring nodes; routes must be computed individually for each bundle, from the Bundle Protocol agent's current network connectivity model for the bundle s destination node (the contact graph). Clearly this places a premium on optimizing the implementation of the route computation algorithm. The scalability of CGR to very large networks remains a research topic. The information carried by CGR contact plan messages is useful not only for dynamic route computation, but also for the implementation of rate control, congestion forecasting, transmission episode initiation and termination, timeout interval computation, and retransmission timer suspension and resumption.

Burleigh, Scott C.↗

Scheduling revisited workstations in integrated-circuit fabrication

The cost of building new semiconductor wafer fabrication factories has grown rapidly, and a state-of-the-art fab may cost 250 million dollars or more. Obtaining an acceptable return on this investment requires high productivity from the fabrication facilities. This paper describes the Photo Dispatcher system which was developed to make machine-loading recommendations on a set of key fab machines. Dispatching policies that generally perform well in job shops (e.g., Shortest Remaining Processing Time) perform poorly for workstations such as photolithography which are visited several times by the same lot of silicon wafers. The Photo Dispatcher evaluates the history of workloads throughout the fab and identifies bottleneck areas. The scheduler then assigns priorities to lots depending on where they are headed after photolithography. These priorities are designed to avoid starving bottleneck workstations and to give preference to lots that are headed to areas where they can be processed with minimal waiting. Other factors considered by the scheduler to establish priorities are the nearness of a lot to the end of its process flow and the time that the lot has already been waiting in queue. Simulations that model the equipment and products in one of Texas Instrument's wafer fabs show the Photo Dispatcher can produce a 10 percent improvement in the time required to fabricate integrated circuits.

Kline, Paul J.↗

A NASA Strategy for Leveraging Emerging Launch Vehicles for Routine, Small Payload Missions

Orbital flight opportunities for small payloads have always been few and far between, and then on February 1, 2002, the situation got worse. In the wake of the loss of the Columbia during STS- 107, changing NASA missions and priorities led to the termination of the Shuttle Small Payloads Projects, including Get-Away Special, Hitcbker, and Space Experiment Module. In spite of the limited opportunities, long queue, and restrictions associated with flying experiments on a man-rated transportation system; the carriers provided a sustained, high quality experiment services for education, science, and technology payloads, and was one of the few games in town. Attempts to establish routine opportunities aboard existing ELVs have been unsuccessful, as the cost-per-pound on small ELVs and conflicts with primary spacecraft on larger vehicles have proven prohibitive. Ths has led to a backlog of existing NASA-sponsored payloads and no prospects or plans for fbture opportunities within the NASA community. The prospects for breaking out of this paradigm appear promising as a result of NASA s partnership with DARPA in pursuit of low-cost, responsive small ELVs under the Falcon Program. Through this partnership several new small ELVs, providing 1000 lbs. to LEO will be demonstrated in less than two years that promise costs that are reasonable enough that NASA, DoD, and other sponsors can once again invest in small payload opportunities. Within NASA, planning has already begun. NASA will be populating one or more of the Falcon demonstration flights with small payloads that are already under development. To accommodate these experiments, Goddard s Wallops Flight Facility has been tasked to develop a multi-payload ejector (MPE) to accommodate the needs of these payloads. The MPE capabilities and design is described in detail in a separately submitted abstract. Beyond use of the demonstration flights however, Goddard has already begun developing strategies to leverage these new ELVs as elements of a larger system designed to provide routine, low-cost end-to-end services for small science, Exploration, and education payloads. The plan leverages the management approaches of the successful Sounding Rocket Program and Shuttle Small Payloads Projects. The strategy consists of using a systems implementation approach of elements, including 1) Falcon ELVs, 2) advanced launch site technologies and processes, 3) suite of experiment carriers accommodating different mission requirements, 4) streamlined integration and test operations, 5 ) experiment brokering and management, and 6) standardized, distributed payload operations. The envisioned suite of carriers includes the MPE, a standard interface experiment carrier, and potentially a reentry fieeflyer experiment carrier. Key to the success of this strategy is standard experiment interfaces within the carriers to limit mission- unique tasks, establishmg and managing a program of scheduled reoccurring flights rather than discrete missions, and streamlined, centralized implementation of the elements. These individual elements are each under development and Goddard will demonstrate the overall system strategy low-cost small payload missions on the initial Falcon demonstration launches from Wallops. goal is to show that this model should be converted to a sustained NASA program supporting science, technology, and education, with annual flight opportunities. The paper will define in detail the various elements of the overall program, as well as provide status, philosophy, and strategy for the program that will hopefully once-and-for-all provide low-cost, routine access to space for the small payloads community.

Underwood, Bruce E.↗