EQL Language, Graphs, Real Time Rule Based Systems, Runtime Optimization
Abstract
Abstract—Analyzing and reducing the execution-time upper bound of real-time rule-based expert systems is a very important task because of the stringent timing constraints imposed on this class of systems. This paper presents a new runtime optimization to reduce the execution-time upper bound of real-time rule-based expert systems. In order to determine rules to be evaluated at runtime, a predicate dependency list, which consists of a predicate, its active rule set and corresponding inactive rule set, is created for each predicate in a real-time rule-based program. Based on the predicate dependency list and the current value of each variable, the new runtime optimization dynamically selects rules to be evaluated at runtime. For the timing analysis of the proposed algorithm, the paper introduces a predicate-based rule dependency graph, a predicate-based enable-rule graph, and their construction algorithm. The paper also discusses the bounded time of the equational logic rule-based program using the predicate-based rule dependency graph as well as the predicate-based enable-rule graph. The implementation and performance evaluation of the proposed algorithm using both synthetic and practical real-time rule-bases programs are also presented. The performance evaluation shows that the runtime optimizer reduces the number of rule evaluations and predicate evaluations as well as the response time upper bound significantly, and the new algorithm yields better execution-time upper bound compared to other optimization methods.
1. J.-R. Chen, and A.M.K. Cheng, "Predicting the Response Time of Real-Time Rule-Based Programs with Variable-Expression
Assignments," Proc. Sixth IEEE CS Int'l Conf. Tools with Artificial Intelligence, pp. 297-303, 1994.
2. J.-R. Chen, and A.M.K. Cheng, "Predicting the Response Time of OPS5-style Production Systems," Proc. IEEE Conf. AI for Applications, Feb. 1995.
3. J.-R. Chen, and A.M.K. Cheng, "Response Time Analysis of EQL Real-Time Rule-Based Systems," IEEE Trans. Knowledge and Data Eng., vol. 7, no. 1, pp. 26-43, Feb. 1995.
4. A.M.K. Cheng, J.C. Browne, A.K. Mok, and R.-H. Wang, "Estella: A Language for Specifying Behavioral Constraint Assertions in Real-Time
Rule-Based Systems," Proc. Sixth Ann. IEEE Conf. Computer Assurance, June 1991.
5. A.M.K. Cheng, J.C. Browne, A.K. Mok, and R.-H. Wang, "Analysis of Real-Time Rule-Based Systems with Behavioral Constraint Assertions Specified
in Estella," IEEE Trans. Software Eng., vol. 19, no. 9, Sept. 1993.
6. A.M.K. Cheng, "Parallel Execution of Real-time Rule-based Systems," Proc. IEEE Int'l Parallel Processing Symp., pp. 779-789, Apr. 1993.
7. T. Ishida, "An Optimization Algorithm for Production Systems," IEEE Trans. Knowledge and Data Eng., vol. 6, no. 4, pp. 549-558, Aug. 1994.
8. D.P. Miranker, and B.J. Lofaso, "The Organization and Performance of a TREAT Based Production System Compiler," IEEE Trans. Knowledge and Data Eng., pp. 3-10, Mar. 1991.
9. D.P. Miranker, "TREAT: A New and Efficient Match Algorithm for AI Production Systems," Research Notes in AI, 1990.
10. Y.W. Wang, and E.N. Hanson, "A Performance Comparison of the RETE and TREAT Algorithms for Testing Database Rule
Conditions," Proc. IEEE Data Eng. Conf., pp. 88-97, 1992.
11. A.J. Pasik, "A Source-to-Source Transformation for Increasing Rule-Based System Parallelism," IEEE Trans. Knowledge and Data Eng., vol. 4, no. 4, pp. 336-343, Aug. 1992.
12. B. Zupan, and A.M.K. Cheng, "Optimization of Rule-Based Systems Using State Space Graphs," IEEE Trans. Knowledge and Data Eng., vol. 10, no. 2, Apr. 1998.
13. Y.-H. Lee, and A.M.K. Cheng, "Dynamic optimization for Real-Time Rule-Based Systems Using Predicate Dependency," Proc. IEEE Real-Time Technology and Applications Symp., June 2000.
14. C.K. Wang, A.K. Mok, and A.M.K. Cheng, "MRL: A Real-Time Rule-Based Production System," Proc. IEEE Real-Time Systems Symp., pp. 267-276, Dec. 1990.
15. C.L. Forgy, "RETE: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem," Artificial Intelligence, vol. 19, pp. 17-37, 1982.
16. D.P. Miranker, and D.A. Brant, "An Algorithmic Basis for Integrating Production Systems and Large Database," Proc. Sixth Int'l Conf. Data Eng., vol. 10, no. 2, pp. 353-360, Feb. 1990.
17. J.C. Browne, A.M.K. Cheng, and A.K. Mok, "Computer-Aided Design of Real-Time Rule-Based Decision Systems," technical report, Computer Science Dept., Univ. of Texas at Austin, 1988.
18. R.-H. Wang, and A.K. Mok, "Response-Time Bounds of Rule-Based Programs Under Rule Priority Structure," Proc. IEEE Real-Time Systems Symp., pp. 142-151, 1994.
19. M. Jarke, and J. Koch, "Query Optimization in Database Systems," Computing Surveys, vol. 16, no. 2, June 1984.
20. M. Cherniack, and S. Zdonik, "Changing the Rules: Transformations for Rule-Based Optimizers," Proc. ACM SIGMOD, June 1998.
21. A.J. Gonzalez, and D.D. Dankel, The Engineering of Knowledge-Based Systems. Prentice Hall, 1993.
22. J.J. Helly, "Distributed Expert System for Space Shuttle Flight Control," PhD dissertation, Dept. of Computer Science, Univ. of Calif. at Los Aangeles, 1984.
23. C.A. Marsh, "The ISA Expert System: A Prototype System for Failure Diagnosis on the Space Station," Mitre report, The MITRE Corporation, Houston, 1988.
