Forward Chaining Parallel Inference

Abstract

Rule based inference has demonstrated its applicability for a wide variety of domains. As users have grown more comfortable with this technology, the scope of attempted projects has grown from small laboratory demonstrations into massive real world time-critical systems. However, as the scope of systems has increased, execution speed has become unacceptable. One method of improving inference performance is parallelization. The parallelization of inference is not as straightforward as the parallelization of traditional numeric algorithms. Difficulties stem from the unpredictability of execution paths, small absolute task sizes, wide relative task size variances, and high proportion of shared volatile data. This paper describes the completed and ongoing efforts of the Parallel Inferencing Performance Evaluation and Refinement project (PIPER). PIPER Phase I produced an initial parallel inference engine (expert system tool kit) for the BBN Butterfly(registered trademark) Plus. Currently, PIPER Phase II is investigating parallel inference techniques on Thinking Machines' Connection Machine (CM) parallel computer. The Phase I inference engine is based on the Merit Enhanced Traversal Engine (METE) algorithm which is an extension of Forgy's (1979) RETE algorithm. To evaluate the efficacy of this design and implementation, an iterating 108 rule knowledge base was composed. This rule set was designed to roughly simulate the information rich nature of its target application domain, Strategic Defense Initiative contact discrimination, and was processed on from 7 to 85 Butterfly(registered trademark) Plus processor nodes. Three uniprocessor control groups were also employed to gauge speed-up. Using the control group which produced the most conservative speed-up factors, the Phase I inference engine achieved a maximum true speed-up in excess of 29 utilizing.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1990
Accession Number
ADA578291

Entities

People

  • Jay Labhart
  • Michael C. Rowe
  • Steve Carrow
  • Steve Matney

Tags

Communities of Interest

  • Materials and Manufacturing Processes
  • Space
  • Weapons Technologies

DTIC Thesaurus Topics

  • Aircrafts
  • Algorithms
  • Application Software
  • Computer Program Reliability
  • Computer Programming
  • Computer Programs
  • Computers
  • Expert Systems
  • Inference Engines
  • Language
  • Lepidoptera
  • Operating Systems
  • Parallel Computing
  • Parallel Processing
  • Parallel Processors
  • Programming Languages
  • Simulations

Fields of Study

  • Computer science

Readers

  • Aerospace Engineering
  • Artificial Intelligence
  • Parallel and Distributed Computing.

Technology Areas

  • AI & ML
  • AI & ML - Bayesian Inference