Exercise 2: modeling buffer sizes and analyzing buffer requirements
In this exercise you will be using the FSM-SADF graph shown in the figure below. This graph contains three actors P, Q, and R. Each actor has a self-edge with one initial token. The actors communicate with each other by sending tokens through the channels p2q and q2r. When implementing this graph in a real platform, memory space to store these tokens needs to be allocated for the channels p2q and q2r. In this exercise, you will explore how to model these buffer allocations in the FSM-SADF graph. You will also see that there is a trade-off between the buffer space assigned to a channel and the throughput that can be achieved.
Open your file browser and go to the folder '<path where you unpacked the archive>/hands-on/exercise 2'.
Open the file 'example.xml' in a text-editor and study the contents of this file.
The buffer size of a channel can be modeled in an FSM-SADF graph by adding for each channel a new channel that goes in the opposite direction. The rates on the newly added ports should be equal to the rates of the corresponding ports on the original channel. So, when modeling the buffer size of the channel p2q, you need to add a new port to actor P with rate 2 and a new port to actor Q with rate 3. Next, you can connect these two ports through a new channel which you could for example name q2p. The number of initial tokens on this new channel q2p equals the storage space of the original channel p2q. For example, when you put 4 initial tokens on the channel q2p you constrain the buffer size of the channel p2q to at most 4 tokens.
Add two channels to the example graph to model the buffer size of the channels p2q and q2r. The channel p2q should be assigned a buffer size of 4 tokens and the channel q2r should be assigned a buffer size of 2 tokens. (
hint)
- Add one input port to the actor P with rate 2.
- Add one output port to the actor Q with rate 3.
- Add one input port to the actor Q with rate 1.
- Add one output port to the actor R with rate 2.
- Add a new channel from the newly created input port of actor P to the newly created output port of actor Q. This channel should contain 4 initial tokens.
- Add a new channel from the newly created input port of actor Q to the newly created output port of actor R. This channel should contain 2 initial tokens.
Compute the throughput of the newly created graph using sdf3analyze-fsmsadf (
hint)
Use on linux:
../../sdf3/linux/sdf3analyze-fsmsadf --graph example.xml --algo throughput-statespace
Use on windows:
..\..\sdf3\windows\sdf3analyze-fsmsadf --graph example.xml --algo throughput-statespace
What is the throughput of the graph when constraining the buffer size of the channels p2q and q2r to respectively 4 and 2 tokens?
The throughput is equal to 0.142857 iterations/time-unit.
Change the buffer size assigned to channels p2q and q2r to respectively 80 and 40 tokens.
What is the throughput of the graph using these larger buffer sizes?
The throughput is equal to 0.25 iterations/time-unit.
This example shows that enlarging the buffer size of the channels allows the graph to reach a higher throughput. When implementing an application (i.e., an FSM-SADF graph) on a multiprocessor platform it is interesting to explore this trade-off between buffer sizes and throughput. Using this trade-off space, a designer can find the minimal buffer sizes needed to meet the throughput constraint of an application. In the next part of this exercise you will explore this trade-off space for our example graph.
Compute the throughput of the graph for all possible buffer sizes when varying the buffer size of the channel p2q between 4 and 8 initial tokens and varying the buffer size of channel q2r between 2 and 4 tokens. Put the results in the following table.
buffer size p2q |
buffer size q2r |
throughput |
4 |
2 |
? |
4 |
3 |
? |
4 |
4 |
? |
5 |
2 |
? |
5 |
3 |
? |
5 |
4 |
? |
6 |
2 |
? |
6 |
3 |
? |
6 |
4 |
? |
7 |
2 |
? |
7 |
3 |
? |
7 |
4 |
? |
8 |
2 |
? |
8 |
3 |
? |
8 |
4 |
? |
Plot the trade-off space between the total buffer size (sum of buffer sizes of both channels) versus the throughput. Can you explain why increasing the total buffer size leads to a larger throughput? Why does this effect stop from some buffer size onwards?

An actor can only fire (execute) when it has sufficient tokens on all its inputs. Remember that you modeled the buffer size of a channel by adding a new channel in the opposite direction. As a result, an actor needs to read tokens (which represent available buffer space) from this new channel. In fact, it needs to read as many tokens from this channel as it is going to produce on the original channel. Hence, the actor can only execute when there is buffer space available on its output channel.
Increasing buffer sizes may allow an actor to fire earlier as it no longer has to wait for buffer space to be freed by another actor. Hence, increasing the buffer sizes may lead to earlier executions of actors which in turn may lead to a larger throughput. However, at some point an actor or a group of actors will simply be limited by the speed at which they can perform their computation (i.e., they are limited by their execution time. From that moment onwards, it is no longer beneficial to increase the buffer sizes as this will not resolve the compute bottleneck which is limiting the throughput at that point.
Previous exercise | Next exercise