Finite-state machine-based scenario-aware dataflow (FSM-SADF) is a dynamic dataflow model of computation that combines streaming data and finite-state control. For the most part, it preserves the determinism of its underlying synchronous dataflow (SDF) concurrency model and only when necessary introduces the non-deterministic variation in terms of scenarios that are represented by SDF graphs. This puts FSM-SADF in a sweet spot in the trade-off space between expressiveness and analyzability.

Finite-state machine-based scenario-aware dataflow (FSM-SADF) is a dynamic non-deterministic dataflow model of computation that combines streaming data and finite-state control. However, FSM-SADF in its current state cannot be used in applications involving modeling and analysis of systems whose behavior depends on explicit values of timestamp of events. In this work we propose a compositional semantics for FSM-SADF that enables FSM-SADF to be used in modeling and analysis of such systems. We base the semantics of the composition on standard composition of processes with conditional rendezvous communication at the control level and the compositions of SDF graphs at the dataflow level. We evaluate the approach on a case study from the multimedia domain in the context of first come, first served schedulers.

A number of modeling approaches combining dataflow and finite-state machines (FSMs) have been proposed to capture applications that combine streaming data with finite control. FSM-based scenario-aware dataflow (FSM-SADF) is such an FSM/dataflow hybrid that occupies a sweet spot in the tradeoff between analyzability and expressiveness. However, the model suffers from compactness issues when the number of scenarios increases. This hampers its use in analysis of applications exposing high levels of data-dependent dynamics. In this paper, we address this problem by combining parameterized dataflow with finite control of FSM-SADF. We refer to the generalization as FSM-based parameterized SADF (FSM-πSADF). We introduce the formal semantics of the model, in terms of maxplus algebra and in particular max-plus automata. Thereafter, by leveraging the existing results of FSM-SADF, we propose a worst-case performance analysis framework for FSM-πSADF. We show that by using FSM-πSADF and its analysis framework, one can, unlike with FSM-SADF, compactly capture streaming applications exhibiting high levels of data-dependent dynamics in presence of finite control. Furthermore, we show that for practical models our analysis typically yields tighter bounds on worst-case performance indicators such as throughput and latency than the existing techniques based on conservative FSM-SADF modeling (if such modeling can be applied at all). We evaluate our approach on a realistic case-study from the multimedia domain.

Dynamic dataflow models of computation (MoCs) have been introduced to provide designers with enough expressive power to capture increasing levels of dynamism in modern streaming applications. Among dynamic dataflow MoCs, parametrized dataflow MoCs hold an important place as they integrate dynamic parameters and run-time adaptation of parameters in a structured way. In this work, we analyze the temporal behaviour of an important class of parametrized dataflow MoCs based on synchronous dataflow (SDF). We refer to such models as SDF-based parametrized dataflow (SDF-PDF). We show that our analysis allows to derive tighter worst-case throughput guarantees than the existing techniques. To achieve this, we introduce the (max,+) algebraic semantics of the model. Thereafter, we model run-time parameter adaptation using the theory of (max,+) automata, where the maximum cycle mean (MCM) analysis of the (max,+) automaton structure immediately yields the worst-case throughput value. We evaluate our approach on a representative case study from the multimedia domain.

The FSM-based scenario-aware data ow (FSM-SADF) model of computation has been introduced to facilitate the analysis of dynamic streaming applications. FSM-SADF interprets application's execution as an execution of a sequence of static modes of operation called scenarios. Each scenario is modeled using a synchronous data ow (SDF) graph (SDFG), while a finite-state machine (FSM) is used to encode scenario occurrence patterns. However, FSM-SADF can precisely capture only those dynamic applications whose behaviors can be abstracted into a reasonably sized set of scenarios (coarse-grained dynamism). Nevertheless, in many cases, the application may exhibit thousands or even millions of behaviours (fine-grained dynamism). In this work, we generalize the concept of FSM-SADF to one that is able to model dynamic applications exhibiting fine-grained dynamism. We achieve this by applying parametrization to the FSM-SADF's base model, i.e. SDF, and defining scenarios over parametrized SDFGs. We refer to the extension as parametrized FSM-SADF (PFSM-SADF). Thereafter, we present a novel and a fully parametric analysis technique that allows us to derive tight worst-case performance (throughput and latency) guarantees for PFSM-SADF specifications. We evaluate our approach on a realistic case-study from the multimedia domain.