On the analysis of synchronous dataflow graphs: a system-theoretic perspective

In the design of real-time systems, time forms a key requirement in a system’s specification. System designers must be able to verify whether a system meets its timing demands or not, e.g., whether it responds to input within a specific time window, or whether it is able to process data at a given rate. Synchronous data ow (SDF) graphs are models of computation that allow for conservative analysis of a system’s temporal dynamics. By assuming worst-case temporal behaviour for the system’s components, a temporal analysis translates to guarantees on the timing of the system. is potentially leads to an over-dimensioned system, where bu ers used for communication links may be larger and clock speeds may be higher than necessary. Different classes of SDF graphs exist. These classes vary in the richness of the properties that specify the behaviour of a graph. e richer these properties, the smaller the graph needed to express the same behaviour. As a result, the difficulty of the analysis of an SDF graph depends on its succinctness: the richer the properties of a graph, the more computationally demanding its analysis. In this thesis, we consider the following three classes, in order of increasing succinctness: homogeneous (HSDF), multi-rate (MRSDF, sometimes referred to as SDF) and cyclo-static (CSDF) synchronous data flow. Current approaches to the analysis of SDF graphs are divided into two main lines of thought. The first consists of those approaches that perform an exact analysis by considering the temporal dynamics of the graph at the nest possible level of granularity. As a result, the computed performance characteristics are tight: if the components of the system behave according to their worst-case behaviour, then the system’s performance matches the performance predicted by the model. Consequently, over-dimensioning of the system is kept to a minimum. A disadvantage of the approach is its scalability: while HSDF graphs may be analysed in polynomial time, for MRSDF and CSDF graphs, analysis has an exponential time complexity. Approaches that belong to the second line of thought are those that aim for a low computational complexity of the analysis, using approximation. To achieve this, they simplify the potentially complex patterns that compose the temporal behaviour of an SDF graph. This simplification is conservative: performance characteristics computed from this simplified behaviour are pessimistic with respect to the worst- case behaviour of the system. As a result, the system may be over-dimensioned to a larger extent when compared to an exact analysis. is is compensated by better scalability compared to exact methods, as it allows the three classes of dataflow to be analysed in polynomial time. With respect to accuracy and computational complexity, these two lines of thought are currently at different ends of a discontinuous spectrum. In case an exact analysis is computationally too expensive, the only alternative is a, possibly too coarse, conservative approximation. Likewise, the sole alternative to an overly pessimistic approximation is an exact analysis that may potentially be too costly. In this thesis, we develop a mathematical characterisation of SDF graphs that provides a basis for combining the two lines of thought described above. We view SDF graphs as linear discrete event systems, which may be described elegantly using a mathematical structure called max-plus algebra. The central conviction of this thesis is that this system theoretic perspective uni es current approximate and exact approaches, by allowing for incremental analysis, in which an initial rough estimate may be improved in a stepwise fashion, until the result is accurate enough. is approach to the analysis of synchronous data ow graphs consists of two main building blocks, the first of which is approximation: we present transformations of CSDF graphs into a pair of equally-sized HSDF graphs, which give a simplification of the temporal behaviour of the CSDF graph. These HSDF graphs, which we refer to as single-rate approximations, may be analysed efficiently, and their performance characteristics provide bounds on those of the CSDF graph. The second building block consists of graph transformations, which increase the level of detail of a specific part of the graph, by expanding it into a larger subgraph. This transformation generalises existing transformations, such as the construction of single-rate equivalents. Furthermore, it adds novel transformations, such as the construction of multi-rate equivalents: MRSDF graphs that express the same behaviour as the more succinct CSDF graphs. As an application of the theory presented in this thesis, we present two approaches to the computation of the throughput, which is a primary performance characteristic, of an multi-rate synchronous data ow (MRSDF) graph. Our first approach is an exact approach that exploits the structure of the single-rate equivalent of the graph, restricting the analysis to a subgraph. Our second approach combines the approximations and transformations into an incremental approach, which iteratively improves the accuracy of the analysis by partially unfolding critical actors. We validate the soundness of our approach to throughput analysis by applying it to a number of benchmark sets and case studies and comparing the results with current state-of-the art approaches. This comparison concerns the efficiency of our exact approach, and the validity of our incremental approach: our exact method computes the throughput of an SDF graphs in a fraction of the time required by state-of-the-art approaches, and our incremental approach trades o accuracy with size of the analysed graph.