Abstract
Original language  Undefined 

Awarding Institution 

Supervisors/Advisors 

Award date  5 Feb 2016 
Place of Publication  Enschede 
Publisher  
Print ISBNs  9789036540414 
DOIs  
Publication status  Published  5 Feb 2016 
Keywords
 IR99239
 Performance analysis
 METIS315411
 EWI27882
 Data flow
Cite this
}
On the analysis of synchronous dataflow graphs: a systemtheoretic perspective. / de Groote, Robert.
Enschede : 9789036540414, 2016. 222 p.Research output: Thesis › PhD Thesis  Research UT, graduation UT › Academic
TY  THES
T1  On the analysis of synchronous dataflow graphs: a systemtheoretic perspective
AU  de Groote, Robert
PY  2016/2/5
Y1  2016/2/5
N2  In the design of realtime 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 worstcase temporal behaviour for the system’s components, a temporal analysis translates to guarantees on the timing of the system. is potentially leads to an overdimensioned 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), multirate (MRSDF, sometimes referred to as SDF) and cyclostatic (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 worstcase behaviour, then the system’s performance matches the performance predicted by the model. Consequently, overdimensioning 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 overdimensioned 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 maxplus 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 equallysized HSDF graphs, which give a simplification of the temporal behaviour of the CSDF graph. These HSDF graphs, which we refer to as singlerate 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 singlerate equivalents. Furthermore, it adds novel transformations, such as the construction of multirate 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 multirate synchronous data ow (MRSDF) graph. Our first approach is an exact approach that exploits the structure of the singlerate 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 stateofthe 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 stateoftheart approaches, and our incremental approach trades o accuracy with size of the analysed graph.
AB  In the design of realtime 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 worstcase temporal behaviour for the system’s components, a temporal analysis translates to guarantees on the timing of the system. is potentially leads to an overdimensioned 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), multirate (MRSDF, sometimes referred to as SDF) and cyclostatic (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 worstcase behaviour, then the system’s performance matches the performance predicted by the model. Consequently, overdimensioning 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 overdimensioned 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 maxplus 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 equallysized HSDF graphs, which give a simplification of the temporal behaviour of the CSDF graph. These HSDF graphs, which we refer to as singlerate 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 singlerate equivalents. Furthermore, it adds novel transformations, such as the construction of multirate 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 multirate synchronous data ow (MRSDF) graph. Our first approach is an exact approach that exploits the structure of the singlerate 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 stateofthe 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 stateoftheart approaches, and our incremental approach trades o accuracy with size of the analysed graph.
KW  IR99239
KW  Performance analysis
KW  METIS315411
KW  EWI27882
KW  Data flow
U2  10.3990/1.9789036540414
DO  10.3990/1.9789036540414
M3  PhD Thesis  Research UT, graduation UT
SN  9789036540414
PB  9789036540414
CY  Enschede
ER 