CPSC 120 - Assignment #4

CPSC 120 -- Assignment #4

Simulating a Simple Computer
Due Friday, December 9, 2011 by 4 p.m.

For this assignment you will write a Java program that simulates the behavior of a simple computer. Basically your program will "load" a program into memory (the program will be in a simple machine language) then execute it by mimicking the fetch-execute cycle. You need to model the computer using a class. This is actually easier than it may sound --the computer has certain components and it performs just a few rather simple operations (the steps in the fetch-execute cycle plus steps to execute each instruction in its machine language). The following is a description of the simplified computer that you will model.

Simplified Computer

Earlier in the course we looked at the general idea of what the control unit in the CPU does: it fetches an instruction from memory, it decodes the instruction, and then it sends out signals to the appropriate units (such as the ALU or memory) to execute the instruction. It continues this cycle, called the fetch-execute cycle, forever (until the plug is pulled!). This description is correct but it begs a few questions: how does the control unit know where to find the instruction? where does it put it? how does it "decode" it? To answer these questions we need to add a bit to our description of the CPU. The CPU contains a small amount of memory, called registers, that it uses to hold data (including instructions) while using them. A register, called the program counter, contains the address in memory of the next instruction to be executed. At the fetch step in the fetch-execute cycle, the CPU looks up the address of the next instruction in the program counter then goes to that memory address to get the instruction. The instruction is brought into the CPU and stored in another register called the instruction register. The program counter is automatically incremented so it will contain the address of the next memory location (the instructions in the program will be stored in consecutive memory locations). The instruction is then sent to a logic circuit, called the decoder, that takes as input the machine code (the 0's and 1's) for the instruction and produces as output 0's and 1's that are control signals sent to the circuits involved in the execution of the instruction.

Hence, a more detailed view of the fetch-execute cycle is as follows:

Step 1 (Fetch) Get the next instruction (whose address is in the program counter) from main memory and put it in the instruction register.
Step 2 Increment the program counter (so it now contains the address of the next sequential memory location --- which should contain the next sequential istruction in the program).
Step 3 Decode the instruction and send signals (control signals) to the appropriate hardware units (such as the ALU or memory) to execute the instruction.
Step 4 Go back to step 1.

There are also some registers in the CPU used by the ALU when it performs its operations. Different computers have different numbers of registers for this purpose. In our simplified computer there is only one register, called the accumulator, that is used by the ALU. When the ALU performs an operation, such as add, one of the operands must be in the accumulator and the ALU leaves the result of the operation in the accumulator. This is illustrated in the modification of a handout from earlier in the course.

Simplified Machine Language

The machine language for the simplified computer has the seven instructions given in the table below. Each instruction has a 3-bit operation code and all instructions (except HALT) require one operand. In each case that operand is an address of a location in memory. The address will be 5-bits long so a complete machine language statement will be 8-bits (3 bits for the operation followed by 5 bits for the address). Each assembly language statement will consist of the mnemonic for the operation and then a symbolic address for the operand (an identifier that serves as a label for the memory location); the corresponding machine language statement will consist of the 3-bit code for the operation followed by the 5-bit address for the operand. The chart shows the operation code and the assembly language mnemonic for each instruction, and explains what the CPU does to execute the instruction.

Instruction Operation Code Assemply Mnemonic English Word Meaning (How it Works!)

001 (1) LDA Load Loads the value in memory at the specified address into the accumulator.

010 (2) STA Store Stores the current contents of the accumulator in memory at the specified address.

011 (3) ADD Add Adds the value at the specified memory address to the current contents of the accumulator. The result stays in the accumulator.

100 (4) SUB Subtract Subtracts the value at the specified memory address from the current contents of the accumulator. The result stays in the accumulator.

101 (5) JMP Jump Places the specified memory address in the program counter (so that the next instruction executed will be the one that is stored in memory at that address).

110 (6) JMZ Jump on Zero If the value currently in the accumulator is zero, the specified memory address is placed in the program counter; otherwise nothing is done. (Hence, if the accumulator currently contains zero, the next instruction executed will be the one stored in memory at the specified address; otherwise the next instruction executed will be the next sequential instruction in the program).

000 (0) HALT Halt Stops execution - the computer halts!

Instruction Operation Code	Assemply Mnemonic	English Word	Meaning (How it Works!)
001 (1)	LDA	Load	Loads the value in memory at the specified address into the accumulator.
010 (2)	STA	Store	Stores the current contents of the accumulator in memory at the specified address.
011 (3)	ADD	Add	Adds the value at the specified memory address to the current contents of the accumulator. The result stays in the accumulator.
100 (4)	SUB	Subtract	Subtracts the value at the specified memory address from the current contents of the accumulator. The result stays in the accumulator.
101 (5)	JMP	Jump	Places the specified memory address in the program counter (so that the next instruction executed will be the one that is stored in memory at that address).
110 (6)	JMZ	Jump on Zero	If the value currently in the accumulator is zero, the specified memory address is placed in the program counter; otherwise nothing is done. (Hence, if the accumulator currently contains zero, the next instruction executed will be the one stored in memory at the specified address; otherwise the next instruction executed will be the next sequential instruction in the program).
000 (0)	HALT	Halt	Stops execution - the computer halts!

Example #1: The following is a program to compute 5 + 3 written in the assembly language of our simplified computer. Num1, Num2, Start, and Answer are labels for memory locations. The semicolon indicates a comment (each line has a comment describing what it does).


	Num1:   5		;Data -- one of the operands
	Num2:   3		;Data -- the other operand
	Start:	LDA  Num1	;Load the first number into the accumulator
	        ADD  Num2	;Add the second number to it
	        STA  Answer	;Store the answer in memory
	        HALT		;Stop execution
	Answer: 0	        ;Data -- the memory location where the answer will be stored

The machine language version of the program depends on where in memory the program is loaded. In your program assume that programs are always loaded in memory beginning at address 0. If the program is loaded into memory beginning at address 0, then the contents of memory and the program counter will be as follows (note that the program counter contains the address of the first executable instruction -- the load instruction):


     Memory (binary)		      Memory (Decimal)
Address        Contents	         Address         Contents	
 00000         00000101        	    0		    005
 00001         00000011		    1		    003		
 00010	       00100000		    2		    100
 00011	       01100001		    3		    301
 00100	       01000110             4	            206
 00101         00000000		    5		    000
 00110	       00000000		    6	 	    000

Program Counter:  00010 (2)   (The address of the first instruction to execute is 2.)

Example #2: The following is an assembly language program to compute 5*3. Note that to do this in our simplified computer we must perform repeated additions since there is no hardware unit for multiplication.

   Num:     5	        ;Data --- the number we are adding 3 times
   Count:   3	        ;Data --- keeps count of the number of times 5 has been added to the sum
   Sum:     0	        ;Data --- contains the cumulative sum
   One:     1	        ;Data --- the number we must subtract from the count each iteration
   Start:   LDA Count	;Load the count into the accumulator
	    JMZ END	;If the count is 0, we are done so jump to a HALT instruction
	    SUB One	;Subtract one from the count
	    STA Count	;Store the updated count back in memory
	    LDA Sum	;Load the cumulative sum into the accumulator
	    ADD Num	;Add 5 to it
	    STA Sum	;Store the result in the cumulative sum
	    JMP Start  	;Jump back to the start location to see if another 5 needs to be added
    END:    HALT        ;If not, halt.

If this program is loaded into memory beginning at address 0, the contents of memory will be as follows:

              	
   Memory (binary)		    Memory (Decimal)
Address     Contents	    	 Address      	Contents	
 00000      00000101        	   0		  005
 00001      00000011		   1		  003	
 00010	    00000000		   2	          000
 00011	    00000001		   3		  001
 00100	    00100001		   4		  101
 00101	    11000010		   5   	          602
 00110	    10000011		   6	 	  403
 00111	    01000001		   7		  201
 01000	    00100010   		   8		  102
 01001	    01100000		   9		  300
 01010	    01000010		  10		  202
 01011	    10100100		  11		  504
 01100	    00000000		  12		  000
       
Program Counter:  00100 (4)

YOUR PROGRAM

Your program must contain:

A class to model the computer and its operation.
A class with the main method which will instantiate a computer object, call the appropriate method from the Computer class to load a program into memory, print the state of the computer after loading the program, then run the program, and finally print the state of the computer after running the program. If an error occurs at any point the main method should use the status returned to print a message explaining the error and not continue. In loading a program the only possible error will be that the program exceeded the amount of memory available. In running a program there are three possible errors:
1. An invalid address could be in the program counter. If this is the case print the current value in the program counter along with the error message.
2. An invalid opcode could be encountered in an instruction. If this is the case print the current contents of the instruction register along with the message.
3. An invalid address for an operand of an instruction. In this case print the contents of the instruction register along with the error message.

More Details about the Computer class

To design the class for the computer you need to think about the following:
- What are the attributes of a computer (the basic ones needed to execute programs)? Your answer determines the instance variables for the class.
- What are the behaviors of the computer (operations the computer performs)? Your answer determines the methods.
- After getting the main design think about other things such as constants and what should be public and what private.
We will work on the design in class. Details will be posted here.
"Loading" a program will involve reading in the machine code version of the program which includes the data and instructions in numeric form. We will use decimal rather than binary to represent the program - each instruction will be three decimal digits. The first digit represents the operation code, the second two digits are the address of the operand. The method should use a sentinel controlled loop that stops when a -1 is entered for the instruction. After reading all the instructions and storing them in memory (beginning location 0), the address of the first executable instruction in the program should be read in and stored in the program counter. Input, along with prompts, for the first example above would look similar to the following:
```
Enter the program (machine code) one line at a time. Enter -1 when you are through.
005
003
100
301
206
000
000
-1 

Enter the address of the first executable instruction.
2
```
The method that loads the program should return a status value indicating whether the load was successful. It is unsuccessful if the computer runs out of memory (the user exceeded the amount of memory available).
Methods in the computer class that "run" the program should check to make sure instructions are in the correct form. That is, in the appropriate methods the program should make sure that the opcode is valid and that addresses are valid.

Additional Requirements:

Your program must use good programming practices as described in previous assignments (such as meaningful identifiers, constant identifiers, white space, documentation, etc.).
Documentation for the Computer class must include header documentation at the beginning of the file that contains the name of the class, your name, the date, and a description of the class. Each method must have header documentation describing what the method does, what parameters are expected and what, if anything, the method returns. Use whitespace and borders on the documentation to make it easy to find each method!
Indent and align your code properly (emacs helps you do this - it automatically indents in most cases -- if a line isn't indented correctly go to it and press TAB OR select the whole program using CTRL-x, CTRL-p then use ALT-CTRL-\. If TAB doesn't make it indent correctly you probably have a syntax error).
See the following code conventions for more detail about formatting and documenting your program.
Warning: A program that doesn't compile receives almost no credit no matter how small the error.
Optional (Extra Credit): Make your program work for input that is in binary.

Submit to Inquire: A zip file containing your program.

Academic Integrity Reminder!!! Programming assignments are to be your own work. You may get help on the specifics of the assignment from no one except the instructor. You may not show your program to anyone or look at anyone else's program or share ideas with anyone about how to write the program.