Date: Mon, 17 Nov 2003 01:38:33 -0600 (CST) From: Yale Patt Message-Id: <200311170738.hAH7cXq02040@sunfire2.ece.utexas.edu> To: ee360n-15280@sunfire2.ece.utexas.edu Subject: a student writes... Dear Dr Patt, I have 2 questions regarding branch prediction. For the 2-bit counter technique, does the processor maintain a separate counter for each branch instruction in the program? Or is there another way to keep track of how many times a certain branch has been taken? We'd like to have a separate counter for each branch instruction. Unfortunately, this would require more storage than we want to devote. So, we use a mechanism very much like a cache. In fact, I would prefer to call it a cache of two bit counters, and while I am at it, let's store the corresponding target addresses also. We access this "cache" the same way we access caches you are familiar with. The address we use is the PC. If we get a hit, out pops the 2 bit counter and the target address to use if the counter predicts taken. I am also unclear why its accuracy is (n-1)/n. This is true ONLY for loop branches, which is presumably what you are asking about. I think this will be true only when n=2 i.e. the predictor is wrong when the loop is first entered. If the loop is looped for n>2 times, then shouldn't the predictor predict incorrectly twice? (giving us (n-2)/n.) Nope! With the 2 bit counter, the first time through you predict correctly, because the last time you executed the loop, the not taken decision moved you from 11 to 10. Now you enter the loop again. The 10 state predicts taken. It is ONLY when you fall through rather than branching back that you predict wrong. Ergo, n - ONE divided by n. OK? Yale Patt Sincerely, <>