1 00:00:03,056 --> 00:00:10,001 So this brings us to some techniques. So we're going to start it off by talking 2 00:00:10,001 --> 00:00:16,016 about prediction and how we can use branch prediction to determine two things. 3 00:00:16,016 --> 00:00:21,785 The outcome and the target address. So branch prediction. 4 00:00:24,078 --> 00:00:28,057 Everyone always thinks that it means this first, thing. 5 00:00:28,057 --> 00:00:33,028 That's not what it means. Encompasses both things, you are to 6 00:00:33,028 --> 00:00:40,008 predict the outcome, so that's whether the branch is taken or not taken and you also 7 00:00:40,008 --> 00:00:48,154 want to predict the target address. Now if you think about that, the first one 8 00:00:48,154 --> 00:00:53,059 sounds relatively trivial. I could sort of pull numbers out, or, I 9 00:00:53,059 --> 00:00:55,098 could, I could pull something out of a hat. 10 00:00:56,015 --> 00:00:59,022 Taken, not taken. You know, just sort of choose randomly. 11 00:00:59,022 --> 00:01:02,091 It's going to do okay, probably. I could probably try to correlate it 12 00:01:02,091 --> 00:01:06,297 somehow using heuristics. The second part here, I have to get the 13 00:01:06,297 --> 00:01:09,067 number exact. So if I choose at random for my branch 14 00:01:09,067 --> 00:01:11,627 prediction outcome, I'm going to get it 50 percent right. 15 00:01:11,627 --> 00:01:16,222 Or if I just always choose, I don't know, we'll, we'll say, if I just always choose 16 00:01:16,222 --> 00:01:20,687 not taken, or something like that. We're probably going to do pretty good. 17 00:01:20,687 --> 00:01:25,129 But, getting the actual destination correct, you have to be exact. 18 00:01:25,129 --> 00:01:30,686 You have to choose a number out of let's say if you have a 32-bit instruction 19 00:01:30,686 --> 00:01:35,402 pointer, two, you have to choose some random number, out of two of the 32 20 00:01:35,402 --> 00:01:39,440 locations and get it right all the time with high accuracy. 21 00:01:39,440 --> 00:01:44,769 So we'll, we'll spend some time about this, talking about this and some 22 00:01:44,769 --> 00:01:50,405 strategies to, to getting the prediction target, and predicting our branch target 23 00:01:50,405 --> 00:01:55,629 and our jump target correct. But, you have to think about both of them, 24 00:01:55,629 --> 00:01:58,982 is all I really wanted to get, get across here. 25 00:01:58,982 --> 00:02:08,690 Okay, so this, this is something we, this is a little bit more review from something 26 00:02:08,690 --> 00:02:14,445 we talked about in lecture, I think, two. We talked a little bit about figuring out 27 00:02:14,445 --> 00:02:18,651 where we can resolve a branch. So here's a little bit longer pipe. 28 00:02:18,651 --> 00:02:24,073 One, two, three, four, five, six, six stages, not quite a five stage pipe. 29 00:02:24,073 --> 00:02:31,948 But put issue stage in here. And let's look to see where everything 30 00:02:31,948 --> 00:02:37,163 gets known. So we know that our target address, for 31 00:02:37,163 --> 00:02:43,132 branches, jumps, and jumping link, will likely be known here. 32 00:02:43,132 --> 00:02:49,186 But that's not really helpful, unless we know which way, the branch is. 33 00:02:49,186 --> 00:02:54,099 Or rather, which way the branch is going, or the branch outcome. 34 00:02:54,099 --> 00:03:00,355 Because even if we know at least for jumps and jumping links we know the outcome. 35 00:03:00,355 --> 00:03:03,661 It's taken. But for conditional branches, we may not 36 00:03:03,661 --> 00:03:08,275 know that, until somewhere over here. So we can't necessarily use that 37 00:03:08,275 --> 00:03:13,047 information, until later in the pipe, for branches, to, to do something useful, in 38 00:03:13,047 --> 00:03:19,375 the naive approach. In the execute stage, we know the branch 39 00:03:19,375 --> 00:03:23,200 outcome. We'd talked about a trick in Mips at least 40 00:03:23,200 --> 00:03:28,541 where you can try to pull that forward a stage into our decode stage by having some 41 00:03:28,541 --> 00:03:32,767 sort of special comparator on the output of a register file, comparing it with 42 00:03:32,767 --> 00:03:34,793 zero. But that doesn't work for all branch 43 00:03:34,793 --> 00:03:37,546 types. So if you have something like a branch 44 00:03:37,546 --> 00:03:41,944 equals where you're actually trying to compare two real registers, you have to 45 00:03:41,944 --> 00:03:46,492 wait for the full bypass doing a 32 bit compare is sort of the equivalent of doing 46 00:03:46,492 --> 00:03:50,449 a full 32 bit sort of tract. You're not really going to know that until 47 00:03:50,449 --> 00:03:54,652 the end of the execute stage. That trick doesn't, doesn't really hold 48 00:03:54,652 --> 00:03:57,067 water. It holds water for comparing with zero. 49 00:03:57,067 --> 00:04:01,637 You might even be able to do it if you have lots of extra time in your decode 50 00:04:01,637 --> 00:04:04,583 stage. But let's assume that, you don't. 51 00:04:04,583 --> 00:04:10,564 Also target addresses for jump registers and jump and link register. 52 00:04:10,564 --> 00:04:18,005 Jump registers, jump and link register. You need to read the actual address that 53 00:04:18,005 --> 00:04:23,509 you're going to out of register somewhere. So this, you can't even have a chance of 54 00:04:23,509 --> 00:04:26,795 trying to predict it out here, or the destination. 55 00:04:26,795 --> 00:04:30,510 It's pretty hard. Because, I don't know, it's somewhere in 56 00:04:30,510 --> 00:04:33,958 the bypass, you just compute some value, then you jump through it. 57 00:04:33,958 --> 00:04:38,040 Hm. So the, the, the, we don't, at least down 58 00:04:38,040 --> 00:04:42,994 here, by the time they're done here we have one of two address excuse me, we have 59 00:04:42,994 --> 00:04:46,097 the both of the addresses that the branch can potentially go to. 60 00:04:46,097 --> 00:04:50,012 Go to either the fall through address or the branch target. 61 00:04:50,012 --> 00:04:52,058 We know that sort of at the end of decode stage. 62 00:04:52,058 --> 00:04:56,079 For jumping link registers and jump registers, we don't even have that 63 00:04:56,079 --> 00:04:58,089 information. It's not encoded in the instruction 64 00:04:58,089 --> 00:05:00,055 anywhere. It's encoded in the register. 65 00:05:00,055 --> 00:05:02,077 So, we need to go fetch something from the register. 66 00:05:02,077 --> 00:05:04,068 Might have to go through the bypass network. 67 00:05:04,068 --> 00:05:06,004 So, we're going to have to wait.