Estimation on Worst-Case Execution Time of Real-Time Complex Event Processing

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.