Modular Performance Analysis of Cyclic Dataflow Graphs

Abstract

Applications for parallel and distributed embedded systems are often specified as dataflow graphs with dependency cycles. Examples of corresponding models of computation are marked graphs or synchronous data flow graphs. Performance analysis is often used in the exploration of different implementation alternatives or in order to provide guarantees on the timing behavior. This paper describes a new approach to the modular performance analysis of cyclic dataflow graphs such as SDF graphs as existing component-based analysis methods are not able to faithfully deal with cycles in the event flow. The new method results in tight bounds on essential quantities like buffer sizes, end-to-end delays and throughput. Because of the generality of the approach, one can analyze not only systems that can be modeled as marked graphs but also implementations that contain buffers with finite sizes, that produce system-wide back-pressure caused by blocking write semantics. The embedding of the novel approach into a modular performance analysis method allows the analysis of distributed implementations that use resource sharing mechanisms such as fixed-priority scheduling and TDMA. The paper presents the new models and methods as well as experimental results.