Parallel Inference Coordination

Origin. FGCP's Parallel Inference Machine (PIM); OR-parallel and AND-parallel execution models; research on granularity control and load balancing.

Mechanism. Inference tasks decompose into subtasks executable in parallel. OR-parallelism explores alternative clauses simultaneously; AND-parallelism solves subgoals of a conjunction simultaneously. The challenge is coordination: OR-parallel branches must manage variable bindings that diverge, and AND-parallel subgoals must synchronize on shared variables. Granularity control determines when parallel execution is worth its overhead.

Procedure. Identify independent subgoals (no shared unbound variables) — these can run AND-parallel. Identify alternative clauses — these can run OR-parallel. Estimate task granularity: if the subgoal is trivial, sequential execution beats coordination overhead. Assign tasks to processors with work-stealing for load balance. Merge results: AND-parallel results conjoin, OR-parallel results disjoin.

Applies to. Search problems, model checking, theorem proving, and any inference task with exploitable parallelism.

Limitations. Parallelism overhead exceeds gain when granularity is too fine. OR-parallelism requires copying environments or complex binding management, which dominates for deep searches. The FGCP discovered that parallelism in logic programming is harder to exploit than anticipated — most programs have limited parallelism, and the coordination costs often exceeded the parallel gains.