Computer Architecture ELEC3441
Instruction Set Architecture (1) 2nd Semester, 2020-21
Dr. Hayden Kwok-Hay So
Department of Electrical and Electronic Engineering
Review: ISA
n Instruction set architecture defines the user observable behavior a processor
• Acontractbetweenhardwareandsoftware
n Usually includes:
• Observablestateofaprocessor
• Asetofmachineinstructions
• Semanticsoftheinstructionandprocessor execution
HKU EEE ELEC3441 – HS 2
Computer Architecture: HW/SW Interface
Applications
Compiler
Assembler
Operating System
Instruction Set Architecture
Microarchitecture Processor Memory I/O
Digital Design
Circuit Design
Transistors
HKU EEE ELEC3441 – HS 3
Review: Compiling Applications
Applications foo.c (C/C++/Java)
ISA
Assembly Code
Assembler
Machine Instructions
foo.s
foo.exe
HKU EEE ELEC3441 – HS
4
Compiler
Hardware Software
Note about learning an ISA
n By learning how ONE ISA is designed, you learn how various architectural tradeoffs are performed.
n NOT to memorize details of a single ISA
n The subset of RISC-V covered in class is very similar to MIPS:
• MoreexamplesinCOD
• WilluseMIPSsoftwareforsimulationinsome
cases
HKU EEE ELEC3441 – HS 5
Version 2.0
HKU EEE ELEC3441 – HS 6
RISC-V ISA
n New RISC design from UC Berkeley
n Realistic & complete ISA, but open & small
n Not over-architected for a certain implementation style
n 32-bit and 64-bit address space variants • RV32 and RV64
n Designed to be extensible
• High-performance multiprocessing
• Efficient instruction encoding for embedded system • etc
n Easy to subset/extend for education/research n Complete compilation toolchain
n FPGA and ASIC designs
HKU EEE ELEC3441 – HS 7
RISC-V Foundation
http://www.riscv.org
HKU EEE ELEC3441 – HS 8
RISC-V ISA 2.0
n A revised version to the original definition
n Divides into an integer base ISA + extension
• Floating point, etc
n Revised instruction coding
• Make hardware design easier n Added 128-bit support
n Much more…
n We will be using RISC-V ISA 2.0 this semester:
• Things may break
• RISC-V base integer ISA is similar to MIPS in textbook
• Will try cross reference between RISCV and MIPS
HKU EEE ELEC3441 – HS 9
RISC-V ISA Overview
n The riscv processor has a load-store architecture
• Mostinstructionsoperateonvaluesdirectlytoand from the register file
• Dedicatedload/storeinstructionstotransfer data between register file and main memory
n RV32 has a 32-bit word length
• Fixedinstructionlengthof32bits
• Adatawordis32bitswide
• RISCV-VISAdesignedtoallowvariablelength instruction code and instruction extension
• Not covered in this course
HKU EEE ELEC3441 – HS 10
RV32 Processor State – Base Integer Design
n Register file with 32 32-bit general- purpose registers
n Labeled x0 – x31
• x0 always contains the value 0
n Application Binary Interface (ABI) names used in assembler
• t0 – t6 for temp variables
• s0 – s11 for saved variables, etc
n Additional Program Counter (PC) register
• Contains the memory address of the current executing instruction
Register
ABI Name
x0
zero
x1
ra
x2
sp
x3
gp
x4
tp
x5-7
t0-2
x8
s0/fp
x9
s1
x10-17
a0-7
x18-27
s2-11
x28-31
t3-6
https://blog.riscv.org/2015/01/announcing-the-risc-v-gcc-4-9-port-and-new-abi/
HKU EEE ELEC3441 – HS 11
XLEN=32 in RV32
Integer Register-Register Operations
n Basic arithmetic and bit operations:
• Arithmetic:ADD,SUB
• BitOperations:AND,OR,XOR,SLL,SRL,SRA • Comparison:SLT,SLTU
n Take two source register inputs (denoted rs1, rs2) and produce one destination register output (denoted rd).
HKU EEE ELEC3441 – HS 12
ADD/SUB
Assembler
Semantics
ADD rd, rs1, rs2
rdßrs1 + rs2
SUB rd, rs1, rs2
rdßrs1 – rs2
n 3 operands:
• 2sourcesand1destination
n Add/sub the values of the 2 source registers (rs1, rs2) and store the result in destination register (rd)
n Discard overflow
n Lower 32 bits are written
HKU EEE ELEC3441 – HS 13
ADD/SUB Example
n C code:
y = (e + f) – (g + h);
n Assume e, f, g, h, y stored in a0, a1, a2, a3,
a4 respectively. n RISCV code:
ADD t0, a0, a1
ADD t1, a2, a3
SUB a4, t0, t1
HKU EEE
ELEC3441 – HS 14
Bit Operations
n Similar semantics to ADD/SUB instructions n Bit operations useful for masking values
Assembler
Semantics
AND rd, rs1, rs2
rd ß rs1 AND rs2
OR rd, rs1, rs2
rdßrs1 OR rs2
XOR rd, rs1, rs2
rdßrs1 XOR rs2
n E.g.:
# t0ß0xABCD0123
# t1ß0x000F0000
AND t2, t0, t1
# t2 contains 0x000D0000
HKU EEE
ELEC3441 – HS 15
Quick Quiz
# t0ß0x00C00005 # t1ß0xFFFFFFFF XOR t2, t0, t1
What is the value stored in t2?
HKU EEE ELEC3441 – HS 16
RISC-V Instruction Encoding
n Each supported instruction in the ISA must be uniquely encoded to describe its function
n Any unique encoding works, but good encoding may optimize:
• Regularity
• Simple hardware decode
• Instruction length
• Extensibility
n In RV32,
• Each instruction is 32-bit wide
• Favors hardware regularity over human readability
• 6 general types of instructions
• R-type, I-type, S-type, SB-type, U-type, UJ-type
HKU EEE ELEC3441 – HS 17
R-type Instruction Encoding
n So far, all the simple integer register-register operations are encoded as R-type instructions
31
25 24 20 19 15 14 12 11 7 6
755357
0
funct7
rs2
rs1
funct3
rd
opcode
0000000 src2 src1 0000000 src2 src1 0000000 src2 src1 0100000 src2 src1
ADD/SLT/SLTU dest OP AND/OR/XOR dest OP SLL/SRL dest OP SUB/SRA dest OP
n Instructions within the same type shares similar encoding
n Differentiate only by the funct3 and funct7 fields
HKU EEE ELEC3441 – HS
18
R-Type format
Quick Quiz
n If the size of register file is increased to include 64 registers, how many bits are needed to encode rs1?
n How would the above change affect the number of instructions representable?
HKU EEE ELEC3441 – HS 19
Immediate Operations
n Very often programs need to operate on (small) numerical constants in the code
• e.g.:“a=b+3”
n RV32 includes register-immediate instructions for
these cases
n Small constant embedded within the instruction.
• Arithmetic: ADDI
• Bit Operations: ANDI, ORI, XORI
• Comparison: SLTI, SLTIU
n Take one source register inputs (rs1) and produce one destination register output (rd).
HKU EEE ELEC3441 – HS 20
I-type Instruction Encoding
n Most register-immediate operations are encoded using the I-type format
31 20 19 15 14 12 11 7 6
12 5 3 5 7 I-immediate[11:0] src ADDI/SLTI[U] dest OP-IMM I-immediate[11:0] src ANDI/ORI/XORI dest OP-IMM
n NOTE: since the constant is encoded within the instruction, size of immediate must be < 32 bits
n In RV32, I-type instruction, immediate constants are encoded using 12 bits
n Note that bit locations of rs1, funct3, rd and opcode are the same as in R-type
• Simplicityèhigh performance HKU EEE ELEC3441 - HS
0
I-Type format
imm[11:0]
rs1
funct3
rd
opcode
21
ADDI Example
n C code:
y=y+e+1
n Assume e, y stored in a0, a1 respectively. n RISCV code:
ADD t0, a1, a0
ADDI a1, t0, 1
Why is there no SUBI instruction... ?
HKU EEE ELEC3441 - HS 22
Unsigned Numbers
n Represent non-negative binary numbers (0, 1, 2, 3, ...) using their natural binary representations
n An n-bit bitstring can represent numbers in
"n$ #0,2 −1%
n Represents equally spaced integers on the number line
012345678∞
HKU EEE ELEC3441 - HS 23
Value
0
1
2
3
4
5
6
7
8
9
10
11
Binary
0
1
10
11
100
101
110
111
1000
1001
1010
1011
Bitstring (8- bit)
00000000
00000001
00000010
00000011
00000100
00000101
00000110
00000111
00001000
00001001
00001010
00001011
Two’s Complement (1)
n Negative numbers are represented by the 2’s complement of the absolute value of that number
• 2’scomplementofann-bitnumbervisthevalue 2n - v
n For example, to represent value -3 using a 4- bit bitstring:
• 3®“0011”
• 24 -3=16-3=13 • \-3®“1101”
HKU EEE ELEC3441 - HS 24
00000000 00000001
00000010 00000011
00000100 00000101
00000110 00000111
Two’s complement (2)
n 2’s complement of a number can be obtained by “adding 1 to the 1’s complement of the number”
Original
23
00010111
1’s complement
11101000
2’s complement
-23
11101001
n The value of a bitstring {bn−1bn−2b0} complement can be calculated as:
n−2 −2n−1 +∑2ibi
i=0
n Range:
• Note that is asymmetric
HKU EEE ELEC3441 - HS
in 2’s
[−2n−1 ,2n−1 −1]
25
Quick Quiz
n What is the binary representation of 13? 11012
n What is the binary representation of -13?
0010
0011
Cannot be represented
Cannot be determined based on given information
HKU EEE ELEC3441 - HS 26
1
2
3
4
Quick Quiz
n What are the binary representations of 13 and -13 as 8-bit integers?
13: 00001101 -13: 00000011
13: 00001101 -13: 11110011
n What are the binary representations of 13 and -13 as 12-bit integers?
13: 000000001101 -13: 000011110011 13: 000000001101 -13: 111111110011
1
2
1
2
HKU EEE ELEC3441 - HS 27
Sign Extension
n The sign of an integer can only be known with the width of integer specified
n In 2’s complement representations, the most significant bit (MSB) of an integer denotes its sign:
• MSB=1 è negative
• MSB=0 è non-negative
n To cast an integer value to a representation with more bits, it must be sign-extended to preserve its sign:
• If it is negative number, fill the additional bits with 1
• If it is non-negative, fill the additional bits with 0
HKU EEE ELEC3441 - HS 28
ADDI with negative numbers
31 20 19 15 14 12 11 7 6
12 5 3 5 7 I-immediate[11:0] src ADDI/SLTI[U] dest OP-IMM I-immediate[11:0] src ANDI/ORI/XORI dest OP-IMM
n Subtraction with immediate values can be achieved by using negative immediate with ADDI
n Recall that immediate constants are 12 bits long in all I-type instructions
• Range: [-211, 211-1]
n In general, instructions must clearly specify in its semantics if it is treating the value as signed or unsigned numbers
• E.g. SLTI vs SLTIU
HKU EEE ELEC3441 - HS
0
imm[11:0]
rs1
funct3
rd
opcode
29
Load Upper Immediate
U-Type format
n Load upper bits of immediate constant
n Form constants of any values in combination
with ADDI, etc
n No need for sign extension
n NOTE: opcode and rd in the same location as most other instructions
HKU EEE ELEC3441 - HS 30
Memory Operations
n All program data + instruction originally stored in main memory
• Array,structure,userdata,string,etc
n Dedicated instruction to load/store data
between register file and main memory
n NOTE: registers are much faster than main memory
• Limitedregistersavailability(32registersvs.4GB of memory)
• Compilermustuseregisterswiselyforbest performance
HKU EEE ELEC3441 - HS 31
RV32 Memory Model
n Memory is byte-addressable
• Eachaddresscorrespondsto1byteofdata
n Native data types:
• Word:32bit(int)
• Half-word:16bit(short) • Byte:8bit(char)
n RV32 has a Little-Endian byte addressing scheme
• Theleastsignificantbyteisatthelowestaddress
HKU EEE ELEC3441 - HS 32
Endianness
int A[20]
A[0]=0xABCD0123
A[1]=0xFACECAFE
Big Little Endian Endian
FE
CA
CE
FA
23
01
CD
AB
FA
CE
CA
FE
AB
CD
01
23
HKU EEE
0x000A0007 0x000A0006 0x000A0005 0x000A0004 0x000A0003 0x000A0002 0x000A0001 0x000A0000
ELEC3441 - HS
33
Word Alignment
n Words are naturally aligned at 4-byte boundary
n Half-words naturally aligned at 2-byte boundary
n RV32I allows non- aligned access
• Not common in most processors
• See ISA spec
HKU EEE
0x000A0007 0x000A0006 0x000A0005 0x000A0004 0x000A0003 0x000A0002 0x000A0001 0x000A0000
ELEC3441 - HS 34
AB
CD
01
23
AB
CD
01
23
AB
CD
01
23
imm[11:0]
rs1
f3
rd
opcode
I
S
Memory Operations
offset[11:0] base width dest LOAD
imm[11:5]
rs2
rs1
f3
imm[4:0]
opcode
offset[11:5] src base width offset[4:0] STORE
n Immediate is sign extended n LW/SW – Word
n LH/SH – Half Word
n LB/SB – Byte
HKU EEE ELEC3441 - HS 35
Load:
(dest)ßM[(base) + offset]
Store:
M[(base) + offset]ß(src)
Memory Operations – Load
int y = e + f[3];
n Assume e, f, y stored in a0, a1, a2 respectively.
n RISCV code:
lw t0,12(a1) #12=3x4
ADD a2, a0, t0
n LW, LH, LB instructions load word, half-word and byte from memory
HKU EEE ELEC3441 - HS 36
Memory Operations – Store
int f[7] = f[6] + f[5];
n Assume f is stored in a0. n RISCV code:
lw t0,20(a0) #20=5x4 lw t1, 24(a0)
ADD t0, t0, t1
sw t0, 28(a0)
n SW, SH, SB instructions store word, half- word and byte to memory
HKU EEE ELEC3441 - HS 37
31
31
20 19 15 14 12 11 7 6 0
12 5 3 5 7
Load/Store Instruction Encoding
imm[11:0]
rs1
funct3
rd
opcode
offset[11:0] base
25 24 20 19
width
dest LOAD
7 6 0
15 14
12 11
imm[11:5]
rs2
rs1
funct3
imm[4:0]
opcode
755357 offset[11:5] src base width offset[4:0] STORE
n LOAD instructions are encoded as I-type
n STORE instructions are encoded as S-type
n funct3 encodes the length (W, H, B)
n 12-bit offset is sign extended and added to base address in rs1
n Note the bit location of imm[11:5] and imm[4:0] in S-type
HKU EEE ELEC3441 - HS 38
Branch Operations
n Normally programs execute sequentially
• Thenextinstructiontofetchisnormallyatlocation
PC + 4 (32 bit)
n Decision making constructs requires fetching instruction from run-time determined location
• if-the-else,do...while,goto,switch,etc
n RISCV has two types of control transfer instructions:
• Unconditionaljump • Conditionalbranch
HKU EEE ELEC3441 - HS 39
Motivation: Unconditional Jump
n Just like GOTO
n RISC-V Assembler supports unconditional jump
0xA000 addi a0, zero, 9
0xA004 JUMP aLabel
0xA008 ori a0, a0, 27
.
.
aLabel: 0xBC08 subi a0, a0, 18
0xBC0C and a1, a1, a0
0xBC10 <. . .>
label
HKU EEE ELEC3441 – HS
40
Motivation: Conditional Branch
n Just like If-Then
n Jump only if the branch condition is true
0xA000 addi a0, zero, 9
0xA004 BEQ a0, a1, aLabel
0xA008 ori a0, a0, 27
.
.
aLabel: 0xBC08 subi a0, a0, 18
0xBC0C and a1, a1, a0
0xBC10 <. . .>
HKU EEE ELEC3441 – HS
label
41
Branch Offset
Absolute
0xA000 addi a0, zero, 9
0xA004 JUMP [to 0xBC08]
0xA008 ori a0, a0, 27
Relative
0xA000 addi a0, zero, 9
0xA004 JUMP [+701 insts]
0xA008 ori a0, a0, 27
0xBC08 subi a0, a0, 18
0xBC0C and a1, a1, a0
0xBC10 <. . .>
0xBC08 subi a0, a0, 18
0xBC0C and a1, a1, a0
0xBC10 <. . .>
.. ..
n Most processors use relative jump (with jump offsets)
n Portable code
n Easier to encode (no need to store 32 bits)
HKU EEE ELEC3441 – HS 42
Conditional Branches
31 30 2524 2019 1514 1211 8 7 6
16553417
0
imm[12]
imm[10:5]
rs2
rs1
funct3
imm[4:1]
imm[11]
opcode
offset[12,10:5] offset[12,10:5] offset[12,10:5]
src2 src1 src2 src1 src2 src1
BEQ/BNE BLT[U] BGE[U]
offset[11,4:1] offset[11,4:1] offset[11,4:1]
BRANCH BRANCH BRANCH
n 12-bit branch immediate encoded as signed offset in multiples of 2
• E.g. offset[12:1] = 0x00C è jumps to PC + 12*2 = PC + 24
Assembler
Semantics
BEQ rs1, rs2, dest
if rs1=rs2 then branch dest
BNE rs1, rs2, dest
If rs1≠rs2 then branch dest
BLT rs1, rs2, dest
If rs1
0xBC08 <. . .>
0xBC0C <. . .>
0xBC10 return
HKU EEE
ELEC3441 – HS 45
31
Unconditional JALR
20 19 15 14 12 11 7 6 0
12 5 3 5 7 offset[11:0] base 0 dest JALR
n Similar to JAL, except destination is relative to the value of rs1
n Semantics:
• Unconditionaljumptooffset+(rs1) • Storereturnaddress(PC+4)inrd
n Note
• theoffsetisnotoffsetbymultipleof2
• EntirelysameasanI-typeformatinstruction
HKU EEE ELEC3441 – HS 46
I-Type format
imm[11:0]
rs1
funct3
rd
opcode
JAL + JALR for function calls
0xA000 addi a0, zero, 9
0xA004 jal ra, 0x1C00
0xA008 addi a0, a0, 27
.
.
0xBC04 <. . .>
0xBC08 <. . .>
0xBC0C <. . .>
0xBC10 jalr zero, ra
HKU EEE
ELEC3441 – HS 47
If-Then-Else Conversion
if (a >= b) { c=a–b
} else { c=a+b
}
blt a1, a0, truepart
add a2, a1, a0
j exit
truepart: sub a2, a1, a0
exit : <...>
HKU EEE
ELEC3441 – HS 48
Summary
n RISC-V ISA is a new academic RISC ISA used as examples
• RV32formsthebasesetofarchitecturalfeature • 32-bitarchitecture
• 32GeneralPurposeRegisterFile
n Each instruction in an ISA must be uniquely encoded.
• EncodingandsemanticsofISAmusttradeoff between hardware efficiency and usability.
HKU EEE ELEC3441 – HS 49
SI Prefix
Prefix
exa
peta
tera
giga
mega
kilo
milli
micro
nano
pico
Symbol (base 10)
E
P
T
G
M
k
m
μ
n
p
Power (base 10)
18
15
12
9
6
3
-3
-6
-9
-12
Symbol (base 2)
Ei
Pi
Ti
Gi
Mi
Ki
Power (base 2)
60
50
40
30
20
10
n Binary prefix more important as order-of- magnitude increases:
• 1000 ó 1024
• 1,000,000,000 ó 1,073,741,824
HKU EEE ELEC3441 – HS 50