TY - GEN
T1 - Concurrent reasoning with inference graphs
AU - Schlegel, Daniel R.
AU - Shapiro, Stuart C.
PY - 2014
Y1 - 2014
N2 - Since their popularity began to rise in the mid-2000s there has been significant growth in the number of multi-core and multi-processor computers available. Knowledge representation systems using logical inference have been slow to embrace this new technology. We present the concept of inference graphs, a natural deduction inference system which scales well on multi-core and multi-processor machines. Inference graphs enhance propositional graphs by treating propositional 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 heuristics within a prioritized message passing architecture 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.
AB - Since their popularity began to rise in the mid-2000s there has been significant growth in the number of multi-core and multi-processor computers available. Knowledge representation systems using logical inference have been slow to embrace this new technology. We present the concept of inference graphs, a natural deduction inference system which scales well on multi-core and multi-processor machines. Inference graphs enhance propositional graphs by treating propositional 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 heuristics within a prioritized message passing architecture 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.
UR - https://www.scopus.com/pages/publications/84958523180
U2 - 10.1007/978-3-319-04534-4_10
DO - 10.1007/978-3-319-04534-4_10
M3 - Conference contribution
AN - SCOPUS:84958523180
SN - 9783319045337
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 138
EP - 164
BT - Graph Structures for Knowledge Representation and Reasoning - Third International Workshop, GKR 2013, Revised Selected Papers
PB - Springer Verlag
T2 - 3rd International Workshop on Graph Structures for Knowledge Representation and Reasoning, GKR 2013
Y2 - 3 August 2013 through 3 August 2013
ER -