Exercise 1: throughput analysis
Synchronous Dataflow Graphs (SDFGs) are often used to model time-constrained multimedia applications. They allow modeling of both pipelined streaming and cyclic dependencies between tasks. Furthermore, analysis techniques to study, for example, the throughput and storage requirements of an SDFG exist. The graph shown in the figure below models an MPEG-4 Simple Profile decoder. The nodes, called actors, communicate with tokens sent from one actor to another over the edges (called channels). The actors typically model application tasks and the channels model data or control dependencies. An essential property of SDFGs is that every time an actor fires (executes) it consumes the same amount of tokens from its input channels and produces the same amount of tokens on its output channels. These amounts are called the rates (indicated next to channel ends; rates equal to 1 are omitted for clarity). An actor can only fire if sufficient tokens are available on the channel from which it consumes. Tokens thus capture dependencies between actor firings. Such dependencies may originate from data dependencies, but also from dependencies on shared resources.

The rates determine how often actors have to fire with respect to each other such that productions and consumptions are balanced. These rates are constant, which forces an SDFG to execute in a fixed repetitive pattern, called an iteration. An iteration consists of a set of actor firings that have no net effect on the token distribution. These actor firings typically form a coherent collection of computations. An iteration could for example correspond to the processing of a frame in an audio or video stream. This makes iterations the natural granularity for defining scenarios, from the perspective of the application and from the perspective of the model. Note that subsequent iterations in an SDFG are allowed to overlap in time. Hence, different scenarios may be active simultaneously.
The dynamic behavior within an application can be captured in a set of scenarios. These scenarios can be modeled in an FSM-based Scenario-Aware Data-Flow (FSM-SADF) graph. Consider, as an example, the MPEG-4 decoder shown in the figure below which operates on frames with a QCIF resolution. The frame detector (FD) models the part of the application which determines the frame type and the number of macro blocks to decode. The modeled decoder supports two different types of frames (I or P). When a frame of type I is found, a total of 99 macro blocks must always be processed. This scenario is called I99. A frame of type P requires processing between 0 and 99 macro blocks. The workload varies considerably depending on the number of macro blocks which is processed. Therefore, a number of different scenarios Px are defined based on the number of macro blocks which must be processed. The graph contains different scenarios for the situations in which (up to) 0, 30, 40, 50, 60, 70, 80, or 99 macro blocks are processed for a single P frame. Within each scenario, the VLD and IDCT operations are performed for every individual block. The other operations are performed once per frame. Therefore, the communication rates vary with each scenario. As a consequence, x is set equal to the maximum number of macro blocks that may need to be processed in the scenario. Note that there is a trade-off between the number of scenarios, the run-time of the analysis techniques, and the implementation efficiency. A designer should consider this trade-off when selecting the scenarios and modeling the application.

In this exercise you will use the simple FSM-SADF graph shown in the figure below to illustrate how an FSM-SADF graph is described in XML. This graph contains three actors (P, Q, and R) and four channels (not named). The graph can execute in two scenarios (a and b). The FSM specifies that the graph always start with an execution of scenario a. After this first iteration, the graph may remain in scenario a or switch to scenario b.




The SDF3 tool sdf3analyze-fsmsadf offers several algorithms to compute the throughput of an FSM-SADF graph. In this tutorial you will use an algorithm called 'throughput-statespace'. This algorithm computes the maximal throughput that an FSM-SADF graph may reach when considering all possible scenario sequences (including the worst-case sequence).


The FSM (starting at line 67) specifies the possible scenario sequences. Currently, the graph will start with executing one iteration in scenario a. Afterwards it can remain in state q1 and execute scenario a once more or switch to state q2. In state q2, the graph will execute one iteration in scenario b and next it can choose to stay in this state or return to state q1. Using the FSM, a designer can specify possible scenario sequences as they may occur in the application.


Previous exercise | Next exercise