Lab 9: Build a Simple Datapath

In this lab, you will build a working datapath for a simple instruction set using some of the larger components we’ve already built in this class. You are provided with a simple program counter that increments with a clock signal, an instruction memory element, an instruction decoder, a register file, and ALU, and data memory. Your job is to connect these components together so they can execute instructions.

Assigned: Monday, October 31

Due: Monday, November 7 by 10:30pm

Submitting your work: Submit your completed datapath file by email. Include your answers to questions from each part of the lab in the body of your email.

Groups

  • Hamza, Adam W., and Sara
  • Maddie and Giang
  • Jerry and Adam H.
  • Sophie and Blake
  • Tanner and Fengyuan
  • Ana and Kamal
  • Hattie and Eli
  • Matt and Ryan
  • Theo and Linda
  • Jacob and Bea
  • Devin and Charlie

Part A: Getting Started

First, download datapath.circ and open it with Logisim. Start logisim with the following command:

$ java -jar /home/curtsinger/bin/logisim.jar &

Major Datpath Components

This circuit includes six major components, described below.

Program Counter

An image of the datapath's program counter

This section of the datapath implements a program counter. This component is connected to a clock input. If you click the clock with the hand tool, it will cycle through and increment the program counter on every falling edge. The program counter is stored in Logisim’s register component, and holds an 8 bit value. The two digits in the component show that value in hexadecimal.

Instruction Memory

An image of the datapath's instruction memory

This piece of the datapath is the instruction memory. Your starter file is pre-loaded with a program that should count up in the first register, and keep a running sum of the counter values in the second register. We’ll get to instruction encoding later, so don’t worry about why this sequence of hexadecimal values represents that program yet.

One key feature of this architecture is that we have 32 bit instructions. Our memory element is set up so each access pulls out 32 bits all at once. So, if the program counter is 2 we get the third chunk of 32 bits (remember, we start counting at zero). So, PC=0 gives us the first instruction, PC=1 gives us the second instruction, and so on.

Instruction Decoder

An image of the datapath's instruction decoder

This single component is the instruction decoder. It’s actually just a splitter, because this instruction set was designed to be simple to decode. Real instruction sets are as compact as possible, but ours uses extra bits to align most values to 4-bit boundaries (a single hex digit, called a “nibble”).

The splitter shows which bits of the 32 bit instruction come out of each wire. At the top we have bit 31 by itself, and at the bottom we have bits 0-7 together in an 8 bit bus. The splitter is set up specifically for our instruction format, which we’ll discuss later in this section.

Register File

An image of the datapath's register file

This component is a 4x8 register file. At the top of the block there is a connection to the clock signal. The two left connections select registers for the two read ports. Directly across from these two bit selectors, there are two outputs, one for each read port. Along the bottom of the register file block we have the write address (which register to write to), the write enable bit, and the 8 bit data input that should be written. This register file stores new values on a falling clock edge.

I have added some extra outputs to make it easy to see the state of each register. You can use these to watch your program execute, but don’t hook anything up to the output pins inside the register file rectangle.

ALU

An image of the datapath's ALU

This component is a fairly standard 8-bit ALU for our architecture. The two inputs are on the left side, and the output is on the right edge. Along the top edge we have four inputs: a invert, b invert, carry in, and the operation selector. The four operations are addition (00), and (01), or (10) and xor (11). Remember, you can compute a-b by adding a to negated b. You can negate b by setting b invert to 1 to flip the bits of b and setting carry in to 1 to add 1.

Data Memory

An image of the datapath's data memory element

Our final datapath component is the data memory element. This component is a random access memory (RAM) that allows you to load and store from arbitrary addresses. Values in this memory element are each 8 bits, so the address 3 refers to the fourth 8-bit chunk (byte) of memory.

The A input on the left edge is an 8-bit address. The D input on the left is the 8-bit value that should be stored at this address, and the D output on the right is the value loaded from the given address.

Along the bottom, there are control connections. The clock is already connected with an inverter, so this memory element will store values when the main clock falls. If the str input is connected to a zero, storing is disabled. If it’s a one then the input data will be stored. The other inputs allow you to disable the memory element (sel), enable/disable loading (ld), and clear the memory (clr). The only control pins you will need for this assignment are the clock and store control; leave the rest disconnected.

Instruction Set

Our instruction set for this assignment is designed to be easy to decode. Each instruction specifies all of the information you need to control the datapath. The bits, from left to right, have the following meanings:

bit 31
Jump instruction. Set the program counter to the value in the immediate field.
bits 28-29
ALU operation
bit 27
ALU a invert
bit 26
ALU b invert
bit 25
ALU carry in
bit 24
if 1, ALU should use immediate value for input b
bit 22
Load instruction. If 1, use ALU output as an address. Load from this address and store result in destination register.
bit 21
Store instruction. If 1, use ALU output as an address. Take the value from the second source register and store it to this memory location.
bit 20
Write the result of the instruction to the destination register. The result may be the ALU output or a value loaded from memory.
bits 16-17
Destination register
bits 12-13
First source register
bits 8-9
Second source register
bits 0-7
8-bit immediate value

Any missing bits are unused. Just fill these bits with zeros when encoding an instruction. Here are a few sample instruction encodings, along with explanations.

addi $r0, $r0, 1

This instruction takes our first register (which we’re calling $r0), and increments it. In binary, we encode this instruction as 0000 0001 0001 0000 0000 0000 0000 0001. In hexadecimal, that’s 0x01100001. This instruction is not a jump, sets the ALU operation to addition. We set a invert, b invert, and carry in to zero, but bit 24 is set because we are using an immediate value. This is not a load or store instruction, but we to want to write the result to our destination register, so bit 20 is also set to 1. The destination register is 0, first source is 0, second source doesn’t matter (we aren’t using it), and the immediate value is 1.

add $r1, $r1, $r0

We encode this instruction in hexadecimal as 0x00111000. This instruction is similar, except our destination and first source registers are 1 instead of 0. The immediate bit is set to zero because we are not using an immediate value for this instruction.

j 0

This instruction jumps to the instruction at address zero. We encode this instruction as 0x80000000. This sets the jump bit, and uses the immediate value 0x00. If we instead wrote 0x800000af, this instruction would jump to the instruction at 0xaf.

lw $r1, 4($r0)

This instruction loads the value at 4+$r0 and stores it in $r1. We encode this instruction as 0x01510004. The ALU operation is set to addition. We are using an immediate value for that addition (the value 4). This is a load instruction, so bit 22 is set, and we also want to store the result to our destination register, so bit 20 is also set. The destination register is 1. The first source is $r0, and the second source doesn’t matter. Finally, we have our 8-bit immediate value 4.

sw $r2, 0($r0)

This instruciton takes the value in $r2 and stores it at the address 0+$r0. We encode it as 0x01200200. Again we have the immediate bit set, because we’re adding an immediate value of zero. We’re storing, so bit 21 is set. Nothing should be written to any registers, so bit 20 is not set. The destination register doesn’t matter, so it is zero. The first source is $r0 (used in the address) and the second source is $r2. Finally, the immediate is zero in this case, so the instruction ends with 0x00.

Sample Program

Instruction memory is pre-loaded with the following program:

0: addi $r0, $r0, 1
1: add $r1, $r1, $r0
2: j 0

Part A Questions

  1. We don’t have a $zero register in this architecture. How can you store the value zero to a register? Pay close attention to the operations supported by our ALU.

  2. Instruction sets don’t usually have a dedicated opcode for nop. Instead, they use instructions that have no effect on registers or memory (like addi $r0, $r0, 0). This instruction set has many different ways to encode nop. For example, any operation that has zeros in the four bits 31, 22, 21, and 20 (jump, load, store, and writeback, respectively) will behave like a nop. Write down encodings for at least two additional instructions we could use as nop.

  3. This instruction set supports some interesting memory operations that MIPS does not allow. Write encodings for the following instructions:

    • Load a value from the location $r0+$r1 and store the result in $r2
    • Store the value in $r3 to $r3+$r0
    • At least one other memory operation that MIPS does not support. Explain what this instruction does.

Part B: Complete the Datapath

Using the specifications above, complete the implementation of this datapath. I recommend starting with basic ALU instructions that do not use immediate values like add $r0, $r0, $r1. Next, move on to support for addi, ori, and so on. Once you have these basic instructions working, you can modify the program counter loop to support jump instructions. Finally, add load and store operations by integrating the data memory component.

You should write simple test programs to make sure your implementation is working at various stages in the process. Don’t wait until you’ve “completed” the datapath to test it! You’ll probably get something wrong, and circuits are hard to debug.

You can load a sample program by clicking on lines in instruciton memory with the hand tool. Just start typing hexadecimal values and the digits will gradually fill the available space. You can also right click on the instruction memory element and select Edit Contents, although I have had trouble with this editor before. Once you have a program loaded, click the clock element with the hand tool to toggle the clock on and off.

Once you’ve run a program, your registers will probably contain garbage values. Under the Simulate menu, select Reset Simulation to clear registers and the program counter to zero.

Part B Questions

  1. Write a program that adds 1 to $r0, 2 to $r1, 4 to $r2, and 8 to $r3, then repeats this process indefinitely. Encode this program using our instruction set and test it. Submit the assembly code and encoded instructions.

  2. Write a program that stores the value 0 in address zero, 1 in address 1, 2 in address 2, and so on using an infinite loop. Test your program using your completed datapath. Submit the assembly code and encoded instructions.

  3. Write at least one more program that does something interesting using a mix of memory, immediate, and register-only instructions. Submit your assembly, encoded instructions, and an explanation of what the program does.