Transcript ppt - ECE

Announcements

HW1 is due on this Friday

Appendix A (on CD) is very helpful to HW1.
331 W02.1
Spring 05
Review I: Execute Cycle

Q1: How does control know
which instruction to fetch?

Q2: who does decode?
What happens in decode
phase?

Q3: How do control and
datapath interact to finish
exec phase?

Q4: What does datapath
have?
Fetch
Exec
331 W02.2
Decode
Spring 05
Review II: word length

What does 32-bit architecture mean?
331 W02.3
Spring 05
Assembly Language

Language of the machine

More primitive than higher level languages
e.g., no sophisticated control flow

Very restrictive
e.g., MIPS arithmetic instructions

We’ll be working with the MIPS instruction set
architecture



331 W02.4
similar to other architectures developed since the 1980's
used by NEC, Nintendo, Silicon Graphics, Sony, …
32-bit architecture
- 32 bit data line and address line
- data and addresses are 32-bit
Spring 05
MIPS R3000 Instruction Set Architecture

Instruction Categories




Registers
Load/Store
Computational
Jump and Branch
Floating Point
R0 - R31
- coprocessor



PC
HI
Memory Management
Special
LO
3 Instruction Formats: all 32 bits wide
OP
rs
rt
OP
rs
rt
OP
rd
sa
funct
immediate
jump target
Q: How many already familiar with MIPS ISA?
331 W02.5
Spring 05
MIPS Arithmetic Instruction

MIPS assembly language arithmetic statement
add
$t0, $s1, $s2
sub
$t0, $s1, $s2

Each arithmetic instruction performs only one
operation

Each arithmetic instruction specifies exactly three
operands
destination  source1
op
source2

Those operands are contained in the datapath’s
register file ($t0, $s1,$s2)

Operand order is fixed (destination first)
331 W02.6
Spring 05
Compiling More Complex Statements

Assuming variable b is stored in register $s1, c is
stored in $s2, d is stored in $s3 and the result is to
be left in $s0, and $t0 is a temporary register,
what is the assembler equivalent to the C
statement
h = (b - c) + d
331 W02.7
Spring 05
Registers

Registers are


Faster than main memory
Can hold variables so that
- code density improves (since registers are named with
fewer bits than a memory location) – why is that?

Register addresses are indicated by using $
331 W02.8
Spring 05
MIPS Register File

Operands of arithmetic instructions must be from a
limited number of special locations contained in
the datapath’s register file

Holds thirty-two 32-bit registers
- With two read ports and
- One write port
Register File
src1 addr
src2 addr
dst addr
write data
5
32 src1
data
5
5
32
locations
32 src2
32
data
32 bits
331 W02.9
Spring 05
Naming Conventions for Registers
0
$zero constant 0
16 $s0 callee saves
1
$at reserved for assembler
...
2
$v0 expression evaluation &
23 $s7
3
$v1 function results
24 $t8 temporary (cont’d)
4
$a0 arguments
25 $t9
5
$a1
26 $k0 reserved for OS kernel
6
$a2
27 $k1
7
$a3
28 $gp pointer to global area
8
$t0 temporary: caller saves
29 $sp stack pointer
(callee can clobber)
30 $fp frame pointer
...
15 $t7
331 W02.10
(caller can clobber)
31 $ra return address
Spring 05
Registers vs. Memory

Arithmetic instructions operands must be
registers,
— only thirty-two registers provided
Processor
Control
Datapath

Devices
Memory
Input
Output
What about programs with lots of variables?


331 W02.11
Store variables in the memory
Load variables from memory to registers before use;
store them back to memory after use.
Spring 05
Accessing Memory

MIPS has two basic data transfer instructions for
accessing memory
lw $t0, 4($s3)
sw $t0, 8($s3)

The data transfer instruction must specify



#load word from memory
#store word to memory
where in memory to read from (load) or write to (store) –
memory address
where in the register file to write to (load) or read from
(store) – register destination (source)
The memory address is formed by summing the
constant portion of the instruction and the contents
of the second register
331 W02.12
Spring 05
Processor – Memory Interconnections

Memory is viewed as a large, single-dimension
array, with an address

A memory address is an index into the array
read addr/ 32
write addr
Processor
read data 32
32write data
Memory
232
Addressable
locations
Q: what should be
the smallest
addressable
unit?
331 W02.13
Spring 05
MIPS Data Types
Integer: (signed or unsigned)
32 bits
Character:
8 bits
Floating point numbers:
32 bits
Memory addresses (pointers):
32 bits
Instructions:
32 bits
Bit String: sequence of bits of a particular length
8 bits is a byte
16 bits is a half-word
32 bits (4 bytes) is a word
64 bits is a double-word
331 W02.14
Spring 05
Byte Addresses

Since 8-bit bytes are so useful, most architectures
address individual bytes in memory
memory: 232 bytes = 230 words

Therefore, the memory address of a word must be
a multiple of 4 (alignment restriction)
0
1
2
Aligned
Alignment restriction: requires
that objects fall on address that is
multiple of their size.
331 W02.15
Not
Aligned
Spring 05
3
Addressing Objects: Endianess and Alignment

Big Endian:
leftmost byte is word address
IBM 360/370, Motorola 68k, MIPS, Sparc, HP PA

Little Endian:
rightmost byte is word address
Intel 80x86, DEC Vax, DEC Alpha (Windows NT)
little endian byte 0
3
2
1
0
msb
0
big endian byte 0
331 W02.16
lsb
1
2
3
Spring 05
MIPS Memory Addressing

The memory address is formed by summing the
constant portion of the instruction and the contents
of the second (base) register
$s3 holds 8
Memory
...0110
24
...0101
20
...1100
16
...0001
12
...0010
8
...1000
4
...0100
Data
0
Word Address
lw
$t0, 4($s3)
#what? is loaded into $t0
sw
$t0, 8($s3)
#$t0 is stored where?
331 W02.17
Spring 05
Compiling with Loads and Stores

Assuming variable b is stored in $s2 and that the
base address of integer array A is in $s3, what is
the MIPS assembly code for the C statement
A[8] = A[2] - b
...
...
A[3]
$s3+12
A[2]
$s3+8
A[1]
$s3+4
A[0]
$s3
331 W02.18
Spring 05
Compiling with a Variable Array Index

Assuming A is an integer array whose base is in
register $s4, and variables b, c, and i are in $s1,
$s2, and $s3, respectively, what is the MIPS
assembly code for the C statement
c = A[i] - b
331 W02.19
Spring 05
MIPS Instructions, so far
Category
Arithmetic
(R format)
Data
Instr
Op Code
Example
add
0 and 32
add $s1, $s2, $s3
$s1 = $s2 + $s3
subtract
0 and 34
sub $s1, $s2, $s3
$s1 = $s2 - $s3
load word
35
lw
$s1, 100($s2)
$s1 =
Memory($s2+10
0)
store word
43
sw $s1, 100($s2)
Memory($s2+10
0) = $s1
transfer
(I format)
331 W02.20
Meaning
Spring 05
Machine Language - Arithmetic Instruction

Instructions, like registers and words of data, are
also 32 bits long



Example:
add $t0, $s1, $s2
registers have numbers $t0=$8, $s1=$17, $s2=$18
Instruction Format:
op
rs
000000 10001
rt
rd
10010
01000
shamt
00000
funct
100000
Can you guess what the field names stand for?
331 W02.21
Spring 05
MIPS Instruction Fields

op

rs

rt

rd

shamt

funct
331 W02.22
op
rs
rt
rd
shamt
6 bits
5 bits
5 bits
5 bits
5 bits
funct
6 bits
= 32 bits
Spring 05
Machine Language - Load Instruction

Consider the load-word and store-word instructions,



Introduce a new type of instruction format



What would the regularity principle have us do?
New principle: Good design demands a compromise
I-type for data transfer instructions
previous format was R-type for register
Example: lw $t0, 24($s2)
op
331 W02.23
rs
35
18
100011
10010
rt
16 bit number
8
01000
24
0000000000011000
Where's the compromise?
Spring 05
Memory Address Location

Example:
lw $t0, 24($s2)
Memory
0xf f f f f f f f
2410 + $s2 =
0x00000002
0x12004094
$s2
Note that the offset can
be positive or negative
data
331 W02.24
0x0000000c
0x00000008
0x00000004
0x00000000
word address (hex)
Spring 05
Machine Language - Store Instruction

Example: sw $t0, 24($s2)
op

rs
43
18
101011
10010
rt
16 bit number
8
01000
24
0000000000011000
A 16-bit address means access is limited to
memory locations within a region of 213 or 8,192
words (215 or 32,768 bytes) of the address in the
base register $s2
331 W02.25
Spring 05
Assembling Code

Remember the assembler code we compiled for the C
statement
A[8] = A[2] - b
lw
sub
sw
$t0, 8($s3)
$t0, $t0, $s2
$t0, 32($s3)
#load A[2] into $t0
#subtract b from A[2]
#store result in A[8]
Assemble the MIPS object code for these three
instructions
331 W02.26
Spring 05
Review: MIPS Data Types
Integer: (signed or unsigned)
32 bits
Character:
8 bits
Floating point numbers:
32 bits
Memory addresses (pointers):
32 bits
Instructions:
32 bits
Bit String: sequence of bits of a particular length
8 bits is a byte
16 bits is a half-word
32 bits (4 bytes) is a word
64 bits is a double-word
331 W02.27
Spring 05
Beyond Numbers

Most computers use 8-bit bytes to represent characters with the
American Std Code for Info Interchange (ASCII)
ASCII
Char
ASCII
Char
ASCII
Char
ASCII
Char
ASCII
Char
ASCII
Char
0
Null
32
space
48
0
64
@
96
`
112
p
1
33
!
49
1
65
A
97
a
113
q
2
34
“
50
2
66
B
98
b
114
r
3
35
#
51
3
67
C
99
c
115
s
36
$
52
4
68
D
100
d
116
t
37
%
53
5
69
E
101
e
117
u
38
&
54
6
70
F
102
f
118
v
39
‘
55
7
71
G
103
g
119
w
4
EOT
5
6
ACK
7
8
bksp
40
(
56
8
72
H
104
h
120
x
9
tab
41
)
57
9
73
I
105
i
121
y
10
LF
42
*
58
:
74
J
106
j
122
z
43
+
59
;
75
K
107
k
123
{
44
,
60
<
76
L
108
l
124
|
47
/
63
?
79
O
111
o
127
DEL
11
12
15

FF
So, we need instructions to move bytes around
331 W02.28
Spring 05
Loading and Storing Bytes

MIPS provides special instructions to move bytes
lb
$t0, 1($s3)
#load byte from memory
sb
$t0, 6($s3)
#store byte to
op

rs
rt
memory
16 bit number
What 8 bits get loaded and stored?

load byte places the byte from memory in the rightmost 8
bits of the destination register
- what happens to the other bits in the register?

331 W02.29
store byte takes the byte from the rightmost 8 bits of a
register and writes it to a byte in memory
Spring 05
Example of Loading and Storing Bytes

Given following code sequence and memory state
(contents are given in hexidecimal), what is the
state of the memory after executing the code?
add $s3, $zero, $zero
lb
$t0, 1($s3)
sb
$t0, 6($s3)
Memory
00000000
24
00000000
20
00000000
16
10000010
12
01000402
8
FFFFFFFF
4
009012A0
0
Data
331 W02.30


What value is left in $t0?
What if the machine was little
Endian?
Word
Address (Decimal)
Spring 05
Review: MIPS Instructions, so far
Category
Arithmetic
(R format)
Instr
Op Code
Example
Meaning
add
0 and 32
add $s1, $s2, $s3
$s1 = $s2 + $s3
subtract
0 and 34
sub $s1, $s2, $s3
$s1 = $s2 - $s3
Data
load word
35
lw
$s1, 100($s2)
$s1 = Memory($s2+100)
transfer
store word
43
sw $s1, 100($s2)
Memory($s2+100) = $s1
(I format)
load byte
32
lb
$s1, 101($s2)
$s1 = Memory($s2+101)
store byte
40
sb $s1, 101($s2)
Memory($s2+101) = $s1
331 W02.31
Spring 05
Review: MIPS R3000 ISA

Instruction Categories

Load/Store

Computational
Jump and Branch
Floating Point


Registers
R0 - R31
- coprocessor


Memory Management
Special
PC
HI
LO

3 Instruction Formats: all 32 bits wide
6 bits
5 bits
5 bits
rd
OP
rs
rt
OP
rs
rt
OP
331 W02.32
5 bits
5 bits
shamt
16 bit number
6 bits
funct
R format
I format
26 bit jump target
Spring 05