Path History Compression

The global history pattern along with the branch address stored in the program counter is used to index the target buffer. When all the bits of the history buffer and the program counter are used, the resulting bit pattern is long and is equal to (p+1)*w. The number of different path history patterns captured by this hashing address length is 2^((p+1)*w). However, most programs do not have that many patterns. Thus, the effect of varying the number of bits stored per target address stored in the history buffer on the misprediction rates was investigated. Table 3 shows the results of this investigation for the benchmarks. The least significant bits of the target addresses were used in the history patterns. It is observed that the least significant bits capture more information than the more significant bits. For javac, javadoc and deltablue the misprediction rates decrease when b is increased from 2 to 8 and does not change when bit size of b is increased further. This study shows that registering only the least significant bits of the target address in the history buffer could reduce the bit width of the hashing address without much loss in performance.

 

Table 3: Effect of history bit compression of misprediction rates

	Misses (%)
b	Javac	Javadoc	Richards	Deltablue
2	4.7	3.4	23.4	1.6
4	3.7	2.4	25.6	1.3
6	3.3	2.0	6.0	0.8
8	2.6	1.2	6.0	0.6
10	2.6	1.2	6.0	0.6
12	2.6	1.2	6.0	0.6
32	2.6	1.2	4.3	0.6

b is the number of bits from target address used in the path history information.
A path length of two and a fully associative target buffer of unlimited size was used.