The simple computer (part 1)

Features Gordon Moore Jan 22, 2013

Gordon Moore looks at how a simple computer processor works and how it’s programmed to multiply two numbers together

If you were going to design your own computer, what would you need? Actually, the real question is probably: ‘what do you want it to do?’ Please don’t say ‘everything’, because even not the combined might of Intel, AMD, ARM, Apple and the rest has managed that trick, yet.

I suppose that we could add a caveat to my question by changing it to ‘what would you want it to compute?’ Alan Turing asked a similar question to that before coming up with the notion of what we now call a Turing Machine; the simplest possible system that could compute anything that it was possible to compute. 

While we need not be quite so esoteric, we must decide what our computer needs to do. A computational device, pretty much be definition, needs to be able to represent numbers, both positive and negative, and then add two of them together; if it can do that, it can also do subtraction, then multiplication, division, finding square roots and even be made to calculate trigonometric functions (such as sine, cos and tan) as well as work out exponentials and logarithms. I hope you’re not bored already. 

Take, for instance, multiplication. If we break it down, it is just repetitive addition: 3 x 4 becomes 3 + 3 + 3 + 3, or 4 + 4 + 4. This understanding logically brings us to the realisation that our processor will need to be able to repeat an operation a number of times. In other words, to multiply 3 by 4 we need to keep adding three by ‘looping’ the task four times. Also, we’re going to need somewhere to store the numbers to be added, as well as somewhere to store our result and any interim values (3 + 3 = 6, 6 + 3 = 9, etc.). While we are at it, we might as well use the same store to hold the steps of our routine for calculating the functions we need.

We need a ‘store’, or memory. In modern computers, that is made up of dynamic RAM chips (4GB-worth, or more in a modern PC), though in the past it was made from all sorts of strange equipment: mercury delay lines, cathode ray tubes (the Williams tube) and a device made from thousands of tiny rings (toroids) or a magnet with many wires running through them (aka a magnetic core). In the early days of computing - 70 years ago, during the Second World War - storage was phenomenally expensive and you couldn’t have much of it (just tens, or maybe hundreds, of bytes).

Our ‘store’, or local memory (as opposed to, say, mass storage such as a disk), basically consists of a series of locations, one after the other. Each location has a unique identifier - called an address. At each address there is some information held, such as a number or an instruction. For computers, addresses start at location 0 rather that 1, because they use binary numbers to represent the addresses and 0 is the first binary number.

To hold numbers in our store, and then retrieve them we need commands, that we might call ‘Store’ and ‘Load’, although nowadays we just call it a ‘MOVE’ command. This shifts data from the store to the processor or from the processor back to the store. Finally, we get to sorting out a method for adding two numbers together, an arithmetic unit if you will - or the arithmetic and logic unit (ALU), as it is often called.

The functions of this computer now need to be made to happen in an organised manner, so we need some kind of electronic controller that will run through our routine one step at a time, and that can also jump around in our routine, what we will call our ‘program’.
You will notice from the block diagram of a simple computer in Fig. 1 that there is a place called ‘Results Of Calculations’. We often call this the accumulator on basic designs, though in modern chips there are a number of accumulators called registers. Some of these are general purpose, whereas others are specialised (such as those working with an area of memory called The Stack).

If you think about it, having an accumulator is not specifically required, since we could just arrange for our calculations to be done in the Store. While this is right in theory, in practice we want things to happen as quickly as possible and a main memory store is far too slow for a processor. It is better to create a few, very fast registers near the actual ALU rather than access the slower main memory. The downside of this is that these fast registers are more expensive and use up valuable silicon, so we can’t have too many - and correspondingly we can’t afford to make our main store out of these fast registers. In practice, computer designers also use varying levels of cache memory to hold portions of the main store in ever faster memory areas, though each one that is faster is smaller in the amount it can hold. The purpose of these is to try to improve the throughput of instructions.

To keep things very simple, we shall have just one amount of main storage and one fast register, the accumulator, where the calculations take place.

A very simple program

Let’s design a very simple routine to add two numbers and store the result using our simple design. The program will do the following steps:

1. Move the first number from the store into the accumulator
2. Add the second number from the store to the number in the accumulator. (This is done by the ALU)
3. Move the number in the accumulator to the store (hopefully in some spare location).

We can abbreviate this long-winded description by using some abbreviations.

MOV AC, the first number
ADD AC, the second number
MOV to the result, AC

Notice how this kind of goes a bit backward? The first line says that there is an instruction called MOV which moves things, the next part is saying where it is to move something to, in this case the AC or accumulator, the second part says where should we move it from. The second line is saying that we now add to the accumulator, the second number. The third line is using the move instruction again to move to somewhere in memory the value in the AC or accumulator.

This terse way of writing things is called Assembly Language. It is very low level, much lower than say Java, C# or Objective C computer languages.

You might think it should go the other way round. Well, actually, in some styles of writing these instructions it does. The style we are using is called Intel style. It's provided by Intel for use with its Assembler programs. An assembler is a program that takes instructions written in a text editor and converts them into machine code. Many assemblers use Intel style: MASM, TASM, NASM, FASM and YASM etc. Many of these are free.

The second style is named after AT&T Bell Labs, a major US company, which created Unix. The GNU Assembler (or just GAS or even AS), the assembler used on Linux, supports both AT&T as well as Intel style, but it seems most assembly language programs written for Linux use the AT&T style. The basic difference is that the order of the source and destination operands are different. That breaks down as follows...

Intel Style: Opcode destination, source
AT & T Style: Opcode source, destination

Another difference is that registers in AT&T style have a % sign in front of them, whereas in Intel style they don’t.  In AT&T style, instructions have to be of the correct type, so to move a long word we use MOVL. For Intel the type of instruction required is derived from the context - so we can just use MOV. In AT&T style, literals are preceded with a $ sign.

Anyway, we're using Intel style here. Now, we need to create a more formal way of identifying the numbers, though. So, as we said we would store the numbers in memory somewhere, let’s do just that: suppose we store our first number at memory location 13, our second number at memory location 14 and the result at memory location 15. We can now write our code as:

MOV AC, [13]
ADD AC. [14]
MOV [15], AC
STP

Note the use of the square brackets; these tell us that we want the value stored in the particular memory location. So we are not moving the number 13 into the accumulator, but the value stored at memory address or location 13 into the accumulator.
If we don’t use the square brackets then we are saying to our computer use the actual number, which is okay sometimes, but would mean that we would have to change our program each time we wanted to add different numbers. By using the memory locations we can just change the numbers in memory and use the same program.

So we could do

MOV AC, 3
ADD AC, 4

In the accumulator we would then have 7.

The numbers 3 and 4, when used in this way, are called Literals (or Constants). Note we can’t say, for example, “MOV 5, AC”, because we cannot move the contents of the accumulator into the number 5, it just doesn’t make sense. And did you notice the new instruction: “STP” (stop)? Well, we have to tell our computer that it has finished, otherwise who knows what it might continue doing!

So much for the theory

It’s all very good to look at how we might do this on paper, but how does it really work? Well, for your delectation and wonder I have created a simulation of our simple computer called, er... Simple Computer. You can download it from bit.ly/RWjPVX. It's written in C# and the source code is also available (as a solution file). Please email me at gfmoore01@gmail.com for a copy of the source and feel free to improve on it yourself. It might look a little complicated, but we shall explain each part as we go along.

Hopefully you can recognise that, on the right, we have our store or main memory. This consists of 16 ‘pigeon holes’ starting at 0 and going to 15 - so not very much. We can add a little more memory if we click on the red right arrow at the top right. This gives us 16 extra pigeon holes. Again, not very much, you might think - and you would be right, but this is meant to be a ‘simple’ computer, and that’s enough to demonstrate the principles of computing. It’s also the right size for displaying by projection to my students in class.

At the top we have our Instruction Pointer (IP), also commonly called a Program Counter (PC). This simply tells us what instruction we are currently executing (or rather about to execute). Every time an instruction is executed this gets changed, usually by adding one to its value. However, we can also change it depending on certain conditions and this allows us to jump around our program. We shall see why we would want to do that shortly.

The Instruction Pointer has a red line that points to the instruction about to be executed. Underneath this is the Accumulator. This holds the results of our calculations and any values we want to work on. If there were many of these we would use the term ‘registers’.

Below that we have the Instruction Decoder, the Arithmetic and Logic Unit and some status flags: Zero, negative and Overflow. When we look at how our processor works out what to do then the Instruction Decoder will be useful, but for now just ignore it. Note, though, that there is a blue line from the Instruction Decoder that points to the memory store. This shows which memory location data is going to come from or be stored to.

Underneath the flags is the Execution Unit. This allows us to run our programs. This can be done a single step at a time, by pressing the Execute button each time, or we can have it running freely at varying speeds.

You should note that there is also a Break button, for when we want to stop our program. After which, the program can be resumed by pressing Execute again. We also have a Reset button, which changes the Instruction Pointer back to zero and clears the accumulator, also back to zero. This is so we can rerun our programs.

Underneath that, are some radio buttons that allow us to choose the style of Assembly language (see INTEL Vs. AT&T Style box out, below) we wish to program in, or even in machine code.

Finally, there are some buttons that allow us to save and load our programs. These are simply text files with some header and footer information and have the extension .sc - you can look at them with notepad or something similar. CMem is a button that clears the memory. Finally, note that there is no undo function!

So let’s load our first program, shall we? In the first memory location, i.e. address 0, type in:

MOV AC, [13]

Then click into memory location 1 and type:

ADD AC, [14]

Then click into memory location 2 and type:

MOV [15], AC

And then in memory location 3 type:

STP

Then at memory locations 13 and 14 type in two numbers you wish to add, e.g. 7 and 4. The program may display an alert if it thinks you have done something wrong, something that is usually caused by a forgotten comma, or not using spaces. Oh yes, even the spaces are important! This syntax checking is very elementary though. Just clear the alert and correct the line in memory.

Although not strictly necessary, I always press Reset. Note how the red line points to the memory location 0 – our first instruction, and the blue line points to memory location 13, where our first number comes from. Now press EXEC.

In the accumulator you should see the number 7. The IP moves to the next memory location ready to execute the next instruction and the red address bus line shows that the data will come from or go to memory address 14. Now press EXEC again, and the accumulator shows 11, because 4 has been added to the 7 that was there. The IP moves on and the address bus is pointing to 15.

Press EXEC again and the number 11 is now stored in memory location 15. Pressing EXEC once more causes the program to stop. (Pressing EXEC again has no more effect.)

Well done! We have run our first program. I’m sure you are astounded at what you have so far achieved. We can run this program automatically by selecting the Run Freely radio button and perhaps adjusting the speed slider (our clock rate) to about the middle of the range. Press Reset and then press EXEC. The program now runs through the steps under its own steam. It truly is a thing of great beauty.

You might have noticed that the result in memory location 15 remains at 11. This is because Reset does not change any of our memory locations. It is often very useful to make sure that memory locations are set to known values at the start of our program. So, in the case of our program, we would like to make sure that memory location 15 is cleared (set to zero).

To do this we need to edit our program. We need to insert a blank line at memory location 0 and push down by one line the rest of our code. To do this, you will need to move the mouse so that it is on the [0] and right click. A context menu will then now appear, allowing you to either insert a blank line or delete a line should you need to. Inserting a line tries to be clever by only moving what it thinks to be a code block and leaving what it thinks to be a data block in the same place. The two blocks are separated by an empty memory location.

So, in the (now) empty memory location enter:

MOV [15], AC

On a reset we can guarantee that the accumulator is set to zero. So by moving the accumulator to memory location 15 we have cleared that location. Press reset and EXEC.

Save your program as SimpleAdd.sc; you never know, this could be the start of something big, that you may want to remember it forever.

Time to times

You are now doubt very pleased with yourself. If you aren’t, then you should be, because you are now a fully-fledged programmer. Not only that, but an assembly language programmer at that! There aren’t too many of those around anymore, so hold your head up high.
Let’s face it, though, adding two numbers together is hardly ground breaking. So now we need to think about how we might multiply our two numbers together.

Well, we could just create a multiply instruction and indeed there is one in Simple Computer, but let’s just think for a moment how we might do the work in software. In the early days this was an important consideration. Hardware was very expensive, and unreliable, consisting as it did of thousands of Valves, little cylinders of glass filled with various wires and a little coil. They were operated at high voltages and allowed electronic switches to be made. These in turn made up the digital electronic circuits for the computer. Building a multiplier circuit was no small matter. If this could be done in software rather than hardware, then so much the better as software was comparitively cheap.

So, once again, let us look at multiplication. Remember the example of 4 x 3? What are we really doing when we work this out? Well most likely you just look up the answer in your brain, since you memorised your tables, right! So we could do it by using a look up table in our memory.

The question, though, is how did we create that look up table? Well we said that multiplication is really repeated addition: 4 x 3 is 4 + 4 + 4. So, we have added four to itself three times ( or, as we also illustrated earlier, you could say that it is three added to itself four times.

How could we implement this algorithm as a program, then? Well, let us suppose we start with a zero. We load the zero into the accumulator, then we add four to get four, then we save that result. We have now done the operation once. Then we load the four into the accumulator and add another four to get eight. Then we save that result - we have now done the operation twice. Then we load the last result into the accumulator, before adding four to get 12, then we save that result again. We have now done the operation three times and our multiplication task is now finished.

Note how the same three instructions get repeated. Assume that four is in location [13] and [15] will hold our result and starts at zero.
MOV AC, [15]
ADD AC, [13]
MOV [15], AC

Countdown conundrum

So our next problem is to repeat this block of instructions three times. Ideally, it would be nice if we could write some kind of test that asks if we have done something three times. which we could then apply to our additions. Once again, using simple electronics, this is not something that is trivial to do. We would need what is called a comparator circuit that tests if some number equals a given number, e.g. 3. It is much easier if we can just test for zero. That just needs essentially one logic gate (a NOR gate for those in the know).

We aren’t testing for zero, though, we actually want to test for something going ‘one, two, three’. Wait, though, why don’t we test for something going: ‘three, two, one, zero’? Then, when we get to zero we know we have done the thing three times.

You will often find this thought process going on when programming: ‘I want to do something. I don’t know how, or I can’t find an instruction to do what I want. So think, is there another way I can accomplish the same ends?’

This is why teaching programming to children at school is so useful. Programming teaches children to think of alternative, creative ways to solve real-world problems. So we will start with our three, reduce it by one (which is called decrementing), then ask if we are at zero yet. If we are we stop. If we aren’t then we need to jump to the beginning of our little block of code. Internally to make the jump the Instruction Pointer gets changed so that it points at the instruction we want to run.

We actually combine the test and the jump into a new instruction ‘JNZ xx’ which stands for ‘Jump, if not zero, to memory location xx’. The last thing we need to do is to be able to reduce our number of times by one. We could do this by having a subtraction instruction and subtracting one (or add a negative 1), but since this operation is done so many times in assembly language programming we shall instead apply a special operation called DEC AC, which - as you can probably deduce - means decrement the accumulator, i.e. reduce it by 1.

As you can probably tell - at least I hope so by now - its first three lines simply take what is in the accumulator and add another four to it, before storing it back again. The next three lines grabs our multiplier - the three - reduces it by one, and then stores it back.
Memory address 6 is the key instruction, as it looks at the reduced multiplier - which is still in the accumulator, since storing the contents of the accumulator doesn’t change it - and tests it to see if it is zero. If it isn’t, then the program will jump back to memory location 0 and start again.

If it is zero then the program will just go to the next instruction which is STP and do just that. Run it and see. Hopefully you got the number 12 in memory location 15. If you didn’t, something’s gone a bit awry, and you are going to need to do a little bit of debugging, I’m afraid.

If we want to reuse our code, there are two problems of note. The first is that we need to clear our result, i.e. memory location 15. That’s easy: just store the accumulator to location 15, as we did before. The second is a little trickier: the multiplier (the three that gets reduced to zero) needs to be copies, and then this copy needs to be reduced, rather than the original multiplier.

In this case, we need a temporary variable. Again, this is fairly easy to set up. We just load the multiplier into the accumulator and store it in - say - memory location 12, and then change our program to reduce this number, rather than the original. Notice, also, that by adding in new code we are going to need to change our jump instruction to jump to the correct place. Here is the modified, re-usable code:

MOV [15], AC
MOV AC, [14]
MOV [12], AC
MOV AC, [15]
ADD AC, [13]
MOV [15], AC
MOV AC, [12]
DEC AC
MOV [12], AC
JNZ 3
STP

Remember that you need square brackets for the memory locations. If you forget the square brackets the computer will treat the number as a literal value (and also note, that these literals have a minimum value of 0 and a maximum value of 15)!

Next time

While it may not seem like much, what we have done is actually very impressive. When you think about it, over the course of this article we have designed a machine that can multiply two numbers together. Not only that, but we have created code that can be re-used for any two numbers we input. Well done! 

Next time, we will move on to look at how our Simple Computer might implement these instructions, have a look at the limitations of our machine and, wonder of wonders, we will get it to add up a list of numbers. I’m sure you can’t wait for that!