Causality, choice and concurrency (modeling patterns)

Loading...

來自 EIT Digital 的課程

Quantitative Formal Modeling and Worst-Case Performance Analysis

39 個評分

EIT Digital

Quantitative Formal Modeling and Worst-Case Performance Analysis

39 個評分

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.

從本節課中

Modeling systems as token consumption/production systems

In this module/week you will learn to draw a model of a token consumption/production system, and communicate your interpretation of this model with others in an informal manner. At the end of this model, you will be able to draw your own models, and explain your interpretation of them in general terms. Also, you will know about the standard Petri-net interpretation of consumption/production systems, and will be able to point out particular patterns in Petri-net models. Finally, you will be able to refine a consumption/production model into a model that contains sufficient information to allow worst-case performance analysis. This is all tested using a peer-reviewed assignment.

Classes of Petri-nets8:33

Causality, choice and concurrency (modeling patterns)9:24

與講師見面

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

[MUSIC]

So, if you use Petri's interpretation of consumption production systems,

then this forces you to bring out certain features in the modeling.

And that is because in Petri's interpretation an actor has a very

limited way of firing and that limited way of

firing means that certain things can only be modeled in a certain way.

So what are those features that come out, how can we recognize them, and

why is it useful to recognize them?

Let's first have a look at the intensive care unit again.

If you look at the intensive care unit, especially if you look at where

the patients come in, then there is an actor modeling patient arrival.

Puts a token modeling the patient into the buffer.

Then there is an actor modeling that patient our assigned bed.

Because there is a token that needs to be passed,

because there is a buffer in between,

you are certain that a patient can only be assigned a bed if it has already arrived.

There is a dependency between

the assigning of a bed to the arrival of a patient.

And such dependencies, such causality between events is modeled by,

well, a structure like this, two actors with a buffer in between.

And this model B is dependent on A.

In a similar way, that same buffer actually has two

outgoing arrow so that's two actors that consume from it,

both actors depend on the arrival of the patient.

But there's something more going on, there is also a choice involved here.

Either a patient is assigned a bed or

the hospital gets a fine for assigning the bed too late.

And such a choice always pops up like well, in a model like this,

in a Petri net model that is, so a buffer with a token and either an A or

a B can happen because there are two outgoing arrows, one to A and one to B.

Now if we are not modeling a system as a Petri net remember the printer

that was not a Petri net then something special happens.

For example.

Here.

This actor was not a Petri net actor because it consumed from

one of the trays from either this tray or that tray or that tray.

So in this model, a choice is being made, but the choice is

looking different from the way a choice would look in a Petri net model.

If you wanna rely on how the choice is represented in a model,

if you model it as a Petri net, then it will pop up like this.

Otherwise it may pop up in very different ways.

The first phenomenon that I would like to discuss with you is concurrency.

That's what happens when two systems actually are side by side and

doing something completely different.

In a Petri net model this often looks like that.

So you have a system A and a system B and they can both do something.

One can come first.

So A can come first.

B can come first.

They can act together.

And they are completely independent of one another.

If then the tokens pass on through the system, and

come together at a later point, then synchronization happens.

Here in these two clouds, behavior happens and at some point,

the A action makes sure that well this, the left and the right cloud

can only continue if they both agree that the A action should happen.

That is when the tokens are passed to the lower part of this cloud.

You can see a combination of concurrency and

synchronization happening in the model of the wireless LAN.

In particular, you can see that it happens for

example over here where the SRC three and

four part are independent of the Detect part.

And at a later point, well here,

the sink is ensuring that there is a synchronization between the two.

Now, if you look at the whole block, if you also take SRC2 into account.

Then a pattern arises which is a kinda combination of concurrency and

synchronization and of what we call a Fork.

You get a fork-join pattern.

That is a combined pattern.

We've now had the basic patterns.

The basic patterns are causality, choice, synchronization, and concurrency.

But if you combine these things then you may get a fork-join pattern,

where the fork actually makes sure that two concurrent streams arise.

And these are joined later in the synchronization step.

A different pattern in which combinations

occur is when you are modeling resources.

Maybe you remember this model of the robot.

There is a resource in the center.

The middle buffer contains one token and

all the moves of the robot are going to synchronize with that one token.

They are gonna take that token and put it back.

If I isolate that, then I get this pattern basically.

You have two clouds, two systems that can work concurrently.

And instead of synchronizing on an action, they synchronize on a common resource.

Know that there is also a choice involved here

because the resource has to choose every time whether an A happens or a B happens.

If you wanna make explicit what that choice is, so if you want for

example to have a kinda round robin scheduling where first A happens,

then B happens, and then A happens, and then B happens.

And you wanna enforce that in your model, then you got something like this.

In this model, I've taken apart the buffer that does the modeling of the resource and

I've made it two buffers.

And the token that is the actual resource is being passed around from A to B and

then from B to A.

And you can see that the choice in this model on the left has disappeared.

Now we've seen a number of features that come up, and

why is it useful to recognize those features?

Well, one reason why it is useful to recognize these features is because

if you recognize a feature like that in a real system,

then you immediately know how to model it as a Petri net.

So it makes the modeling exercise easier and having experience in recognizing these

features makes you a better, or at least a faster modeler of systems.

The other reason why it's useful is that if you have modeled a system, and

you found out that there is a certain feature missing for example.

Then you know that you're restricted to a certain class of models that you've

found a model that may actually be easier to analyze because each of

these features introduces a bit of complexity in the analysis of the system.

For example, you may have noticed that Automata, you know,

Petri nets in which the actors have only one incoming and one out coming arrow.

Automata are basically Petri nets in which there is no concurrency.

And similarly you can see that data flow graphs

are basically Petri nets in which there is no choice.

So that wraps it up.

You now have an idea of all the features that are there and why they are useful.

And I suggest that now you are going you should do some exercises to, well,

get a bit acquainted in recognizing the different features in different models.

Don't forget to also look at the peer reviewed assignment for

the end of this week.

Because, also in that assignment you could model your system as a Petri net and

see what kinda features pop up there.

[MUSIC]

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2019 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取