Search NASA⌕ Search

SEARCH · Search NASA

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 91 records · Page 5

Tandem Predictions for HPC Jobs

At the core of the predictive analytics applied to High Performance Computing (HPC), the most prominent tasks are the prediction of job runtimes and the prediction of job queue times, both of which have the potential for informing HPC users during their every-day decision making. Accurate runtime predictions can help users better choose so-called wallclock times at job submission, decreasing the odds of their jobs waiting in queues longer than necessary. The accurate and timely queue time predictions offered for the available partitions can inform the favorable selection of partitions for running jobs. This potential is well understood as we see in the abundance of research studies that propose solutions for these tasks, including the work published in the last several years. These tasks are seemingly receptive to the Machine Learning (ML) solutions, considering that there is no shortage of training data where HPC centers over time run millions and millions of jobs. However, we study the existing research literature, as well as look for examples in the toolchains supported on the exemplar HPC facilities, and, surprisingly, do not find any practical solutions that are ready to be adopted. We interpret this as a manifestation of the shortage of UX/UI efforts that support HPC analytics and also as a sign that the research has not come to the consensus on solving these tasks. In this study, we aim to shed new light on the long-running task of job queue time prediction by exploring the utility of runtime predictions in improving prediction accuracy and, actually, predicting these two metrics together, in tandem. In other words, we show how runtime predictions become valuable input in the queue time modeling. We challenge the existing approaches to feature engineering for the queue time prediction and describe promising results we obtained for a large dataset of HPC jobs from a supercomputer at the National Renewable Energy Laboratory.

HPC↗

Tandem Predictions for HPC Jobs: Preprint

At the core of the predictive analytics applied to High Performance Computing (HPC), the most prominent tasks are the prediction of job runtimes and the prediction of job queue times, both of which have the potential for informing HPC users during their every-day decision making. Accurate runtime predictions can help users better choose so-called wallclock times at job submission, decreasing the odds of their jobs waiting in queues longer than necessary. The accurate and timely queue time predictions offered for the available partitions can inform the favorable selection of partitions for running jobs. This potential is well understood as we see in the abundance of research studies that propose solutions for these tasks, including the work published in the last several years. These tasks are seemingly receptive to the Machine Learning (ML) solutions, considering that there is no shortage of training data where HPC centers over time run millions and millions of jobs. However, we study the existing research literature, as well as look for examples in the toolchains supported on the exemplar HPC facilities, and, surprisingly, do not find any practical solutions that are ready to be adopted. We interpret this as a manifestation of the shortage of UX/UI efforts that support HPC analytics and also as a sign that the research has not come to the consensus on solving these tasks. In this study, we aim to shed new light on the long-running task of job queue time prediction by exploring the utility of runtime predictions in improving prediction accuracy and, actually, predicting these two metrics together, in tandem. In other words, we show how runtime predictions become valuable input in the queue time modeling. We challenge the existing approaches to feature engineering for the queue time prediction and describe promising results we obtained for a large dataset of HPC jobs from a supercomputer at the National Renewable Energy Laboratory.

97 MATHEMATICS AND COMPUTING↗

Queued Up: 2025 Edition – Characteristics of Power Plants Seeking Transmission Interconnection As of the End of 2024 [Slides]

Electric transmission system operators (ISOs, RTOs, or utilities) require proposed power plants seeking to connect to the transmission grid to undergo a series of impact studies before they can be built. This process establishes what new transmission equipment or upgrades may be needed before a project can connect to the system and assigns the costs of that equipment. The lists of projects in this process are known as “interconnection queues”. In collaboration with interconnection.fyi, Berkeley Lab compiled, aggregated, and cleaned interconnection queue data from >50 transmission grid operators (7 ISO/RTOs and 49 non-ISO balancing areas), which collectively represent ~97% of currently installed U.S. electric generating capacity. The dataset includes requests submitted to queues through the end of 2024, and only includes requests seeking to connect to the transmission grid (not distribution-connected or behind-the-meter projects). The files below include both a PDF report and an Excel data file. The PDF report analyzes interconnection data and metrics through the end of 2024. The Excel data file includes (a) the full project-level interconnection queue dataset through 2024, (b) a codebook (data dictionary) describing each data field, and (c) 35 additional tabs featuring tables summarizing a range of interconnection metrics. Key highlights from the Queued Up: 2025 Edition (featuring data through 2024) include: • As of the end of 2024, there were ~10,300 projects actively seeking grid interconnection in the U.S., representing 1,400 GW of generation and approximately 890 GW of storage. • Historic withdrawal rates alongside relatively fewer new requests resulted in a 12% decrease in total active queue volume compared to the prior year. • Active natural gas capacity (136 GW, +72% year-over-year) increased in 2024, while solar (956 GW, -12%), storage (890 GW, -13%), and wind (271 GW, -26%) capacity decreased. • 408 GW of capacity already has a draft or executed interconnection agreement (IA) but has not yet reached commercial operations. • The time projects spend in queues before reaching COD is increasing. For the regions with available data, the median duration from IR to COD has doubled from <2 years for projects built in 2000-2007 to over 4 years for those built in 2018-2024. • Ultimately, most of this proposed capacity will not be built. Only 13% of capacity that submitted interconnection requests from 2000-2019 had reached commercial operations by the end of 2024; 77% of that capacity had been withdrawn and 10% was still active. • FERC Order 2023 and various other reforms are being implemented. These are important measures to reduce interconnection bottlenecks and enhance grid system reliability, but it is too early to measure and assess their full impact. • New additions for the 2025 edition include: (a) additional detail on data processing and gaps; (b) updates on interconnection reforms; (c) new analysis on interconnection agreements, and more.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Data Interconnection Exploration

This project involves innovating the way the Quality Assurance organization at the Jet Propulsion Laboratory (JPL) tracks the receiving inspection of JPL Critical Items (JCI) procured from suppliers. The Quality Assurance organization uses a Microsoft Access based front-end to enter items into an inspection queue. The current design has grown to be much more than was expected when the inspection queue system was created in 2007. The goal is to migrate to a web based solution that will allow the handling of more data, multiple input interfaces, and customizable display options. This has been achieved by implementing a divided tables scheme, the use of ColdFusion programming language, and the usage of Web 2.0 technologies such as AJAX and jQuery. These updates will allow for future expansion as well as the standardization of inspection queues for the Quality Assurance organization. When engineers and scientists order flight hardware, they cannot use it straight away. After a spacecraft or a satellite has been launched, it will be impossible to repair; therefore, the parts used must be inspected to make sure they are operating correctly and within the required specifications. The task of inspecting these JPL Critical Items (JCI) falls on the Quality Assurance organization. One of the tools the receiving inspection group uses is a database to maintain a queue of inspections that need to be done and of inspections that have been completed. The current Access interface has worked well but increased amounts of data, multiple input interfaces, and changes to how data is handled have made it necessary to seek a new way of organizing items for inspection. In addition, the different inspection groups have recently been merged and each has different ways of keeping track of inspection information. The ultimate goal is for the new group to have one shared inspection queue and website. To achieve this goal, I have been working with Ian Luczon of Procurement Quality Assurance and 3 Myers Hawkins, another intern, to not only create the new queue for receiving inspection but also a central web portal for the newly combined inspection group.

flight hardware↗

Buffered freepointer management memory system

A system and method of buffered freepointer management to handle burst traffic to fixed size structures in an external memory system. A circular queue stores implicitly linked free memory locations, along with an explicitly linked list in memory. The queue is updated at the head with newly released locations, and new locations from memory are added at the tail. When a freed location in the queue is reused, external memory need not be updated. When the queue is full, the system attempts to release some of the freepointers such as by dropping them if they are already linked, updating the linked list in memory only if those dropped are not already linked. Latency can be further reduced by loading new locations from memory when the queue is nearly empty, rather than waiting for empty condition, and by writing unlinked locations to memory when the queue is nearly full.

Jacob, Philip↗

DIVA/DeviceEditor (DIVA) v6.0.0

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. Once a design has been submitted to the queue, a small number of dedicated staff evaluate the design for feasibility and provide feedback to the responsible researcher if the design is either unreasonable (e.g., encompasses a combinatorial library of a billion constructs) or small design changes could significantly facilitate the downstream implementation process. The dedicated staff then use DNA assembly design automation software to optimize the DNA construction process for the design, leveraging existing parts from the DNA repository where possible and ordering synthetic DNA where necessary. Once all requisite process inputs are available, the design progresses from "waiting for reagents" to "in progress" in the design queue. Human-readable and machine-parseable DNA construction protocols output by the DNA assembly design automation software are then executed by the dedicated staff exploiting lab automation devices wherever possible. Since the all employed DNA construction methods are sequence-agnostic, standardized (utilize the same enzymatic master mixes and reaction conditions), completely independent DNA construction tasks can be aggregated into the same multi-well plates and pursued in parallel. The resulting sets of cloned constructs can then be screened by high-throughput next-gen sequencing platforms for sequence correctness. A combination of long read-length (e.g., PacBio) and paired-end read platforms (e.g., Illumina) would be exploited depending the particular task at hand (e.g., PacBio might be sufficient to screen a set of pooled constructs with significant gene divergence). Post sequence verification, designs for which at least one correct clone was identified will progress to a "complete" status, while designs for which no correct clones were identified will progress to a "failure" status. Depending on the failure mode (e.g., no transformants), and how many prior attempts/variations of assembly protocol have been already made for a given design, subsequent attempts may be made or the design can progress to a "permanent failure" state. All success and failure rate information will be captured during the process, including at which stage a given clonal construction procedure failed (e.g., no PCR product) and what the exact failure was (e.g. assembly piece 2 missing). This success/failure rate data can be leveraged to refine the DNA assembly design process.

Plahar, Hector↗

Performance modeling and measurement of real-time multiprocessors with time-shared buses

A closed queueing network model is constructed to address workload effects on computer performance for a highly reliable unibus multiprocessor used in real-time control. The queueing model consists of multiserver nodes and a nonpreemptive priority queue. Use of this model requires partitioning the workload into task classes. The time average steady-state solution of the queueing model directly produces useful results that are necessary in performance evaluation. The model is experimentally justified with the Fault-Tolerant Multiprocessor (FTMP) located at the NASA AIRLAB. Extensive experiments are performed on FTMP with a synthetic workload generator (SWG) to directly measure performance parameters, such as processor idle time, system bus contention, and task processing times. These measurements determine values for parameters in the queueing model. Experimental and analytic results are then compared.

Woodbury, Michael H.↗

A Queuing Theory Approach to Pilot-Controller Coordination for m:N Operations

In recent years, attention and interest by industry and researchers has grown in a control paradigm for remotely piloted aircraft termed “m:N operations.” In an m:N operation, a team of m remote pilots in command (RIPCs) collaboratively manage the flights of N aircraft. A consequence of an m:N concept of operations is that the RPICs will have to switch attention from one aircraft to another and from one task to another. Previous research in m:N operations has focused on the workload experienced by an RPIC and their level of situation awareness on their flights. Researchers have found that RPIC workload and situation awareness are generally sensitive to increasing N, although NASA’s Multi-Vehicle (m:N) Working Group has suggested that the driver of workload/situation awareness is the number of exceptions requiring human intervention as opposed to the value of N itself. In any case, a natural antecedent of workload is task load. In this paper, queueing theory is applied to a 1:N Urban Air Mobility (UAM) air taxi operation in order to estimate pilot task load for managing radio communications with air traffic controllers (ATCs) under increasing N. An M/M/1 queueing system is used to model the RIPC’s servicing of calls and clearance requests (e.g., departure, arrival, or airspace transition) to ATC for the N aircraft. Important parameters for the queueing model are the task arrival rate and the average service time for task completion. Radio communication times from past human-in-the-loop simulation studies are used to measure service times for a 1:4 and 1:12 UAM operation and to interpolate service times for 4 < N < 12. A Monte Carlo method is then employed, using the measured and interpolated service times, to estimate arrival rate and related queueing statistics. The paper concludes by considering the estimated queuing statistics, particularly the RPIC’s utilization (i.e., proportion of time actively servicing tasks), the length of the task queue over time, and the implications for task-balanced system design.

task load↗

Age class based arbitration

A system, includes a plurality of sub-queues. Each sub-queue is assigned to an age class of a sequence of age classes. A set of age thresholds divides the sub-queues. A queue manager places a received transaction into a sub-queue based on a comparison of an age of the received transaction to the set of age thresholds.

97 MATHEMATICS AND COMPUTING↗

Evaluating the impacts of Variable Message Signs on Airport Curbside Performance Using Microsimulation

Curbs play a vital role in facilitating vehicle access and egress for individuals at airports. Inefficiently allocating this resource hinders airport accessibility and productivity, resulting in congestion, longer travel times, and increased pollution. As airport demand fluctuates throughout the day and grows over time, airports face intensified curbside pressure. Yet, curb management research is significantly less robust at airports than in urban areas. Given the unbalanced nature of airport demand—riders tend to arrive simultaneously at specific entrances at certain hours—Variable Message Sign (VMS) arises as a cost-effective technology to divert vehicles from congested to underutilized curbs. Still, VMS implementation faces a significant challenge. Historically, airports have managed VMS heuristically and by intuition rather than an evidence-based approach. This research investigates the impacts of implementing VMS on curb performance at airports. By considering different driver compliance rates (DCR), we aim to determine when the sign should be turned on and off to diverge traffic to avoid undesired externalities while enhancing curb performance. Using a validated agent-based microsimulation model, VISSIM, we analyzed the Seattle-Tacoma (SeaTac) Airport as a case study. We modeled sixteen VMS management scenarios and a baseline where the message sign is not displayed, diverging vehicles between the departures and arrivals access levels at four different moments (early morning, morning, afternoon, and late night). We quantified the effects of VMS using seven metrics, including curb productivity index (CPI), curb accessibility (CA), queue length, queue duration, delay, vehicle counts, and emissions. The results of each scenario were compared against the baseline using absolute and relative changes and Repeated Measures ANOVA. Overall, VMS improved curb performance and traffic conditions at the airport, reducing emissions by 14.8% to 8.9%. Moreover, significant reductions in queue length (1,150 ft to 100 ft) and duration (15 to 144 minutes) were observed in the sending link under all VMS policies. However, impacts on the receiving link varied based on congestion, with significant increases in queue duration (9.8 to 24 min) when congested but no substantial changes in free flow. Notably, diverging vehicles to congested links resulted in non-significant results, and activating late and deactivating late VMS affected curb productivity (-5.8% to -61.4%), curb accessibility (-16.5% to -25.8%), cumulative counts (-33.4% to -59.4%), and vehicle delay (95.98% to 594.3%). Activating VMS before congestion begins in the sending link and deactivating before a queue forms in the receiving link yield the most significant improvements: 8.1% to 10.1% in CPI, 9.4% to9.6% in CA, -29.3% to -77.9% in total delay, -11.6% to -13.9% in total emissions, and 101% to 103% in cumulative counts. As the analysis was made with a wide range of time periods, access levels, driver compliance rates, and scenarios, we believe our findings can provide valuable insights into how airports should manage VMS. Our work introduces a novel approach to the scientific airport literature, as some of our metrics were previously unexplored. Additionally, we propose a methodology that other airports can adopt to maximize their curb performance.

Gutierrez, Jorge D.↗

Modeling and Control Using Stochastic Distribution Control Theory for Intersection Traffic Flow

In this work, we investigated stochastic distribution control theory-based traffic signal optimization to achieve a smooth and uniform flow of vehicles through signalized intersections. In this context, the static and linear dynamic stochastic distribution models were developed to express the relationship between the signal timing and the traffic queue length together with its probability density function. Two stochastic distribution control algorithms were designed to control the signal timing at intersections such that the probability density function of the traffic queue of each intersection road segment is made as narrow and as small as possible. Also, a recursive input-output traffic queue estimation model was proposed, which is data-driven and dynamic in nature, to calculate real-time traffic queue length using traffic signal timings and loop-detector data. The control algorithms were evaluated for a one-signal corridor, two-signal corridor, and 2 x 2 network of signalized intersections. MATLAB simulation examples are provided to demonstrate the use of the proposed algorithms and comparison to the existing widely-used semi-actuated control has been made. Desired results were obtained.

97 MATHEMATICS AND COMPUTING↗

Synthetic residential load models for smart city energy management simulations

The ability to control tens of thousands of residential electricity customers in a coordinated manner has the potential to enact system-wide electric load changes, such as reduce congestion and peak demand, among other benefits. To quantify the potential benefits of demand-side management and other power system simulation studies (e.g. home energy management, large-scale residential demand response), synthetic load datasets that accurately characterize the system load are required. This study designs a combined top-down and bottom-up approach for modelling individual residential customers and their individual electric assets, each possessing their own characteristics, using time-varying queueing models. The aggregation of all customer loads created by the queueing models represents a known city-sized load curve to be used in simulation studies. The three presented residential queueing load models use only publicly available data. An open-source Python tool to allow researchers to generate residential load data for their studies is also provided. The simulation results presented consider the ComEd region (utility company from Chicago, IL) and demonstrate the characteristics of the three proposed residential queueing load models, the impact of the choice of model parameters, and scalability performance of the Python tool.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Hybrid Power Plants: Status of Installed and Proposed Projects [Slides]

As battery prices fall and wind and solar generation rises, power plant developers are increasingly combining wind and solar projects with on-site batteries, creating “hybrid” power plants. But hybrid or co-located plants have been part of the U.S. electricity mix for decades, with widely ranging configurations that extend beyond pairing a generator with a battery. This new summary tracks and maps existing hybrid and co-located plants across the United States while also synthesizing data from generation interconnection queues to illustrate developer interest in the next wave of plants. The scope is inclusive of co-located hybrid plants that pair two or more generators and/or that pair generation with storage at a single point of interconnection, and also full hybrids that feature co-location and co-control. The focus is on larger, 1 MW+ systems: smaller (often behind-the-meter) projects are also increasingly common, but are not included in the data synthesis. Based in part on EIA Form 860 data, there were at least 125 co-located hybrid plants (>1 MW) already operating across the United States at the end of 2019, totaling over 14 GW of aggregate capacity. Some of the most common configurations include wind+storage (13 projects, 1,290 MW wind, 184 MW storage), PV+storage (40 projects, 882 MW PV, 169 MW storage), and fossil+storage (10 projects, 2,414 MW fossil, 91 MW storage). Data from interconnection queues demonstrates the considerable commercial interest that exists in hybrid power plants, especially solar co-located with storage. By the end of 2019, there were at least 367 GW of solar plants in the nation’s queues; 102 GW (~28%) of this capacity was proposed as a hybrid, most typically pairing PV with battery storage. For wind, 225 GW of capacity sat in the queues, with 11 GW (~5%) proposed as a hybrid, again most-often pairing wind with storage. The proposed solar+storage plants are located throughout the United States, but with California and the non-ISO West being the most prominent areas of commercial interest. Proposed wind+storage and standalone storage plants also center to a degree on these regions of the country.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Generator Interconnection Costs to the Transmission System in non-ISO Balancing Authorities [Slides]

Electric transmission system operators—including Independent System Operators (ISOs), Regional Transmission Organizations (RTOs), and utilities—require proposed power plants to undergo a series of interconnection studies before connecting to the grid. These studies assess what transmission upgrades or new infrastructure may be necessary and assign the associated costs to the project. Lawrence Berkeley National Laboratory has compiled, aggregated, and cleaned interconnection cost data, originally for ISOs/RTOs, and now for five non-ISO Balancing Authorities: PacifiCorp, Bonneville Power Authority, Duke Energy Progress, Duke Energy Carolinas and Duke Energy Florida. Insufficient transparency in interconnection cost data may contribute to rapidly expanding interconnection queues, with active queue capacities tripling between 2020 and 2024 in the studied BAs. Most projects withdraw after receiving high interconnection cost estimates. Interconnection costs have increased since the early 2000s, with average costs for "complete" projects reaching $194/kW between 2018 and 2024. Active queue projects and withdrawn projects incur substantially higher costs, primarily due to rising network upgrade costs. Recent interconnection costs in non-ISO balancing authorities are higher than in ISO regions, potentially due to a greater willingness to pay among developers. Utility-scale solar, wind, and storage projects have interconnection costs that exceed those for natural gas. However, when focusing on projects that do not withdraw from the queue, the interconnection costs for these technologies are more similar to natural gas projects. Other key findings include: (1) Larger generation projects benefit from lower proportional interconnection costs, (2) capacity transmission service (NRIS) often requires additional network investments, and (3) projects with high network upgrade costs are often clustered geographically. The dataset includes results from 2,104 interconnection studies conducted between 2000 and 2024, covering projects that are operational, withdrawn, or still progressing through the study process. The Excel file contains (a) the complete project-level interconnection cost dataset, and (b) seven additional tabs summarizing cost metrics across dimensions such as time, market structure, cost category (point of interconnection vs. broader network upgrades), fuel type, service type (ERIS vs. NRIS), generator size, and geography.

24 POWER TRANSMISSION AND DISTRIBUTION↗

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↗