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.
First, download datapath.circ and open it with Logisim. Start logisim with the following command:
$ java -jar /home/curtsinger/bin/logisim.jar &
This circuit includes six major components, described below.
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.
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.
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.
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.
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.
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.
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:
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.
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
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
Instruction memory is pre-loaded with the following program:
0: addi $r0, $r0, 1 1: add $r1, $r1, $r0 2: j 0
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.
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
This instruction set supports some interesting memory operations that MIPS does not allow. Write encodings for the following instructions:
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
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.
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.
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.
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.