ANALYSIS OF OR-PARALLEL EXECUTION MODELS

We discuss fundamental limitations of or-parallel execution models of nondeterministic programming languages. Or-parallelism corresponds to the execution of different nondeterministic computational paths in par allel. A natural way to represent the state of (parallel) execution of a nondeterministic program is by means of an or-parallel tree. We ide ntify three important criteria that underlie the design of or-parallel implementations based on the or parallel tree: constant-time access t o variables, constant-time task creation. and constant-time task switc hing, where the term constant-time means that the time for these opera tions is independent of the number of nodes in the or-parallel tree, a s well as the size of each node. We prove that all three criteria cann ot be simultaneously satisfied by any or-parallel execution model base d on a finite number of processors but unbounded memory. We discuss in detail the application of our result to the class of logic programmin g languages and show how our result can serve as a useful way to categ orize the various or-parallel methods proposed in this field. We also discuss the suitability of different or-parallel implementation strate gies for different parallel architectures.