Event count automata: a state-based model for stream processing systems
Event count automata: a state-based model for stream processing systems
复制标题
DOI：
10.1109/rtss.2005.21
复制
发表时间：
2005-12
期刊：
影响因子：
--
通讯作者：
S. Chakraborty;L. T. Phan;P. Thiagarajan
中科院分区：
文献类型：
--
作者：
S. Chakraborty;L. T. Phan;P. Thiagarajan
最近，人们对针对流处理应用的(共同)设计的模型和方法越来越感兴趣；例如，那些用于音频/视频处理的模型和方法。由这类应用程序处理的流往往是高度突发性的，并且在其处理要求中表现出高度的数据依赖的可变性。因此，在处理此类应用程序时，经典的事件和服务模型(如周期性、偶发性等)可能过于悲观。在本文中，我们提出了一种新的模型，称为事件计数自动机(ECA)来捕获这类流的时间属性。我们的模型可以用来清晰地描述与异类多处理器体系结构上的流处理相关的属性，如缓冲区溢出/下溢约束。它还可以为开发分析方法以计算在不同调度策略下处理的流的延迟/定时属性提供基础。我们的ECA虽然在风格上类似于时间自动机和混合自动机，但具有不同的语义，更轻量级，特别适合对流处理应用程序和体系结构进行建模。我们介绍了该模型的基本方面，并说明了它的建模潜力。然后，我们将其应用于一个特定的流处理环境，并开发了一种基于着色Petri网(CPN)形式的分析技术。最后，通过使用CPN仿真工具生成的初步实验结果，验证了我们的建模和分析技术
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 paper, we 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. We present the basic aspects of this model and illustrate its modeling potential. We then apply it in a specific stream processing setting and develop an analysis technique based on the formalism of colored Petri nets (CPNs). Finally, we validate our modeling and analysis techniques with the help of preliminary experimental results generated using the CPN simulation tool