Scheduling speculative work in MUSE and performance results

Citation:

Anon. Scheduling speculative work in MUSE and performance results. International Journal of Parallel Programming. 1992.

Abstract:

Work which may later be pruned is called speculative work. In this paper we present and evaluate a simple and efficient strategy, used in the Muse OR-parallel Prolog system, for better scheduling of speculative work. The strategy concentrates workers on the leftmost available work in the Prolog tree as long as there exists enough parallelism, thus emulating the sequential Prolog execution as much as possible. This strategy therefore makes it less probable that unnecessary work is executed. A new cut scheme that reduces the amount of speculative work is also presented. The performance results of our strategy are compared with the performance results of similar strategies implemented in the Aurora OR-parallel Prolog system. The comparison shows that our strategy performs quite well.