Supporting Branches

1Learning Outcomes¶

• Implement a datapath that supports conditional branches (B-Type).

• Explain how the input/output signals of the branch comparator help determine (for all B-Type instructions) if a branch is “taken.”

• Explain how the PCSel control signal determines the instruction to execute in the next clock cycle.

To support branch instructions like beq we must consider state element updates, arithmetic operations, and data selectors.

State element updates:

• RegFile: We read two registers rs1 and rs2 and compare the values R[rs1] and R[rs2]. We do not write to any registers.

• PC: We read from and write to PC. The value to write now conditionally depends on the result of the two-register comparison, which determines whether a branch is taken:

  • taken: pc + 4

  • not taken: pc + imm

• DMEM: No reading nor writing.

Like before, we reuse what already exists in our R-, I-, and S-Type datapath. Even with this, we will need to add three new blocks and some additional control logic.

1.1Branch Comparator¶

There are three arithmetic operations that branch instructions must (proactively) perform.

1. pc + 4. This hardware is already in our datapath.

2. pc + imm.

3. Compare R[rs1] and R[rs2].

We only have one general-purpose ALU available during the EX phase of our single-cycle datapath. We use this ALU to compute pc + imm. We discuss details below

Since this ALU is now busy, we must introduce additional combinational logic to compute a comparison of R[rs1] and R[rs2] within the same clock cycle. We call this new combinational logic block the branch comparator.

We discuss the details of the branch comparator at the end of this section.

1.2MUX for PC input¶

To conditionally update the input to the PC element, we introduce a new mux that selects between pc + imm and pc + 4 to feed into the PC element. We also therefore introduce a new control signal PCSel to feed into this mux.

These two new blocks are shown in Figure 1. The branch comparator performs a logical operation to compare R[rs1] and R[rs2] and feeds two 1-bit-wide signals, BrEq and BrLT, into control logic. The new mux uses PCSel to update PC based on the branch result.

1.3MUX for ALU input¶

We need one more mux in our datapath to compute PC + imm with our existing ALU. The new mux in Figure 2 selects the ALU input A based on a new control signal, ASel.

• Set ASel to 1 to pass in the program counter value pc.

• Set ASel to 0 to pass in the register value R[rs1].

1.4Immediate Generator Block¶

We must also update the Immediate Generator block, ImmGen. Immediates in B-Type are different from I-Type and S-Type and have an implicit trailing zero. Read more in the Immediate Generator section.

2Tracing the Branch Datapath¶

Let’s walk through the updated datapath for branch instructions (B-Type):

1. Instruction Fetch: At the beginning of the clock cycle, read PC and fetch the current instruction from IMEM.

   Before the next rising clock edge, set up PCSel, and ensure that the input to PC is stable. If PCSel=taken, update PC to the output of the ALU. Else, update to next instruction pc + 4.

2. Instruction Decode: Fetch R[rs1] and R[rs2] from RegFile, build the immediate imm for B-Type instructions. Also configure control logic (see below).

3. Execute: Compute pc + imm using the ALU. Because control signals are ASel=1 and BSel=1, the two muxes before the ALU will select pc and imm, respectively. Because ALUSel=Add, the ALU will add these two values together.

   The branch comparator compares R[rs1] and R[rs2] (doing an unsigned comparison if BrUn=1) and outputs two signals, BrEq and BrLT, to the control logic.

   After some delay, the output of the ALU is stable at the mux controlled by PCSel. Additionally, the control signal PCSel is stable after the control logic uses the BrEq and BrLT signals to determine whether to take the branch (see details below).

4. Memory: (We don’t access DMEM, so skip this.)

5. Write Back: (We don’t write to RegFile, so skip this.)

3Branch Comparator Block¶

The Branch Comparator Block in Figure 3 takes two data inputs and a control input, then outputs the result of comparing the two inputs.

This branch block is used to implement branches on the datapath with logic shown in Figure 4:

The control logic sets two control signals:

1. Sets BrUn based on the current instruction, i.e., sets BrUn=1 if the instruction is bltu or bgeu.

2. Sets PCSel based on branch flags BrLT and BrEq.

In other words, the control logic subcircuit feeds input into the branch comparator and uses output of the branch comparator to compute additional control signals.^[2].

3.1Set PCSel¶

Note that the two output signals BrLT and BrEq are sufficient for determining the results of all branch comparisons:

• beq, bne: Check BrEq and set PCSel accordingly.

• blt (and bltu): If BrLT=1 and BrEq=1, then PCSel=taken.

• bge (and bgeu): If BrLT=0, then PCSel=taken. This is because checking $A \geq B$ is equivalent to checking $A \nless B$.