优先队列的并行插入和删除

Concurrent Insertion and Deletion for Priority Queues

优先队列广泛地使用在许多并行算法中(例如,多处理机调度和某些组合优化算法)。在这些算法中,共享优先队列的存取冲突限制了加速比的提高。本文提出一种链表优先队列的并行插入和删除方法,具有较小并行开销和较大的并行度,并且保证和串行存取算法的优先顺序完全一致,即删除操作返回已经插入和正在插入的所有元素中的最佳元素。同时,我们还介绍了目前性能最好的堆的并行插入和删除算法,并对准和链表结构并行插入和删除算法的性能和适用范围进行了比较,进一步提出了散列结构的优先队列。在ENCORE Multimax520多处理机上的实验结果验证了我们的理论分析结果:使用链表结构的并行分枝限界算法性能上可获得很大提高。

Priority queues are widely used in many parallel algorithms,e.g.,multiprocessor sche- duling and some combinatorial search algorithms.But the speedups of these algorithms are often limi- ted by the access conflict of shared priority queues.In this paper,we design a concurrent insertion and deletion algorithm for linear list priority queues,with less overhead,to achieve more parallelism. The algorithm assures that the priority order of queue is the same as that of the sequential algorithm, i.e.,deletion operation returns the best one of all elements inserted and being inserted.We also int- roduce the most efficient concurrent insertion and deletion algosithm of heap structure,and compare its efficiency and scope with that of linear lists.On this basis,we propose the structure of hash list priority queue to overcome the shortcomings of linear lists.The experiments on ENCORE Multimax 520 multiprocessor has verified the results of theoretical analysis:Using linear list priority queue can greatly improve the efficiency of parallel branch and bound algorithms.