Method for Graph-based Real-time Rule Scheduling in Multi-core Environment
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61562063)

  • Article
  • | |
  • Metrics
  • |
  • Reference [26]
  • |
  • Related
  • | | |
  • Comments
    Abstract:

    Safety-critical systems detect external events, match the targeted event patterns, and give timely responding actions; otherwise catastrophic results will be incurred. With the increasing demand for intelligence in the safety-critical systems, applying rule-based reasoning to these systems has become an inevitable trend. Besides, rule scheduling is the key to assure hard real-time constraints within rule-based reasoning solutions. In this study, a solution to the multi-core rule scheduling problem, named GBRRS (graph-based real-time rule scheduling), was proposed. With the real-time rule reasoning process analyzed, how rules in safety-critical systems can be modeled as tasks using the graph mapping is described first, and the graph-based end-to-end reasoning task model, E2ERTG, is proposed. Then, a multi-core scheduling algorithm, GBRRS, is presented to guarantee each rule's deadline via the control of the reasoning task's deadline. Simulation-based experiments have been conducted to evaluate the performance of GBRRS. The result shows that GBRRS remains a rule success ratio above 80% even with relatively high workload of the rule set and is superior to DM-EDF by average 13%~15% in terms of rule success ratio.

    Reference
    [1] John C. Safety critical system:Challenges and directions. In:Proc. of the 24th Int'l Conf. on Software Engineering. New York:IEEE, 2002. 547-550.[doi:10.1109/ICSE.2002.1007998]
    [2] Dean T, Boddy M. An analysis of time-dependent planning. In:Proc. of the 7th National Conf. on Artificial Intelligence. New York:IEEE, 1988. 49-54.
    [3] Garvey A, Lesser V. Design-to-time real-time scheduling. IEEE Trans. on Systems Man & Cybernetics, 1996,23(6):1491-1502.[doi:10.1109/21.257749]
    [4] Lesser V, Pavlin J, Durfee E. Approximate processing in real-time problem solving. AI Magazine, 1988,9(1):49-61.
    [5] Mouaddib A, Charpillet F, Haton J. GREAT:A model of progressive reasoning for real-time systems. In:Proc. of the 6th Int'l Conf. on Tools with Artificial Intelligence. New York:IEEE, 1994. 521-527.[doi:10.1109/TAI.1994.346447]
    [6] Kang J, Cheng A. Shortening matching time in OPS5 production systems. IEEE Trans. on Software Engineering, 2004,30(7):448-457.[doi:10.1109/TSE.2004.32]
    [7] Cheng A, Fujii S. Self-stabilizing real-time OPS5 production systems. IEEE Trans. on Knowledge and Data Engineering, 2004, 16(12):1543-1554.[doi:10.1109/TKDE.2004.95]
    [8] Li X, Qiao Y, Wang HA. A flexible event-condition-action rule processing mechanism based on a dynamically reconfigurable structure. In:Proc. of the 11th Int'l Conf. on Enterprise Information Systems. New York:IEEE, 2009. 328-329.[doi:10.5220/0001987402910294]
    [9] Li X, Qiao Y, Li X, Wang HA. Real-time ECA rule reasoning in active database. Journal of Computer Research and Development, 2010,47(1):250-258(in Chinese with English abstract).
    [10] Li N, Qiang G. Deadline-aware event scheduling for complex event processing systems. In:Proc. of the 14th Int'l Conf. on Intelligent Data Engineering and Automated Learning. New York:IEEE, 2013. 101-109.[doi:10.1007/978-3-642-41278-3_13]
    [11] Li N. Real-time sensor data stream processing with event-graph[Ph.D. Thesis]. Beijing:Institute of Automation, Chinese Academy of Sciences, 2014(in Chinese with English abstract).
    [12] Qiao Y, Zhong K, Wang HA, Li X. Developing event-condition-action rules in real-time active database. In:Proc. of the 2007 ACM Symp. on Applied Computing. New York:ACM Press, 2007. 511-516.[doi:10.1145/1244002.1244120]
    [13] Qiao Y, Li X, Wang HA, Zhong K. Real-time reasoning based on event-condition-action rules. In:Meersman R, Tari Z, Herrero P, eds. Proc. of the Move to Meaningful Internet Systems. Berlin:Springer-Verlag, 2008. 1-2.[doi:10.1007/978-3-540-88875-8_1]
    [14] Qiao Y, Han QN, Wang HA, Li X, Zhong K, Zhang KM, Liu J, Guo AX. RTRS:A novel real-time reasoning system based on active rules. ACM Applied Computing Review, 2013,13(2):66-76.[doi:10.1145/2505420.2505426]
    [15] Paschke A, Kozlenkov A. Rule-based event processing and reaction rules. In:Governatori G, Hall J, Paschke A, eds. Proc. of the Rule Interchange and Applications. Berlin:Springer-Verlag, 2009. 53-66.[doi:10.1007/978-3-642-04985-9_8]
    [16] Wang D, Rundensteiner E, Ellison RT, Wang H. Active complex event processing infrastructure:Monitoring and reacting to event streams. In:Proc. of the 29th Int'l Conf. on Data Engineering Workshops. New York:IEEE, 2011. 249-254.[doi:10.1109/ICDEW. 2011.5767635]
    [17] Mei Y, Madden S. ZStream:A cost-based query processor for adaptively detecting composite events. In:Proc. of the SIGMOD Int'l Conf. on Management of Data. New York:ACM Press, 2009. 193-206.[doi:10.1145/1559845.1559867]
    [18] Wu E, Diao Y, Rizvi S. High-performance complex event processing over stream. In:Proc. of the SIGMOD Int'l Conf. on Management of Data. New York:ACM Press, 2006. 407-418.[doi:10.1145/1142473.1142520]
    [19] Xiao F, Aritsugi M, Wang Q, Zhang R. Efficient processing of multiple nested event pattern queries over multi-dimensional event streams based on a triaxial hierarchical model. Artificial Intelligence in Medicine, 2016,72(1):56-71.[doi:10.1016/j.artmed.2016. 08.002]
    [20] Li X, Fan YS, Wang HA, Qiao Y. Estimation on worst-case execution time of real-time complex event processing. Journal of Computer Research and Development, 2012,49(10):2054-2065(in Chinese with English abstract).
    [21] Manabe Y, Aoyagi S. A feasibility decision algorithm for rate monotonic and deadline monotonic scheduling. Real-Time Systems, 1998,14(2):171-181.[doi:10.1023/A:1007964900035]
    [22] Li J, Luo Z, Ferry D, Agrawal K, Gill C, Lu CY. Global EDF scheduling for parallel real-time tasks. Real-Time Systems, 2015, 51(4):395-439.[doi:10.1007/s11241-014-9213-9]
    附中文参考文献:
    [9] 李想,乔颖,李欣,王宏安.主动数据库中的实时ECA实时规则推理算法.计算机研究与发展,2010,47(1):250-258.
    [11] 李娜.基于事件图的实时感知数据流处理[博士学位论文].北京:中国科学院自动化研究所,2014.
    [20] 李想,范玉顺,王宏安,乔颖.实时复杂事件处理的最坏响应时间估算.计算机研究与发展,2012,49(10):2054-2065.
    Related
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

王娟娟,乔颖,熊金泉,王宏安.多核环境下基于图模型的实时规则调度方法.软件学报,2019,30(2):481-494

Copy
Share
Article Metrics
  • Abstract:4122
  • PDF: 4791
  • HTML: 1578
  • Cited by: 0
History
  • Received:January 21,2017
  • Revised:May 02,2017
  • Online: July 20,2017
You are the first2032375Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063