<commit_before># Pipelined MIPS CPU

## Warnings

*   for all control signal: explict for zero if it's uneccessory
*   for all output: explict for zero if it's uneccessory

## Tips

*   PC，IR最好一直传递到最后一级，这样方便观测流水线运行的状况。
*   流水线各级是否产生气泡可以用LED指示灯显示，方便观察流水线运行状况

## Instructions

1. Data processing
2. PSR (Program Status Register) transfer
3. Multiply
4. Single data swap
5. Single data transfer
6. Branch Predictor
7. Block data transfer
8. Coprocessor register transfer
9. Coprocessor data transfer
10. Coprocessor data operation
11. Undefined Instruction
12. Software interrupt 

## Frameworks

### Controller

*   Instruction decoding
*   Pipeline Registers
*   FSM(branch predictor)
*   Interrupt handler

## Installation

```sh
$ sudo apt install logisim # install logisim platform
$ sudo apt install verilog # install icarus verilog simulatr
$ sudo apt install gtkwave # install waveform viewer comes with icarus verilog
$ sudo apt install yosys   # synthesize
$ sudo apt install geda    # graphic eda toolchains
```

## Tools

```sh
$ iverilog -o demo demo_tb.v demo.v # compiler
$ iverilog -o demo -c src.list      # src.list => demo.v demo_tb.v
$ iverilog -s main -o hello hello.v # set root module to `main`
$ iverilog -E -o preprocessed.v unpreprocessed.v # pre-process signal stage
$ iverilog -I/include               # for `include directive
$ iverilog -y/lib                   # add lib search path
$ vvp demo                          # simulation runtime engine
$ vvp -n demo -lxt2
$ gtkwave demo.lxt
$ gtkwave trace.vcd
```

### test bench

*   `$time/$finish/$display/$monitor`

*   `$value$plusargs`

```verilog
module main;

  reg clk, reset;
  reg [31:0] x;
  wire [15:0] y;
  wire        rdy;

  sqrt32 dut (clk, rdy, reset, x, y);

  always #10 clk = ~clk;

  initial begin
     clk = 0;
     reset = 1;

     if (! $value$plusargs("x=%d", x)) begin
        $display("ERROR: please specify +x=<value> to start.");
        $finish;
     end

     #35 reset = 0;

     wait (rdy) $display("y=%d", y);
     $finish;
  end // initial begin

endmodule // main
```

```sh
$ iverilog -osqrt_plusargs.vvp sqrt_plusargs.v sqrt.v
$ vvp sqrt_plusargs.vvp +x=81
  # => y = 9
```

*   $readmemh

```verilog
module main;

  reg clk, reset;
  reg [31:0] data[4:0];
  reg [31:0] x;
  wire [15:0] y;
  wire        rdy;

  sqrt32 dut (clk, rdy, reset, x, y);

  always #10 clk = ~clk;

  integer i;
  initial begin
     /* Load the data set from the hex file. */
     $readmemh("sqrt.hex", data);
     for (i = 0 ;  i <= 4 ;  i = i + 1) begin
       clk = 0;
       reset = 1;

       x = data[i];

       #35 reset = 0;

       wait (rdy) $display("y=%d", y);
     end
     $finish;
  end // initial begin

endmodule // main
```

```sh
  # sqrt.hex =>
  # 51
  # 19
  # 1a
  # 18
  # 1
$ iverilog -osqrt_readmem.vvp sqrt_readmem.vl sqrt.vl
$ vvp sqrt_readmem.vvp
  # y = 9
  # y = 5
  # y = 5
  # y = 4
  # y = 1
```

### GTKWave

In your .v file, specify:

```verilog
$dumpfile(“file.vcd”)
$dumpvars(level, vars_or_modules)
```

where level means 0 all or 1 listed only:

*   file.vcd is created when vvp is run
*   Visualize using: gtkwave file.vcd

```verilog
module trace;
    reg clk=0; reg[3:0]a=4'd0; reg b=0;
    always #1 clk=~clk;
    always @(posedge clk) begin
        a=a+1; b=a[2]; end
    initial begin
        $dumpfile(“trace.vcd”);
        $dumpvars(0, trace); // all vars
    end
endmodule
```

### yosys

## ideal pipeline registers

### IF/ID

*   pc
*   ir

### ID/EX

*   pc
*   ir
 
*   WritetoLO(WB)
*   RegWe(WB)
*   RAMtoReg(WB)
*   LOtoReg(WB)
*   Syscall(WB)
*   RAMWe(MEM)
*   RAMByte(MEM)
*   RegDst(EX)
*   ALUOp(EX)
*   ALUSrc(EX)
*   ExtOp(EX)
*   ALUSham(EX)
*   Beq(EX)
*   Bne(EX)
*   Bgtz(EX)
*   Jmp(EX)
*   Jal(EX)
*   Jr(EX)

*   rt(EX)
*   rd(EX)
*   sham(EX)
*   imm16(EX)
*   imm26(EX)
*   R1(EX)
*   R2(EX/MEM)
*   $v0(WB)
*   $a0(WB)

### EX/MEM

*   pc
*   ir
 
*   WriteTLO(WB)
*   RegWe(WB)
*   RAMtoReg(WB)
*   LOToReg(WB)
*   Syscall(WB)
*   RAMWe(MEM)
*   RAMByte(MEM)
 
*   Result(MEM/WB)
*   RW# (WB)
*   R2(MEM)
*   $v0(WB)
*   $a0(WB)

### MEM/WB

*   pc
*   ir
 
*   WriteTLO(WB)
*   RegWe(WB)
*   RAMtoReg(WB)
*   LOToReg(WB)
*   Syscall(WB)
 
*   RAMData(WB)
*   Result(WB)
*   RW# (WB)
*   $v0(WB)
*   $a0(WB)

## hazard

### hazard detection in forward unit

#### decode stage

*   for branch usage in decode stage
*   for WB.RegData -> ID/EX pipeline register data hazard

```verilog
if ((IF/ID.rs != 0) && (IF/ID.rs == EX/MEM.RW#) && EX/MEM.RegWe) begin
    IF/ID.ForwardA = 10 (from memory access stage)
end else if ((IF/ID.rs != 0) && (IF/ID.rs == MEM/WB.RW#) && MEM/WB.RegWe) begin
    IF/ID.ForwardA = 01 (from write back stage)
end else begin
    IF/ID.ForwardA = 00 (no forwarding)
end

if ((IF/ID.rt != 0) && (IF/ID.rt == EX/MEM.RW#) && EX/MEM.RegWe) begin
    IF/ID.ForwardA = 10 (from memory access stage)
end else if ((IF/ID.rt != 0) && (IF/ID.rt == MEM/WB.RW#) && MEM/WB.RegWe) begin
    IF/ID.ForwardA = 01 (from write back stage)
end else begin
    IF/ID.ForwardA = 00 (no forwarding)
end
```

#### execute stage

*   id/ex r-instr(r-r-alu, r-imm-alu, load/store, branch) + mem/wb r-r-alu: $rd => $rs/$rt
*   id/ex r-instr(r-r-alu, r-imm-alu, load/store, branch) + mem/wb r-imm-alu: $rd => $rs/$rt
*   id/ex r-instr(r-r-alu, r-imm-alu, load/store, branch) + mem/wb load: $rt => $rs/$rt
*   id/ex r-instr(r-r-alu, r-imm-alu, load/store, branch) + jal : $ra => $rs/$rt

```verilog
if ((ID/EX.rs != 0) && (ID/EX.rs == EX/MEM.RW#) && EX/MEM.RegWe) begin
    ID/EX.ForwardA = 10 (from memory access stage)
end else if ((ID/EX.rs != 0) && (ID/EX.rs == MEM/WB.RW#) && MEM/WB.RegWe) begin
    ID/EX.ForwardA = 01 (from write back stage)
end else begin
    ID/EX.ForwardA = 00 (no forwarding)
end

if ((ID/EX.rt != 0) && (ID/EX.rt == EX/MEM.RW#) && EX/MEM.RegWe) begin
    ID/EX.ForwardB = 10 (from memory access stage)
end else if ((ID/EX.rt != 0) && (ID/EX.rt == MEM/WB.RW#) && MEM/WB.RegWe) begin
    ID/EX.ForwardB = 01 (from write back stage)
end else begin
    ID/EX.ForwardB = 00 (no forwarding)
end
```

#### MEM stage

ex/mem sw + mem/wb load: $rt => $rt

```verilog
assign MEMForward = (MEM/WB.RegWe && EX/MEM.RAMWe && EX/MEM.rt == MEM/WB.RW#)
```

### load-use hazard and branch hazard

*   load use hazard when: id/ex r-instr(r-r-alu, r-imm-alu, load/store, branch) mem load
*   branch hazard: forward + stall + flush(IF/ID)

```verilog
// load use stall
// stall 1 clock
// then forward unit get start to work
assign lwstall = ID/EX.rt != 0 && ID/EX.RAMtoReg && (ID/EX.rt == IF/ID.rs || ID/EX.rt == IF/ID.rt)

// with forward, hazard still exist (the same to load use stage)
// branch stall in decode stage
// stall 1 clock
// then forward unit get start to work
assign branchstall = (IF/ID.Branch && ID/EX.RegWe && (ID/EX.RW# == IF/ID.rs || ID/EX.RW# == IF/ID.rt))
    || (IF/ID.Branch && EX/MEM.RAMtoReg && (EX/MEM.RW# == IF/ID.rs || EX/MEM.RW# == IF/ID.rt))

assign StallF(PC) = StallD(IF/ID) = FlushE(ID/EX) = (lwstall || branchstall)
assign FlushD = success (jmp || jr || jal || branch)

assign en_pipeline_register = !StallX
assign rst_pipeline_register = FlushE
```

### how to stall the pipeline

*   flush signal: Force control values in ID/EX register to 0
    *   EX, MEM and WB do nop (no-operation)
*   Prevent update of PC and IF/ID register
    *   Using instruction is decoded again
    *   Following instruction is fetched again
    *   1-cycle stall allows MEM to read data for lw
        *   Can subsequently forward to EX stage
*   send zero signal(RegWe/RAMWe/WritetoLO) to pipeline registers

if detected, stall and insert bubble

## branch predict

*   always not taken
*   backward taken, forward not taken
*   **饱和计数预测器**(Saturating counter/2 bit predictor) algorithm state machine
*   神经分支预测器

### 2 bit predictor

not taken(miss: should taken) -> not taken(miss: should taken) -> taken

*   get true outcome: just like signal in PC update logic = (zero && beq) || (!zero && bne)<commit_msg>update(arch-pipeline hazard): complete most of hazard resolution<commit_after># Pipelined MIPS CPU

## Warnings

*   for all control signal: explict for zero if it's uneccessory
*   for all output: explict for zero if it's uneccessory

## Tips

*   PC，IR最好一直传递到最后一级，这样方便观测流水线运行的状况。
*   流水线各级是否产生气泡可以用LED指示灯显示，方便观察流水线运行状况

## Instructions

1. Data processing
2. PSR (Program Status Register) transfer
3. Multiply
4. Single data swap
5. Single data transfer
6. Branch Predictor
7. Block data transfer
8. Coprocessor register transfer
9. Coprocessor data transfer
10. Coprocessor data operation
11. Undefined Instruction
12. Software interrupt 

## Frameworks

### Controller

*   Instruction decoding
*   Pipeline Registers
*   FSM(branch predictor)
*   Interrupt handler

## Installation

```sh
$ sudo apt install logisim # install logisim platform
$ sudo apt install verilog # install icarus verilog simulatr
$ sudo apt install gtkwave # install waveform viewer comes with icarus verilog
$ sudo apt install yosys   # synthesize
$ sudo apt install geda    # graphic eda toolchains
```

## Tools

```sh
$ iverilog -o demo demo_tb.v demo.v # compiler
$ iverilog -o demo -c src.list      # src.list => demo.v demo_tb.v
$ iverilog -s main -o hello hello.v # set root module to `main`
$ iverilog -E -o preprocessed.v unpreprocessed.v # pre-process signal stage
$ iverilog -I/include               # for `include directive
$ iverilog -y/lib                   # add lib search path
$ vvp demo                          # simulation runtime engine
$ vvp -n demo -lxt2
$ gtkwave demo.lxt
$ gtkwave trace.vcd
```

### test bench

*   `$time/$finish/$display/$monitor`

*   `$value$plusargs`

```verilog
module main;

  reg clk, reset;
  reg [31:0] x;
  wire [15:0] y;
  wire        rdy;

  sqrt32 dut (clk, rdy, reset, x, y);

  always #10 clk = ~clk;

  initial begin
     clk = 0;
     reset = 1;

     if (! $value$plusargs("x=%d", x)) begin
        $display("ERROR: please specify +x=<value> to start.");
        $finish;
     end

     #35 reset = 0;

     wait (rdy) $display("y=%d", y);
     $finish;
  end // initial begin

endmodule // main
```

```sh
$ iverilog -osqrt_plusargs.vvp sqrt_plusargs.v sqrt.v
$ vvp sqrt_plusargs.vvp +x=81
  # => y = 9
```

*   $readmemh

```verilog
module main;

  reg clk, reset;
  reg [31:0] data[4:0];
  reg [31:0] x;
  wire [15:0] y;
  wire        rdy;

  sqrt32 dut (clk, rdy, reset, x, y);

  always #10 clk = ~clk;

  integer i;
  initial begin
     /* Load the data set from the hex file. */
     $readmemh("sqrt.hex", data);
     for (i = 0 ;  i <= 4 ;  i = i + 1) begin
       clk = 0;
       reset = 1;

       x = data[i];

       #35 reset = 0;

       wait (rdy) $display("y=%d", y);
     end
     $finish;
  end // initial begin

endmodule // main
```

```sh
  # sqrt.hex =>
  # 51
  # 19
  # 1a
  # 18
  # 1
$ iverilog -osqrt_readmem.vvp sqrt_readmem.vl sqrt.vl
$ vvp sqrt_readmem.vvp
  # y = 9
  # y = 5
  # y = 5
  # y = 4
  # y = 1
```

### GTKWave

In your .v file, specify:

```verilog
$dumpfile(“file.vcd”)
$dumpvars(level, vars_or_modules)
```

where level means 0 all or 1 listed only:

*   file.vcd is created when vvp is run
*   Visualize using: gtkwave file.vcd

```verilog
module trace;
    reg clk=0; reg[3:0]a=4'd0; reg b=0;
    always #1 clk=~clk;
    always @(posedge clk) begin
        a=a+1; b=a[2]; end
    initial begin
        $dumpfile(“trace.vcd”);
        $dumpvars(0, trace); // all vars
    end
endmodule
```

### yosys

## ideal pipeline registers

### IF/ID

*   pc
*   ir

### ID/EX

*   pc
*   ir
 
*   WritetoLO(WB)
*   RegWe(WB)
*   RAMtoReg(WB)
*   LOtoReg(WB)
*   Syscall(WB)
*   RAMWe(MEM)
*   RAMByte(MEM)
*   RegDst(EX)
*   ALUOp(EX)
*   ALUSrc(EX)
*   ExtOp(EX)
*   ALUSham(EX)
*   Beq(EX)
*   Bne(EX)
*   Bgtz(EX)
*   Jmp(EX)
*   Jal(EX)
*   Jr(EX)

*   rt(EX)
*   rd(EX)
*   sham(EX)
*   imm16(EX)
*   imm26(EX)
*   R1(EX)
*   R2(EX/MEM)
*   $v0(WB)
*   $a0(WB)

### EX/MEM

*   pc
*   ir
 
*   WriteTLO(WB)
*   RegWe(WB)
*   RAMtoReg(WB)
*   LOToReg(WB)
*   Syscall(WB)
*   RAMWe(MEM)
*   RAMByte(MEM)
 
*   Result(MEM/WB)
*   RW# (WB)
*   R2(MEM)
*   $v0(WB)
*   $a0(WB)

### MEM/WB

*   pc
*   ir
 
*   WriteTLO(WB)
*   RegWe(WB)
*   RAMtoReg(WB)
*   LOToReg(WB)
*   Syscall(WB)
 
*   RAMData(WB)
*   Result(WB)
*   RW# (WB)
*   $v0(WB)
*   $a0(WB)

## hazard

### hazard detection in forward unit

#### decode stage

*   for branch usage in decode stage
*   for WB.RegData -> ID/EX pipeline register data hazard

```verilog
if ((IF/ID.rs != 0) && (IF/ID.rs == EX/MEM.RW#) && EX/MEM.RegWe) begin
    IF/ID.ForwardA = 10 (from memory access stage)
end else if ((IF/ID.rs != 0) && (IF/ID.rs == MEM/WB.RW#) && MEM/WB.RegWe) begin
    IF/ID.ForwardA = 01 (from write back stage)
end else begin
    IF/ID.ForwardA = 00 (no forwarding)
end

if ((IF/ID.rt != 0) && (IF/ID.rt == EX/MEM.RW#) && EX/MEM.RegWe) begin
    IF/ID.ForwardA = 10 (from memory access stage)
end else if ((IF/ID.rt != 0) && (IF/ID.rt == MEM/WB.RW#) && MEM/WB.RegWe) begin
    IF/ID.ForwardA = 01 (from write back stage)
end else begin
    IF/ID.ForwardA = 00 (no forwarding)
end
```

#### execute stage

*   id/ex r-instr(r-r-alu, r-imm-alu, load/store, branch) + mem/wb r-r-alu: $rd => $rs/$rt
*   id/ex r-instr(r-r-alu, r-imm-alu, load/store, branch) + mem/wb r-imm-alu: $rd => $rs/$rt
*   id/ex r-instr(r-r-alu, r-imm-alu, load/store, branch) + mem/wb load: $rt => $rs/$rt
*   id/ex r-instr(r-r-alu, r-imm-alu, load/store, branch) + jal : $ra => $rs/$rt

```verilog
if ((ID/EX.rs != 0) && (ID/EX.rs == EX/MEM.RW#) && EX/MEM.RegWe) begin
    ID/EX.ForwardA = 10 (from memory access stage)
end else if ((ID/EX.rs != 0) && (ID/EX.rs == MEM/WB.RW#) && MEM/WB.RegWe) begin
    ID/EX.ForwardA = 01 (from write back stage)
end else begin
    ID/EX.ForwardA = 00 (no forwarding)
end

if ((ID/EX.rt != 0) && (ID/EX.rt == EX/MEM.RW#) && EX/MEM.RegWe) begin
    ID/EX.ForwardB = 10 (from memory access stage)
end else if ((ID/EX.rt != 0) && (ID/EX.rt == MEM/WB.RW#) && MEM/WB.RegWe) begin
    ID/EX.ForwardB = 01 (from write back stage)
end else begin
    ID/EX.ForwardB = 00 (no forwarding)
end
```

#### MEM stage

ex/mem sw + mem/wb load: $rt => $rt

```verilog
assign MEMForward = (MEM/WB.RegWe && EX/MEM.RAMWe && EX/MEM.rt == MEM/WB.RW#)
```

### load-use hazard and branch hazard

*   load use hazard when: id/ex r-instr(r-r-alu, r-imm-alu, load/store, branch) mem load
*   branch hazard: forward + stall + flush(IF/ID)

```verilog
// load use stall
// stall 1 clock
// then forward unit get start to work
assign lwstall = ID/EX.rt != 0 && ID/EX.RAMtoReg && (ID/EX.rt == IF/ID.rs || ID/EX.rt == IF/ID.rt)

// with forward, hazard still exist (the same to load use stage)
// branch stall in decode stage
// stall 1 clock
// then forward unit get start to work
assign branchstall = (IF/ID.Branch && ID/EX.RegWe && (ID/EX.RW# == IF/ID.rs || ID/EX.RW# == IF/ID.rt))
    || (IF/ID.Branch && EX/MEM.RAMtoReg && (EX/MEM.RW# == IF/ID.rs || EX/MEM.RW# == IF/ID.rt))

assign StallF(PC) = StallD(IF/ID) = FlushE(ID/EX) = (lwstall || branchstall)
assign FlushD = success (jmp || jr || jal || branch)

assign en_pipeline_register = !StallX
assign rst_pipeline_register = FlushE
```

### how to stall the pipeline

*   flush signal: Force control values in ID/EX register to 0
    *   EX, MEM and WB do nop (no-operation)
*   Prevent update of PC and IF/ID register
    *   Using instruction is decoded again
    *   Following instruction is fetched again
    *   1-cycle stall allows MEM to read data for lw
        *   Can subsequently forward to EX stage

if detected, stall and insert bubble

## branch predict

*   always not taken
*   backward taken, forward not taken
*   **饱和计数预测器**(Saturating counter/2 bit predictor) algorithm state machine
*   神经分支预测器

### 2 bit predictor

not taken(miss: should taken) -> not taken(miss: should taken) -> taken

*   get true outcome: just like signal in PC update logic = (zero && beq) || (!zero && bne)
{'fraction_non_alphanumeric': 0.15558335939943696, 'fraction_numerical': 0.016765717860494214, 'mean_word_length': 2.7341742583508526, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 27, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4591773', 'n_tokens_mistral': 6865, 'n_tokens_neox': 6441, 'n_words': 1803}