Latency analysis of an eager schedule

Loading...

Do curso por EIT Digital

Quantitative Formal Modeling and Worst-Case Performance Analysis

36 ratings

EIT Digital

Quantitative Formal Modeling and Worst-Case Performance Analysis

36 ratings

Welcome to Quantitative Formal Modeling and Worst-Case Performance Analysis. In this course, you will learn about modeling and solving performance problems in a fashion popular in theoretical computer science, and generally train your abstract thinking skills. After finishing this course, you have learned to think about the behavior of systems in terms of token production and consumption, and you are able to formalize this thinking mathematically in terms of prefix orders and counting functions. You have learned about Petri-nets, about timing, and about scheduling of token consumption/production systems, and for the special class of Petri-nets known as single-rate dataflow graphs, you will know how to perform a worst-case analysis of basic performance metrics, like throughput, latency and buffering. Disclaimer: As you will notice, there is an abundance of small examples in this course, but at first sight there are not many industrial size systems being discussed. The reason for this is two-fold. Firstly, it is not my intention to teach you performance analysis skills up to the level of what you will need in industry. Rather, I would like to teach you to think about modeling and performance analysis in general and abstract terms, because that is what you will need to do whenever you encounter any performance analysis problem in the future. After all, abstract thinking is the most revered skill required for any academic-level job in any engineering discipline, and if you are able to phrase your problems mathematically, it will become easier for you to spot mistakes, to communicate your ideas with others, and you have already made a big step towards actually solving the problem. Secondly, although dataflow techniques are applicable and being used in industry, the subclass of single-rate dataflow is too restrictive to be of practical use in large modeling examples. The analysis principles of other dataflow techniques, however, are all based on single-rate dataflow. So this course is a good primer for any more advanced course on the topic. This course is part of the university course on Quantitative Evaluation of Embedded Systems (QEES) as given in the Embedded Systems master curriculum of the EIT-Digital university, and of the Dutch 3TU consortium consisting of TU/e (Eindhoven), TUD (Delft) and UT (Twente). The course material is exactly the same as the first three weeks of QEES, but the examination of QEES is at a slightly higher level of difficulty, which cannot (yet) be obtained in an online course.

Na lição

Performance analysis

In this module/week you will learn to exploit the structure of single-rate dataflow graphs to perform worst-case analysis of performance metrics like throughput, latency and buffering. After this week, you know how to calculate the maximum cycle mean of a dataflow graph, how to construct a periodic schedule for it, how to optimize this schedule for latency analysis, and how to determine the size of buffers with back-pressure such that the worst-case analysis remains valid. If you understood the material of the previous module/week, the proofs presented in this week will give you a deeper understanding of the mathematical underpinning of these methods.

Latency analysis of a periodic schedule6:55

Latency analysis of an eager schedule9:28

The formal definition of latency5:26

The boot-up time of a dataflow graph4:59

Optimizing latency estimates w.r.t. boot-up time5:33

Conheça os instrutores

Dr.ir. Pieter Cuijpers
Assistant Professor
Mathematics and Computer Science
Anne Remke
Prof. dr.
Computer Science

So, we know how to calculate the periodic schedule right?

And we know how to calculate a latency bound for it.

And I've claimed that that bound is going to be a bound on a eager schedule as well.

It's not so surprising because an eager schedule fires as soon as possible.

Which means that a periodic schedule can only fire later than that.

And so, a bound on the periodic schedule is also going to be a bound

on the eager schedule.

But can we actually prove that.

I would like to have a proof because I'm not so

sure if this still holds after a number of firings.

Maybe in an eager scheduling something happens along the way.

So, I would like a more rigorous proof.

Luckily, all the ingredients that we need for that proof are already available.

You may remember from the proof about the throughput.

That it was bounded by 1 over the maximum cycle mean of the graph.

That this formula, or this inequality.

Actually captures about on the production time of any arrow,

or the consumption time of any arrow has a similar bound.

And you will also remember that we could also iterate that bound over the graph.

So, if you were looking for a bound on the cert token coming out of the graph.

Then you could enter a pass back to find that

bound by just looking at the production times needed over

a pass but only considering paths that have in total have more tokens Then N.

So, in this case, more tokens than three.

What I actually discovered when I wanted to explain

how the latency bound worked is that you can also look at slightly different paths.

The principle is still the same, but

the thing is that it's not necessary to go over the total number of tokens.

If you go back through the graph, and you end up first here,

then you are still looking for

a q(1) and then if you would go this way, you would end up at the input.

So, we still need a path that lead to the input, but

if you would go this way they wouldn't then.

This buffer already has enough tokens in it to allow Q to fire immediately.

So, from the point of view of this buffer, the worst case response time of Q is zero.

The only thing is that Q is still being delayed by this pass going up here.

And from this point of view, so if you are here in the graph.

Then if you go back, you still have to look for r 2(1).

But each of the incoming buffers has at least one token in it.

So, the worst case response time of r 2 1

is going to be 0 because this first token can't be produced

immediately, or is going to be of r2, actually.

So, the consumption time is 0.

The production time of that one is going to be the production time of that actor.

Now, if we put that in a formula, at first we get this.

We get that the output is bounded by pass, which pass?

Well the pass from the input to P, and

along those parts we add up all the execution times of the actors.

And we take the worst-case response time of the input,

minus the number of tokens that were on the path.

And the other one, we take only the paths from p to q that are longest

in the sense that if you would take any longer paths, you would have to go

over this bound saying that, on the path there can only be n tokens.

And the fact that you start that path from an actor q,

that has enough tokens on the input, actually on all of its inputs,

means that this q(n- iota(X))

This number is actually smaller than the number of tokens that's available.

So q(n-i(X)) is going to be zero, because that one can fire immediately.

Except that you still have to add up the time of the actor, but that's in tau X.

And then 0 is actually going to be smaller than the offset

that was already there in the periodic schedule.

So, we can increase that with the offset and

then we can start looking at the Input, because on the input, we also had a bound.

The worst-case input bound we can also fill in.

And that one contains

the offset of the first actor that is involved in the periodic schedule.

And after that, you get this The input bound

which says that you will have at least a certain number of tokens per period.

Now, if we now look at what we have, then we have pause, with a certain length.

And what we can do is we can eliminate all the cycles from those paths.

So, we split up a path into all the cycles in the path and

goes on straight which looks like this.

And then the cycles in the path for that we know something.

Namely, we know that the execution time in the cycle

is going to be less than the maximum cycle mean.

Or the number tokens in the cycle times the maximum cycle mean.

So, we can replace that by a formula holding the maximum cycle mean.

And And maximum cycle mean

by construction is smaller than the period of the schedule.

So, we can increase the bound a little big

further by filling in the period of the schedule.

Now, because the number of tokens in.

The cycles is less than the total number of tokens in the path,

and so we now have the rest of the parts was called x.

So, the number of so tokens in the total

path was going to be n minus x.

The number of tokens in the cycle has to be less than n minus yotta x,

which means that we can replace the number of tokens,

here by n minus yotta x, and then we've still increased the amount.

And then we can merge the two formulas, actually,

because they now Have become the same.

And if we merge them, then this

is actually very familiar because it is the formula that we used

to construct one step When we were doing the construction of the periodic schedule.

Because in the periodic schedule, we said that the offset of

p had to be larger than the offset of

any actor before in the In the graph

plus the number of tokens times the period that you needed to get to that actor

minus the execution time plus the number of tokens that you need to get to that

actor minus the execution time, and if you iterate that over path,

you get this formula, which means that if you fill in this here,

then here we actually get t p.

And then, this crosses out that part and this crosses out that part,

so we only get plus n t.

In short, the output time

is going to be less than the offset of the output actor plus and times the period.

And that's exactly the output time of the periodic schedule.

So, now you know that the output of a periodic schedule is indeed going to be

later always than the output of the eager schedule, and

since the input has not changed, that means that the latency is also going

to be later than the latency of an eager schedule,

which means that the latency bound still works for eager schedules.

[MUSIC]

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2018 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play