Links to other weeks notes [ 2 ]( 3 )[ 4 ][ 5 ][ 6 ][ 7 ] 8 ][ 10 ]
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 programThe 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.
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 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 20Note 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) sw Source 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) add $5, $3, $4 sw $5, 8($2)
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.
The MIPS instruction
add $8, $17, $18is represented as (in decimal combinations)
0 17 18 8 0 32or 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 1200or (binary)
100011 10011 01000 0000010010110000
op rs rt address I-type
The Big Picture:
The textbook, "Computer Organization & Design", page 98-108.
[ previous week ][ next week ]