Lab: Build a Datapath, part I

Assigned

November 24, 2020

Due

December 1, 2020 by 8:00am Grinnell time

Submitting

You will submit datapath labs I and II together; you can find submission instructions on the datapath II lab page.

Overview

In this lab, you will build a working datapath and assembler for a simple architecture we’re calling PIPS. You will be given a Logisim file with the major components of the datapath, as well as a nearly-working assembler. Your responsibility is to connect the components of the datapath to implement PIPS instructions and add translation rules to the assembler to convert PIPS assembly to PIPS machine code.

Before starting the lab, download datapath.tar.gz. This archive includes the starter code for the assembler and the provided Logisim components. Extract this archive by double-clicking it in your file browser; if that doesn’t work, run the following shell command:

$ tar xvzf datapath.tar.gz

Logisim Datapath

We will take a quick tour of the datapath components at the start of the lab, but here is a brief description of what is provided for your reference:

Program Counter: This is a single 16-bit register that holds the address of the currently-executing instruction. On each clock tick, the program counter is advanced by four.
Instruction Memory: This is the memory element that holds the encoded instructions your datapath should run. You can right click on this component and choose “Load Image…” to open a file produced by your assembler and load it into instruction memory.
Instruction Decoding: This unlabeled area of the datapath is just a series of splitters that break an instruction loaded from instruction memory into its individual fields. You will have a chance to read about all of these fields later on.
Microprogram ROM: This is a read-only memory area that converts instruction opcodes into control signals. This works very much like the microprogram memory in the K&S datapath, although there are many more “switches” to control. We’ll spend some time discussing this element in class.
Register File: This is a register file with sixteen 16-bit registers, two read ports, and one write port. Registers are written on the rising clock edge. Register 0 is fixed to the constant zero and writes to it are ignored.
ALU: The ALU takes two 16-bit values as input, performs an operation, and produces a 16-bit result. The available operations (in order) are addition, AND, OR, XOR, slt, and unsigned slt. The ALU also has invert controls for both inputs as well as a carry-in pin. In addition to the 16-bit result, there is a one-bit $zero$ pin that turns on when the result of the ALU operation is a zero.
Data Memory and Memory Controller: Data memory holds the values your program writes with store instructions, and returns them when you execute load instructions. The memory controller hides some of the ugly details required to support reading and writing 8- or 16-bit values. We won’t use data memory in today’s lab, but it’s here for you to use when we get to part 2 of this lab sequence.

Assembler

In addition to the Logisim starter file, you will find a few files related to the assembler. You won’t need to look closely at every file that’s provided, but here’s a quick summary of what you’ll find in each file:

asm: This program is the main entry point for the assembler. Execute this program with one or more assembly input files as command-line arguments. You can alo run this program with the “-h” flag to see a description of the command line options. You should not modify this file.
assembler.py: This is the main logic of the assembler. This file contains code to process input files after they are loaded by the asm program, keep track of translation rules, and handle other bookkeeping for things like labels. You should not modify this file.
pips.py: This file holds a variety of useful utilities for generating PIPS machine code. The two functions you will use most from this Python module are iformat and rformat. These functions take parameters that correspond to the fields in the encoded instruction and return a sequence of bits that encode the requested instruction. You will also find a detailed description of the PIPS instruction set in this file; we’ll look through this together at the start of lab. You should not modify this file.
rules.py: This is the file where you will write rules to translate assembly instructions into machine code. The starter code includes three example instruction translations: addi, li, and add. We’ll discuss the way you write these rules in part II of the project.

Part A: Addition

In this part, you’ll start out by implementing the addi, li, and add instructions in your datapath. The provided assembler rules are already able to translate these instructions, so you’ll only need to modify the datapath for this part. Start logisim with the command below, and then open the datapath circuit.

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

We’ll start with the addi instruction.

Implementing `addi`

The first step in implementing an instruction is to identify the pieces of the datapath you will need to connect together. Here’s a list of the datapath connections for an addi instruction:

The $r1$ field in the instruction indicates which register should be read from the register file. This should be connected to $R_{a0}$.
The register file will read the value of the requested register and pass that value out to $R_{d0}$. This value should go to the ALU as the A input.
The other ALU input should be the immediate value from the instruction (remember this is an addi instruction).
You will need to configure the ALU to perform addition by setting the $A_{inv}$, $B_{inv}$, and $C_{in}$ inputs to zero. The ALU performs addition when the three-bit $op$ input is set to 000. You can set up all of these values using constants from the “Wiring” category.
The result from the ALU should be passed back to the register file as the data to write to a register (the $W_d$ input).
The $r0$ field in the instruction indicates which register should be written by the instruction. Connect this to $W_a$ in the register file.
Finally, you should pass a 1 to $W_e$ to enable writing. You can do this with a constant in the “Wiring” category.

You should implement this control scheme without using the microprogram ROM for now.

Once you have your implementation ready, we can test it with the provided addi_test.s program. Working in whatever directory you unzipped the provided archive in, run this command to assemble the test program.

$ ./asm programs/addi_test.s

This will produce the file programs/addi_test.hex, which holds the machine code version of the simple test program. You can find the assembly instructions in either file (they’re included as comments in the machine code file).

To load your program, right click on instruction memory and choose “Load Image…” Select the addi_test.hex file. Now that your program is loaded, you can cycle the clock to execute instructions. All of the datapath’s clocks should run in sync, so do this by pressing Control+T (swap Command for Control on macOS). Do not click individual clocks, as doing so will only cycle one clock!

Complete at least four clock cycles (more shouldn’t hurt in this case). You should now have the value zero in $t0, one in $t1, two in $t2, and three in $t3. To verify this, right click on the register file and select “view register file”. This will show you the state of this component as it is simulated in the datapath rather than its original state. You can see the value of each register in the four hex digits at the center of the register component inside the register file. Each register component is labeled.

Once you have a working addi instruction you can move on to the next subpart. You do not need to have anyone check off this part.

(Double-click on the “main” circuit in the explorer pane to exit the zoomed view of the register file and return to your overall datapath.)

Implementing `add`

Your next task is to implement the add instruction. If you work through the datapath configuration for this instruction you’ll notice that almost all of the connections are the same. The only difference is that an add instruction should read a second register and pass its value to the ALU instead of the immediate value. This brings us to one of the important details of how PIPS instructions are encoded.

PIPS has two instruction formats: iformat and rformat. Instructions in iformat have two register fields ($r0$ and $r1$) and an immediate value. However, rformat instructions omit the immediate value and instead hold an additional register input (along with some other useful fields we’ll see later). The value of bit 16 in the instruction tells us whether the instruction is in iformat or rformat. However, every instruction will have some value for the $r2$ and $immediate$ fields. You will need to add some logic to select either the $r2$ or $immediate$ fields depending on the instruction format.

In the case of an add instruction, you will want to connect $r2$ to the second read port of your register file. After the register file you will need to use a multiplexor to choose either the output from the second read port ($R_{d1}$) or the immediate value and pass the result to the ALU’s $B$ input. This choice is determined by the format of the instruction.

You may worry what will happen when you run an addi instruction with this configuration, but this is actually okay; reading a register (even one encoded as a few bits from the edge of an immediate value) won’t change any state, and the datapath should discard the meaningless register value and use the immediate value instead.

You can leave all of the constants you used to control the ALU and register file in place; you should now have a datapath that can run both addi and add instructions. To test this, try assembling and running the add_test.s program:

$ ./asm programs/add_test.s

Warning! Before you load the assembled program, make sure you reset the simulation (type Control+R) to reset register values and the program counter. You’ll notice that this test program uses an li instruction in addition to add instructions. If your datapath is working you should find the value 3 in $s0, 6 in $s1, 12 in $s2, and 24 in $s3 after completing at least four clock cycles.

You can also run both test programs in sequence by assembling them together:

              $ ./asm -o programs/add_addi_test_combined.hex programs/addi_test.s programs/add_test.s

            

This just concatenates the two assembly files together and processes them as one program. We’ll use this in later labs to load libraries of useful procedures along with programs you write.

Once you have both add and addi working with constants as your control signal, have the instructor or a mentor sign off on your lab work before you go on to the next step.

Part B: Controlling the Datapath with a Microprogram

At this stage you have a datapath that can run add and addi instructions, but because you used constants to control the ALU you can’t support both subtraction and addition on the datapath in its current state. The signals that tell the ALU what to do should depend on what instruction we’re running; specifically, these signals should come from the $opcode$ field of the instruction.

The easiest way to convert an opcode into the corresponding control signals is with a microprogram. You can see in the provided circuit that the opcode is used as an address for the microprogram ROM. An add or addi instruction uses opcode zero, so you will want to store whatever values you need to control the datapath for an add operation in address zero of the microprogram ROM. The $D$ output of the microprogram ROM will produce 16 bits of data, and you can use splitters to break out individual bits and pass them on to control the ALU and register file. By loading values into the microprogram ROM, you are effectively making a look-up table that converts an opcode into control signals. We’ll start out by looking at a setup for the add and addi instructions you already implemented.

We will need to get rid of all the constants you added to control the datapath and instead get these values from the microprogram ROM. That means we need five control lines:

Write enable for the register file (1 bit)
A invert for the ALU (1 bit)
B invert for the ALU (1 bit)
Carry in for the ALU (1 bit)
Operation for the ALU (3 bits)

You won’t need all sixteen bits for control, but you should be efficient in your use of bits because the control signals will only increase as you add new instruction types. I recommend assigning these control lines to bits in order: bit zero (the rightmost bit) enables writing to a register, bit 1 turns on and off $A_{inv}$, and so on.

Editing the Microprogram for Control

The archive of materials for this lab includes data for the microprogram ROM in the file microprogram.hex. Every entry in the file corresponds to one of the sixteen possible opcodes in PIPS machine code, but all of the microprogram bits are initially set to zeros. You will need to change the 16-bit hexadecimal value for each opcode entry as you implement additional instructions.

If you haven’t already, open microprogram.hex in a text editor of your choice, such as emacs or vi.
Begin a block of documentation near the top of the file that clearly specifies what each bit field is used for (i.e., Register write enable, ALUOp). You should explicitly include either the number of bits (i.e., 4) or the bit range (i.e., 6–9).
The add and addi instructions both use opcode zero, so fill in the microprogram for these instructions at address zero. In doing so, you should clearly specify the value assigned to each bit field (in your comments). In addition to giving the raw value of the bits for each field, we strongly encourage you to then group these bits into nibbles before finally translating the nibbles into hex. It is a process you need to do anyway, and recording the incremental steps makes it much easier to detect and resolve errors that may have been introduced along the way.
After you have documented and completed the microprogram for the add/addi opcode in microprogram.hex, load it into the microprogram ROM by right clicking and selecting “Load Image…” While it is possible to edit the microprogram inside of Logisim, we recommend editing only in microprogram.hex and then re-loading the contents of ROM after each change.

Adding Datapath Control Lines

Now that you have a microprogram loaded into ROM, you’ll need to use splitters to extract each control line’s bits from the 16-bit output from the microprogram ROM. I recommend using a bunch of one-output splitters, much like how instructions are decoded; it’s easier to keep track of outputs this way, and you can leave space for labels. That does not mean each output should be a single bit—when the control line connects to a multi-bit bus, your output splitter should also produce the necessary bits (otherwise you will have to join them at the other end and your diagram will be far more cluttered with individual wires than it needs to be).

Once you’ve connected the control signals from your microprogram ROM to the ALU and register file re-run the test programs from the previous part to make sure your addition instructions all still work.

Once you’ve finished, have an instructor or mentor check off this part of the lab. Be prepared to show your commented microprogram file and updated datapath.