Links to other weeks notes [ 2 ]( 3 )[ 4 ][ 5 ][ 6 ][ 7 ] 8 ][ 10 ]

## Week 3, 28/31 July 1997

### Summary of MIPS Instructions with an Example

Write a complete MIPS assembly program to verify that 1+2+3+...+n=(1+n)*n/2, for the case of n=3. I.e., compute

```   1 + 2 + 3 - (1 + 3) * 3 / 2.
```
and show that the result is zero. Follow the execution of the instructions.
```main:                            # beginning of the program
li  \$8,  1                    # initial values, \$8 gets 1
li  \$9,  2                    # \$9 gets 2
li  \$10, 3                    # \$10 gets 3
add \$11, \$8,  \$9              # \$11 = 1+2 = 3
add \$11, \$11, \$10             # \$11 = 3+3 = 6
add \$12, \$8,  \$10             # \$12 = 1+3 = 4
mul \$12, \$12, \$10             # \$12 = 4*3 = 12
div \$12, \$12, \$9              # \$12 = 12/2 = 6
sub \$13, \$11, \$12             # \$13 = 6-6 = 0
j \$31                         # end the program
```
The register immediately after an instruction name is the destination register, whose old value is destroyed and is written by the new value. In the case of `add \$11, \$11, \$10`, the second \$11 refers to the value before executing this instruction, and the new result is written back to the same register \$11. That means that the old value 3 is destroyed and new value 6 is set.

### Computer Memory

Memory is a very important part of computer hardware. The main memory is made of semi-conductor chip. The memory is used to store information, e.g., numbers, characters, and graphics. The size of memory is measured in byte. Some other larger units are useful when we talk about memory:

```   1 kilobyte (kbyte) = 1024 bytes    (approximately thousand bytes)
1 Megabyte (MB) = 1048576 bytes    (approximately million bytes)
1 Gigabyte (GB) = 1073741824 bytes (approximately billion bytes)
```
Each binary digit is called a bit. One byte means a sequence of eight bits. For example:
```   01011101
```

Memory Address: Let us think memory as a large hotel with a lot of identical rooms. Each room is used to stuff thing or people. Each room has a room number to identify its location. The memory address is analogous to the room numer of the hotel.

MIPS computer organizes its memory in bytes. Each byte has a unique address, starting from 0, 1, 2, until 2^{32}-1 = 4294967297. MIPS computer can have as large as 4GB memory in theory. Every 4 bytes are grouped together as a word. The address of a word is the same as the first byte with smallest address. The address of a word must be a multiple of 4, e.g., 0, 4, 8, 12, etc. A word has 32 bits.

As you can see, memory and registers have the same function: store information. The difference is that memory is very large but slow. Registers are few but fast. Registers reside on the processor; memory sits on separate memory chips.

### Load and Store Word Instructions

Load and store word instructions are used to transport data between memory and registers. Load is from memory to CPU (registers); and store is the reverse. The syntax of load word is:

```   lw \$8, 0(\$4)
```
which means: use the value in register \$4 as a memory address, load in the value at that address to the register \$8.

Example: What does this program do, assuming that values at memory locations are mem[16] = -1, mem[20] = 7, mem[24] = 20, etc.

```   li \$4, 20             # load immediate value 20 to \$4
lw \$8, 0(\$4)          # load value at mem[20] to \$8, \$8 gets 7
lw \$10, 4(\$4)         # load value at mem[24] to \$10, \$10 gets 20
```
Note the distinction between `li` and `lw`. Load immediate sets the value of a register according to the value supplied by the instruction; it has nothing to do with memory. Load word fetches a value from memory, at the location specified by the address in \$4. Since \$4 is 20, it gets the value at memory location 20, which is 7. The last instruction is 4(\$4). This means the address of 4+\$4 = 4+20=24. At that memory location, we have value 20. So \$10 gets 20.

In general, the syntax of load and store word instructions is

```   lw Destination Reg, offset(Address Reg)
```
any registers can be used to store both values or addresses. The address referenced is offset + value of Address Reg.

More examples:

```   lw \$8, 100(\$2)
```
Register \$8 gets the value at memory location 100 + \$2.
```   sw \$8, 100(\$2)
```
The value in register \$8 is stored back into memory at location 100 + \$2.

Example: Follow a MIPS assembly program execution. The values inside memory and registers are as show. How does the code execute? How do the values in memory and registers change?

```value     0   20    -1    3    1000             memory
reg       \$2  \$3    \$4    \$5    \$6         address    contents

sw  \$4, 0(\$3)                              12    |  3  |
add \$6, \$6, \$3                             16    |  7  |
lw  \$2, -4(\$6)                             20    | 111 |
sub \$5, \$4, \$4                             24    |  77 |
....
1012    |1004 |
1016    |  7  |
1020    |-102 |
```
Answer: the first instruction stores the value in \$4=-1 to memory location \$3=20, so mem[20] becomes -1. The second instruction makes \$6=1000+20=1020. The third instruction loads the value at memory location -4+\$6=1016, which has 7, to \$2. So \$2=7. The last instruction sets \$5 to zero.

Question: The values inside memory and registers are 0 except mem[8]=10. Follow the MIPS instruction execution as in the above example.

```   li  \$4, 1
li  \$2, 4
sw  \$4, 0(\$2)
lw  \$3, 4(\$2)
sw  \$5, 8(\$2)
```

### Binary Numbers

The familiar decimal numbers have ten symbols, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. To represent number larger than 9, we use two symbols. in particular, 9+1=10, with result 0 and a carry 1. Of course, any number can be represented with only ten symbols.

In binary number system, only two symbols are used: 0 and 1. Again, all numbers can be represented with just two symbols.

```     binary         decimal      hexadecimal
0       ->     0              0
1       ->     1              1
10       ->     2              2
11       ->     3              3
100       ->     4              4
101       ->     5              5
110       ->     6              6
111       ->     7              7
1000       ->     8              8
1001       ->     9              9
1010       ->    10              a
1011       ->    11              b
1100       ->    12              c
1101       ->    13              d
1110       ->    14              e
1111       ->    15              f
```
Binary addition and multiplication are quiet simple. Rules for addition: 0+0=0, 0+1=1, 1+0=1, 1+1=10 (result 0, carry to the next digit a 1). Rules for multiplication: 0*0=0, 0*1=0, 1*0=0, 1*1=1. Examples:
```        10                            10
+ 11                          * 11
-------                     ---------
101                            10
+ 10
---------
110
```
The powers of 2 in binary have simple forms (just like powers of 10 in decimal). 10 (2), 100 (4), 1000 (8), and in general 1000...000 with n zeros is 2^n in decimal.

To convert hexadecimal to binary, use the above table of correspondence, prepending zeros if necessary. Hexadecimal to binary, group the bit pattern in 4 bits, starting from the least significant bit. Each 4 bits is mapped to a hexadecimal digit.

### Representing instructions in the computer

The MIPS instruction

```   add \$8, \$17, \$18
```
is represented as (in decimal combinations)
```   0   17   18    8      0     32
```
or more precisely, in machine's bits
```  000000 10001 10010 01000 00000 100000
op    rs     rt   rd   shamt  funct    R-type
```
There are precisely 32 bits (1 word), we divide into 6 fields with 6, 5, 5, 5, 5, and 6 bits each. Each field has a name, as we have labelled above. The op and funct fields specify the type of operations, rs and rt are the source register numbers, while rd is the destination (result) register. Notice that the order is not the same as in assembly statement. Shamt is shift amount (not used for this instruction).

For the lw instruction of

```   lw \$8, 1200(\$19)
```
the machine instruction (decimal) is
```   35  19   8   1200
```
or (binary)
```   100011 10011 01000 0000010010110000
```

### Stored-program concept

The Big Picture:

1. Instructions are represented as numbers; and
2. Programs can be stored in memory to be read or write just like numbers.