Wikipedia states:

The main advantage of the neural predictor is its ability to exploit long histories while requiring only linear resource growth. Classical predictors require exponential resource growth.

What is the reason for this?

  • $\begingroup$ Wikipedia lists several references in that section. Have you read them? Do they address this question? Can you summarize what you found? $\endgroup$ – D.W. Feb 11 at 20:43

In a classic perceptron-based branch predictor, each static branch has one weight value for each global history bit. Therefore the storage is equal to the number of static branches with entries times the size of weights times the number of history bits. If the number of static branches is constant and the weight size is constant, the storage size increases linearly with the number of history bits. The computation overhead for a straightforward tree design would be a little more complex: the final addition of each half would replace a carry-propagate adder at the end with a carry-save adder and the final addition would use a carry-propagate adder one bit larger. (For a branch direction decision, one technically does not need the full sum but only the most significant bit.)

If one wants to include correlations of history bits (e.g., branch A is usually taken when history bit 7 is set and history bit 9 is clear and when history bit 7 is clear and history bit 9 is set will not be predicted well with only separate weights for history bits 7 and 9), the growth would obviously be superlinear. The classic design does not account for correlations among history bits.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.