Project 3: Processor Design

2007Sp CS61C
TA: Alex Kronrod
Due Friday, April 6, 2007 @ 11:59:59pm
Last updated: 4/6

Updates


Introduction

Now that you are done with implementing an ALU, let's implement a simple 8-bit single cycle CPU. This means, we will have 8-bit instructions and 8-bit byte addressing. As with HW6, you will be using Logisim to complete this project.


Getting Started

Copy the contents of ~cs61c/proj/03 to your home directory.

   $ mkdir ~/proj
   $ cp -r ~cs61c/proj/03 ~/proj3
This will copy in cpu.circ, the Logisim circuit file where you will be implementing your processor, and converter.circ, a file that will help you implement a particular instruction in this project.


Assignment -- Part 1: the ISA

In cpu.circ, you will be implementing a simple 8-bit processor with four 8-bit data registers. This processor will also have separate instruction and data memories.

Similar to the MIPS ISA presented in lecture, there will be three different instruction types: R, I, and J-type. The R-type instruction format seen in lecture has 3 fields to specify the source, target, and destination registers. Unfortunately, with 8 bits we don't have enough bits to specify all the information if we want to maximize functionality. As a result, we will permanently designate two registers to have special functionality -- one always acting as a source ($rs), and the other always acting as the destination ($rd). The remaining two registers ($r0 and $r1) will behave as normal data registers that you have been accustomed to. Naturally, there will be special instructions to move information between the data registers ($r0 and $r1) and the special registers ($rs and $rd). Note: In total, there are 4 registers!

The primary instruction encoding is given below. You can determine which instruction a byte encodes by looking at the opcode (bits 5-7). Please note that $rx registers below refer only to registers $r0 and $r1.

$rx value Register name
0 $r0
1 $r1

7654 3210 NameMeaning (RTL)Notes
0 rx funct see R-type Instructions Section
1 rx immediate disp DISP[imm] = R[$rx] see Display Instruction
2 rx immediate lui R[$rd] = imm << 4
3 rx immediate ori R[$rd] = R[$rx] | imm
4 rx immediate lw R[$rd] = MEM[R[$rx] + imm]
5 rx immediate sw MEM[R[$rx]+imm] = R[$rs]
6 address jump PC = (PC & 0xE0) | address see J-type instruction section
7 offset beq if R[$r0]==R[$r1], PC = PC+1+offset see J-type instruction section

R-type instructions

The following table lists the various R-type instructions there are based on the funct field.

Funct Name Meaning (RTL) Notes
0 add R[$rd] = R[$rs] + R[$rx]  
1 sub R[$rd] = R[$rs] - R[$rx]  
2 or R[$rd] = R[$rs] | R[$rx] bitwise OR
3 and R[$rd] = R[$rs] & R[$rx] bitwise AND
4 sll R[$rd] = R[$rs] << R[$rx] shift left logical, zero extend from the right
5 slt R[$rd] = R[$rs] < R[$rx] set $rd to 1 if $rs < $rx, else 0; treat values as signed
6 srl R[$rd] = R[$rs] >>> R[$rx] shift right logical, zero extend from the left
7 sra R[$rd] = R[$rs] >> R[$rx] shift right arithmetic, sign extend from the left
8 mxd R[$rx] = R[$rd] move value into register $rx from $rd
9 msx R[$rs] = R[$rx] move value into register $rs from $rx
10 msd R[$rs] = R[$rd] move value into $rs from $rd
11 not R[$rd] = ~R[$rx] bitwise NOT
12 neg R[$rd] = -1*R[$rx] negate
13 jr PC = R[$rx] jump register
14-15 "reserved for future use" You can implement anything you want with these.

You've already built an ALU that should support the first 8 R-type instructions. Let us now add 6 more instructions. Note that you actually don't have to modify your ALU in order to implement these new instructions. Try to think of clever ways to use the ALU in order to get the wanted functionality.

I-type instructions

All immediate fields are treated as unsigned numbers and are zero-extended accordingly.

see the behavior of
I-type instructions in the table above (opcode 1-5).

J-type instructions

jump

The jump instruction's argument is a pseudoabsolute address, just as in MIPS. address is an unsigned number representing the lower five bits of the next instruction to be executed. The upper three bits are taken from the current PC.

    PC = (PC & 0xe0) | address  

beq

The beq instruction's argument is a signed offset relative to the next instruction to be executed normally, also as in MIPS. beq can be represented as the following:

    if $r0 == $r1
      PC = PC + 1 + offset
    else
      PC = PC + 1
Note: offset is two's-complement!

Assignment -- Part 2: Testing

I am now done, I think... but how do I know it works? Write programs using the instructions you have to test the correctness of your CPU's functionality. For now, here is a simple program halt.hex that does nothing, it halts (infinite loop) by jumping to itself. Note that this only works when $r0 == $r1

You are required to write two programs:

  • Fibonacci Numbers have been recurring throughout the semester - so why not do it now? Write a program that computes the first N Fibannocci numbers and stores ith number in memory at address i (MEM(i)=Fib[i]) Let Fib[0]=0, Fib[1]=1, Fib[2]=1, etc. In the beginning, write code that initializes $r0 to N, specifying how many numbers you want to compute. Use the value 10 for N for the program that you submit. The last instruction must be a halt (an instruction that jumps or branches to itself indefinitely). Save the ROM image in a file "fib.hex"

  • Write a program that displays the first byte of memory in octal (base 8). For example, if the first byte were 0x9f, the seven segment displays would read 0237. Again, you may clobber any memory values you like and your program must end with a halt. Save the ROM image in a file "octal.hex".


    Sample problems:
  • Here is a file outlining a process of creating a program: Creating MAL instructions, converting to TAL, figuring out jumps, and writing machine code. alldisp_steps.txt
  • Here's the hex file for sample program above: alldisp.hex
  • Another sample code given in .s format below, you'll need to use the assembler to get the .hex file=).

    Assembler

  • If you are doing wrap-around for immediates for the DISP instruction, the assembler's "nop" was wrong. Please download the new version of the assembler - which uses "beq 0" as a nop.

    We've provided a simple assembler to make writing your programs easier. You should try writing a few by hand before using this, mainly because it's good practice and makes you feel cooler. We may also ask you to do it by hand when grading your project.

    The assembler can be downloaded here. The assembler takes files of the following form:

    lui 0 #comments are allowed, this is a better halt program
    mxd $r0
    ori $r0, 15
    mxd $r0
    mxd $r1
    beq -1
    lw  1($r1) #never executed, but example of how you can use lw
    lw  $r1 1  #this is also allowed.
    

    Anywhere a register is required, it must be either $r0 or $r1. Labels are not supported and immediates are decimal and not checked for being within bounds. Any blank lines, commented lines, or malformed instructions will correspond to a nop in the executable. The assembler can be invoked using the following UNIX command:

    % perl asm.pl < input.s > output.hex
    See sample .s files we have provided:
    clever_counter.s - An 8 bit counter in hex (never halts)
    alldisp.s - Uses all four display modules.

    NOTE: If you find any bugs with the assembler, please let me know by e-mail or on the newsgroup.

    Logisim

    It is strongly recommended that you download and run Logisim on your local machine while developing your CPU. As you've probably discovered in lab, Logisim can quickly overwhelm the instructional machines. Though Logisim is generally stable compared to earlier semesters, it is still recommended that you save and backup your .circ files early and often. The official version of Logisim we will be using for evaluation is v2.1.5.

    RAM Modules

    Logisim RAM modules can be found in the built-in memory library. To add the library to your project, select "Project/Load Library/Built-in Library..." and select the Memory module.

    The best way to learn how these work is simply to play with them. In any case, here's a little bit of info to help you get started. The Logisim help page on RAM modules can be found here, but is not terribly helpful. "A" chooses which address will be accessed (if any). "sel" essentially determines whether or not the RAM module is active (if "sel" is low, "D" is undefined). The clock input provides synchronization for memory writes. "out" determines whether or not memory is being read or written. If "out" is high, then "D" will be driven with the contents of memory at address "A". "clr" will instantly set all contents of memory to 0 if high. "D" acts as both data in and data out for this module. This means that you must use a controlled buffer on the input of "D" to prevent conflicts between data being driven in and the contents of memory. The "poke" tool can be used to modify the contents of the module.

    You will be using a Logisim ROM module for your instruction memory. It is a much simplified version of a RAM module Both RAM and ROM modules can also be loaded from files using "right-click/Load Image..."

    Note: ROM's are READ only, while with RAM's you can either read or write (but you can't do both at the same time).
    You want to be able to read the code from the instruction memory, but you want to be able to read from and write to the data memory!

    The Display Instruction

    If you check the tattoo on your left arm, you'll be reminded that every computer has five parts: control, datapath, memory, input, and output devices. Accordingly, your project must include an array of four seven-segment displays for output. It should look something like the array shown below:

    The disp instruction assigns a register's value to the immth seven-segment display. This value should be held until the next time a disp instruction replaces that display index. You may ignore or wrap immediates beyond the range of the display you've implemented. We've provided a converter library to make seven-segment displays easier to deal with. It can be downloaded here and included via the "Load Library/Logisim Library" menu option. See the examples section to get a better idea of how to incorporate these into your project. Any single digit hexadecimal value 0-f will be displayed as you'd expect. 0xff is displayed as a blank display (no segments highlighted). All other inputs will result in a '?' being displayed.


    Hints and Comments

    This section contains hints and comments to help you get started and foster some academic debate. Feel free to skip this section for now and come back after you've gotten your hands dirty.

    General suggestions

  • Modularize all your subcircuits. Try reusing circuits you have already built. For example, think of a way to create an "extended ALU" that adds the new functionality, which is just a wrapper around your already implemented ALU.
  • Test all your subcircuits separately, preferably right when you finish building it.
  • When designing your datapath, think of the design we've learned in class. Having the basic layout of your datapath may make things easier to reason about and to implement.
  • Build the control first. Then implement datapath, testing as you add new elements. For example. first test that your control is working. Then add the register file and test that you can access and write correct registers. Then the ALU... etc.

  • Create MAL instructions to help you write code. Then convert them to TAL instructions. Pay attention to which registers you must use when you're converting to TAL instructions.

    Testing for Equality

    It is possible to test for equality using already required ALU components (without adding a subtractor or comparator). Think about truth tables and boolean algebra.

    Display Logic

    You might want to make some sort of specialized register file for keeping track of current display values. The desired functionality is about halfway between a register file and a RAM module.

    Logisim's Combination Analysis Feature

    Logisim offers some functionality for automating circuit implementation given a truth table, or vice versa. Though not disallowed (enforcing such a requirement is impractical), use of this feature is discouraged. Remember that you will not be allowed a laptop running Logisim on the final.

    Key Differences From MIPS

    1) The zero register isn't special. $r0 is just a regular register like $r1.
    2) Data memory and instruction memory are distinct. This is what we tell you in MIPS as well, but when we talk about caching we'll find out they still live in the same address space.
    3) BEQ instruction is I-type in MIPS, but is J-type in the spec given

    Things to Ponder

    1. How can we swap the two registers without going to memory?
    2. What instructions act as nops?
    3. What are the different ways of halting a program?

    Miscellaneous Requirements


    Extra for Experts

    Once you've got your CPU up and running, give these a try:

    1. Write an assembler that can handle labels, long branches and jumps, and pseudo instructions. Feel free to define your own register and/or memory conventions to make this work (declare MEM[15] as assembler reserved, etc.)
    2. Try writing a program that divides MEM[0] by MEM[1] and stores the quotient in MEM[2] and the remainder in MEM[3].
    3. There are two R-type funct values that have not been used. Play around with these two - implement something new.
    4. Write something crazy that we haven't thought of.

    Submission

    From the directory containing cpu.circ and the files that will be specified in part 2 of this project, submit your project using the following command:
  • Make sure to have all .circ files you created for this project as well as all files that you loaded as libraries be put into the directory and submit them as well!
      % submit proj3