Annotation algorithms for unrestricted independent and-parallelism in logic programs

Abstract

We present two new algorithms which perform source-to-source transformations aimed at ex- ploiting goal-level, restricted independent and-parallelism. They rely on annotating the code with execution primitives which are simpler and more flexible than the well-known &/2 parallel execution operator. This makes it possible to generate better parallel expressions by exposing more potential parallelism among the literals of a clause than is possible with &/2. The algo- rithms we present differ on whether the order of the solutions obtained is preserved or not and on the use of determinism information. Finally, we compare the performance obtained by our approach with that of previous annotation algorithms and show that we can obtain relevant improvements.