Astrologers in our processors

Ya we have an astrologer in our modern micro processors he is the “Branch Predictor”. I have been surfing in the web then I have gone crazy to find out what is the question i.e most viewed and most voted question on stack overflow then I came across a question which is viewed around 500k times, The Question has 8886 up votes,  8946 stars and the answer had 13457 up votes. Let’s come to the point

Branch Predictor predicts which way the branch ( say if-else) goes and continues with the instructions in that branch before actually evaluating the result of the boolean expression if the prediction comes out to be true it continues to execute that part of the code else it discards the instructions that got evaluated and goes to the other branch. This technique is used by modern pipelined micro processor with x86 architectures for better performance.

Branch predictors mostly predicts the value of the boolean expression(i.e which way to go) from the previously calculated outputs of the boolean outputs i.e it tries to recognize a pattern.

Now let’s see the effect of branch prediction on our codes:

Say you have an N sized array named “A” (say a) and you would like to find all the elements less than an element ‘a’ (say) in the array now using general procedure checking every element in the array

CASE 1: Array Is Not Sorted

Now it checks with each element if it is less than a then it executes that part of the code that increments code else don’t.  If the array is not sorted branch predictor as usually tries to predict whether the number is less than ‘a'(in this case) or not but as the array is not sorted most of the times there is a possibility that the predictor  is wrong and it has to discard the instructions it had already fetched along the other branch.

CASE 2:Array Is Sorted

When the array is sorted we have all the numbers less than ‘a’ in the beginning of the N-sized array and all the numbers greater than ‘a’ will be towards the end and branch predicts the correct value most of the times and have a better performance as each times it saves the time for execution of the boolean execution which decides the branch;

Amazing right?????

Related links:

Stack Overflow link is here

wiki link is here

Advertisements