Okay. So we've learned that we really don't want any blocking or any I/O while we're processing after we get a service request that should ideally all be done up front. Maybe it was something like a DMA that just puts the data we need in memory for us. But it's pretty clear that we might not always be lucky enough to have that situation. We may have a request for service and then have to go get some data and weep to get it from a device or we may have to have minor amounts small I/O while we're executing after we have already acquired the major portion of our data. But either way that's going to either impact our execution efficiency or introduce some intermediate blocking while our service runs and that's a challenge. So RMA really would like to consider that when the services requested the only thing we need is the CPU Right, so we we need to deal with this, this is a this is a major assumption of RMA that we need to work around. So we'll first start out with a small problem, a minor amount of bio blocking and issues with execution efficiency in other words, we need to do things like maybe read some memory mapped registers or we got some slow memory or things like that, but not major kinds of blocking events on I/O devices or shared memory we'll cover that next. So as we said, this is our assumed time line and the only thing we really have is interference by higher priority tasks. If we have blocking that would undoubtedly come up, come in the middle of our execution, we would make we would request some sort of I/O here and that might cause us to block. And then we would have a big chunk of time we come out of here that would be blocking essentially waiting waiting on I/O and that would be bad what we want to do is wait on all the I/O up front here and at the end. So let's talk about what happens if it's a small amount of IO like really things like memory mapped registers or basic simple memory mapped IO so short IO requests and things like registers and so forth or perhaps different types of memory mapped IO. So in other words, input that we can just read by the referencing A pointer in C code for example in the loop or something like that. And that will slow down our execution but not dramatically not as much as waiting for say a DMA to complete that hasn't even been started or something like that. Or waiting on a mute texts, mutual exclusion semaphore to gain access to shared memory those things would be major blocking IO events. So we're talking about minor ones here that just impact our execution efficiency in fact it looks like we're executing the entire time if we look at something like H top but we're being installed our execution is stalling the process of pipeline and slowing us down perhaps. So if we have CPU pipeline stalls that are due to hazards like memory mapped IO for example like we're talking about now we're just missing cash and having to go to a slow memory. Go to slow memory then that's going to clearly increase our wicked right? Like it gets longer goes up and data dependencies, memory map registers etc. So during service execution maybe off chip memory being loading cash after a DMA completion etc. Lots of possibilities there and we know most likely you're familiar with the idea of pipeline processing for microprocessors where we fetch an instruction, we decode that instruction we executed and we write back results. And the nice thing is we basically complete instruction every single clock so if we just look at the clock 1234 down to end we have a CPI equal to 1 you can also talk about instructions per clock. So an IPC equals 1 just depends which way you want to do your ratio if you tend to have multiple clocks for instruction then we normally talk CPI if you can normally get multiple instructions done per clock with something like DLIW or super scaler then we talk about instructions per clock but that's a computer architecture discussion. For now it's sufficient just to know that normally we can get an instruction done on every clock unless we're stalling waiting on something like a access to a slower memory device memory that registers simple IO but simple IO that can make our execution time longer. The good news is this isn't really going to mess up our may is just going to make our wicket longer. So it's more of an execution efficiency problem than it is really an intermediate IO blocking problem but it can still give us some trouble so we should look at it. So the wicket should be whatever our CPI is in the best case, tends the longest path, longest path in our service loop where we do processing before we go back and wait on a semaphore again and how would we determine that? Well, we could look at the assembly code so we could compile it and you have minus cap S to GCC. >> Okay. Hello? I want to show you some code to describe how to output assembly code and how to actually measure worst case execution time for a small chunk of code. So I have some starter code that I wrote called LCM compute these common multiple, which seems appropriate for this course and it does. So I have an assembly code version and I have C code version and then I'll show you how you can generate assembly code and then hand tune it and things like that. And I'll show you how you can get worst case execution time for any block of code that you wish. So download the lcm.zip, take a look at it and do a make and the one thing you may need to adjust is generation of assembly code for arm architecture versus intel architecture or whatever architecture running on. And of course, we're assuming it's arm architecture, so I'll just leave it like that I'll just show you real quick that this has been set up to be versatile. So here's some basically hand modified arm assembly code, L C M armed S this L C M intel dot S. Honestly, I didn't touch this at all is just the output from the compiler, but I just captured into a dot s assembly code file so it can be assembled independently of the compilation process. And so, and then you have lcm c dot c the point there is, it's all written in C. And what you do as was stated in the video and the lecture notes as you just issued this minus capital S to any C code with the C compiler. And it'll output assembly code. So here I output it to lcmc.gen.sm. So the .S is code that I've modified, the lcm.gen.sms code that it was output assembly code. That's output by the compiler. And I made some C code rappers for it. And the assembly code rapper, just to prove to you that the assembly code can be linked and used and then a wrapper for the C code. And so, that really describes everything we have here. And there's just typical kind of make files stuff here. So I won't go into that. I believe we cover that in prior sessions. So I've made it, and first thing I want to show you is just, I'm going to do a make clean and when I do the make you'll notice right here is the dash S and it runs on lcmc.c and now put this lcmc.gen.sm. So since we're on a arm architecture, this assembly code is going to be armed assembly code. And I teach courses on compiler construction, that kind of thing. So there's plenty of great references out there on assembly cogeneration, how to write assembly code and that kind of thing. I can certainly put things in resources if you're more interested, but it's a little ugly, although it's not bad. Arm code is not bad to read. When code is generated, things like labels have just kind of coded values, they're not as easy to read but I actually think that code looks pretty clean, so gcc does a pretty good job if we look at lcmarm.s which basically was my creation. You can see my comments in there. I don't bother, all the directives that the compiler generates is probably being generated for a good reason to make the assembly code more portable, etcetera. You can see that, then I use labels that are more human readable. So like, wow, check loop body else, branch, right? But you have the same basic things to to manage your stack for a function call and then your loop body, you're all springs your well check et cetera. You just write one function after another and you can, what you can do is do the minus S as I suggested output assembly code and then start messing around with it. It's a great way to learn assembly code. It's a great way to comment assembly code. It's a great way to maybe have the compiler do most of the work and then you can fine tune some assembly code. Like I said, I have of course I'm compiler construction that I teach it, where you going to that gory detail here. We don't want to do that. I just wanted to point out that you can output the assembly code and you could account instructions that way. That's a lot of work to compute something like worst case execution time. So what I recommend instead of going straight to assembly code, my joke about assembly code always is as a programmer doing things in assembly code will either get you fired or promoted. There's not much space in between. I have plenty of stories about both, but the case where it might get you promoted is often the most interesting. That's if you can actually shave off some time and get something to work more efficiently by writing hand tuned assembly. Or maybe you just need to bring your worst case execution down just a smidge and playing around with the assembly. You can do a little bit better job than the compiler or the compiler optimization. Hard to do, but not impossible. So let's look at how we do worst case execution time. Well, what does this code do? So let's look at lcm wrapper.c. And what we see here is it computes the least common multiple and it has to do that by first computing the greatest common divisor. This code also, since I was writing assembly code, I didn't assume any built in libraries or anything, [LAUGH] so I wrote my own implementation of division in my own implementation of greatest common factor, at least common multiple and all that sort of thing. So you can see that it computes a quotation, the divide function I wrote, computes the remainder, etcetera. And then finally computes the LCM. To get an idea of how long it takes to compute an LCM, it totally depends on the size of the numbers, right? So if I start out with really small numbers, first of all, so let's start out with small numbers, I compiled this and I run it. What I'm going to see is that basically, it doesn't vary a whole lot in time. Well, actually that very somewhat when I ran that before this, it actually was all .026 seconds. Let's see a little bit more variation. Yeah, it's as it gets cached. You can see that's kind of interesting, right, it Just settles out at .026 almost exactly occasionally. It varies when cash gets flushed out. But if I really want to see a lot of variation in time, I can put in bigger numbers. You basically have to loop to find greatest common factor to compute LCM. And so it's well this isn't real heavy lifting, greatest common factor. It does require iteration. So if you put in bigger numbers it requires more iteration. So if we put in bigger numbers we would expect the execution time to be longer than the .026. And we would also expect maybe more variation. So let's see if we see that. And in fact we do we see that the average c .009 899. And we see that the worst case is .01 89 so that's that's reasonably different. [LAUGH] And we see a fair amount of variation. If you're doing things like image processing, it's going to be more. So I always get questions. And how do you compute worst case execution time? Well, you do trials, so you take a block of code like this and here is just the LCM code is what I want to measure. You just do clock, get time. I like clock Montana Crockett, you're starting in time. Just do that for 100 trials, 1000 trials, whatever is reasonable or what you're measuring and get your racket, put that into cheddar, use that for your army analysis. And you are good to go for that block of code. You could do this while your code is integrated with your service, you could do this for a function. You can just do this for a line of code like I've done here basically just make sure that your clock get time and for the start in the end or right around what you want to time. Here just this one line of code that I'm highlighting. And try not to junk it up with extra stuff. So you notice, I compute the floating point versions of starting in time after my time trial, right? So it doesn't junk up that code there. And how many times is enough? Well, could do 1000 and see if we get substantial differences. Let's see, we got .01 89. So let's try 1000. I think we have time for that. And we'll see if it's substantially different. Now, I've got printemps coming out of the screen and stuff like that, but keep in mind that I have the time measurement just around what I want to measure, so it still comes out 0.189. Right, so not substantially different. So my advice is you really want to use the WCET, you don't want to use average and you certainly don't want to use best case. So that should give you an idea of how to compute WCET by experiment. And if you want to do it more directly, you can actually kick out assembly code and start counting instructions and estimating clocks for instruction or instructions per clock and that kind of thing. That's what we call more of an architectural modeling, direct method. The method that I'm going over here is an indirect method by trial and honestly for this class, that's absolutely fine. Okay, so as you just saw a brief code, demonstration there, we can measure WCET. But if we're really interested in directly modeling it with the underlying computer architecture, we got a lot more work to do. Right. So we talked about the fact that you have to, first of all understand the pipeline, you've got to understand the pipeline stages, the instruction fetch, decode executed right back wherever many stages you have in your pipeline, it varies even within arm architecture. And we said that we could kick out the assembly co with dash minus capital S, which I just showed you. And really any kind of thing that stalls the pipeline, like access to off chip registers or memory devices or things like that, which really aren't I/O as we said, like DMA or camera interfaces or flash, but they are off chip i o that's going to impact the efficiency of execution rather than causing blocking. And so things like memory access could cause us bounded intermediate I/O so I ideally you would just no see, right. If you could lock your code and data into level one cache that would help. Or you could use a tightly coupled memory knows a scratch pad or zero wait state memory. But that might not be possible. It might not be feasible certainly for this course it might not if you don't have time to for example, create your own custom printed circuit board with an arm our series micro processor as opposed to using raspberry pi with arm a series. Right? So let's just see if you don't have time for that. You're going to use the indirect method. I just showed you you're just going to do trials and measure your worst case execution time at some point. You'll be convinced I've done enough and I know the true worst case, right? But to be complete, really, what we want to do is understand why there's variation in that execution time. Well, it has to do with the path length for a release the instruction count and the clock count. So you can kick out the assembly and count instructions. The longest path in the algorithm depends on how many times you branch loop etc. The execution efficiency of execution that passed. So the number of cycles it takes to complete that block of code and the number of stall cycles for the pipeline as we've discussed. And so this is where it gets a little bit detailed. This is a model I built when I was working for on chip, firmware chip architecture, custom chip architecture. But really when you think about any time you execute a block of code there's a certain amount of time that you spend executing instructions. There's a certain amount of time you spend waiting on off chip devices to respond. I call that IOT so there's instruction count time, I/O time. As we said intermediate I/O time. And then from that you can figure out how much overlap you need between the I/O time and the instruction count time to fit within certain balance to make a certain execution, worst case execution time. And if we related that to a deadline we can figure out how much we need to overlap things like cache fetches and off chip register accesses and things like that. And we can come up with a clocks per instruction associate with that as well. if this seems a little confusing keep in mind this is a computer architecture and like I said instead of modeling and directly we could just measure it but we'll proceed because it's really not that hard. One thing to think about is if your deadline is less than your I/O time then basically this means that your code is I/O bound, right? So in other words the I/O I need to do takes basically longer than my deadline. So if the I/O time is greater than my deadline is another way to think of it. I have that kind of written backwards. If my compute time is greater than my deadline and I'm CPI bet we've talked about this before so but this is kind of at a micro level, right? We're talking about instruction level within the execution of most specific requests for service. And so if the time it takes to go off chip to fetch things out of memory and out of registers and things like that plus the time it takes to actually execute instructions that are in cast is too long then we really have a problem. But we could have a solution if we can take that instruction count time and that I/O time and overlap it so that they can be crushed together and fit within that window of time that we have, that's what overlap is required. So if the IOT + ICT is less than or equal to the deadline, then we don't need to overlap. We don't need to do any fancy cache prefetches Schedule DMA so that we have data sitting in our cache or in our tightly coupled memory. But if IOT plus ICT is greater than decent by then we do have to create some overlap. Is this hard to do? Yeah, it's kind of hard to do. Its writing, assembly code scheduling, cache pre fetches things like that. There are some simpler ways to do this that are discussed in the course, it's much easier to do for large I/O camera I/O and flash output I/O than it is for instruction level I/O. But it's not impossible. What it does is it basically improves my clocks per instruction. So I can reduce the number of clocks required for instruction or increase the number of instructions per clock however you want to look at it. So how does this look graphically? Well, it's really pretty simple in the worst case, the time it takes to actually execute instructions is completely in addition, the time it takes to get what we need into memory. Out of memory mapped registers or out of out of off chip memory etcetera. Remember we're talking about big io but small ale. And if those two added together push you past make a wicket that pushes you past your deadline, you got a problem, right? So you got to improve that efficiency by doing things like cash pre fetches, getting what you need into level one cache or tightly coupled memory ahead of time. And that causes you to have completely overlapped IOT and which should be less than your deadline. You can know the way look at us. I have a certain margin for things like stalls or so and so forth. We saw that in the measurement and that if I take the wicket, anything better than the wicked is just my margin, Right? And from this good compute things like overlap required CP. I required non overlap allowed is what LA is so since this is an architecture course this isn't something we're going to dwell on, but it's something that is good to know why does WCET vary well because your pipeline stalls because you miss cache because you've got some extra time where you're not just executing instructions with operate and data that comes right out of single cycle access cash. That's why. So, these are just definitions that might help you to do that analysis. And so what I would do is do some trials and take some measurements and thank you very much.
