[MUSIC] Of course, we only build this thing during the weekend because my son likes that kind of thing. I was thinking too much about this last lecture, I wanted an example that I could use to show everything that we've done in the past three weeks. And then he said, why don't you use the box? I truly I think that's a good idea. And the most fun part of the box, I think is actually this one. The movement sensor. It's a bit of a crappy movement sensor, I admit. But, it works. Oh, of course, I didn't do any proper designing. But in the past three weeks, we've had the tools, we've learned the tools, to do a proper design of a movement sensor. So, what does a good movement sensor do? Well, it has to be fast, of course. It has to be reliable. And it shouldn't take too much memory or too many processing resources. Now, question for today is how to design a movement sensor that fits those requirements? Well, let's draw a picture. So what do you need for a good movement sensor? Well, you need a camera. In our robot we only have a one-bit camera, that's called the light sensor. If you have a more expensive fund and you actually have a camera or something that takes pictures, and a camera that stores the pictures somewhere in memory. And then the whole idea of movement sensing is that you compare the current picture with the picture that you took awhile ago. So there's also going to be some kind of compare functionality. And because you compare with a picture that you took awhile ago, well, just to be sure you already can make a copy of the current picture to be used later. And a later version you load from that memory, and you send it to the compare, and you send it straight away to the compare as well. And then in case you find a difference between the two pictures, you set off an alarm. So we have here the camera. We have here a copy, a load, a compare, and an alarm. Well, let's clean that up. So this is a nice functional description of the system that we are interested in. And of course, we can go through the list to see if we completely understand it. If you look at the actors, what do they represent? Well, they represent functional parts of the movement center. And what do the buffers represent? Well, they are memory places in the system, right? And the tokens are pictures that are being passed around. And then, what are the firing rules? Well, the camera produces one picture every time. The copy functionality copies one picture every time, so it seems that it's actually kind of a Petri net. It is a Petri net, except for the alarm. The alarm is actually not a Petri net, or the comparison part actually only puts a token into the buffer for the alarm when there is something wrong, when it detects a movement. But of course, if we pretend that also if it has not detected a movement it's going to put a void token into that last buffer, then this is actually completely a Petri net and then we've basically covered the whole list. But that's not the only picture that we need to draw. We also need to say something if we want to talk about performance. We also need to say something about the hardware on which this system runs. For example, we could run it on a piece of hardware like this. We have a CPU that does some processing. We have a memory. There is of course, the camera chip. And they are all connected using a single bus that you can use to read or write images to the place where you need them to go. That would be one option. Another option could be that we have four CPUs, that we have a quad core, with actually an internal piece of memory, the cache, and an external piece of memory, well, I just called it memory here to store images for a longer while. And of course, the camera, or we have three different buses. One for reading from the camera, one for writing into the external memory, and one for reading from the external memory. That of course, has a lot of advantages compared to the previous one. Because what, you have much more resources to use. And one thing that I want to show you about this is that, depending on the architecture that you have, the refinement of the Petri net changes a little bit. The first refinement actually does not depend on the hardware. It just is about the evolutions of the Petri net as we first described it. One of the things that is typical about this Petri net, is that here, the copy action can actually be done as often as we like. We can do it once, we can do it twice, we can forget to do it actually but that's not intended if we look at the interpretation of the movement center. In the interpretation of the movement center we actually only want to copy once, and we want to copy before the compare actually takes a token from this buffer. So what we do, we do, well, we refine first this Petri net into a different one that contains information about that schedule. What happens is that we copy this buffer into two new ones. And basically, if a token is in the first buffer, that means that it's in this memory location but has not been copied yet. And if the token is in the other buffer, then it means that it's in the memory location, and it has already been copied. But both buffers together represent the same physical memory as the one but for that we had in the original system. And of course, there is a refinement relation because you cannot copy to the copy, and the load to the load, and the camera to the camera, and the compare to the compare just as before. Now to emphasize that these two buffers are the same memory location. We can actually refine the system a little bit more. And have a look at the architecture, at the memory in the architecture. Now for the first refinement actually the refinement is the same for both architectures. Because, well, it just says there is a memory of K images large. The size is K images, and that we use to store images that come from the camera. And that's what you model using there's feedback. And then the second one is, well, we have a memory of M + L images large, which we use to store the copied images. Is M + L images large, because of course, we already had L images that were waiti-. We compare every image that enters to movement detector with an image that is, well, L periods back, L periods ago, taken L periods ago, but we also have M additional images that may be stored in that part of the memory. And of course, once we've loaded an image, we also have to still put it somewhere, for example, in the cache if we are looking at this system or in the register of the CPU, while it's not an entire image then. But that would be modelled by this N. And then if we continue, and only look at the left architecture then we see that we have to also refine for a schedule for using the bus. If there's only a single bus that all the processes have to share, then there is one token that is polished around all processes. And in this case, it's plastered around in a round robin fashion making sure that you first hits the camera, then hit the copy, then you do the load, then you do the compare, and then you're well, full circle. But you could also think of a different schedule and make a data flow graph that represents that different schedule. It would all become a more difficult data flow graph, most likely. If you on the other hand look at the other architecture, then you get a completely different kind of data flow graph. In the other architecture, we have separate resources for reading, writing, arithmetic, no, and getting the camera out. And it means that we also get separate buffers here, there and there. And for the compare action, we have four different possible CPUs at our disposable. That means that we can actually run four compare algorithms at the same time, and that means that P, actually well, it should be taken as smaller or equal to four. But you can here model how many processors you want to use to do the compare action. Now, this is actually the model that I want to continue with in this lesson. I cannot keep treating both of them simply because there is no time in a video like this. What I do want to point out is that there are of course, the usual patterns In this Petri-net still. We have a data flow graph, that's a pattern. We have these feedback arcs for modeling resources, that's a pattern. And we also have a fork joined construct here. The copy is actually a fork. I don't know if you can see it, but it's a fork. And just after that there is a join. So if you remember from the first week, you can also recognize the patterns in this Petri-net. So, let's continue. What are the quantitative questions that we're interested in? Well, we're interested in that the image recognition or the speed of reaction should be quick, and should be reliable. And for that, the choice of the period is quite important. If you look at this graph, I've put on the x axis the time between images that are being compared. So we have a period T for our graph, and we have L x T as the time between the image that are compared. If this time is very short then you can see that actually the images do not change a lot in a short time, so there is no difference being detected. And if the time is too large then there's also no difference being detected because the movement that we would try to detect has already happened. Only if you hit the sweet spot, in this case B, so if you take T x L = or around B then you will have good quality. And if you have a chosen T L then you could make up a bogus formula like this to represent that quality. Now, the second measure that we have for quality is that the machine should react fast enough. And fast enough just means that, once you've made a picture, you do not want to wait too long until the alarm goes off. For that, we have to kind of measure the latency of the system. It's not exactly the latency, by the way. I'm going to get back to that later. But we have to measure something like the latency, and we know how to do that. We have to just calculate a periodic schedule for it. So, I suggest that you try to calculate a periodic schedule and then I will give you my solution. Okay. So here's my answer. We have a maximum cycle mean which contains seven components because there are seven cycles in the graph. And, of course, the period has to be chosen larger than a maximum cycle mean. And then we have a latency which has four components because there are actually four backward passes through the graph. The down pass here, there is a pass back to the load. There is another pass back to the load and there is a pass back via the load and then to the camera. And that gives us four components like this and for the delayed latency, you only get two components because you only need to take care of the pass that go from the alarm back to the camera. But there is something special going on. I've calculated the latency and the delayed latency, but those are not exactly the things that I need to know for this system. So you have to be careful. You cannot just without thinking use delayed latency and latency if you want to say something about reaction speed, as in this case, the reaction speed, for example, is a little bit different. The delayed latency is just the time from the starting of the camera in a periodic schedule, until the alarm goes off. But, if we want to know how fast a system reacts to movement, then you also have to take into account the time it takes until the picture is taken. So if the movement starts and then the picture is taken, and then the alarm goes off, then you have to take the time into account from the starting of the movement until the picture is taken, and that can at most be one period. So, the delayed latency may be this, but if you want to know the reaction time. You have to add one more period and that I call the detection speed. Detection speed. In the same way, the latency, if you want, are interested in the boot up time of this graph. Then you will notice that the boot up time usually is the time it takes until the system is operational. But we have L images that are uninitialized in the system. So, the first L comparisons of the system are actually bogus comparisons. They are not comparisons to a real image. Which means that only after those L comparisons, the system really starts operating. Which means that the boot up time actually has an L plus one times T factor, as well if you look at the interpretation of this system. Now, a third thing that is going on is that you may think that this formula has a dependency on the period here as well, which would mean that if you draw it, you first get a line down and then a line up, and that there is some sweet spot over here. Where the latency actually goes from a downward to an upward movement. But if you look at the maximum cycle mean you will quickly realize that this is actually not the case. Because the maximum cycle mean is larger than the load, and is there for certainly larger than the load divided by L. Which means that only the upper part of this formula is relevant for us. And that brings us to having three formulas that together guarantee that the quality of our image comparison is good. Now we only have to make sure that we do not take more resources than necessary. So we have to make sure that this K, L, M, N and P that are still in the graph, that they do not take too large values. So how can we do that? Well, if you look at the maximum cycle mean, you will see that, if you look at the other formulas, you will see that actually only L occurs anywhere else, but P, N, K, and M, they only occur in the maximum cycle mean, which means that if we take the period as large as possible, then those values will be as small as possible. And that means that we can just solve the other two equations taking the period as big as possible and then we get, this. And this actually solves the whole system for us. It gives us a value for the period, such that the quality is optimal, and it gives us values for the memory usage and for the processor usage such that this period can also actually be maintained. And these are minimum values. Now if you don't like these values then you're in trouble. The only thing that you can do is either change the architecture so that you get a different graph or you change the quality requirements that you had on it or you ask some programmer to change the actors a little bit, to change the algorithms. So congratulations, you've reached the end of this book on Quantitative Performance Modelling and Best-case Performance Analysis. I hope you've learned a lot I'm sure that I did. And from here there are a number of possible paths forward. You could look at different data flow types, you could look at multi-rate, at cyclostatic, at mode-controlled data flow. You could also look at other fields and try to use formal modeling there, such as the real-times systems world or you could go for performance measurements rather than performance analysis. You could also decide to start doing completely different things. For the people in the course that I give at my home University and for people in the EIT University, they should not stop yet. There is one more assignment that they need to do. There is a paper that I've looked up which is very instructive and which teaches you something more about how to model using data flow graphs. And I want them to do an assignment on that which sadly I cannot ask everybody on Coursera to do because it requires a teacher to actually check the material, you cannot do that using peer refute. After that of course there is the exam, of which I put a copy online as well so that you can compare what the level is that I require from my Master's students at university compared to what I require from you if you want to get the certificate. Well, basically that rounds it up. I wish you all the best and hope to see you some next time maybe some other MOOC. [MUSIC]
