Amdahl's Law

Execution Time After Improvement =

Execution Time Unaffected +( Execution Time Affected / Amount of Improvement )

Time before

Improvement

Time after
Improvement
Amdahl’s Law
Example: Executing a program on n independent processors

Fractionenhanced = parallelizable part of program

Speedup =n
enhanced
ExTime oldFractionenhanced
ExTime = ExTime (1- Fractionenhanced )+
old
new n

ExTime old 1
Speedup overall  
ExTimenew Fraction enhanced
1  Fractionenhanced  
Speedup enhanced


Lim Speedup = 1 / (1 - Fraction )
n overall enhanced

BITS Pilani, Pilani Campus

Reduced Instruction Set Computer

- Relatively few instructions

- Relatively few addressing modes
- Memory access limited to load and store
- Fixed length and easily decodable instruction format
- Relatively large number of registers in the processor
- Efficient Instruction pipeline

BITS Pilani, Pilani Campus

Example - RISC Architectures

-Hewlett Packard PA- RISC

-IBM and MOTOROLA Power PC
-SGI MIPS
-SPARC Developed by SUN Microsystems
-ARM Advanced RISC machine

BITS Pilani, Pilani Campus

RISC - ARCHITECTURE

We’ll be working with the MIPS instruction set architecture

 used by NEC, Nintendo, Silicon Graphics, Sony

 the name is not related to million instructions per second
 it stands for microcomputer without interlocked pipeline
stages

BITS Pilani, Pilani Campus

MIPS Arithmetic

• All MIPS arithmetic instructions have 3 operands

• Operand order is fixed (e.g., destination first)

• Example:
compiler’s job to associate
variables with registers
C code: A = B + C

MIPS code: add $s0, $s1, $s2

MIPS Arithmetic
• Design Principle 1: simplicity favors regularity.
Translation: Regular instructions make for simple hardware!

• Simpler hardware reduces design time and manufacturing cost.

Allowing variable number
• Of course this complicates some things... of operands would
simplify the assembly
C code: A = B + C + D; code but complicate the
E = F - A; hardware.

MIPS code add $t0, $s1, $s2

(arithmetic): add $s0, $t0, $s3
sub $s4, $s5, $s0

• Performance penalty: high-level code translates to denser machine

code.
 Operands must be in registers – only 32 registers provided (which
require 5 bits to select one register).
MIPS (Microprocessor without Interlocked Pipeline Stages)

Register Set:

For Integer operations 32 bit general purpose registers- Numbered

0 to 31.

Register $0 Special purpose , value always zero, used to synthesize

a variety of functions.

Floating point registers (FPRs) used as single precision (32-bit)

registers.

BITS Pilani, Pilani Campus

Registers vs. Memory
• Arithmetic instructions operands must be in registers
– MIPS has 32 registers
• Compiler associates variables with registers
• What about programs with lots of variables (arrays, etc.)?
Use memory, load/store operations to transfer data from
memory to register – if not enough registers spill registers
to memory . MIPS is a load/store architecture

Control Input
Memory
Datapath Output

Processor I/O
Memory Organization
• Bytes are load/store units, but most data items use larger
words
• For MIPS, a word is 32 bits or 4 bytes.
•0 32 bits of data
4 32 bits of data Registers correspondingly hold 32 bits of data
8 32 bits of data
12 32 bits of data

...

• 232 bytes with byte addresses from 0 to 232-1

• 230 words with byte addresses 0, 4, 8, ... 232-4
– i.e., words are aligned
Load/Store Instructions
• Load and store instructions
• Example:
C code: A[8] = h + A[8]; address
value offset
MIPS code (load): lw $t0, 32($s3)
(arithmetic): add $t0, $s2, $t0
(store): sw $t0, 32($s3)

• Load word has destination first, store has destination last

• MIPS arithmetic operands are registers, not memory locations.
– Therefore, words must first be moved from memory to registers using
loads before they can be operated on; then result can be stored back to
memory
Machine Language
• Instructions, like registers and words of data, are also 32 bits
long
– Example: add $s4, $s1, $s2
• Instruction Format R-type (“R” for arithmetic):

000000 10001 10010 01000 00000 100000

op rs rt rd shamt funct
opcode – first second register shift function field -
operation register register destin- amount selects variant
source source ation of operation
operand operand operand

6 bits 5 bits 5 bits 5 bits 5 bits 6 bits

MIPS Encoding: R-Type

31 26 25 21 20 16 15 11 10 6 5 0

opcode rs rt rd shamt funct

rd

rt
add $4, $3, $2

rs

31 26 25 21 20 16 15 11 10 6 5 0
0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0
opcode rs rt rd shamt funct

0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0

Encoding = 0x00622020
13
Machine Language
• Consider the load-word and store-word instructions,
– what would the regularity principle have us do?
• we would have only 5 or 6 bits to determine the offset from a base
register

• Design Principle : Good design demands a compromise

• Introduce a new type of instruction format
– I-type (“I” for Immediate) for data transfer instructions
– Example: lw $s4, 1002($s2)

100011 10010 01000 0000001111101010

6 bits 5 bits 5 bits 16 bits

op rs rt 16 bit offset
MIPS Encoding: I-Type
31 26 25 21 20 16 15 0

opcode rs rt Immediate Value

rt
Immediate
lw $5, 3000($2)

rs

31 26 25 21 20 16 15 0
1 0 0 0 1 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 1 1 0 1 1 1 0 0 0
opcode rs rt Immediate Value

1 0 0 0 1 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 1 1 0 1 1 1 0 0 0

Encoding = 0x8C450BB8
15
MIPS Encoding: I-Type
31 26 25 21 20 16 15 0

opcode rs rt Immediate Value

rt
Immediate
sw $5, 3000($2)

rs

31 26 25 21 20 16 15 0
1 0 1 0 1 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 1 1 0 1 1 1 0 0 0
opcode rs rt Immediate Value

1 0 1 0 1 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 1 1 0 1 1 1 0 0 0

Encoding = 0xAC450BB8
16
The immediate value is signed
Control: Conditional Branch
• Decision making instructions
– alter the control flow,
• i.e., change the next instruction to be executed

• MIPS conditional branch instructions:

bne $t0, $t1, Label I-type instructions

beq $t0, $t1, Label
beq $t0, $t1, Label
000100 01000 01001 0000000000011001 (= addr.100)

• Example: if (i==j) h = i + j; word-relative addressing:

25 words = 100 bytes;
bne $s0, $s1, Label also PC-relative (more…)
add $s3, $s0, $s1
Label: ....
Addresses in Branch
• Instructions:
bne $t4,$t5,Label Next instruction is at Label if $t4 != $t5
beq $t4,$t5,Label Next instruction is at Label if $t4 = $t5
• Format:
I op rs rt 16 bit offset

• 16 bits is too small a reach in a 232 address space

• Solution: specify a register (as for lw and sw) and add it to offset
– use PC (= program counter), called PC-relative addressing, based on
– principle of locality: most branches are to instructions near current
instruction (e.g., loops and if statements)
Control: Unconditional Branch (Jump)

• MIPS unconditional branch instructions:

j Label
• Example:
if (i!=j) beq $s4, $s5, Lab1
h=i+j; add $s3, $s4, $s5
else j Lab2
h=i-j; Lab1: sub $s3, $s4, $s5
Lab2: ...
• J-type (“J” for Jump) instruction format
– Example: j Label # addr. Label = 100

000010 00000000000000000000011001
6 bits 26 bits
op 26 bit number
Addresses in Jump
• Word-relative addressing also for jump instructions
J op 26 bit address

• MIPS jump j instruction replaces lower 28 bits of the PC with A00

where A is the 26 bit address; it never changes upper 4 bits
– Example: if PC = 1011X (where X = 28 bits), it is replaced with
1011A00
– there are 16(=24) partitions of the 232 size address space, each
partition of size 256 MB (=228), such that, in each partition the upper
4 bits of the address is same.
– if a program crosses an address partition, then a j that reaches a
different partition has to be replaced by jr with a full 32-bit
address first loaded into the jump register
Immediate Operands
• Make operand part of instruction itself

• Example: addi $sp, $sp, 4 # $sp = $sp +

4

001000 11101 11101 0000000000000100

6 bits 5 bits 5 bits 16 bits

op rs rt 16 bit number
How about larger constants?
• First we need to load a 32 bit constant into a register
• Must use two instructions for this: first new load upper immediate
instruction for upper 16 bits
lui $t2, 1010101010101010 filled with zeros

1010101010101010 0000000000000000

• Then get lower 16 bits in place:

ori $t2, $t2, 1010101010101010
1010101010101010 0000000000000000

0000000000000000 1010101010101010
ori
1010101010101010 1010101010101010

• Now the constant is in place, use register-register arithmetic

Logical Operations
Shift Logical Left (SLL $S1,$S2,10)
Shift Logical Right (SRL $S1,$S2,10)
AND (AND $S1,$S2,$S3)
OR (OR $S1,$S2,$S3)
NOR (NOR $S1,$S2,$S3)
ANDI (ANDI $S1,$S2,100)
ORI (ORI $S1,$S2,100)