Proc. GKR 2013 Concurrent Reasoning with Inference Graphs

Since their popularity began to rise in the mid-2000s there has been significant growth in the number of multi-core and multi-processor com-puters available. Knowledge representation sys-tems using logical inference have been slow to em-brace this new technology. We present the con-cept of inference graphs, a natural deduction in-ference system which scales well on multi-core and multi-processor machines. Inference graphs enhance propositional graphs by treating proposi-tional nodes as tasks which can be scheduled to operate upon messages sent between nodes via the arcs that already exist as part of the propositional graph representation. The use of scheduling heuris-tics within a prioritized message passing architec-ture allows inference graphs to perform very well in forward, backward, bi-directional, and focused reasoning. Tests demonstrate the usefulness of our scheduling heuristics, and show significant speedup in both best case and worst case inference scenarios as the number of processors increases.