UPDATE! Extended Deadline!

Due Friday, April 18th, 2008 at 11:59pm

TAs: Ben Sussman and Brian Zimmer
Post any questions or comments to the newsgroup.

Overview

In this project you will be using Logisim to create an 16-bit single cycle CPU. Please read this document CAREFULLY as there is a lot of new stuff to cover and a lot of your questions are no doubt answered within.

Instruction Set Architecture (ISA)

You will be implementing a simple 16-bit processor with four registers ($r0 through $r3). It will have separate data and instruction memory.

One important thing to note: Because of the limitations of Logisim and to make things simpler for you guys we have to use HALF WORD (16 bit) addressed memory! This is UNLIKE MIPS where the instructions are WORDS (32 bits) while the memory is BYTE addressed (8 bits). I hope this transition is not confusing.

The instruction encoding is given below. You can determine which instruction a half-word encodes by looking at the opcode (the top four bits, which are bits 15-12). Note how we did not fill up the following table with 16 instructions as is possible with 4 bits of opcode. The same goes for the wasted upper bits of the func field. This was to make the project a bit shorter and easier!

15-12 11 10 9 8 7 6 5 4 3 2 1 0
0 rs rt rd party bits! funct See R-type Instructions
1 rs rt immediate-u disp: DISP[imm] = $rs
2 rs rt immediate-u lui: $rt = imm << 8
3 rs rt immediate-u ori: $rt = $rs | imm
4 rs rt immediate-s addi: $rt = $rs + imm
5 rs rt immediate-u andi: $rt = $rs & imm
6 rs rt immediate-s lw: $rt = MEM[$rs + imm]
7 rs rt immediate-s sw: MEM[$rs+imm] = $rt
8 jump address jump
9 rs rt offset beq
10 rs rt offset bne

R-Type Instructions
funct meaning
0 or: $rd = $rs | $rt
1 and: $rd = $rs & $rt
2 add: $rd = $rs + $rt
3 sub: $rd = $rs - $rt
4 sllv: $rd = $rs << $rt
5 srlv: $rd = $rs >> $rt
6 srav: $rd = $rs >> $rt
7 slt: $rd = ($rs < $rt) ? 1 : 0

NOTE:The order of the above opcodes is DIFFERENT than the order in your ALU from hw6. This is because we wanted an instruction of all zeros (0x0000) to be a NOP, and thus we placed or as the instruction with a func value of zero.

srl vs. sra

Just as in MIPS, srl and sra differ here soley 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. This means that if there there is a one in the sign bit, which is the most significant bit (bit 15 in our CPU), then it fills in ones in the most significant bits as it shifts the number over, and zeros otherwise. 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 12 bits of the next instruction to be executed. The upper four bits are taken from the current PC. We do NOT do any concatenation of zeroes to the bottom or our address like we would in MIPS. This is because our CPU will be HALF-WORD addressed, so every possible address holds a valid 16 bit instruction.

PC = (PC & 0xF000) | address

beq/bne

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

The bne instruction differs only by the test in the if statement: replace the == with !=

immediate Fields

Some immediate fields are treated as unsigned numbers and are thus zero-extended accordingly, while others are treated as signed numbers and are thus sign-extended accordingly. To tell which instruction does which refer to the instruction chart above near the top of the page:

immediate-s stands for a SIGNED immediate.
immediate-u stands for a UNSIGNED immediate.

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 (this is up for debate, however I remember it being just as buggy), 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.6.

If you are having trouble with logisim: REBOOT! Don't waste your time chasing a bug that is not your fault. However, if rebooting doesn't solve the problem, it is very likely that the bug is a flaw in your code! Please post to the newsgroup any crazy bugs that you find and we will investigate. But keep in mind, Logisim seems to be working better than in previous semesters on Ben and Brian's home machines.

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 AND Overflow LEDs

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 EITHER array shown below:

OR

Note the above image has blank values. This will likely not be possible if you implement the displays in the "more awesome" way, so do not be concerned.

Option 1:

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, because our registers are 16 bits wide, just drop the upper 8 bits).

UPDATE: This part is causing a lot of confusion, so here is an update: If you create your Displays as specified above, you will be IGNORING the upper 8 bits of the register which you are displaying! That way, the logic we created for you (which only takes in 8 bits) will work with your registers. YOU DO NOT HAVE TO IMPLEMENT DISPLAY THIS WAY HOWEVER!!

Option 2:

Instead, you can implement multiple ARRAYS of 4 seven-segment-displays to display the ENTIRE contents of a 16 bit register at once. To do this, you can have (minimum) two sets of 4 Seven-Segment- Displays where each set is associated with one index. This significantly more awesome way (big thanks to Paul Pearce and others for suggesting it) is preferred by the staff, and should hopefully make more sense to you.

All other inputs will result in a '?' being displayed. You need at least 4 total seven-segment displays and at least 2 total valid immediates for the disp instruction. However your CPU will be SIGNIFICANTLY more awesome with more displays so if you finish early, that's a good place to start some sweet improvements.

You also need to have TWO LED units which light up to signify the two kinds of overflow. They should go on if and ONLY if They should be viewiable in your main circuit.

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 half-words 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 lower nine bits of the first half-word of memory in octal (base 8). For example, if the first half-word were 0x829f, the seven segment displays would read 237. 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 This is Nathan Kallus' v2.0 of the Assembler. For the craziest assembler of the all, look no further than ultimate badass Gilbert Chou for creating the epic v3.0 of the assembler available here. This assembler should work with labels, comments and hex for unsigned immediates. It may be super buggy however!

The assembler takes files of the following form:

lui $r0, 85 
ori $r0, 68 
lui $r1, 85 
ori $r1, 68 
beq $r0, $r1, -1

Anywhere a register is required, it must be either $r0, $r1, $r2 or $r3. 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. Commas are optional but the $ is not. 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.

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) What instructions (and with what arguments) can act as nops?
2) What are the different ways of halting a program?
3) How can we implement Multiplication? Division?

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) Memory is addressed every 16 bits, allowing which we will call a HALF-WORD. We could have simply redefined WORD to mean 16 bit however we felt this would have been too confusing, so we decided to call it HALF-WORD addressing. Unlike MIPS, every memory address holds a valid 16 bit HALF-WORD that could be an instruction or an entire integer.
3) Data memory and instruction memory are distinct. This is what we tell you in MIPS as well, but when we talk about cacheing we'll find out they actually live in the same address space.
4) 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 to organize your CPU. In particular label the control, datapath, and display sections, but it can also be useful to label specific busses and wires. It could make debugging a lot easier!

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