[ Bristol CS | Index ] One way to execute a program faster on a parallel computer is to allocate some processors to speculative computation: work which may prove to be unnecessary. However, this technique, speculative parallelism, requires the programmer to have some control over the physical processors in the machine, and is therefore not usually possible in high-level concurrent languages. This paper investigates the exploitation of speculative parallelism in concurrent logic programming languages. We propose a simple language extension that makes the technique possible, and illustrate its use in two applications: (1) the familiar branch-and-bound search algorithm, and (2) a new dynamic buffer protocol for interprocess communication. The new language feature has been implemented by extending the JAM Parallel Parlog system. The results of our experiments confirm that speculative parallelism can result in greater parallel speedups than is possible with other (divide and conquer) forms of parallelism alone.
The full paper is available in gzipped PostScript format.