the 2 level branch predictor

A student writes:

	Dear Dr. Patt,

	I had a question on the 2-level branch predictor scheme you explained in
	class. According to this scheme we keep a history of previous 
	branches based
	on their addresses (program counter values) and have a 2 bit saturating
	counter associated with each branch/address. 

I assume you are talking about the PAs predictor.  Recall there are 9 variations
based on how many history registers there are an how many pattern tables there
are.  For history of size n, each pattern table consists of a table of 
2^n saturation 2bit counters.  

If we are indeed keeping a history register for each static branch, these
registers are kept in a cache structure, so as to have a better shot at having
the relevant histories still in the cache.  With a hundred branches, not a
big problem.  The cache has to only accomodate 100 entries.  We often make that
cache big enough to accomodate 1000 branches.

As to the pattern tables, yes, having 1000 pattern tables takes a lot of space,
so we use the "s" variation which shares tables, and yes, we could end up with
negative interference.  A paper by Kimming So (ASPLOS 1992) showed that 
sometimes that interference is positive.  That is, the counter is set due to
one branch and used to predict the direction of another branch that hashes to
the same pattern table.

	Let us consider we load a
	program into memory which has 24 branches and the size of our history
	register is 18. In this case which of the 24 branches would get 
	stored in the history register? If we increase the branches in the 
	program to say 100 and select 18 values by some logic, isn't there 
	a possibility that we have
	made a wrong choice and a different set of 18 values 
	would have given higher efficiency?

Yes, we can sometimes do worse than doing nothing.  The question is whether
most of the time, the structure improves performance or most of the time
the structure worsens performance.  

In any case, since it is the branch predictor, it is all speculative.
Ergo, getting it wrong never affects correctness of the running program,
only its performance.

Hope this helps.
Yale Patt

	Thanks,

	<<name withheld to protect the student worried about interference>>