Event Count Automata: A State-based Model for Stream Processing Systems

Abstract

Recently there has been a growing interest in models and methods targeted towards the (co)design of stream processing applications; e.g. those for audio/video processing. Streams processed by such applications tend to be highly bursty and exhibit a high data-dependent variability in their processing requirements. As a result, classical event and service models such as periodic, sporadic, etc. can be overly pessimistic when dealing with such applications. In this talk, I will present a new model called Event Count Automata (ECA) for capturing the timing properties of such streams. Our model can be used to cleanly formulate properties relevant to stream processing on heterogeneous multiprocessor architectures, such as buffer overflow/underflow constraints. It can also provide the basis for developing analysis methods to compute delay/timing properties of the processed streams under different scheduling policies. Our ECAs, though similar in flavor to timed and hybrid automata, have a different semantics, are more light-weight, and are specifically suited for modeling stream processing applications and architectures. I will present the basic aspects of this model and illustrate its modeling potential. I will then apply it in a specific stream processing setting and present an analysis technique based on the formalism of Colored Petri Nets (CPNs). Finally, I will validate the model with the help of preliminary experimental results generated using the CPN simulation tool.

Bio

Samarjit Chakraborty is an Assistant Professor in the Department of Computer Science at the National University of Singapore. He obtained his Ph.D. from ETH Zurich in 2003. For his Ph.D. thesis, he received the ETH Medal and the European Design and Automation Association’s “Outstanding Doctoral Dissertation Award” in 2004. Samarjit’s research interests are primarily in the area of system-level design of real-time and embedded systems. He has served on the technical program committees of a number of conferences in the real-time embedded systems area, including CODES+ISSS, DATE, RTSS, ECRTS and RTCSA. He also served as the TPC Co-Chair of the 2006 IEEE Workshop on Embedded Systems for Real-Time Multimedia (ESTIMedia), which was held in Seoul in October this year.

TecMF: Samarijt2006 (last edited 2010-08-11 15:16:53 by localhost)