TREAT - 1st Edition - ISBN: 9780273087939, 9781483258898


1st Edition

A New and Efficient Match Algorithm for AI Production System

Authors: Daniel P. Miranker
eBook ISBN: 9781483258898
Imprint: Morgan Kaufmann
Published Date: 1st January 1990
Page Count: 160
Sales tax will be calculated at check-out Price includes VAT/GST
Price includes VAT/GST

Institutional Subscription

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.


TREAT: A New and Efficient Match Algorithm for AI Production Systems describes the architecture and software systems embodying the DADO machine, a parallel tree-structured computer designed to provide significant performance improvements over serial computers of comparable hardware complexity in the execution of large expert systems implemented in production system form.

This book focuses on TREAT as a match algorithm for executing production systems that is presented and comparatively analyzed with the RETE match algorithm. TREAT, originally designed specifically for the DADO machine architecture, handles efficiently both temporally redundant and non-temporally redundant production system programs.

This publication is suitable for developers and specialists interested in match algorithms for AI production systems.

Table of Contents

1 Introduction

1.1 The Problem

1.2 Outline of the Book

1.3 Digest of Conclusions

2 Background

2.1 Production Systems

2.2 Characteristics of Computer Architectures

2.2.1 Fifth Generation Computers

2.2.2 MIMD and SIMD

2.2.3 Shared or Distributed Memory

2.2.4 Granularity

3 The Design of Production System Algorithms

3.1 The Correspondence Between Production Systems and Relational Databases

3.2 Three Issues in Parallel Production System Algorithms

3.2.1 Low-Level Matching

3.2.2 Partitioning and Distribution

3.2.3 Synchronization and Parallel Firing

3.3 The Development of Matching Algorithms

3.3.1 McDermott's Conjecture

3.4 The Details of the RETE Match

3.4.1 The RETE Algorithm

3.4.2 The RETE Match in Action

3.4.3 Advantages of the RETE Match

3.4.4 The Disadvantages of the RETE Match

4 TREAT: A New Match Algorithm

4.1 The Motivation for TREAT

4.2 Conflict Set Support

4.3 The TREAT Algorithm

4.3.1 Handling Negated Condition Elements

4.3.2 Detailed TREAT Algorithm

4.3.3 An Example of TREAT in Action

4.4 Dynamic Ordering of the Joins

4.4.1 Applicability of Relational Database Optimizations to TREAT

4.4.2 Seed-Ordering

4.4.3 Semijoin Reduction

4.4.4 Static Ordering

4.4.5 Partitioning Algorithms

4.4.6 Advantages of TREAT

4.4.7 Disadvantages of TREAT

4.5 Why TREAT is Expected to Perform Well

4.5.1 Counting the Comparisons for TREAT

4.5.2 Determining the Size of RETE Beta-Memories

4.5.3 Counting Comparisons for RETE

4.5.4 How the Bulk of the Rules Will Perform

4.6 Comparative Performance of TREAT and RETE on a Sequential Machine

4.6.1 Synopsis of the OPS5 Programs Used as Benchmarks

4.6.2 Counting Comparisons for Variable Bindings

4.7 Conclusion

5 The DADO Machine

5.1 The System Architecture

5.1.1 Backend Symbolic Matcher

5.1.2 Topology of the Interconnect

5.1.3 Operating Modes: SIMD as a Metaphor

5.1.4 Comparison to Other Tree Machines

5.1.5 The Naive DADO Algorithm for Production System Execution

5.2 The DADO Prototypes

5.2.1 DADO1 and DADO2

5.2.2 The DAD02 I/O Chip

5.3 Evaluation of Alternative Designs

5.3.1 Design Alternatives

5.3.2 Queuing Models of the Design Alternatives

5.3.3 Characterization of the SIMD Instruction Stream

5.3.4 Evaluation Method, RESQ2 Queuing Network Simulation Package

5.3.5 Evaluation Results

5.3.6 Performance Evaluation Conclusions

5.4 Programming DADO

5.4.1 The Layering of the DADO Software Environments

5.5 The EPROM Resident Kernel

5.6 PPL/M

5.6.1 Examples ofPPL/M

5.6.2 Tree Associative Operations

5.6.3 Language Problems to be Corrected in PPL/M and Future Potential DADO System Programming Languages

6 Other Parallel AI Machines

6.1 Semantic Net-Based Machines

6.1.1 NETL

6.1.2 The NETL Architecture

6.1.3 A Possible NETL Implementation

6.1.4 Effectiveness of NETL

6.1.5 The Connection Machine

6.1.6 Connection Machine Implementation

6.1.7 Effectiveness of the Connection Machine

6.2 Logic Based Machines

6.2.1 The Bagel

6.2.2 FAIM

6.2.3 Japanese Efforts

6.3 Parallel Lisps

6.3.1 Multilisp and Futures

6.3.2 Qlisp

6.3.3 Concurrent Common Lisp

6.3.4 Connection Machine Lisp

6.4 Discussion

7 The Parallel Implementation of OPS5 on DADO

7.1 Related Parallel Production System Efforts

7.1.1 Parallel Firing and Synchronization

7.1.2 Partitioning of Rule Systems

7.1.3 Parallelizing the RETE Match The RETE Match on the ILLIAC IV Gupta's Production System Machine

7.2 Limitations of OPS5 as a Production System Model

7.2.1 Production System Does Not Imply OPS5

7.2.2 Hashing Vs. Associative Processing

7.3 The Parallel Implementation of TREAT

7.3.1 Partitioning Methods, PM-Level and Full-Distribution

7.3.2 Outline of PM-Level TREAT Implementation on the DADO Machine

7.3.3 Implementation Efforts

7.4 Expected Performance

7.4.1 Method

7.5 Parallelism and the Three Phases of the Production System Cycle

7.5.1 Select Phase

7.5.2 Act

7.5.3 Match

7.5.4 Allocation of PEs

7.5.5 Performance Results

7.6 Conclusions

8 Conclusions and Future Research

8.1 Ongoing and Future Research

8.2 Conclusions

Appendix A LISP Code for Seed Ordered TREAT

Appendix B Implementation Outline for PM-level TREAT in PPSL


No. of pages:
© Morgan Kaufmann 1990
Morgan Kaufmann
eBook ISBN:

About the Author

Daniel P. Miranker

Ratings and Reviews