Transcript cse331-week2

CSE 331
Computer Organization and Design
Fall 2007
Week 2
Section 1: Mary Jane Irwin (www.cse.psu.edu/~mji)
Section 2: Krishna Narayanan
Course material on ANGEL: cms.psu.edu
[adapted from D. Patterson slides]
CSE331 W02.1
Irwin 2007 PSU
Reminder: Course Administration

Instr (Sec1): Mary Jane Irwin ([email protected])



Instr (Sec2): Krishna Narayanan ([email protected])



348C IST Bldg
OH’s: Tues 2:30 – 3:45pm & Wed 9:15 – 10:30am
348D IST Bldg
OH’s: Mon, Thurs 2:30 – 4:00pm
TA:


Evens Jean ([email protected] )
360E IST Bldg
OH’s: Tues, Thurs 2:30 – 4:00pm
Web: ANGEL, cms.psu.edu
 Lab: Accounts on CSE machines in 220 IST, Windows Lab
 Texts: Computer Organization and Design: The
Hardware/Software Interface,
3rd Edition Revised Printing, Patterson and Hennessy
VHDL Starter’s Guide, 2nd Edition, Yalamanchili

CSE331 W02.2
Irwin 2007 PSU
Fall Career Days
http://www.fairs.sa.psu.edu/fall/student/
 Wed, Sept 19 and Thurs, Sept 20
 One of the largest Career Fairs in the nation employers who are interested in hiring
engineering students for co-op/interns (Sept
19) and full-time (Sept 20) positions
 If you would like to volunteer to help with set
up, click on Volunteer to Help link.
CSE331 W02.3
Irwin 2007 PSU
Eta Kappa Nu Tutoring
Mondays 7-9PM in 101 EE East
 Free tutoring in EE/CMP ENG core courses…







EE 210
EE 310
EE 317
EE 324
EE 330
EE 350







CSE 121/122
CSE 221
CSE 260
CSE 271/275
CSE 331
CSE 465
CSE 431
Other courses available upon request
 Contact Mike Barry ([email protected])

CSE331 W02.4
Irwin 2007 PSU
Head’s Up
 Last

week’s material
Course introduction, basics of a computer system,
introduction to SPIM – PH 1.1-1.3, A.9
 This

week’s material
Introduction to MIPS assembler, adds/loads/stores
- Reading assignment - PH 2.1 through 2.4
 Next

week’s material
MIPS control flow operations
- Reading assignment - PH 2.6 & 2.5 & A.10
 Reminders
Online Quiz 1 is due Thurs, Sept. 13 (by 11:55pm)
 HW 2 (another spim assignment) is due Tues, Sept 11
(by 11:55pm)

CSE331 W02.5
Irwin 2007 PSU
Marketing and management will not usually ask for
a combination of features, cost, and schedule
that are simultaneously realizable – count on
that. They will reliably ask for the impossible. …
It’s a very short step from using Moore’s Law to
check your road map to using it to dictate the
road map.
Bob Colwell, The Pentium Chronicles
CSE331 W02.6
Irwin 2007 PSU
Review: Execute Cycle
The datapath executes the instructions
as directed by control
Devices
Processor
Network
Control
000000 00100 00010 0001000000100000
Memory
Input
Datapath
contents Reg #4 ADD contents Reg #2
results put in Reg #2
Output
Memory stores both instructions and
data
CSE331 W02.7
Irwin 2007 PSU
Review: Processor Organization
 Control needs to have circuitry to
Fetch
 Decide which is the next instruction
and input it from memory
Exec
Decode
 Decode the instruction
 Issue signals that control the way
information flows between datapath components
 Control what operations the datapath’s functional units
perform
 Datapath



CSE331 W02.8
needs to have circuitry to
Execute instructions - functional units (e.g., adder) and
storage locations (e.g., register file)
Interconnect the functional units so that the instructions can
be executed as required
Load data from and store data to memory
Irwin 2007 PSU
Assembly Language Instructions

The language of the machine


Stored program (von Neumann) concept


Want an ISA that makes it easy to build the
hardware and the compiler while maximizing
performance and minimizing cost
Instructions are stored in memory (as is the data)
Our target: the MIPS ISA


similar to other ISAs developed since the 1980's
used by Broadcom, Cisco, NEC, Nintendo, Sony, …
Design goals: maximize performance, minimize cost,
reduce design time (time-to-market), minimize memory
space (embedded systems), minimize power
consumption (mobile systems)
CSE331 W02.9
Irwin 2007 PSU
RISC - Reduced Instruction Set Computer
 RISC
philosophy
fixed instruction lengths
 load-store instruction sets
 limited number of addressing modes
 limited number of operations

 MIPS,
Sun SPARC, HP PA-RISC, IBM
PowerPC …
 Instruction sets are measured by how well
compilers use them as opposed to how well
assembly language programmers use them
 CISC
CSE331 W02.10
(C for complex), e.g., Intel x86
Irwin 2007 PSU
The Four Design Principles
1.
2.
3.
4.
Simplicity favors regularity.
Smaller is faster.
Make the common case fast.
Good design demands good compromises.
CSE331 W02.11
Irwin 2007 PSU
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
 Operand order is fixed (the destination is specified
first)
 The
operands are contained in the datapath’s
register file ($t0, $s1, $s2)
CSE331 W02.13
Irwin 2007 PSU
Compiling More Complex Statements
variable b is stored in register $s1, c
is stored in $s2, and d is stored in $s3 and the
result is to be left in $s0, what is the
assembler equivalent to the C statement
h = (b - c) + d
 Assuming
CSE331 W02.15
sub
$t0, $s1, $s2
add
$s0, $t0, $s3
Irwin 2007 PSU
MIPS Register File
 Operands
of arithmetic instructions must be from a
limited number of special locations contained in the
Register File
datapath’s register file

Thirty-two 32-bit registers
- Two read ports
- One write port
 Registers

are
src1 addr
src2 addr
dst addr
write data
5
5
5
32 src1
data
25 = 32
locations
32 src2
32
Fast
data
32 bits
- Smaller is faster & Make the common case fast

Easy for a compiler to use
- e.g., (A*B) – (C*D) – (E*F) can do multiplies in any order

Improves code density
- Since register are named with fewer bits than a memory location
 Register
CSE331 W02.17
addresses are indicated by using $
Irwin 2007 PSU
Naming Conventions for Registers
0
$zero constant 0 (Hdware)
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
CSE331 W02.18
(caller can clobber)
31 $ra return address (Hdware)
Irwin 2007 PSU
Registers vs. Memory

Arithmetic instructions operands must be in
registers
only thirty-two registers are provided

Devices
Processor
Network
Control
Datapath

Memory
Input
Output
Compiler associates variables with registers
What about programs with lots of variables?
CSE331 W02.20
Irwin 2007 PSU
Processor – Memory Interconnections
 Memory is a large, single-dimensional array
 An address acts as the index into the memory
array
The word
address of the
data
Memory
read addr/ 32
write addr
Processor
?
locations
read data 32
32write data
The data stored in
the memory
CSE331 W02.22
10
101
1
32 bits
8
4
0
232 Bytes
(4 GB)
 230 Words
(1 GW)
= 4 Bytes = 1 Word
Irwin 2007 PSU
Accessing Memory
 MIPS
has two basic data transfer instructions for
accessing memory (assume $s3 holds 2410)
lw
sw
 The
$t0, 4($s3) #load word from memory
28
$t0, 8($s3) #store word to memory
32
data transfer instruction must specify
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
CSE331 W02.24
Irwin 2007 PSU
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
. . . 0001
lw
sw
CSE331 W02.26
$t0, 4($s3)
$t0, 8($s3)
...0110
24
...0101
20
...1100
16
...0001
12
...0010
8
...1000
4
...0100
32 bit Data
0
Word Address
. . . 0001
#what? is loaded into $t0
#$t0 is stored where?
in location 16
Irwin 2007 PSU
Compiling with Loads and Stores
variable b is stored in $s2 and that
the base address of array A is in $s3, what is
the MIPS assembly code for the C statement
A[8] = A[2] - b
 Assuming
...
...
A[3]
$s3+12
A[2]
$s3+8
A[1]
$s3+4
A[0]
$s3
CSE331 W02.28
lw
$t0, 8($s3)
sub
$t0, $t0, $s2
sw
$t0, 32($s3)
Irwin 2007 PSU
Compiling with a Variable Array Index
 Assuming
...
...
A[3]
$s4+12
A[2]
$s4+8
A[1]
$s4+4
A[0]
$s4
that the base address of
array A 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
add
$t1, $s3, $s3
#array index i is in $s3
add
$t1, $t1, $t1
#temp reg $t1 holds 4*i
add
$t1, $t1, $s4
#addr of A[i] now in $t1
lw
$t0, 0($t1)
sub
$s2, $t0, $s1
CSE331 W02.30
Irwin 2007 PSU
Dealing with Constants

Small constants are used quite frequently
(50% of operands in many common
programs)
e.g.,

Solutions? Why not?



A = A + 5;
B = B + 1;
C = C - 18;
Put “typical constants” in memory and load them
Create hard-wired registers (like $zero) for
constants like 1, 2, 4, 10, …
How do we make this work?

CSE331 W02.31
How do we Make the common case fast !
Irwin 2007 PSU
Constant (or Immediate) Operands

Include constants inside arithmetic instructions


Much faster than if they have to be loaded from
memory (they come in from memory with the
instruction itself)
MIPS immediate instructions
addi $s3, $s3, 4
#$s3 = $s3 + 4
There is no subi instruction, can you guess why
not?
CSE331 W02.32
Irwin 2007 PSU
MIPS Instructions, so far
Category
Instr
Arithmetic add
Data
transfer
CSE331 W02.33
Example
Meaning
add $s1, $s2, $s3 $s1 = $s2 + $s3
subtract
sub $s1, $s2, $s3 $s1 = $s2 - $s3
add
immediate
addi $s1, $s2, 4
$s1 = $s2 + 4
load word
lw
$s1, 32($s2)
$s1 = Memory($s2+32)
store word
sw $s1, 32($s2)
Memory($s2+32) = $s1
Irwin 2007 PSU
In may ways, legacy code is a more difficult
target for a new microarchitecture. A mountain
of x86 code has accumulated since the 1970s.
Designing an engine to correctly run both
legacy code and modern compiled code at
world-class performance levels is like
designing a new jet fighter to run on anything
from jet-A fuel to whale blubber and coal.
Bob Colwell, The Pentium Chronicles
CSE331 W02.35
Irwin 2007 PSU
Review: MIPS Organization
 Arithmetic instructions – to/from the register file
 Load/store
instructions - to/from memory
Memory
Processor
1…1100
Register File
src1 addr
src1
data
32
5
src2 addr
32
5
registers
dst addr
($zero - $ra)
src2
5
write data
32 data
32
32 bits
32 ALU
32
read/write
addr
230
words
32
read data
32
write data
32
32
4
0
byte address
(big Endian)
CSE331 W02.36
5
1
6
2
32 bits
7
3
0…1100
0…1000
0…0100
0…0000
word address
(binary)
Irwin 2007 PSU
Review: Unsigned Binary Representation
Hex
Binary
Decimal
0x00000000
0…0000
0
0x00000001
0…0001
1
231 230 229
...
23 22 21
20
bit weight
0
bit position
0x00000002
0…0010
2
0x00000003
0…0011
3
31 30 29
...
3
0x00000004
0…0100
4
1 1 1
...
1 1 1 1
bit
0x00000005
0…0101
5
0x00000006
0…0110
6
0x00000007
0…0111
7
1 0 0 0
...
0 0 0 0
-
0x00000008
0…1000
8
0x00000009
0…1001
9
1
232 - 1
…
0xFFFFFFFC 1…1100
232 - 4
0xFFFFFFFD 1…1101
232 - 3
0xFFFFFFFE
1…1110
0xFFFFFFFF
1…1111
232 - 2
232 - 1
CSE331 W02.37
2
Irwin 2007 PSU
1
Review: Signed Binary Representation
2’sc binary
-23 =
1000
-(23 - 1) =
1001
1010
1011
complement all the bits
1100
1011
0101
1101
1110
and add a 1 and add a 1
1111
1010
0110
0000
0001
complement all the bits
0010
0011
0100
0101
23 - 1 =
CSE331 W02.38
0110
decimal
-8
-7
-6
-5
-4
-3
-2
-1
0
1
2
3
4
5
6 Irwin 2007 PSU
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?
CSE331 W02.40
Irwin 2007 PSU
MIPS Instruction Fields
 op
op
rs
rt
rd
shamt
6 bits
5 bits
5 bits
5 bits
5 bits
funct
6 bits
= 32 bits
 rs
opcode indicating operation to be performed
address of the first register source operand
 rt
address of the second register source operand
 rd
the register destination address
 shamt shift amount (for shift instructions)
 funct
CSE331 W02.42
function code that selects the specific variant of
the operation specified in the opcode field
Irwin 2007 PSU
Machine Language - Load Instruction

Consider the load-word and store-word instr’s

What would the regularity principle have us do?
- But . . . Good design demands compromise

Introduce a new type of instruction format


I-type for data transfer instructions (previous format
was R-type for register)
Example: lw $t0, 24($s2)
op
rs
rt
16 bit number
23hex
18
8
100011
10010
01000
24
0000000000011000
Where's the compromise?
CSE331 W02.44
Irwin 2007 PSU
Memory Address Location
 Example:
lw $t0, 24($s2)
Memory
0xf f f f f f f f
2410 + $s2 =
$t0
0x00000002
. . . 1001 0100
+ . . . 0001 1000
. . . 1010 1100 =
0x120040ac
0x12004094
$s2
Note that the offset
can be positive or
negative
data
CSE331 W02.46
0x120040ac
0x0000000c
0x00000008
0x00000004
0x00000000
word address (hex)
Irwin 2007 PSU
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 offset means access is limited to
memory locations within a range of +213-1 to
-213 (~8,192) words (+215-1 to -215 (~32,768)
bytes) of the address in the base register $s2

CSE331 W02.48
2’s complement (1 sign bit + 15 magnitude bits)
Irwin 2007 PSU
Machine Language – Immediate Instructions

What instruction format is used for the addi ?
addi $s3, $s3, 4 #$s3 = $s3 + 4

Machine format:
op
8

rs
rt
19
19
16 bit immediate
I format
4
The constant is kept inside the instruction itself!


So must use the I format – Immediate format
Limits immediate values to the range +215–1 to -215
CSE331 W02.50
Irwin 2007 PSU
Instruction Format Encoding
 Can
reduce the complexity with multiple formats
by keeping them as similar as possible

First three fields are the same in R-type and I-type
 Each
format has a distinct set of values in the
op field
Instr
Frmt
op
rs
rt
rd
shamt funct
address
add
R
0
reg
reg reg 0
32ten NA
sub
R
0
reg
reg reg 0
34ten NA
addi
I
8ten
reg
reg NA NA
NA
constant
lw
I
35ten reg
reg NA NA
NA
address
sw
I
43ten reg
reg NA NA
NA
address
CSE331 W02.51
Irwin 2007 PSU
Assembling Code
 Remember
the assembler code we compiled
last lecture 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 (decimal is fine)
lw
35
19
8
sub
0
8
18
sw
43
19
8
CSE331 W02.53
8
8
0
34
32
Irwin 2007 PSU
Review: MIPS Instructions, so far
Category
Instr
Arithmetic add
(R format)
subtract
Op
Code
Example
Meaning
0&
32
add $s1, $s2, $s3 $s1 = $s2 + $s3
0&
34
sub $s1, $s2, $s3 $s1 = $s2 - $s3
Arithmetic add
(I format) immediate
8
addi $s1, $s2, 4
$s1 = $s2 + 4
Data
transfer
(I format)
load word
35
lw $s1, 100($s2)
$s1 = Memory($s2+100)
store word
43
sw $s1, 100($s2)
Memory($s2+100) = $s1
CSE331 W02.54
Irwin 2007 PSU
Two Key Principles of Machine Design
1.
2.
Instructions are represented as numbers
Programs are stored in memory to be read or
written, just like numbers
Memory
 Stored-program
concept
Programs can be shipped as
files of binary numbers –
binary compatibility
 Computers can inherit readymade software provided they
are compatible with an
existing ISA – leads industry
to align around a small
number of ISAs

CSE331 W02.55
Accounting prg
(machine code)
C compiler
(machine code)
Payroll
data
Source code in
C for Acct prg
Irwin 2007 PSU
Review: MIPS R3000 ISA
 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
6 bits
5 bits
5 bits
5 bits
rd
OP
rs
rt
OP
rs
rt
OP
CSE331 W02.56
5 bits
shamt
16 bit number
6 bits
funct
R format
I format
26 bit jump target
Irwin 2007 PSU