CSE 140L Lab 4 - Design of a Mini Central Processing Unit

Spring 2009, Professor Cheng, TAs Thomas Weng, Renshen Wang, Chengmo Yang, Mingjing Chen

Due time: Demonstrate by 6/5, Report by end of 6/5.

Important! Please regularily check http://webboard.ucsd.edu for the latest updates and news regarding this lab. FAQs and announcements will be on the webboard, so check it often!

Objective
In this lab, we will build a mini CPU which consists of a program counter, an ALU(Arithmetic Logic Unit), an instruction decoder, three registers and a chunk of instruction memory. We use buses and various components from the Altera library to design the ALU, memory, registers and program counter, and use VHDL code to design the instruction decoder. The excution results will be displayed in the LED digits of your board. Unlike a real CPU, our mini CPU will consist of at most 15 instructions. However, because we have the branch instruction, programs can run more than 15 cycles (maybe much more if a program contains a loop).

Lab Details
Design a simple load/store type computer system that can perform addition, multiplication, comparison and branch. The system reads a 7-bit value from the read-only memory (ROM) block (3-bit instruction & 4-bit data). The memory block should be able to hold at least 16 instructions. There are three 4-bit registers R1, R2 and R3. Registers R1 and R2 store the data. Register R3 presents the results of the calculations. There is a 1-bit for comparison.

INPUT: Instructions can be read from files into the ROM. The instruction ROM will then contain the program instructions. Each individual instruction will be stored in order in the ROM using addresses. So, the first instruction will be stored at address 0, the second at address 1, and so on.

As mentioned before, our mini CPU is limited to 15 instructions. This is controlled from the program counter. The clock will be 1 Hz, similar to our previous labs. Every second then, the program counter increments 1. So the program counter goes 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F. At F, the program counter will stop, thus essentially shutting down our CPU. The program counter feeds into the instruction ROM, sending the current program cycle. The instruction ROM will take that number and output the corresponding instruction on the next clock rising edge. For example, if the current program counter cycle is 3, then the instruction ROM will output whatever instruction is stored in address 3.

OUTPUT: You need to output the 3 registers R1, R2, R3 and the program counter for the next instruction. Four numbers output to the 4 LED displays in hexadecimal format (assume the maximum number of instructions in all the test programs is no more than 16).

The detail specification of the instructions are shown in the following table. NOTE: all numbers are unsigned.

Something important to note is that for the mov instructions, we are outputting the value you are trying to move into register 1 or 2 on the same cycle you are moving it. But it is actually on the FOLLOWING clock cycle that the register file would actually be changed. Remember all that about how D flip flops are updated the following clock cycle?

We will provide you with one test program. It will consist of a set of instructions that can be read into ROM to execute on the machine you build. You will demonstrate this to us and include the results of the program in your report.

Example

Here is an example program with 8 instructions and what it will do on your mini CPU. Remember, your programs are limited to 15 instructions.

Here is the stored instructions and corresponding addresses in the ROM:

Address  Inst          Instruction Description
0        000 0000      Init registers
1        001 0001      Move 1 into R1
2        010 0010      Move 2 into R2
3        100 0000      Add R1 and R2, with result going into R3
4        011 0000      Mov R3 into R1
5        010 0100      Move 4 into R2
6        110 0000      Compare R1 and R2 and set compare flag if R2 >= R1
7        111 0011      Branch to address 3 if compare flag is true
8        000 0000      Init registers
	
Here is the actual runtime of our program, with corresponding program cycle:

PC       Inst          Output       Other changes
0        000 0000      000          R1, R2, and R3 are all cleared
1        001 0001      100          R1 now has value 1
2        010 0010      120          R2 now has value 2
3        100 0000      123          R3 now has value R1 + R2, which is 3      
4        011 0000      323          R1 now has value R3, which is 3
5        010 0100      343          R2 now has value 4
6        110 0000      343          Compare R1 with R2, which returns true since 4 > 3 
7        111 0011      343          Jump to instruction at address 3 because compare flag is true
3        100 0000      347          R3 now has value R1 + R2, which is 3 + 4 = 7
4        011 0000      747          R1 now has value R3, which is 7
5        010 0100      747          R2 now has value 4
6        110 0000      747          Compare R1 with R2, which returns false since 4 is not > 7 
7        111 0011      747          Go to instruction at next cycle, which is 8, since compare flag is false
8        000 0000      000          R1, R2, and R3 are all cleared

After this, the PC will count up to F before stopping. 
Your program will be doing nothing however since it ended at program counter 8. 
Notice how though it actually ran more than that, due to the branch. 

Guidelines and Tutorials

This lab will seem tough at first, as you are essentially designing a very simple CPU. Many of the concepts here are new. However, we will provide you guys with many of the modules and try to guide you guys as much as possible. In this lab, we will structure things for you so you do not have to come up with anything on your own (you will get to do that in 141L). Instead, you will learn how a basic CPU works, how things related to what you learned in CSE 30 (remember, these instructions are essentially assembly commands) and how data path and control path work. This lab will essentially be the culmination of all of the things you have learned in CSE 140 and CSE 140L up until now.

You will be designing logic with both schematic capture and VHDL. You will be designing a register file (which is sequential logic) and an ALU (which is combinational). You will be implementing both the data path (the components that handle data manipulation and storage) and the control path (the components than determine how to process the current instruction, and control the modules in the data path).

The first thing to do is to break down your CPU into its components. Remember, this was the point of all the emphesis on modules! We will provide some of the modules, and give you the framework for the rest. Here we will provide a description of the modules you will need to implement your mini-CPU.

Download Lab 4 Project Files

Program Counter - This module is connected to the clock and outputs the the current program cycle. Really, all it does is outputs the cycle number. So it will output 0 initially, then 1, then 2, and so on. We will use a 4-bit program counter, which means we can output up to F. Our particular program counter will automatically stop when it hits F (which is 1111). For branches however, our program counter will be set to whatever address that the branch tells the CPU to go to, if the comparison bit has been set to high. For example, if the instruction is "branch to address 0011", the CPU will first check the comparison bit. If it is high, the program counter will be set to 0011, and continue on from there. We will give this module to you.

Instruction ROM - This module connects to the program counter and outputs the instruction corresponding to the current program cycle. It basically is a table that stores an instruction at a given address. A program is a sequential list of instructions, and these instructions are stored in the instruction ROM in order. Thus, at address 0, the first instruction of a program is stored, and so on. The ROM reads in the current program cycle from the program counter, read the address that the program cycle points to (so if the current program cycle is 3, then the ROM will read address 3), and will output the corresponding instruction. Remember, in our machine, instructions are 7 bits long, with the first 3 bits being the instruction type, and the last 4 bits being data. Because our program counter stops at F, you can store up to 15 instructions in your instruction ROM. We will give this module to you as well.

Instruction Decoder (Control path) - This module decodes the instructions by reading in the first 3 bits of the instruction (which correspond to the instruction type), decoding it, and outputing all the control signals needed to control the rest of the CPU. This instruction decoder can be thought of as the brain of the CPU. For example, the add instruction is 100. The instruction decoder sees this, and based on the 100, will output the correct control signals to control the other modules, such as the register file, the ALU, etc. In the case of an add instruction, the instruction decoder will tell the register file that R1 and R2 need to be outputted and R3 needs to be written into, and will also tell the ALU that we need to add R1 and R2 together. You will implement the instruction dccoder using VHDL. We will give you guys the VHDL template for this.

Register File - This module contains the registers that will be used to store the data that we want to operate on. Remember back to your CSE 30 days. This register file is the same register file that you guys played with in your assembly programs. We want three 4-bit registers, R1, R2, and R3. Each register is made up of D flip flops. The register file will be the most complicated module in our mini CPU. It will receive as input the 4-bit output from the ALU and the last 4 bits of the acutal instruction (this corresponds to the 4-bit value of a mov instruction, in case the instruction was a mov command). It also has as inputs many control signals, such as which register to move the values to, or which value to use (either the ALU output for the case of add or the 4-bit instruction value for a mov). It outputs all three register values (yes, this means that every clock cycle, all three register values will be output. It also outputs the comparison result that it gets from the ALU. You will implement the register file module with schematic capture. See the previous class tutorial linked below for more help.

ALU (Datapath) - If the instruction decoder (control path) can be thought of the heart of the CPU, the ALU module is the heart. It takes in as inputs the two 4-bit values to be operated on, which are R1 and R2 (so this means our register file is directly connected to the ALU). It also has one control signal input, "operation select," which tells the ALU which operation to perform on the two values. It outputs the corresponding 4-bit result. For example, if R1 is 3, and R2 is 2, and the operation is add, then the output for the ALU will be 5. If the operation is multiply, then the output will be 6. Note that the output is also a 4-bit value, which means that it is possible for the result to overflow (quite easily with multiply). There is another output, a 1-bit comparison result, that is used for the compare instruction. Both these values are fed into the register file. This module should be the easiest to implement. There are only several ALU operations you need to support: addition, multiplication, and compare. You will implement this with schematic capture. See the previous class tutorial linked below for more help.

Some of you might be confused as to why the ALU outputs to the register file and the register file outputs into the ALU. Remember, these register files are D flip flops, which mean that we read on one cycle, but actually write on the next. So say we are in clock cycle 1. We can read the values from the register file, operate, and try to write back to the register file. But the register file will NOT be updated with the new value until the NEXT clock cycle. This was something that we tried to instill in you during lab 2, and now you see why! Knowing how these flip flops work is critical to understanding how a CPU works!

Clock module - Provides the 1 Hz signal that is used to synchronize and run our CPU. But because our board only supports synchronous ROM, and the counter is also synchronous, to avoid delay/pipelining we cheat a little on the clock source. The rising edge at the counter is half a second before the rising edge at the instruction ROM, so the instruction is fetched in one clock cycle. The modules and connections are provided to you in the template.



You are free to check out other resources to aid you. The textbook (specifically chapters 6.1-6.3 and chapter 7.1-7.3) also describes computer architecture pretty well.

Additional Tutorials and Hints

We will be providing additional tutorials and hints as needed in this section, so check back often. We will finalize this section by Monday depending on what is needed.

Megafunction Tutorial

ROM Programming Tutorial

Module Building Tutorial

Minimum Clock Cycle & Limiting Path Tutorial

Design Tips

1. Work in paper before you start working in Quartus II. In paper you can easily change the input/output ports, wire connections, or module names in several seconds using pencil and earser rather than using your mouse to drag and click here and there.

2. Work in the top-down fashion. First draw the global architecture and organize the modules (Register File, ALU, etc.). Think about what input/output ports are needed for each module and how wires can be connected. After it is done, you may proceed to draw schematic diagrams / write VHDL code for each module.

3. Use labels instead of real wire connections if you cannot arrange wires cleanly. If you want connect two ports by crossing the entire schematic diagram, you may consider to draw two short wires in the two ports respectively and give them the same name. Quartus II will automatically connect them.

4. Use buses! It is not only a mandatory requirement for this lab, but also greatly simplify your schematic diagrams.

5. Arrange the order of input/output ports of each module wisely. Assume you want to connect the output ports A, B, C, D, E in module 1 to the input ports A', B', C', D', E' in module 2. If the order of input ports in module 2 appear to be C', B', A', E', D', you would have a messy wire connection (you can use labels to avoid this issue, but you may want to connect directly if these two modules are adjacent.). Thus, when you create modules, try to keep the order of input/output ports consistent among tight-coupled modules. If you create modules using schematic diagrams, the order of ports depends on the relative positions of the ports in the diagrams (from top to bottom); if you write VHDL code, you can change the order in the entity definitions.

6. Debugging may be a suffering and tedious process. Probably you'll get some strange stuff displayed in LED in your first run. Although you are programming hardware instead of software this time, you can still adopt the following two tips learnt from your basic programming courses:

1) Start with simple cases. The test program is a bit long and complicated since we want to the function of your mini CPU thoroughly. You may create some simple cases yourself (maybe only consisting of one instruction) to test. This will help you to identify the bugs easily. E.g. if your machine works well for move1, move2, but runs crazily for add and multi, you know something wrong with your ALU.

2) "Print" intermediate results. When we debug a C program, we can use "printf" to print intermediate results to trace the code. Here, our "printf" statements are two display modules "DEC_7SEG". If you want to see any intermediate results of your design, e.g. contents of R1, R2, or computational results of ALU, connect them to the display modules. A limitation is that you cannot have more than two "printf" statements each time. But you can easily change and recompile your code to obtain more information you want.

Other Resources

For reference, here is a list of resources that you can refer to:

Single cycle CPU - A picture of a single cycle CPU, it is actually a bit more advanced than the one we are designing for this lab. But you can hopefully have an overview of how a CPU works. Our implementation will be a bit easier however, and somewhat different. You can also start to see how our simple mini CPU kind of looks like the real thing.

Microprocessor Design - A wikibook on microprocessor design, it isn't bad, but a bit incomplete from what I saw. You can quickly survey it for an overview of the components of a CPU. Not terribly useful, but a half decent online resource.

ALU - The Wikipedia entry for ALU, a decent description of what an ALU does. You can wiki other parts of the CPU too, and read about the other parts that make up a CPU. Some good ones to look for are: processor register, register file, computer architecture, CPU, ISA, control unit, etc.

Demonstration

You will need to demonstrate your project to a lab TA. Please look at the office hours for when we are available. Note, you can contact us if those times do not work, as we are happy to meet you outside those times too durning the evening. You can bring your laptop with your FPGA board to us and program the FPGA board in between demonstrations. For those of you without a laptop, we will try to set up machines in the lab that have Quartus II for your use, so you can bring your saved files on a flash drive or email and reprogram on the lab machines. If all looks good, we will give you thumbs up. If something doesn't work correctly, then please go back and fix it.

Demonstration Program
Please download the demo program which will be used in your demonstration. It consists of 16 instructions. The first 10 instructions are as follows and the rest are all 000 0000.

PC                Instruction
0                 000 0000
1                 001 0001
2                 010 0001
3                 100 0000
4                 011 0000
5                 010 0010
6                 101 0000
7                 010 0100
8                 110 0000
9                 111 0010

Report Instructions

You lab report should include:

- Title page, which contains Names and PID of students, due date, title of lab, and brief discription of each person's contribution.
- Schematic diagrams of the top-level design, ALU (datapath) and registers, must use BUS.
- VHDL code of the instruction decoder.
- For the test program, show the instructions inside ROM in a table including the index of instruction, the command of instruction, the 3-bit instruction, the 4-bit data and the excepted content of all the registers (R1, R2, R3, comparison). Note that some instructions may be repeated multiple times like a loop because of the branch instruction. Please show ALL the iterations of the loop.
- Describe the minimal clock cycle and the limiting path.
- What is the control path? Why is it called that? What is the data path? Why is it called that? How does the control path relate to the data path?
- Describe step by step what happens when the instruction that is being processed is Mov 1 into R1.
- Describe step by step what happens when the instruction is branch. The compare flag could be 0 or 1. Discuss both cases.
- Let's say you wanted to add a shift operation into your CPU. What would you have to do? Start from the instruction set (what would you have to do the instructions in order to support a shift operation?) and continue through the other modules.

Grading

30% of your grade will be from the demonstration, so this is an easy 30%. Another 40% will be in your logic schematics and timing diagrams. Easy points assuming you were able to demonstrate this for us. 30% will be in your answers to the questions.