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.

Open your file browser (e.g., explorer, nautilus) and go to the folder '<path where you unpacked the archive>/hands-on/exercise 1'.
Open the file 'example.xml' in a text-editor and study the contents of this file.
What is the execution time of actor Q in scenario b?
Actor Q has an execution time of 3 time units in scenario b. This value is specified in the executionTime element on line 56 of the example.xml file.
What is the execution time of actor Q in scenario a?
Actor Q has an execution time of 2 time units in scenario a. This value is specified in the executionTime element on line 36 of the example.xml file. Note that this value is specified within the defaultProperties element. This means that this execution time will be used in all scenarios except for those scenarios that explicitly over-write this value. The execution time of actor Q in scenario b is an example in which the default value is over-written.
What is the first scenario which this graph will execute?
The FSM on line 67 specifies that its initial state is state q1. This state corresponds to an execution of scenario a (see line 68).

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).

Open a terminal (command window) and change the local directory to '<path where you unpacked the archive>/hands-on/exercise 1'.
Execute depending on your platform the following command:
../../sdf3/linux/sdf3analyze-fsmsadf --graph example.xml --algo throughput-statespace
or
..\..\sdf3\linux\sdf3analyze-fsmsadf --graph example.xml --algo throughput-statespace
What is the throughput of the graph?
The throughput of this graph is equal to 0.333333 iterations/time-unit. This means that a new iteration of the graph can (on average) be started once every 3 time-units. This throughput will be realized when the graph is constantly switching between scenarios a and b. When it would indefinitely remain in one of the two scenarios, it would be able to realize a higher throughput. This is something we will explore in more detail later.
Change the execution time of the actor R in scenario b from 1 time unit to 4 time units. (hint)
What is the throughput of the graph?
The throughput of this graph is now equal to 0.25 iterations/time-unit. When increasing the execution time of actor R in scenario b, the worst-case scenario corresponds to a continuous execution of scenario b.

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.

Let's assume that our application (FSM-SADF graph) always starts with executing two iterations in scenario b. Next, the application will continuously execute scenario a. Adapt the FSM to such that it incorporates this application knowledge. (hint)
What is the throughput of the graph?
The throughput of this graph is now equal to 0.4 iterations/time-unit. In this situation, the throughput depends only on the actor execution times in scenario a. Throughput is defined as the long-run average number of iterations per time-unit. In this long-run average, the transient (execution of scenario b) plays no role. Hence, the throughput will only depend on the behavior of the graph in scenario a.
Change the execution time of the actor Q in scenario b from 3 time unit to 300 time units. (hint)
Why does the throughput of the graph not change?
According to the FSM, the graph will initially execute scenario b twice and afterwards to will continuously execute scenario a. Remember that the throughput is defined as the long-run average number of iterations per time-unit. Hence, in our example the throughput depends only on the actor execution times in scenario a. The transient (execution of scenario b) plays no role in the long-run average number of iterations per time-unit. Hence, the throughput will only depend on the behavior of the graph in scenario a.

Previous exercise | Next exercise