Transcript if - Seattle Pacific University

Taking orders
• A computer does what you tell it to do
• Not necessarily what you want it to do...
• We give computers orders by means of instructions
• Instructions tell the computer what it should be doing,
right now
• Arithmetic
• Logic
• Data movement
• Control
Seattle Pacific University
EE/CS/CPE 3760 - Computer Organization
Ch2a- 2
Binary review
Binary representations of numbers consist of only 1’s and 0’s
01012 = 510
10002 = 810
11111112 = 12710
Unsigned (always positive)
binary numbers
Seattle Pacific University
Binary Facts:
210 = 1024 = 1K 1,000
220 = 1,048,576 = 1M 1,000,000
230 = 1,073,741,824 = 1G 1,000,000,000
Being fluent in binary is highly underrated
on the dating scene
EE/CS/CPE 3760 - Computer Organization
Ch2a- 3
Converting between binary and hex
Binary
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Hexadecimal
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
Seattle Pacific University
Group bits together in groups of 4
10001100101100100001112
--> 10 0011 0010 1100 1000 01112
Assign the appropriate hex digit to each group
10 0011 0010 1100 1000 01112
--> 2 3
2
C
8
7
Done
= 232C8716
EE/CS/CPE 3760 - Computer Organization
Ch2a- 4
The Translation Process
Computers speak in binary. We don’t.
(Exception: Geeks)
High-level language
A=B+C
Assembly language
Compiler
add
$1, $2, $3
Compilers and Assemblers
translate from one language
to another.
Assembler
Machine language
000000 00010 00011 00001 00000 100000
Seattle Pacific University
EE/CS/CPE 3760 - Computer Organization
Ch2a- 5
MIPS Instructions
Operation
add
Destination
A,
B,
Sources
C
A=B+C
sub
D,
A,
D =A-B
Seattle Pacific University
B
In MIPS,
All register-to-register
arithmetic instructions
have three operands.
EE/CS/CPE 3760 - Computer Organization
Ch2a- 6
Operands
add
A, B, C
What are A, B, and C?
The operands of arithmetic instructions are always registers
add
$17, $18, $19
Add contents of registers 18 and 19 and put result in register 17
sub
$19, $19, $18
Subtract $19 - $18 and put the result back in $19
Seattle Pacific University
EE/CS/CPE 3760 - Computer Organization
Ch2a- 7
Registering
$2
47
• MIPS has 32 general-purpose registers
• $0 through $31
• Each register holds 32 bits
• 0 to 232 -1 (4 billion) if unsigned
• -231 to +231-1 (-2 billion to +2 billion) if signed
• Most registers can hold any value, for any purpose
• Exception: $0 is always zero!
Seattle Pacific University
EE/CS/CPE 3760 - Computer Organization
Ch2a- 8
Register Naming and Conventions
• In MIPS, all registers (except $0) can be used for any purpose
desired
• However, there are standard use conventions that make it
easier to write software
#
$0
$1
$2
$3
$4
$5
$6
$7
$8
$9
$10
$11
$12
$13
$14
$15
Name
$zero
$at
$v0
$v1
$a0
$a1
$a2
$a3
$t0
$t1
$t2
$t3
$t4
$t5
$t6
$t7
Purpose
Constant zero
Reserved for assembler
Function return value
Function parameter
Temporary – Caller-saved
Seattle Pacific University
#
$16
$17
$18
$19
$20
$21
$22
$23
$24
$25
$26
$27
$28
$29
$30
$31
Name
$s0
$s1
$s2
$s3
$s4
$s5
$s6
$s7
$t8
$t9
$k0
$k1
$gp
$sp
$fp
$ra
Purpose
Temporary – Callee-saved
Temporary – Caller-saved
Reserved for OS
Global pointer
Stack pointer
Frame pointer
Function return address
EE/CS/CPE 3760 - Computer Organization
Ch2a- 9
Reflections on Registers
• Registers are just “special” memory locations
• A small number of registers, as opposed to a huge
number of memory locations
• Because there are a small number of registers,
accessing them is fast
• Principle: Smaller is usually faster.
• Trade-offs
• More registers --> More data in fast memory -->
Faster execution
• Fewer registers --> Registers are faster --> Faster
execution
• Compromise: 16 to 32 registers works well
Seattle Pacific University
EE/CS/CPE 3760 - Computer Organization
Ch2a- 10
Complicated arithmetic
F = (A + B) - (C + D)
Assume:
A is in $8
B is in $9
C is in $10
D is in $11
F is in $12
add
add
sub
$12 = ($8 + $9) - ($10 + $11)
Note:
Typically, the compiler
assigns variables to
registers
$13, $8, $9
$14, $10, $11
$12, $13, $14
Seattle Pacific University
We don’t have a 5-operand
add/subtract instruction!
Use temporary variables to
solve the problem.
# $13 <-- A + B
# $14 <-- C + D
# F <-- (A+B) - (C+D)
$13 and $14 are
temporary variables
EE/CS/CPE 3760 - Computer Organization
Ch2a- 11
Getting to the bits of it all
We’ve looked at assembly language (briefly)
The CPU wants bits.
R-Type Instruction
add
$13, $8, $9
Assembler
000000 01000 01001 01101 00000 100000
0
Opcode
32 bits, total
Seattle Pacific University
8
9
RS
RT
13
0
32
RD ShAmt Function
6 bits
5 bits
5 bits
5 bits
5 bits
6 bits
0 = Add
$8
$9
$13
0
32=Add
EE/CS/CPE 3760 - Computer Organization
Ch2a- 12
Staying Regular
R-Type instructions all have the same format:
Opcode
6 bits
RS
5 bits
RT
5 bits
RD ShAmt Function
5 bits
5 bits
6 bits
Add has an opcode of ‘0’, a function of ‘32’
add $13,$8,$9: 000000 01000 01001 01101 00000 100000
Subtract has an opcode of ‘0’, a function of ‘34’
sub $13,$8,$9: 000000 01000 01001 01101 00000 100010
The instructions differ only in one bit!
Regularity:
Similar functions should be similar in format.
Seattle Pacific University
Regularity is a key
to high-performance
EE/CS/CPE 3760 - Computer Organization
Ch2a- 13
Constants
Many times, an instruction needs to use a constant value
• Multiply by 4
• Add 3
Instructions with constant data in them are called immediate instructions
• addi $12, $10, 4
# Reg. 12 <-- Reg. 10 + 4
add
immediate
I-Type instructions all have the same format:
Opcode
RS
RT
6 bits
5 bits
5 bits
8
10
12
001000 01010 01100
Seattle Pacific University
I-Type Instruction
Immediate Data
16 bits
4
0000 0000 0000 0100
EE/CS/CPE 3760 - Computer Organization
Ch2a- 14
Doing Double Duty
• You desire to copy the value in register $8 to $10
• Called a “move” in computer terms
• move $10, $8
#copy register $8 to $10
• Doesn’t exist in MIPS assembly language!
• add $10, $8, $0
# adds zero and $8, result in $10
• Does the same thing as a move
• Allows the add instruction to serve double duty!
• Many instructions have double/triple functions
• sub $8, $0, $8 # negate $8
• addi $12, $0, 4 # load register $12 with value 4
Seattle Pacific University
EE/CS/CPE 3760 - Computer Organization
Ch2a- 15
Boooooring
A = B+C
• Straight-line code is nice,
but boring
• Just arithmetic and
loads/stores based on a
predetermined sequence
• Decision-making elements
add some spice to the
equation
• Control allows programs to
make decisions based on
their current state
• The most common control
structure is the branch
Seattle Pacific University
D = B+F
M[18]=D
D = B+F
D>23?
Y
N
M[22] = D
C = B+A
EE/CS/CPE 3760 - Computer Organization
Ch2a- 16
Going places
Consider the lowly GoTo
if (x == y) q = 13;
Next:
if (x != y) GoTo Next;
q = 13;
...
if (p > q) r = 3; else r=2;
while (y < 2) y = y+1;
Loop:
End:
if (y >=2) GoTo End;
y = y+1;
GoTo Loop;
...
Seattle Pacific University
R3:
Next:
if (p>q) GoTo R3;
r = 2;
GoTo Next;
r = 3;
...
if (condition) GoTo location and
GoTo location are all we need
EE/CS/CPE 3760 - Computer Organization
Ch2a- 17
Branching out
if ($9 == $10) GoTo Label;
beq
beq - Branch if EQual
$9, $10, Label
if ($7 != $13) GoTo Next;
bne
bne - Branch if Not Equal
$7, $13, Next
Branches need:
Opcode
Two registers to compare
Location to go to
I-Type Instruction
Opcode
6 bits
RS
5 bits
Seattle Pacific University
RT
5 bits
Immediate Data
16 bits
More details on specifying
the branch target in
immediate data later
EE/CS/CPE 3760 - Computer Organization
Ch2a- 18
Unconditional branches - Jumps
GoTo Exit;
j
Exit
j - Jump (unconditionally)
Jumps need only an opcode and data There is a lot more room for the data...
J-Type Instruction
Opcode
Immediate Data
6 bits
Seattle Pacific University
26 bits
More details on specifying
the jump target in
immediate data later
EE/CS/CPE 3760 - Computer Organization
Ch2a- 19
IF-Then Structures
if $x == $y then S1
S2
S1 should be executed if $x == $y is True
If $x != $y, or after S1 is executed, S2 is executed
False:
bne
S1
S2
$x, $y, False
# if $x != $y, skip S1
# $x == $y, execute S1
# either way we get here, execute S2
If you can’t express the condition as a negative, try this:
True:
False:
beq
j
S1
S2
$x, $y, True
False
Seattle Pacific University
# if $x == $y, then execute S1
# $x != $y, so exit
# $x == $y, execute S1
# either way we get here, execute S2
EE/CS/CPE 3760 - Computer Organization
Ch2a- 20
IF-Then-Else Structures
if $x == $y then S1 else S2
S3
S1 should be executed if $x == $y
S2 should be executed if $x != $y
After executing S1 or S2, execute S3
IF:
Finish:
beq
S2
j
S1
S3
$x, $y, IF
Finish
Seattle Pacific University
# if $x == $y, goto S1, skip S2
# $x != $y, execute S2
# now execute S3
# $x == $y, so execute S1
# either way, we do S3 afterwards
EE/CS/CPE 3760 - Computer Organization
Ch2a- 21
While Loops
while $x == $y do S1
Execute S1 repeatedly as long as $x == $y is true
Repeat: bne
S1
j
Exit:
$x,$y, Exit
Repeat
# exit if $x != $y is False
# execute body of loop
# do it all over again
# end of the loop
Warning: The following loop always executes at least once,
no matter what $x and $y are:
Repeat: S1
beq
Exit:
$x,$y, Repeat
Seattle Pacific University
# execute body of loop
# do it again if $x == $y
# end of the loop
EE/CS/CPE 3760 - Computer Organization
Ch2a- 22
For Loops
for i = $start to $finish {S1}
S2
Use temporary, $t0 to hold i
Execute S1 for all values from $start to $finish (step of 1)
Loop:
done:
add
bgt
S1
addi
j
S2
$t0, $start, $0
# copy start to i ($t0)
$t0, $finish, done # if i > finish, then we’re done - do S2
# execute S1
$t0, $t0, 1
# increment count
Loop
# go again
Note: bgt doesn’t really exist - more on that next...
Seattle Pacific University
EE/CS/CPE 3760 - Computer Organization
Ch2a- 23
Other conditions
slt
Set on Less Than
$4, $10, $11
Set $4 = 1 if ($10 < $11), otherwise $4 = 0
if ($7 < $8) then $15 = 3;
slt
beq
addi
$1, $7, $8
$1, $0, GoOn
$15, $0, 3
Example: $7=4, $8=9
$1 = 1 ( $7 < $8)
$1 0, Don’t branch
Set $15 to 3
Example: $7=4, $8=2
$1 = 0 ( $7 > $8)
$1 == 0, Branch
GoOn ($15 not changed)
# $1 <-- ($7 < $8)
# If not less than, go on
# ($7 < $8), so $15 <-- 3
GoOn:
if ($12 >= $3) then $4 = $2;
slt
bne
add
$1, $12, $3
$1, $0, GoOn
$4, $2, $0
Example: $12=4, $3=2
$1 = 0 ( $12 > $3)
# $1 <-- ($12 < $3)
$1 == 0, Don’t branch
# If less than, go on
# ($12 >= $13), so $4 = $2 Set $4 to 2
GoOn:
Seattle Pacific University
EE/CS/CPE 3760 - Computer Organization
Ch2a- 24