IMPROVING THE EFFICIENCY OF NONDETERMINISTIC INDEPENDENT AND-PARALLELSYSTEMS

We present the design and implementation of the and-parallel component of ACE. ACE is a computational model for the full Prolog language tha t simultaneously exploits both or-parallelism and independent and-para llelism. A high-performance implementation of the ACE model has been r ealized and its performance reported in this paper. We discuss how som e of the standard problems which appear when implementing and-parallel systems are solved in ACE. We then propose a number of optimizations aimed at reducing the overheads and the increased memory consumption w hich occur in such systems when using previously proposed solutions. F inally, we present results from an implementation of ACE which include s the optimizations proposed. The results show that ACE exploits and-p arallelism with high efficiency and high speedups. Furthermore, they a lso show that the proposed optimizations, which are applicable to many other and-parallel systems, significantly decrease memory consumption and increase speedups and absolute performance both in forward execut ion and during backtracking. Copyright (C) 1996 Elsevier Science Ltd