# Lab: Build a Datapath, part 1

Assigned
Wednesday, Oct 31, 2018
Due
Tuesday, Nov 6, 2018 by 10:30pm

## 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:

1. The $r1$ field in the instruction indicates which register should be read from the register file. This should be connected to $R_{a0}$.
2. 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.
3. The other ALU input should be the immediate value from the instruction (remember this is an addi instruction).
4. 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.
5. 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).
6. The $r0$ field in the instruction indicates which register should be written by the instruction. Connect this to $W_a$ in the register file.
7. 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: