The Rules

Now for some rules. Each page in the notebook can be empty or contain the number zero or the number one. There are only a few actions you’re allowed to take, and we label them with some shorthand:

The Action Table

One of our two pieces of paper will contain the “action table”, which represents the program that the computer executes. It can be drawn out as a table as follows:

This table is just a set of simple rules: if you read the symbol in the first column then carry out the actions in the second column. So, if we start with the first page of a blank notebook, it will read E (empty) and so write a 1 on the page (W1) and move forward to the next page (+). Crucially, it then repeats.

So this rather silly program will just write a one on every page in the notebook. (There’s clearly a problem when we reach the end of the notebook, but let’s ignore that for now!).

Adding Global State

If you play around with what we have so far, you’ll find this action table is pretty limiting. We don’t, for example, have a way to say “write only ones on the first two pages”. We fix that by creating multiple sets of actions for the same input. In order to decide which set to run, we need the system to have a simple ‘state’, which in our case will be a letter (A,B,C,..) on the second piece of paper. We’ll have a special state (label it ‘H’ for halt) that causes our program to terminate.

Now, we also need to extend our action table:

What does this do? Starting with the first page (assumed empty) and in state A we first follow this line:

And so we write 1 on the first page, move forward one page and update the state to B. Now we read another empty page but we’re in state B so we follow this line:

Which writes a 1 and ends the program (state H). The result is that it wrote ones to the first two pages (only).

A More Interesting Program

Let’s develop the equivalent of the counting program you can find at the aturingmachine.com site:

Our version will start with an empty notebook and count in binary, overwriting any previous number with its successor. For example, if the notebook currently contains the value 7 in binary, then after the action table instructions have been followed the value 8 in binary will be written in the notebook. To do this, you obviously need to understand how binary addition works. If you don’t, then you should look at the other mini-course in this series on Bits, Bytes and Number Systems before proceeding.

We’ll need four states: States A and A’ will initialise the last page to 1. State B will move through the notebook until we find the last non-blank cell in the notebook. State C will handle the adding and carrying of bits. State A is very easy to define:

This moves us through the notebook until we find the back cover, then moves us one page back, writes a 1 and moves to state B.

State B is the start of our main cycle. It moves forward through the notebook until it finds the (back) cover, then it goes back one page and moves into state C. So we have:

State C is the only clever bit. When we move into it we’ll be looking at the last page thanks to state B. So we know we’re looking at the Least Significant Bit (LSB) of the binary number. If it’s a zero, we just change it to a one and we’re done with this number and the cycle starts again with state B:

If it’s a one, we turn it to a zero and repeat state C starting on the previous page (in effect we carry the bit to the left). We are done with this number when we find a zero, or we find an empty page, or we get to the front cover. So:

Now, if it was a 0, we have just changed it to a 1 and there is no carry so we are done. We can move onto the next integer by switching back to state B:

Putting all that together we get:

If you find this all quite easy, it’s a useful exercise to wrtie some of your own ‘programs’ for this system. As optional challenges:

• Can you write a version of the counting program so the MSB of the number is always on the first page (i.e. not start at the last page)?

• Can you write a program to countdown from ten (you’ll need to initialise it to ten and implement subtraction! This is quite hard)?

Memory

For this course we don’t need to delve into the gory details of computer memory technology, but it is useful to have a high-level idea of how it works. Computer memory is a very large collection of memory cells, which are just small electronic circuits that can store a single bit (i.e. 0 or 1). There are various types of memory cell available, but we generally look for the fewest components possible (cheaper and smaller).

The cells are usually arranged in a grid like this. The idea is that a specific bit can be read or written by first selecting a row and then a column using electronic switches (transistors). The interesting thing about this is that it takes the same time to access the first cell as the last one. We have what we call Random Access Memory (RAM) since we can randomly jump around reading data without a latency penalty (alternatives to RAM are discussed at the end of this section). You will likely come across two types of RAM cells: DRAM and SRAM (others do exist but these two are dominant):

• Dynamic RAM (DRAM). A DRAM cell is basically a capacitor and a transistor. You may recall from physics lessons that a capacitor can be used to store charge: you pump it in, then you can take it out when you want. This makes it an obvious choice: we can use a discharged capacitor to represent a ‘0’ and a charged capacitor a ‘1’. The transistor is just a switch that selects the charge or discharge mode. Simple, cheap and space-efficient. But there’s a problem: charged capacitors naturally leak charge over time. So 1s eventually become 0s! To fix this you need to regularly stop all memory accesses, and look at each capacitor to decide whether its charge needs to be topped up or not. This refresh cycle has to occur hundreds of times each second and, while it’s happening, the DRAM is essentially useless. This refresh operation is handled inside the memory chip itself.

• Static RAM (SRAM). An SRAM cell is a collection of four to six transistors forming what is called a bi-stable circuit. This solution has the advantage of faster read and write times, but the extra components are expensive and make the cells rather large (limiting capacity when compared to DRAM).

In practice, the 16GB or so of memory that our computers come with is almost entirely DRAM. The cheaper, smaller cells keep costs down so, for a given amount of money, you can buy more RAM. There is a performance penalty associated with constantly having to refresh, but in modern DRAM implementations this is not significant.
That said, there are parts of a computer where we just can’t be waiting for DRAM operations to complete. So we use small chunks of SRAM (MB not GB) wherever we need really fast performance (e.g. within the CPU as you’ll see).

One more thing on memory before we move on. We know that if nothing refreshes a cell, the information is eventually lost. So data only survives while the computer is powered on and hence able to refresh the cells. We call this volatile memory (power off, data lost). We therefore need some form of non-volatile memory (power off, data intact) to store things between power cycles. For today’s computers that means a hard disc, which you get in one of two flavours:

• HDD. A traditional Hard Disc Drive has a spinning platter with lots of tiny magnetic ‘pits’ on it. There is a read and a write head (think CD player on steroids) that can measure or change the magnetic state of the pit beneath it as the platter spins. This is a form of Sequential Access Memory (SAM) since we can’t just jump randomly to a pit: we have to wait until it comes round on the platter. HDDs offer an excellent capacity-to-cost ratio. However, they are painfully slow compared to RAM.

• SSD. A Solid State Disc (SSD) uses the same core technology as USB sticks to store data without power. The physics behind them is rather complex and beyond scope here. The key points are they’re not cheap and they don’t quite have the performance of RAM, but they are random access and still much faster than a HDD. Costs seem to be falling fast at the moment as data capacities increase.

The CPU

We’ll use a (highly simplified) model of a computer as illustrated above. It contains three hardware components: a Central Processing Unit (CPU), some main memory (DRAM), and something to interconnect the two (a motherboard). Although we’ve just delved into the innards of the memory, all we care about here is that there are a number of memory `slots’, each a byte in size, and each addressable through some unique number:

The CPU is really a collection of electronic circuits that includes:

• A register bank. Small chunks of super-fast SRAM memory embedded in the CPU to store internal data/state being worked on. We might have just tens of registers, each of size 64 bits (yes, just bits).

• An Instruction Buffer (IB). A special register that holds a copy of the current instruction (action table rule) we are dealing with.

• A Program Counter (PC). A special register that holds the memory address of the next instruction to be processed.

• A Memory Access Unit (MAU). A piece of electronics that shifts data back and forth between main memory (DRAM) and the registers. A CPU can only act on values in registers.

• An Arithmetic Logic Unit (ALU). A piece of electronics that can read integer values from the registers and perform arithmetic (addition, multiplication, etc.) on them, storing the result back in another register.

• A Branching Unit (BU). Some electronics that allows us to execute conditional behaviour (e.g. if A then B else C). We’ll come back to this.

The last three in that list are known as functional units of the CPU. A modern CPU has many functional units, each carrying out a specialised task such as the ones above.

How much Memory can we use?

A consequence of this CPU structure is that the PC register (the one that contains the memory address of the next instruction) is of finite size. What this means is that there are only a finite number of memory slots that a given processor can support.

Rewind around 10 years and CPUs were mostly 32-bit (i.e. their registers were 32 bits long). So you simply couldn’t use more than 4GB of memory. So we moved to 64 bits. Which is more than anyone could ever need…err, right? ;-)

L-0x23-1   # Load first value (currently at memory slot 0x23) into register 1
L-0x24-2   # Load second value (currently at memory slot 0x24) into register 2
A-1-2-3    # Add the values and store the result in register 3
S-3-0x25   # Store the answer in register 3 in main memory (slot 0x25)

The Fetch-Execute Cycle

The Fetch-Execute (or Fetch-Decode-Execute) cycle is the name given to what the CPU does. It maps directly to what you were doing when you worked through the notebook example: you figured out which line of the action table to read, then deciphered it and made any changes necessary, before repeating that process. Here it breaks down to:

• Fetch the next instruction from main memory. This involves feeding the MAU with the memory address in the Program Counter and telling it to store it in the Instruction Buffer. After doing this the Program Counter is incremented.

• Decode the instruction in the Instruction Buffer. This just means figuring out which functional unit to send it to and doing so.

• Execute the instruction within the chosen functional unit.

The CPU just does this cycle over and over forever. Incrementing the Program Counter ensures we don’t just execute the same instruction forever. The figure below illustrates the whole tedious process necessary just to add two integers.

You’re probably aware that CPUs have frequencies associated with them—e.g. Intel i7 3GHz. This is the frequency at which the CPU can complete cycles. So a 3GHz machine can do 3,000,000,000 cycles (=instructions) a second! Really it’s not what computers can do, but how fast they can do it that is impressive.

Where is the program stored?

Note that the figures above show the program shoved somewhere in the same memory as the data (i.e. the numbers 63, 12, and 75). This makes our main memory a jumbled interleaving of code (instructions) and data.

This is an interesting choice that has some quite serious consequences. In particular, it allows for a program to write data into a slot containing an instruction, thereby wiping out that part of the program. This might be accidental (in which case the program will crash when it gets to that memory slot and tries to treat it as an instruction) or deliberate.

0x77  L-0x23-1         # Load first value (currently at memory slot 0x23) into register 1
0x78  L-0x24-2         # Load second value (currently at memory slot 0x24) into register 2
0x79  L-0x25-3         # Load third value (currently at memory slot 0x25) into register 3
0x7A  B-1-0x7B-0x7E    # If register 1's value is > 0 then go to 0x7B else 0x7E
0x7B  A 1-2-4          # Add the values in registers 1 and 2 and store in 4
0x7C  S-4-0x26         # Store the answer in register 4 in main memory (slot 0x26)
0x7D  H                # Halt
0x7E  A 2-3-4          # Add the values in registers 2 and 3 and stores in 4
0x7F  S-4-0x26         # Store the answer in register 4 in main memory (slot 0x26)
0x80  H                # Halt

Machine Code

We have considered a very generic, simplified CPU with a very limit set of instructions. A real instruction is a binary number that can be stored in the instruction buffer (and so is limited in size to the instruction buffer). Here’s an example for a MIPS processor:

A program is just a sequence of instructions in a form understood by the processor. We call this form machine code. It’s perfect for a computer, but very hard for a human to work with.

   lw     $t0, 4($gp)       # Load value (n) at address 4 in main memory ($gp) into register $t0
   addi   $t0, $t0, 3       # Add 3 to the value (n=n+3)
   mult   $t0, $t0, $t0     # Square the value (n=n*n)
   sw     $t0, 0($gp)       # Store the answer back in main memory, address 0