Match Box: fine-grained parallelism at the match level
Mark W. Perlin, J.-M. DeBaud · 2003
Introduces Match Box, an 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 pattern matching algorithms. The idea is to precompare 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 join testing in constant time. It also finds application on conventional serial processors.>