CS 240 Lab 5

Processor Datapath

CS 240 Lab 5

• Lab slides
• Learning Goals & Reflection

In this lab, you will construct part of the hardware (called the datapath) for a simple computer. (referred to as the HW Arch). You have already studied some of the circuits that are major components in previous labs, including multiplexers, ALUs, registers, and register files.

To start with, use this simulator link to open the “CircuitVerse” simulator (a new one for today since we don’t have access to LogicWorks). It may take a while to load, with the progress bar getting stuck around halfway for a while. If this happens, try refreshing a few times.

Next, download this circuit file and use the “Project -> Import File” option to load it into the simulator. We’ll use different sub-circuits in different parts of the lab.

Note: It’s important to select “Project -> Preview Circuit” to run a circuit in CircuitVerse because some outputs seem to randomly reset themselves otherwise.

Random-Access Memory

If you already did this part but your partner hasn’t, walk through it again together. If both of you have already done it, you should skip it.

This exercise will show you how a RAM device is used to store and retrieve values from memory.

• If you’re using LogicWorks, download this instructionMemory.cct circuit and then open it in LogicWorks.
• If you’re using CircuitVerse, select the “RAM Test” tab of the HW ISA circuit. Then select “Preview Circuit” from the “Project” menu.

This circuit can be used to store data into a RAM at specific addresses, with the current value being overwritten by incoming data when the “Write” button is pressed.

Examine the circuit carefully to understand its operation: you write data values into a memory location specified by an address by using the inputs on the left to specify the data and address.

The currently selected address and the value stored at that address are displayed on the hex displays on the right (or in CircuitVerse, the address is shown on the left where you select it and the output is on the right in binary).

Exercise 1:

To read from memory:

If you’re in CircuitVerse, select the RAM and then click on “Load Data” from the properties menu on the right. Paste in the following values and hit “Ok”: 0x5002,0x5003,0x5003,0x0230

Read the data at addresses 0 through 3, and confirm it below (enter just the 4 hex digits you see, from top to bottom):

GCorrect answer:

Address 00: Correct answer: 5002

Address 01: Correct answer: 5003

Address 02: Correct answer: 5003

Address 03: Correct answer: 0230

Check AnswersCorrect answer: See above

To write into the RAM, select the address you want to write to, set the data input to the desired new value for that address, and pulse the Write input (click the button in CircuitVerse or toggle the input on and then off again in LogicWorks).

Try writing the value 0x0123 into address 4 now.

Given that the RAM has N address inputs, how many 16-bit values can it store?

• LogicWorks (N = 8) Correct answer: 256
• CircuitVerse (N = 16) Correct answer: 65536

Fetching Instructions

The RAM we just saw can be used to store a program, if each word stored corresponds to an HW ISA instruction. By feeding these instructions one at a time into a CPU, we can run that program. This means we need to keep track of the current instruction, and have a mechanism for loading subsequent instructions one at a time. The Program Counter or PC is used for this purpose: it’s a register that determines which instruction to read, and that increases its value every clock cycle.

The PC is connected to the address inputs of the memory device, and the instruction stored at that address is output on the data output lines of the memory device (and is then fed into the processor for execution).

The PC must be updated after an instruction is fetched, with the address of the next instruction stored in memory. Often, this will simply be PC + 2, since the default is that instructions execute in sequential order. An adder can accomplish this, as shown below:

Exercise 2:

Download the FetchInstruction.cct circuit and then open it in LogicWorks.

OR

Select the “PC Assembly” tab in CircuitVerse.

In LogicWorks, the memory has been loaded with a program previously, by writing data representing instructions to sequential addresses in memory, starting at address 0 (as you did in the previous exercise).

In CircuitVerse, you’ll need to select the RAM chip on the right, click “Load Data” from the “Properties” menu, and paste in the following data: 0x5012,0xFFFF,0x5013,0xFFFF,0x0040,0xFFFF,0x2232,0xFFFF,0x2233,0xFFFF,0x3414,0xFFFF,0x7401,0xFFFF,0x8003

Make the necessary connections to the circuit in LogicWorks or CircuitVerse to implement instruction fetch (look at the diagram above to understand where to make the connections in the circuit, although in CircuitVerse we use a 16-bit register instead of an 8-bit register).

This step requires a bit more inference than usual. Ask the instructor for help if you’re not sure how to proceed.

If you’re working in LogicWorks, when you’ve made the connections, check them against this image (there are three connections to make).

In CircuitVerse, there are four connections to make. Check your results against the “Simple PC” tab.

Note that in CircuitSim and LogicWorks, a row of wires with numbers on them represents breaking a multi-wire data line (called a bus) into its individual components. Also, the upwards triangle in CircuitVerse represents +5V, i.e., logical 1, while the three bars represents ground which is logical 0. Describe how the value of “2” is achieved as an input to the adder in the circuit:

Example answer: The B1 line (wire 1 in CircuitVerse) is set to +5V while the rest of the lines are set to ground, meaning that together, the inputs are permanently set to the binary representation of the number 2.

When the adder adds 2 to the PC, it stores the result back into the PC. Turn on “Simulation -> Show Values” in LogicWorks and you’ll be able to see the data values each bus is carrying as hex digits (CircuitVerse doesn’t have that feature, but we’ve hooked up the F1 debug flag to the wire that should receive the adder output, so you can see the value there). When the PC output value is 0, what is the value of the output from the adder? Correct answer: 2

Since the adder output is connected to the PC input, the PC output will update to match. Given that the PC register uses D flip-flops to store data internally, when will this happen?

Continuously while the clock signal is on.
Continuously while the clock signal is off.
Once per cycle, at some point during the ON part of the clock signal.
Once per cycle, exactly on an edge of the clock signal.

When the PC is updated to have the value 2, what will be the value of the adder ouptut? Correct answer: 4

Explain what would happen during a single clock tick if the PC register used D latches (which update continuously during the clock ON pulse) instead of D flip-flops (which update once exactly on the falling edge of the clock) to store data?

Example answer: If the PC register used D latches, the input value would immediately determine the output value, which would then change the input to the adder, changing its outputs and feeding back into the PC inputs. This loop would keep adding 2 continuously during the ON tick of the clock, resulting in an undefined (and definitely incorrect) PC value. By using D flip-flops, we guarantee that the data is read in only at one instant (when the clock tick ends), and that the old address value is output during the entire clock ON cycle.

Exercise 3:

To fetch the instructions from memory:

Pulse the Reset input (1 then back to 0, or click the button and release it in CircuitVerse). Note that the PC value is now 0.

To go to the next address, you will activate the clock (set to 1 and back to 0, or click and release in CircuitVerse).

Record the address and instruction below, and then repeatedly clock and record results for 8 instructions (do NOT reset between clocks; you just need to reset once).

Instruction Set Architecture

Before we add further components to our CPU, let’s take a look at how these instructions in the instruction memory are supposed to be interpreted. The HW ISA is a specification that determines what the HW Arch circuit is supposed to do.

Exercise 4:

For the first instruction we saw above, 0x5012, use the HW ISA Instructions table shown below to translate it into assembly syntax.

Note: The Opcode, Rs, Rt, and Rd values together are encoded in 16 bits (4 bits = 1 hex digit each). The opcode bits are the most significant bits, while the Rd bits are least significant.

Note: The JMP offset is unsigned. All other offsets are signed.

Keep the HW ISA Instructions slide open in another tab for reference throughout the lab.

The assembly syntax for 0x5012: Correct answer: OR R0, R1, R2

We haven’t shown you the register file yet, but you’ve seen the HW ISA, which is a specification for what the HW Arch circuit must do. According to the specification, which register should 0x5012 store its result in?

R0
R1
R2
R3

Which registers does 0x5012 read values from?

R0
R1
R2
R3

Explain what the result of executing 0x5012 should be, in terms of changes to the contents of the register file:

Example answer: The value of register R2 would be set to 1, since R0 always holds 0 and R1 always holds 1, so 0 | 1 is 1.

After working through the exercises above, click here to see each instruction from the provided RAM translated into HW ISA assembly, along with an explanation of what it does:

Basically, this is how a program is executed:

Initially, the program instructions are loaded into the instruction memory.

Then, the instruction fetch mechanism you just saw loads one instruction at a time (one instruction per clock cycle).

The rest of the CPU executes that instruction during the clock cycle, updating the register file, data memory, and/or program counter as specified by the HW ISA.

The CPU circuit needs to be fast enough to deliver correct outputs by the end of the clock cycle, when these outputs will be internalized by the D flip-flops in each memory component and a new instruction from the instruction memory will be sent to the CPU.

Fill in the table for the following program to show your understanding of the HW instructions at the machine code level:

Describe the result (specific values of modified registers, plus the current PC value) after allowing 10 total instructions to execute:

Example answer: 10 instructions will run all 5 of the listed instructions, plus after jumping up (which happens twice) instructions at addresses 4 and 6 will run twice more each. The final PC will be 8 (ready to do the jump again) and the values of R2 and R3 will be 13 and 21, respectively.

Does this program ever stop?

Yes
No

To connect this to a programming language we’re familiar with, click here to show an example of C code which might compile into these instructions:

void fibonacci() {
    int x = 1, y = 1;
    while (1) {
        x = x + y;
        y = x + y;
    }
}

Control Flow

As you learned about in lecture and the pre-lab assignment for today, the logic of conditional execution in the HW computer is implemented by BEQ and JMP instructions.

The diagram below shows the additional logic for producing a branch address for the BEQ instruction:

The offset for BEQ (which comes from the last 4 bits of the instruction) specifies the number of words away from the next instruction in memory (PC + 2) to jump to. The additional adder calculates a branch address = PC + 2 + 2 * offset.

A 2x8 MUX then selects whether the next address going back to the PC is PC+2 or the branch address.

The selection line to the MUX is based on two control lines: the Branch bit, which is true when a BEQ instruction is being executed, and the Zero bit, which is true when the contents of Rs and Rt are equal.

The Zero bit comes from the ALU: when the result produced by the ALU is 0, the Zero bit is set to 1 (we saw that in the ALU lab).

So, on a BEQ instruction, the ALU performs Rs - Rt, which will set the Zero bit to 1 only when the contents of Rs is equal to the contents of Rt.

You’ll find an implementation of this logic in the “Program Counter” tab in CircuitVerse (it just has one “Branch” input instead of “Branch” and “Zero”). Use it to answer the following questions:

1. With Advance and Branch set to 0, set Reset to 1 and then back to 0. What is the address value? Correct answer: 0

2. Toggle the Advance input on and then off again 3 times. What is the address value now (in decimal)? Correct answer: 6

3. Set Offset to 1101 (i.e., -3) and toggle Advance again. What is the address value in decimal? Correct answer: 8

   Why didn’t the offset value affect it? Example answer: Since Branch is still 0, the offset result is discarded at the right-hand multiplexer.

4. Now set Branch to 1 and toggle the Advance input one more time. What is the address value now? Correct answer: 4

   Explain why an offset of -3 produces this result:

   Example answer:

   The BEQ logic takes the offset and multiplies it by 2 using a left-shift before applying it. So -3 becomes -6. It also applies the usual +2 update before applying the offset, so in total we have 8 + 2

   • 6 = 4.

Basic Datapath

The following diagram describes the basic datapath for executing the arithmetic and logic instructions:

Exercise 5:

Download the datapath.cct circuit and then open it in LogicWorks.

OR

Select the “Datapath Assembly” tab in CircuitVerse.

Make the necessary connections to implement the diagram shown above. Make sure to turn on “Simulation -> Show Values” in LogicWorks.

Note that in LogicWorks we do not have a control unit, and instead control the ALU Op and RegWrite values directly

Click here to check your work in LogicWorks or in CircuitVerse, check your work against the “Memoryless” tab:

The following table describes which ALU function will be produced by a given value of ALUOp:

BEQ is accomplished by subtraction (which sets the Zero bit).

BEQ and JMP do not change the value of a register.

The following table describes the ALU Op and Reg Write control lines for the arithmetic/logic and control flow instructions:

Simulate executing some instructions to verify that your circuit is correct:

• Pulse the “Reset” line (set it to 1 and then back to 0) so that all registers are set to 0 (except R1 which always contains 1).
• Execute these tests in order without resetting in between.
• For each given test, set the specified values on the input devices and then pulse the CLK input (set to 1 and back to 0) to execute the instruction.
• For each given instruction, record the values for each of the signals in the datapath, and note what registers are modified by the instruction.
• Then, to verify your result, set the inputs on the hex keyboards and switches in the circuit, and pulse the CLK to observe the output of the ALU.

Note: The ALUop is not always the same as the opcode for an instruction- check the table directly above!

1. ADD R1,R1,R5

   ALUop (in hex):	Rs:	Rt:	Rd:	RegWrite:	ALU result (4 hex digits):
   GCorrect answer: Correct answer: 2	Correct answer: 1	Correct answer: 1	Correct answer: 5	Correct answer: 1	Correct answer: 0002

   Check AnswersCorrect answer: See above

   Which register is changed? Correct answer: R5

   What value does that register have now (in decimal)? Correct answer: 2

2. ADD R5,R5,R2

   ALUop (in hex):	Rs:	Rt:	Rd:	RegWrite:	ALU result (4 hex digits):
   GCorrect answer: Correct answer: 2	Correct answer: 5	Correct answer: 5	Correct answer: 2	Correct answer: 1	Correct answer: 0004

   Check AnswersCorrect answer: See above

   Which register is changed? Correct answer: R2

   What value does that register have now (in decimal)? Correct answer: 4

3. OR R2 R5 R6

   ALUop (in hex):	Rs:	Rt:	Rd:	RegWrite:	ALU result (4 hex digits):
   GCorrect answer: Correct answer: 1	Correct answer: 2	Correct answer: 5	Correct answer: 6	Correct answer: 1	Correct answer: 0006

   Check AnswersCorrect answer: See above

   Which register is changed? Correct answer: R6

   What value does that register have now (in decimal)? Correct answer: 6

4. SUB R5,R6,R3

   ALUop (in hex):	Rs:	Rt:	Rd:	RegWrite:	ALU result (4 hex digits):
   GCorrect answer: Correct answer: 6	Correct answer: 5	Correct answer: 6	Correct answer: 3	Correct answer: 1	Correct answer: FFFC

   Check AnswersCorrect answer: See above

   Which register is changed? Correct answer: R3

   What value does that register have now (in decimal)? Correct answer: -4

5. AND R2,R5,R7

   ALUop (in hex):	Rs:	Rt:	Rd:	RegWrite:	ALU result (4 hex digits):
   GCorrect answer: Correct answer: 0	Correct answer: 2	Correct answer: 5	Correct answer: 7	Correct answer: 1	Correct answer: 0000

   Check AnswersCorrect answer: See above

   Which register is changed? Correct answer: R7

   What value does that register have now (in decimal)? Correct answer: 0

Full Datapath with Memory Access Instructions

The following diagram adds the logic and the Data Memory device needed to implement the memory access instructions (LW and SW):

To distinguish between what is done in the dataptath for arithmetic/logic and control flow instructions (ADD, SUB, AND, OR, BEQ) versus what is done for memory access instructions (LW, SW), the following is necessary:

• Use a 2x4 MUX at the input of the Register File to choose the source for the register to be written to (Rd gets written to for arithmetic/logic operations, Rt gets written to for LW).

• Use a 2x16 MUX at the second input to the ALU. The MUX selects whether the ALU input comes from Rt or from the offset specified by the third operand of the instruction.

Exercise 6:

Below we have specified several operations by giving the relevant instruction values Rs, Rt, and Rd/offset as well as the Control Unit output values derived from the Opcode part of an instruction.

Refer to the table from the previous part about which ALU Op specifies which ALU function.

Before predicting the following operations, assume that all registers contain a value of 0 initially except R1 (which contains a 1). But assume that the registers are NOT reset between operations.

For each operation, predict the ALU result (in decimal) and explain which registers or memory locations would get a new value as a result of the operation.

Operation 1:

Explain the operation and result, and what register is modified with what new value:

Example answer: Addition of R1 with itself. R1 + R1 = 1 + 1, stored in R6. R6 gets a 2.

Operation 2:

Explain the operation and result:

Example answer: Addition of R6 with itself. R6 + R6 = 2 + 2, stored in R3. R3 gets a 4.

Operation 3:

Assume that Operation 3 is a Store Word (SW) instruction. Explain how you would know this from the values of the control signals.

Example answer: Mem being 1 means it’s either LW or SW. MemStore being 1 means it’s SW.

What value would be stored to what address in Data Memory?

Operation 4:

Assume that Operation 4 is a Load Word (LW) instruction. Explain how you would know this from the values of the control signals.

Example answer: Mem being 1 means it’s either LW or SW. MemStore being 0 means it’s LW.

What address in Data Memory is being accessed?

Example answer: The address being accessed is address 8, the same one we just wrote to. But the way it’s computed is different. This time Rs = R3, and the offset is 4, so we compute 4 + 4 = 8.

What register will receive what new value from that address in Data Memory?

Example answer: R6 gets the value 1, which was previously stored in address 8.

Stretch Exercises: Control Unit

You have seen that the ALU Op bits (which control the operation of the ALU) are not the same as the instruction opcode (which specifies which instruction is being executed).

It is necessary to translate the instruction opcode to the proper ALU operation (which specifies ainv bneg op1 op0 into the ALU) for each instruction, as shown below:

Note: The JMP instruction is not shown in this table because it does not use the ALU.

Exercise 7:

1. Explain why LW and SW have the same ALU operation as ADD:

   Example answer: Because they need to add the address register to the offset that comes as part of the opcode to get the actual address to read from or write to.

2. Write a Boolean function for each ALU operation bit in terms of the opcode “O0-O3” inputs.

   ainv = 0 (always off in these examples)

   bneg = Example answer: O1O0

   op1 = Example answer: O2’ + O2O1O0 (could be simplified to O2’ + O1)

   op0 = Example answer: O2O1’O0

The logic to produce the ALU Op bits (which you just designed) is part of the Control Unit.

The Control Unit also produces the other data path control signals for each instruction, as shown below:

Explain why the Reg Write bit is set for LW, ADD, SUB, AND, OR, but not for SW, BEQ, or JMP:

Example answer: The operations where RegWrite is set are operations where a result is written to a register. SW, BEQ, and JMP don’t write to a register: SW writes to memory instead, and BEQ and JMP change the PC.

Write a boolean function for each control line as a function of the opcode bits O0-O3:

RegWrite = Example answer: (O3’O2’O1’O0 + O2O1O0 + O3)’

Mem = Example answer: O3’O2’O1’

Mem Store = Example answer: O3’O2’O1’O0

Branch = Example answer: O2O1O0

Jump = Example answer: O3

Although we will not do so in lab today, you can see that it is easy to implement the Control Unit with basic logic gates.

Extra Exercises: Full Implementation

Download the computer.cct circuit and open it in LogicWorks.

OR

Select the “Full CPU” tab in CircuitVerse.

Close the timing window and parts palette in LogicWorks (or minimize the “Circuit Elements” and/or “Properties” windows in CircuitVerse) to view the full circuit:

The CPU has been abstracted to a black box, and is connected to the Instruction Memory, where programs must be loaded prior to execution by the CPU.

The WR, LOAD, Instruction/Data in, and Address in inputs on the left are used to load a program into Instruction Memory.

LOAD is used to control the 244 devices that you see on the bottom left, and is needed for proper operation of the circuit for loading a program vs. running a program (the 244 is a multi-input/output tri-state buffer that can be set to let data through or appear disconnected; the LOAD switch toggles whether the top or bottom buffer is activated). Simply follow the instructions given later for how to use it.

The PC/address and Instruction hex displays on the bottom show the address in Instruction Memory currently being executed, and the instruction itself.

The Rs and Rt register file ports and the ALU result from the CPU are also displayed. These can be used to verify correct execution of instructions.

The Reset and CLK switches on the bottom are used to control execution of a program in the CPU. The following program will perform a loop (the first three instructions initialize registers to values to be used in the calculation).

Exercise 8:

Fill in the hexadecimal value for each encoded instruction in the table below, including values to make the BEQ and JMP instructions reach the intended lines:

To load the Instruction Memory with this program:

Note: in CircuitVerse, the LW, SW, and JUMP instructions are not implemented, so this program won’t work. Skip to the next exercise.

To execute the program:

• Set LOAD = 1 (only necessary in LogicWorks)
• Set Reset = 1, then back to 0
• Set CLK = 1, then back to 0, for each instruction. Stop the first time PC = 8, and examine the output of the ALU. The first time, you should see the value of 6 displayed at the ALU output.

Keep executing the program, examining the result each time PC = 8.

The program is finished when PC = 0x18. How many times was the loop repeated? Correct answer: 3

Writing Programs

Exercise 9:

Write a program that does NOT use LW, SW, BEQ, or JUMP which sets the ALU result to a value of 0x1000 or higher.

Load your program into the CPU and test to make sure it works.

Exercise 10:

Note: in CircuitVerse, the LW, SW, and JUMP instructions are not implemented, so while you can write these programs, you cannot execute them on the CPU.

Assume that after the previous exercise, you have a value of 4 stored in address 2 and a value of 2 stored in address 6 in Data Memory.

Write a program which will add those two values together, and store the result in address 0 in Data Memory. Write your program as a series of hexadecimal instructions in the table below, using registers 5 and 6 to store the data after loading it from memory, and register 7 to hold the addition result before loading it back into memory:

Load your program into the Instruction Memory and verify that it works correctly.

Now, write a program which will load from memory addresses 2 and 6 and multiply those two values using a loop with successive addition (use the R2 and R3 registers to hold the loaded values, and R4 for the result. Record your program below:

Note that at the end, you can use instruction 4444 to show register 4 which should hold the result.

Load your program into the Instruction Memory and verify that it works correctly.