Skiplist-based concurrent priority queues
N Shavit, I Lotan - Proceedings 14th International Parallel and …, 2000 - ieeexplore.ieee.org
This paper addresses the problem of designing scalable concurrent priority queues for large
scale multiprocessors machines with up to several hundred processors. Priority queues are …
scale multiprocessors machines with up to several hundred processors. Priority queues are …
Efficient stepping algorithms and implementations for parallel shortest paths
The single-source shortest-path (SSSP) problem is a notoriously hard problem in the
parallel context. In practice, the Δ-stepping algorithm of Meyer and Sanders has been widely …
parallel context. In practice, the Δ-stepping algorithm of Meyer and Sanders has been widely …
Multiqueues: Simple relaxed concurrent priority queues
H Rihani, P Sanders, R Dementiev - … of the 27th ACM symposium on …, 2015 - dl.acm.org
We present a simple, concurrent data structure that approximates the behavior of a priority
queue and that gives very good performance guarantees. We also discuss models for the …
queue and that gives very good performance guarantees. We also discuss models for the …
A parallel priority queue with constant time operations
GS Brodal, JL Träff, CD Zaroliagis - Journal of Parallel and Distributed …, 1998 - Elsevier
We present a parallel priority queue that supports the following operations in constant time:
parallel insertionof a sequence of elements ordered according to key, parallel decrease …
parallel insertionof a sequence of elements ordered according to key, parallel decrease …
Randomized priority queues for fast parallel access
P Sanders - Journal of Parallel and Distributed Computing, 1998 - Elsevier
We present simple randomized algorithms for parallel priority queues on distributed memory
machines. Inserting O (n) elements or deleting the O (n) out ofmsmallest elements …
machines. Inserting O (n) elements or deleting the O (n) out ofmsmallest elements …
Engineering multiqueues: Fast relaxed concurrent priority queues
Priority queues with parallel access are an attractive data structure for applications like
prioritized online scheduling, discrete event simulation, or greedy algorithms. However, a …
prioritized online scheduling, discrete event simulation, or greedy algorithms. However, a …
Implementation and analysis of distributed relaxed concurrent queues in remote memory access model
AA Paznikov, AD Anenkov - Procedia Computer Science, 2019 - Elsevier
Remote memory access (RMA) technique is a very attractive way for improving efficiency of
high-performance computations (HPC) and simplifying parallel program development …
high-performance computations (HPC) and simplifying parallel program development …
Multiqueues: Simpler, faster, and better relaxed concurrent priority queues
H Rihani, P Sanders, R Dementiev - arXiv preprint arXiv:1411.1209, 2014 - arxiv.org
Priority queues with parallel access are an attractive data structure for applications like
prioritized online scheduling, discrete event simulation, or branch-and-bound. However, a …
prioritized online scheduling, discrete event simulation, or branch-and-bound. However, a …
Optimal and load balanced mapping of parallel priority queues in hypercubes
SK Das, MC Pinotti, F Sarkar - IEEE Transactions on Parallel …, 1996 - ieeexplore.ieee.org
We efficiently map a priority queue on the hypercube architecture in a load balanced
manner, with no additional communication overhead, and present optimal parallel …
manner, with no additional communication overhead, and present optimal parallel …
Fast priority queues for parallel branch-and-bound
P Sanders - Parallel Algorithms for Irregularly Structured Problems …, 1995 - Springer
Currently used parallel best first branch-and-bound algorithms either suffer from contention
at a centralized priority queue or can only approximate the best first strategy. Bottleneck free …
at a centralized priority queue or can only approximate the best first strategy. Bottleneck free …