Optimization schemas for parallel implementation of non-deterministic languages and systems

Naive parallel implementation of non-deterministic systems (such as a theor em proving system) and languages (such as logic, constraint, or concurrent constraint languages) can result in poor performance. We present three opti mization schemas, based on flattening of the computation tree, procrastinat ion of overheads, and sequentialization of computations that can be systema tically applied to parallel implementations of non-deterministic systems/la nguages to reduce the parallel overhead and to obtain improved efficiency o f parallel execution. The effectiveness of these schemas is illustrated by applying them to the ACE parallel logic programming system. The performance data presented show that considerable improvement in execution efficiency can be achieved. Copyright (C) 2001 John Wiley & Sons, Ltd.