Project 4: Processor Design

Please post any questions about this project to the class newsgroup [instructions]

your classmates probably have the same questions you do and
would benefit from seeing the TA's answer in a public forum!

Posted: 20-Mar-2006
Due: 10-Apr-2006, at NOON (two weeks not counting spring break)

In this project you will create a simple 8-bit CPU in Logisim.

Updates

WARNING: do not blindly copy the control signals shown in your textbook. More details can be found here.

Portions of the text which have been updated are shown in red.
23-Mar Changed 0xD0 to 0xE0
25-Mar Added logisim-ucb-2.jar, which raises input/output pin limit to 20 of each
25-Mar Swapped the polarity of the "write disable" pin on the RAM blocks
31-Mar Fixed typo on address of third byte of memory
31-Mar clarified that you do not need to preserve input memory locations
31-Mar added a note about connecting two software gates directly to each other
03-Apr there is now an assembler to make it easier to prepare test programs.
04-Apr Here are the instructions for using the assembler.
05-Apr The terms r1 and r2 have been replaced with ra and rb to reduce confusion.
05-Apr Clarified that the argument to beq is signed but the argument to j is unsigned (though the spec forces this to be the case it was not explicitly stated)

Logisim

WARNING: Logisim is much more stable than it was last semester, but it still does crash from time to time. Save your work often. Also, make a copy of your work from time to time in case a bug in logisim corrupts your saved file.

We have extended Logisim 2.0.4 with an additional type of gate for this project. You can start our extended version of Logisim with this command:

java -jar ~cs61c/projs/04/logisim-ucb-2.jar

Our extension to Logisim add a new gate type, called "software", which uses software code to simulate a piece of hardware that has not yet been designed. The source code for this new gate is in the .jar file if you are curious.

Simulation

When building large, complex systems, digital designers will often simulate individual components of the system (both in isolation and together), and then reimplement those components in hardware. Some technologies, like RDL let you test a system containing a mix of hardware and software components.

In this project you will complete the following design tasks:

  1. Create a high-level design for your CPU, showing the major functional blocks (ALU, register file, etc) and how they are connected.
  2. Implement a software simulation of each functional block.
  3. Verify your software-simulated system to make sure that it functions correctly.
  4. One by one, reimplement the blocks in "real" (non-software) gates. You should re-confirm that your system functions correctly after each block is reimplemented -- this way, if you encounter any bugs, you will always know which block caused them.
You'll probably notice that steps 1-2 are very similar to the last project.

The advantage of this design method is that task #1 is much easier than going directly to an all-hardware-gate design, so you're likely to get to a "correct" solution much more quickly. Furthermore, fixing bugs in the software stage is easier than fixing them once you've turned everything into gates.

Once you arrive at a "correct" solution, you can incrementally convert it into hardware, testing as you go to make sure that you never break the "correctness" of your CPU.

Important Distinction

It is very important to understand the distinction between these software components and the actual hardware gates you will convert them into. Unrestricted C code, like the kind you will be writing, cannot be turned into hardware -- you can't drop off a bunch of C code at an IC foundry or an FPGA vendor and expect to get back a CPU!

However, writing software in popular languages like C or Java is often an easy way of prototyping a system before undertaking the effort of a detailed hardware implementation.

ISA

You will be implementing a simple 8-bit processor with only two registers. Your processor will have separate instruction and data memory.

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

+-----+-----+-----+-----+-----+-----+-----+-----+
|  7  |  6  |  5  |  4  |  3  |  2  |  1  |  0  |
+-----+-----+-----+-----+-----+-----+-----+-----+----------------------+
|  0     0     0  |  0  |  0  | rd  | ra  | rb  |  or: $rd = $ra | $rb |
+-----+-----+-----+-----+-----+-----+-----+-----+----------------------+
|  0     0     0  |  0  |  1  | rd  | ra  | rb  | add: $rd = $ra + $rb |
+-----+-----+-----+-----+-----+-----+-----+-----+----------------------+
|  0     0     0  |  1  |  0  | rd  | ra  | rb  | and: $rd = $ra & $rb |
+-----+-----+-----+-----+-----+-----+-----+-----+----------------------+
|  0     0     0  |  1  |  1  | rd  | ra  | rb  | sub: $rd = $ra - $rb |
+-----+-----+-----+-----+-----+-----+-----+-----+----------------------+
|  0     0     1  | rd  |      immediate        |  lw: $rd = MEM[imm]  |
+-----+-----+-----+-----+-----+-----+-----+-----+----------------------+
|  0     1     0  | rd  |      immediate        |  sw: MEM[imm] = $rd  |
+-----+-----+-----+-----+-----+-----+-----+-----+----------------------+
|  0     1     1  | rd  |      immediate        | lui: $rd = imm << 4  |
+-----+-----+-----+-----+-----+-----+-----+-----+----------------------+
|  1     0     0  | rd  |      immediate        | ori: $rd = $rd | imm |
+-----+-----+-----+-----+-----+-----+-----+-----+----------------------+
|  1     0     1  |          address            | j                    |
+-----+-----+-----+-----+-----+-----+-----+-----+----------------------+
|  1     1     0  |          offset             | beq                  |
+-----+-----+-----+-----+-----+-----+-----+-----+----------------------+
The beq instruction's offset argument is a signed offset relative to the instruction following the current instruction, just as in MIPS. Specifically, if PC is the program counter, then beq does this:
   if $ra == $rb
   then
       PC = PC + 1 + offset
   else
       PC = PC + 1
The jump instruction also only changes the bottom 5 bits of the PC (since only that many can be specified in the address -- which is an unsigned number):
   PC = (PC & 0xE0) | address

Testing

You will need to write a program which multiplies the number in the first byte of memory (0x00) with the number in the second byte of memory (0x01) and stores the result in the third byte of memory (0x02). You do not need to handle signed numbers or overflow. You also do not need to preserve the values stored in the first two bytes of memory; if you find it convenient to change those values during the course of computing the result, you may do so.

The last instruction in your program should be a one-instruction infinite loop (an instruction which unconditionally jumps to itself -- an idiom for "HALT").

Assembler

Aaron Staley has contributed an assembler to make it easier to prepare test programs; you can find the source code for it here:
gcc -o proj4-assembler ~cs61c/projs/04/astaley-asm.c
You can find instructions on using the assembler here.

The "software" Extension

Underneath the "gates" menu, you will find a new type of gate called "software". You can instantiate this gate and adjust its three properties, inputs (how many inputs the gate has), outputs (how many outputs the gate has), and filename (the name of a .c file containing the gate's implementation.

Once you create a gate, you must set its filename property to the name of a .c source code file in the directory where you were when you typed the command to launch Logisim. Logisim will automatically compile your code and run it; when you modify the file (and save it), Logisim will notice and recompile your code.

Your C code must follow a very specific pattern; make a copy of ~cs61c/projs/04/template.c and:

  1. Change the definition of INPUTS and OUTPUTS to indicate how many inputs and output your function has. You must also manually change the pulldown menus for your software module in Logisim; this is not updated automatically.
  2. Add code in main() -- between the two comments -- to compute the outputs out[n] using the inputs in[n].

Logisim RAM Modules

You can change the contents of a logisim RAM module by choosing the "poke" tool (the little hand). Double click on the memory cell you want to change and type the new value in hexadecimal.

You can also save the contents of a RAM to a file and load it back by right-clicking on the RAM and using the "save" and "load" menu options. Once you've saved a RAM file, you can edit it with a text editor; each line is a one-byte hexadecimal value (don't mess with the header!)

To make a RAM work properly, you must:

  1. Connect the clock to the RAM (at the little triangle symbol on the bottom)
  2. Connect an address line to the "A" input
  3. Connect both the data input and output to the "D" terminal
  4. Connect a control line to "out"; this line should be "0" when the RAM is to be written (a better name for this pin would be "write disable" or "read enable")
This might seem a bit strange. The "D" terminal is both an input and an output. The behavior of the RAM block depends on what value you provide on the "out" pin. On the rising edge of the clock, Logisim checks the "out" pin and:
  • if it sees a "0", it samples the "A" and "D" inputs and writes the value it finds on "D" into the address specified by "A".
  • if it sees a "1", it samples the "A" input, fetches the value from that location in memory, and serves it up on the "D" pin as an output.
There's more detail on this in the Logisim manual page on RAMs. We've also included a sample circuit demonstrating how to use Logisim RAMs in both read-only and read-write mode.

Hints

You can use the Project->LoadLibrary menu option to load several of the Logisim built-in libraries. One of them (Arithmetic) includes adders, subtractors, and comparators that you will probably find useful.

Always leave open the terminal window in which you typed the command to start Logisim! This is important; any errors compiling or running your C code will be reported here, and we will need this output to diagnose any problems you might have. Furthermore, you can use printf() in your C code to display intermediate results; anything you pass to printf() will be displayed in the terminal window.

Logisim can build combinational circuits for you automatically from boolean equations; this is useful for generating control circuitry. See the "Combinational Analysis" option on the "Window" menu.

Hand-in

Your CPU must implement the full instruction set shown above.

"Readability" will be part of the grade. When the readers grade the design, without much effort, they should immediately see what a region of the circuit does. Your design should be sensibly organized into subcircuits; putting too many things in a single circuit makes it very difficult to understand.

You must hand in these files:
cpu-software.circ your initial circuit design using "software" gates
*.c C files required for cpu-software.circ
cpu.circ your completed CPU design where ALL "software" gates have been replaced
mult.hex the instruction-memory contents for the multiplier program from the "Testing" section of this assignment
You must hand in both cpu-software.circ and cpu.circ to recieve full credit for this assignment. You must not use any "software" gates in cpu.circ.

To turn in your assignment, type:

submit proj4

Note on connecting two software gates directly to each other

If you connect two software gates directly to each other, you will need to put a "buffer" on the wire between them facing in the direction in which data is supposed to flow. Make sure that the "bit width" of the buffer is set correctly.

Nearly all logisim gates other than the "software gate" require you to manually specify the bit width. I designed the software gate to auto-detect this to save you time, but if you connect two software gates to each other there's nothing to detect from. So you have to stick something in there to "force" the bitwidth. A buffer is just a gate that does nothing (copies its input to its output) but it forces both the bitwidth on the wire as well as the direction that data should flow.