[MUSIC] When you're making coffee, it is important to know what the maximum throughput of your filter is. Otherwise, you might get a mess. Intuitively, the throughput is defined as how much stuff can we put through a filter per second. But if I put in water slowly, then it comes out slowly. And if I put it in fast, then it comes out faster, up to a certain maximum. So what is the throughput then? And what to think about the stuff that I put in that does not come out at all? I think it's a bit difficult to define, formally, what throughput is for systems like that. So this is the filter that we introduce as a running example for this week. Notice that I put on actors on the inputs and the outputs to avoid the loose consumption and production arrows. This one, actually, fits better to the formal definition. Now, if we're thinking about throughput of a single radiator flow graph like this, then it still depends on the interpretation whether throughput is a sensible notion at all. For example, if you would interpret the actor f as consuming tokens. Destroying them, throwing them away, doing something different for a while. And then making new tokens on its outputs, then there is no actual relation between the input and the output except for the time in between. And you cannot really speak about tokens going through so, what throughput doesn't really mean anything. But, of course, we are looking at this as we are interpreting it as a filter. And then the data packets that come in are the same but improved data packets when they come out. So then you can talk about throughput of a graph. Now what is the maximum throughput of a graph like this, and how can we calculate it? While there are still a few things that we have to keep in mind. For example, if you look at arbitrary systems such as the coffee. Then it could be that if you start putting in more, the throughput actually becomes less because things get blocked for example. That does not happen in a dataflow graph. A dataflow graph does not become faster or slower because it gets an overload of input, so that's a good thing for us that helps us calculate it. Another thing that helps us calculate the throughput is the fact that if there's one token coming in, there's also only one token coming out. That makes that there is a nice, even distribution and that we really can talk about throughput. And multi-rate dataflow for example, it's more difficult. If there were three tokens coming in and only one coming out, then do you define the throughput based on the input or on the output? It's a bit tricky. A single rate dataflow, we are fine there. So as it turns out for single rate dataflow, we can just look at the output of the system. Because if there is many tokens coming out of the output, well that means that also many tokens must have been coming in. Which means that the throughput is many tokens. If there's few coming out, few is coming in. And if we look at it the other way around. If we look at the input, if too many tokens are coming in, then still only a few may be trickling out on the output. And the rest gets buffered inside somehow so then the throughput is really what is coming out still and not so much what is coming in. So, for a single rate dataflow, and that we have already seen in the exercises of last week where we did some formalization. Is the average number of tokens that comes out of the dataflow graph per second. And we define that as the limit for arbitrarily long executions of the number of tokens at some point of execution divided by the time at that point of execution. And our goal is to prove that, that limit is larger than a certain amount t, which we're going to try to calculate. So, what is the maximum number of tokens that can come out of this dataflow graph per second? Well, let's assume that we have worst case response time for the actors and let's assume that we have eager processing. Then, we can look the cycles in the graph. In a previous week, we've seen that in a cycle like this, the number of tokens is constant. And we also know that well, if a token wants to go around in a cycle like this it has to pass all the actors. And each actor has a maximum firing time. If I add up the firing times of all these actors, then I get the time it takes for a token to go around. And I cannot guarantee that the graph will fire faster than that, so if I look at these L tokens and they all go around. Well they can be processed at the same time by the actor f. So this cycle determines that L divided by tau of f is a bound to what I can guarantee as a throughput. I cannot guarantee more than this. Because I know that this cycle is going to be slower than L tokens in tau f seconds. And if I look at this cycle up here, then g is going to be slower than K over tau g seconds. And because f depends on g, f is going to be slower than K over tau g as well. And then there is a third cycle. Which says that there is another bound namely M plus N over tau f plus tau g. And together these three form bounds on how fast the system can get. Let's clean that up, it says then that the average throughput is at least bounded by the minimum of these three numbers. Now in literature we actually calculate the cycle mean or the period of the graph rather than the throughput usually. And that just means that we divide the execution time of each cycle, divided through the number of tokens in the cycle, rather than the other way around. And that brings us to perhaps the most important definition of this whole week. And that's the maximum cycle mean of a graph. The maximum cycle mean is the maximum of all of the cycle means of each of the individual cycles in a graph. The reason why that definition is so important is because of the theorem that goes with it. Which says that the throughput at the output of an eagerly scheduled dataflow graph with worst-case response times is guaranteed to be higher than the minimum of the throughput guaranteed on the input. Because of course, you cannot have more coming out than is going in. The minimum of the throughput guaranteed on the input and one divided by the maximum cycle mean. In the next video, I am going to give you a formal proof of this theorem. Just using all the formalities that we introduced in the previous week. So, you can safely skip this if you are just interested in how to calculate performance for a graph. But if you want to know why this calculation is actually correct then I would really strongly advise you to try to completely understand the next video. It's going to be a long one. It's going to be a tough one, but it's going to be worth the trouble. >> [MUSIC]