5.2   The TOY Machine


This section under construction.


TOY is an imaginary machine (created at Princeton) that is very similar to ancient computers. We study it today because it shares the essential characteristics of modern day microprocessors. Also, it demonstrates that simple computational models can perform useful and nontrivial calculations. In this document we describe how to use and program the TOY machine. In Chapter 6, we describe how to build such a machine in hardware.

Inside the TOY machine. The TOY machine consists of an arithmetic logic unit, memory, registers, a program counter, switches, lights, and a few buttons Load, Look, Step, Run, Enter, Stop, and Reset. We now describe the function of each of these components. Then, we will describe how the use these components to write TOY machine language programs.

The X-TOY Machine

Why study TOY.

Word size. The TOY machine has two types of storage: main memory and registers. Each entity stores one word of information. On the TOY machine, a word is a sequence of 16 bits. Typically, we interpret these 16 bits as a hexadecimal integer in the range 0000 through FFFF. Using two's complement notation, we can also interpret it as a decimal integer in the range -32,768 to +32,767. See Section 5.1 for a refresher on number representations and two's complement integers.

Main memory. The TOY machine has 256 words of main memory. Each memory location is labeled with a unique memory address. By convention, we use the 256 hexadecimal integers in the range 00 through FF. Think of a memory location as a mailbox, and a memory address as a postal address. Main memory is used to store instructions and data.

Registers. The TOY machine has 16 registers, indexed from 0 through F. Registers are much like main memory: each register stores one 16-bit word. However, registers provide a faster form of storage than main memory. Registers are used as scratch space during computation and play the role of variables in the TOY language. Register 0 is a special register whose output value is always 0.

Program counter. The program counter or pc is an extra register that keeps track of the next instruction to be executed. It stores 8 bits, corresponding to a hexadecimal integer in the range 00 through FF. This integer stores the memory address of the next instruction to execute.

Core dump. A core dump is a complete listing of the state of the machine contents at a particular instant in time. The core dump provides a record of what the machine has done, and it also completely determines what machine will do. Both data and the program are stored in main memory, and it is up to the programmer to ensure that data is treated as data, and that instructions are treated as instructions.


A Core Dump of TOY

Input. The switches and Load button are used to enter instructions and data into the machine. The switches behave just like ordinary light switches: they are either on or off. There are 8 memory address switches to select one of the 28 = 256 possible memory addresses. There are also 16 data switches to select a 16 bit integer to load into the corresponding memory location. To enter data into memory, you set the appropriate memory and data switches, and then press the Load button. This tedious process is repeated for each memory location. All registers and memory locations are initially 0000; the program counter is initially 10.

Output. The memory address switches, lights and Look button are used to display the address and contents of one word of main memory, as the program is being executed. To select which word of main memory to view, you set the 8 memory address switches and press the Look button. Now, the 8 address lights display the chosen memory address (which at the moment is the same as the address switches). The 16 data lights display the contents of that memory location. Old programmers could often know what part of the program was being executed by staring at the pattern of memory lights.

Running the machine. To execute a TOY program, you first enter the program and data into main memory, one word at a time, as described below. Then, you set the initial value of the program counter: to do this, set the memory address switches to the desired value (typically 10) and press Look. Now, you can press the Run or Step button to initiate the computation. From this point on, the TOY machine executes instructions in a specific, well-defined way. First it checks the value of the program counter and fetches the contents of this memory location. Next, it increments the program counter by 1. (For example, if the program counter is 10, it gets incremented to 11.) Finally, it interprets this data as an instruction and executes it according to the rules below. Each instruction can modify the contents of various registers, main memory, or even the program counter itself. It may also output integers to the LED standard output. If the program needs to read a value from standard input, then the INWAIT light activates and the machine waits until the user enters a 16-bit integer using the data switches, and presses the Enter button. After executing the instruction, the whole fetch-execute cycle is repeated, using the new value of the program counter to obtain the next instruction. This continues forever, or until the machine executes a halt instruction. As with Java, it is possible to write programs that go into infinite loops. It is always possible to stop the TOY machine by pulling the plug or pressing the Stop button.

Von Neumann Machine. One of the essential characteristics of the TOY machine is that it stores computer programs as numbers, and both data and programs are stored in the same main memory. In 1945, Princeton scholar John von Neumann first popularized this stored-program model or von Neumann machine. It enables computers to perform any type of computation, without requiring the user to physically alter or reconfigure the hardware. In contrast, to program the ENIAC computer, the operator had to manually plug in cables and set switches. This was quite tedious and time consuming. This simple but fundamental idea of the stored-program machine has been incorporated into all modern digital computers.

Since the program and data share the same space, the machine can modify its data or the program itself while it is executing. That is, code and data are the same, or at least they can be. The memory is interpreted as an instruction when the program counter references it, and as data when an instruction references it. The ability to treat the program as data is crucial. Consider what happens when you want to download a program from a remote location, e.g., download.com. It is no different from receiving email, or any other data. Compilers and debuggers are also programs that read in other programs as input data. Treating programs as data is not without its perils. Computer viruses are (malicious) programs that propagate by writing new programs or modifying existing ones.

In hindsight von Neumann's idea may seem obvious. However, it is not obvious whether a computer built around a stored program model can be as powerful as a computer that can be rewired and reconfigured. In fact, the ability to physically reconfigure a computer does not enable you to solve more problems, so long as basic instruction set is rich enough (as is the case with the TOY machine). This is a consequence of previous work by Alan Turing on Turing machines. We will study this later in Chapter 7.

Q + A

Q. Did ancient programmers really flip switches to enter a program?

A. Yes. They later moved on to punch cards for a more permanent form of storage.

Q. What's the difference between a register and a memory cell?

A. Both store 16-bit integers. However, in the TOY machine all computations (add, subtract, etc.) can only be performed on the contents of registers, not main memory. To perform arithmetic on a memory cell, it must first be transferred to a register, and then transferred back. It is desirable to make registers as fast as possible so they are typically built from more expensive materials than main memory, even though in principle, both just store 16 bits. This is analogous to the difference between computer RAM (scarce and expensive) and the hard drive (plentiful and cheap).

Q. Are special purpose computers or microprocessors still fabricated today?

A. Yes, because it is possible to do simple things faster in hardware than software. The Enigma machine was a special purpose encryption machine used by the Germans in World War II. Alan Turing led a team at Bletchley Park to build a Turing bombe machine, whose sole capability was to break Enigma codes. Here's an Enigma kit that you can buy to build your own. Some modern examples include: signal processing, chess chips for Deep Blue to evaluate board positions, N-body simulation chips, cryptography chips that can manipulate 2048 bit integers. Astrophysicists use a very specialized chip for calculating the Newtonian gravitational force between particles. One of the most successful such chips is the GRAPE-6 which is capable of one teraflop (floating point operations per second) per board, and a 64 processor board is capable of a sustained rate of 64 teraflops. This may be the fastest computer in the world, although it is only good at this one specialized task.

Exercises

  1. How many total bits of storage does the TOY machine have? Include registers, main memory, and the program counter.
  2. TOY uses 8-bit memory addresses which means it's possible to access 256 words of memory. How many words of memory can a 32-bit machine access? A 64-bit machine access?
  3. How many words of main memory does a Pentium IV with 1GB of memory have? A Pentium IV is a 32-bit machine.
  4. How many words of main memory does a Mac G5 with 1GB of memory have? A G5 processor is a 64-bit machine.

Creative Exercises

  1.