Or-parallel Prolog with heuristic task distribution

Abstract

An important determiner of the performance of or-patallel Prolog systems is the order in which the or-nodes in the computation tree are tried. Existing models of or-parallel Prolog select clauses for execution in much the same way as sequential systems do; clauses are tried chronologically (that is, in the order stated in the program) with the added advantage that some can be executed simultaneously on other processors. There is no attempt to examine clauses to assess their suitability in terms of finding answers or select those clauses that have low overhead in task migration for scheduling to other processors. Such systems do not exploit or-parallelism to the fullest and may sometimes have worse performance than sequential systems depending on the structure of the computation tree. Often in an or-parallel environment, it is more desirable to distribute nodes with larger work load to other processors leaving those nodes with lighter work load for local processing. This is so that scheduling costs, including task creation and task migration, are reduced and processors spend more time doing useful work. [8, 5] show that or-parallel Prolog systems are more suited to coarse-grain parallelism. We describe a method of gathering empirical data about clauses in the program. A heuristic function uses the data to deduce the relative “weights” of each clause and the system uses these “weights” to select the clauses for local processing or distributing to other processors.