Transcript Chap2a_11

Computer Architecture
Chapter 2 a
With thanks to M.J. Irwin, D. Patterson, and J. Hennessy for some lecture slide contents

The collection of instructions of a computer

Different computers have different instruction sets


Early computers had very simple instruction sets


But with many aspects in common
Simplified implementation
Many modern computers also have simple instruction
sets
§2.1 Introduction
Instruction Set
The MIPS Instruction Set

Used as the example throughout the book

Stanford MIPS commercialized by MIPS Technologies


See www.mips.com
Large share of embedded core market

Applications in consumer electronics, network/storage equipment,
cameras, printers, …

Uses the Reduced Instruction Set Architecture (RISC) approach

Typical of many modern ISAs

See MIPS Reference Data tear-out card, and Appendixes B and E
MIPS-32 ISA

Registers
Instruction Categories

Computational

Load/Store

Jump and Branch

Floating Point
-
R0 - R31
coprocessor

Memory Management
PC
HI

Special
LO
3 Instruction Formats: all 32 bits wide
op
rs
rt
op
rs
rt
op
rd
sa
immediate
jump target
funct
R format
I format
J format
MIPS (& RISC) Design Principles




Simplicity favors regularity

fixed size instructions

small number of instruction formats

opcode always the first 6 bits
Smaller is faster

limited instruction set

limited number of registers in register file

limited number of addressing modes
Make the common case fast

arithmetic operands from the register file (load-store machine)

allow instructions to contain immediate operands
Good design demands good compromises

three instruction formats

Add and subtract, three operands

Two sources and one destination
add a, b, c
# a gets b + c

All arithmetic operations have this form

Design Principle 1: Simplicity favors regularity

Regularity makes implementation simpler

Simplicity enables higher performance at lower cost
§2.2 Operations of the Computer Hardware
Arithmetic Operations
Arithmetic Example

C code:
f = (g + h) - (i + j);

Compiled “MIPS code”:
add t0, g, h
add t1, i, j
sub f, t0, t1
# temp t0 = g + h
# temp t1 = i + j
# f = t0 - t1
MIPS Arithmetic Instructions

MIPS assembly language arithmetic statement
add $t0, $s1, $s2
sub $t0, $s1, $s2

Each arithmetic instruction performs one operation

Each specifies exactly three operands that are all
contained in the datapath’s register file ($t0,$s1,$s2)
destination  source1

op
source2
Instruction Format (R format)
0
17
18
8
0
0x22
MIPS Instruction Fields

MIPS fields are given names to make them easier to
refer to
op
op
rs
6-bits
rt
rd
shamt
funct
opcode that specifies the operation
rs
5-bits
register file address of the first source operand
rt
5-bits
register file address of the second source operand
rd
5-bits
register file address of the result’s destination
shamt 5-bits
shift amount (for shift instructions)
funct
function code augmenting the opcode
6-bits




Arithmetic instructions use register
operands
MIPS has a 32 × 32-bit register file

Use for frequently accessed data

Numbered 0 to 31

32-bit data called a “word”
Assembler names

$t0, $t1, …, $t9 for temporary values

$s0, $s1, …, $s7 for saved variables
Design Principle 2: Smaller is faster

Compare with main memory: millions of locations
§2.3 Operands of the Computer Hardware
Register Operands
MIPS Register File

Register File
Holds thirty-two 32-bit registers


Two read ports and

One write port
Registers are

Faster than main memory
src1 addr
src2 addr
dst addr
write data
32 bits
5
32 src1
data
5
5
32
locations
32 src2
32
- But larger register files are slower than
smaller ones (e.g., a 64 word file could
be as much as 50% slower than a 32 word file)
data
write control
- Read/write port increase impacts speed quadratically

Easier for a compiler to use
- e.g., (A*B) – (C*D) – (E*F) can do multiplies in any order vs.
stack

Can hold variables so that
- code density improves (since registers are named with fewer bits
than a memory location)
Register Operand Example

C code:
f = (g + h) - (i + j);

Compiler puts f,g,h,i,j in $s0, …, $s4

Compiled MIPS code:
add $t0, $s1, $s2
add $t1, $s3, $s4
sub $s0, $t0, $t1
Registers vs. Memory

Registers are faster to access than memory

Operating on memory data requires loads and stores


More instructions to be executed
Compiler must use registers for variables as much as
possible

Only spill to memory for less frequently used variables

Register optimization is important!
Immediate Operands

Constant data specified in an instruction
addi $s3, $s3, 4

No subtract immediate instruction

Just use a negative constant
addi $s2, $s1, -1

Design Principle 3: Make the common case fast

Small constants are common (50% of MIPS arithmetic
instructions in SPEC2006 use constants!)

Immediate operand avoids a load instruction
The Constant Zero

MIPS register 0 ($zero) is the constant 0


Cannot be overwritten
Useful for common operations

E.g., move between registers
add $t2, $s1, $zero
Aside: MIPS Register Convention
Name
Register
Number
$zero
0
$at
1
$v0 - $v1
2-3
$a0 - $a3
4-7
$t0 - $t7
8-15
$s0 - $s7
16-23
$t8 - $t9
24-25
$gp
28
$sp
29
$fp
30
$ra
31
Usage
Preserve
on call?
constant 0 (hardware)
n.a.
reserved for assembler
n.a.
returned values
no
arguments
no
temporaries
no
saved values
yes
temporaries
no
global pointer
yes
stack pointer
yes
frame pointer
yes
return addr (hardware)
yes
MIPS Memory Access Instructions



MIPS has two basic data transfer instructions for
accessing memory
lw
$t0, 4($s3)
#load word from memory
sw
$t0, 8($s3)
#store word to memory
The data is loaded into (lw) or stored from (sw) a register
in the register file – a 5 bit address
The memory address – a 32 bit address – is formed by
adding the contents of the base address register to the
offset value

A 16-bit field meaning 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
Memory Operand Example 1

C code:
g = h + A[8];


g in $s1, h in $s2, base address of A in $s3
Compiled MIPS code:

Index 8 requires offset of 32 bytes
- 4 bytes per word
lw $t0, 32($s3)
add $s1, $s2, $t0
offset
# load word
base register
Memory Operand Example 2

C code:
A[12] = h + A[8];


h in $s2, base address of A in $s3
Compiled MIPS code:

Index 8 requires offset of 32 bytes

Index 12 requires offset of 48 bytes
lw $t0, 32($s3)
add $t0, $s2, $t0
sw $t0, 48($s3)
# load word
# store word
Machine Language - Load Instruction

Load/Store Instruction Format (I format):
lw $t0, 24($s3)
35
19
8
2410
Memory
2410 + $s3 =
. . . 0001 1000
+ . . . 1001 0100
. . . 1010 1100 =
0x120040ac
0xf f f f f f f f
0x120040ac
$t0
0x12004094
$s3
data
0x0000000c
0x00000008
0x00000004
0x00000000
word address (hex)
Byte Addresses

Since 8-bit bytes are so useful, most architectures
address individual bytes in memory


Alignment restriction - the memory address of a word must be
on natural word boundaries (a multiple of 4 in MIPS-32)
Big Endian:
leftmost byte is word address
IBM 360/370, Motorola 68k, MIPS, Sparc, HP PA

Little Endian: rightmost byte is word address
Intel IA-32, DEC Vax, DEC Alpha (Windows NT)
3
2
1
little endian byte 0
0
msb
0
big endian byte 0
lsb
1
2
3
Aside: 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
0x28

19
8
memory
16 bit offset
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?

store byte takes the byte from the rightmost 8 bits of a register
and writes it to a byte in memory
- what happens to the other bits in the memory word?

Given an n-bit number
n

1
n

2
n

1
n

2
x

x
2

x
2



x
2

x
2

Range: 0 to +2n – 1

Example


0000 0000 0000 0000 0000 0000 0000 10112
= 0 + … + 1×23 + 0×22 +1×21 +1×20
= 0 + … + 8 + 0 + 2 + 1 = 1110
Using 32 bits

1
0
1
0
0 to +4,294,967,295
§2.4 Signed and Unsigned Numbers
Unsigned Binary Integers
2s-Complement Signed Integers

Given an n-bit number
n

1
n

2
n

1
n

2
x


x
2

x
2



x
2

x
2

Range: –2n – 1 to +2n – 1 – 1

Example


1111 1111 1111 1111 1111 1111 1111 11002
= –1×231 + 1×230 + … + 1×22 +0×21 +0×20
= –2,147,483,648 + 2,147,483,644 = –410
Using 32 bits

–2,147,483,648 to +2,147,483,647
1
0
1
0
Review: Unsigned Binary Representation
Hex
Binary
Decimal
0x00000000
0…0000
0
0x00000001
0…0001
1
231 230 229
...
23 22 21
20
0x00000002
0…0010
2
31 30 29
...
3
0
0x00000003
0…0011
3
0x00000004
0…0100
4
1 1 1
...
1 1 1 1
bit
0x00000005
0…0101
5
0x00000006
0…0110
6
1 0 0 0
...
0 0 0 0
-
0x00000007
0…0111
7
0x00000008
0…1000
8
0x00000009
0…1001
9
…
0xFFFFFFFC
1…1100
0xFFFFFFFD
1…1101
0xFFFFFFFE
1…1110
0xFFFFFFFF
1…1111
232 - 4
232 - 3
232 - 2
232 - 1
232 - 1
2
1
bit weight
bit position
1
Review: Signed Binary Representation
-23 =
-(23 - 1) =
complement all the bits
0101
and add a 1
0110
1011
and add a 1
1010
complement all the bits
23 - 1 =
2’sc binary
decimal
1000
-8
1001
-7
1010
-6
1011
-5
1100
-4
1101
-3
1110
-2
1111
-1
0000
0
0001
1
0010
2
0011
3
0100
4
0101
5
0110
6
2s-Complement Signed Integers

Bit 31 is sign bit

1 for negative numbers

0 for non-negative numbers

–(–2n – 1) can’t be represented

Non-negative numbers have the same unsigned and 2scomplement representation

Some specific numbers

0:
0000 0000 … 0000

–1:
1111 1111 … 1111

Most-negative: 1000 0000 … 0000

Most-positive: 0111 1111 … 1111
Signed Negation

Complement and add 1

Complement means 1 → 0, 0 → 1
x

x

1111...111


1
2
x

1


x

Example: negate +2

+2 = 0000 0000 … 00102

–2 = 1111 1111 … 11012 + 1
= 1111 1111 … 11102
Sign Extension

Representing a number using more bits



In MIPS instruction set

addi: extend immediate value

lb, lh: extend loaded byte/halfword

beq, bne: extend the displacement
Replicate the sign bit to the left


Preserve the numeric value
c.f. unsigned values: extend with 0s
Examples: 8-bit to 16-bit

+2: 0000 0010 => 0000 0000 0000 0010

–2: 1111 1110 => 1111 1111 1111 1110
Hexadecimal
Base 16
Compact representation of bit strings
4 bits per hex digit

0
0000
4
0100
8
1000
c
1100
1
0001
5
0101
9
1001
d
1101
2
0010
6
0110
a
1010
e
1110
3
0011
7
0111
b
1011
f
1111
Example: eca8 6420

1110 1100 1010 1000 0110 0100 0010 0000

Small constants are used often in typical code

Possible approaches?


put “typical constants” in memory and load them

create hard-wired registers (like $zero) for constants like 1

have special instructions that contain constants !
addi $sp, $sp, 4
#$sp = $sp + 4
slti $t0, $s2, 15
#$t0 = 1 if $s2<15
Machine format (I format):
0x0A

18
8
0x0F
The constant is kept inside the instruction itself!

Immediate format limits values to the range +215–1 to -215
§2.5 Representing Instructions in the Computer
MIPS Immediate Instructions
Aside: How About Larger Constants?

We'd also like to be able to load a 32 bit constant into a
register, for this we must use two instructions

a new "load upper immediate" instruction
lui $t0, 1010101010101010
16

0
8
10101010101010102
Then must get the lower order bits right, use
ori $t0, $t0, 1010101010101010
1010101010101010
0000000000000000
0000000000000000
1010101010101010
1010101010101010
1010101010101010
Instructions for bitwise manipulation

Operation
C
Java
MIPS
Shift left
<<
<<
sll
Shift right
>>
>>>
srl
Bitwise AND
&
&
and, andi
Bitwise OR
|
|
or, ori
Bitwise NOT
~
~
nor
Useful for moving, extracting and inserting groups of
bits in a word
§2.6 Logical Operations
Logical Operations
MIPS Shift Operations

Need operations to pack and unpack 8-bit characters into
32-bit words

Shifts move all the bits in a word left or right
sll $t2, $s0, 8#$t2 = $s0 << 8 bits
srl $t2, $s0, 8#$t2 = $s0 >> 8 bits

Instruction Format (R format)
0

16
10
8
0x00
Such shifts are called logical because they fill with
zeros

Notice that a 5-bit shamt field is enough to shift a 32-bit value
25 – 1 or 31 bit positions
MIPS Logical Operations

There are a number of bit-wise logical operations in the
MIPS ISA
and $t0, $t1, $t2 #$t0 = $t1 & $t2
or
$t0, $t1, $t2 #$t0 = $t1 | $t2
nor $t0, $t1, $t2 #$t0 = not($t1 | $t2)

Instruction Format (R format)
0
9
10
8
0
0x24
andi $t0, $t1, 0xFF00 #$t0 = $t1 & ff00
ori

$t0, $t1, 0xFF00 #$t0 = $t1 | ff00
Instruction Format (I format)
0x0D
9
8
0xFF00
Shift Operations
op
rs
rt
rd
shamt
funct
6 bits
5 bits
5 bits
5 bits
5 bits
6 bits

shamt: # positions to shift

Shift left logical


Shift left and fill with bits with 0

sll by i bits multiplies by 2i
Shift right logical

Shift right and fill with bits with 0

srl by i bits divides by 2i (unsigned only)
OR Operations

Useful to include bits in a word

Set some bits to 1, leave others unchanged
or $t0, $t1, $t2
# $t1 is the “OR mask”
$t2
0000 0000 0000 0000 0000 1101 1100 0000
$t1
0000 0000 0000 0000 0011 1100 0000 0000
$t0
0000 0000 0000 0000 0011 1101 1100 0000
AND Operations

Useful to mask bits in a word

Clear some bits to 0, leave others unchanged
and $t0, $t1, $t2
# $t1 is the “AND mask”
$t2
0000 0000 0000 0000 0000 1101 1100 0000
$t1
0000 0000 0000 0000 0011 1100 0000 0000
$t0
0000 0000 0000 0000 0000 1100 0000 0000
NOT Operations

Useful to invert bits in a word


Change 0 to 1, and 1 to 0
MIPS has NOR 3-operand instruction

a NOR b == NOT ( a OR b )
nor $t0, $t1, $zero
Register 0: always
read as zero
$t1
0000 0000 0000 0000 0011 1100 0000 0000
$t0
1111 1111 1111 1111 1100 0011 1111 1111