Portable distributed priority queues with MPI

This paper analyzes the performance of portable distributed priority queues by examining the theoretical features required and comparing various implementations. In spite of intrinsic bottlenecks and induced hot-spots, we argue that tree topologies are attractive to manage the naturally centralized control required for the deletemin operation in order to detect the site which holds the item with the largest priority. We introduce an original perfect balancing to cope with the load variation due to the priority queue operations which continuously modify the overall number of items in the network. For comparison, we introduce the d-heap and the binomial distributed priority queue. The purpose of this experiment is to convey, through executions on a Cray-T3D and Meiko-T800, an understanding of the nature of distributed priority queues, the range of their concurrency and a comparison of their efficiency to reduce request latency. In particular, we show that the d-heap combines an adjustable degree with a small depth, which make it efficient in both theory and practice. The Message Passing Interface (MPI) provides the code with portability.