Imaginary Computer

Imaginary Computer Design

The Imaginary Computer is a conceptual computer that simulates many of the basic features found in modern electronic digital computers. It is designed to demonstrate the "Stored Program Computer Architecture," also known as "von Neumann Architecture," named for the mathematician John von Neumann (1903-1957, pronounced noy mahn).

Imaginary Computer

The Imaginary Computer is made up of the following main parts:

• Primary Memory
  32 8-bit (1 byte) memory cells. Each cell can hold machine instructions or data values. Numbers are 8-bit signed integers; the left-most bit is the sign bit (0 indicates a positive 7-bit integer, 1 indicates a negative 7-bit integer)

  00	01000101	01111110	01001101	10011110	04	01111111	00000000	00000000	00000000
  08	00000000	00000000	00000000	00000000	12	00000000	00000000	00000000	00000000
  16	00000000	00000000	00000000	00000000	20	00000000	00000000	00000000	00000000
  24	00000000	00000000	00000000	00000000	28	00000000	00000000	00000101	00000000

• Central Processing Unit (CPU)
  The CPU consists of a Control Unit, an Arithmetic-Logic Unit (ALU), and a small set of temporary storage cells called registers.
  • The control unit keeps track of where to read the next instruction in the Program Counter (PC) and coordinates the Fetch, Decode, Execute Cycle

  • The ALU does exactly what its name implies: performs arithmetic calculations and logic to make decisions (and thus branching) possible.

  • The Imaginary Computer only has 3 registers: the Accumulator , which "accumulates" the intermediate results of arithmetic operations; the Instruction Register (IR), which holds the current instruction fetched and decoded by the control unit; and the Program Counter (PC), which tells the Control Unit where to get the next instruction. (Real computers typically have several registers: some general purpose registers for general storage, and special purpose registers like the accumulator and instruction register, as well as registers designed specifically to address memory.)

    Control Unit	Registers	ALU
    Example: Fetch: instruction at [03] Decode: ADD value at [30] to AC Execute: Instruct ALU to perform calculation	Program Counter (PC) Example: [3]	Example: Get value at [30] (5) ADD to current value (13) Keep result (18) 13 + 5 = 18
    	Instruction Register (IR) Example: [10011110]
    	Accumulator (AC) Example: [13]

• Input and Output
  Unlike a "real" computer, the Imaginary Computer does not have an input device (keyboard) or an output device (console/printer); we will have to load data into memory before executing a program, and either inspect the accumulator or specific memory addresses to see the results of calculations.

  As we will see, the Imaginary computer has an instruction that, while not strictly necessary, is designed to make programming the computer easier. By convention we will store "final results" in the highest memory address, 31.

Imaginary Computer Instructions

• The Operation Code (opcode) specifies what to do. The Imaginary Computer instruction set has a total of 8 instructions, therefore 3 bits (2 * 2 * 2, 2³ = 8) are required for the opcode. All instructions have an opcode.

• The Operand provides additional data for the opcode to operate on. Typically the operand is a memory address where data to be operated on is stored or where the next instruction should be read, or it is an immediate (constant) numerical value to be operated on. Most Imaginary Computer operands are memory addresses; however one instruction (LDC, which is a mnemonic for Load Constant), is designed to facilitate programming by allowing the user to load a constant value directly into the accumulator. Some instructions do not require an operand, in which case that part of the instruction is usually filled with 0's. The HLT instruction does not have an operand.

  3 bits are needed for the opcode, therefore 5 bits remain to hold the operand. 5 bits can represent at most 32 (2⁵) memory addresses, therefore the Imaginary Computer is limited to 32 bytes of RAM. We could add more memory, but how would we address it?

  Opcode			Operand
  1	0	0	1	1	1	1	0

The Imaginary Computer has 2 instructions for calculations: ADD and SUB for addition and subtraction respectively. In both cases the operand specifies the memory address of the data to be added or subtracted. The operation is performed on whatever is currently in the accumulator, and the result is stored in the accumulator.

3 instructions manage data. LOD copies the data item from the memory address specified by the operand and "loads" it into the accumulator (the contents of memory are not changed). LDC Loads the constant specified in the operand into the accumulator. Note that while the accumulator can hold an 8-bit value, operands are limited to 5 bits; therefore, to allow for positive and negative constant values, the range of constant integers that can be loaded with LDC from -16 to + 15. STO copies the contents of the accumulator to the memory address specified in the operand.

Note ADD, SUB, LOD, and LDC above: the contents of the accumulator are very temporary; any useful work in a computer requires constant storing of data in memory to save intermediate results and constant loading data from memory to perform calculations.

3 instructions control the program flow. The control unit fetches the instruction located at the memory address specified by the Program Counter, stores it in the Instruction Register, decodes and executes the instruction (using the ALU and registers), then increments the Program Counter. Having completed the cycle, the PC is pointing to the next instruction and the control unit is ready to start again. This is called sequential program flow and is a lot like a mail carrier walking down the street and delivering mail to each house in order.

Frequently we want to do the same (or similar) operations over and over. The Imaginary Computer uses the JMZ instruction to set the Program Counter to the value specified in the operand if the accumulator is 0; the JMP instruction sets the Program Counter to the value specified in the operand if the accumulator is equal or greater than 0 (e.g. is positive).

Finally, and perhaps most important of all, we need to tell the computer when to stop with the HLT instruction. If we did not have a way to tell when to stop, the Control Unit would just continue to faithfully fetch instructions. Eventually it would get down into our data area and try to decode and execute those values as if they were instructions, possibly with disastrous results.

Imaginary Computer Instruction Set

PROGRAM 1

The following Imaginary Computer program adds 2 numbers that are loaded in the accumulator via the LDC instruction, assigning the first number to memory location 30 and the result to memory location 31. Note that the program starts reading instructions at memory address 0 and continues sequentially until the HLT instruction is executed.

Machine Language Address: Instruction 00: 01000101 01: 01111110 02: 01001101 03: 10011110 04: 01111111 05: 00000000

Assembly Language Address  Instruction 00  LDC 5  ;load constant 5 in AC 01  STO 30 ;store AC value in [30] 02  LDC 13 ;load constant 13 in AC 03  ADD 30 ;add value in [30] to AC 04  STO 31 ;store result in [31] 05  HLT    ;halt program execution

Try "running" this program on paper using only the Machine Language version (the one in binary). Assume that the Program Counter always starts at 00 and the Accumulator is 0 and program startup.

• Note the LDC instructions at 00 and 02: the decimal values 5 and 13 are loaded directly into the accumulator. Because there is only one accumulator, the first number must be stuffed into a memory cell while we get the second number to perform the addition.
• The instruction at 03) adds the number in the accumulator to the number in memory cell 30 and puts the result back in the accumulator.
• Instruction 04 saves the result in memory; the result only stays in the accumulator until we load another data item or do another calculation.
• Note that we could have used only one memory cell if we did not care about saving one of the numbers.

Now look at the Assembly Language version. While machine language is the only language the computer understands at the CPU level, assembly language is much easier for humans to read and understand.

• Assembly language instructions are mnemonics that remind the programmer what the instruction does.
• Each assembly instruction maps directly to one corresponding machine instruction (and vise versa).

PROGRAM 2:

        DEF 31 0            ;loop counter, init to 0
        DEF 30 4            ;number of repetitions
                            ; Start of program
                            ; LOOP
        LOD 30              ;00 AC = num reps
        SUB 31              ;01 0 when counter = limit
        JMZ 07              ;02 goto END LOOP if 0
        LDC 1               ;03 increment by 1
        ADD 31              ;04 increment counter
        STO 31              ;05 save counter
        JMP 00              ;06 goto LOOP
                            ; END LOOP
        HLT                 ;07

        00:00111110         ; LOD 30
        01:10111111         ; SUB 31
        02:11100111         ; JMZ 07
        03:01000001         ; LDC 1
        04:10011111         ; ADD 31
        05:01111111         ; STO 31
        06:11000000         ; JMP 00
        07:00000000         ; HLT
         .    .             ;
         .    .             ; additional unused memory
         .    .             ;
        30:00000100         ; pre-loaded to 4
        31:00000000         ; pre-loaded to 0

This program subtracts a counter (starting at 0) from a known value (4) that we want to count up to, then uses the JMZ instruction to compare the result in the accumulator with 0 (this is the Logic part of the ALU). If the accumulator is not 0, the instruction is ignored and program control proceeds to the next instruction.

Next we add 1 to the counter and save the new value. The JMP instruction jumps to the address specified in the operand if the accumulator is positive (equal or greater than 0); this is guaranteed to jump because we just explicitly performed the addition of our counter.
(Note: If we counted far enough, eventually the counter would "overflow" and become a negative number, causing the jump to fail. In this case the next instruction would be executed, which is HLT.)

The program ultimately halts when the counter gets up to 4: the result of the subtraction is 0, JMZ finally has the condition it needs to jump to the address in its operand, which is the location of the HLT instruction.

Note the implication of forgetting to store the value of the counter back in memory after incrementing the counter: the counter keeps getting loaded as 0, the result of the subtraction is always 4, and the accumulator never decrements to 0. This is called an infinite loop.

The following table shows a "program trace" for each pass through the loop until the JMZ instructions finds 0 in the accumulator the program stops. The * character is used to show that the program did not execute the instruction on that pass due to branching by the JMZ or JMP instruction.

Address	Instruction/Directive	Accum	Accum	Accum	Accum	Accum
00	LOD 30	4	4	4	4	4
01	SUB 31	4	3	2	1	0
02	JMZ 07	4	3	2	1	0
03	LDC 1	1	1	1	1	1
04	ADD 31	1	2	3	4	*
05	STO 31	1	2	3	4	*
06	JMP 00	1	2	3	4	*
07	HLT	*	*	*	*	0
	Data Area
30	DEF 30 4	4	4	4	4	4
31	DEF 31 0	0	1	2	3	4

Imaginary Computer Machine Simulator

While the Imaginary Computer is designed to be used with pencil and paper, it is also valuable to watch the instructions in action and to verify if your programs work.

I have written an Imaginary Computer simulator in JavaScript where you can enter and try programs and see the results. You can enter binary machine instructions directly in the memory cells or you can type assembly instructions in the Assembly window, assemble them, then load them into memory.

Note that the simulator is a "work in progress," if you find errors or discover something that does not work please let me know.