COWL: Copy-On-Write for Logic Programs

In order for parallel logic programming systems to be-come popular, they should serve the broadest range of ap-plications. To achieve this goal, designers of parallel logic programming systems would like to exploit maximum par-allelism for existing and novel applications, ideally by sup-porting both and-parallelism and or-parallelism. Unfortu-nately, the combination of both forms of parallelism is a hard problem, and available proposals cannot match the ef-ficiency of, say, or-parallel only systems. We propose a novel approach to And/Or Parallelism in logic programs. Our initial observation is that stack copy-ing, the most popular technique in or-parallel systems, does not work well with And/Or systems because memory man-agement is much more complex. Copying is also a sig-nificant problem in operating systems where the copy-on-write (COW) has been developed to address the problem. We demonstrate that this technique can also be applied to And/Or systems, and present both shared memory and dis-tributed shared memory designs. 1