The OR + AND modeling framework for parallel Prolog models
Philip Bitar, Charles R. Chen · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1990
This paper reports one of the fundamental challenges in the design of parallel Prolog execution models, which is to make available at runtime{emdash}to be used as needed{emdash} all useful AND and OR parallelism that is latent within a program. In order to accomplish this goal, the authors have developed the OR + AND modeling framework, which is based on a new tree representation, the OR + AND tree{emdash}the OR tree augmented by AND parallelism. The advantage of the OR + AND strategy is that certain solutions for the problems of binding for parallel execution, binding for fast serial execution, maintaining serial semantics (side effects), and scheduling parallel work can be obtained in the OR tree, in the context of OR parallelism, and then carried over to the OR + AND tree with little or no additional complexity. The authors illustrate the use of this framework by describing two models developed for shared-memory architecture: an improved window chain model, and an entirely new model, the ancestor/binding list model.