What is Pipeline Interlock?



"pipeline interlock" is a mechanism to detect hazard and resolve it.

This mechanism is necessary to preserve original data dependencies specified in a sequence of the instructions. There are three types of data dependent hazards:

  1. RAW(read after write)- Some data might be read before a necessary modification
  2. WAW(write after write)- A wrong data might be left because of a wrong sequence of write-operations
  3. WAR(write after read)- A new data might be written before a necessary reference

which correspond to

  1. true dependencies
  2. output dependencies
  3. anti-dependencies

respectively. An interlock prevents instructions from being executed in a wrong sequence to preserve the original data dependencies.


There are two general categories of hazards;


  1. "structural"
  2. "data dependent"

Data dependent hazards are described above. Structural hazards are caused by the collisions where two different instructions attempt to use the same hardware resource.


An example in CISC-3:

For a pipelined computer named CISC-3 having 3 stages, which are "Prefetch Unit," "Decode Unit" and "Execution Unit," an appropriate state transition in "Prefetch Unit" can be a simple way to resolve a hazard. There are "FLAG-REGISTERS", which are modified by some "compare instructions" and referred by "conditional branch instructions." There are three states; "IDLE", "FETCH" and "WAIT" for the "Prefetch Unit". The "WAIT" state is for the "compare instruction" to wait until the modification completes. 

  always @(posedge CLOCK1 or posedge RESET)
        begin : state_machine
		  if (RESET)   STATE <= `IDLE;
		  else 
		    begin
              case (STATE)
                `IDLE:   if(RUN) STATE<=`FETCH; else STATE<=`IDLE;
                `FETCH:  if (COND_BRA && STALL) STATE<=`WAIT;
                         else STATE<=`FETCH;
                `WAIT:   STATE<=`FETCH;     
                default: STATE<=`IDLE; // penalty is always 1 clock cycle,
              endcase                  // since new FR value will be known
		    end                // within the next cycle
        end


The STALL signal is generated as follows:


  wire STALL;

  assign STALL=FR_BUSY && (INSTRUCTION_BUFFER[15:12]==4'h4); 
                                // Conditional Branch

The FR_BUSY is set when an instruction which modifies the Flag Registers(FR) is decoded:


  reg FR_BUSY;

  always @(posedge CLOCK1)
      FR_BUSY=INSTRUCTION_BUFFER[15:12]==4'b0011; 
                                   // Compare




This hazard is sometimes called a "control hazard," which is essentially a RAW(read after write) hazard. The "FLAG-REGISTERS" might be referred by the "conditional branch instructions" before the modification.

Since the "Prefetch Unit" can not wait until the real modification of FLAG-REGISTER, the following "forwarding" should be used:


  always @(LEFT_OPERAND or RIGHT_OPERAND or FUNC_CNTL_CPR or FLAG_REGISTER)
    begin 
              if(FUNC_CNTL_CPR) 
                begin
                       if(LEFT_OPERAND > RIGHT_OPERAND) FLAG_FORWARDED=2'b10;
                  else if(LEFT_OPERAND == RIGHT_OPERAND) FLAG_FORWARDED=2'b00;
                  else FLAG_FORWARDED=2'b01;
                end
        else 
          FLAG_FORWARDED=FLAG_REGISTER;
    end  // end of "always" for FLAG_FORWARDing logic


Ryuichi TAKAHASHI



Related publications:

  1. Peter M. Kogge:
    The Architecture of Pipelined Computers,
    McGraw-Hill, New York (1981)

  2. Mike Johnson:
    Superscalar Microprocessor Design,
    P T R Prentice-Hall, Inc. (1991)

  3. John L. Hennessy and David A. Patterson:
    Computer Architecture A Quantitative Approach 2nd edition,
    Morgan Kaufmann Publishers, Inc. (1996)

  4. Ryuichi TAKAHASHI and Takeshi YOSHIMURA:
    "Strategies for High Level Synthesis," (in Japanese)
    The Trans. of the IEICE, VolJ74-A, No.2, pp.143-151 (1991)

  5. Ryuichi TAKAHASHI:
    System Development and Design Using Verilog HDL (in Japanese)
    Kyoritu-pub. (1996)
    ISBN978-4-320-12222-2



Some Hints on Computer Design



Microcomputer Design Educational Environment City-1



Ryuichi TAKAHASHI's personal homepage