1What two things must a computer instruction encode?
The operation (opcode) and the operands
2What are the typical fields of a three-operand ALU instruction?
Opcode, options/data type, src1, src2 and dst
3What does the opcode encode?
The operation to perform, e.g. add, subtract, multiply
4How many bits is an opcode field typically?
3 or 4 bits
5What does the data type field of an instruction specify?
The operand type, e.g. int, unsigned, long, float, double
6What might the options field of an instruction specify?
Whether to set the ALU flags
7What do the operand fields of an instruction encode?
Registers or constants
8What is a register file?
The collection of general purpose registers
9How many operands does a binary ALU instruction need?
Three: two sources and one destination
10How many operands does a unary ALU instruction need?
Two: one source and one destination
11Which of these are unary ALU operations?
12Which of these are binary ALU operations?
13Give an example of an instruction with no operands
NOP (no operation)
14Why are there separate shift instructions for signed and unsigned numbers?
Signed right shifts must preserve the sign bit
15In some architectures, which operand is the destination?
The first operand, e.g. ADD R2, R0, R1
16What does the Z flag indicate?
The result was zero
17What does the N flag indicate?
The result was negative
18What does the C flag indicate?
The result had a carry (unsigned overflow)
19What does the V flag indicate?
The result had a signed overflow
20Where are the ALU flags stored?
In the status register (SR, CPSR, PS or PSW)
21What three things can an operand be?
A register, a constant or a memory location
22How many bits encode a register operand for R registers?
$\log_2 R$
23How many bits encode a register operand with 32 registers?
5
24How many bits encode three register operands with 16 registers?
12 (4 bits each)
25How many bits are needed to encode 8 addressing modes?
3
26What is an addressing mode?
A specification of how to interpret an operand
27What is register addressing?
The operand is stored in a register
28What is immediate addressing?
A constant is stored in the instruction
29What is direct addressing?
The memory address is stored in the instruction
30What is the effective address in direct addressing?
The immediate constant
31What is register indirect (deferred) addressing?
The memory address is stored in a register
32Which addressing mode corresponds to the C dereference operator?
Register indirect
33Which memory addressing mode has the shortest encoding?
Register indirect (only the base register number is encoded)
34What is displacement addressing?
Address = base register + small constant
35How many bits does displacement addressing need with D-bit displacement and B base registers?
$D + \log_2 B$
36What is indexed addressing?
Address = base register + index register
37What is indexed addressing useful for?
Indexing into arrays
38How many bits does indexed addressing need with B base and I index registers?
$\log_2 B + \log_2 I$
39What is autoincrement addressing?
Register indirect, with the register incremented or decremented before or after access
40What is the RTL for MOV *R7++, R0?
R0 <- M[R7]; R7 <- R7 + 1
41What is the RTL for MOV *--R7, R0?
R7 <- R7 - 1; R0 <- M[R7]
42What is the RTL for MOV *(R7 + 4), R0?
R0 <- M[R7 + 4]
43Why are autoincrement modes popular with DSPs?
They step through arrays without extra increment instructions
44What special autoincrement feature do DSPs have?
Wrap-around, for circular buffers
45Which processors have many addressing modes: CISC or RISC?
CISC
46Why don't RISC processors support direct memory addressing?
Encoding full addresses doesn't fit in a fixed-length instruction
47How many bits would three direct 32-bit memory operands need?
96 bits
48Why do CISC instructions have variable lengths?
Memory addresses need many more bits than register numbers
49What is the advantage of CISC variable-length instructions?
Few operand restrictions, so they're easy for assembly programmers
50What is the disadvantage of variable-length instructions?
They're harder to fetch, decode and pipeline
51Why do RISC architectures use fixed-length instructions?
They are important for pipelining
52What problem do fixed-length instructions create?
Large constants and addresses don't fit in one instruction
53What are the two strategies for loading large constants on RISC?
Synthesise them with multiple instructions, or load them from a literal pool
54What is constant synthesis?
Building a large constant from smaller immediates using shifts and ORs
55What instruction count does naive 32-bit constant synthesis need?
4 (two immediate loads, a shift and an OR)
56What instruction speeds up constant synthesis on many RISCs?
A load-high instruction like MOVHI
57How does ARM Thumb synthesise 0x1000?
MOV R0, #128 then LSLS R0, R0, #5
58What is a literal pool?
Constants and addresses stored at the end of a function, too big for an instruction
59How are literal pool values accessed?
PC-relative indirect addressing with an offset
60What is the RTL for loading from a literal pool?
R0 <- M[PC + offset]
61What constants can ARM encode directly in an instruction?
Small integers, or 8-bit patterns with an arbitrary shift
62How does ARM read a variable at an arbitrary memory address?
Load its address from the literal pool into a register, then use register indirect
63Why does large constant encoding favour a load/store ISA?
There's little room left in the instruction for other operands
64What were early ISAs designed for?
Making assembly language programming simple
65Which of these are typical CISC features?
- Many data types like BCD and bit fields
- Complex instructions like CRC and polynomial evaluation
- Many addressing modes
- Fixed-length instructions
66What does BCD stand for?
Binary coded decimal
67What is memory indirect addressing?
R0 <- M[M[R1]], i.e. a pointer to a pointer
68What was found about complex CISC instructions?
They were rarely used and made the CPU hard to optimise
69What is the 80/20 observation about instruction sets?
80% of the time only 20% of the instructions are used
70How do rarely used instructions hurt performance?
Supporting them adds complexity that penalises common instructions
71What is the best measure of computer performance?
Time to execute a benchmark suite, e.g. SPEC
72What is the program execution time formula?
$T = \text{IC} \times \text{CPI} \times \frac{1}{\text{Clock Rate}}$
73What does CPI stand for?
Clock cycles per instruction
74What does instruction count depend on?
The ISA and compiler technology
75What does CPI depend on?
The processor organisation and ISA
76What does clock rate depend on?
Hardware technology and processor organisation
77What is the MIPS formula?
$\text{MIPS} = \frac{\text{Clock Rate}}{\text{CPI} \times 10^6}$
78Why is MIPS a misleading performance measure?
It ignores how many instructions are needed to do a task
79Why is watts/MIP a poor estimate of battery life?
Energy per program also depends on instruction count
80What is Amdahl's Rule?
Make the common case fast
81What is the Amdahl's Rule execution time formula?
$T_{new} = T_{old}\left[(1 - U) + \frac{U}{S}\right]$
82What is the Amdahl's Rule overall speedup formula?
$S_{overall} = \frac{1}{(1 - U) + U/S}$
83What is the overall speedup of a 10× enhancement used 50% of the time?
About 1.82
84What is the overall speedup of a 2× enhancement used 90% of the time?
About 1.82
85What is the overall speedup of a 4× enhancement used 60% of the time?
About 1.82
86Feature A: speedup 2, used 20%; B: speedup 5, used 50%. Which is better?
B (1.67 vs 1.11)
87What is microcoding?
Executing each instruction as a sequence of micro-instructions
88What is microcode?
A lower-level machine language
89What are the micro-steps to execute an instruction?
Fetch, decode, read operands, execute, write result, update PC
90What does MAR stand for?
Memory address register
91What does MDR stand for?
Memory data register
92What does IR stand for?
Instruction register
93What are the micro-steps to fetch an instruction?
MAR <- PC; wait for memory; IR <- memory
94How is the PC incremented in a simple microcoded CPU?
Through the ALU: A <- PC; B <- instruction size; PC <- Y
95What did RISC remove?
Unused instructions, data types and addressing modes
96What is the prime motivation for RISC?
Improving performance through pipelining
97What CPI does RISC aim for?
1
98How does RISC achieve a CPI of 1?
Pipelining and a dedicated adder for the PC
99Why can RISC CPUs reach higher clock speeds?
They are simpler, e.g. hardwired rather than microcoded
100What is the main cost of RISC?
A higher instruction count
101Which of these are RISC characteristics?
- Single-cycle instructions
- Fixed-length instructions
- Load/store architecture
- Many addressing modes
102Why do RISC architectures have many registers?
Only load/store access memory, so registers hold temporary operands
103Why should RISC instructions be no wider than the data bus?
So each instruction can be fetched in one cycle
104What bottleneck does RISC worsen?
The memoryus bottleneck, from more instruction fetches
105How is the RISC memory bottleneck mitigated?
Cache memory
106CISC: 100 MHz, CPI 4, IC $10^9$. What is the execution time?
40 s
107RISC: 200 MHz, CPI 1, IC $2 \times 10^9$. What is the execution time?
10 s
108Why is the RISC example faster than the CISC example?
Mostly due to its lower CPI
109Is the instruction count larger for CISC or RISC?
RISC
110Is the CPI higher for CISC or RISC?
CISC
111Do RISC architectures necessarily have fewer instructions?
No, the instructions are less complex, not necessarily fewer
112How can CPI be below 1?
Superscalar or VLIW architectures executing several instructions at once
113What is a superscalar processor?
One that fetches and executes several instructions at once using multiple ALUs
114What does VLIW stand for?
Very Long Instruction Word
115Why are modern x86 (CISC) processors fast?
They convert instructions into simpler micro-instructions that are pipelined
116What is the goal of pipelining?
To reduce CPI by overlapping the execution of instructions
117What kind of parallelism is pipelining?
Instruction-level parallelism (ILP)
118For best pipeline performance, how should stage times compare?
Each stage should take about the same time
119What are the five stages of the example CPU pipeline?
Fetch, Decode, Read, Execute, Write
120What happens in the Fetch stage?
The instruction is fetched from memory: IR <- M[PC]
121What happens in the Decode stage?
The opcode and operands are determined
122What happens in the Read stage?
Source operands are read from the register file
123What happens in the Execute stage?
The ALU performs the operation
124What happens in the Write stage?
The result is written to the destination
125What is the latency and ideal CPI of a 5-stage pipeline?
Latency 5 cycles; CPI 1
126What is the ideal CPI of a pipelined processor?
1
127What are the three types of pipeline hazard?
Resource (structural), data and control
128What is a resource hazard?
Two pipeline stages need the same resource at the same time
129Which resources commonly cause resource hazards?
Memory and the ALU
130What happens when a resource hazard occurs?
A stage is stalled, creating a pipeline bubble
131What is a pipeline bubble?
An empty slot in the pipeline caused by a stall
132What is the effect of pipeline stalls on CPI?
They increase the average CPI
133Why does a LOAD cause a resource hazard on a Princeton architecture?
The Fetch stage and the LOAD's memory read compete for the single memory
134How do processors avoid instruction/data memory resource hazards?
Separate instruction and data caches
135Which instruction needs multiple ALU passes, causing a resource hazard?
Division, typically N cycles for N-bit operands
136What is a data hazard?
An instruction depends on data from a previous instruction still in the pipeline
137What is a RAW hazard?
Read-after-write: I2 reads a result before I1 has written it
138What dependency causes a RAW hazard?
A true dependency
139Which data hazard is most common?
RAW
140Why does MUL R7,R8,R0 then ADD R0,R8,R1 cause a stall?
R0 is written in stage 5 for I1 but read in stage 3 for I2
141What is a WAR hazard?
Write-after-read: I2 overwrites an operand before I1 has read it
142What dependency causes a WAR hazard?
An anti-dependency
143Why are WAR hazards uncommon in typical pipelines?
Operands are read in an earlier stage than results are written
144When can WAR hazards occur?
With out-of-order execution or autoincrement addressing
145What is a WAW hazard?
Write-after-write: writes happen in the wrong order
146What dependency causes a WAW hazard?
An output dependency
147When can WAW dependencies arise in code?
When a compiler isn't optimising
148When is a WAW hazard a problem?
With out-of-order or superscalar execution, not a normal pipeline
149I1: STORE R6, *R1; I3: MUL R10, R9, R1. What dependency is R1?
An anti-dependency (I1 reads R1, I3 writes it)
150What is static hazard detection?
Hazard handling by the compiler
151How does a compiler handle hazards?
Insert NOPs or reorder instructions
152What is dynamic hazard detection?
Hazard handling by the processor at run time
153How does a processor handle hazards dynamically?
Stall with a pipeline interlock, or reorder instructions out of order
154What is a pipeline interlock?
Hardware that stalls an instruction until its hazard clears
155What is a pipeline without interlocks called?
An exposed or open pipeline
156What is data forwarding?
Using bypass multiplexers to pass results directly to following instructions
157What is the purpose of data forwarding?
To reduce hazard delays
158What is a load delay slot?
The extra cycle (or more) before a loaded value can be used
159What is the disadvantage of a long pipeline?
Hazards and stalls cost more cycles
160Why do some CPUs have very long pipelines?
Shorter stages allow a higher clock rate