Abstract
Language  English 

Qualification  Doctor of Philosophy 
Awarding Institution 

Supervisors/Advisors 

Award date  4 Jul 2008 
Place of Publication  Eindhoven 
Publisher  
Print ISBNs  9789038613154 
DOIs  
State  Published  2008 
Fingerprint
Cite this
}
Timing analysis of synchronous data flow graphs. / Ghamarian, A.H.
Eindhoven : Technische Universiteit Eindhoven, 2008. 107 p.Research output: Thesis › Phd Thesis 1 (Research TU/e / Graduation TU/e) › Academic
TY  THES
T1  Timing analysis of synchronous data flow graphs
AU  Ghamarian,A.H.
PY  2008
Y1  2008
N2  Consumer electronic systems are getting more and more complex. Consequently, their design is getting more complicated. Typical systems built today are made of different subsystems that work in parallel in order to meet the functional re quirements of the demanded applications. The types of applications running on such systems usually have inherent timing constraints which should be realized by the system. The analysis of timing guarantees for parallel systems is not a straightforward task. One important category of applications in consumer electronic devices are multimedia applications such as an MP3 player and an MPEG decoder/encoder. Predictable design is the prominent way of simultaneously managing the design complexity of these systems and providing timing guarantees. Timing guarantees cannot be obtained without using analyzable models of computation. Data flow models proved to be a suitable means for modeling and analysis of multimedia applications. Synchronous Data Flow Graphs (SDFGs) is a data flow model of computation that is traditionally used in the domain of Digital Signal Processing (DSP) platforms. Owing to the structural similarity between DSP and multimedia applications, SDFGs are suitable for modeling multimedia applications as well. Besides, various performance metrics can be analyzed using SDFGs. In fact, the combination of expressivity and analysis potential makes SDFGs very interesting in the domain of multimedia applications. This thesis contributes to SDFG analysis. We propose necessary and sufficient conditions to analyze the integrity of SDFGs and we provide techniques to capture prominent performance metrics, namely, throughput and latency. These perfor mance metrics together with the mentioned sanity checks (conditions) build an appropriate basis for the analysis of the timing behavior of modeled applications. An SDFG is a graph with actors as vertices and channels as edges. Actors represent basic parts of an application which need to be executed. Channels represent data dependencies between actors. Streaming applications essentially continue their execution indefinitely. Therefore, one of the key properties of an SDFG which models such an application is liveness, i.e., whether all actors can run infinitely often. For example, one is usually not interested in a system which completely or partially deadlocks. Another elementary requirement known as boundedness, is whether an implementation of an SDFG is feasible using a lim ited amount of memory. Necessary and sufficient conditions for liveness and the different types of boundedness are given, as well as algorithms for checking those conditions. Throughput analysis of SDFGs is an important step for verifying throughput requirements of concurrent realtime applications, for instance within designspace exploration activities. In fact, the main reason that SDFGs are used for mod eling multimedia applications is analysis of the worstcase throughput, as it is essential for providing timing guarantees. Analysis of SDFGs can be hard, since the worstcase complexity of analysis algorithms is often high. This is also true for throughput analysis. In particular, many algorithms involve a conversion to another kind of data flow graph, namely, a homogenous data flow graph, whose size can be exponentially larger than the size of the original graph and in practice often is much larger. The thesis presents a method for throughput analysis of SD FGs which is based on explicit statespace exploration, avoiding the mentioned conversion. The method, despite its worstcase complexity, works well in practice, while existing methods often fail. Since the statespace exploration method is akin to the simulation of the graph, the result can be easily obtained as a byproduct in existing simulation tools. In various contexts, such as designspace exploration or runtime reconfigu ration, many throughput computations are required for varying actor execution times. The computations need to be fast because typically very limited resources or time can be dedicated to the analysis. In this thesis, we present methods to compute throughput of an SDFG where execution times of actors can be param eters. As a result, the throughput of these graphs is obtained in the form of a function of these parameters. Calculation of throughput for different actor exe cution times is then merely an evaluation of this function for specific parameter values, which is much faster than the standard throughput analysis. Although throughput is a very useful performance indicator for concurrent realtime applications, another important metric is latency. Especially for appli cations such as video conferencing, telephony and games, latency beyond a certain limit cannot be tolerated. The final contribution of this thesis is an algorithm to determine the minimal achievable latency, providing an execution scheme for executing an SDFG with this latency. In addition, a heuristic is proposed for optimizing latency under a throughput constraint. This heuristic gives optimal latency and throughput results in most cases.
AB  Consumer electronic systems are getting more and more complex. Consequently, their design is getting more complicated. Typical systems built today are made of different subsystems that work in parallel in order to meet the functional re quirements of the demanded applications. The types of applications running on such systems usually have inherent timing constraints which should be realized by the system. The analysis of timing guarantees for parallel systems is not a straightforward task. One important category of applications in consumer electronic devices are multimedia applications such as an MP3 player and an MPEG decoder/encoder. Predictable design is the prominent way of simultaneously managing the design complexity of these systems and providing timing guarantees. Timing guarantees cannot be obtained without using analyzable models of computation. Data flow models proved to be a suitable means for modeling and analysis of multimedia applications. Synchronous Data Flow Graphs (SDFGs) is a data flow model of computation that is traditionally used in the domain of Digital Signal Processing (DSP) platforms. Owing to the structural similarity between DSP and multimedia applications, SDFGs are suitable for modeling multimedia applications as well. Besides, various performance metrics can be analyzed using SDFGs. In fact, the combination of expressivity and analysis potential makes SDFGs very interesting in the domain of multimedia applications. This thesis contributes to SDFG analysis. We propose necessary and sufficient conditions to analyze the integrity of SDFGs and we provide techniques to capture prominent performance metrics, namely, throughput and latency. These perfor mance metrics together with the mentioned sanity checks (conditions) build an appropriate basis for the analysis of the timing behavior of modeled applications. An SDFG is a graph with actors as vertices and channels as edges. Actors represent basic parts of an application which need to be executed. Channels represent data dependencies between actors. Streaming applications essentially continue their execution indefinitely. Therefore, one of the key properties of an SDFG which models such an application is liveness, i.e., whether all actors can run infinitely often. For example, one is usually not interested in a system which completely or partially deadlocks. Another elementary requirement known as boundedness, is whether an implementation of an SDFG is feasible using a lim ited amount of memory. Necessary and sufficient conditions for liveness and the different types of boundedness are given, as well as algorithms for checking those conditions. Throughput analysis of SDFGs is an important step for verifying throughput requirements of concurrent realtime applications, for instance within designspace exploration activities. In fact, the main reason that SDFGs are used for mod eling multimedia applications is analysis of the worstcase throughput, as it is essential for providing timing guarantees. Analysis of SDFGs can be hard, since the worstcase complexity of analysis algorithms is often high. This is also true for throughput analysis. In particular, many algorithms involve a conversion to another kind of data flow graph, namely, a homogenous data flow graph, whose size can be exponentially larger than the size of the original graph and in practice often is much larger. The thesis presents a method for throughput analysis of SD FGs which is based on explicit statespace exploration, avoiding the mentioned conversion. The method, despite its worstcase complexity, works well in practice, while existing methods often fail. Since the statespace exploration method is akin to the simulation of the graph, the result can be easily obtained as a byproduct in existing simulation tools. In various contexts, such as designspace exploration or runtime reconfigu ration, many throughput computations are required for varying actor execution times. The computations need to be fast because typically very limited resources or time can be dedicated to the analysis. In this thesis, we present methods to compute throughput of an SDFG where execution times of actors can be param eters. As a result, the throughput of these graphs is obtained in the form of a function of these parameters. Calculation of throughput for different actor exe cution times is then merely an evaluation of this function for specific parameter values, which is much faster than the standard throughput analysis. Although throughput is a very useful performance indicator for concurrent realtime applications, another important metric is latency. Especially for appli cations such as video conferencing, telephony and games, latency beyond a certain limit cannot be tolerated. The final contribution of this thesis is an algorithm to determine the minimal achievable latency, providing an execution scheme for executing an SDFG with this latency. In addition, a heuristic is proposed for optimizing latency under a throughput constraint. This heuristic gives optimal latency and throughput results in most cases.
U2  10.6100/IR635718
DO  10.6100/IR635718
M3  Phd Thesis 1 (Research TU/e / Graduation TU/e)
SN  9789038613154
PB  Technische Universiteit Eindhoven
CY  Eindhoven
ER 