Lab: Build a Datapath, part IV

Assigned

• December 3, 2020

Due

• December 8, 2020 by 11:59pm Grinnell time

Overview

In this continuation, we will add support for the memory operations of the PIPS instruction set. In addition, we will use memory-mapped I/O to connect a terminal to your datapath so your programs can actually produce output. Your work will continue to augment and update your existing datapath.circ, microprogram.hex, and rules.py files from the previous labs.

Although it may be possible to proceed without having finished the previous portions of the lab, you will be better positioned for this work if you do. Please undertake completion of parts I–III before working on this lab.

Grading Guidelines

Your datapath will ultimately be assessed by a test suite, and the final grade mostly determined by how many tests your datapath passes.

In addition to verifying circuit and program correctness, other elements of style will also be considered.

• For circuits, wires, gates, and pins should be laid out in a fashion that facilitates comprehension.
• For programs, clarity, organization, and overall efficiency with respect to the number of instructions required to complete any given task. In part that means
  • ensuring comments clearly indicate the purpose of each instruction (or short set of instructions), rather than the literal interpretation, AND
  • nicely aligning the various labels, fields, and comments in your code.

Part A: Memory Accesses

The first major piece we’ll add to our datapath in this lab is support for standard memory operations. PIPS is a 16-bit architecture, so a word in this architecture is a 16-bit value. In addition to loading and storing words, we will also want to support loading and storing individual bytes of data.

The datapath provided with the first lab includes a memory controller and a RAM element at the far right edge of the datapath. You should not make any direct connections to the RAM element; the memory controller takes care of some ugly details that make it possible to support writes to individual bytes.

As with the MIPS datapath, we’ll use the output from the ALU as the address we are loading from or storing to. For a write operation, you will need to pass the data you would like to write to the $W_d$ field, and turn on the $W_e$ input. If you are writing or reading a byte, send a zero to the bottom control line; otherwise send a one to this control line. For load operations, the read data comes out on the $R_d$ port. This value is always 16 bits, even if you are just loading a byte.

Just as you did with the register file, you will need to invert the clock input to the memory controller. This avoids the unpredictable behavior we could see when writing a value just as the write enable input to the memory controller changes.

You will need to add control lines from your microprogram ROM output that tell memory whether to enable writes and whether your operation should access a byte or a full word. Another control line should indicate whether the register file write data comes from the ALU result or the memory $R_d$ port. With these added lines you should be able to implement lw, lb, sw, and sb. Remember that lw and lb use the value of the register specified in the $r1$ field as the base address, add an immediate value to this address, and then store the loaded value into the register specified in field $r0$.

The sw and sb instructions do not update any registers, so these instructions will use the value of the register specified in the $r0$ field as the value to store; you should already have support for reading this register from the beq and bne instructions. You will need to pass the register file output $R_{d1}$ on to the memory controller to store this value. For the lw and lb instructions, you will need to add one final control line that takes the output of memory and passes it back to the register file instead of the ALU result.

Once your datapath supports load and store instructions you should implement assembler rules for these instructions and test them. At this point you should be able to write procedures that use the stack, although you will need to explicitly load a stack starting address into the $sp register at the start of your program. To do this, just insert li $sp, 0xf800 before the main body of your program. This sets up your stack at the address 0xf800, and the stack can grow downward. The choice of address is largely arbitrary, although we’re leaving space in the upper addresses for some extra features we’ll add later. Because we control the entire processor, it is safe to statically assign memory locations like this.

Test your datapath by writing an interesting procedure that uses conditional branches and stack operations (e.g., your remainder and gcd procedures from Lab 6 should be able to run with minimal modifications for PIPS, depending on the pseudoinstructions you may have used). Call the procedure from at least two different points and verify that it does what you expect. You may assume that PIPS calling conventions work much like MIPS calling conventions, except we have fewer registers.

Please have the instructor or a mentor sign off on this part before moving on. You should be prepared to show your well-documented microprogram, your test program (whose comments also indicate the expected behavior), and assembler rules. You will demonstrate the assembly of your program, load it, and run it.

Part B: Terminal Output

Logisim has two useful features we will add to the PIPS datapath: command-line invocation, and terminal output. The terminal component makes it possible for your circuit to produce text output, and command-line invocation allows you to run PIPS programs on your datapath from the Linux command line, rather than inside of Logisim. We’ll need to make two small changes to the datapath to support these features.

Adding a halt output

You can run Logisim circuits from the command line, but Logisim needs to know when they’ve finished so the program will terminate. To indicate that a circuit has terminated, you must add an output with the name “halt” and set this output to 1. We’ll just choose an arbitrary program counter value, say 0xff00, that indicates when a program has terminated, and then jump to this location when we want the program to stop.

Add a Comparator from Logisim’s Arithmetic components, and compare the current program counter value to the constant 0xff00. If the two are equal, turn on the halt pin. This will work when your circuit is run from the terminal, but it won’t stop the circuit when you run it inside of Logisim. To make both work, invert the value passed to “halt” and connect this to the enable pin of the program counter registers. This will allow the program counter to update until the program counter reaches 0xff00.

Write a simple program named halt_test.s that performs a few simple operations and then jumps to 0xff00. Assemble this program and load it into your datapath inside of Logisim. Select “Ticks Enabled” from the “Simulation” menu to start running the program. You may want to increase the tick frequency in this menu as well. Verify that your program runs, jumps to 0xff00, and then the program counter stops changing even though the clock continues to tick.

Once that works, save your circuit and open a new terminal window. To run the same program, type the following shell command from your datapath directory:

$ java -jar /home/curtsinger/shared/logisim.jar -tty halt -load programs/halt_test.hex datapath.circ

This should run your circuit briefly, print “halted due to halt pin”, and then terminate. If the command does not terminate you may have named the “halt” output incorrectly. The instructor or mentor can help you troubleshoot at this point.

Connecting to a terminal

Real MIPS microprocessors incorporate the standard registers detailed in our textbook, but they also add some additional features; some of them use predefined pointer names like TRISA, LATA, and PORTA. These values are locations in memory, but writes or reads to those locations control special peripheral devices (electronic connector pins on the CPU’s host board) instead of just accessing memory. This is a common technique for adding peripherals to architectures without modifying the instruction set to support extra operations or registers. We will use this trick to add a terminal to our datapath so PIPS programs can produce text output.

First, select a “TTY” component from the “Input/Output” category in Logisim and add it to your datapath below the memory controller. Connect this terminal to an inverted clock signal, just as you did with the register file and memory controller. The terminal has two other inputs: a character to write, and an enable pin. We will connect the terminal’s data input to the data being written to memory, but only enable writes when the PIPS processor is writing to a special address 0xff10.

Add a comparator to compare the write address to the constant 0xff10. If the two values are equal and the write enable pin for memory is on, pass a 1 to the enable input on the bottom of the TTY device. Now select a Bit Extender from Logisim’s Wiring category. We’ll use this to truncate the 16-bit data value down to 7 bits, which is what the terminal expects. Connect the $W_d$ value to the input of the bit extender and connect the extender’s output to the terminal’s data input.

Now you should have a working terminal. The program below should print “Hello” to the terminal, using the raw ASCII encoding of the characters in the message. This program uses assembler constants, which allows you to use named values so you can avoid sprinkling magic numbers throughout your code.

# Print "Hello" to the PIPS terminal
# Charlie Curtsinger
.constant TERMINAL 0xff10
.constant HALT     0xff00

nop # First instruction does not execute
main:
  li $s0, TERMINAL
  li $t0, 0x48   # Load ASCII value for 'H'
  sb $t0, 0($s0) # Print 'H'
  li $t0, 0x65   # Load ASCII value for 'e'
  sb $t0, 0($s0) # Print 'e'
  li $t0, 0x6c   # Load ASCII value for 'l'
  sb $t0, 0($s0) # Print 'l'
  sb $t0, 0($s0) # Print 'l'
  li $t0, 0x6f   # Load ASCII value for 'o'
  sb $t0, 0($s0) # Print 'o'
  li $t0, 0x0a   # Load ASCII value for newline
  sb $t0, 0($s0) # Print newline
  j  HALT        # Stop execution

If you save this program to programs/print_hello.s, you should be able to assemble and run it from the command line:

$ ./asm programs/print_hello.s
$ java -jar /home/curtsinger/shared/logisim.jar -tty tty -load programs/print_hello.hex datapath.circ
Hello
$ 

Writing an Interesting Program

You now have a datapath that can perform basic arithmetic operations, run loops and conditionals, access memory, and produce output. We can now write interesting programs for this datapath. Your task for this part of the lab is to write a program that computes the first 15 numbers in the Fibonacci sequence and prints them to the terminal. You will need to implement a print_number procedure that takes an integer and displays it in decimal (base ten) form. You will also need to implement a procedure that computes the Fibonacci sequence using a recursive implementation, which requires that you use the stack. While I expect you can come up with an implementation of the Fibonacci sequence on your own, this C implementation of a number printing procedure may be helpful:

void
print_decimal_number (int n) {
  if (n == 0) {
    putchar ('0');
  } else {
    int digit = n % 10;
    if (n > digit) {
      print_decimal_number (n / 10);
    }
    putchar ('0' + digit);
  }
} // print_decimal_number

You may find it useful to refer to an ASCII table, such as the one at https://ascii.cl.

Notice that this procedure uses both remainder and division; these are not operations that PIPS supports natively, so you will need to implement remainder and quotient as procedures in your solution. Make sure you use the equivalent of MIPS calling conventions in your implementation.

When you are finished, I should be able to run your code with the following commands inside your datapath directory:

$ ./asm programs/fibonacci.s
$ java -jar /home/curtsinger/shared/logisim.jar -tty tty -load programs/fibonacci.hex datapath.circ
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610

Package to Submit

When you are finished, please create an archive of your entire datapath directory using the following command, starting from inside the datapath directory:

$ cd ..
$ tar cvzf datapath-iv.tar.gz datapath

This should create a datapath-iv.tar.gz file one directory up from your datapath. Submit this archive to complete the lab.