Introduction to RISC
Architecture
RISC vs CISC
• AIM Multiply the numbers stored in
address 1:2 and 2:1 and store the
result in 4:2
• CISC approach
MULT (4:2)(1:2)(2:1)
• RISC approach
LOAD A,1:2
LOAD B,2:1
MULT A,B
2
STORE (4:2),A
Performance equation
o RISC aims to reduce cycles/instruction and CISC aims to
reduce instructions/program
CISC RISC
Emphasis on hardware Emphasis on software
Includes multi-clock Single-clock,
complex instructions reduced instruction only
Memory-to-memory: Register to register:
"LOAD" and "STORE" "LOAD" and "STORE"
incorporated in instructions are independent instructions
Small code sizes, Low cycles per second,
high cycles per second large code sizes
Transistors used for storing Spends more transistors
complex instructions on memory registers 3
MIPS Processor
oRISC processor introduced in 1985
oMany design principles and instructors still used by latest
ARM processors
oPredecessor of RISC V processors
o32 and 64 bit versions are available (word size)
oThirty two 32-bit general purpose registers – GPRs (r0 – r31)
oThirty two 32-bit floating point registers – FPRs (f0 – f31)
o32-bit program counter – PC
4
MIPS Compiler Conversions (32-bit int registers)
Name Register number Usage
$zero 0 the constant value 0
$v0-$v1 2-3 values for results and expression evaluation
$a0-$a3 4-7 arguments
$t0-$t7 8-15 temporaries
$s0-$s7 16-23 saved (by callee)
$t8-$t9 24-25 more temporaries
$gp 28 global pointer
$sp 29 stack pointer
$fp 30 frame pointer
$ra 31 return address
5
MIPS arithmetic
oMost instructions have 3 operands
oOperand order is fixed (destination first)
Example:
C code: A=B+C
MIPS code: add $s0, $s1, $s2
($s0, $s1 and $s2 are associated with registers by compiler)
6
MIPS arithmetic
oC code: A = B + C + D;
E = F - A;
MIPS code: add $t0, $s1, $s2
add $s0, $t0, $s3
sub $s4, $s5, $s0
oOperands must be registers (unlike x86)
oOnly 32 registers provided
oIf data is not already in registers, first they should be copied
from memory to registers before operating 7
MIPS Alignment Requirement
oMIPS restricts memory accesses to be aligned as follows:
o32-bit word must start at byte address that is multiple of 4
o32-bit word at address 4n includes four bytes with addresses
4n, 4n+1, 4n+2, and 4n+3
o16-bit half word must start at byte address that is multiple of 2
o16-bit word at address 2n includes two bytes with addresses
2n and 2n+1
o8-bit data will be always aligned since the memory is still
considered byte aligned from the processor perspective
8
MIPS Alignment Requirement
31 23 15 7 0
0 this word is aligned; the others are not!
4
address 8
12
16
20
24
9
MIPS Addressing Modes
o Register addressing
o Immediate addressing
o register content plus offset (register indexed)
o r0 + offset absolute addressing
10
Load Store Instructions
o As discussed before, operands should be in registers before
any arithmetic/logic operations
o Result of arithmetic/logic operations should be also stored in
registers
o Using load instruction, data is moved from memory to
registers
o Using store instruction, data is moved from register to
memory
11
Load/Store Instructions
oExample:
C code: A[8] = h + A[8];
MIPS code:
lw $t0, 32($s3) ;assumes
address of A is in s3 register. $s3+32 is
address of A[8]
add $t0, $s2, $t0 ;assumes h is
already in s2 register
12
sw $t0, 32($s3)
Loading/Storing immediate 32-bit data
oFor loading 32-bit immediate data, 2 instructions are required
o"load upper immediate" followed by or immediate
lui $t0, 1010101010101010b
ori $t0, $t0, 1010101010101010
olui instruction automatically fills the lower 16 bits with zeros
oInstead of ori, addi (add immediate) can be also used
oFor storing 32-bit immediate data, it must be first stored in a
32-bit register (using lui and ori) and using sw instruction it
can be copied to memory
13
Instruction Set Architecture
o There are mainly 3 types of instructions
o Register (R-type)
o Immediate (I-type)
o Jump Type (J-type)
14
R-type Instructions
o Instructions, like registers, and words of data, are also
32 bits long
o Example: add $t0, $s1, $s2
o Registers have numbers: $t0=9, $s1=17, $s2=18
15
I-type Instructions
o I-type for data transfer instructions
o other format was R-type for register
o Example: lw $t0, 32($s2)
35 18 8 32
op rs rt Immediate Data
6 bits 5 bits 5 bits 16 bits
16
J-type Instructions
o MIPS unconditional branch instruction
j label
o MIPS conditional branch instructions
beq $s4, $s5, Lab1 ;branch if equal
bne $s4, $s5, Lab1 ;branch if not
equal
op (6 bits) 26 bit offset address
oMIPS calculates branch address as (PC+4) +
offset*4 17
MIPS Code to sort an array
.data
array: .word 5, 3, 8, 1, 2 # Array to sort
n: .word 5 # Number of elements
.text
.globl main
main:
# Load base address of array into $t0
lui $t0, %hi(array)
ori $t0, $t0, %lo(array)
# Load n into $t1
lui $t9, %hi(n)
ori $t9, $t9, %lo(n)
lw $t1, 0($t9)
addi $t1, $t1, -1 # $t1 = n - 1
add $t4, $t1, $zero # $t4 = outer loop counter (i)
18
MIPS Code to sort an array
outer_loop:
add $t5, $t4, $zero # $t5 = inner loop counter (j)
add $t6, $zero, $zero # $t6 = j index (0)
inner_loop:
# Reload base address of array
lui $t0, %hi(array)
ori $t0, $t0, %lo(array)
# Compute offset: offset = j * 4
sll $t7, $t6, 2 # $t7 = j * 4
add $t8, $t0, $t7 # $t8 = address of array[j]
lw $t9, 0($t8) # $t9 = array[j]
lw $s0, 4($t8) # $s0 = array[j+1]
slt $s1, $t9, $s0 # if $t9 < $s0 => $s1 = 1
beq $s1, $zero, do_swap # if array[j] >= array[j+1], swap
19
MIPS Code to sort an array
skip_swap:
addi $t6, $t6, 1 # j++
addi $t5, $t5, -1 # inner loop counter--
bgtz $t5, inner_loop # if j > 0, continue
j check_outer
do_swap:
sw $s0, 0($t8) # array[j] = array[j+1]
sw $t9, 4($t8) # array[j+1] = array[j]
j skip_swap
check_outer:
addi $t4, $t4, -1 # i--
bgtz $t4, outer_loop # if i > 0, continue
end:
addi $v0, $zero, 10 # syscall 10: exit
syscall
20
8086 Code to sort an array
.model tiny
.data
arr dw 5, 3, 8, 1, 2 ; array of 5 elements
n dw 5 ; number of elements
.code
start:
mov cx, n ; outer loop counter = n
dec cx ; outer loop runs n-1 times
outer_loop:
push cx ; save outer loop counter
mov si, 0 ; SI = index
mov cx, n
dec cx ; inner loop runs n-1 times
inner_loop:
mov bx, si
21
8086 Code to sort an array
shl bx, 1 ; offset = index * 2 (word size)
mov ax, arr[bx] ; AX = arr[si]
mov dx, arr[bx+2] ; DX = arr[si+1]
cmp ax, dx
jbe no_swap ; if arr[si] <= arr[si+1], skip swap
; swap arr[si] and arr[si+1]
mov arr[bx], dx
mov arr[bx+2], ax
no_swap:
inc si
loop inner_loop
pop cx ; restore outer loop counter
loop outer_loop
exit:
mov ah, 4Ch
int 21h
end start
MIPS is using ~25% more instructions 22
MIPS Processor Design
o With the information that we have seen till now, let’s try to build a
processor
o We will design a rudimentary MIPS processor
o Remember the first step in a processor design is to decide word
size, what operations will be supported by the processor etc.
(architecture)
o Now we have to design the instruction set and decide how the
opcodes, registers etc. will be encoded in binary format (instruction
set design)
o Now finally we design the hardware which works based on this
instruction set (organization, micro-architecture)
23
MIPS Processor Design
oMIPS follows Harvard architecture
oWe have separate memory to store instructions and data
oThe memory which stores instruction we call it instruction
memory and the memory which stores data we call it data
memory
oProcessor cannot write to instruction memory
oIt has an address bus, which accepts the address of the
instruction and spits out the instruction through the data bus
24
Program Counter
o We know every instruction of MIPS is 32 bits long (4 bytes)
o The programme counter (PC) is a 32 bit register which points to
the instruction memory from where the instruction will be fetched
o So, after reading an instruction, for PC to point to the next
instruction, it should be incremented by 4 (again remember unit of
memory is byte)
o Now we are considering the case where there are no branching
(processor is always executing sequentially one instruction after
the other)
25
Program Counter
oThe output of programme counter is given to an adder which
adds 4 to the current value of PC
oThe value gets stored back in PC on the next clock edge
Add
4
PC
Read
address Instruction
Instruction
memory
26
Register File
oThere are 32 registers. Hence all the address widths should
be 5 (25 = 32)
oIn our design, it is possible to write to 1 register and read from
2 registers at the same time
oNow we will abstract the register file as below
27
Arithmetic and Logic Unit
oThe ALU takes two operations and does a specific operation
oIt has several digital circuits to do each of this operation
oA Multiplexer chooses which of these circuits output goes as
the output of the ALU
oWe use the table below to set the ALUOp, which decides
which circuits output is the output of the ALU
28
Putting Things Together for R-type Instruction
29
Arithmetic and Logic Unit
oThe ALU takes two operations and does a specific operation
oIt has several digital circuits to do each of this operation
oA Multiplexer chooses which of these circuits output goes as
the output of the ALU
oWe use the table below to set the ALUOp, which decides
which circuits output is the output of the ALU
30
Implementing I-type Instruction
op rs rd address/constant
6 bits 5 bits 5 bits 16 bits
lw $t0, –4($t1)
Load the data in the memory address
$t1+(-4) into the register $t0
1000 0100 0100 1111 1111 1111 1100
11 1 0
sw $a0, 16($t0)
Store the data in the register $a0 in the
memory $t0+16
31
1010 0100 0010 0000 0000 0001 0000
Implementing I-type Instruction
oFirst issue we find with the existing design is the rd register
encoding position is different for R-type and I-type instruction
oSo we need a multiplexer which chooses what goes as the
register write address to the register file
oIf it is R-type, bits [15:11] should go as the write address and
if it is I-type bits [20:16] should go as the write address
32
Implementing I-type Instruction
33
Implementing I-type Instruction
oFor sw instruction, some data has to be stored in the memory
(data memory)
oThe data to be stored is coming from the register indicated by
rd field in the instruction
oThe address where it should be stored is provided by the ALU
by adding rs with the immediate data (address field/constant
field)
34
Implementing I-type Instruction
35
Implementing I-type Instruction
36
Implementing I-type Instruction
37
Implementing I-type Instruction
38
Implementing I-type Instruction
39
Going further
oImplementation of J-type instruction and the design of control
logic is beyond the scope of this course
oThose who are interested in it, please take CompArch
40
Complete Processor
41
Processor Performance
oWe can express the processor performance as number of
instructions per second (One expansion for MIPS is millions of
instructions per second but it has nothing to do with the name
of the MIPS processor)
oThe processor that we discussed processes one instruction per
clock cycle
oBecause the programme counter can be incremented only on
clock edges (otherwise there is a combinational loop) and
register values can be stored only in clock edges
42
Limitations of Single Cycle Processor
oAlthough MIPS supports one instruction/clock, it is very
inefficient
oThe clock frequency is decided by the critical path (most
probably the load instruction path)
oEarly processors used to be single cycle, but with the
introduction of floating-point operations, it is almost
impossible
43
Pipelining
oPipelining is an implementation technique in which multiple
instructions are overlapped in execution
oIt helps break large combinational circuits into smaller ones,
which improves the clock frequency
oIn ideal scenario using pipelining we can still execute one
instruction/clock cycle
oThe penalty paid is the additional chip area
44
Pipelining Example
oAnn, Brian, Cathy, Dave each have
one load of clothes to wash, dry, A B C D
and fold
oWasher takes 30 minutes
oDryer takes 40 minutes
o“Folder” takes 20 minutes
45
Pipelining Example
6 PM 7 8 9 10 11 Midnight
Time
30 40 20 30 40 20 30 40 20 30 40 20
T
a A
s
k
B
O
r
d C
e
r
D
Sequential laundry takes 6 hours for 4 loads 46
Pipelining Example
6 PM 7 8 9 10 11 Midnight
Time
30 40 40 40 40 20
T
a A
s
k
B
O
r
d C
e
r
D
Pipelined laundry takes 3.5 hours for 4 loads 47
Pipelining Lessons
o Pipelining doesn’t help to reduce latency of single task, it
helps throughput of entire workload
o Pipeline rate is limited by slowest pipeline stage
o Multiple tasks operating simultaneously using different
resources
oPotential speedup = Number pipeline stages
oUnbalanced lengths of pipeline stages reduces speedup
oTime to “fill” pipeline and time to “drain” it reduces speedup
oStall for Dependencies
48
MIPS Pipelining
o MIPS instructions classically take five steps
1. Fetch instruction from memory.
2. Read registers while decoding the instruction. The
regular format of MIPS instructions allows reading and
decoding to occur simultaneously
3. Execute the operation or calculate an address.
4. Access an operand in data memory.
5. Write the result into a register
49
MIPS Pipelining
o MIPS instructions classically take five steps
1. Fetch instruction from memory.
2. Read registers while decoding the instruction. The
regular format of MIPS instructions allows reading and
decoding to occur simultaneously
3. Execute the operation or calculate an address.
4. Access an operand in data memory.
5. Write the result into a register
50
MIPS Pipelining
0
M
u
x
1
P
C Add
Add
Shift MemWrite
4 MemToReg
left 2
RegWrite
Read Instruction Read Read
I [25 - 21] 1
Read Read address data
address [31-0] M
RegDst register 1 data 1 ALU
I [20 - 16] Write u
Read Zero
Instruction 0 address x
memory 0 register 2 Read Result
data 2 M Data 0
Write Write
M u memory
u register data
x
I [15 - 11] x Write Register File ALUOp
1
1 data
ALUSrc
I [15 - 0] Sign 51
extend
MIPS Pipelining
52
MIPS Pipelining
53
MIPS Pipelining
54
55