Or-Parallel Prolog Execution on Clusters of Multicores

Abstract

Logic Programming languages, such as Prolog, provide an excellent  framework for the parallel execution of logic programs. In  particular, the inherent non-determinism in the way logic programs  are structured makes Prolog very attractive for the exploitation of  implicit parallelism. One of the most noticeable sources of implicit parallelism in Prolog programs is or-parallelism. Or-parallelism arises from the simultaneous evaluation of a subgoal call against the clauses that match that call. Arguably, the most successful model for or-parallelism is environment copying, that has been efficiently used in the implementation of or-parallel Prolog systems both on shared memory and distributed memory architectures. Nowadays, multicores and clusters of multicores are becoming the norm and, although, many  parallel Prolog systems have been developed in the past, to the best  of our knowledge, none of them was specially designed to explore the  combination of shared with distributed memory architectures. Motivated by our past experience, in designing and developing parallel Prolog systems based on environment copying, we propose a novel computational model to efficiently exploit implicit parallelism from large scale real-world applications specialized for the novel architectures based on clusters of multicores.