And-or tree
From Wikipedia, the free encyclopedia
An and-or tree can be viewed as the parallel execution of a logic programming system. An and-or tree has or-nodes (choice points) and and-nodes. Or-nodes are created when there are multiple ways to solve a goal; and-nodes are created when a goal invokes several conjunctive subgoals.
[edit] Explanation
Non-determinismarises in many areas of computer science. Artificial intelligence and constrained optimization are two such areas where non-determinism is commonly found. By non-determinism we mean the existence of multiple (potential) solutions to a problem. Search problems, generate and test problems, constrained optimization problems, etc. fall in this class. Non-determinism has also been incorporated in many programming languages including the following salient examples:
- logic programming languages (e.g., Prolog)
- constraint programming languages
- concurrent constraint languages (e.g., AKL)
- rule based languages (e.g., OPS5)
Non-determinism present in a problem offers a rich source of parallelism. A problem is usually expressed as a goal to be achieved/proved/solved together with rules (or clauses) that specify how a given goal can be reduced into smaller subgoals. Given a (sub-)goal, there may be multiple ways of reducing it (non-determinism). On applying a rule, a (sub-)goal may reduce to a number of smaller (conjunctive) subgoals, each of which need to be solved in order to prove the original (sub-)goal. Two principal forms of parallelism can be exploited in problems that admit non-determinism:
- Or-parallelism The different potential solutions can be explored in parallel (i.e., given a subgoal, there may be more rules that can be used to reduce it).
- And-parallelism While looking for a specific solution, the different operations involved can be executed in parallel (i.e., conjunctive subgoals may be reduced in parallel).
Or-parallelism is a direct result of nondeterminism, while and-parallelism is the “traditional” form of parallelism, also found in standard (deterministic) programming languages. Solution of problems with non-determinism has been abstractly represented using and/or trees. Or-parallelism can be exploited by exploring the branches emanating from an or-node of this tree in parallel. Likewise, and-parallelism is exploited by exploring the branches emanating from and-nodes in parallel. A system that builds an and-or tree to solve a problem with non-determinism may look trivial to implement at first, but experience shows that it is quite a difficult task. A naive parallel implementation may lead to a slow down, or, may incur a severe overhead compared to a corresponding sequential system. Excessive parallel overhead may cause a naive parallel system to run many times slower on one processor compared to a similar sequential system.
