Towards a parallel search for solutions of non-deterministic computations
In this paper we explore the possibilities to perform the search for results of non-deterministic computations in parallel. We present three different approaches to this problem: Dividing the search space statically, using a Bag of Tasks approach and using semi-explicit parallelism. Then we discuss their advantages and limitations. Finally, we discuss benchmarks using a monadic SAT solver as an example of a nontrivial application of a non-deterministic program.
Full Text: PDF