Parallel execution strategies for conventional logic problems: A review

Abstract

Parallel execution strategies/or Prolog programs are reviewed. Three models, AOPM, APPNet and RAP are discussed in some detail. The AOPM and the APPNet are AND-OR parallel execution models and represent the two ends of the spectrum for approaches to AND-OR parallelism. The AOPM exploits fine-grained parallelism while the APPNet exploits coarse­-grained parallelism. RAP is an AND-parallel execution model and is based on fine-grained parallelism. The problem of shared variables in AND-parallelism is dealt with differently by each model. APPNet uses dependent AND-parallelism where streams of results are back-unified to eliminate inconsistent combinations of results. The AOPM and RAP use different approaches to independent AND-parallelism. Both models use intelligent backtracking to avoid the generation of inconsistent results. All three models have shown significant speed ups in the execution of Prolog programs.