abstract.
In this lab we designed a simple CPU based on Von Neuman's IAS computer. The major difference of our computer is that it uses seperate memories for instructions and data. Also, our computer does not have an IBR (Instruction Buffer Register) and it has 2-bit register for flags that are useful with conditional jumps and ALU operations. In order to implement our computer, we first developed a state machine that outlined our Fetch-Decode-Execute states. Then we coded it up in VHDL and finally, we implemented the design on an ALTERA board. As an extension we wrote an assembler for our computer.
architecture.
Figure 1. Architecure of the Simple Swarthmore CPU (taken from the lab instructions and slightly modified for visual purposes).
Figure 1 shows the architecture of the SSC - Simple Swarthmore CPU. Here are descriptions of some of the components:
Main Memory (RAM) : stores the data used by the CPU. The CPU can overwrite the data.
Instruction Memory (ROM) : contains the instructions for the CPU. In our implementation, the ROM is coded once and the CPU cannot overwrite the instructions, but it could be modified slightly to allow overwriting and coding on the fly.
PC (Program counter): points to the instruction that's being used. After each instruction, the PC gets incremented. Some instructions can change the PC counter value.
ACC (Accumulator): it holds the results of ALU operations. It also serves as a register for the ALU (ie, when the ADD instruction is called, the ALU takes one of the addends from memory (through the MBR) and the other addend from the accumulator.
MBR (Memory Buffer Register) : Holds instructions from RAM or data from ROM.
MAR (Memory Address Register) : Holds the address of the next piece of data (or memory) to be put on the MBR.
IR (Instruction Register) : the MBR sends the instruction to the IR, where it gets decoded. Usually the IR holds the opcode of the instruction.
MQ (Multiplier / Quotient) : this register is helpful in some arithmetic operations. For the
JUMP +M(X) instruction, next instruction is taken from memory if MQ holds a negative number
Flags : used to indicate an underflow or an overflow in arithmetic operations. these flags are used by the ALU and are useful for some instructions.
instruction set.
Group |
Opcode | Mnemonic |
opcode field |
address/data field |
Action |
A |
10 |
LOAD |
[0:1] |
[2:9] |
Load the value X into ACC. |
B |
00000 |
LOADM |
[0:4] |
[5:9] |
Load the contents of data memory at location X into the accumulator [ACC]. |
B |
00001 |
STORM |
[0:4] |
[5:9] |
Move the contents of ACC to data memory location X. |
B |
00010 |
JUMPM |
[0:4] |
[5:9] |
Take the next instruction from instruction memory location X. |
B |
00011 |
JUMP_MQ |
[0:4] |
[5:9] |
Take the next instruction from instruction memory location X, if the number in MQ is non-negative. |
B |
00100 |
JUMP_C |
[0:4] |
[5:9] |
Take the next instruction from instruction memory location X, if the carry flag is set. |
B |
00101 |
JUMP_OF |
[0:4] |
[5:9] |
Take the next instruction from instruction memory location X, if the overflow/underflow flag is set. |
B |
00110 |
ADD |
[0:4] |
[5:9] |
Add the contents of data memory location X to ACC; put the result in ACC. Set flags as appropriate for the events carry/shift out, and overflow/underflow. |
B |
00111 |
AND |
[0:4] |
[5:9] |
AND the contents of ACC and the contents of data memory location X. |
C |
01000 |
STOR_IO |
[0:4] |
unused |
Write the value in ACC to an I/O output port. |
C |
01001 |
LOAD_IO |
[0:4] |
unused |
Load a value from an I/O device (DIP switches) into the ACC. |
D |
110010 |
INC |
[0:5] |
unused |
Increment ACC, set flag for overflow/underflow. |
D |
110100 |
DEC |
[0:5] |
unused |
Decrement ACC, set flag for overflow/underflow. |
D |
110110 |
LSH |
[0:5] |
unused |
Shift the contents of ACC left by one bit, set flags for carry out. |
D |
111000 |
RSH |
[0:5] |
unused |
Shift the contents of ACC right by one bit set flags for carry out. |
D |
111010 |
INV |
[0:5] |
unused |
Invert the contents of ACC. |
D |
111100 |
SWAP |
[0:5] |
unused |
Swap the contents of MQ and ACC. |
D |
111110 |
LOAD_MMQ |
[0:5] |
unused |
Load the contents of memory at the location specified by the value in MQ into ACC. |
Table 1. Instruction set for the SSC with brief explanations. The instructions are divided into 4 main groups that follow similar execution steps in the computer. (This table is a combination of two tables from the lab instruction page. The mnemonics are changed.
As seen in Table 1, different instructions require different amounts of time to execute. For instance, the LOAD instruction can be executed in one step. All the computer has to do is put the data field in the ACC. However, for instructions like LOADM, it takes more cycles; first, the computer has to go to the memory address specified by the data field, then bring the data from memory and put it in the ACC. The hardest task in this lab was to figure out a way to build the CPU efficiently. Given the differences in the executions of instructions, we created a state machine that we later used to code up the CPU. Figure 2 shows the SSC state machine.
Figure 2. State Machine for the CPU: opcodes that follow similar FETCH-DECODE-EXECUTE steps are grouped together.
In order to show how the computer works, let us introduce a little program. We want to add four numbers and store their average in memory location 11. We also want two of the numbers to come from the instructions and two of the numbers to come from an I/O device. Here is the walktrough for the program
The opcodes will be in blue.
memory location |
instruction |
instruction details |
0 |
1000000010 |
LOAD 2 (load 2 into the ACC) |
1 |
0000100001 |
STORM 1 (move the value in ACC to mem location 1) |
2 |
1000000100 |
LOAD 4 (load 4 into the ACC) |
3 |
0000100010 |
STORM 2 (move the value in ACC to mem location 2) |
4 |
0100100000 |
LOAD_IO (load the value fromt the I/O device - let's assume this value is 6) |
5 |
0000100101 |
STORM 5 (move the value in ACC to mem location 5) |
6 |
0100101111 |
LOAD_IO (load the value fromt the I/O device - let's assume this value is 8) notice that the rightmost 5 bits don't have any significance. |
7 |
0000100111 |
STORM 7 (move the value in ACC to mem location 7) we don't really have to do this, but let's store the value in memory just in case... |
Table 2 a. First part of the instructions that put the values of the numbers we want to add in proper locations on memory.
at this point, we have stored all 4 numbers in memory, now we can start to add them together. At this point the data memory is shown in Table 2 b.
memory location |
data in binary |
data in decimal |
0 |
00000000 |
0 |
1 |
00000010 |
2 |
2 |
00000100 |
4 |
3 |
00000000 |
0 |
4 |
00000000 |
0 |
5 |
00000110 |
6 |
6 |
00000000 |
0 |
7 |
00001000 |
8 |
... |
00000000 |
0 |
Table 2 b. data memory after 7 instructions
memory location |
instruction |
instruction details |
8 |
0011000001 |
ADD 1 (add the value of the ACC to the value in memory location 1) --so, the value in the ACC was 8, and now we're adding 2 to it. after the execution of this instruction, the accumulator will hold 10. |
9 |
0011000010 |
ADD 2 (add the value of the ACC to the value in memory location 2) --final value in the ACC : 14 |
A |
0011000101 |
ADD 5 (add the value of the ACC to the value in memory location 5) --final value in the ACC : 20 |
B |
0000100011 |
STORM 3 (store the value of the sum in memory location 3. we don't have to do this, but let's save it just in case) |
C |
1110000000 |
RSH (shifting the values in the ACC by one; this is equivalent to division by 2) |
D |
1110000000 |
RSH (divide by two one more time. the resulting number is the sum of the four numbers divided by 4, namely it's the average of the 4 numbers) |
E |
0100011111 |
STOR_IO (puts the value in the ACC to an I/O port. |
Table 2 c. Second part of the instructions. In this part the four values are brought down and added in the ACCumulator.
After all instructions are executed, we can display the result using the I/O device. In our case, we displayed the result on an ALTERA board and showed numbers on seven-segment displays.
assembler.
Writing each instruction in binary is very hard. For example, if we want to store the value in the ACC to memory location 5, we have to write "0000100011". Clearly this is very time consuming to write, hard to understand and to walk through. Also, decoding the code in binary is a huge pain. So what we did to make life easier for ourselves was to write an assembler that took simple commands and changed it to binary instructions that the computer understands. We wrote an assembler in PHP (yes, it's a little weird) to do this. We used PHP because, with some change to the code, we can create a webpage where anyone can write code for the CPU and convert their code into binary instructions easily. You can see the code for the assembler here.
Right now, the assembler will only work using a text file that's in the same folder as the assembler. The binary code is written in a .MIF (memory initialization file) that VHDL can program onto the ALTERA board.
So, let's write the above program and let the assembler convert it to binary code.
LOAD 2
STORM 1
LOAD 4
STORM 2
LOAD_IO
STORM 5
LOAD_IO
STORM 7
ADD 1
ADD 2
ADD 5
STORM 3
RSH
RSH
STOR_IO
Here's the output from the assembler. Notice that, all commands are almost identical (the opcodes are identical) except the assembler always puts zeros for unused bits.
DEPTH = 32;
WIDTH = 10;
ADDRESS_RADIX = HEX;
DATA_RADIX = BIN;
CONTENT
BEGIN
0 : 1000000010 ;
1 : 0000100001 ;
2 : 1000000100 ;
3 : 0000100010 ;
4 : 0100100000 ;
5 : 0000100101 ;
6 : 0100100000 ;
7 : 0000100111 ;
8 : 0011000001 ;
9 : 0011000010 ;
a : 0011000101 ;
b : 0000100011 ;
c : 1110000000 ;
d : 1110000000 ;
e : 0100000000 ;
f : 0000000000 ;
10 : 0000000000 ;
11 : 0000000000 ;
12 : 0000000000 ;
13 : 0000000000 ;
14 : 0000000000 ;
15 : 0000000000 ;
16 : 0000000000 ;
17 : 0000000000 ;
18 : 0000000000 ;
19 : 0000000000 ;
1a : 0000000000 ;
1b : 0000000000 ;
1c : 0000000000 ;
1d : 0000000000 ;
1e : 0000000000 ;
1f : 0000000000 ;
END;
testing.
Figure 3 shows how the different components were connected to each other.
Figure 3. Components of the SSC.
We tested out circuit using the waveform editor in MAX II+.
Figure 4. Waveform editor showing how the program progresses in the CPU. [click on image to see a larger version]
Figure 5. Detail from the waveform editor showing different stages. [click on image to see a larger version]
what we learned.
We learned a lot about the computer architecture and how data flow is done through different sections of the CPU. We also learned how each part of the CPU (ALU, ACC, MBR... etc) is useful and why we need them.
We improved out VHDL skills as well as out PHP skills.
One of the most important lessons to take out of this lab is to know what you want to do and what you will do EXTREMELY WELL. The state machine is extremely important and slight mistakes in the state machine cause a lot of headache. |