The AND/OR process model can exploit both AND and OR parallelisms embedded in the logic program [Con83a]. One problem with this model is that it requires the excessive run time overhead for ordering the body literals. To reduce the run time overhead, most schemes fix the execution orders of body literals in compile time, which severely restrict the AND parallelism.
The AND/OR process model is modified to reduce the runtime overhead in this thesis. In the proposed model, the run time overhead for literal ordering is reduced by generating the execution orders in compile time. Several possible ordered lists are generated in compile time with several heuristic rules according to the possible input binding patterns and one of them is selected in run time to solve the body literals.
Because each ordered list can generate the proper data dependencies, the nearly optimal AND parallelism can be exploited, which is better than the other compile approaches. Though this approach may restrict AND parallelism in some cases, it can be compensated by reducing the run time overhead. The run time control for the forward and backward executions is managed simply and efficiently by a simple data structure.
