Title :
Match Box: fine-grained parallelism at the match level
Author :
Perlin, Mark ; DeBaud, Jean-Marc
Author_Institution :
Carnegie-Mellon Univ., Pittsburgh, PA, USA
Abstract :
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
Keywords :
computational complexity; knowledge based systems; parallel algorithms; pattern recognition; search problems; Match Box; binding spaces; computationally intensive incremental join testing; fine-grained parallelism; forward-chaining production rules; incremental matching algorithm; massively parallel architecture; pattern matching; tuple instantiations; working memory monitoring; Computer science; Glass; Medical robotics; Monitoring; Parallel architectures; Parallel processing; Pattern matching; Performance evaluation; Production systems; Space exploration;
Conference_Titel :
Tools for Artificial Intelligence, 1989. Architectures, Languages and Algorithms, IEEE International Workshop on
Conference_Location :
Fairfax, VA
Print_ISBN :
0-8186-1984-8
DOI :
10.1109/TAI.1989.65350