Tagged versus Tagless Target Buffers

We also studied the impact of interference due to the presence and absence of tags with the target buffers. The XOR hashing scheme was utilized in studying both the approaches. In the tagless scheme, the target address of the indirect branch is selected using the hashing address to index the target buffer. Since, no tags are associated with each target buffer entry more than one hashing address can map to the same location. Due to this interference, the target of the indirect branch is selected based on the outcome of some other branch path pattern. A positive interference occurs when the when two different patterns that map to the same target location have the same target address. Similarly, when the interference results in more misses it is called as negative interference. A tagged target buffer can be used to eliminate the effects of negative interference.

The impact of the tagged and tagless target buffers was studied for various buffer sizes by varying the associativity and the path length. Figures 13 and 14 shows the variation in misprediction rate using target buffer sizes of 2K and 4K for the tagged and tagless buffers respectively for javac and richards benchmarks. Additional entries were provided for the tagless case to account for the area overhead in maintaining tags. In these plots, an increase in the number of target address bits in history buffer corresponds to a decrease in path length. It is observed that the misprediction rates decrease with increase in associativity for the tagged buffers. Also, it is observed that there is not a significant improvement when associativity is increased beyond 8. For javac, it is observed that the tagless target buffer performs better than the the tagged buffers when a=1 and a=2 for all path lengths. It must be noted that the tagged buffers are useful only when they are able to register the alternate target address when a conflicting path history is identified. Thus, direct mapped tagged buffers perform inherently worse than the tagless buffers as they also do not benefit from positive interference. Hence, higher associativities are required in the tagged caches to benefit from the absence of negative interference.

When path lengths become large (number of target bits in history buffer becomes small), the number of different patterns generated corresponding to an indirect branch increases. Hence, a tagless buffer can benefit from the positive interference between these different patterns. Thus, it is observed that the tagless buffer performs better than the 4 and 8-way associative tagged buffers for longer path lengths for javac. For the richards benchmark the effect of positive interference is lesser, since it benefits from longer distinguishing patterns as was observed in Figure 6. Thus, the tagless target buffer performs better than only a direct mapped tagged buffer for all path lengths for the richards benchmark. It is also be observed that the the tagged buffers of higher associativity provide a greater improvement in prediction rates for smaller path lengths in both the benchmarks. This indicates that the conflict misses due to short term variations in targets is being reduced by the tagging mechanism.

**Figure 13:** Comparison of tagged and tagless target buffers using *javac*. The size of the tagged and tagless target buffers were 2K and 4K respectively. The XOR hashing scheme with global path history were used for all cases.
$\begin{figure} \vspace{0.01in} \centerline{\psfig{figure=tag_javac.eps,height=2.5in,width=2.5in}} \vspace{0.01in} {\bf } \vspace{0.01in} \end{figure}$

**Figure 14:** Comparison of tagged and tagless target buffers using *richards*. The size of the tagged and tagless target buffers were 2K and 4K respectively. The XOR hashing scheme with global path history were used for all cases.
$\begin{figure} \vspace{0.01in} \centerline{\psfig{figure=tag_richards.eps,height=2.5in,width=2.5in}} \vspace{0.01in} {\bf } \vspace{0.01in} \end{figure}$

Figures 15 and 16 show the variation in misprediction rates for the various buffer sizes. A tagged target buffer requires additional area overhead for maintaining the tags as compared to a tagless target buffer. Hence, a tagless target buffer can have more number of entries corresponding to the same implementation cost. It can be observed that an associative tagged target buffer with 8 or more entries per set outperforms the tagless buffer. It can also be observed that the increase in buffer size reduces the conflict misses significantly for the tagless and tagged buffers with associativity less than or equal to 4. The tagged buffers with associativity greater than 4 do not benefit much from increase in buffer size since the higher number of entries per set already takes care of most of the conflict misses. Due to the increase in access and cycle times associated with the higher associativities [21], the area overhead of the tags in the tagged buffers and the small difference in the misprediction rates between tagless and tagged buffers with large associativities (a > 4), the tagless target buffer may be a better choice in many cases.

**Figure 15:** Comparison of tagged and tagless target buffers using *javac* with variation in target buffer size. A path length of 2 was used.
$\begin{figure} \vspace{0.01in} \centerline{\psfig{figure=tag_javac1.eps,height=2.5in,width=2.5in}} \vspace{0.01in} {\bf } \vspace{0.01in} \end{figure}$

**Figure 16:** Comparison of tagged and tagless target buffers using *richards* with variation in target buffer size. A path length of 4 was used.
$\begin{figure} \vspace{0.01in} \centerline{\psfig{figure=tag_richards1.eps,height=2.5in,width=2.5in}} \vspace{0.01in} {\bf } \vspace{0.01in} \end{figure}$