Grant Wallace
1. Branch prediction is based on the value of registers rather than on previous branch history. Since the actual outcome of a branch will be determined by register values, this method can give more accurate predictions.
2. Allows for early-resolved branches. If the predicate can be calculated a sufficient number of cycles before the branch instruction, the branch direction is pre-determined.
1. The prediction algorithm is static, based on profile information. The profiled data may differ greatly from the runtime data leading to poor predictions.
2. The primary results reported were acquired by running the training data sets through the branch-optimized code. It seems that real data sets could dramatically decrease the prediction rates. Though one set of comparison results was shown using a reference data set, its not clear how varied the reference data sets were.
3. In the practical prediction algorithm, the quantization of register values is very course grained. Register values are mapped into 256 bins in the linear mapping, or 32 bins in the logarithmic case. In the worst case (logarithmic with large register values) as many as 2^31 values could be mapped into one bin. Since a branch will be taken or not taken based on a register value difference of 1, a substantial amount register/branch correlation information could be lost in the mapping.
1. If a branch occurs every 4 or 5 instructions (on average), and predicate predictors must be set 16 cycles before the branch, then a branch prediction must be made 3-4 branches ahead of time (conservatively assuming 1 instruction/cycle). This seems to imply we need to make predictions for 2^3 branches even though only one of those predictions will be used. Will this add substantially more code?
2. They mention super-block construction to eliminate multiple paths to a branch. How does super-block construction work, what are its effects on code size etc.?
[1] "Compiler Synthesized Dynamic Branch Prediction", S. A. Mahlke and B. Natarajan, Proceedings of the 29th International Symposium on Microarchitecture.