This paper addresses the problem of designing bounded range priority queues, that is, queues that support a fixed range of priorities. Bounded range priority queues are fundamental in the design of modern multiprocessor algorithms -- from the application level to lowest levels of the operating system kernel. While most of the available priority queue literature is directed at existing small-scale machines, we chose to evaluate algorithms on a broader concurrency scale using a simulated 256 node shared memory multiprocessor architecture similar to the MIT Alewife. Our empirical evidence suggests that the priority queue algorithms currently available in the literature do not scale. Based on these findings, we present two simple new algorithms, LinearFunnels and FunnelTree, that provide true scalability throughout the concurrency range. 1 Introduction Priority queues are a fundamental class of data structures used in the design of modern multiprocessor algorithms. Their uses range from ...

Sorting in one of a set of fundamental problems in computer saence.In this paper we present the first wait-free algorithm for sorting an input array of size N using P s N proceseom to achieve optimal running time.Known sorting algorithms, when made wait-flee through previously eskabliehed trsmsformation techniques have complexity O(logs N).The randomized algorithm we present here, when run in the CRCW PRAM model executes in optimal O(log N) time where P = N and O(N log N/P) otherwise.The wait-free property guarantees that the sort will complete despite any delays or failures incumed by the processors.This is a very desirable property from an operating systems point of view, since it allows oblivious thread scheduling as well as thread creation and deletion, without fear of losing the algorithm's correctness.We further present a variant of the algorithm which is shown to suffer no more than O(m) cent ention when rust Sy'tlChrOnOUd~.Sorting is a basic algorithmic building block and hm attracted the attention of many reeearchera.In this paper we present a wait-i%ee algorithm for sorting an ssmay of N elements, in the CRCW PRAM model with processor failures and undetectable restarts.Herlihy [17] defines a wait-free data structure M one on which any operation by any processor is guaranteed to complete within a bounded number of steps, regardless of the actions or failures of other proceesom.By extension, a wait-free algorithm for some iixed-size problem is guaranteed to arrive at the solution within a bounded "MIT and

Dijj%-acting trees are an effective and highly scalable distributed-parallel technique for shared counting and load balanc-We believe ourmodel and modeling approach open the way to steady-state analysis of other distributed-parallel structures such as counting networks and elimination trees.

Shared counters are among the most basic coordination structures in multiprocessor conputation, with applications ranging from barrier synchronization to concurrent-data-structure design. This article introduces diffracting trees, novel data structures for share counting and load balancing in a distributed/parallel environment. Empirical evidence, collected on a simulated distributed shared-memory machine and several simulated message-passing architectures, shows that diffracting trees scale better and are more robust than both combining trees and counting networks, currently the most effective known methods for implementing concurrent counters in software. The use of a randomized coordination method together with a combinatorial data structure overcomes the resiliency drawbacks of combining trees. Our simulations show that to handle the same load, diffracting trees and counting networks should have a similar widthw, yet the depth of a diffracting tree isO(logw), whereas counting networks have depthO(log2w). Diffracting trees have already been used to implement highly efficient producer/consumer queues, and we believe diffraction will prove to be an effective alternative paradigm to combining and queue-locking in the design of many concurrent data structures.

Shared counters are among the most basic coordination structures in multiprocessor computation, with applications ranging from barrier synchronization to dynamic load balancing. Introduced in this paper are diffracting trees, novel distributed-parallel data structures for shared counting. Diffracting trees combine a randomized coordination method together with a combinatorial data structure, to yield a logarithmic depth counter that improves on the log2 depth of counting networks, and overcomes the resiliency drawbacks of combining trees. Empirical evidence collected on a simulated distributed shared-memory multiprocessor shows that diffracting trees substantially outperform both combining trees and counting networks, currently the most effective known methods for shared counting. Not only do diffracting trees have higher throughput and lower latency, but unlike any known technique, their latency remains almost constant as the number of processors increases.