Idea Transcript
CS 2630 Computer Organization Meeting 6: Stored programs Brandon Myers University of Iowa
Peer instruction What value is stored in $t0 when the program finishes?
(numeric response)
Where we are going Compiler
Instruction set architecture (e.g., MIPS) Memory system
Processor Datapath & Control Digital logic
translating source code (C or Java) Programs to assembly language And linking your code to Library code How the software talks To the hardware I/O system How a processor runs MIPS Programs! How switches (1 or 0) can be used to build Interesting functions: from integer arithmetic to programmable computers
Where we are going
Instruction memory
Learn what gets stored in here
Execution engine
Data memory
Storing an instruction as bits • each MIPS instructions is 32 bits, stored in “instruction memory” contents
meaning
address 0000
8e
13
00
00
lw
$s3, 0($s0)
0004
8e
14
00
04
lw
$s4, 4($s0)
0008
02
74
90
20
add
$s2, $s3, $s4
000C
ae
12
00
08
sw
$s2, 8($s0)
0010
22
10
00
04
addi $s0, $s0, 4
0014
22
31
ff
ff
addi $s1, $s1, -1
0018
1e
20
ff
f9
bgtz $s1, loop
Storing an instruction as bits each MIPS instructions is 32 bits, stored in “instruction memory” contents
meaning
address 0000
8e
13
00
00
lw
$s3, 0($s0)
0004
8e
14
00
04
lw
$s4, 4($s0)
0008
02
74
90
20
add
$s2, $s3, $s4
000C
ae
12
00
08
sw
$s2, 8($s0)
0010
22
10
00
04
addi $s0, $s0, 4
0014
22
31
ff
ff
addi $s1, $s1, -1
0018
1e
20
ff
f9
bgtz $s1, loop
R-type
opcode = 0 for R-type and funct is this
R-type
opcode = 0 for R-type and funct is this
Example: 3 steps to translate from human code to machine code
R-type
opcode = 0 for R-type and funct is this
Example:
0x00
8
9
13
step 1: fill in the fields
0
0x20
R-type Example:
0x00
8
9
13
0
0x20
000000 01000 01001 01101 00000 100000
step 2: write as a 32-bit binary number
R-type Example:
0x00
8
9
13
0
0x20
000000 01000 01001 01101 00000 100000 0x01096820
step 3: typically write the code as hex, so translate to hexadecimal by turning each 4 bits into a digit
I-type
Example:
0x09
10
14
-1
001001 01010 01110 11111 11111 111111 0x254EFFFF MIPS green sheet, P&H
Peer instruction Give the 32-bit representation of this instruction
a) b) c) d) e)
0x00231025 0x014B4825 0x00430825 0x00611025 0x01695025
• QUESTIONS FOR NEXT TIME • what if too big for 16 bits? • will the funct ever be bigger than 6 bits?
http://qz.com/726338/the-code-that-tookamerica-to-the-moon-was-just-published-togithub-and-its-like-a-1960s-time-capsule/
lots more info: http://tcf.pages.tcnj.edu/files/2013/12/Apollo-Guidance-Computer-2009.pdf
CS 2630 Computer Organization Meeting 7: Stored programs II: program execution, immediates, addresses Brandon Myers University of Iowa
Where we are going Compiler
Instruction set architecture (e.g., MIPS) Memory system
Processor Datapath & Control Digital logic
translating source code (C or Java) Programs to assembly language And linking your code to Library code How the software talks To the hardware I/O system How a processor runs MIPS Programs! How switches (1 or 0) can be used to build Interesting functions: from integer arithmetic to programmable computers
Representations of a program int x = arr[1]; arr[2] = x + 10;
High level language program (human readable)
Compiler
lw $t0, 4($r0) addi $t0, $t0, 10 sw $t0, 8($r0) Assembler
10001110000010000000000000000100 00100001000010000000000000001010 10101110000010000000000000001000
assembly program as text (CS2630 student readable)
assembly program as binary (machine readable)
Register names -> numbers this table in the MIPS reference sheet says, e.g., that register $t8 is represented by 5-bit number 24
Register Number
Conventional Name
Usage
$0
$zero
hard-wired to 0
$1
$at
reserved for assembler
$2 - $3
$v0, $v1
return values from functions
$4 - $7
$a0 - $a3
arguments
$8 - $15
$t0 - $t7
temporary registers
$16 - $23
$s0 - $s7
saved registers
$24 - $25
$t8 - $t9
temporary registers
$26 - $27
$k0 - $k1
reserved for OS
$28
$gp
global pointer
$29
$sp
stack Pointer
$30
$fp
frame Pointer
$31
$ra
return Address
opcode
More instructions
opcode
funct
Branches: relative addressing
example
Instruction execution PC 0x0000 contents
meaning
address 0000
8e
13
00
00
loop: lw $s3,0($s0)
0004
8e
14
00
04
lw
$s4, 4($s0)
0008
02
74
90
20
add
$s2, $s3, $s4
000C
ae
12
00
08
sw
$s2, 8($s0)
0010
22
10
00
04
addi $s0, $s0, 4
0014
22
31
ff
ff
addi $s1, $s1, -1
0018
1e
20
ff
f9
bgtz $s1, loop
Analogy: choose-your-own-adventure novel • on most pages: you continue reading by turning the page (as in a normal book) • on some pages: you are given the choice to jump to a different page
Instruction execution PC 0x0000 contents
meaning
address 0000
8e
13
00
00
loop: lw $s3,0($s0)
0004
8e
14
00
04
lw
$s4, 4($s0)
0008
02
74
90
20
add
$s2, $s3, $s4
000C
ae
12
00
08
sw
$s2, 8($s0)
0010
22
10
00
04
addi $s0, $s0, 4
0014
22
31
ff
ff
addi $s1, $s1, -1
0018
1e
20
ff
f9
bgtz $s1, loop
Instruction execution PC 0x0004 contents
meaning
address 0000
8e
13
00
00
loop: lw $s3,0($s0)
0004
8e
14
00
04
lw
$s4, 4($s0)
0008
02
74
90
20
add
$s2, $s3, $s4
000C
ae
12
00
08
sw
$s2, 8($s0)
0010
22
10
00
04
addi $s0, $s0, 4
0014
22
31
ff
ff
addi $s1, $s1, -1
0018
1e
20
ff
f9
bgtz $s1, loop
Instruction execution PC 0x0008 contents
meaning
address 0000
8e
13
00
00
loop: lw $s3,0($s0)
0004
8e
14
00
04
lw
$s4, 4($s0)
0008
02
74
90
20
add
$s2, $s3, $s4
000C
ae
12
00
08
sw
$s2, 8($s0)
0010
22
10
00
04
addi $s0, $s0, 4
0014
22
31
ff
ff
addi $s1, $s1, -1
0018
1e
20
ff
f9
bgtz $s1, loop
Instruction execution PC 0x000C contents
meaning
address 0000
8e
13
00
00
loop: lw $s3,0($s0)
0004
8e
14
00
04
lw
$s4, 4($s0)
0008
02
74
90
20
add
$s2, $s3, $s4
000C
ae
12
00
08
sw
$s2, 8($s0)
0010
22
10
00
04
addi $s0, $s0, 4
0014
22
31
ff
ff
addi $s1, $s1, -1
0018
1e
20
ff
f9
bgtz $s1, loop
Instruction execution PC 0x0010 contents
meaning
address 0000
8e
13
00
00
loop: lw $s3,0($s0)
0004
8e
14
00
04
lw
$s4, 4($s0)
0008
02
74
90
20
add
$s2, $s3, $s4
000C
ae
12
00
08
sw
$s2, 8($s0)
0010
22
10
00
04
addi $s0, $s0, 4
0014
22
31
ff
ff
addi $s1, $s1, -1
0018
1e
20
ff
f9
bgtz $s1, loop
Instruction execution PC 0x0014 contents
meaning
address 0000
8e
13
00
00
loop: lw $s3,0($s0)
0004
8e
14
00
04
lw
$s4, 4($s0)
0008
02
74
90
20
add
$s2, $s3, $s4
000C
ae
12
00
08
sw
$s2, 8($s0)
0010
22
10
00
04
addi $s0, $s0, 4
0014
22
31
ff
ff
addi $s1, $s1, -1
0018
1e
20
ff
f9
bgtz $s1, loop
Instruction execution PC 0x0018 contents
meaning
address 0000
8e
13
00
00
loop: lw $s3,0($s0)
0004
8e
14
00
04
lw
$s4, 4($s0)
0008
02
74
90
20
add
$s2, $s3, $s4
000C
ae
12
00
08
sw
$s2, 8($s0)
0010
22
10
00
04
addi $s0, $s0, 4
0014
22
31
ff
ff
addi $s1, $s1, -1
0018
1e
20
ff
f9
bgtz $s1, loop
Instruction execution
branches use “relative addressing”
PC 0x0018 contents
meaning
address 0000
8e
13
00
00
loop: lw $s3,0($s0)
0004
8e
14
00
04
lw
$s4, 4($s0)
0008
02
74
90
20
add
$s2, $s3, $s4
000C
ae
12
00
08
sw
$s2, 8($s0)
0010
22
10
00
04
addi $s0, $s0, 4
0014
22
31
ff
ff
addi $s1, $s1, -1
0018
1e
20
ff
f9
bgtz $s1, loop
0xfff9 = -7 0x0018 + 4 + (-7 * 4) = 0x0000
Peer instruction
What is the immediate for the beq instruction?
a)3 b)12 c) 8 d)2 e)-3
Jumps: absolute addressing
example
example
Peer instruction
What is the maximum distance you can jump using a single j? a) b) c) d) e) f)
25 instructions 26 instructions 224 instructions 225 instructions 226 instructions 230 instructions
The plot thickens Some MIPS instructions you can write cannot be translated to a 32-bit number some reasons why Spoiler Alert! 1) constants are too big 2) relative addresses are too big 3) absolute addresses are outside the range of a jump 4) convenience instructions that have no opcode
Storing an instruction as bits each MIPS instructions is 32 bits, stored in “instruction memory” contents
meaning
address 0000
8e
13
00
00
lw
$s3, 0($s0)
0004
8e
14
00
04
lw
$s4, 4($s0)
0008
02
74
90
20
add
$s2, $s3, $s4
000C
ae
12
00
08
sw
$s2, 8($s0)
0010
22
10
00
04
addi $s0, $s0, 4
0014
22
31
ff
ff
addi $s1, $s1, -1
0018
1e
20
ff
f9
bgtz $s1, loop
Pseudo instructions Not all the MIPS instructions are “real” (i.e., understood by the processor) TAL – the true assembly language; MIPS processors know all of these instructions MAL – slightly more convenient language; each MAL instruction is usually translated to 1-3 TAL instructions by the assembler
Pseudo instructions (MAL) Example: how many bits are required for the immediate in this instruction? addiu $t1, $t2, 0x123456 assembler translates it to lui $t2, 0x0012 ori $t3, $t3, 0x3456 addu $t1, $t2, $t3
lui = “load upper immediate”
More pseudo instructions (MAL) • other I-type instructions with too-large immediate • move $rd, $rs • li $rd, [32-bit immediate] • la $rd, [32-bit immediate] • branch instructions with , = • really use slt (set if less than), followed by beq to 0 or 1
• For you to try: use these instructions in a MIPS program, then see what MARS translates them to
Peer instruction • Put the following into • (A) only in MAL • (B) TAL
Acknowledgements • Snips of green sheet from http://wwwinst.eecs.berkeley.edu/~cs61c/resources/MIPS_help.html