摘要
实时复杂事件处理系统(CEP系统)用于从原子事件流中检测出复杂事件,需要确保事件处理任务在截止期内完成.确保实时性的关键问题是如何估算系统中复杂事件处理程序(CEP程序)的最坏响应时间.现有针对一般程序的估算方法需要标注对象程序中子程序执行次数的取值范围.然而,CEP程序较为复杂,难以直接获知子程序执行次数的取值范围.虽然执行次数间存在关联关系,可以间接求解出取值范围,但这样得到取值范围不够严格,使估算精度较低,因此现有估算方法难以直接使用.提出一种CEP程序的最坏响应时间估算方法.采用新标注方式,通过对CEP程序的检测结构进行分析,归纳出子程序执行次数间的关联约束,并使用关联约束进行标注,替代了标注其取值范围,避免了标注困难.实验表明方法具有较高估算精度.
Real-time complex event processing （CEP） system is used to detect complex events from primitive event stream and must guarantee that the tasks of processing events can be completed in deadline. In order to guarantee that, a key problem is how to estimate the worst-case execution time （WCET） of the CEP program in a CEP system. In current WCET estimation methods for general programs, the range of the execution number of each sub-program needs to be annotated by developers. In a CEP program, however, ranges of execution numbers of sub-programs for detection of sub- event patterns are hard to directly obtain because of the complexity of CEP program. Although execution numbers of different sub-programs have relations and ranges can be solved from these relations, these ranges are still not strict enough, which will reduce the estimation accuracy. Thus current methods cannot accurately estimate the WCET of CEP programs. This paper presents a novel WCET estimation method for CEP program. In face of annotation difficulties, constraints among execution numbers of sub-programs are annotated, instead of ranges of these execution numbers. The constraints are generated from detection structures used by the CEP program. Results of simulations indicate that the method is effective and has higher accuracy.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2012年第10期2054-2065,共12页
Journal of Computer Research and Development
基金
国家自然科学基金项目(61033005
61174169)
国家"八六三"高技术研究发展计划基金项目(2012AA040915)
关键词
复杂事件处理
实时
最坏响应时间
标注
事件流
complex event processing
real-timel worst-case execution timel annotation
event stream
