Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “QUEUES”

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 145 records · Page 8

Parallel discrete event simulation: A shared memory approach

With traditional event list techniques, evaluating a detailed discrete event simulation model can often require hours or even days of computation time. Parallel simulation mimics the interacting servers and queues of a real system by assigning each simulated entity to a processor. By eliminating the event list and maintaining only sufficient synchronization to insure causality, parallel simulation can potentially provide speedups that are linear in the number of processors. A set of shared memory experiments is presented using the Chandy-Misra distributed simulation algorithm to simulate networks of queues. Parameters include queueing network topology and routing probabilities, number of processors, and assignment of network nodes to processors. These experiments show that Chandy-Misra distributed simulation is a questionable alternative to sequential simulation of most queueing network models.

Reed, Daniel A.↗

Efficient partitioning and assignment on programs for multiprocessor execution

The general problem studied is that of segmenting or partitioning programs for distribution across a multiprocessor system. Efficient partitioning and the assignment of program elements are of great importance since the time consumed in this overhead activity may easily dominate the computation, effectively eliminating any gains made by the use of the parallelism. In this study, the partitioning of sequentially structured programs (written in FORTRAN) is evaluated. Heuristics, developed for similar applications are examined. Finally, a model for queueing networks with finite queues is developed which may be used to analyze multiprocessor system architectures with a shared memory approach to the problem of partitioning. The properties of sequentially written programs form obstacles to large scale (at the procedure or subroutine level) parallelization. Data dependencies of even the minutest nature, reflecting the sequential development of the program, severely limit parallelism. The design of heuristic algorithms is tied to the experience gained in the parallel splitting. Parallelism obtained through the physical separation of data has seen some success, especially at the data element level. Data parallelism on a grander scale requires models that accurately reflect the effects of blocking caused by finite queues. A model for the approximation of the performance of finite queueing networks is developed. This model makes use of the decomposition approach combined with the efficiency of product form solutions.

Standley, Hilda M.↗

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↗

Parallel integer sorting with medium and fine-scale parallelism

Two new parallel integer sorting algorithms, queue-sort and barrel-sort, are presented and analyzed in detail. These algorithms do not have optimal parallel complexity, yet they show very good performance in practice. Queue-sort designed for fine-scale parallel architectures which allow the queueing of multiple messages to the same destination. Barrel-sort is designed for medium-scale parallel architectures with a high message passing overhead. The performance results from the implementation of queue-sort on a Connection Machine CM-2 and barrel-sort on a 128 processor iPSC/860 are given. The two implementations are found to be comparable in performance but not as good as a fully vectorized bucket sort on the Cray YMP.

Dagum, Leonardo↗

A Simulation Study of Paced TCP

In this paper, we study the performance of paced TCP, a modified version of TCP designed especially for high delay- bandwidth networks. In typical networks, TCP optimizes its send-rate by transmitting increasingly large bursts, or windows, of packets, one burst per round-trip time, until it reaches a maximum window-size, which corresponds to the full capacity of the network. In a network with a high delay-bandwidth product, however, Transmission Control Protocol's (TCPs) maximum window-size may be larger than the queue size of the intermediate routers, and routers will begin to drop packets as soon as the windows become too large for the router queues. The TCP sender then concludes that the bottleneck capacity of the network has been reached, and it limits its send-rate accordingly. Partridge proposed paced TCP as a means of solving the problem of queueing bottlenecks. A sender using paced TCP would release packets in multiple, small bursts during a round-trip time in which ordinary TCP would release a single, large burst of packets. This approach allows the sender to increase its send-rate to the maximum window size without encountering queueing bottlenecks. This paper describes the performance of paced TCP in a simulated network and discusses implementation details that can affect the performance of paced TCP.

Kulik, Joanna↗

Job Scheduling Under the Portable Batch System

The typical batch queuing system schedules jobs for execution by a set of queue controls. The controls determine from which queues jobs may be selected. Within the queue, jobs are ordered first-in, first-run. This limits the set of scheduling policies available to a site. The Portable Batch System removes this limitation by providing an external scheduling module. This separate program has full knowledge of the available queued jobs, running jobs, and system resource usage. Sites are able to implement any policy expressible in one of several procedural language. Policies may range from "bet fit" to "fair share" to purely political. Scheduling decisions can be made over the full set of jobs regardless of queue or order. The scheduling policy can be changed to fit a wide variety of computing environments and scheduling goals. This is demonstrated by the use of PBS on an IBM SP-2 system at NASA Ames.

Henderson, Robert L.↗

Delay Banking for Managing Air Traffic

Delay banking has been invented to enhance air-traffic management in a way that would increase the degree of fairness in assigning arrival, departure, and en-route delays and trajectory deviations to aircraft impacted by congestion in the national airspace system. In delay banking, an aircraft operator (airline, military, general aviation, etc.) would be assigned a numerical credit when any of their flights are delayed because of an air-traffic flow restriction. The operator could subsequently bid against other operators competing for access to congested airspace to utilize part or all of its accumulated credit. Operators utilize credits to obtain higher priority for the same flight, or other flights operating at the same time, or later, in the same airspace, or elsewhere. Operators could also trade delay credits, according to market rules that would be determined by stakeholders in the national airspace system. Delay banking would be administered by an independent third party who would use delay banking automation to continually monitor flights, allocate delay credits, maintain accounts of delay credits for participating airlines, mediate bidding and the consumption of credits of winning bidders, analyze potential transfers of credits within and between operators, implement accepted transfers, and ensure fair treatment of all participating operators. A flow restriction can manifest itself in the form of a delay in assigned takeoff time, a reduction in assigned airspeed, a change in the position for the aircraft in a queue of all aircraft in a common stream of traffic (e.g., similar route), a change in the planned altitude profile for an aircraft, or change in the planned route for the aircraft. Flow restrictions are typically imposed to mitigate traffic congestion at an airport or in a region of airspace, particularly congestion due to inclement weather, or the unavailability of a runway or region of airspace. A delay credit would be allocated to an operator of a flight that has accepted, or upon which was imposed, a flow restriction. The amount of the credit would increase with the amount of delay caused by the flow restriction, the exact amount depending on which of several candidate formulas is eventually chosen. For example, according to one formula, there would be no credit for a delay smaller than some threshold value (e.g., 30 seconds) and the amount of the credit for a longer delay would be set at the amount of the delay minus the threshold value. Optionally, the value of a delay credit could be made to decay with time according to a suitable formula (e.g., an exponential decay). Also, optionally, a transaction charge could be assessed against the value of a delay credit that an operator used on a flight different from the one for which the delay originated or that was traded with a different operator. The delay credits accumulated by a given airline could be utilized in various ways. For example, an operator could enter a bid for priority handling in a new flow restriction that impacts one or more of the operator s flights; if the bid were unsuccessful, all or a portion of the credit would be returned to the bidder. If the bid pertained to a single aircraft that was in a queue, delay credits could be consumed in moving the aircraft to an earlier position within the queue. In the case of a flow restriction involving a choice of alternate routes, planned altitude profile, aircraft spacing, or other non-queue flow restrictions, delay credits could be used to bid for an alternative assignment.

Green, Steve↗

Combining multi-layered bitmap files using network specific hardware

Images and video can be produced by compositing or alpha blending a group of image layers or video layers. Increasing resolution or the number of layers results in increased computational demands. As such, the available computational resources limit the images and videos that can be produced. A computational architecture in which the image layers are packetized and streamed through processors can be easily scaled so to handle many image layers and high resolutions. The image layers are packetized to produce packet streams. The packets in the streams are received, placed in queues, and processed. For alpha blending, ingress queues receive the packetized image layers which are then z sorted and sent to egress queues. The egress queue packets are alpha blended to produce an output image or video.

97 MATHEMATICS AND COMPUTING↗

Ordering of guarded and unguarded stores for no-sync I/O

A parallel computing system processes at least one store instruction. A first processor core issues a store instruction. A first queue, associated with the first processor core, stores the store instruction. A second queue, associated with a first local cache memory device of the first processor core, stores the store instruction. The first processor core updates first data in the first local cache memory device according to the store instruction. The third queue, associated with at least one shared cache memory device, stores the store instruction. The first processor core invalidates second data, associated with the store instruction, in the at least one shared cache memory. The first processor core invalidates third data, associated with the store instruction, in other local cache memory devices of other processor cores. The first processor core flushing only the first queue.

97 MATHEMATICS AND COMPUTING↗

Improving Block-level Efficiency with scsi-mq

Current generation solid-state storage devices are exposing a new bottlenecks in the SCSI and block layers of the Linux kernel, where IO throughput is limited by lock contention, inefficient interrupt handling, and poor memory locality. To address these limitations, the Linux kernel block layer underwent a major rewrite with the blk-mq project to move from a single request queue to a multi-queue model. The Linux SCSI subsystem rework to make use of this new model, known as scsi-mq, has been merged into the Linux kernel and work is underway for dm-multipath support in the upcoming Linux 4.0 kernel. These pieces were necessary to make use of the multi-queue block layer in a Lustre parallel filesystem with high availability requirements. We undertook adding support of the 3.18 kernel to Lustre with scsi-mq and dm-multipath patches to evaluate the potential of these efficiency improvements. In this paper we evaluate the block-level performance of scsi-mq with backing storage hardware representative of a HPC-targerted Lustre filesystem. Our findings show that SCSI write request latency is reduced by as much as 13.6%. Additionally, when profiling the CPU usage of our prototype Lustre filesystem, we found that CPU idle time increased by a factor of 7 with Linux 3.18 and blk-mq as compared to a standard 2.6.32 Linux kernel. Our findings demonstrate increased efficiency of the multi-queue block layer even with disk-based caching storage arrays used in existing parallel filesystems.

Cluster Computing↗

Network resiliency through memory health monitoring and proactive management

A method for managing a network queue memory includes receiving sensor information about the network queue memory, predicting a memory failure in the network queue memory based on the sensor information, and outputting a notification through a plurality of nodes forming a network and using the network queue memory, the notification configuring communications between the nodes.

97 MATHEMATICS AND COMPUTING↗

Network resiliency through memory health monitoring and proactive management

A method for managing a network queue memory includes receiving sensor information about the network queue memory, predicting a memory failure in the network queue memory based on the sensor information, and outputting a notification through a plurality of nodes forming a network and using the network queue memory, the notification configuring communications between the nodes.

Andrade Costa, Carlos H.↗

Job Scheduler-Driven Power Gateway for High Performance Computing

Power gateways in the form of a microgrid can incorporate multiple distributed energy resources (DER) in either grid forming or grid following mode and support high performance computing (HPC) power profiles including the large load-follow requirements observed in multi-user HPC systems. The microgrid’s flexibility to operate in either grid forming or grid following mode and to actively switch between these modes enables baseline power from multiple non-baseline DER while maintaining high power quality metrics for the HPC system. But this enormous flexibility in demand response and time of use shifting is generally programmed independently of any integration with an HPC job scheduler which can better inform the load shaping by the microgrid. While there are many existing approaches where the HPC job scheduler takes in information from the grid to make queue scheduling decisions, this work takes the opposite view and explores a scheduler where the jobs in the queue can directly impact the settings of the grid. Several HPC scheduler strategies are tested where the jobs in the queue directly impact the settings of a microgrid designed for HPC operation which is driving a datacenter with three classes of HPC architectures. The scheduler operation is shown using a microgrid with 64 kW of solar capacity and 320 kWh of battery over a period of 21 days operating with significant low-follow swings, a throttled grid, cloudy conditions, switching between grid following and grid forming modes, and a wide range of battery states-of-charge all while maintaining high quality power metrics. The scheduler provides a mechanism for the job queue to directly impact a power gateway like a microgrid and to improve HPC power outcomes such as maximizing renewable energy usage

microgrid↗

Algorithms and data structures to accelerate network analysis

As the sheer amount of computer generated data continues to grow exponentially, new bottlenecks are unveiled that require rethinking our traditional software and hardware architectures. Here in this paper we present five algorithms and data structures (long queue emulation, lockless bimodal queues, tail early dropping, LFN tables, and multiresolution priority queues) designed to optimize the process of analyzing network traffic. We integrated these optimizations on R-Scope, a high performance network appliance that runs the Bro network analyzer, and present benchmarks showcasing performance speed ups of 5X at traffic rates of 10 Gbps.

97 MATHEMATICS AND COMPUTING↗

Offline Arterial Signal Timing Optimization for Closely Spaced Intersections

The stop-and-go driving behavior at a busy arterial causes a significant amount of fuel waste and emissions that could be reduced. For closely spaced intersections, the traditional bottom-up signal timing approach could fail under high volumes when the queues reach the upstream intersections. A well-coordinated arterial should manage the queue length to prevent the control from failing. Traditionally, coordination among signalized intersections for an arterial means finding the good offsets for each intersection. The control of the intersections along an arterial can also be coordinated by optimizing splits. Splits impact the capacity of an intersection. Similar to the highway, the capacity drop could cause growing queues. This work is based on the Virtual Phase-Link (VPL) model, a street traffic model designed for online traffic model predictive control, to obtain a top-down offline arterial signal timing. The VPL-based model can guarantee capacity consistency in intersections along an arterial. We, therefore, adopted the VPL-based model and developed an offline signal timing optimization approach. The proposed timing derived from the VPL-based offline signal timing optimization showed very good results in simulation. We also collected field experiment data, which demonstrated overall energy reductions and speed improvements on some sections of the study arterial.

47 OTHER INSTRUMENTATION↗

DIVA/DeviceEditor (DIVA) v5.1

The DIVA software interfaces a process in which researchers design their DNA with a web-based graphical user interface (DeviceEditor), submit their designs to a central queue, and a few weeks later receive their sequence-verified clonal constructs. Each researcher independently designs the DNA to be constructed with a web-based BioCAD tool, and presses a button to submit their designs to a central queue. Researchers have web-based access to their DNA design queues, and can track the progress of their submitted designs as they progress from "evaluation", to "waiting for reagents", to "in progress", to "complete". Researchers access their completed constructs through the central DNA repository. Along the way, all DNA construction success/failure rates are captured in a central database. his success/failure rate data can be leveraged to refine the DNA assembly design process.

Lane, Stephen↗

Utility-Scale Solar 2016: An Empirical Analysis of Project Cost, Performance, and Pricing Trends in the United States

The utility-scale solar sector has led the overall U.S. solar market in terms of installed capacity since 2012. In 2016, the utility-scale sector installed more than 2.5 times as much new capacity as did the residential and commercial sectors combined, and is expected to maintain its dominant position for at least another five years. This report—the fifth edition in an ongoing annual series—provides data-driven analysis of the utility-scale solar project fleet in the United States. We analyze not just installed project prices, but also operating costs, capacity factors, and power purchase agreement ("PPA") prices from a large sample of utility-scale PV and CSP projects throughout the United States. Highlights from this year's edition include the following: Installation Trends: The use of solar tracking devices dominated 2016 installations, at nearly 80% of all new capacity. In a reflection of the ongoing geographic expansion of the market beyond California and the Southwest, the median long-term average insolation level at newly built project sites declined again in 2016. While new fixed-tilt projects are now seen predominantly in less-sunny regions, tracking projects are increasingly pushing into these same regions. The median inverter loading ratio has stabilized in 2016 at 1.3 for both tracking and fixed-tilt projects. Installed Prices: Median installed PV project prices within a sizable sample have fallen by two-thirds since the 2007-2009 period, to $2.2/WAC (or $1.7/WDC) for projects completed in 2016. The lowest 20th percentile of projects within our 2016 sample were priced at or below $2.0/WAC, with the lowest-priced projects around $1.5/WAC. Overall price dispersion across the entire sample and across geographic regions decreased significantly in 2016. Operation and Maintenance (“O&M”) Costs: What limited empirical O&M cost data are publicly available suggest that PV O&M costs were in the neighborhood of $18/kWAC-year, or $8/MWh, in 2016. These numbers include only those costs incurred to directly operate and maintain the generating plant. Capacity Factors: The cumulative net AC capacity factors of individual PV projects range widely, from 15.4% to 35.5%, with a sample median of 26.3%. This project-level variation is based on a number of factors, including the strength of the solar resource at the project site, whether the array is mounted at a fixed-tilt or on a tracking mechanism, the inverter loading ratio, degradation, and curtailment. Changes in at least the first three of these factors drove mean capacity factors higher from 2010- to 2013-vintage projects, where they’ve remained fairly steady among both 2014- and 2015-vintage projects as an ongoing increase in the prevalence of tracking has been offset by a build-out of lower resource sites. Meanwhile, several of the newer CSP projects in the United States are struggling to match long-term performance expectations. PPA Prices: Driven by lower installed project prices and improving capacity factors, levelized PPA prices for utility-scale PV have fallen dramatically over time. Most recent PPAs in our sample are priced at or below $50/MWh levelized, with a few priced as aggressively as ~$30/MWh. Though impressive in pace and scale, these falling PPA prices have been offset to some degree by declining wholesale market value within high penetration markets like California, where in 2016 a MWh of solar generation was worth just 83% of a MWh of flat, round-the-clock generation. At the end of 2016, there were at least 121.4 GW of utility-scale solar power capacity within the interconnection queues across the nation. The growth within these queues is widely distributed across all regions of the country: California and the Southeast each account for 23% of the 83.3 GW of solar that first entered the queues in 2016, followed by the Northeast (17%), the Southwest (16%), the Central region (12%), Texas (6%) and the Northwest (3%). The widening geographic distribution of solar projects is a clear sign that the utility-scale market is maturing and expanding outside of its traditional high-insolation comfort zones.

14 SOLAR ENERGY↗

Utility-Scale Solar: Empirical Trends in Project Technology, Cost, Performance, and PPA Pricing in the United States – 2018 Edition

The utility-scale solar sector has led the overall U.S. solar market in terms of installed capacity since 2012. In 2017, the utility-scale sector accounted for nearly 60% of all new solar capacity, and is expected to maintain its market-leading position for at least another six years. Two-thirds of all states, representing all regions of the country, are now home to one or more utility-scale solar projects. This report—the sixth in an ongoing annual series—provides in-depth data-driven analysis of the utility-scale solar project fleet in the United States. Drawing on empirical project-level data from a wide range of sources, this report analyzes technology trends, installed project prices, operating costs, capacity factors, power purchase agreement ("PPA") prices, the levelized cost of solar energy (LCOE), and the market value of solar. Given its current preeminence in the market, utility-scale PV also dominates much of this report, though data from CPV and CSP projects are also presented where appropriate. Highlights from this year's edition include: -Installation and Technology Trends: The use of solar trackers dominated 2017 installations with nearly 80% of all new capacity. In a reflection of the ongoing geographic expansion of the market beyond California and the high-insolation Southwest, the median insolation level at newly built project sites declined again in 2017. While new fixed-tilt projects are now seen predominantly in less-sunny regions, tracking projects are increasingly pushing into these same regions. The median inverter loading ratio grew to 1.32 in 2017, allowing the inverters to operate closer to full capacity for a greater percentage of the day. -Installed Prices: Median installed PV project prices have steadily fallen by two-thirds since the 2007-2009 period, to $2.0/WAC (or $1.6/WDC) for projects completed in 2017. The lowest 20th percentile of projects within our 2017 sample were priced at or below $1.8/WAC, with the lowest-priced projects around $0.9/WAC. Overall price dispersion across the entire sample has decreased steadily every year since 2013; similarly, price variation across regions decreased in 2017. -Operation and Maintenance ("O&M") Costs: PV O&M costs were in the neighborhood of $16/kWAC-year, or $8/MWh, in 2017. These numbers include only those costs incurred to directly operate and maintain the generating plant. -Capacity Factors: The cumulative net AC capacity factors of individual projects vary widely, from 14.3% to 35.2%, with a sample median of 26.3%. This project-level variation is based on a number of factors, including the strength of the solar resource at the project site, whether the array is mounted at a fixed tilt or on a tracking mechanism, the inverter loading ratio, degradation, and curtailment. Changes in at least the first three of these factors drove mean capacity factors higher from 2010-vintage to 2013-vintage projects, where they've remained fairly steady among more-recent project vintages as an ongoing increase in the prevalence of tracking has been offset by a build-out of lower resource sites. -PPA Prices and LCOE: Driven by lower installed project prices and improving capacity factors, levelized PPA prices for utility-scale PV have fallen dramatically over time, by $20-$30/MWh per year on average from 2006 through 2012, with a smaller price decline of ~$10/MWh per year evident from 2013 through 2016. Most recent PPAs in our sample—including many outside of California and the Southwest—are priced at or below $40/MWh levelized (in real 2017 dollars), with a few priced as aggressively as ~$20/MWh. The median LCOE among operational PV projects in our sample has followed PPA prices lower, suggesting a relatively competitive market for PPAs. -Solar's Wholesale Energy Market Value: Falling PPA prices have been offset to some degree by a decline in the wholesale energy market value of solar within higher-penetration markets like California, where solar earned just 79% of the average price across all hours within CAISO's real-time wholesale energy market in 2017 (down from 125% back in 2012). In other markets with less solar penetration, however, solar's hourly generation profile still earns more than the average wholesale price (e.g., 127% in ERCOT, 112% in PJM). -Solar+Storage: Adding battery storage is one way to at least partially restore the value of solar, and three recent PV+storage PPAs in Nevada (each using 4-hour batteries sized at 25% of PV nameplate capacity) suggest that the incremental PPA price adder for storage has fallen to ~$5/MWh, down from ~$15/MWh just a year ago for a similarly configured project. As PV plus battery storage becomes more cost-effective, a number of developers are regularly offering it as a viable upgrade to standalone PV. At the end of 2017, there were at least 188.5 GW of utility-scale solar power capacity within the interconnection queues across the nation. The 2017 growth within these queues is widely distributed across all regions of the country, but is most pronounced in the up-and-coming Midwest region, which accounts for 27% of the 99.2 GW of new queue capacity. The widening geographic distribution is as clear of a sign as any that the utility-scale market is maturing and expanding outside of its traditional high-insolation comfort zones.

14 SOLAR ENERGY↗