Due 11:59pm Friday, November 17th, 2006

TA of record: Dave J.
Post any questions or comments to the newsgroup.

Overview

In this project you will be using Logisim to create an 8-bit single cycle CPU.

ISA

You will be implementing a simple 8-bit processor with only two registers ($r0 and $r1). It will have separate data and instruction memory.

The instruction encoding is given below. You can determine which instruction a byte encodes by looking at the opcode (the top three bits).

7 6 5 4 3 2 1 0
0 rd rx funct See R-type Instructions
1 rd immediate disp: DISP[imm] = $rd
2 rd immediate lui: $rd = imm << 4
3 rd immediate ori: $rd = $rd | imm
4 rd immediate lw: $rd = MEM[imm]
5 rd immediate sw: MEM[imm] = $rd
6 address jump
7 offset beq

R-Type Instructions
funct meaning
0 or: $rd = $rd | $rx
1 xor: $rd = $rd ^ $rx
2 and: $rd = $rd & $rx
3 add: $rd = $rd + $rx
4 srl: $rd = $rx >> 1
5 sra: $rd = $rx / 2
6 not: $rd = ~$rx
7 neg: $rd = -1*$rx

srl vs. sra

Just as in MIPS, srl and sra differ here by sign extension. Since sra stands for shift right arithmetic, it considers it's operand a two's complement signed number and sign extends appropriately. srl considers it's operand a set of separate logical values, and zero extends instead.

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

immediate Fields

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

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

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

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.

Testing

Once you've implemented your CPU, you can test it's correctness by writing programs to run on it! In particular, you will be required to create two programs to test the functionality of your processor. Here is a simple program that can be run as a basic sanity check. halt.hex loads the same immediate (via lui/ori) into both registers and then branch equals -1. It is extremely important that your lui and ori instructions work, since they allow for automated testing. It is recommended that you make small programs to test each of your other instructions individually.

Write a program that multiplies the first two bytes of memory (MEM[0] and MEM[1]) and stores their product in MEM[2]. The last instruction of your program must be a halt (an instruction that jumps or branches to itself indefinitely). Feel free to clobber the original arguments. Save the ROM image in a file "mult.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".

Assembler

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.

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

lui $r0, 3
ori $r0, 15
lui $r1, 3
ori $r1, 15
beq -1

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

Hints and Comments

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

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.

Jumps in the Assembler

If you are calculating your jump addresses off of line numbers, keep in mind that the first instruction in your program is at address 0, but the first line is often labelled as line 1. So remember to subtract 1 off of all your addresses or insert a nop at the beginning just before you run the assembler.

Questions to Think About

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?
4) How can implement subtraction using existing instructions?

RISC vs. CISC

Although this project's ISA is inspired by MIPS, it is arguable whether or not it is truly a RISC architecture. Some of the RISC-ier features include the commutivity of the R-type instructions. By limiting them to being commutative or unary (operations that take a single argument), our instruction set can cram in an extra four ALU based instructions. Non-commutative instructions such as subtraction can be executed as combination of a few simpler instructions. On the other hand, the disp instruction can't really be used in combination with other instructions to do something more interesting. It is a unitasker in the sense that it can only be used to display values with this specific architecture. We'll find out later that MIPS overloads the load and store instructions for I/O using a scheme called "memory mapped I/O".

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) The instructions don't exactly follow the RIJ model. Instead the instructions are categorized by the number of registers encoded by the instruction. Accordingly, the instructions fall into a model more like RIS (register, immediate, and special case types).
3) Even though your CPU is an 8-bit CPU, it can only access 16 bytes of data memory (Why? Think about difference #1).
4) 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.
5) The disp instruction borders on being a CISC style instruction.

Miscellaneous Requirements

You may use any built-in logisim library circuit components in implementing your CPU.

You must have your instruction ROM module and data RAM module visible from the main circuit of your Logisim project. You must include an array at least four seven segment displays in the main circuit as well. Feel free to add additional seven segment displays if it does not clutter your CPU.

Use the label tool and disconnected wires to organize your CPU. In particular label the control, datapath, and display sections.

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) Use your program from part 2 to write a program that displays a location in memory as a decimal value! (be careful about jumps, being a linker can be tough).
4) Write something crazy that we haven't thought of.

Submission

You must submit the following files:
cpu.circ
mult.hex
octal.hex

From the directory containing your project files, submit using the following command:
% submit proj3