Using instructional simulation in the computing curriculum.

Abstract

Instructional simulations allow a student to engage in an activity that would otherwise be impractical or impossible, such as controlling a nuclear power plant or changing the effects of gravity. This paper presents a simulation tool that illustrates how the central processing unit (CPU) and memory work together in modern computer. The tool provides students with a small but complete instruction set making the simulation a fully functioning computing environment. The system's graphical user interface provides multiple viewing perspectives (e.g., digital, binary, and mnemonic). Students are able to write complete working programs and monitor the inner workings of the CPU during execution. This paper concludes with results from classroom usage along with implications and future work.

Introduction

Simulations provide powerful learning opportunities if they are properly designed, implemented and integrated into a curriculum (Maurer, 1998). A well-conceived simulation allows students to explore a concept by providing a virtual "hands on" environment that would otherwise be unavailable. The simulation provides a learning opportunity that lecture alone cannot achieve (Gredler, 1996). For an instructional simulation to be effective, however, it must be well conceived and carefully implemented (Lajoie, 2000). In this paper we present just such a simulation tool for introducing students to inner workings of the computer's brain, the Central Processing Unit (CPU).

The simulation described in this paper is called CPUSIM. It is based on the Little Man Computer (LMC) paradigm, a frequently used conceptualization of the CPU. The Little Man paradigm is a simplified but powerful model of a computer architecture containing all the components of modern computers: memory, a central processing unit, and input/output capability. A diagram of the LMC appears in Figure 1 (from Englander, 2000).

The LMC model uses common analogies to represent important concepts. A computer's memory holds data and instructions. The LMC analogy for memory is a series of mailboxes. The computer's Arithmetic Logic Unit (ALU) performs operations such as addition, subtraction and multiplication. The LMC analogy for the ALU is a calculator. Input/Output (I/O) activity refers to communication between the computer and its users, its storage devices, other computers (via a network) or the outside world. The LMC analogy for I/O activity is communications through an IN basket and an OUT basket. A program counter is a special purpose storage location containing the address of the next instruction to be executed. The LMC analogy for the program counter is a simple counter.

The LMC model uses base 10 (decimal) numbers, making the data easier for students to understand. The mailboxes and calculator each contain three decimal digits. The first digit is the operation code (op code) which determines what kind of action the computer should take, such as add, jump, load, or store. The other two digits indicate the appropriate mailbox address associated with that instruction. For example, the instruction 512 would be interpreted as op code 5 (LOAD) and address 12, meaning the value in mailbox 12 would be copied into the calculator. See issue's website <http://rapidintellect.com/AEQweb/fal02.htm>

The LMC model is valuable as a conceptual tool for introducing students to important computer architecture concepts. However, the analogy between LMC and real computers is not perfect. There are two problematic areas:

1) The decimal representation is intuitive for human discussion, but it creates a problem when mapping to the machine's binary equivalent. One decimal digit op codes supports 10 instructions, and two decimal digit addresses support 100 memory locations. Mapping these to binary requires 4 bit op codes (yielding 16 possible op codes, 6 of which go unused) and 7 bit addresses (yielding 128 memory locations, 28 of which go unused). Also, the 11 total required bits is itself an unusual number (one and three-eights bytes).

2) One of the major goals of the Little Man analogy is to reveal the inner workings of the CPU to the student. However, Little Man actions (e.g., "loading" and "storing") are left as an analogy. Students interested in a deeper understanding of CPU behavior would benefit from exposure to microinstructions and register-level transactions within the CPU.

Despite deviations from reality, the LMC paradigm is proven as a powerful conceptual tool. Furthermore, the simulation described below addresses these concerns by supporting a binary design and presenting register level microinstructions to explain the CPU actions associated with the behavior of the Little Man.

The CPUSIM System

The CPU Simulator System (CPUSIM) is an intuitive graphical simulation of the Little Man model. There have been other Little Man simulations (Parker 1996; Price, 1990). However, CPUSIM provides a unique mix of beneficial characteristics. CPUSIM is built on a simple 8-bit architecture and contains a small but complete instruction set allowing students to write and execute interesting programs. CPUSIM has a friendly graphical user interface (GUI) with multiple viewing perspectives (e.g., digital, binary, and mnemonic). Programs may be executed in real-time or with breaks between each instruction, providing the student with the ability to inspect the behavior of the inner workings of the CPU during processing. During simulation, the fetch/execute cycle for each instruction is presented as a trace of register-transfer activities. CPUSIM provides an excellent simulation tool for introducing students to computer organization. The simulator is designed for use by both students and instructors, and is available at http://cis1.wku.edu/crews/CPUSIM.

CPUSIM Fetch-Execute Cycle

With the LMC model, the behavior of the Little Man (e.g., control unit) is described at a high level for each instruction in the instruction set. For example, Englander explains the fetch-execute activities of the LOAD instruction this way:

   The Little Man walks over to the mailbox address specified in the
   instruction. He reads the three-digit number located in that mailbox, and
   then walks over to the calculator and punches that number into the
   calculator. The three-digit number in the mailbox is left unchanged, but of
   course the original number in the calculator is replaced by the new number.
   (Englander, 2000, p. 149)

The above description is sufficient to carry out the desired behavior using pencil and paper. However, since the "little man" is clearly fictitious, it does not provide an accurate understanding of the LOAD operation with respect to the internals of the CPU. CPUSIM addresses this problem by presenting the instruction set at a microcode level. The fetch-execute cycle for each instruction is described as a series of register transactions. CPUSIM microcode uses the following five registers:

* The program counter (PC) contains the address of the next instruction.

* The instruction register (IR) holds the current instruction being executed by the computer. This register is not identified in the traditional LMC model but is essential to the CPUSIM system.

* The memory address register (MAR) holds the address of a memory location.

* The memory data register (MDR) is a read/write connection to the data stored in memory at the address identified by the MAR.

* The accumulator (A) is a general purpose register.

Using these five registers, all the instructions available to the student can be clearly explained as a series of microcode instructions involving the transfer of data between registers. For example, the first half of every instruction, the Fetch, is the same for all instructions. The microcode for the Fetch is: See issue's website <http://rapidintellect.com/AEQweb/fal02.htm>

As you can see from the comments to the right of each microinstruction, the Little Man idea is maintained. However, by adding the register-level microinstruction activity, the actual CPU implementation of the Fetch is more clearly understood. The following section presents the entire instruction set for CPUSIM and the corresponding microinstructions for execution.

CPUSIM Instruction Set

The LMC instruction implemented within CPUSIM is fundamentally consistent with the instruction set of most CPUs. However, by keeping the size of the instruction set small, students can quickly and confidently grasp the entire instruction set. See issue's website <http://rapidintellect.com/AEQweb/fal02.htm>

Creating a CPUSIM Program

Consider a simple program that inputs two numbers and displays their sum. This program can be accomplished with the following instructions:

Input      'read first value, placing it into the calculator
Store 20   'store value in mailbox 20
Input      'read second value, placing into calculator
Add 20     'add first value (stored at 20) to second value
Output     'display the sum from the calculator

When using the CPUSIM simulator, selected instructions are entered directly into specified memory locations. Selected instructions in memory may be edited by choosing a new instruction from the pull down list. Selected instructions may also be moved, edited and deleted using the graphical user interface (GUI).

Running a CPUSIM Program

Programs are executed by selecting the Run Machine Instruction button or the Run Without Pause button under the register trace grid, or pressing F8 or F9 as a shortcut. During execution, the CPUSIM interface displays the values of each register as each microinstruction completes. Selecting Run Machine Instruction causes the simulator to perform the Fetch Execute cycle for the next instruction only. Figure 2. See issue's website <http://rapidintellect.com/AEQweb/fal02.htm>

Selecting Run Without Pause causes the program execute Fetch Execute cycles for each instruction in sequence, pausing only for user input, until the Halt instruction is executed. This run without pause feature allows the programs to execute at full speed in "real" time, very helpful for testing and debugging longer problems.

Sample CPUSIM Programs

The Add Two Numbers program is a good first program for beginning students. Other programs that are good for beginning students include:

* Biggest of Three: Write a program that will prompt the user to input three values. The output should be the largest of the three input values.

* Countdown: Write a program that uses a loop to display the values 10 down to 1.

* Positive Difference: Write a program that will prompt the user to enter two values. The output should be the positive difference of the two values. For example, if the input is 5 and 7, the output should be 2. If the input values are reversed, the output should still be 2.

* Largest in a Series: Write a program that will prompt the user to enter a series of values. The program should continue to accept input values until the value zero is entered. The program should then display the largest value entered by the user.

Solutions are available at http://cis1.wku.edu/crews/CPUSIM/answers and may be downloaded and executed to provide additional experimentation with the CPUSIM system.

Classroom Usage

The CPUSIM tool has been used in multiple class settings. In the spring 2002 semester, CPUSIM was presented in class, and students were assigned each of the four sample problems presented above (Biggest of Three, Countdown, Positive Difference, and Largest in a Series) as homework problems. After the assignments were turned in, student attitudinal data (N = 18) was collected. The instrument contained a series of statements and students were asked to respond on a five point scale if they agreed or disagreed with the statement (the middle value was neutral). Two of the statements, S1 and S3, where "negative" (e.g. "cumbersome" and "lot of mental effort") statements. Students generally disagreed with the negative statements. Likewise students responded very favorably to the positive comments. The final percentages are shown, see issue's website <http://rapidintellect.com/AEQweb/fal02.htm>

Students were also given an opportunity to make personal comments regarding the CPUSIM simulator. These comments were also strongly favorable.

* "I do believe that the CPUSIM helps to understand the register principle."

* "I felt that the program provided a helpful visual aid for understanding how registers work."

* "It's a great tool for beginning programmers along with the Little Man concept to help understand how a processor works. I look forward to using it to teach my daughter who seems to be computer savvy for her age (she's 13)."

* "The CPUSIM simulator program was very beneficial in understanding how registers work in transferring/copying instructions/data."

* "It was great to test if my program worked. The CPUSIM was a good supplement to in class discussion."

* "It was a very interesting activity. It helped me a lot."

* "I enjoyed using CPUSIM. The steps are very few and the programs follow a very logical sequence."

* "Great program! Excellent hands-on approach."

Based on these encouraging results, we plan to continue using CPUSIM and develop additional simulators to enhance other aspects of our curriculum. We are also excited to share our simulator with other interested educators. It is available for free download for academic use at http://cis1.wku.edu/crews/CPUSIM.

Conclusions

The Little Man Computer is a valuable model for introducing students to key ideas in computer architecture, including memory, the central processing unit (CPU), and input/output capability. The LMC also contains a small instruction set that allows students to write and execute simple programs. By writing and executing LMC programs, students gain valuable experience with important ideas including the stored program concept and the fetch-execute cycle.

The unique and significant contribution of the CPUSIM simulator presented in this paper is the visualization of the underlying microcode executed for each instruction. This functionality presents the control unit at a deeper level than previous LMC simulations without losing the simplicity and elegance of the Little Man model. As CPUSIM continues to improve and expand, we welcome contributions and collaborations with fellow instructional technology researchers seeking to advance the role of instructional technology in computing education.

References

Englander, I. (2000). The architecture of hardware and software systems (2nd ed.). New York, NY: Wiley Press.

Lajoie, S. (2000). Computers as cognitive tools: no more walls (Vol. II). Hillsdale, NJ: LawrenceErlbaum Associates.

Gredler, M. (1996). Educational games and simulations: a technology in search of a (research) paradigm. In D. Jonassen (Ed.). Handbook of research for educational communications and technology (pp. 521-540). New York, NY: Macmillan.

Maurer, M. & Davidson, G. (1998). Leadership in instructional technology, Upper Saddle River, NJ: Prentice-Hall.

Parker, B. & Drexel, P. (1996). A system-based sequence of closed labs for computer systems organization, ACM SIGCSE Bulletin, 28 (1) 53-57.

Price, B., Baecker, R., & Small, I. (1990). A principled taxonomy of software visualization. Journal of Programming Languages and Computing, 1 (1), 97-123.

Thad Crews, Ph.D., Western Kentucky University

Crews is an assistant professor of Information Systems in the Gordon Ford College of Business. He is Chair of the Technology in Education Committee for the National Association of Information Technology Professionals. Before starting his career in academics, Dr. Crews worked professionally as a software engineer for Electronic Data Systems (EDS).