Problem $3$

Suppose we have the following loop executing on a pipelined LC$-3$b machine.

Assume that before the loop starts, the registers have the following decimal values stored in

them:

The fetch stage takes one cycle, the decode stage also takes one cycle, the execute stage

takes a variable number of cycles depending on the type of instruction $($see below$),$ and the

store stage takes one cycle.

All execution units $($including the load$/$store unit$)$ are fully pipelined and the following instructions

that use these units take the indicated number of cycles:

Data forwarding is used wherever possible. Instructions that are dependent on the previous

instructions can make use of the results produced right after the previous instruction finishes the

execute stage. Multiple Instructions can write the results to the register file concurrently in the

same cycle.

The target instruction after a branch can be fetched when the BR instruction is in ST stage. For

example, the execution of an ADD instruction followed by a BR would look like:

The pipeline implements $"$in$-$order execution." A scoreboarding scheme is used as discussed in

class.

Assumptions:

There are enough ports to the register file.

There are enough ports to the memory.

There are separate execution units for ADD, AND, STW$,$ and BR instructions $($They can

all be in the execute stage at the same time.$)$

Answer the following questions:

How many cycles does the above loop take to execute if no branch prediction is used?

How many cycles does the above loop take to execute if all branches are predicted with

$100\%$ accuracy?

How many cycles does the above loop take to execute if a static BTFN $($backward

taken$-$forward not taken$)$ branch prediction scheme is used to predict branch directions?

What is the overall branch prediction accuracy? What is the prediction accuracy for each

branch?

A BTFN $($backward taken$-$forward not taken$)$ predictor will predict a branch taken

if the branch location is to a PC less than the branch instruction $("$backwards$"$ in addresses$),$ and

will predict a branch not taken if the branch location is to a PC greater than the branch

instruction $("$forwards$"$ in addresses$).$