Okay so, very long instruction words, processors. Still wanna have high performance and we took all this hardware that was in a, out of our superscalar reserve through it out. Well, something's got to make up for it. And what makes up for it, is a very, very, very smart compiler. So, we put a lot of emphasis on the compiler, in these sorts of architectures. And, the compiler really has to do the scheduling. It has to do all of the dependency checking. It probably to avoid all the different data hazards, and this is just we're just getting started. We're gonna talk mostly next lecture about all of the different optimizations a compiler can do to try to approximate what a on-board superscalar can do, but by doing it statically. So it's a pretty cool trick if you take all that hardware, you put in the compiler, you run it once. And then, every time you go to execute the code, you don't have to go and recalculate all the dependencies. Sounds good. Okay. So let's see how we execute some code here and what is the sort of performance aspects to executing loop code on a very long instruction word processor. So here we have a very basic array increments. We're gonna take every element of this array. We're gonna increment it by the value C. [clears throat] And our, we run through aour compiler and here's the sequential code sequence. This has not been scheduled yet for VLIWs or for our VLIW architecture over here. So, we load some, we, we load the value. We increment our counters. We actually do the floating points, add. We store the value back. We increments the array index, and then we, we loop. Seems simple enough. Let's see how this gets scheduled here. Well, because the architecture and because the compiler knows about latencies here Let's say tthis load here has a few cycles of latency.. So it's gonna actually schedule this ad later. And the add, it's a floating-point add, this has a couple of cycles of latency also, so it schedules the consumer of that results here, this F2. Later. And, yeah, I don't know, you can sprinkle in the array additions and then the counter additions, kind of somewhere free, has lots of open slots. But let's say it schedules at the same time as the load in the store. So this is pretty cool. We are actually executing two wide parallels in here. And we didn't need all the extra overhead of in [inaudible] super scour. Oh, and we can just go to the branch somewhere. Okay. So, first question here how many floating point operations are we doing per cycle are we doing very well here? So, it looks, looks, looks pretty poor. We have one floating point operation here, just this ad. And we have one, two, three, four, five, six, seven, eight cycles? Yeah. So we're having 0.18 or 0.125 floating, like floating point operations per cycle. It's not that great. [inaudible[. You know we're actually having three instructions here. It's better than nothing but we're not really using the machine very well. Out of our superscalar, we'll probably try to take connstructions that are below here maybe intermix them, try to reorder a bunch of things and try to run faster. So what's a technique to go faster? Well, one of the big comply, as I said we have a lot of emphasis on compilers in this unit. One of the things the compiler can do, is it can actually unroll the loop. So here we have our loop, we unroll it, four times, and, now, we're going to sort of take the loop overhead, and we're gonna factor it out, so that it only happens once every four times. That sounds good. We're gonna do some more work here, per each [inaudible] loop. But things are a little more complicated. What happens here if N, big, upper case N here are terminating value is not a multiple of four. Well, we need to do something about that. We probably need to check sorta before we go to execute here whether we're, we're doing okay or whether we're actually are [inaudible] for convenient leaf and it's big enough and probably can run as multiple four for a long period of time and so is the last iteration you'll have to clean up. But we need to generate some clean up code and compiler is responsible to do this. So these compiler optimizations do take some effort. Okay, so let's look at the scheduling now of our loop unrolled code. We can do a bunch of loads upfront here. So we've inter, intermingled these loops. And what's kinda cool is because you pull out the loads and are thrown to the top and the stores been pushed into the bottom. And then put all the ads sort of in the middle. And maybe sprinkle the array update somewhere else. And we go to actually schedule that, we're going to do something similar. We're going to have the loads [inaudible] first, execute the floating point ads of the floating points stores and have the result. But what you could noticed here is we're actually starting to get some overlap, because we've unrolled, we can overlap this load and the first floating points addition 'cause we've effectively covered the latency of our functional units by putting other loop iterations during that time. So if you look at this schedule versus the schedule back here. We're just sort taking these dead cycles and we've put the other loop iterations in those dead cycles. In this loop unrolled case, we're incrementing this counters and the indexes not by four anymore. We're incrementing by however many times we've loop unrolled times the offset, so we're incrementing it by sixteen now. Does that make sense? 'Cause in, in this code here we were incrementing R2 by four, because that's the size of a single value is four bytes. So we have to sort of move our array index over by four. But now, because we're batching up all this work together. [clears throat] We actually have to move the, the index by a, a bigger value. So we're moving it by four 'cause we've unrolled four times, times the size of the data value, which was four. So we're moving it by sixteen. And, and, one of the nice things here if we look is in both the loads in the stores, we're using our register indirect addressing mode here to add in some offsets. So, we're actually offsetting, let's say, twelve plus this base register of R1 to figure out where we're actually doing the load from. But it's just, a convenient way that we don't have to compute a bunch of addresses [clears throat]. Okay, so going back here, we can see we're starting to overlap actual operations with other loop iterations. Well, that's really cool. So we're starting to get some performance here. So, let's, let's look at the performance. So, I ask the same question here. How many floating point operations per cycle? Hopefully, hopefully it's higher, one, two, three, four divided by one, two, three, four, five, six, seven, eight, nine, ten, eleven cycles Okay, so that's 0.36 is a lot better than 0.125. This is good. Loop unrolling is helping us. But is this, is this everything? Or could we do more in our compiler? So these four compiler people came up even fancier idea, which is called software pipelining. So uses, uses a term we've seen before, pipelining, but does it in software. So the idea here is that instead of. Just having one loop, unrolling the loop, and then overlapping the iterations. We're actually going to take multiple of these schedules, and interleave them. And try to fill some of these empty spots. So let's, let's look at this. We're going to have the code unrolled four times. It's the same piece of code we had on the previous slide. And we're gonna draw our schedule that we had before. So here is the schedule we had before in purple. Okay, that doesn't look so bad. But now, we're going to schedule it with another iteration of the exact same four time unrolled loop shown here in green. So we've just overlapped this with, this other iterational loop. Well are we, are we done here? Well, not quite. We still have some open spots here. So let's try to overlap even another iteration, as shown here in red. Now the fix-up code that you need to have to do this correctly gets more complex 'cause all of a sudden now you're overlapping multiple iterations, but as long as you don't modify some value, as long as you don't do a store, speculatively, or a store, you're probably okay, 'cause always just doing [inaudible]. Doing extra loads, doing extra work. You're doing extra work and you're filling slots thinking that you're not gonna have anything go wrong or thinking that the index variable N if you will, is a multiple of four and large, and you're not at the end. So let's, let's put some names to these things. [clears throat].. So we call the, beginning here the run up, the prologue. Here, we actually have our sort of actual iteration. You can see that the, sorry this is in green, that doesn't show up very well there are instructions here. There's ads. It's pretty full. We're actually doing a lot of work on our machine here. And then the epilog here is the, is when we're done. This when we're falling out. We're sort of at the last loop iteration of the outer loop, if you will. So let's, let's do some math and look at the performance of this. Okay, so let's ask the same question here. How many, floating point operations, per cycle? Well, we go look over here. We have one, two, three, four. And we have four cycles in our, in our tight loop case. That looks pretty good. That's cool. We just got a bunch of performance. But we have to do a lot of compiler optimization to make this work before we're able to use the [inaudible] machine, and we're able to overlap three different iterations of this of this loop, that we also did a software transform to unroll it twice. So this is called a software pipeline, pipelining. And have the nice picture in here to sort of show what's going on visually. So we're gonna have time on the horizontal axis, and we'll have sort of activity of how many instructions are executing or something like that on the vertical axis or, or shown here as performance. When you run multiple loop unroll iterations, you have, starts from start up, you have the actual you are in the loop, and then you come down from that. And that's, that's better than having lots of start up and sort of come down with small loop iteration portion here in the middle. [clears throat] But when we go look at the software pipelined, we can overlap, basically one iterational loops execution with or one loop start up or, a, a with loop iteration of another loop Now we can actually execute sort of our prologue, execute multiple iterations, very tight, and then have our epilogue here. Yeah, so. Our software pipelining [inaudible] start up and wind down costs. Once for the execution of the loop and not every iteration of the loop. So that's, that's, that's fun. That's cool. We're getting performance. If only the world was dense loops, life would be easy. Alas, the world is not all loops. If we just had a processor, which just did enter array calculations and all of our problems in the world were just dense array computations life would be really easy. But they're not. A lot a time code has lots of branches. It has if than else clauses. And here so graphically show something like a if than else. So we have some piece a code that makes a decision and executes the code on the left or executes the code on the right, based on an if statement. So this is the if true statement and this is the ELF's clause. [clears throat] and data dependent branches are a problem typically for very long instruction word processors. Now, why is that? Hm. Well in a, out of word processor, you can try to execute, code sort of around the branches and move instructions above the branch and below the branch. But if you're doing static scheduling when you hit this branch, and let's say it's a hard to predict branch. You can't really do anything because you packed a bunch of instructions next to each other and they need to execute atomically. So, thinking measure of move code up and down across that branch. Superscalar can do that, 'cause it has its instruction window, it has a bunch of techniques a bunch of hardware to be able to do that. But in our VLIW processor, that's a problem. So I wanted to introduce a, a compiler, an important compiler nomenclature here, which is important for this class, it's called a basic block. So what is a basic block? A basic block is a piece of code which has a single entry and a single exit. So this is a basic block, it has one entry, and one exit. And why is single entry important? Well, if you can jump into the middle of this piece of code, the compiler cannot necessary reorder the instructions inside this block. If you have multiple exits, let's say you exit here, the compiler can't push instructions below that exit point. But if you have a basic block, the compiler basically knows that these, this instruction sequence is going to execute effectively, effectively atomic, but not actually atomic. I mean that you can have other things going on inside there. But from a compiler perspective it can reorder the instructions around in here to get better performance. Hm, okay. So loops, loops are easy. We can solve for pipeline. We can unroll. Squirrelly code if and else spaghetti code are hard. So compiler guys came up with some fancy tricks to make VLIWs work better and take advantage of some of the code motion that out of a force superscalar does but in the compiler and not in dynamically in hardware. And one of the more famous ways to do this is something called [inaudible] scheduling, which was John Ellis' who was one of Jon Fishers' student's thesis work. This was in the Bulldog compiler out of [inaudible] So, what you do is you profile the code and, you compare the probabilities that these branches go the one way or the other way. So, let's say profiling, this is not a something hardware is doing at run time, this is something that you do with the program while you are sort of still back in the compiler stage. You take the program, the compiler goes and runs it on some input given, given input set and comes up with the probabilities of which way things go. And then what you do is, you come up, you take this profile information and you come up with some guess at what is the most probable one. And we're going to circle that here. And say. These darkened edges are the most probable sort of path through the squirrelly piece of code given this is the entry point. Now, this doesn't mean that you can't have branches that sort of branch out of this, but if you do you need to have some fix-up code 'cause what we're about to do is we're gonna take this entire sort of, big [inaudible] of code here. We're gonna remove all of the branches and we're gonna schedule for our VLIW processor as one big monolithic piece of chunk code. And by doing this we can move instructions, let's say, that are down here, which this opens last to executing your early portion of this codes sequence, we can move them up. And likewise we can move things that use the resolve of long latency instructions up here and push it down across branches. So our out-of-order superscalar does this with branch speculation, but our compiler can do this on our VLIW processor using trace schedule. But when do this, which be careful because there's always a possibility that while unlikely you can still branch the other way. So typically, the way this is done is you have some form of fix-up code that you branch away, you have to sort of fix up anything that was after the branch that made a committed change if you will, to the, the processor state. And you sort of roll that back somehow. So, we're basically in software, doing the rollback case from number our out-of-order superscalar. So instead of taking the, architectural register file and copying it to the physical register file on branch mispredict, instead our compiler generates a code sequence which does that same operation if you were to branch away there. And we'll roll back, only the only the certain register that needs to be rolled back and only the memory state that needs to be rolled back. So, that's pretty cool, so we can basically take all the functionality that was dawn in our out-of-order superscalar and put it in the software using trace scheduling.
