Introduction

Languages and automata describe behavior of systems in terms of the possible sequences of actions or activities that they may exhibit. Markov Chains and, in general, stochastic and statistical models, introduce a quantitative sense of the likelihood of such sequences to occur. In this section we turn our attention to performance models that innately include a quantitative measure of time. This allows us to determine the measure of time it takes to complete certain actions. This way we can determine performance qualities such as makespan, latency or throughput.

We break the behavior of a system down into independent actions that each take their own, fixed, amount of time. To construct meaningful models from such actions we assume that actions may proceed concurrently, in general, but there may also be dependencies between activities that constrain their order of occurrence and therefore the progress that can be made. We further allow such models to have dependencies on input events, and to be able to produce events to their environments to model systems that produce outputs. We introduce a concrete model in which such systems can be expressed, namely, Timed Synchronous Dataflow models. We refer to them, in short, as SDF models. We show that, although SDF models are deterministic, they can effectively be used for worst-case performance analysis of systems that exhibit timing variations.

We introduce methods to study different aspects of their performance. For this we discuss their behavior (semantics). The mathematical framework in which to express the behavior of SDF graphs is max-plus algebra. We introduce this algebra and we study the essential properties of the class of max-plus-linear systems and how to use those properties to analyze SDF models. We discuss a particular, generic representation of max-plus-linear systems called the state-space representation and develop results to study throughput, latency and stability.

More information about the topics in this section are found in the cited references. More information on dataflow models can be found in (Bhattacharyya et al. 2018; Geilen et al. 2020). Background on max-plus algebra and max-plus-linear systems can be found in (Heidergott, Olsder, and Van Der Woude 2014; Baccelli et al. 1992; Schutter and Boom 2008; Schutter et al. 2020). Modelling of manufacturing systems and cyber-physical systems is discussed in (Basten et al. 2020). More about the modelling of railroad systems can be found in (Goverde 2007). The notes in this section are partially based on these works.