Run-Time Prediction for Production Systems

Franz Barachini, Hans Mistelberger, Anoop GuptaAAAI 1992

Abstract

Predicting the execution time of production systems like RETE is challenging due to the inherent unpredictability of rule-based pattern matching. This paper presents a novel method for fine-grained, node-level statistical estimation of run-times. By tracking match probabilities at individual nodes within a data-flow network, the proposed approach achieves predictions accurate within a factor of two, providing a viable path for soft real-time guarantees in expert systems.

Introduction

In the early 1990s, expert systems were a cornerstone of AI, yet their practical application in safety-critical environments was limited by their unpredictability. Algorithms like RETE and TREAT, while efficient, are prone to "combinatorial explosions" where minor memory updates cause massive spikes in execution time. For real-time systems—such as power grid controllers or telecommunications networks—this variance is unacceptable.

Previous efforts to address this focused on hardware acceleration, which increases speed but does not improve predictability. This research shifts the focus toward forecasting execution time before rule execution, allowing systems to manage deadlines proactively by raising exceptions or switching to simpler strategies when a deadline is at risk.

Methodology: Node-Level Statistical Estimation

The core innovation of this work is moving away from coarse rule-level profiling toward granular, node-level statistics within the RETE network. Simple historical averaging fails because system states change significantly between runs.

Key Components

  • Token Flow Ratios ($p_k$): The system maintains the probability that a data "token" will successfully match at a specific node $k$.
  • Dynamic Updating Algorithms: Match probabilities are updated after each phase using three distinct algorithms (ALGO 1, 2, and 3). These algorithms apply different damping factors to balance historical data with recent system behavior.
  • Granular Estimation: Before processing a "plus-token" (data addition), the system calculates the expected number of matches and memory insertions across the network.
  • Hardware Calibration: The model is calibrated using micro-costs derived from a T800 Transputer, specifically accounting for equality tests (5 $\mu$s) and memory insertions (50 $\mu$s).
Extracted figure from page 6 of Run-Time Prediction for Production Systems

Experimental Evaluation

The method was evaluated across seven diverse production systems, ranging from academic benchmarks like the "Monkey and Bananas" problem (EMAB) and Rubik’s Cube solvers (RUBIK) to industrial applications in road maintenance (VAHINE) and alarm correlation for public switching systems (ALAMOS).

Key Results and Insights

The proposed method demonstrates that while rule-level behavior appears chaotic, node-level match probabilities are remarkably stable. By summing the predictable costs of individual node operations, the system generates a highly accurate overall estimate.

Performance Accuracy

In average cases, the system predicts run-time per rule and action with an error of less than a factor of two. For highly irregular rules, such as the "Goal" action in the RUBIK system, the method achieved better than 10% precision in over 90% of instances.

Real vs. estimated run-time (ms) across successive rule firings, demonstrating the model's ability to track performance fluctuations.

The "Context Switch" Challenge

A significant finding was the impact of "context switches"—points where the system's goal or state changes fundamentally (e.g., shifting from problem-solving to memory cleanup). These shifts temporarily invalidate historical probabilities, leading to transient prediction errors.

Conclusion and Future Work

This research provides a high-confidence estimation method suitable for "soft" real-time systems. However, several challenges remain. Predicting the total time for a sequence of rule firings remains difficult because the next rule to fire is not always known in advance. Future iterations could benefit from identifying specific Working Memory Elements (WMEs) that signal a goal shift, allowing the system to reset statistical expectations. Additionally, the prediction process adds approximately 50 $\mu$s per affected node, a cost that must be integrated into the system's deadline management.

Summary updated

BibTeX
@inproceedings{barachini1992run,
  author = {Franz Barachini and Hans Mistelberger and Anoop Gupta},
  title = {{Run-Time Prediction for Production Systems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}
Figure