UCCD1133
Introduction to Computer Organisation and Architecture
Chapter 4
Computer Architecture and Organisation Fundamental
Slides adapted from http://booksite.elsev1ier.com
Disclaimer
• This slide may contain copyrighted material of which has not been specifically authorized by the copyright owner. The use of copyrighted materials are solely for educational purpose. If you wish to use this copyrighted material for other purposes, you must first obtain permission from the original copyright owner.
2
Outline
• Overview
• Assembly Language
• Machine Language
• Programming
• Addressing Modes
• The Memory Map
Architecture: programmer’s view of computer. Defined by instructions & operand locations
Page <3>
Overview
Page <4>
Chapter 4-1
MIPS Assembly Language
5
Assembly Language
• Instructions: commands in a computer’s language
• Assembly language: human-readable format of instructions • Machine language: computer-readable format (1’s and 0’s)
• Instruction set: the vocabulary of commands understood by a given architecture.
• MIPS architecture:
• Developed by John Hennessy and his colleagues at Stanford and in the
1980’s.
• Used in many commercial systems, including Silicon Graphics, Nintendo, and Cisco
• Other instruction set architectures: Intel x86, ARM
• Once you’ve learned one architecture, it’s easy to learn others.
Page <6>
Assembly Language
❑ Four design principles of computer architecture Simplicity favors regularity
Make the common case fast Smaller is faster
Good design demands compromise
Page <7>
MIPS Assembly Language
❑ Examples of core instructions sets:
Category
Instruction
Arithmetic
add (add), subtract (sub), add immediate (addi)
Data transfer
load word (lw), store word (sw), load byte (lb), store byte (sb), load upper immediate (lui)
Logical
and (and), or (or), nor (nor),
and immediate (andi), or immediate (ori), shift left logical (sll),
shift right logical (srl)
Conditional branch
branch on equal (beq), branch on not equal (bne), set on less than (slt)
Unconditional jump
Jump (j), jump register (jr), jump and link (jal)
Page <8>
Instructions: Arithmetic
Addition
MIPS assembly code C Code
add a, b, c a = b + c;
• add: mnemonic indicates operation to perform
• b, c: source operands (on which the operation is performed)
• a: destination operand (to which the result is written)
Page <9>
Instructions: Arithmetic
Subtraction
•
Similar to addition – only mnemonic changes
MIPS assembly code
sub a, b, c
C Code
a = b – c;
•
•
• a: destination operand
sub: mnemonic
b, c: source operands
Page <10>
Design Principles 1
Simplicity favors regularity
• MIPS has consistent instruction format
• Same number of operands (two sources and one destination) • Easier to encode and handle in hardware
Page <11>
Instructions: Arithmetic
Multiple Instructions
• More complex code is handled by multiple MIPS instructions.
C Code MIPS assembly code
a = b + c – d; add t, b, c # t = b + c sub a, t, d # a = t – d
Page <12>
Design Principles 2
Make the common case fast
• MIPS includes only simple, commonly used instructions
• Hardware to decode and execute instructions can be simple, small, and
fast
• More complex instructions (that are less common) performed using multiple simple instructions
• MIPS is a reduced instruction set computer (RISC), with a small number of simple instructions
• Other architectures, such as Intel’s x86, are complex instruction set computers (CISC)
Page <13>
CISC vs RISC
Page <14>
Operands
• Operand location: physical location in computer – Registers
– Memory
– Constants (also called immediates)
Location
Example
Comments
32 Registers
$t0 … $t7 $s0 … $s7 $sp, $ra
• Fast locations for data.
• In MIPS, data must be in registers to
perform arithmetic
230 memory words
Mem[0],
Mem[4],
… Mem[4294967292]
• Accessed only by data transfer instructions (load & store).
• MIPS uses byte addresses, so sequential word addresses differ by 4.
Page <15>
Operands: Registers
• MIPS has 32 32-bit registers
• Registers are faster than memory
• MIPS is called “32-bit architecture” because it operates on 32-bit data
Name
Register Number
Usage
$0
0
the constant value 0
$at
1
assembler temporary
$v0-$v1
2-3
Function return values
$a0-$a3
4-7
Function arguments
$t0-$t7
8-15
temporaries
$s0-$s7
16-23
saved variables
$t8-$t9
24-25
more temporaries
$k0-$k1
26-27
OS temporaries
$gp
28
global pointer
$sp
29
stack pointer
$fp
30
frame pointer
$ra
31
Function return address
Page <16>
Operands: Registers
• Registers:
• $beforename
• Example: $0, “register zero”, “dollar zero”
• Registers used for specific purposes:
• $0 always holds the constant value 0.
• the saved registers, $s0-$s7, used to hold variables
• the temporary registers, $t0 – $t9, used to hold intermediate values during a larger computation
• Discuss others later
Page <17>
Design Principles 3
Smaller is Faster
• MIPS includes only a small number of registers
• A very large number of registers may increase the clock cycle time because it takes electronic signals longer when they must travel farther.
Page <18>
Instructions: Arithmetic Instructions with Registers
•
Revisit add instruction
C Code
a = b + c
MIPS assembly code
# $s0 = a, $s1 = b, $s2 = c add $s0, $s1, $s2
Operands are replaced by registers.
Page <19>
Operands: Memory
• Too much data to fit in only 32 registers
• Store more data in memory
• Memory is large, but slow
• Commonly used variables kept in registers
Page <20>
Byte-Addressable Memory
• Each data byte has unique address
• 32-bit word = 4 bytes, so word address increments by 4
Word Address Data
40
F3
07
88
01
EE
28
42
F2
F1
AC
07
AB
CD
EF
78
0000000C
00000008
00000004
00000000
Word 3 Word 2 Word 1 Word 0
width = 4 bytes
• The address of a memory word must be multiplied by 4. For example,
– the address of memory word 2 is 2 × 4 = 8
– the address of memory word 10 is 10 × 4 = 40 (0x28)
Page <21>
Instructions: Data Transfer Reading and Write the Memory
• Memory read is called load
• Mnemonic: load word (lw)
• Example: lw $s0, 4($t1)
• Address calculation:
– add base address ($t1) to the offset (4)
– address = ($t1 + 4)
– Result: $s0 holds the value at address ($t1 + 4)
– Any register may be used as base address
• Memory write are called store
• Mnemonic: store word (sw)
• Example: sw $t7, 44($0)
Page <22>
Instructions: Data Transfer
Reading Byte-Addressable Memory
• Example:
Load a word of data at memory address 4 into $s3.
MIPS assembly code
lw $s3, 4($0) # read word at address 4 into $s3
Word Address Data
40
F3
07
88
01
EE
28
42
F2
F1
AC
07
AB
CD
EF
78
0000000C
00000008
00000004
00000000
Word 3 Word 2 Word 1 Word 0
width = 4 bytes
• $s3holdsthevalue0xF2F1AC07afterload.
Page <23>
Instructions: Data Transfer
Writing Byte-Addressable Memory
• Example:
stores the value held in $t7 into memory address 0x2C (44)
MIPS assembly code
sw $t7, 44($0) # write $t7 into address 44
Word Address Data
40
F3
07
88
01
EE
28
42
F2
F1
AC
07
AB
CD
EF
78
0000000C
00000008
00000004
00000000
Word 3 Word 2 Word 1 Word 0
width = 4 bytes
Page <24>
Big-Endian & Little-Endian Memory
• How to number bytes within a word?
• Little-endian: byte numbers start at the little (least significant) end
• Big-endian: byte numbers start at the big (most significant) end
• Word address is the same for big- or little-endian
Big-Endian
Byte Address
W ord Address
C 8 4 0
Little-Endian
Byte Address
C
D
E
F
8
9
A
B
4
5
6
7
0
1
2
3
F
E
D
C
B
A
9
8
7
6
5
4
3
2
1
0
MSB LSB
MSB LSB
Page <25>
Big-Endian & Little-Endian Memory
• Jonathan Swift’s Gulliver’s Travels: the Little-Endians broke their eggs on the little end of the egg and the Big-Endians broke their eggs on the big end
• It doesn’t really matter which addressing type used – except when the two systems need to share data!
Big-Endian
Byte Address
W ord Address
C 8 4 0
Little-Endian
Byte Address
C
D
E
F
8
9
A
B
4
5
6
7
0
1
2
3
F
E
D
C
B
A
9
8
7
6
5
4
3
2
1
0
MSB LSB
MSB LSB
Page <26>
Big-Endian & Little-Endian Example
• Suppose$t0 initiallycontains0x23456789
• After following code runs on big-endian system, what value is $s0?
• In a little-endian system?
sw $t0, 0($0)
lb $s0, 1($0)
Page <27>
Big-Endian & Little-Endian Example
• Suppose$t0 initiallycontains0x23456789
• After following code runs on big-endian system, what value is $s0?
• In a little-endian system?
sw $t0, 0($0)
lb $s0, 1($0)
• Answer:
• Big-endian: 0x00000045 • Little-endian: 0x00000067
Note: MIPS is big endian
Byte Address Data Value
Big-Endian
0 1 2 3
Word Address
0
Little-Endian
3 2 1 0
Byte Address Data Value
23
45
67
89
23
45
67
89
MSB
LSB
MSB
LSB
Page <28>
Design Principles 4
Good design demands good compromises
❑ MIPS Multiple instruction formats allow flexibility
– add, sub: use 3 register operands
– lw, sw: use 2 register operands and a constant
❑ Number of instruction formats kept small
– to adhere to design principles 1 and 3 (simplicity favors regularity and smaller is faster).
Page <29>
Operands: Constants/Immediates
• lwandswuseconstantsorimmediates
• immediately available from instruction
• 16-bit two’s complement number
• addi:addimmediate
• Subtract immediate (subi) necessary?
C Code
a = a + 4;
b = a – 12;
MIPS assembly code
# $s0 = a, $s1 = b addi $s0, $s0, 4 addi $s1, $s0, -12
Page <30>
Chapter 4-2
Machine Language
31
Machine Language
• Binary representation of instructions
• Computers only understand 1’s and 0’s
• 32-bit instructions
• Simplicity favors regularity: 32-bit data &
instructions
• 3 instruction formats:
• R-Type: register operands
• I-Type: immediate operand
• J-Type: for jumping (discuss later)
Recall
Decimal
Binary
Hexadecimal
0
0000
0
1
0001
1
2
0010
2
3
0011
3
4
0100
4
5
0101
5
6
0110
6
7
0111
7
8
1000
8
9
1001
9
10
1010
a
11
1011
b
12
1100
c
13
1101
d
14
1110
e
15
1111
f
Page <32>
R-Type
• Register-type
• 3 register operands:
– rs, rt:
– rd:
• Other fields:
– op:
– funct:
– shamt:
source registers destination register
the operation code or opcode (0 for R-type instructions) the function with opcode, tells computer what operation to
perform
the shift amount for shift instructions, otherwise it’s 0
R-Type
5 bits 5 bits 5 bits 5 bits 6 bits
op
rs
rt
rd
shamt
funct
6 bits
Page <33>
R-Type Examples
Assembly Code
add $s0, $s1, $s2 sub $t0, $t3, $t5
Field Values
op
6 bits
rs
5 bits
rt
5 bits
rd
5 bits
shamt funct
0
17
18
16
0
32
op
6 bits
Machine Code
rs rt rd shamt funct
5 bits 5 bits 5 bits 5 bits 6 bits
(0x02328020) (0x016D4022)
0
11
13
8
0
5 bits
6 bits
34
000000
10001
10010
10000
00000
100000
000000
01011
01101
01000
00000
100010
Note the order of registers in the assembly code: add rd, rs, rt
Page <34>
I-Type
• Immediate-type
• 3 operands: – rs,rt:
– imm:
• Other fields:
– op:
– Simplicity favors regularity: all instructions have opcode
– Operation is completely determined by opcode
registeroperands
16-bit two’s complement immediate
op
rs
rt
imm
6 bits
I-Type
5 bits 5 bits 16 bits
the opcode
Page <35>
I-Type Examples
Assembly Code
addi $s0, $s1, 5
addi $t0, $s3, -12
lw $t2, 32($0)
sw $s1, 4($t1)
Field Values
op rs rt imm
8
17
16
5
8
19
8
-12
35
0
10
32
43
9
17
4
Note the differing order of registers in assembly and machine codes:
addi rt, rs, imm
lw rt, imm(rs)
sw rt, imm(rs)
Machine Code
6 bits
5 bits
5 bits
16 bits
op rs rt imm
001000
10001
10000
0000 0000 0000 0101
001000
10011
01000
1111 1111 1111 0100
100011
00000
01010
0000 0000 0010 0000
101011
01001
10001
0000 0000 0000 0100
(0x22300005) (0x2268FFF4) (0x8C0A0020) (0xAD310004)
6 bits
5 bits
5 bits
16 bits
Page <36>
Machine Language: J-Type
• Jump-type
• 26-bit address operand (addr)
• Used for jump instructions (j)
op
addr
6 bits
J-Type
26 bits
Page <37>
Review: Instruction Formats
op
rs
rt
rd
shamt
funct
6 bits
5 bits
R-Type
5 bits 5 bits
I-Type
5 bits
J-Type
26 bits
5 bits
6 bits
op
rs
rt
imm
6 bits
5 bits
16 bits
op
addr
6 bits
Page <38>
Power of the Stored Program
• Instructions represented in binary, just like data
• Instructions and data stored in memory
• Programs can operate on programs
• e.g., compilers, linkers, …
• Binary compatibility allows compiled programs to work on different computers
• Standardized ISAs
The BIG Picture
Page <39>
Power of the Stored Program
• 32-bit instructions & data stored in memory
• Sequence of instructions: only difference between two applications
• To run a new program:
– No rewiring required
– Simply store new program in memory
• Program Execution:
– Processor fetches (reads) instructions from memory in sequence
– Processor performs the specified operation
Page <40>
The Stored Program
Assembly Code
lw $t2, 32($0)
add $s0, $s1, $s2
addi $t0, $s3, -12
sub $t0, $t3, $t5
Machine Code
0x8C0A0020
0x02328020
0x2268FFF4
0x016D4022
Stored Program
Address
0040000C
00400008
00400004
00400000
Instructions
016D4022
2268FFF4
02328020
8C0A0020
PC
Program Counter (PC): keeps track of current instruction
Main Memory
Page <41>
Interpreting Machine Code
• Start with opcode: tells how to parse rest
• If opcode all 0’s
– R-type instruction
– Function bits tell operation
• Otherwise
– opcode tells operation
001000
10001
10111
1111 1111 1111 0001
8
17
23
-15
(0x2237FFF1)
(0x02F34022)
op
op
op rs rt imm
op rs rt rd
shamt funct
Machine Code
rs rt imm
2237FFF1
rs rt rd shamt funct
02F34022
Field Values
Assembly Code
addi $s7, $s1, -15
sub $t0, $s7, $s3
000000
10111
10011
01000
00000
100010
0
23
19
8
0
34
Page <42>