Automatic compile-time parallelization of logic programs for restricted, goal level, independent and parallelism

A framework for the automatic parallelization of (constraint) logic program s is proposed and proved correct. Intuitively, the parallelization process replaces conjunctions of literals with parallel expressions. Such expressio ns trigger at run-time the exploitation of restricted, goal-level, independ ent and parallelism. The parallelization process performs two steps. The fi rst one builds a conditional dependency graph (which can be simplified usin g compile-time analysis information), while the second transforms the resul ting graph into linear conditional expressions, the parallel expressions of the &-Prolog language. Several heuristic algorithms for the latter ("annot ation") process are proposed and proved correct. Algorithms are also given which determine if there is any loss of parallelism in the linearization pr ocess with respect to a proposed notion of maximal parallelism. Finally, a system is presented which implements the proposed approach. The performance of the different annotation algorithms is compared experimentally in this system by studying the time spent in parallelization and the effectiveness of the results in terms of speedups. (C) 1999 Elsevier Science Inc. All rig hts reserved.