Modern microprocessors use a branch table buffer to assist predictions made in response to control

hazards. On a branch:

Make a prediction, based on the branch table buffer.

If you were right, no action is necessary.

If you were wrong, flush the pipeline. The penalty can vary based on how you implemented

the microprocessor, but in the videos we suggested moving the entire branch logic to the ID

stage to reduce this to $1cc.$

From item $1,$ there exists some cache table in the microprocessor. For each row it contains:

The address of the branch encountered. This is the index. Typically it is some hash of the

lower bits of the address, but we will use the whole address for today's activity.

For that branch, the correct branch target address when it was last evaluated.

Modern microprocessors will contain some history in each row about the trend of the branch being

taken or not. We are not modelling that with today's activity. Note that each branch instruction

has its own row in the table.

The instructor will hand$-$trace this code and complete a branch table buffer as an example.

Repeat the last exercise for the following code snippet. Assume it was called with a value of $n=3.$

It's an implementation of the Fibonacci number, with two conditionals each base case $(f_0=0$ and

$($:$f_1=1\}.$

The following question is free response but you and your partner should use math to support your

response. Hint: trees.

Calculate the number of clock cycles it takes to run the previous question, if a mistake in

prediction is a penalty of $1c{c}^1$

Assuming that the processor no longer predicted the branch and interlocked until the condition

was evaluated, how long does it take to run the code? Hint: This is essentially taking a penalty

on each branch..

This module discussed moving the branch logic to the ID stage. But, what if it remained in

the MEM stage $(3$ cc penalty$).$ Recalculate the run time if you interlocked using this scheme.

VERY IMPORTANT $-$ USE TREES FOR THE MATH PLEASE!