An application of program unification to priority queue vectorization (Q685093)

Priority queues are well-known discrete structures in computer science applications, their most popular use is the area of event-scheduling in simulation, in particular, discrete event simulation. Usually the attention is concentrated on scalar uniprocessing or multiprocessing of a single priority queue, when the underlying application is assumed to be a single simulation, generating a single sample-path of the stochastic process. In contrast the paper focusses on using vector machines to generate several sample-paths in parallel. The tool used to achieve this is the technique of program unification which allows the transformation of a sequential program into unified vector program. For ease of explanation the authors restrict their attention to a very special implementation called the heap or implicit heap, determine factors which affect execution speedup and attempt to give a rough justification for why the implicit heap has a better performance then the skew heap both theoretically and using some experimental data. For the purpose of comparing the performance of various queue implementations the ``hold model'' is used. While it is easy to show that the hold model assumptions are not true in general models, it is still a useful device since it enables us to obtain measurements in a simple but meaningful framework incorporating some reasonable amount of randomness; random enough to be useful, but yet not random enough to make the model results too complicated to interpret. The two key parameters that affect the performance of the hold model are the size of the priority queue and the probability distribution used to generate the times-to-occurence for events. There are considered distributions with very different standard deviations to mean ratios: exponential distribution, the mixture of two exponentials, and four-stage Erlang. The project was undertaken to determine if any one particular priority queue implementation would perform uniformly better than the other through program unification on a vector machine.