How Does a Computer Work?

--- tags: programming languages, compiler construction --- # How Does a Computer Work? We are going to build (virtually) a simple computer. It consists of a memory containing the data and the program and a central processing unit (CPU) that executes the program on the data by modifying the content of the memory. ## The algorithm Our example program needs to be simple, but not too simple. I chose the greatest common divisor. Here is a high-level description. > `gcd(a,b)`: > > Input: Two whole numbers (integers) called `a` and `b`, both greater than `0`. > > (1) if `a>b` then replace `a` by `a-b` and goto (1). > (2) if `b>a` then replace `b` by `b-a` and goto (1). > > Output: `a`. (As usual, this algorithm is to be read in a top down manner, line by line, unless there is an explicit instruction to go to some particular line other than the next one.) **Exercise:** Convince yourself that by the time the algorithm reaches the line labelled "Output", it is the case that the value of `a` equals the value of `b`. **Exercise:** Detail the steps for `a=12` and `b=8`. Do this by completing the following table. | Step | `a` | `b` | |:---:|:---:|:---:| |Input|12|8| |(2)|4|8| |...|...|...| What is the result (output) of the algorithm? **Exercise:** Detail all the steps for `a=9` and `b=33`. Do this by completing the following table (you may have to add rows this time). | Step | `a` | `b` | |:---:|:---:|:---:| |Input|9|33| |(2)|9|24| |...|...|...| What is the result of the algorithm? **Exercise:** Make examples of your own. The aim of this note is to give a first understanding of how such an algorithm is executed on a computer. If we didn't know about computers, we could invent one by thinking about what is needed for a machine to be able to create tables such as the one above. It would also be fun to do this on an actual microchip, but this would involve learning many details particular to this one microchip and take more time. Instead I will invent a "virtual" computer architecture that is more abstract but contains the most important features. ## Computer architecture Let us first look at some of the big ideas of [computer architecture](https://en.wikipedia.org/wiki/Computer_architecture). One of the principles of a modern computer is that data and program both reside in the same memory. Moreover, both the data and the program are just a sequence of bits. And a sequence of bits is just a number (in base 2). So we can see the content of the computer memory as just one big number and a computation as a function taking one input number to one output number. But this point of view, while sometimes interesting, does make understanding computation quite cumbersome. So instead we follow standard practice and devide the computer memory in small chunks, called [words](https://en.wikipedia.org/wiki/Word_(computer_architecture)), each having an address. The [CPU](https://en.wikipedia.org/wiki/Central_processing_unit), or central processing unit, executes a program by operating on the memory. The basic computational mechanism, the so-called [instruction cycle](https://en.wikipedia.org/wiki/Instruction_cycle), is the following. (1) Fetch the next instruction from the memory. (2) Read data. (3) Execute the instruction on the data. (4) Go to (1). **To summarize:** - The memory is a sequence of memory cells, each of which has an **address** and a content which stores a **word**, which is a sequence of bits of a fixed given length (8 bits below). - The **CPU** (central processing unit) reads both the program and the data from the memory, executes one instruction at a time, and writes the results back to memory. In the following, we will look in more detail how the algorithm `gcd(a,b)` is executed in a computer. To simplify matters, I will invent my own hardware, machine language and assembly language, abstracting away from most of the details. ## My hardware I assume that I have a minimal hardware that can execute `gcd(a,b)`: - Memory has words of length 8 bit. - Addresses are 4 bits long. (Hence, the largest addressable memory has only $2^4=16$ words.) - The CPU has a program counter (PC) and two registers, called R1 and R2. - Binary operations (such as addition) take the content of the two registers and write the result in R1. Unary operations (such as negation) take the input from R1 and write the output to R1. To understand the following, it is probably best to read it in conjunction with the example below. - The CPU can test whether Register 1 is equal to 0, or greater 0, or smaller 0. - The CPU can jump to a specified address. This is implemented by updating the program counter. To understand how tests and jumps work, see the example below. Finally, we make the convention that computation starts by initializing the program counter with the address stored at address 0. **Remark:** The fact that at an address we can store addresses is a crucial ingredient of programmable computers. Addresses denote the place where data is stored, but can also be data themselves. [^geb] [^geb]: To learn more about such "strange loops" I recommend the book [Goedel, Escher, Bach](https://www.physixfan.com/wp-content/files/GEBen.pdf). **Remark:** In particular, programs can change themselves during execution. This is a very interesting fact that we do not pursue any further in the following. [^geb2] [^geb2]: [Goedel, Escher, Bach](https://www.physixfan.com/wp-content/files/GEBen.pdf) contains much more about this topic. ## My machine code [Machine code](https://en.wikipedia.org/wiki/Machine_code) is the generic term for the family of programming languages that can be directly executed by a CPU. Each microchip (CPU) comes with its own "native" machine language. In the following I will invent only enough of a machine language to execute the program `gcd(a,b)`. The numbers in the first column below have no deeper significance. For our purposes, it is only important that each instruction has a unique code and that the machine is "hardwired" to execute the coded instruction. Read through the right-hand column of the table below and remember, roughly, which operations our machine can execute. (It is safe to ignore the left-hand column for now.) (If you know programming languages such as C, Java or Python you will be familiar with notation such as `R1=R1+R2`. If not, read this as: add R1 and R2 and store the result in R1.) |machine code | comment |:---:|:---:| | 1000wxyz | read content of address wxyz into register R1 | 1100wxyz | read content of address wxyz into register R2 | 1110wxyz | write content of register R1 to address wxyz | 01000000 | R1 = R1 + R2 | 00000000 | R1 = -R1 | 0010wxyz | if R1=0 then jump to address wxyz | 0011wxyz | if R1>0 then jump to address wxyz | 0001wxyz | if R1<0 then jump to address wxyz | 1111wxyz | jump to address wxyz | 00000001 | print content of R1 Technically, "jump to address wxyz" means update the program counter to wxyz. ## My assembly code Machine code is considered to be unreadable for humans. Assembly[^assembly] is the generic name for programming languages which are still very close to machine language, but offer somewhat better readability.[^assemblyHistory] In the following, I make something up for illustrative purposes. [^assembly]: [Wikipedia](https://en.wikipedia.org/wiki/Assembly_language) has more information on assembly. In particular, I want to quote ![](https://hackmd.io/_uploads/rJX64m0ot.png) [^assemblyHistory]: Assembly was invented in the late 1940ies as a high-level language to replace machine language. Much of the programming in the 50ies and 60ies was done in assembly, in particular for [systems programming](https://en.wikipedia.org/wiki/Systems_programming#History). In the 70ies [C](https://en.wikipedia.org/wiki/The_C_Programming_Language) became popular for this purpose and today assembly is mostly used as the target language for [compilers](). We will look at the details of how compilers work in a subsequent note. (The first two columns below are identical to the table above.) |machine code | comment | assembly |:---:|:---:|:---:| | 1000wxyz | read content of address wxyz into register R1 | READ1 wxyz | 1100wxyz | read content of address wxyz into register R2 |READ2 wxyz | 1110wxyz | write content of register R1 to address wxyz|WRT1 wxyz | 01000000 | R1 = R1 + R2 | ADD | 00000000 | R1 = -R1 | NEG | 0010wxyz | if R1=0 then jump to address wxyz | IFEQ wxyz | 0011wxyz | if R1>0 then jump to address wxyz | IFGR wxyz | 0001wxyz | if R1<0 then jump to address wxyz | IFSM wxyz | 1111wxyz | jump to address wxyz | GOTO wxyz | 00000001 | print content of R1 | PRINT Some of the typical instructions for assembly code are read, write and goto. These are instructions you will rarely see in most modern high-level programming languages such as Python, Java, C, etc. If you take a closer look, you will see that these instructions mention particular addresses (such as wxyz). High-level programming language hide these aspects of memory management from the programmer. **Exercise** (optional): Before going to the example below, you may want to think about how to write `gcd(a,b)` in the assembler language above. ## Example After these preliminaries, we are now able to illustrate how `gcd(a,b)` may look in the machine language of a computer. In the following, let `a=8` and `b=12`. (The comma in the second column is only meant to improve readability.) |address | content | assembly | comment |:---:|:---:|:---:|:---:| |0| 0000,0011 || address where the program starts: 3 |1| 0000,1000|| first input: 8 |2| 0000,1100|| second input: 12 |3| | READ1 0001 | read content of address 2 to R1 |4| | NEG | R1 = -R1 |5| | READ2 0010 | read content of address 1 to R2 |6| | ADD | R1 = R1 + R2 |7| | IFEQ 1001 | if R1=0 goto 9 |8| | IFGR 1010 | if R1>0 goto 10 |9| | IFSM 1100 | if R1<0 goto 12 |10| | PRINT | print R1 |11| | WRT1 0001 | write content of R1 to address 1 |12| | GOTO 0011 | jump to address 3 |13| | NEG | R1 = - R1 |14| | WRT 0010 | write content of R1 to address 2 |15| | GOTO 0011 | jump to address 3 **Remark:** It is temtping to abbreviate some of the comments as follows. In line 3: `R1 = addr_2`. In line 11: `addr_1 = R1`. Etc. This would be in line with the use of `=` in programming languages such as C, Java or Python. (Registers and memory cells correspond to the variables in programming languages such as C, Java or Python.) **Exercise:** Pretend to be the CPU and execute the program. To do this, at each point in time, you need to keep 3 pieces of information in your CPU: the program counter, register 1 and register 2. Picture the computation as a squence of "cards", one card for each point of time, and each card containing the content of the program counter, register 1 and register 2. **Exercise:** The program in the table had to be adapted to the instructions available in the machine. Convince yourself that it indeed computes `gcd(a,b)`. **Exercise:** Go back to the section on the machine language and fill out the second column. The second column will then correspond to the content of the memory just before the execution of `gcd(8,12)`. ## GCD on the Little Man Computer In the interest of simplification, the (virtual) hardware, machine language and assembly language above contain just enough to explain our example of gcd. But with a bit more effort one can write assembly programs that can be run on a machine. Sri Pranav Kunda implemented the following version of gcd on the [Little Man Computer](https://en.wikipedia.org/wiki/Little_man_computer): ```lcm INP STA A INP STA B SUB A BRZ 17 BRP 13 BRA 8 LDA A SUB B STA A LDA B BRA 4 LDA B SUB A STA B BRA 4 LDA A OUT HLT A DAT B DAT ``` To run the code, go to the [web interface](https://peterhigginson.co.uk/LMC/) and paste the code in the left-hand column, click "Submit", then "RUN", then enter the numbers in "INPUT", eg $8$ and $12$. **Exercise:** Follow the computation step by step, reading through [the commented code](https://pastebin.com/tvhWafNk) as well as the [documentation](https://peterhigginson.co.uk/LMC/help.html).