• DocumentCode
    2420698
  • Title

    Match Box: fine-grained parallelism at the match level

  • Author

    Perlin, Mark ; DeBaud, Jean-Marc

  • Author_Institution
    Carnegie-Mellon Univ., Pittsburgh, PA, USA
  • fYear
    1989
  • fDate
    23-25 Oct 1989
  • Firstpage
    428
  • Lastpage
    434
  • 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;
  • fLanguage
    English
  • Publisher
    ieee
  • 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
  • Type

    conf

  • DOI
    10.1109/TAI.1989.65350
  • Filename
    65350