Build a Datapath, part 1

Due: 5:00 pm Tuesday 5 November 2019
Summary: You will build a complete datapath for a simple Instruction Set Architecture in Logisim.
Collaboration: You will work during lab in pairs of your choice. You must complete the work together in these groups, whether during or after the scheduled lab time.

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 B of the lab.

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 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.

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.

The add and addi instructions both use opcode zero, so fill in the microprogram for these instructions at address zero. Fill in the microprogram for this opcode in microprogram.hex, and then load it into the microprogram ROM by right clicking and selecting “Load Image…” While it is possible to edit the microprogram inside of Logisim, I recommend editing only in microprogram.hex and re-loading the contents of ROM after each change.

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.

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. You should be prepared to show your commented microprogram file and updated datapath.

Part C: Subtraction

Now that you’re able to control the datapath with a microprogram, we’re ready to implement support for subtraction instructions. Before you can test these out on your datapath you’ll need to assemble them. This will require that you write new assembler rules in the rules.py file. This file is written in the Python programming language, although you won’t need to know much about Python to add rules.

Let’s look at the addi instruction’s rule in detail as an example:

@assembler.instruction('addi #, #, #', 1)
def addi_inst(dest, op1, immediate):
  return pips.iformat(opcode='add', r0=dest, r1=op1, imm=immediate)

The first line of this rule declares that we are creating an assembler instruction. In Python terminology, this is known as a decorator. This runs a function to register the addi rule with the assembler so it will match lines in the input program. The decorator assembler.instruction is a function that takes two parameters: an instruction format and the number of machine instructions this assembly instruction will be converted to. The “#” character in the format indicates that some value will appear here; we don’t care what it is yet, but the way we use the value will determine whether it has to be a register, immediate, or something else.

The second line begins a Python function definition. The name of the function is not important, although giving it a descriptive name makes it easy to re-use this function when implementing pseudo-instructions like li. The addi_inst function takes three parameters: dest, op1, and immediate. The assembler will call this function to convert an instruction to machine code, and it will pass in the values that matched the three “#” wildcards in the pattern. This function is expected to return a string of 32 zeros and ones—yes, these are stored in a Python string rather than an integer—that represent this instruction in machine code. You generally aren’t responsible for producing the sequence of bits because the pips module has some helpful utilities.

The third line returns a value from this function. The value returned is produced by the pips.iformat function, which takes in the fields of an iformat instruction and combines them into a bit string. Each field is passed in using Python keyword arguments; the value before each “=” character is the name of a parameter to the iformat function, and the value after the “=” is being passed in as a parameter. This isn’t strictly necessary, but it makes it clearer what values are going into which fields of the instruction.

The call to pips.iformat says that we want to encode an iformat instruction with the ‘add’ opcode, using the first wildcard value in the instruction as the destination register, the second wildcard as a source register, and the third as an immediate value. The pips.iformat function will convert these parameters from strings for you. You should look closely at the documentation for the iformat function in pips.py to see how these fields are laid out and what they each do. There are also two tables in pips.py: one that converts opcode names into their corresponding numeric values, and another that converts register names to numbers. You’ll need to refer to the opcode table to see where you should add your microcode entries when setting up a new opcode’s control signals.

Add the following code to your rules.py file to start translating a subi instruction:

@assembler.instruction('subi #, #, #', 1)
def subi_instr(dest, op1, immediate):
  return pips.iformat(???)

You’ll need to fill in the parameters to pips.iformat to do the conversion. Refer to the opcode table and iformat documentation to as you work out how to encode this instruction.

One important detail to mention at this point is that Python is a whitespace-sensitive language. Instead of using curly braces or parentheses, Python uses indentation levels to determine scope and control flow. It’s important that you indent Python code consistently within one source file; do not mix tabs and spaces or you’ll get some strange errors.

Once you have encoded your PIPS subi instruction, write another rule in rules.py to convert a sub instruction to PIPS machine code.

Now that you can assemble programs that use sub and subi, add a microprogram for the subtraction opcode. Don’t forget to re-load the microprogram from microprogram.hex. Write a simple test program, assemble it, and use it to test all five of the instructions you can currently translate. Once you have this working, have the instructor or a mentor sign off on this part of the lab.

Part D: More ALU Operations

Now that you know how to add assembler rules and microprograms for basic ALU operations, add support for the following instructions:

nop (there are many possible encodings!)
and and andi
or and ori
nand and nandi
nor and nori
xor and xori
slt and slti
sltu and sltiu

The table below shows all of the available ALU operations. You will need to use these operations in combination with the $A_{inv}$ , $B_{inv}$ , and $C_{in}$ controls to implement each of the opcodes supported by PIPS.

op number	ALU Operation	Result
0	addition	$A + B$
1	and	$A \& B$
2	or	$A \\| B$
3	xor	$A \oplus B$
4	slt	for signed $A$ and $B$ : $A < B$
5	sltu	for unsigned $A$ and $B$ : $A < B$

{:.table.table-lines}

Caution: The slt and sltu operations work a bit differently than they did in the ALU you built earlier this semester. You should not invert either input when running an slt operation; just select the slt or sltu operation using the ALU’s $op$ input.

After completing the implementation of each instruction, add lines to a simple test program that verifies that these instructions work as expected. Once you finish this part of the lab you should have a single test program that shows all of these instructions working. You’ll need to add comments to your test program to explain what values should appear in each register so you can audit the results of your execution.

Have the instructor or a mentor sign off on your implementation once you have completed this part.

Part E: For those with extra time

If you complete parts A–D during lab you can move ahead to branches and jumps. It will be easiest to implement beq first, and add support for the others later. This will require use of the $zero$ output from the ALU, and will require that you alter some of the connections around the program counter so you can send in the destination of a branch instruction.

Addressing in PIPS is much simpler than for MIPS. All jumps and branches in PIPS go to an absolute 16-bit address, which is stored in the immediate field. One other important difference from MIPS is that PIPS will not unconditionally execute the instruction after a jump or branch; there is no branch delay slot.

The assembler has support for labels. If you write a label in your assembly and use its name as an immediate value it will be converted to the address of the first instruction after the label.

If you finish both beq and bne, you can move on to j, jr, and jal. The $link$ field is particularly important for implementation of the jal instruction; this field tells the datapath to discard the result of the ALU and instead pass the address of the next instruction to the $W_d$ input of the register file; this allows you to select $ra as the destination register and update it to point to the next instruction.

CC-BY-NC-SA This work is licensed under a Creative Commons Attribution NonCommercial ShareAlike 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/4.0/ or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.