1 of 101

CS61C: Great Ideas in Computer Architecture (aka Machine Structures)

Lecture 13: RISC-V Datapath

Instructors: Caroline Liu, Justin Yokota, Peyrin Kao

CS 61C

Summer 2022

2 of 101

CS 61C Hardware Roadmap

Processor (CPU)

  • Datapath
  • Control Logic
  • Pipelining

Synchronous Digital Systems

  • Combinatorial Logic
  • Sequential Logic

Transistors

Today, we’re building a circuit that can run every base RISC-V instruction!

CS 61C

Summer 2022

3 of 101

Review: Subcircuits

CS 61C

Summer 2022

4 of 101

Combinatorial Logic: Multiplexer (MUX)

  • Intuitively:
    • If S is 0, output the value in A.
    • If S is 1, output the value in B.
    • S is the “select” bit
  • Usually drawn like this:

Out = (A)(!S) + (B)(S)

S

A

B

Out

0

0

0

0

1

0

0

0

0

0

1

1

1

0

1

1

0

1

0

0

1

1

0

1

0

1

1

0

1

1

1

1

CS 61C

Summer 2022

5 of 101

Combinatorial Logic: Arithmetic Logic Unit (ALU)

  • Inputs:
    • 32-bit input A
    • 32-bit input B
    • 2-bit operation selector S
  • Outputs:
    • 32-bit result R
  • Behavior:
    • If S=0b00, set R=A+B (addition)
    • If S=0b01, set R=A&B (bitwise AND)
    • If S=0b10, set R=A|B (bitwise OR)
    • If S=0b11, set R=A^B (bitwise XOR)

Select

ALU

A

B

R

CS 61C

Summer 2022

6 of 101

Sequential Logic: Registers

  • Inputs:
    • n-bit value D
    • One-bit clock value
    • One-it write-enable
  • Outputs:
    • n-bit value Q
  • Behavior:
    • If WEn=1, then on the rising edge of the clock, set Q=D
    • At all other times, do nothing

D

Q

clk

Input

Output

WEn

WEn

CS 61C

Summer 2022

7 of 101

Sequential Logic: Read-Only Memory

  • Behavior:
    • MemAddress identifies an address in memory.
    • Reading from memory: Set MemReadData to the value at that address.

Inputs

MemAddress

32 bits

Clock

1 bit

Output

MemReadData

32 bits

MEM

MemReadData

MemAddress

CS 61C

Summer 2022

8 of 101

Sequential Logic: Read/Write Memory

  • Behavior:
    • MemAddress identifies an address in memory.
    • Reading from memory: Set MemReadData to the value at that address.
    • Writing to memory: If MemWEn=1, then on the next rising edge of the clock, write the value in MemWriteData at that address.

Inputs

MemAddress

32 bits

MemWriteData

32 bits

MemWEn

1 bit

Clock

1 bit

Output

MemReadData

32 bits

MEM

MemWEn

MemReadData

MemWriteData

MemAddress

CS 61C

Summer 2022

9 of 101

Datapath for add

CS 61C

Summer 2022

10 of 101

List of RISC-V Instructions

Instruction

Name

Type

add

ADD

R

sub

SUBtract

R

and

bitwise AND

R

or

bitwise OR

R

xor

bitwise XOR

R

sll

Shift Left Logical

R

srl

Shift Right Logical

R

sra

Shift Right Arithmetic

R

slt

Set Less Than (signed)

R

sltu

Set Less Than (Unsigned)

R

addi

ADD Immediate

I

andi

bitwise AND Immediate

I

ori

bitwise OR Immediate

I

xori

bitwise XOR Immediate

I

Instruction

Name

Type

slli

Shift Left Logical Immediate

I*

srli

Shift Right Logical Immediate

I*

srai

Shift Right Arithmetic Immediate

I*

slti

Set Less Than Immediate (signed)

I

sltiu

Set Less Than Immediate (Unsigned)

I

lb

Load Byte

I

lbu

Load Byte (Unsigned)

I

lh

Load Half-word

I

lhu

Load Half-word (Unsigned)

I

lw

Load Word

I

Instruction

Name

Type

sb

Store Byte

S

sh

Store Half-word

S

sw

Store Word

S

beq

Branch if EQual

B

bge

Branch if Greater or Equal (signed)

B

bgeu

Branch if Greater or Equal (Unsigned)

B

blt

Branch if Less Than (signed)

B

bltu

Branch if Less Than (Unsigned)

B

bne

Branch if Not Equal

B

jal

Jump And Link

J

jalr

Jump And Link Register

I

auipc

Add Upper Immediate to PC

U

lui

Load Upper Immediate

U

CS 61C

Summer 2022

11 of 101

add instruction

  • What state elements do we need to change?
    • Add the values in registers rs1 and rs2, and store the result in register rd
    • Increment the program counter: PC = PC + 4

31 25 24 20 19 15 14 12 11 7 6 0

R

funct7

rs2

rs1

funct3

rd

opcode

I

imm[11:0]

rs1

funct3

rd

opcode

I*

funct7

imm[4:0]

rs1

funct3

rd

opcode

S

imm[11:5]

rs2

rs1

funct3

imm[4:0]

opcode

B

imm[12|10:5]

rs2

rs1

funct3

imm[4:1|11]

opcode

U

imm[31:12]

rd

opcode

J

imm[20|10:1|11|19:12]

rd

opcode

CS 61C

Summer 2022

12 of 101

Stage 1: Instruction Fetch (IF)

+4

PC+4

PC

Here’s a circuit that adds 4 to PC on each clock cycle.

​

PC+4 is written to the register on the next rising edge.

CS 61C

Summer 2022

13 of 101

Stage 1: Instruction Fetch (IF)

IMEM

PC

inst

+4

PC+4

PC

Let’s find out what instruction is at the address in PC.

​

We can input the address into a memory block, and retrieve a 32-bit instruction.

CS 61C

Summer 2022

14 of 101

Stage 2: Instruction Decode (ID)

inst[11:7]

inst[24:20]

inst[19:15]

IMEM

PC

inst

+4

PC+4

PC

Let’s split up the instruction bits into some useful fields.

​

Now we have the 5-bit values rs1, rs2, and rd.

CS 61C

Summer 2022

15 of 101

Stage 2: Instruction Decode (ID), Register Read

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

IMEM

PC

inst

+4

PC+4

PC

Let’s find out what values are in the rs1 and rs2 registers.

​

We can input the register numbers into the RegFile and retrieve 32-bit values stored in those registers.

CS 61C

Summer 2022

16 of 101

Stage 3: Execute

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

ALU

A

B

RegWEn

IMEM

PC

inst

+4

PC+4

PC

Let’s add the 32-bit values stored in rs1 and rs2 together.

CS 61C

Summer 2022

17 of 101

Stage 4: Memory

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

ALU

A

B

RegWEn

IMEM

PC

inst

+4

PC+4

PC

We don’t need to read from or write to memory, so we can do nothing in this stage.

CS 61C

Summer 2022

18 of 101

Stage 5: Register Write

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

ALU

A

B

RegWEn

IMEM

PC

inst

+4

PC+4

PC

Let’s write the computation result back to register rd.

​

Note that we also set RegWriteIndex to rd.

CS 61C

Summer 2022

19 of 101

Five-Stage Datapath: add

  1. Instruction Fetch (IF)
    • Look up the 32-bit instruction at address PC, using instruction memory IMEM
    • Add 4 to PC for the next cycle
  2. Instruction Decode (ID), Register Read
    • Extract fields from the 32-bit instruction
    • Read data from the registers, using the RegFile
  3. Execute
    • Perform calculation on register data, using the Arithmetic Logic Unit (ALU)
  4. Memory
    • Read or write to memory (not needed for add)
  5. Register Write
    • Write the result of calculation to a register, using the RegFile

CS 61C

Summer 2022

20 of 101

Why Five-Stage Datapath?

  • We broke up the processor circuit into five stages
  • Why is this useful?
    • A single logic block that runs the entire instruction is bulky and inefficient
    • Smaller stages are easier to design
    • Modularity: Easier to change one stage without affecting the other stages

CS 61C

Summer 2022

21 of 101

Datapath for sub

CS 61C

Summer 2022

22 of 101

List of RISC-V Instructions

Instruction

Name

Type

add

ADD

R

sub

SUBtract

R

and

bitwise AND

R

or

bitwise OR

R

xor

bitwise XOR

R

sll

Shift Left Logical

R

srl

Shift Right Logical

R

sra

Shift Right Arithmetic

R

slt

Set Less Than (signed)

R

sltu

Set Less Than (Unsigned)

R

addi

ADD Immediate

I

andi

bitwise AND Immediate

I

ori

bitwise OR Immediate

I

xori

bitwise XOR Immediate

I

Instruction

Name

Type

slli

Shift Left Logical Immediate

I*

srli

Shift Right Logical Immediate

I*

srai

Shift Right Arithmetic Immediate

I*

slti

Set Less Than Immediate (signed)

I

sltiu

Set Less Than Immediate (Unsigned)

I

lb

Load Byte

I

lbu

Load Byte (Unsigned)

I

lh

Load Half-word

I

lhu

Load Half-word (Unsigned)

I

lw

Load Word

I

Instruction

Name

Type

sb

Store Byte

S

sh

Store Half-word

S

sw

Store Word

S

beq

Branch if EQual

B

bge

Branch if Greater or Equal (signed)

B

bgeu

Branch if Greater or Equal (Unsigned)

B

blt

Branch if Less Than (signed)

B

bltu

Branch if Less Than (Unsigned)

B

bne

Branch if Not Equal

B

jal

Jump And Link

J

jalr

Jump And Link Register

I

auipc

Add Upper Immediate to PC

U

lui

Load Upper Immediate

U

CS 61C

Summer 2022

23 of 101

sub instruction

  • What state elements do we need to change?
    • Subtract the values in registers rs1 and rs2, and store the result in register rd
    • Increment the program counter: PC = PC + 4

31 25 24 20 19 15 14 12 11 7 6 0

R

funct7

rs2

rs1

funct3

rd

opcode

I

imm[11:0]

rs1

funct3

rd

opcode

I*

funct7

imm[4:0]

rs1

funct3

rd

opcode

S

imm[11:5]

rs2

rs1

funct3

imm[4:0]

opcode

B

imm[12|10:5]

rs2

rs1

funct3

imm[4:1|11]

opcode

U

imm[31:12]

rd

opcode

J

imm[20|10:1|11|19:12]

rd

opcode

CS 61C

Summer 2022

24 of 101

Stage 1: Instruction Fetch (IF)

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

ALU

A

B

RegWEn

IMEM

PC

inst

+4

PC+4

PC

Same as the add instruction. Compute PC+4 for the next instruction.

CS 61C

Summer 2022

25 of 101

Stage 1: Instruction Fetch (IF)

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

ALU

A

B

RegWEn

IMEM

PC

inst

+4

PC+4

PC

Same as the add instruction. Fetch the 32-bit instruction from IMEM.

CS 61C

Summer 2022

26 of 101

Stage 2: Instruction Decode (ID)

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

ALU

A

B

RegWEn

IMEM

PC

inst

+4

PC+4

PC

Same as the add instruction. Extract fields from the 32-bit instruction.

CS 61C

Summer 2022

27 of 101

Stage 2: Instruction Decode (ID), Register Read

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

ALU

A

B

RegWEn

IMEM

PC

inst

+4

PC+4

PC

Same as the add instruction. Read data from registers.

CS 61C

Summer 2022

28 of 101

Stage 3: Execute

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

ALU

A

B

RegWEn

IMEM

PC

inst

+4

PC+4

PC

Different from the add instruction! We want to compute A–B, not A+B.

CS 61C

Summer 2022

29 of 101

Stage 3: Execute

Let’s add an input to select different ALU operations.�

How do we know which operation to select?

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

ALU

A

B

RegWEn

IMEM

PC

inst

+4

PC+4

PC

ALUSel

CS 61C

Summer 2022

30 of 101

Stage 3: Execute

Add a circuit that takes the instruction, checks its opcode/funct3/funct7, and outputs the correct ALUSel value.

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

ALU

A

B

RegWEn

IMEM

PC

inst

+4

PC+4

PC

ALUSel

inst[31:0]

CS 61C

Summer 2022

31 of 101

Stage 4: Memory

Same as the add instruction. Do nothing.

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

ALU

A

B

RegWEn

IMEM

PC

inst

+4

PC+4

PC

ALUSel

inst[31:0]

CS 61C

Summer 2022

32 of 101

Stage 5: Register Write

Same as the add instruction. Write the calculation result to a register.

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

ALU

A

B

RegWEn

IMEM

PC

inst

+4

PC+4

PC

ALUSel

inst[31:0]

CS 61C

Summer 2022

33 of 101

New Subcircuit: Control Logic

  • New subcircuit in our datapath: control logic
  • Input: 32-bit instruction
  • Output: Values that change how the datapath behaves
    • Example: ALUSel: What operation should the ALU perform?
    • Example: RegWEn: Should we write a value to the RegFile?
    • More control logic outputs as we see more instructions

ALUSel

inst[31:0]

CS 61C

Summer 2022

34 of 101

Datapath for All R-type Instructions

CS 61C

Summer 2022

35 of 101

List of RISC-V Instructions

Instruction

Name

Type

add

ADD

R

sub

SUBtract

R

and

bitwise AND

R

or

bitwise OR

R

xor

bitwise XOR

R

sll

Shift Left Logical

R

srl

Shift Right Logical

R

sra

Shift Right Arithmetic

R

slt

Set Less Than (signed)

R

sltu

Set Less Than (Unsigned)

R

addi

ADD Immediate

I

andi

bitwise AND Immediate

I

ori

bitwise OR Immediate

I

xori

bitwise XOR Immediate

I

Instruction

Name

Type

slli

Shift Left Logical Immediate

I*

srli

Shift Right Logical Immediate

I*

srai

Shift Right Arithmetic Immediate

I*

slti

Set Less Than Immediate (signed)

I

sltiu

Set Less Than Immediate (Unsigned)

I

lb

Load Byte

I

lbu

Load Byte (Unsigned)

I

lh

Load Half-word

I

lhu

Load Half-word (Unsigned)

I

lw

Load Word

I

Instruction

Name

Type

sb

Store Byte

S

sh

Store Half-word

S

sw

Store Word

S

beq

Branch if EQual

B

bge

Branch if Greater or Equal (signed)

B

bgeu

Branch if Greater or Equal (Unsigned)

B

blt

Branch if Less Than (signed)

B

bltu

Branch if Less Than (Unsigned)

B

bne

Branch if Not Equal

B

jal

Jump And Link

J

jalr

Jump And Link Register

I

auipc

Add Upper Immediate to PC

U

lui

Load Upper Immediate

U

CS 61C

Summer 2022

36 of 101

R-Type Instruction Datapath

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

ALU

A

B

RegWEn

IMEM

PC

inst

+4

PC+4

PC

We can run every R-type instruction with this circuit! We just have to set ALUSel depending on the instruction.

ALUSel

inst[31:0]

CS 61C

Summer 2022

37 of 101

Datapath for addi

CS 61C

Summer 2022

38 of 101

List of RISC-V Instructions

Instruction

Name

Type

add

ADD

R

sub

SUBtract

R

and

bitwise AND

R

or

bitwise OR

R

xor

bitwise XOR

R

sll

Shift Left Logical

R

srl

Shift Right Logical

R

sra

Shift Right Arithmetic

R

slt

Set Less Than (signed)

R

sltu

Set Less Than (Unsigned)

R

addi

ADD Immediate

I

andi

bitwise AND Immediate

I

ori

bitwise OR Immediate

I

xori

bitwise XOR Immediate

I

Instruction

Name

Type

slli

Shift Left Logical Immediate

I*

srli

Shift Right Logical Immediate

I*

srai

Shift Right Arithmetic Immediate

I*

slti

Set Less Than Immediate (signed)

I

sltiu

Set Less Than Immediate (Unsigned)

I

lb

Load Byte

I

lbu

Load Byte (Unsigned)

I

lh

Load Half-word

I

lhu

Load Half-word (Unsigned)

I

lw

Load Word

I

Instruction

Name

Type

sb

Store Byte

S

sh

Store Half-word

S

sw

Store Word

S

beq

Branch if EQual

B

bge

Branch if Greater or Equal (signed)

B

bgeu

Branch if Greater or Equal (Unsigned)

B

blt

Branch if Less Than (signed)

B

bltu

Branch if Less Than (Unsigned)

B

bne

Branch if Not Equal

B

jal

Jump And Link

J

jalr

Jump And Link Register

I

auipc

Add Upper Immediate to PC

U

lui

Load Upper Immediate

U

CS 61C

Summer 2022

39 of 101

addi instruction

  • What state elements do we need to change?
    • Add the value in register rs1 to the immediate in the instruction, and store the result in register rd
    • Increment the program counter: PC = PC + 4

31 25 24 20 19 15 14 12 11 7 6 0

R

funct7

rs2

rs1

funct3

rd

opcode

I

imm[11:0]

rs1

funct3

rd

opcode

I*

funct7

imm[4:0]

rs1

funct3

rd

opcode

S

imm[11:5]

rs2

rs1

funct3

imm[4:0]

opcode

B

imm[12|10:5]

rs2

rs1

funct3

imm[4:1|11]

opcode

U

imm[31:12]

rd

opcode

J

imm[20|10:1|11|19:12]

rd

opcode

CS 61C

Summer 2022

40 of 101

Stage 1: Instruction Fetch (IF)

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

ALU

A

B

RegWEn

+4

PC+4

PC

Same as R-type. Compute PC+4 and fetch instruction from IMEM.

ALUSel

inst[31:0]

PC

inst

IMEM

CS 61C

Summer 2022

41 of 101

Stage 2: Instruction Decode (ID)

ALUSel

inst[31:0]

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

ALU

A

B

RegWEn

IMEM

PC

inst

+4

PC+4

PC

Same as the add instruction. Extract fields from the 32-bit instruction.

​

inst[24:20] don’t correspond to rs2 anymore. Does it matter?

CS 61C

Summer 2022

42 of 101

Stage 2: Instruction Decode (ID), Register Read

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

ALU

A

B

RegWEn

IMEM

PC

inst

+4

PC+4

PC

RegReadData1 has the value in register rs1.

​

RegReadData2 has garbage! rs2 doesn’t exist in addi.

ALUSel

inst[31:0]

CS 61C

Summer 2022

43 of 101

Stage 3: Execute

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

ALU

A

B

RegWEn

IMEM

PC

inst

+4

PC+4

PC

ALUSel

inst[31:0]

We want to feed the immediate, not RegReadData2, into the B input of the ALU. Where is the immediate?

CS 61C

Summer 2022

44 of 101

Stage 3: Execute

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

IMEM

PC

inst

+4

PC+4

PC

ALUSel

inst[31:0]

The immediate is in the instruction!

​

How do we extract the immediate from the instruction?

ALU

A

B

CS 61C

Summer 2022

45 of 101

Stage 3: Execute

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

IMEM

PC

inst

+4

PC+4

PC

ALUSel

inst[31:0]

Add an immediate generator subcircuit!

​

We don’t want to break the R-type datapath. How do we support both B inputs?

ALU

A

B

Imm Gen

CS 61C

Summer 2022

46 of 101

Stage 3: Execute

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

IMEM

PC

inst

+4

PC+4

PC

ALUSel

inst[31:0]

Add a mux to select between the immediate and register value!

​

How do we know which value to select?

ALU

A

B

0

1

Imm Gen

CS 61C

Summer 2022

47 of 101

Stage 3: Execute

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

IMEM

PC

inst

+4

PC+4

PC

ALUSel

inst[31:0]

Ask the control logic subcircuit to figure out which B input to select!

ALU

A

B

0

1

BSel

Imm Gen

CS 61C

Summer 2022

48 of 101

Stage 4: Memory

BSel

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

IMEM

PC

inst

+4

PC+4

PC

ALUSel

inst[31:0]

addi doesn’t write to memory, so do nothing.

ALU

A

B

Imm Gen

0

1

CS 61C

Summer 2022

49 of 101

Stage 5: Register Write

BSel

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

IMEM

PC

inst

+4

PC+4

PC

ALUSel

inst[31:0]

Same as R-type. Write the result of the computation back to a register.

ALU

A

B

Imm Gen

0

1

CS 61C

Summer 2022

50 of 101

New Subcircuit: Immediate Generator

  • New subcircuit in our datapath: immediate generator
  • Input: 32-bit instruction
    • There’s another input, ImmSel, which we’ll see later
  • Output: 32-bit immediate value
    • Extract the immediate bits from the instruction
    • Extend the immediate to 32 bits (usually sign-extend)

CS 61C

Summer 2022

51 of 101

New Control Signal: BSel

  • Chooses which value to send to the B input of the ALU
    • BSel=0: Send data in register rs2 to ALU
    • BSel=1: Send immediate to ALU
  • Control logic subcircuit decodes instruction and outputs appropriate BSel
    • Example: For R-type instructions, set BSel=0
    • Example: For I-type instructions, set BSel=1

BSel

0

1

RegReadData2

Immediate

B (ALU input)

CS 61C

Summer 2022

52 of 101

Datapath for I-type Instructions

CS 61C

Summer 2022

53 of 101

List of RISC-V Instructions

Instruction

Name

Type

add

ADD

R

sub

SUBtract

R

and

bitwise AND

R

or

bitwise OR

R

xor

bitwise XOR

R

sll

Shift Left Logical

R

srl

Shift Right Logical

R

sra

Shift Right Arithmetic

R

slt

Set Less Than (signed)

R

sltu

Set Less Than (Unsigned)

R

addi

ADD Immediate

I

andi

bitwise AND Immediate

I

ori

bitwise OR Immediate

I

xori

bitwise XOR Immediate

I

Instruction

Name

Type

slli

Shift Left Logical Immediate

I*

srli

Shift Right Logical Immediate

I*

srai

Shift Right Arithmetic Immediate

I*

slti

Set Less Than Immediate (signed)

I

sltiu

Set Less Than Immediate (Unsigned)

I

lb

Load Byte

I

lbu

Load Byte (Unsigned)

I

lh

Load Half-word

I

lhu

Load Half-word (Unsigned)

I

lw

Load Word

I

Instruction

Name

Type

sb

Store Byte

S

sh

Store Half-word

S

sw

Store Word

S

beq

Branch if EQual

B

bge

Branch if Greater or Equal (signed)

B

bgeu

Branch if Greater or Equal (Unsigned)

B

blt

Branch if Less Than (signed)

B

bltu

Branch if Less Than (Unsigned)

B

bne

Branch if Not Equal

B

jal

Jump And Link

J

jalr

Jump And Link Register

I

auipc

Add Upper Immediate to PC

U

lui

Load Upper Immediate

U

CS 61C

Summer 2022

54 of 101

R-Type and I-Type Instruction Datapath

BSel

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

IMEM

PC

inst

+4

PC+4

PC

ALUSel

inst[31:0]

ALU

A

B

Imm Gen

0

1

We can run every non-load I-type instruction with this circuit! We just have to set ALUSel depending on the instruction.

CS 61C

Summer 2022

55 of 101

Datapath for Loads

CS 61C

Summer 2022

56 of 101

List of RISC-V Instructions

Instruction

Name

Type

add

ADD

R

sub

SUBtract

R

and

bitwise AND

R

or

bitwise OR

R

xor

bitwise XOR

R

sll

Shift Left Logical

R

srl

Shift Right Logical

R

sra

Shift Right Arithmetic

R

slt

Set Less Than (signed)

R

sltu

Set Less Than (Unsigned)

R

addi

ADD Immediate

I

andi

bitwise AND Immediate

I

ori

bitwise OR Immediate

I

xori

bitwise XOR Immediate

I

Instruction

Name

Type

slli

Shift Left Logical Immediate

I*

srli

Shift Right Logical Immediate

I*

srai

Shift Right Arithmetic Immediate

I*

slti

Set Less Than Immediate (signed)

I

sltiu

Set Less Than Immediate (Unsigned)

I

lb

Load Byte

I

lbu

Load Byte (Unsigned)

I

lh

Load Half-word

I

lhu

Load Half-word (Unsigned)

I

lw

Load Word

I

Instruction

Name

Type

sb

Store Byte

S

sh

Store Half-word

S

sw

Store Word

S

beq

Branch if EQual

B

bge

Branch if Greater or Equal (signed)

B

bgeu

Branch if Greater or Equal (Unsigned)

B

blt

Branch if Less Than (signed)

B

bltu

Branch if Less Than (Unsigned)

B

bne

Branch if Not Equal

B

jal

Jump And Link

J

jalr

Jump And Link Register

I

auipc

Add Upper Immediate to PC

U

lui

Load Upper Immediate

U

CS 61C

Summer 2022

57 of 101

Load instructions

  • What state elements do we need to change?
    • Add the value in register rs1 to the immediate in the instruction (just like non-load I-types)
    • The result of the addition is the memory address to load from
    • Load data from this memory address, and write the data to a register
    • Increment the program counter: PC = PC + 4

31 25 24 20 19 15 14 12 11 7 6 0

R

funct7

rs2

rs1

funct3

rd

opcode

I

imm[11:0]

rs1

funct3

rd

opcode

I*

funct7

imm[4:0]

rs1

funct3

rd

opcode

S

imm[11:5]

rs2

rs1

funct3

imm[4:0]

opcode

B

imm[12|10:5]

rs2

rs1

funct3

imm[4:1|11]

opcode

U

imm[31:12]

rd

opcode

J

imm[20|10:1|11|19:12]

rd

opcode

CS 61C

Summer 2022

58 of 101

Load Stage 1: Instruction Fetch (IF)

BSel

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

ALUSel

inst[31:0]

ALU

A

B

Imm Gen

0

1

+4

PC+4

PC

PC

inst

Same as non-load I-types. Compute PC+4 and fetch instruction from IMEM.

IMEM

CS 61C

Summer 2022

59 of 101

Load Stage 2: Instruction Decode (ID), Register Read

BSel

ALUSel

inst[31:0]

ALU

A

B

Imm Gen

0

1

Same as non-load I-types. Read value of rs1 from register.

IMEM

PC

inst

+4

PC+4

PC

inst[11:7]

inst[24:20]

inst[19:15]

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

RegReadData2

RegWEn

CS 61C

Summer 2022

60 of 101

Load Stage 3: Execute

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

IMEM

PC

inst

+4

PC+4

PC

ALUSel

inst[31:0]

What do we need to compute?

​

Immediate + value in rs1 = memory address to load from

0

1

BSel

Imm Gen

ALU

A

B

CS 61C

Summer 2022

61 of 101

Load Stage 3: Execute

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

IMEM

PC

inst

+4

PC+4

PC

ALUSel

inst[31:0]

BSel=1 to select the immediate, not rs2.

​

ALUSel set to make ALU perform addition.

0

1

BSel

Imm Gen

ALU

A

B

CS 61C

Summer 2022

62 of 101

Load Stage 4: Memory

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

IMEM

PC

inst

+4

PC+4

PC

ALUSel

inst[31:0]

Not adding anything here; just making space for the memory unit.

BSel

ALU

A

B

Imm Gen

0

1

CS 61C

Summer 2022

63 of 101

Load Stage 4: Memory

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

IMEM

PC

inst

+4

PC+4

PC

inst[31:0]

BSel

ALUSel

ALU

A

B

Imm Gen

0

1

Same as the previous slide, but the ALU output to RegWriteData arrow moved.

CS 61C

Summer 2022

64 of 101

Load Stage 4: Memory

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

IMEM

PC

inst

+4

PC+4

PC

inst[31:0]

BSel

ALUSel

ALU

A

B

Imm Gen

0

1

DMEM

MemWEn

MemReadData

MemWriteData

MemAddress

Here’s a memory block. What’s the address we want to load from?

CS 61C

Summer 2022

65 of 101

Load Stage 4: Memory

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

IMEM

PC

inst

+4

PC+4

PC

inst[31:0]

BSel

ALUSel

ALU

A

B

Imm Gen

0

1

DMEM

MemWEn

MemReadData

MemWriteData

MemAddress

We computed the address with the ALU!

Where does the data we read go?

CS 61C

Summer 2022

66 of 101

Load Stage 5: Register Write

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

IMEM

PC

inst

+4

PC+4

PC

inst[31:0]

BSel

ALUSel

ALU

A

B

Imm Gen

0

1

DMEM

MemWEn

MemReadData

MemWriteData

MemAddress

We want to write the data from memory to a register. How do we support writing both data from memory and ALU output to a register?

CS 61C

Summer 2022

67 of 101

Load Stage 5: Register Write

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

IMEM

PC

inst

+4

PC+4

PC

inst[31:0]

BSel

ALUSel

ALU

A

B

Imm Gen

0

1

DMEM

MemWEn

MemReadData

MemWriteData

MemAddress

Add a mux to choose which value to write back to the register!

How do we know which value to write back?

0

1

CS 61C

Summer 2022

68 of 101

Load Stage 5: Register Write

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

IMEM

PC

inst

+4

PC+4

PC

inst[31:0]

BSel

ALUSel

ALU

A

B

Imm Gen

0

1

DMEM

MemWEn

MemReadData

MemWriteData

MemAddress

Add a new control signal: WBSel (write-back select)

WBSel

0

1

CS 61C

Summer 2022

69 of 101

New Control Signal: WBSel

  • Write-back select
  • Chooses which value to write back to the register
    • WBSel=0: Write the data read from memory (MemReadData) to the register
    • WBSel=1: Write the ALU output to the register
    • There’s another WBSel value, which we’ll see later
  • Control logic subcircuit decodes instruction and outputs appropriate WBSel
    • Example: For load instructions, set WBSel=0
    • Example: For R-type and non-load I-type instructions, set WBSel=1

WBSel

1

0

ALU Output

MemReadData

RegWriteData

CS 61C

Summer 2022

70 of 101

Partial Loads

  • Different types of loads:
    • lw (load word): Read 4 bytes from memory
    • lh (load half-word): Read 2 bytes from memory, sign-extend to 4 bytes
    • lhu (load half-word unsigned): Read 2 bytes from memory, zero-extend to 4 bytes
    • lb (load byte): Read 1 byte from memory, sign-extend to 4 bytes
    • lbu (load byte unsigned): Read 1 byte from memory, sign-extend to 4 bytes
  • Some additional circuitry needed to extract the correct bytes from memory
    • You’ll implement a partial load subcircuit in Project 3B!

CS 61C

Summer 2022

71 of 101

Datapath for Stores

CS 61C

Summer 2022

72 of 101

List of RISC-V Instructions

Instruction

Name

Type

add

ADD

R

sub

SUBtract

R

and

bitwise AND

R

or

bitwise OR

R

xor

bitwise XOR

R

sll

Shift Left Logical

R

srl

Shift Right Logical

R

sra

Shift Right Arithmetic

R

slt

Set Less Than (signed)

R

sltu

Set Less Than (Unsigned)

R

addi

ADD Immediate

I

andi

bitwise AND Immediate

I

ori

bitwise OR Immediate

I

xori

bitwise XOR Immediate

I

Instruction

Name

Type

slli

Shift Left Logical Immediate

I*

srli

Shift Right Logical Immediate

I*

srai

Shift Right Arithmetic Immediate

I*

slti

Set Less Than Immediate (signed)

I

sltiu

Set Less Than Immediate (Unsigned)

I

lb

Load Byte

I

lbu

Load Byte (Unsigned)

I

lh

Load Half-word

I

lhu

Load Half-word (Unsigned)

I

lw

Load Word

I

Instruction

Name

Type

sb

Store Byte

S

sh

Store Half-word

S

sw

Store Word

S

beq

Branch if EQual

B

bge

Branch if Greater or Equal (signed)

B

bgeu

Branch if Greater or Equal (Unsigned)

B

blt

Branch if Less Than (signed)

B

bltu

Branch if Less Than (Unsigned)

B

bne

Branch if Not Equal

B

jal

Jump And Link

J

jalr

Jump And Link Register

I

auipc

Add Upper Immediate to PC

U

lui

Load Upper Immediate

U

CS 61C

Summer 2022

73 of 101

Store instructions

  • What state elements do we need to change?
    • Add the value in register rs1 to the immediate in the instruction (just like I-types)
    • The result of the addition is the memory address to store to
    • Store the value in register rs2 to this memory address
    • Increment the program counter: PC = PC + 4

CS 61C

Summer 2022

74 of 101

Store Stage 1: Instruction Fetch (IF)

inst[31:0]

BSel

ALUSel

ALU

A

B

Imm Gen

0

1

DMEM

MemWEn

MemReadData

MemWriteData

MemAddress

As before, we read the instruction from IMEM.

WBSel

0

1

+4

PC+4

PC

PC

inst

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

IMEM

CS 61C

Summer 2022

75 of 101

Store Stage 2: Instruction Decode (ID)

inst[31:0]

BSel

ALUSel

ALU

A

B

Imm Gen

0

1

DMEM

MemWEn

MemReadData

MemWriteData

MemAddress

Note that we have to read values from both rs1 and rs2!

WBSel

0

1

inst[11:7]

inst[24:20]

inst[19:15]

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

RegReadData2

RegWEn

IMEM

PC

inst

+4

PC+4

PC

CS 61C

Summer 2022

76 of 101

Store Stage 3: Execute

inst[31:0]

BSel

ALUSel

ALU

A

B

Imm Gen

0

1

DMEM

MemWEn

MemReadData

MemWriteData

MemAddress

What are we computing?�Address = value in rs1 + immediate

WBSel

0

1

IMEM

PC

inst

+4

PC+4

PC

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

CS 61C

Summer 2022

77 of 101

Store Stage 3: Execute

inst[31:0]

BSel

ALUSel

ALU

A

B

Imm Gen

0

1

DMEM

MemWEn

MemReadData

MemWriteData

MemAddress

Problem: I-type immediates are in inst[31:20]. S-type immediates are in inst[31:25, 11:7]. How to support both?

WBSel

0

1

IMEM

PC

inst

+4

PC+4

PC

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

CS 61C

Summer 2022

78 of 101

Store Stage 3: Execute

inst[31:0]

BSel

ALUSel

ALU

A

B

Imm Gen

0

1

DMEM

MemWEn

MemReadData

MemWriteData

MemAddress

Add a new control signal, ImmSel (immediate select). Update immediate generator to support I-types and S-types.

WBSel

0

1

IMEM

PC

inst

+4

PC+4

PC

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

ImmSel

CS 61C

Summer 2022

79 of 101

Store Stage 4: Memory

inst[31:0]

BSel

ALUSel

ALU

A

B

Imm Gen

0

1

What are we writing to memory? The value in register rs2!

WBSel

0

1

IMEM

PC

inst

+4

PC+4

PC

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

ImmSel

DMEM

MemWEn

MemReadData

MemWriteData

MemAddress

CS 61C

Summer 2022

80 of 101

Store Stage 4: Memory

inst[31:0]

BSel

ALUSel

ALU

A

B

Imm Gen

0

1

How do we tell when we want to write to memory? Add a MemWEn (memory write-enable) control signal!

WBSel

0

1

IMEM

PC

inst

+4

PC+4

PC

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

ImmSel

DMEM

MemWEn

MemReadData

MemWriteData

MemAddress

MemRW

CS 61C

Summer 2022

81 of 101

Store Stage 5: Register Write

inst[31:0]

BSel

ALUSel

ALU

A

B

Imm Gen

0

1

DMEM

MemWEn

MemReadData

MemWriteData

MemAddress

What are we writing back to the register? Nothing! Store instructions don’t modify register values.

WBSel

0

1

IMEM

PC

inst

+4

PC+4

PC

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

ImmSel

MemRW

CS 61C

Summer 2022

82 of 101

Store Stage 5: Register Write

inst[31:0]

BSel

ALUSel

ALU

A

B

Imm Gen

0

1

DMEM

MemWEn

MemReadData

MemWriteData

MemAddress

How do we tell we don’t want to write to a register? Add a RegWEn (register write-enable) control signal!

WBSel

0

1

IMEM

PC

inst

+4

PC+4

PC

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

ImmSel

MemRW

RegWEn

CS 61C

Summer 2022

83 of 101

New Control Signal: ImmSel

  • Immediate select
  • Choose which bits of the instruction to use for the immediate
    • One ImmSel value for each instruction type
  • Only used by the immediate generator

CS 61C

Summer 2022

84 of 101

New Control Signals: MemWEn, RegWEn

  • Memory write-enable, register write-enable
  • Chooses whether to modify memory/registers for this instruction
    • MemWEn=0: Do not modify memory
    • MemWEn=1: Write data to memory
    • RegWEn=0: Do not modify registers
    • RegWEn=1: Write value to register
  • Control logic subcircuit decodes instruction and outputs appropriate WEn
    • Example: For store instructions, MemWEn=1 and RegWEn=0
    • Example: For R-type instructions, MemWEn=0 and RegWEn=1

CS 61C

Summer 2022

85 of 101

Partial Stores

  • Different types of stores:
    • sw (store word): Write 4 bytes to memory
    • sh (store half-word): Write lowest 2 bytes to memory
    • sb (store byte): Write lowest byte to memory
  • Some additional circuitry needed to send the correct bytes to memory
    • You’ll implement a partial store subcircuit in Project 3B!

CS 61C

Summer 2022

86 of 101

Datapath for Branches

CS 61C

Summer 2022

87 of 101

List of RISC-V Instructions

Instruction

Name

Type

add

ADD

R

sub

SUBtract

R

and

bitwise AND

R

or

bitwise OR

R

xor

bitwise XOR

R

sll

Shift Left Logical

R

srl

Shift Right Logical

R

sra

Shift Right Arithmetic

R

slt

Set Less Than (signed)

R

sltu

Set Less Than (Unsigned)

R

addi

ADD Immediate

I

andi

bitwise AND Immediate

I

ori

bitwise OR Immediate

I

xori

bitwise XOR Immediate

I

Instruction

Name

Type

slli

Shift Left Logical Immediate

I*

srli

Shift Right Logical Immediate

I*

srai

Shift Right Arithmetic Immediate

I*

slti

Set Less Than Immediate (signed)

I

sltiu

Set Less Than Immediate (Unsigned)

I

lb

Load Byte

I

lbu

Load Byte (Unsigned)

I

lh

Load Half-word

I

lhu

Load Half-word (Unsigned)

I

lw

Load Word

I

Instruction

Name

Type

sb

Store Byte

S

sh

Store Half-word

S

sw

Store Word

S

beq

Branch if EQual

B

bge

Branch if Greater or Equal (signed)

B

bgeu

Branch if Greater or Equal (Unsigned)

B

blt

Branch if Less Than (signed)

B

bltu

Branch if Less Than (Unsigned)

B

bne

Branch if Not Equal

B

jal

Jump And Link

J

jalr

Jump And Link Register

I

auipc

Add Upper Immediate to PC

U

lui

Load Upper Immediate

U

CS 61C

Summer 2022

88 of 101

Branch instructions

  • What state elements do we need to change?
    • Read the values in registers rs1 and rs2
    • If the comparison is true: set PC = PC + immediate
    • If the comparison is false: set PC = PC + 4

31 25 24 20 19 15 14 12 11 7 6 0

R

funct7

rs2

rs1

funct3

rd

opcode

I

imm[11:0]

rs1

funct3

rd

opcode

I*

funct7

imm[4:0]

rs1

funct3

rd

opcode

S

imm[11:5]

rs2

rs1

funct3

imm[4:0]

opcode

B

imm[12|10:5]

rs2

rs1

funct3

imm[4:1|11]

opcode

U

imm[31:12]

rd

opcode

J

imm[20|10:1|11|19:12]

rd

opcode

CS 61C

Summer 2022

89 of 101

Branch Stage 1: Instruction Fetch (IF)

inst[31:0]

BSel

ALUSel

ALU

A

B

Imm Gen

0

1

DMEM

MemWEn

MemReadData

MemWriteData

MemAddress

As before, we read the instruction from IMEM. We’ll modify the PC logic later, in the write-back stage.

WBSel

0

1

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

ImmSel

MemRW

RegWEn

+4

PC+4

PC

PC

inst

IMEM

CS 61C

Summer 2022

90 of 101

Branch Stage 2: Instruction Decode (ID)

inst[31:0]

BSel

ALUSel

ALU

A

B

Imm Gen

0

1

DMEM

MemWEn

MemReadData

MemWriteData

MemAddress

WBSel

0

1

ImmSel

MemRW

RegWEn

IMEM

PC

inst

+4

PC+4

PC

inst[11:7]

inst[24:20]

inst[19:15]

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

RegReadData2

RegWEn

Note that we have to read values from both rs1 and rs2!

CS 61C

Summer 2022

91 of 101

Branch Stage 3: Execute

inst[31:0]

DMEM

MemWEn

MemReadData

MemWriteData

MemAddress

WBSel

0

1

MemRW

RegWEn

IMEM

PC

inst

+4

PC+4

PC

Note that we have a new type (B-type), so we need to update the immediate generator and ImmSel.

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

BSel

ALUSel

ALU

A

B

Imm Gen

0

1

ImmSel

CS 61C

Summer 2022

92 of 101

Branch Stage 3: Execute

inst[31:0]

DMEM

MemWEn

MemReadData

MemWriteData

MemAddress

WBSel

0

1

MemRW

RegWEn

IMEM

PC

inst

+4

PC+4

PC

If the branch is taken, we have to compute PC + immediate. How do we send PC to the ALU?

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

BSel

ALUSel

ALU

A

B

Imm Gen

0

1

ImmSel

CS 61C

Summer 2022

93 of 101

Branch Stage 3: Execute

inst[31:0]

DMEM

MemWEn

MemReadData

MemWriteData

MemAddress

WBSel

0

1

MemRW

RegWEn

IMEM

PC

inst

+4

PC+4

PC

Add a new mux and control signal (ASel) so we don’t break any existing instructions.

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

BSel

ALUSel

ImmSel

ASel

1

0

Imm Gen

0

1

ALU

A

B

CS 61C

Summer 2022

94 of 101

Branch Stage 3: Execute

inst[31:0]

DMEM

MemWEn

MemReadData

MemWriteData

MemAddress

WBSel

0

1

MemRW

RegWEn

IMEM

PC

inst

+4

PC+4

PC

We’ve computed PC + immediate, but we didn’t compare the register values, and we ran out of hardware! Let’s add some more.

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

BSel

ALUSel

ALU

A

B

Imm Gen

0

1

ImmSel

ASel

1

0

CS 61C

Summer 2022

95 of 101

Branch Stage 3: Execute

inst[31:0]

DMEM

MemWEn

MemReadData

MemWriteData

MemAddress

WBSel

0

1

MemRW

RegWEn

IMEM

PC

inst

+4

PC+4

PC

The branch comparator takes in register values, and sends the comparison result to the control logic subcircuit.

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

BSel

ASel

Imm Gen

ImmSel

ALUSel

ALU

A

B

1

0

0

1

Branch Comp

BrEq

BrLT

BrUn

CS 61C

Summer 2022

96 of 101

Branch Stage 4: Memory

inst[31:0]

DMEM

MemWEn

MemReadData

MemWriteData

MemAddress

WBSel

0

1

MemRW

RegWEn

IMEM

PC

inst

+4

PC+4

PC

Branch instructions don’t write to memory, so nothing to do here. Don’t forget to set MemWEn=0 to disable writing to memory.

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

BSel

ASel

Imm Gen

ImmSel

ALUSel

ALU

A

B

1

0

0

1

Branch Comp

BrEq

BrLT

BrUn

CS 61C

Summer 2022

97 of 101

Branch Stage 5: Register Write

inst[31:0]

DMEM

MemWEn

MemReadData

MemWriteData

MemAddress

WBSel

0

1

MemRW

RegWEn

IMEM

PC

inst

+4

PC+4

PC

Branch instructions don’t write to registers in the RegFile, but they might write PC = PC + immediate.

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

BSel

ASel

Imm Gen

ImmSel

ALUSel

ALU

A

B

1

0

0

1

Branch Comp

BrEq

BrLT

BrUn

CS 61C

Summer 2022

98 of 101

Branch Stage 5: Register Write

inst[31:0]

DMEM

MemWEn

MemReadData

MemWriteData

MemAddress

WBSel

0

1

MemRW

RegWEn

IMEM

PC

inst

+4

PC

Add a mux and control signal (PCSel) to write either PC+4 or PC+imm (ALU output) back to PC.

RegFile

RegWriteData

RegWriteIndex

RegReadIndex1

RegReadIndex2

RegReadData1

inst[11:7]

RegReadData2

inst[24:20]

inst[19:15]

RegWEn

BSel

ASel

Imm Gen

ImmSel

ALUSel

ALU

A

B

1

0

0

1

Branch Comp

BrEq

BrLT

BrUn

PCSel

0

1

PC+4

ALU

CS 61C

Summer 2022

99 of 101

New Control Signal: ASel

  • Chooses which value to send to the A input of the ALU
    • ASel=0: Send data in register rs1 to ALU
    • ASel=1: Send PC to ALU
  • Control logic subcircuit decodes instruction and outputs appropriate ASel
    • Example: For R-type instructions, set ASel=0
    • Example: For B-type instructions, set ASel=1

ASel

1

0

PC

RegReadData1

A (ALU input)

CS 61C

Summer 2022

100 of 101

New Subcircuit: Branch Comparator

  • New subcircuit in our datapath: branch comparator
  • Inputs
    • RegReadData1 and RegReadData2: Register values
    • BrUn: New control signal. Is the branch instruction doing a signed or unsigned comparison?
  • Outputs
    • BrEq: Is RegReadData1 == RegReadData2?
    • BrLt: Is RegReadData1 < ReadReadData2?
    • BrLt performs a signed or unsigned comparison depending on the input BrUn

Branch Comp

BrEq

BrLT

BrUn

RegReadData1

RegReadData2

CS 61C

Summer 2022

101 of 101

New Control Signal: PCSel

  • Chooses how to update PC on the next cycle
    • PCSel=0: Set the next PC = current PC + 4
    • PCSel=1: Set the next PC = current PC + immediate (ALU output)
  • Control logic subcircuit uses instruction and branch comparator output to compute PCSel
    • Example: blt instruction, and BrLt=1. The branch is taken, so PCSel=1.
    • Example: beq instruction, and BrEq=0. The branch is not taken, so PCSel=0.
    • Example: addi instruction. There’s no branch to take, so PCSel=0.

PCSel

0

1

PC+4

ALU Output

PC (register)

CS 61C

Summer 2022