How can I fix delay between Instruction and Program Counter?

Question

I am designing the MIPS processor, this includes Data Memory and Instruction memory for testing. I had a problem with IM synthesis covered in this question (How to make a synthesizable Instruction Memory in SystemVerilog?) and after rewriting it as adviced (ff with a case statement) another problem occured.

The problem: Insruction in CPU has one cycle delay from the Program Counter. Thus, when branch instruction (number i) come, the Program Counter is already (i+1) and then come instr (i+1) and PC is PC_branch. How can I fix it? Delay is caused by this ff in IM. Code and waveforms are below.

The code:

always_ff @(posedge clk) begin
case (addr)      
        32'd0 : rom_ff <= 32'h2408000F; // a = F
        32'd1 : rom_ff <= 32'h240A0000; // res = 0

        32'd2 : rom_ff <= 32'h01485021; // (*) res = res + a
        32'd3 : rom_ff <= 32'h2508FFFF; // a = a - 1

        32'd4 : rom_ff <= 32'h1500FFFD; // if (a != 0) goto (*)
        32'd5 : rom_ff <= 32'hAC0A0ADD; 
        default : rom_ff <= 32'h0;
    endcase
end

The waveform of CPU signals:

Answer 1

What you've encountered there are the problems that come with instruction pipelining. I assume that you're going to synthesize your processor for running it on an FPGA at some point, so removing the register between the instruction memory and the rest of the CPU is sadly not an option.

To fix this, you have three options.

• Ignore the problem. After all, your processor still behaves in a deterministic way - the only problem is that it will execute an additional instruction after a branch. This is called a branch delay slot, which means that the instruction that comes after a branch will be executed as if it was actually before the branch. A lot of processors have this kind of delay slot and compilers can handle them just fine. Early MIPS processors had delay slots, too.
• Unconditionally stall the pipeline after a branch got fetched. This means that you halt the program counter for one cycle and insert a NOP into the pipeline whenever you encounter a branch, which effectively hides the delay slot.
• Flush the pipeline when a branch is taken. This means that your processor keeps executing the instruction stream normally until it detects that it has to jump. At this point, it throws away all the instructions after the jump that it has already fetched. In your case, there would only be a single instruction to throw away.

You might also take a look at how classic RISC pipelines are organized and what a hazard is in a pipeline. Once you implement memory accesses in your processor, you might also come across hazards caused by data loaded from memory not being available fast enough. You can resolve these issues in a similar way by either stalling the pipeline or accepting that you have so-called load delay slots, which means that the data loaded from memory isn't available immediately to the instruction following the load. Some processors have this kind of delay slot, too, although it's less common than branch delay slots.

Answer 2

• Another good option is to use branch prediction. There are many branch prediction algorithms which you can research. Many modern processors use branch prediction. So if the branch predicted is the right one, you win and save cycles. If the branch predicted is the wrong one, you have to clear the data.

• Out-of-order execution can be used to keep the CPU busy. In this technique, many idle/wasted cycles are avoided. The order of execution of instructions is not the original order in out-of-order execution.

Further reading:

• Saylor Academy's free online certificate course on Computer Architecture. It covers MIPS. See: https://learn.saylor.org/course/view.php?id=71
• Free online course from Coursera: https://www.coursera.org/learn/comparch/