Carnegie Mellon University
file.pdf (732.07 kB)
Download file

The Match Box algorithm for parallel production system match

Download (732.07 kB)
journal contribution
posted on 2008-05-01, 00:00 authored by Mark W. Perlin
Abstract: "We introduce Match Box, a new incremental matching algorithm for determining the tuple instantiations of forward-chaining production rules. Match Box is rooted in the mathematical interconnections between tuple and binding spaces, a framework also applicable to other matching algorithms. The idea is to precompute a rule's binding space, and then have each binding independently monitor working memory for the incremental formation of tuple instantiations. A key feature of Match Box is that on a massively parallel architecture, it can perform a rule's computationally intensive incremental joint testing in constant time. It also finds application on conventional serial processors."




Usage metrics