TREAT

1 Introduction 1.1 The Problem 1.2 Outline of the Book 1.3 Digest of Conclusions2 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 Granularity3 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 Match4 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 Conclusion5 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 Languages6 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 Discussion7 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 7.1.3.1 The RETE Match on the ILLIAC IV 7.1.3.2 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 Conclusions8 Conclusions and Future Research 8.1 Ongoing and Future Research 8.2 ConclusionsAppendix A LISP Code for Seed Ordered TREATAppendix B Implementation Outline for PM-level TREAT in PPSL