Instruction Set Architectures (ISAs) Flashcards
What is stored program computers?
Instructions are represented in binary, just like data
Instructions are stored in memory
Programs can operate on programs (such as compilers and linkers)
We make sure that applications are binary compatible to allow compiled programs to work on different computers (Compile on one machine and run on another) - this is also a key argument for standardizing ISAs
What is a instruction set?
The set of instructions a computer can execute.
Different computers have different instruction sets, but often have many in common
How is the RISC-V ISA instruction setup?
A fixed small number of instruction types
Each instruction have an opcode in the same location
format is regular across instruction types - different parts of the instruction (register bits (rd), funct bits) are in the same place for many of the instruction types.
What is a motivation for having simple instruction sets?
Compilers work better on simple instructions, as they are easier to map to applications than complex instructions
How does ISA design use the principle of “common case”
First figure out what the common case is.
Then make sure that the common case is well expressed with the ISA.
Make sure there are ways to express less common cases as well
What are the 4 types of ISAs?
Stack
Accumulator
Register (register-memory)
Register (load-store)
Every type can execute the same task, for example an add operation, but they will do this using different instructions.
What is the most common type of ISA since the 80s?
load-and-store (register)
What are some advantages with load-and-store ISAs?
Accessing registers is much faster than accessing memory.
They allow to seperate computation from memory (using register) which increase efficiency.
Using registers also decrease the amount of dependencies you have. Compared to the stack-type you would be dependent on the stack, which is in memory. And in the accumulator type you would need to serialize access to the accumulator.
What are a trade off with having a lot of registers availble?
The instruction needs to be longer because you need more bits to represent the address of the registers.
What is an advantage with having more registers?
More registers make compiler register allocation more effecient.
Name some ISAs that uses the load-store architecture?
ARM, MIPS, PowerPC, SPARC, RISC-v
Maximum number of operands for these are 3, and they allow no memory addresses (non of the operands can be memory addresses)
Name some ISAs that uses the register-memory architecture
IBM 360/370, Intel 80x86, Motorola 68000
These architectures allows for 2 operands and to apply 1 memory addresses
Name some ISAs using the memory-memory architecture
VAX has to formats of the architecture.
One allows for 2 operands where 2 can be memory addresses.
The other version allows for 3 operands where 3 can be memory addresses
What are some advantages with the register-register ISA architecture?
Simple
fixed length instruction encoding
Easy to generate code
Instructions take a similar number of clock cycles to execute
What are some disadvantages with the register-register ISA architecture?
Higher instruction count than architectures with memory references in instructions, because of book-keeping in regards to handling memory.
Bigger programs (instruction count + low instruction density), this can affect I-cache.
What are some advantages with the register-memory ISA architecture?
Can access data without loading it first.
Instruction format is easy to encode and give better instruction density.
What are some disadvantages with the register-memory ISA architecture?
When the architecture only allows for two operands, one of these can be overwritten during binary operations.
Memory addresses must be encoded in instruction formats, which reduces the number of bits that are available for registers.
Clock cycles per instruction varies based on where the operand is located.
What are some advantages with the memory-memory ISA architecture?
Most compact, both in terms of instruction space and register use.
Doesn’t waste registers for temporaries.
What are some dis-advantages with the memory-memory ISA architecture?
Large variation in instruction size, especially for three-operand instructions.
Large variation in work per instruction - memory access creates bottle necks
What operations does an ISA need to be able to perform?
Arithmetic
Data transfer
Control
System
Floating point
Decimal
String
Graphics
What does arithmetic instructions do?
Integer arithmetic and logal operations (add, subtract, or, and)
What does data transfer instructions do?
Load-store, move instructions (on computers with memory addressing)
What does control instructions do?
branch, jump, call and return, traps
What does System instructions do?
Operating system calls, managing virtual memory
What does floating point instructions do?
floating point operations, add, multiply, divide
What does decimal instructions do?
decimal add, decimal divide, decimal-to-character conversion
What does string instructions do?
String move, compare, search
What does graphics instructions do?
Pixel/vertex operations, compression/decompression
What operations are most common
Load
conditional branch
compare
store
add
The 10 most used instructions stand for 96% of all instructions used. This is a good example of why it is beneficial and important to design after the common case and make the common case fast
How is operand type defined
Defined from the opcode of the instruction.
How is the size of the operand determined
Determined by the operation itself.
E.g. when doing integer arithmetic, operands are either 32- or 64 bits.
floating point are the floating point standard - single or double precision.
What are the two ways of interpreting memory?
Big- and little endian. These tells how bits are ordered within a word.
Define big endian notation
MSB has the lowest address
define little endian notation
LSB stored at lowest memory address
What two things do we need to know when accessing memory
Endianess and alignment
What is alignment in regards to memory?
Alignment deals with how memory is accessed.
An address A of an object stored in memory with size s, is aligned if A mod s == 0.
Alignment ensures that you don’t access parts of different objects and putting them together.
Access is aligned if address is a multiple of the size of the object being accessed.
Example: If an object is 2 bytes. Address 0, 2, 4 are aligned addresses. Address 1, 3 would misaligned as A mod 0 != 0.
Many computers expect accesses larger than a byte to be aligned since this simplifies the implementation.
What is PC-relative addressing?
Displacement addressing, but the register is always the PC
What are the 11 addressing modes?
Register
Immediate
Displacement
Register indirect
Indexed
Direct or absolute
Memory indirect
Autoincrement
Autodecrement
Scaled
PC-relative
What is register addressing mode?
Simply use the name of the register and access the value in it.
used when a value is in a register
Add r4, r3
What is immediate addressing mode?
provide a constant as part of the instruction
used for handling constants
Add r4, #3
What is displacement addressing mode?
Displacement both provides an immediate value and a register value.
Adds the immediate to the register value, and retrieves this memory address.
Add r4, 100[r4]
(ldr r5, [r4, #3]) - maybe
useful for example when accessing the stack. Here you would access memory relative to the stack pointer, and these offsets would be constants.
What is register indirect addressing mode?
When you use a register as a pointer.
Get a register value and use that to access memory. Register contain address, use this address to fetch memory value.
Add r4, [r1]
What is indexed addressing mode?
Have two registers, the base register and the offset register.
Add the value of these registers together and fetch memory from the resulting address.
add r3, [r1 + r2]
What is direct or absolute addressing mode?
Provided constant is used as pointer (memory address).
Add r4, [ox1001]
What is memory indirect addressing mode?
The value in the register is used to access memory, and this memory-value is used to access memory.
So memory value is used to access memory
mem[mem[r2]]
What is autoincrement addressing mode?
Uses value in register to access memory.
After accessing, the value in the register is incremented.
Useful when accessing arrays for incrementing address by an element.
Add r1, [r2]+
What is autodecrement addressing mode?
Uses value in register to access memory.
After accessing, the value in the register is decremented.
Useful when accessing arrays for incrementing address by an element.
Add r1, -[r2]
What is scaled addressing mode?
Add values in register together, and add a scaling factor. Use this to access memory
add r1, 100[r2][r3]
Mem[100 + Reg[r1] + Reg[r2]*d]
What is advantage of using more addressing modes?
Reduces the instruction count
What is a disadvantage with using more addressing modes?
Complicates the CPU significantly. Maybe even to the point where avarage cycle per instruction increases.
How can 32-bit constants be handled using the lui instruction (load upper immediate)
for a 32 bit immediate, you could copy the 20 most significant bits to the left bits of the register.
then you OR with an 12 immediate to get the lower 12 bits.
What 3 addressing modes should a new ISA support?
Immediate, displacement and register indirect
these capture 75-99% of addressing modes used (again, common case)
How big should displacement addressing be to cover the common case
Displacement address should be 12 to 16 bits
How big should immediate fields be to cover the common case?
8 to 16 bits
What instruction is used to support 32 bit immediates
lui (load-upper-immediate)
What are basic blocks when talking about control flow
Sequence of instructions without any embedded branches (exceps at the end)
No branch targets (except at the beginning)
Name 4 types of control flow
Conditional branches
Jumps (unconditional branches)
Procedure calls
Procedure returns
What are the two ways of specifying a branch address?
Explicitly: Commonly offset to PC (PC-relative)
Implicitly: Use register to specify address
What does it mean to explicitly specify a branch address?
Include an offset to the program counter (PC relative addressing)
Advantage: Branching happens independently of where program was loaded in memory
Disadvantage: Branch needs to be relative close to PC
What are some advantages of explicitly specifying branch addresses
Most branches are short - i.e. a loop, meaning branch target is close.
Get position independence.
The branch is independent on where the branch was loaded into memory
What is implicit specification of branch addressing?
Used when branch target is not known at compile time.
Load a memory address into a register. Use instructions to specify that we will interpret this register as an address to do some code.
useful for switch statements and virtual functions, function pointers or dynamically shared libraries.
How long is most branching?
Usually within 10 bits
How can you branch to a location the is too far to encode with a 13-bit signed offset?
Can use the lui instruction
Take the lui instruction to store the 20 most significant bits in a register
then use jalr instruction (jump and link register) with an immediate with the remaining 12 bits which adds these bits to the bits in the register used in jalr, which is the register where we stored the 20 most significant bits
lui x1, <20 MSB>
jalr x1, x1, <12 LSB>
You can also jump PC-relative with a 32 bit offset:
auipc (loads 20 MSB)
jalr (load 12 LSB)
the difference when using auipc is that the 20-bit operand is not a constant but an offset (from PC)
What are the three ways of specifying a branch target
Condition Code (CC)
Condition register/limited comparison
Compare and branch
Define how condition code is used to specifying a branch target
All ALU operations sets some special bits.
Use these bits when branching.
Advantage: sometimes condition is set for free
Disadvantage: CC is extra state. Constrain the ordering of instructions because they pass information from one instruction to another. create a dependency that is not easily identifiable
Define how condition register is used to specifying a branch target
Test an arbitrary register with result of comparison (EQ, Zero, …)
Advantage: simple
Disadvantage: Limited compare may affect critical path or require extra comparison for general condition.
Define how compare and branch is used to specifying a branch target
Compare is part of branch, fairly general compares are allowed (GT, LT, EQ)
Advantage: Branch and compare in one instruction instead of two
Disadvantage: May end up creating a critical path for instructions.
What is a procedure call?
Unconditional jump.
Register state needs to be saved before entering the callee
What is the caller/callee convention
Tells what state needs to be saved by the caller and the callee respectively.
Saving is done by using the stack-
What are temporaries when talking about registers
Registers that do not need to be saved in regards to caller-callee conventions
What is the memory layout for a general program
Stack: grows downwards
heap: dynamic data
static data: global variables. known at compile time
text: program
reserved
When using the stack, what order do you store which data
Saved argument registers (if any)
return address
saved saved registers: restored before return
Local arrays and structures
When designing an ISA what components should the ISA consist of and support
Lean towards load-store architecture
Support displacement, immediate and register indirect addressing modes
Support 8, 16, 32 and 64-bit integers, and 32- and 64-bit floating.
Instructions for simple ops (arithmetic, load, store, …), PC-relative conditionals, Jump and link instructions for procedure calls, register indirect jumps for procedure returns
What is an opcode
Specifies the operation to be done.
What are some things we need to think about when encoding ISAs?
Must include opcode to specify instruction
Need to balance:
- desire to have many registers and addressing modes
- Lower average program/complexity favors fewer registers and fewer different modes
- instructions should be easy to decode
Need to decide if we want a fixed or variable instruction size
Compare fixed vs. variable instruction sizes
Fixed are easier to decode but allows for less registers and addressing modes. can hurt program size.
Variable size allows you to do whatever you’d like and is very flexible, but tends to become complex.
Mixed instruction set types are used to include both and handle the disadvantages
What are the components of a compiler
Front end per language: transform languages into intermediate form
High-level optimizations: largely machine independent
Global optimizer: lower level optimizations, less and less language dependent - more machine dependent (register allocation)
Code generator: independent on language but very dependent on machine
How can architects help compiler writers?
Provide regularity: Ideally an ISA should be independent - all instructions support all addressing modes
Provide primitives, not sollutions: complicated instructions tend to not be used, very specific to how program is written
Simplify trade offs between alternatives: make it easy for the writer to understand the trade-offs to find the best instruction sequence in a given case.
Provide instructions that bind quantities known at compile time as constants: avoid recomputing things that are already known
Describe the components of the RISC-V ISA
General purpose register model and load-store architecture
displacement, immediate and register indirect addressing with appropriate displacement
8, 16, 32, 64 int, and 32, 64 float
focus on simple dominating instructions load, store, add, subtract, move register-register and shift
branching and compare according to analysis of sufficiencies in modern computers
at least 16 (preferably 32) registers, orthogonal, minimalist ISA
What does it mean that RISC-V have multiple dialects
It’s a hybrid instruction set.
Different variants: 64 bit, embedded, 32 bit, atomic instructions, …
benefit of having multiple extension is that having a base instruction set + extension means that you do not need to implement all extensions every time.
What are the 4 types of instructions in RISC-V
R-type: register-register instructions, ALU
I-type: loads and ALU operations on immediates
S-type: store, compare, branch
U-type: jump and link, jump and link register
what is the rd register in RISC-V
destination register
For the different instruction types, this register is mostly in the same place (R, I, U), if not in same place - it is not in the instruction
What is the rs1 and rs2 registers in RISC-V
Source registers, also in the same place for the instructions. If it is not, the instruction type does not have this register
What are the data transfer instructions in RISC-V
load and stores, move data between memory and registers, or between integer and FP
l: load
b: byte
u: unsigned
s:store
Use combination of these to get different opcodes
Name some of the ALU instructions of RISC-V
Arithmetic, shifts, binary logic, remainder
How does the stack architecture work?
(Don’t use any explicit memory addresses)
Push operands on stack
Do operations on values in stack
Result is stored on stack
Pop result from stack
How does the accumulator architecture work?
Have one accumulator where an operand can be stored
Operations are done on the value in the accumulator, and one additional operand
Store result in memory
How does register-memory architectures work?
Can use both memory-addresses (vaules stored in memory) and registers.
One operand can be loaded into a register.
Then an operation can be done on the register value and an directly on an operand that is stored in memory (not loaded)
Store result in register
store register value in memory.
How does load-store architectures work?
Load both operands to seperate registers.
Do operation and store result in new register
Store result from register in to memory
