LR-algorithm: concurrent operations on priority queues
Rassul Ayani · 2002
The heap representation of priority queues is one of the most widely used methods. However, the conventional implementation tends to be inadequate for parallel applications. The paper proposes a new method, the LA-algorithm, which allows concurrent insertions on priority queues. In contrast to the conventional heap implementation, the LR-algorithm directs any two consecutive insertion requests to two different subtrees and thus provides a possibility to perform these insertions in parallel. The LR algorithm was implemented on a Sequent Symmetry shared memory multiprocessor. The obtained performance figures indicate that the algorithm is a promising approach.>