Skip to content

CS 21 25.2 Laboratory Exercise 6

Multicycle Processor

Overview

You will be using Logisim to modify an existing multicycle RISC-V processor implementation to support other kinds of instructions.

General Instructions

For this laboratory activity, you are to work on one HOPELEx Checkpoint Item that will aid in your understanding of the RISC-V multicycle processor.

Important Reminder

You must finish and show your working checkpoint tasks to your lab handler before the end of the laboratory period. HOPELEx checkpoint items contribute 1% to your lab grade.

At the end of the HOPELEx Checkpoints are take-home exercises called TakeHOPE items. These are not graded and will not be submitted, but will help you prepare for the HOPE.

Tip: Quick conversion shell script

Supposing the output of the Ripes assembly is in assembly.txt, the following command automatically transforms the said output into its Logisim-ready form in logisim.txt:

printf "v3.0 hex words\n%s" "$(cat assembly.txt | grep "^\s" | tr -s " " | cut -d " " -f 3)" > logisim.txt

Guided Walkthrough

Overview

A Logisim-Evolution template for a RISC-V multicycle processor can be downloaded via the link in the previous section. This processor implementation supports the following instructions:

  • lw
  • sw
  • add
  • sub
  • and
  • or
  • slt
  • addi
  • beq
  • jal

Note that the ALU is incomplete, causing R-type and I-type instructions not listed above to yield incorrect results.

Volatile memory

Unlike the single-cycle processor in the previous lab, the memory component is set as volatile–the entire address space (which includes loaded instructions) is reset to zero.

This is done to ensure modifications to other parts of memory (e.g., stack memory) do not persist through resets as this may make debugging harder.

Hypothetical jal8 instruction

We will now add microarchitecture support for the hypothetical jal8 instruction.

jal8 is a hypothetical instruction that works like jal, but stores PC + 8 instead of PC + 4. In other words, it has the following parallel goals:

  • REG[rd] = PC + 8
  • PC = PC + SignExt(imm)

Assume that executing jal8 starts by performing Fetch and Decode. As such, we can assume that the architectural and nonarchitectural states of the multicycle processor are then as follows:

  • OldPC = PC
  • PC = PC + 4
  • A = REG[rs1]
  • B = REG[rs2]
  • ALUOut = PC + SignExt(imm)

There are several ways to achieve the goals of jal8 from here, with varying degrees of modification to the datapath and control.

The approach described below adds a new control state JAL8 which is intended to follow after Decode if the instruction is a jal8.

Designing a new JAL8 control state

Since ALUOut already contains PC + SignExt(imm) after Decode, JAL8 can simply set it as the value of PC to achieve the PC = PC + SignExt(imm) goal.

In particular, the following control signals must be set:

  • ResultSrc = 00 so that ALUOut is the output of the Result multiplexer
  • PCWrite = 1 so that PC is updated with the output of the Result multiplexer after the next triggering edge

This leaves the REG[rd] = PC + 8 goal which involves writing to the register file. Recall that PC here refers to the original PC value, which is stored in OldPC as PC is now PC + 4 (i.e., PC = OrigPC + 4).

Since the ALU is still unused in the JAL8 state, we can compute PC + 8 (or more precisely, OrigPC + 4 + 4) in parallel via the following control signals:

  • ALUSrcA = 00 so that PC is the first ALU operand (which contains OrigPC + 4 at this point)
  • ALUSrcB = 10 so that 4 is the second ALU operand
  • ALUOp = 00 so that ALUControl is set to 000 (addition)

The only step left is to write this sum to REG[rd].

Recall that:

  • We have already set the Result multiplexer to output ALUOut via ResultSrc = 00
  • The WD3 port of the register file (which dictates the value to be written) is also connected to the output of the Result multiplexer
  • Our remaining goal is to write PC + 8 to REG[rd]

Given the above, we will be unable to write PC + 8 to REG[rd] in parallel with writing OldPC + SignExt(imm) to PC.

While we can move the execution of REG[rd] = PC + 8 to another new state after JAL8, recall that:

  • ALUOut automatically saves the result of the ALU computation of the previous cycle
  • The existing ALUWB operation performs REG[rd] = ALUOut

As such, doing PC + 8 during the JAL8 cycle will allow us to perform REG[rd] = PC + 8 by doing ALUWB after.

In summary, the new JAL8 control state sets the following control signals:

  • ResultSrc = 00
  • PCWrite = 1
  • ALUSrcA = 00
  • ALUSrcB = 10
  • ALUOp = 00
  • RegWrite = 0 (since the register file must not yet be written to)
  • MemWrite = 0 (since memory must not be written to)
  • IRWrite = 0 (since Instr and OldPC must not be updated)

Doing so results in the following state changes:

  • PC = OldPC + SignExt(imm)
  • ALUOut = OrigPC + 8

jal8 can thus be handled using the following four-cycle sequence:

Cycle Operation Resulting state after triggering edge
1 Fetch PC = OrigPC + 4
OldPC = OrigPC
Instr = MEM[OrigPC]
A = 💩
B = 💩
ALUOut = 💩
REG[rd] = 💩
2 Decode PC = OrigPC + 4
OldPC = OrigPC
Instr = MEM[OrigPC]
A = REG[rs1]
B = REG[rs2]
ALUOut = OrigPC + SignExt(imm)
REG[rd] = 💩
3 JAL8 PC = OrigPC + SignExt(imm)
OldPC = OrigPC
Instr = MEM[OrigPC]
A = REG[rs1]
B = REG[rs2]
ALUOut = PC + 8
REG[rd] = 💩
4 ALUWB PC = OrigPC + SignExt(imm)
OldPC = OrigPC
Instr = MEM[OrigPC]
A = REG[rs1]
B = REG[rs2]
ALUOut = 💩
REG[rd] = OrigPC + 8

Implementing the new state

Before implementing new JAL8 state, we first have to assign a state value to it. Since S0 up to S10 are already used, we can use S11.

To implement the new JAL8 state, open the controlunit implementation. Verify that the following subcircuits are present:

  • maindecoder – Moore circuit computing almost all of the control signals
  • nextstatelogic – Combinational circuit controlling state transitions
  • aludecoder – Combinational circuit computing ALUControl
  • instrdecoder – Combinational circuit computing ImmSrc

Of the subcircuits listed, only the ALU decoder does not need to be modified for JAL8 as there were no changes made to the operation of the ALU.

Main decoder

Open up maindecoder and verify that you can see how each control signal is computed using only the current state.

Do now!

Assuming that the current state is Decode (S1 or 0001), identify the values emitted by maindecoder for the following based on its Logisim implementation:

  • PCUpdate
  • Branch
  • MemWrite
  • IRWrite
  • RegWrite
  • AdrSrc
  • ALUSrcA
  • ALUSrcB
  • ALUOp
  • ResultSrc

Note that floating values (i.e., U) are taken to be don't cares (i.e., X).

Recall that our new JAL8 state is assigned to S11 and that it must set the following control signals as follows:

  • ResultSrc = 00
  • PCWrite = 1
  • ALUSrcA = 00
  • ALUSrcB = 10
  • ALUOp = 00
  • RegWrite = 0
  • MemWrite = 0
  • IRWrite = 0

Recall that PCWrite is indirectly influenced by maindecoder via the PCUpdate and Branch control signals (where PCWrite = PCUpdate | (Branch & Zero)). Since PCWrite must always be 1 for JAL8, it should set PCUpdate to 1.

Do now!

For each control signal computed in maindecoder, locate its input port labeled "input 11" (corresponding to S11), then add a Constant component corresponding to the value JAL8 is supposed to set the said control signal to.

Ensure that the existing connections are kept intact.

To verify your implementation, you may use the Poke tool to manually set the individual bits of the State input and confirm that the outputs shown are as intended.

Next state logic

Open up the nextstatelogic and examine how NextState is being computed from the current state and the current instruction.

Do now!

Recall that S1 (Decode) has the following state transitions:

  • S2 (MemAddr) if current instruction is lw or sw
  • S6 (ExecuteR) if current instruction is lw or sw
  • S8 (ExecuteI) if current instruction is an I-type ALU
  • S9 (JAL) if current instruction is jal
  • S10 (BEQ) if current instruction is beq

Ensure that you understand how a priority encoder is used to determine which kind of instruction is being executed.

Verify that the implementation for NextS1 is consistent with the state transitions listed above for S1 (Decode).

Verify as well that the implementation for NextState ensures that NextS1 will be selected when the current state is S1 (Decode).

Recall that we want the JAL8 state to come after the Decode state, but only when executing the JAL8 instruction, and that we want ALUWB to come after JAL8.

To do this, we need to be able to detect that the current instruction being executed is JAL8. We will define JAL8 as having an opcode of 0b1101110 or 0x6e.

Do now!

To make S1 (Decode) transition to S11 (JAL8) when the current instruction is JAL8, do the following:

  • Add a new comparator that compares the opcode (using a tunnel) and 0010111 (as a constant), then set the equality result to a new IsJAL8 tunnel

  • Add another IsJAL8 tunnel to "Input 6" of the priority encoder used to generate Selector

  • Set the value of the "Input 6" port of the multiplexer computing NextS1 to b (corresponding to S11 (JAL8))

To make S11 (JAL8) transition to S7 (ALUWB) regardless of the current instruction, do the following:

  • Create a new tunnel NextS11 and set its input to 7 (corresponding to S7 (ALUWB))

  • Connect another NextS11 tunnel to the "Input 11" port of the multiplexer computing NextState

Ensure you understand the reason why each step was done.

Instruction decoder and extend unit

Recall that the instruction decoder is in charge of computing ImmSrc, which is used by the extend unit to determine how the immediate value will be constructed from the instruction bits.

Also, recall that J-type instructions correspond to ImmSrc = 011.

Open up instrdecoder and verify that the instruction detection logic is similar to that of nextstatelogic.

Do now!

Add a comparator and IsJAL8 tunnels similar to the previous section, then set the value of "Input 6" port of the multiplexer computing ImmSrc to 3 (which corresponds to 0b011).

Tip: HOPE 2 expectations

You will be expected to add microarchitecture support for hypothetical instructions such as jal8 during HOPE 2.

Verification

The changes in the earlier sections should be enough for the multicycle processor to properly execute the jal8 instruction.

To check whether you have implemented jal8 correctly, you may use this simple test program:

add x0, x0, x0  # 0:  00000033
jal8 x1, 12     # 4:  00c000ee
add x1, x1, x1  # 8:  001080b3
add x1, x1, x1  # c:  001080b3
add x0, x0, x0  # 10: 00000033

After execution of the test program, x1 is expected to have a value of 0xc with all other general-purpose registers equal to 0x0.

Notice that the bottom part of the control unit in mcpfull shows the current state for tracing purposes. You may use this to verify that all state transitions are as intended.

Do now!

Enter the corresponding machine instructions in the memory of the multicycle processor, then tick the clock until it says 12 ticks (or when the stated PC value is 0x14).

Verify that the register values shown in the State tab of Logisim are consistent with the register values shown above.

Verification of existing instructions

The test above does not verify whether the other supported instructions still work as intended.

You are strongly encouraged to make a more comprehensive test program that involves lw, sw, add, sub, and, or, slt, addi, beq, and jal.

HOPELEx Checkpoint

Checkpoint Task: bne

Modify the given Logisim circuit to support the B-type instruction bne.

Ensure that all other instructions that were supported before by the template still work as intended.

You are allowed to use tunnels.

Save the resulting circuit as lab06.circ.

TakeHOPE Problems

Item 1: R-type instructions

Add microarchitecture support for the following instructions:

  1. sub
  2. and
  3. or
  4. xor
  5. sll
  6. srl
  7. sra
  8. slt
  9. sltu

Item 2: I-type instructions

Add microarchitecture support for the following instructions:

  1. andi
  2. ori
  3. xori
  4. slli
  5. srli
  6. srai
  7. slti
  8. sltiu

Item 3: Branch instructions

Add microarchitecture support for the following instructions:

  1. bge
  2. blt
  3. bgeu
  4. bltu

Item 4: Other instructions

Add microarchitecture support for the following instructions:

  1. lui
  2. lb
  3. lbu
  4. lh
  5. lhu
  6. sb
  7. sh

Item 5: Pseudoinstructions

Turn the following pseudoinstructions into basic instructions and add microarchitecture support for them:

  1. not
  2. ble
  3. bleu
  4. bgt
  5. bgtu
  6. beqz
  7. bnez
  8. blez
  9. bgez
  10. bltz
  11. bgtz