Enginursday: Computer Basics

Exploring a simple von Neumann architecture computer

by .Brent. April 9, 2015 1:38 pm UTC 6

• Enginursday

Favorited Favorite 2

This post is about a model computer that Bell Labs released in 1968 for use in high schools – CARDIAC (CARDboard Illustrative Aid to Computation). The central concepts are the same, but the technology of the day was a little less mature.

Here is a video Bell Labs released in conjunction with CARDIAC. It gives one a feeling for the state of computing in that day. I especially like the schematic capture tool they show around 9:19. Wish we had that tech to use here at SparkFun.

Von Neumann Architecture

In 1945, mathematician and physicist John von Neumann described the computer architecture used in CARDIAC (and many other computers) for the United States Army. The von Neumann model consists of five parts: a control unit, a processing unit, memory, input and output.

PROGRAM UNIT

The program unit, also known as the control unit, contains all of the parts required to control the computer. The creators of CARDIAC refer to this as the program unit. Inside are special pieces of memory called registers, a finite state machine, multiplexers, and other pieces that this discussion will largely abstract out. It is left as an exercise to the the reader to dig deeper than the level presented here. The main concept is the finite state machine takes a set of inputs, like the instruction register and a clock signal, and decides what to do next. The control unit is also responsible for managing the program counter register. This register keeps track of where the next instruction to fetch lives.

ACCUMULATOR

The processing unit consists mainly of an ALU (Arithmetic and Logic Unit). The ALU is responsible for basic arithmetic functions like addition and subtraction. The ALU is also often responsible for basic logic operations like bit-wise AND, OR, and NOT. The CARDIAC computer is very basic and cannot do these logic operations, but can do shifting and comparison. An accumulator is one form of ALU configuration. The accumulator is a special register that stores the results of the ALU. This simplifies the ISA (Instruction Set Architecture).

MEMORY

Memory is is a set of storage elements and a few registers to assist in communicating with the storage. The MAR (Memory Address Register) stores the location or address in memory that is to be read or written. The MDR (Memory Data Register) holds the data to be written to memory or the data read from memory.

Now is a great time to talk about a key difference between CARDIAC and traditional computers. Traditional digital computers use tubes or transistors to set the state of the computer. They typically can only have two states – off or on; high or low. This is referred to as binary. Since this is a cardboard illustrative aid, and not a real computer, it’s not troubled by these implementation details. CARDIAC is a human friendly base 10 (decimal) machine. Rather than using binary bits, CARDIAC uses decimal digits.

The MAR is two digits. CARDIAC can thus address 10² or 100 addresses. Not all machines have the memory they are able to address, but in this case we do, all 100 three-digit words! Each memory cell is three digits, and so is the MDR. The accumulator is four digits to accommodate overflow. All four digits are kept in the accumulator until stored, when the most significant digit is dropped. Negative numbers are simple negative numbers here. Don't worry about how the computer encodes them since CARDIAC is really pencil and paper.

INPUT

Input comes in many forms on real computers. Any peripheral one can imagine can be used as input. Some of the more common types of input are the keyboard, mouse, disk, scanner, etc. All of these types of inputs are eventually converted into a format that the processor can work with. In the case of CARDIAC, this is a list of three-digit numbers. These numbers are composed of two parts. The most significant digit is the opcode (operation code), and the other two digits are operand. In most cases the operand is simply an address. In the case of the shift opcode, the middle digit tells how many digits to shift to the left, and the right-most digit tells how many to shift to the right. The halt opcode ignores the operand.

OUTPUT

Computer output comes in as many forms as inputs. There are monitors, speakers, printers, disks, etc. In CARDIAC, output comes in the form of numbers from -999 to 999. For real world applications each value can be assigned a meaning. For example if one wrote a blackjack game, 20 could mean the computer draws a card, 30 could mean hold, and 40 could mean fold.

RUNNING CODE

When CARDIAC first "powers on," the memory is empty; even the registers are initialized to zero. How does one get a program into memory to run?

The program counter begins at 00. This means that the next instruction to load is in memory at location 00. Thankfully there is an exception to memory being empty at boot. Address 00 is ROM that contains the instruction 001. This discussion cannot proceed without first describing the instruction set, so let me do that here:

Back to running code... Memory address 00 always contains 001. This can be broken into the opcode and operand (0 01). 0 indicates the input instruction. The operand 01 indicates that the input will be written into memory address 01. When the first instruction 001 is being processed the PC is incremented by one and is now set to 01. The next instruction to process is the one that was just loaded from the input by the previous instruction. Now the computer is running code that the user has specified!

BOOTLOADING

The process briefly described in the previous section is called bootstrapping. It's how you get up and running at boot time. Real programs require more than a single instruction. How would you get more code into a machine? What is the first instruction you would have loaded? How about 002? The program counter is going to increment again while processing your first instruction and be pointing at memory address 02, may as well have something there to run. How about 800? This makes the full program:

001 ;(In ROM)
002 ;(top of input stack)
800

The computer begins with the PC set to 00 & executes the first instruction (001) at address 00. This loads the first input (002) into memory address 01 and increments PC. The computer now sees the instruction 002, so it loads 800 from the input into memory address 02 and increments PC to 02. Memory address 02 contains 800, or jump to address 00, so it sets the program counter to 00 rather than incrementing it. We are now back at our initial state with one very important difference. We have an infinite loop (neglecting some details). This is the core of our bootloader.

Lets assume we are back at PC = 00, but we have 800 stored at address 02. All we have to do now alternate between load instructions and our real program code. For example let the full input stack be:

002
800
010
100
011
200
012
615
013
515
014
900
810

If you start decoding the new instructions you will see that we are loading 100 into memory at address 10, loading 200 into 11, loading 615 into 12, loading 515 into 13, 900 into 14, and the final instruction is 810. When the computer gets here what is it doing? 810 means jump to address 10. But what is at address 10? It's our first real bit of code!. The program has been bootloaded into memory addresses 10 through 14. Here is that listing:

10: 100  ;clear accumulator and load the contents of 00
11: 200  ;add the contents of 00 to the accumulator
12: 615  ;store the contents of the accumulator to memory address 15
13: 515  ;write the value in memory address 15 to the output
14: 900  ;halt and reset

What does this code do? It adds 1 + 1, outputs the results and halts. 13 lines of assembly code to add 1 + 1! This might give some appreciation for how much goes on behind the scenes in computers.

DOING REAL WORK

You may have noticed that this computer can't even multiply. How would you do this? Doesn't 3 * 4 = 3 + 3 + 3 + 3 = 4 + 4 + 4?

Wouldn't that be nice to have a subroutine that could multiply for you and put the result in a predetermined memory address? Did you notice that the opcode 8 stores the current PC into memory address 99? This address is the second address that isn't standard memory. The opcode is always 8. If one were to run 898 from memory address 14 address 99 would store the value 815 and the PC would jump from 14 to 98. Assume the contents of address 98 are something simple like 200. What would this do? First it would increment the accumulator. The PC would then increment to 99. The computer would run the instruction stored there, 815. This would jump back to PC = 15. This is a trivial subroutine that adds one to the accumulator, but you could instead put your subroutine starting at address 90, run 9 interesting instructions before returning to right where you left off.

I encourage you to play around with writing some CARDIAC assembly code. The ISA of the machine in front of you is doing the same basic thing, only it has many more complicated instructions in addition to this simple set of 10. I've written a simulator that you can try running code in. Be warned that there is virtually no error checking, so your code must be decent. If you tell the machine to run an invalid command and it locks up, hit the reset button. The simulator is preloaded with code to count to 10 on the output. Enjoy!

iframe The source code for the simulator can be found here.