ROB/Problem 4a

This problem focuses on processors with dynamic scheduling, speculative execution using a reorder buffer, and dynamic branch prediction.

Screen Shot 2014-04-16 at 4.25.48 PM.png

  • Explain how dynamic branch prediction works when using a 2-bit prediction scheme. Use the program above to demonstrate how the prediction works. Also, describe how the prediction works for a program containing two or more branches?

  • In what way does a reorder buffer help speculation? What is the key points when introducing support for speculation?

  • In a processor with dynamic scheduling according to Tomasulo's algorithm, hardware based speculation using a reorder buffer (ROB), and dynamic branch prediction, execution of each instruction follows a sequence of steps that is somewhat different depending on the type of instruction. Below are the steps carried out for an ALU instruction. What are the corresponding steps for handling a store instruction?

  • Issue when reservation station and ROB entry is available Read already available operands from registers and instruction Send instruction to reservation station Tag unavailable operands with ROB entry Tag destination register with ROB entry Write destination register to ROB entry Mark ROB entry as busy

  • Execute after issue Wait for operand values on CDB (if not already available) Compute result

  • Write result when CDB and ROB available Send result on CDB to reservation stations Update ROB entry with result, and mark as ready Free reservation station

  • Commit when at head of ROB and ready Update destination register with result from ROB entry Untag destination register Free ROB entry

  1. Explain how RAW hazards are resolved in the basic Tomasulo's algorithm.

Solution

  1. For our example program we would have one entry corresponding to the BNE instruction in the end of the program. The prediction would evolve according to this table if we assume we start in state 00:

Screen Shot 2014-04-16 at 5.34.52 PM.png

For a program with two branches, we would get a 2-bit state entry for each branch as long as they do not share the same index in the branch-prediction bu er. Branches with di erent index (entries) are not correlated with each other.

  1. For a program with two branches, we would get a 2-bit state entry for each branch as long as they do not share the same index in the branch-prediction bu er. Branches with di erent index (entries) are not correlated with each other.

The corresponding steps for a store instruction is:

(a) Issue when reservation station and ROB entry is available

    Read already available operands from registers and instruction    
    Send instruction to reservation station   
    Tag unavailable operands with ROB entry   
    Mark ROB entry as busy

(b) Execute after issue 

    Wait for operand values on CDB (if not already available)    
    Compute address and store it in ROB entry

(c) Write result when CDB and ROB available

 Update ROB entry with source register value, and mark as ready
 Free reservation station

(d) Commit when at head of ROB and ready 

Write result (source register value) to memory at computed address
 Free ROB entry

The important points are:

(1) The actual write is done at the commit stage, 
(2) To carry out the write, the address needs to be computed (execute stage), and, 
(3) the source operand (the value to write) is needed before commit is possible.
  1. RAW hazards are avoided by delaying instruction execution until the source operands are available. Instructions wait in a reservation station until source operands are available. Earlier instructions that write dependent values send their results directly to the waiting reservation stations.

This problem was adapted from: "Exercises for Computer Architecture", Anders Ardo, Lund University