Your processor is trying to predict the future long before you start with AI

Your processor is trying to predict the future long before you start with AI

In a more primitive but not so different way

If you have ever studied computer architecture, you probably know the basic steps the hardware takes to execute a certain routine. If you don’t, here is a brief explanation about this process [1] :

The first step is to have the high-level code translated to assembly language. The compiler is responsible for doing this. After that, the assembler will translate the assembly language into binary instructions. So, if your code has the following sentence in some high-level language:

A + B

The compiler will turn into:

add A,B

The assembler will translate to something like this:

From this point, the processor executes the following steps:

• Fetch: Read instruction from RAM.
• Decode: Understand the purpose of the instruction (add, for example) and set all flags and registers that will allow the execution of it.
• Execute: Process the instruction. The instruction can or not use the arithmetic logic unit (ALU). Arithmetic-logical instructions use ALU,
  and memory instructions can also use it for addresses calculation.
• Write-back: Write into the register set the results obtained.

This sequence is repeated all the time while the processor is operating and each step takes one clock cycle. The execution depends on decoding which depends on fetching. However, fetching doesn’t depend on decode which doesn’t depend on execution, so once the fetching of a certain instruction is done, the next instruction can be fetched already. The same goes for the others, that’s the processor pipeline (as the following picture shows).

Where do predictions come in?

To talk about predictions, we first need to talk about conditional jumps (or conditional branches). A conditional branch instruction is a jump to a new address that may or may not occur depending on a specific condition [2] . Translating to the high-level languages, it is basically an if-then-else clause:

if some condition:
   do this;
else:
   do this instead;

If the condition is satisfied, the code will continue its normal execution. If the condition is not satisfied, the code will jump all lines inside the if block to execute all lines inside the else block. This is one example of conditional branching. For’s and while’s are conditional branches too, since conditions define if the code will be repeated or go straight. The point about conditional branches is: the condition result needs to be calculated at execution time .

That means when a conditional branch instruction comes up in the pipeline, the processor will only know if the branch needs to be taken after calculating the condition result, that is, after the execution stage. Thus, the processor doesn’t know if the following instruction will be executed or a jump to another instruction will occur. This kind of dependency implies a pipeline bubble [3] .

A pipeline bubble, as the image above shows, is a kind of delay on the processor’s pipeline in order to solve some dependency (or hazard, in the computer architecture language) [1] . The grey blocks represent idle time. Considering that the first instruction of the image above is the conditional branch, the next instruction is fetched only after the conditional branch instruction finishes its execution step, to make sure that the next instruction to be executed will be the right one. So if you give it some thought, this isn’t sustainable in terms of performance. That’s where predictions come in.

The branch prediction

What choice the processor have if it doesn’t wait until the calculation of the conditional branches? Well, guessing or predicting the condition result could be a good choice… and it is. The process of predicting the condition result in order to don’t block the processor has been used for decades and it is called “branch prediction”.

The fact that they have been used for a long time does not imply that they are perfect, there is always room for improvement. Experiments using real processors revealed that reducing mispredictions by 50% improved the performance of the processor by 13% [4] . However, designing a branch predictor (BP) covers not only accuracy but a lot of other tradeoffs, such as the area used in the processor chip, energy consumption, and many others.

How does branch prediction work?

Harshal Parekh wrote a nice story not just explaining how it works but showing its impacts in a real situation. I really recommend the reading:

Like most prediction models, the branch prediction is usually based on the past behavior of conditional branches. The most simple branch prediction algorithm could be defined using a flag that indicates if the last branch was taken or not, and the algorithm will always guess that what happened last time will also happen next time. Thus, the flag needs to assume an initial value ( 1 for yes, 0 for no). If the guessing is correct, the flag will keep its value. If it doesn’t, the flag changes its value. An example can be given in the following situation.

After running a certain routine, a given branch b got the following behavior:

On the first three iterations, the branch wasn’t taken, on the following two, they were. The next four also wasn’t taken, and the last one was. Considering that our branch predictor starts with the flag as 0, the accuracy will be 70%. The image below represents each iteration with a red arrow, followed by the current flag value and a symbol representing if the branch behavior was predicted correctly.

The first misprediction will be on the fourth iteration because the last one was 0 (and the fourth is 1) . This way, the flag now changes its value to 1 . Since the branch will be taken on the following iteration, the prediction will be correct, however, on the sixth iteration, the branch is not taken again, so another miss prediction occurs. Now, the flag becomes 0 again and correctly predicts the next three iterations and then misses on the last iteration. In the end, we got 7 correct predictions and 3 mispredictions.

Obviously this is not the way processors do branch prediction nowadays. There is a bunch of other techniques that give much better results. You can look for some of them in this paper written by Sparsh Mittal.

Can AI be used for branch prediction?

It is quite easy to wonder if this kind of problem could be solved by artificial intelligence algorithms, and the answer is yes, they can . Since a long time ago, indeed. An example of a branch predictor that uses this kind of approach is the perceptron predictor , also addressed in the Sparsh Mittal survey . Due to recent advances in the field of artificial intelligence, the combination of these two areas is probably a hot trend inside the buildings of major tech companies such as Intel and AMD, and we can expect much more to come.

So if you enjoy computer architecture and artificial intelligence, this is the research area that you can use all your knowledge in order to improve even more the processors that we have today.

References

[1] Patterson, David A., and John L. Hennessy. Computer Organization and Design: The Hardware/Software Interface (2013). Paperback, Morgan Kaufmann Publishers.

[2] Henry, G. Glenn, and Terry Parks. Static branch prediction mechanism for conditional branch instructions (2003). U.S. Patent №6,571,331.

[3] Chang, Po-Yung. Classification-directed branch predictor design (1997). Doctoral dissertation, University of Michigan.

[4] Mittal, Sparsh. A survey of techniques for dynamic branch prediction (2019). Concurrency and Computation: Practice and Experience 31.1.