CPSC 120: Principles of Computer Science
Lab 3: xComputer
A COMPUTER IS BASICALLY a large circuit that can store and execute machine language programs. It does this in a process called the fetch-and-execute cycle. That is, it performs the actions: fetch an instruction from memory, then execute that instruction. And it repeats these basic actions over and over. It does this mechanically, simply because of the way it is physically constructed. In this lab, you will look at a simulated model computer called xComputer that should help you understand machine language and the fetch-and-execute cycle. Modern computers are much more complicated than xComputer, and every type of computer does things a bit differently. But xComputer captures the essence of what goes on inside every computer. It simulates only the two main working components of a computer, the Main Memory and CPU, but these components are similar in complexity and operation to those in the first personal computers that were introduced in the 1970s.
The xComputer model computer is discussed in Chapter 3 of the text, and it would be useful for you to read the assigned sections of that chapter before doing the lab. It is especially important that you read Section 3.1.2, which discusses the registers of xComputer and how they are used in the fetch-and-execute cycle.
This lab uses an applet that is also named xComputer. To run this program, go to the "cpsc120" folder (you should have a shortcut for it), open the "Lab 3" folder, and double-click the icon named "Run xComputer".
You can also run the applet off the Web by clicking the following button:
Tour of xComputer
The xComputer applet shows the contents of xComputer's memory in a region at the right edge of its window. There is a scroll bar that you can use to scroll through the 1024 memory locations. The memory really contains binary numbers, but it's not easy for people to read binary numbers. So you have the option to view the contents of the memory in other forms. You can select the view using the pop-up menu above the memory display. (One of the options in this menu, "Control Wires," is not really a view of memory at all. I will discuss it later.) Of course, each of these views is only an interpretation of the bits that are actually stored in memory.
The lower right region of the applet shows the xComputer's eight registers. Each register really holds a binary number, but, again, you have the choice to see different interpretations of the bits that are stored in the registers. This is controlled by the pop-up menu that is initially set to "Default display."
Above the registers is a set of buttons, menus, and input boxes that you can use to interact with the xComputer. Most important are the "Run", "Step", and "Cycle" buttons. The "Run" button essentially turns on the computer, telling it to initiate its fetch-and-execute cycle. The "Cycle" button makes the computer do one complete fetch-and-execute cycle. The "Step" button makes it do a single step in the cycle. (Remember: The computer executes programs by running the fetch-and-execute cycle over and over. Each cycle executes one machine language instruction, and each cycle is itself performed as a series of small steps.)
To be executed, a program and any data that it uses must be stored in memory. This means we need some way of getting the information into memory. The hard way to do this is to use the input boxes labeled "addr" and "data." You can use them to enter numbers into memory one number at a time. Type the address where you want to store the number in the "addr" box. Type the number that you want to store in the "data" box. Then press return, or click the "Data to Memory" box. The number will be copied into the specified address in memory.
There has to be an easier way to enter an entire program (and its data if any) into memory. The xComputer applet allows you to write programs in assembly language. Assembly language is almost the same as machine language, except that instructions are written as words and base-10 numbers instead of as binary numbers. The applet will translate the assembly language into machine language and store it in the computer's memory. Assembly language programs can be saved in files, and later they can be loaded back into the applet.
If you run the applet as directed above, it loads several sample assembly language programs. To get at these programs, you can use the pop-up menu at the very top of the applet. Select the program named "SimpleCounter.txt" from this pop-up menu. The applet screen will change to show you the program. The program is in an edit box, so you can edit it if you want. (You have to do this in one of the exercises.) Below the program is a button named "Translate." When you click this, the computer will translate the assembly language program into machine language, put it into the computer's memory, and go back to the main "Computer screen." Try it. You will see the program in the computer's memory. If you want to see the contents of the memory interpreted as assembly language instructions, change the pop-up menu above the memory to "Instructions."
Once the program is in memory, you can run it. Click the "Run" button to start the computer running. This program will run forever if you let it. The program adds one to the number in location 12 over and over. If you watch location number 12, you will see the number changing as the program runs. You can also watch how the registers change. Below the run button, you will see a pop-up menu that you can use to control the speed at which the program runs. The "Run" program changes to a "Stop" button while the program is running. Click the "Stop" button to stop the program.
When a program starts, the number in the Program Counter register (PC) tells the computer where to start. It should contain the address of the first instruction in the program. Usually, to run the program from the beginning, you want to start with a 0 in the PC. The button named "Set PC = 0" can be used to put a 0 into the PC. If you want to run a program from the beginning again, first click this button.
Assembly language instructions are specified by short code words such as "STO", "ADD-C", and "HLT". Most instructions require a number to use as data. For example, "ADD-C 17" is an instruction that means "Add 17 to the number in the Accumulator register (and put the result back into the accumulator)." Some instructions do not include data. For example, "HLT" is an instruction that means "Halt the computer," a command which does not require any data. A complete list of assembly language instructions can be found in the textbook, but here are the ones that are used in this lab. In this list, the number "17" can be replaced with any number from 0 to 1023.
Assembly Language Instructions LOD-C 17 Put the actual number 17 into the Accumulator register (replacing whatever was there before). LOD 17 Copy the number from memory location 17 into the Accumulator register (replacing whatever was there before). STO 17 Copy the number from the Accumulator register into memory location 17 (replacing the previous contents of that memory location). ADD-C 17 Add the actual number 17 to the number currently in the Accumulator (and put the result back in the Accumulator). ADD 17 Add the number in memory location 17 to the number currently in the Accumulator (and put the result back in the Accumulator). SUB-C 17 Subtract the actual number 17 from the number currently in the Accumulator (and put the result back in the Accumulator). SUB 17 Subtract the number in memory location 17 from the number currently in the Accumulator (and put the result back in the Accumulator). INC Add 1 to the number in the Accumulator (and put the result back into the accumulator). DEC Subtract 1 from the number in the Accumulator (and put the result back into the accumulator). JMP 17 Jump to location 17. That is, the next instruction executed will be the one in memory location 17, and execution will continue from there. JMZ 17 Jump to location 17, if the number in the accumulator is zero. If the number in the accumulator is not zero, then this instruction has no effect. JMN 17 Jump to location 17, if the number in the accumulator is negative (when interpreted as a base-ten number). If the number in the accumulator is positive or is zero, then this instruction has no effect. HLT Halt -- that is, stop the clock, which also stops the computer from running.
Assembly language programs can contain comments. A comment is some text meant for human readers. Comments are completely ignored by the computer. In the xComputer assembly language, a semicolon (;) on any line marks the beginning of a comment. The computer ignores everything starting from the semicolon up to the end of the line. (Note that multi-line comments require a semicolon on each line.)
Programs often need data to work on. You can include data in your assembly language programs. On any line of the program, you can put a number instead of an instruction. The number will simply be copied into a memory location. (In fact, of course, assembly language instructions are also translated into binary numbers in the end. As far as the computer is concerned, "JMP 2" and "12290" are just alternative ways of writing the same binary number!)
Here is an assembly language program that adds 42 to 105 and stores the answer in location 10. The comments are there for you, but are not part of the program:LOD-C 42 ; Put the number 42 into the accumulator ADD-C 105 ; Add 105 to the number in the accumulator STO 10 ; Store the number in the accumulator in location 10 HLT ; Stop the computer
Now, suppose that we want to add two numbers, but that the numbers are going to be stored as data in the computer's memory along with the program. This can be done with the program:LOD 4 ; Copy the number in location 3 into the AC ADD 5 ; Add the number from location 4 to the AC STO 10 ; Store the answer in memory location 10 HLT ; Stop the computer 209 ; This is location 4, so this is one of the numbers. 52 ; This is location 5, so this is the other number.
One thing you can do with the xComputer is use it to help you understand the fetch-and-execute cycle. You can use it to step through the cycle, one little step at a time, and see what happens in each step. Try this with the command "LOD-C 17". Put this command in memory location number 0. Click the button "Set PC=0" to make sure that there is a 0 in the Program Counter register. Then, use the "Step" button to go through the fetch-and-execute cycle one step at a time. Here is what you will see:
- Click "Step" and COUNT becomes 1, indicating the first step in the fetch-and-execute cycle. This step is "Load-ADDR-from-PC", so the number (zero) that was in the PC is copied into the Address register.
- Click "Step" and COUNT becomes 2. This step is "Load-IR-from-Memory", and you should see that the content of memory location 0 (the LOD-C instruction) is copied into the Instruction register. (It was the 0 in ADDR that told the memory to use location 0.)
- Click "Step" and COUNT becomes 3. This step is "Increment-PC", so the number in the PC goes up by one. (This prepares the PC for the next fetch-and-execute cycle, where the next machine language instruction in the program would ordinarily be executed.)
- Click "Step" and COUNT becomes 4. This step is "Load-AC-from-IR", so the data portion of the Instruction register (17) is copied into the Accumulator. (This step actually carries out the intent of the LOD-C 17 instruction.)
- Click "Step" and COUNT becomes 5. This step is "Set-COUNT-to-Zero." This changes the value in the COUNT register back to 0, so you only see the 5 in the COUNT register very briefly. This marks the end of one fetch-and-execute cycle and the beginning of the next.
If you were to continue pressing "Step", the computer would go on to execute the next instruction, from memory location 1.
Steps such as "Load-IR-from-Memory" and "Increment-PC" are actually names of control wires. The step is accomplished by turning the control wire on (and turning it off at the end of the step). You can get the computer to show you the name of the control wires that are turned on in each step. Change the pop-up menu above the Memory display to read "Control Wires." The memory display will be replaced by a list of all the control wires in the xComputer. As a program runs, the wires that are turned on will be shown in red. You might want to try stepping through the execution of LOD-C 17 while watching the control wires. You will need to do something like this for some of the exercises.
Labels (and More Programs)
When the data part of an assembly language instruction is the address of a location in memory, it can be very tedious to get the number right. You can end up counting memory locations to figure out the right number to use. And if you modify a program by adding an instruction, you might have to change the numbers because other things have to be moved down one location in memory to make room for the new instruction. To avoid these problems, you can use labels in assembly language programs. A label is a name for a memory location. Instead of using the numerical address of the location, you can use the name. For example, if "adr" is a label for memory location 8, then saying "LOD adr" is the same as saying "LOD 8", and "JMP adr" is the same as saying "JMP 8". The computer will figure out what the actual number should be.
To create a label, just add the name, followed by a colon, to one of the lines in a program. For example, the linestart: LOD-C 0
creates the label start as a name for the location that contains the LOD-C 0 command. Elsewhere in the program, you could say "JMP start" to jump to this location.
Labels can be used for data values as well as for instructions. Suppose that we want a program that adds two numbers that are stored in memory, and we want to use labels to refer to the numbers. Here is a program that does this.LOD num1 ; Copy the first number into the AC ADD num2 ; Add the second number to the AC STO 10 ; Put the answer in location 10 HLT ; Halt the computer num1: 209 ; The first number num2: 52 ; The second number
For a more interesting example, look at the sample program MultiplyByAdding.txt. This program can find the product of two numbers, N1 and N2. It does this by adding N1 to itself N2 times. The numbers are specified using labels at the end of the program. When the program ends, the answer will be in the memory location labeled Ans. Try running the program. As it runs, watch memory locations 16, 17, and 18. These are the locations in which Ans, N1, and N2 are actually stored. The preceding memory location, number 15, is used by the program to keep track of how may times it has added N1 to itself.
This program contains a loop, that is a sequence of instructions that is repeated over and over. Loops are made using jump instructions. A JMP instruction at the end of the loop tells the computer to "jump" back to the beginning of the loop. It then repeats the loop, arrives back at the JMP instruction, jumps back to the start of the loop, and so on. If there were no way to end this, the program would continue forever (until the power is turned off). This is called an infinite loop. The sample program SimpleCounter.txt contains an infinite loop.
Usually, some way is needed to break out of the loop. This can be done with the conditional jump instructions JMZ and JMN. The instruction "JMZ 17" means "jump to location 17, but only if the number in the AC is zero." Similarly, "JMN 17" means "jump to location 17, but only if the number in the AC is negative." If the condition is not true, then the JMZ instruction has no effect. A loop with a JMZ or JMN instruction might execute ten times before the condition becomes true. Then, when the condition becomes true on the eleventh execution, the conditional jump instruction will "break" the loop by jumping to a location outside the loop. Here is the loop from the multiplication program. You should try to understand how it works:Loop: Lod Count ; If Count is equal to N2, then N1 has Sub N2 ; been added to itself N2 times, and Jmz Done ; the program is done. Lod Count ; Add 1 to Count Inc Sto Count Lod Ans ; Ans contains N1 + N1 + ...; Add in Add N1 ; another copy of N1 to Ans Sto Ans Jmp Loop ; Return to start of loop Done: Hlt
We say that the computer's memory stores binary numbers, but even that is not physically accurate. The memory is a bunch of switches that can be on or off. We interpret the on/off patterns as zeros and ones -- but it doesn't really look like zeros and ones. Suppose that we could see each "on" switch as a white dot and each "off" switch as a black dot. The pattern of black and white dots would represent the pattern of data in the memory. We could see the entire pattern at once and we could watch how the pattern changes as the computer computes. You can do this with xComputer. In a way, this is the most accurate view of "computation" that you can get.
To see this view, set the pop-up menu above the Memory display to "Graphics". You will see a white rectangle that represents all of memory, with black and white pixels to represent zeros and ones.
Two of the sample programs are meant to be used with this graphics display: CountAndStore.txt and PowersOfThree.txt. Select CountAndStore.txt from the pop-up menu and hit the "Translate" button. Set the Memory display to "Graphics." Also set the speed of the computer to "Fastest Speed." Now, "Run" the program. This program stores the numbers 1, 2, 3, 4, 5, ... in consecutive memory locations. It fills up the entire memory. You can watch this happen and see the pattern of dots (zeros and ones) created by these numbers.
Do the same thing with the sample program PowersOfThree.txt. This is a fairly complicated program (and not one you should try to understand). The program itself fills up a fair portion of memory at the top of the graphics display. The program will run indefinitely, computing with numbers that it stores in two other regions of memory. You can also see flickering dots right at the end of the program itself. These are labeled data locations used by the program. It's interesting to watch this at full speed and know that this is what computers do. This is computation.
The following exercises are due next Friday, September 27. For these exercises, you are not required to save any files on the computer. For the exercises that ask you to write a program, you should simply type the program or write it out by hand. Note that the material covered on this lab will be included in the test on Wednesday, September 25. So, even though the exercises are not due until after the test, you need to work on them beforehand.
Exercise 1: Answer the following short questions:
- (a) When you set the Memory display to "Instructions", you will see that most of the memory locations contain "ADD 0". Why is that?
- (b) Use the xComputer applet to find the binary number (machine language) translation of the instruction "ADD-C 42". What is the answer, and how did you find it?
- (c) In the "Graphics" memory display, exactly how many black/white dots are there? Why?
- (d) How would you modify the MultiplyByAdding program so that it multiplies 107 times 12 instead of multiplying 13 times 7?
Exercise 2: Consider the fetch-and-execute cycle for the instruction "JMP 59". Use the "Step" button in the xComputer applet to look at all the individual steps in this cycle, as was explained earlier in this lab for the instruction "LOD-C 17". Only one step in the execution of JMP 59 is different from the execution of LOD-C 17. Which step is different? In this step, what control wire is turned on during the execution of JMP 59? Explain carefully the purpose of turning on that control wire. What does it accomplish? How does it fulfill the purpose of the JMP instruction?
Exercise 3: Use the "Step" button in the xComputer applet to look at all the individual steps in the execution of the instruction "LOD 17". How does it differ from the execution of "LOD-C 17"? Carefully explain the purpose of steps number 4 and 5 in the execution of the LOD instruction.
Exercise 4: Write an assembly language program that will compute the value of103 - 27 + 125 - 79
and will store the answer in memory location 25. The program should halt after computing the answer. Turn in a listing of the instructions in your program.
Exercise 5: The sample program SimpleCounter.txt starts counting at zero and keeps counting forever. Add some instructions to this program that will make the computer halt when the count reaches 15. Right now, the program has an infinite loop. You need to add a JMZ instruction that will break out of the loop, and jump to a HLT instruction, if the count is 15. (You can use the loop in the MultiplyByAdding program as a model.) Turn in a listing of the instructions in your program, amd explain briefly how it works.
Exercise 6: Computation is the mechanical manipulation of symbols. A computer is a machine. Hopefully, this lab and the previous lab have given you some insight into the nature of computation and have helped you see how a machine can follow instructions and do computations. Write a short essay (about a page) that discusses what you have learned in these labs about computers and computing. What have you learned from specific exercises such as seeing circuits that add and store numbers, watching the fetch and execute cycle, and (most particularly) seeing the "dancing bits" in the computer's memory?
--David Eck (firstname.lastname@example.org), Fall 2002