Reference no: EM133309120

Assignment:

Question

Instead of using the static predict not-taken scheme for conditional branch instructions we could consider implementing a dynamic branch predictor. A 1-bit branch predictor uses the previous outcome of a conditional branch to predict the next outcome, with 0  meaning not-taken and 1 meaning taken. The predictor state is stored in a branch history table (BHT) indexed by the least significant bits of the program counter by taking it modulo the size of the table. Unconditional jumps don't use the BHT. Consider a 1-bit dynamic branch predictor with an 8-entry branch history table (BHT) that initially has all entries set to "0" for predict-not-taken. Assume that bubble begins at PC 0x100 and that the processor is designed assuming all instructions are 4 byte aligned.

a) What will be the state of the BHT after bubble() with the optimized inner loop is called with a 10-element array sorted in ascending order?

b) How many of the predictions are correct?

c) How many of the predictions are incorrect?

d) What is the misprediction rate?

e) What are the total number of stall/squash cycles due to mispredicted branches?

f) What is the CPI of bXX for bubble considering control hazards?

g) Suppose you can add a 1-bit branch predictor to the pipeline without changing the clock frequency. What is the speedup of using a 1-bit predictor over static predict-not-taken for this call to bubble? Use the Iron Law. Round to 3 significant digits.