.png)
Skip to content
Part 4 · BTB · BHT · Addressing Modes
Branch Prediction & Instruction Format Interview Questions (Part 4)
Branch Prediction & Instruction Format Interview Questions (Part 4)
The longest section in this series, covering two of the densest interview topics: branch prediction — from static prediction through BTB, BHT, and TAGE predictors — and instruction formats and addressing modes, the encoding-level questions that trip up even strong candidates.
Table of Contents
Intro Why This Guide
Branch prediction is one of the most consequential ideas in modern processor design — it's the reason a deeply pipelined CPU doesn't grind to a halt every time it hits an `if` statement. It's also one of the most commonly probed topics in mid-to-senior computer architecture interviews, because it touches prediction accuracy, speculative execution, and — since Spectre and Meltdown — hardware security.
This is Part 4 of our five-part series, and it's the largest: 55 questions spanning branch prediction (static and dynamic predictors, BTB, BHT, two-bit saturating counters, GShare, TAGE, and speculative execution) and instruction formats and addressing modes (MIPS instruction types, x86 ModR/M and SIB bytes, and every major addressing mode you'll be asked to explain with an example).
These two topics are grouped together because they tend to appear back-to-back in interviews once hazards are covered — branch prediction explains how the pipeline stays full, and addressing modes explain how instructions actually reference the operands the pipeline is executing.
Context Why These Questions Are Asked in Interviews
Branch prediction questions test whether you understand speculative execution — a concept that's now inseparable from processor security, given how Spectre and Meltdown exploit misprediction recovery.
Addressing mode questions test attention to encoding-level detail, which matters directly if you're working on instruction decoders, assemblers, or RTL that has to interpret an ISA correctly.
How to use this list
Use the search box below to jump to a specific question, or expand every answer at once to read through the whole section. Tap any question to reveal its full answer.
55 questions
Q91–Q102 Static & Dynamic Branch Prediction
Q91 Why is branch prediction important? ▸
Branch prediction is critical because branch instructions constitute 15-25% of all instructions, and every branch potentially disrupts the pipeline. Without prediction, the processor must stall until the branch outcome is known, wasting cycles equal to the pipeline depth to the branch resolution stage. In a 15-stage pipeline, a mispredicted branch wastes ~15 cycles. With branches every 5-7 instructions, poor prediction would devastate performance. Accurate branch prediction allows the processor to speculatively fetch and execute instructions along the predicted path, keeping the pipeline full. Modern CPUs achieve 95-99% prediction accuracy, which is essential for sustaining high IPC in deep, superscalar, out-of-order pipelines.
Q92 What is static branch prediction? ▸
Static branch prediction uses fixed rules determined at compile time or hardwired into the processor, without considering runtime behavior. Common static strategies: (1) Predict always not taken --- simplest, correct for about 50-60% of branches. (2) Predict always taken --- slightly better (~60-70%) since loops are taken most iterations. (3) Backward taken, forward not taken (BTFNT) --- backward branches (loops) are predicted taken, forward branches (if-then) are predicted not taken; achieves ~65-75% accuracy. (4) Compiler hints --- profiling-guided hints in the instruction encoding. Static prediction is simple and requires no hardware history, but accuracy is limited compared to dynamic prediction.
Q93 What is dynamic branch prediction? ▸
Dynamic branch prediction uses runtime history of branch behavior to predict future outcomes. The processor maintains hardware structures that record whether branches were recently taken or not taken, and uses this history to predict the next occurrence. Dynamic predictors adapt to changing program behavior and achieve much higher accuracy (90-99%) than static prediction. Types include: 1-bit predictors, 2-bit saturating counters, correlating (two-level) predictors, tournament predictors, and neural (perceptron-based) predictors. The key insight is that branch behavior is often repetitive --- a loop branch is taken N-1 times and not taken once, making history-based prediction highly effective.
Q94 How does a 1-bit branch predictor work? ▸
A 1-bit branch predictor uses a single bit per entry in a Branch Prediction Buffer (BPB) indexed by the branch instruction's address (usually the lower bits of the PC). The bit records the last outcome: 0 for not taken, 1 for taken. Prediction: the branch is predicted to go the same way as last time. Update: after resolution, the bit is set to the actual outcome. Problem: for a loop that iterates N times, the 1-bit predictor mispredicts twice per loop execution --- once when entering the loop (if last exit was not-taken) and once when exiting (the taken prediction is wrong). This gives accuracy of (N-2)/N for an N-iteration loop, which is poor for short loops.
Q95 How does a 2-bit saturating counter predictor work? ▸
A 2-bit saturating counter uses two bits per entry, representing four states: Strongly Not Taken (00), Weakly Not Taken (01), Weakly Taken (10), Strongly Taken (11). The branch is predicted taken if the counter is in state 10 or 11, not taken if 00 or 01. On a taken outcome, the counter increments (saturates at 11); on not taken, it decrements (saturates at 00). The key advantage over a 1-bit predictor is that a single anomalous outcome doesn't change the prediction --- you need two consecutive mispredictions to switch. For a loop with N iterations, only one misprediction occurs (at exit), giving accuracy of (N-1)/N. This is the most common basic predictor.
Q96 What is a Branch Target Buffer (BTB)? ▸
A Branch Target Buffer (BTB) is a cache-like structure that stores the target addresses of recently executed branch instructions. It is indexed by the branch instruction's PC and returns the predicted target address. The BTB allows the processor to know where to fetch from in the next cycle if the branch is predicted taken, without waiting for address computation. A BTB entry typically contains: the branch PC (tag), the predicted target address, and sometimes the branch type (conditional, unconditional, call, return). The BTB works in conjunction with the direction predictor: the direction predictor says taken/not-taken, and the BTB provides the target address if taken. A BTB miss for a taken branch results in a penalty while the target is computed.
Q97 What is a Branch History Register (BHR)? ▸
A Branch History Register (BHR) is a shift register that records the outcomes (taken/not-taken) of the most recent N branches as a sequence of bits. Each time a branch is resolved, its outcome (1=taken, 0=not-taken) is shifted into the register, and the oldest bit is shifted out. The BHR captures the pattern of recent branch behavior, which is used by two-level (correlating) predictors to index into a Pattern History Table (PHT). For example, a 4-bit BHR recording T,T,N,T would be 1101. Global BHRs track all branches; local BHRs (per-branch) track individual branch history. The BHR enables the predictor to learn correlations between branches.
Q98 What is a correlating (two-level) branch predictor? ▸
A correlating (two-level) predictor uses the history of previous branches to predict the current branch, capturing correlations between branch outcomes. It has two levels: (1) A Branch History Register (BHR) --- either global (all branches) or local (per-branch). (2) A Pattern History Table (PHT) of 2-bit saturating counters, indexed by the BHR value (possibly combined with the branch PC). This allows the predictor to learn patterns like: 'if the last two branches were taken, this branch is likely not taken.' Notation: (m,n) predictor uses m bits of history to index a table of n-bit counters. For example, a (2,2) global predictor uses the last 2 branch outcomes to index one of 4 two-bit counters for each branch.
Q99 What is a GShare predictor? ▸
GShare is a widely-used branch prediction scheme that XORs the Global Branch History Register (GHR) with the branch PC to index into a single table of 2-bit saturating counters. The XOR operation hashes together branch identity (PC) and branch history (GHR), providing better use of the table entries compared to simple concatenation (which would require a much larger table). For example, with a 10-bit GHR and 10-bit PC, GShare XORs them to produce a 10-bit index into a 1024-entry table, while concatenation would need a 20-bit index (1 million entries). GShare achieves good accuracy with modest hardware and is used as a component in modern hybrid predictors.
Q100 What is a tournament (hybrid) predictor? ▸
A tournament predictor combines two or more different prediction mechanisms and uses a chooser (meta-predictor) to select between them for each branch. Typically, it combines a global predictor (good at capturing inter-branch correlations) with a local predictor (good at capturing individual branch patterns). The chooser is a table of 2-bit counters indexed by branch address: it tracks which predictor has been more accurate for each branch and selects accordingly. The Alpha 21264 used a tournament predictor combining a local history predictor with a global GShare predictor. This approach achieves better accuracy than either component alone because different branches may favor different prediction strategies.
Q101 What is a perceptron-based branch predictor? ▸
A perceptron-based branch predictor uses a simple neural network (a single perceptron) for each branch to predict its outcome. Each perceptron has weights corresponding to positions in the global branch history. The prediction is computed as the dot product of the weight vector and the history vector. If the sum exceeds a threshold, the branch is predicted taken; otherwise, not taken. Weights are trained by incrementing or decrementing based on correct/incorrect predictions. Advantages: perceptrons can learn complex correlations and long branch histories that traditional predictors struggle with. The AMD Zen family and Samsung Exynos use perceptron-based predictors. TAGE-SC-L (the most accurate known predictor) combines TAGE with statistical correctors.
Q102 What is a Return Address Stack (RAS)? ▸
A Return Address Stack (RAS) is a small hardware stack that predicts the target of function return instructions. When a CALL instruction is executed, the return address (PC + instruction size) is pushed onto the RAS. When a RET instruction is encountered, the top of the RAS is popped and used as the predicted return target. This achieves near-perfect prediction for returns because function calls and returns are naturally LIFO-ordered. The RAS is separate from the BTB because return addresses change with each call (a function returns to different callers), making the BTB ineffective for returns. RAS depth is typically 16-32 entries; overflow (deep recursion) may cause mispredictions.
Q103–Q115 Advanced Predictors, Speculation & Security
Q103 What is speculative execution in the context of branch prediction? ▸
Speculative execution is the technique of executing instructions beyond a predicted branch before the branch outcome is confirmed. The processor fetches, decodes, and executes instructions along the predicted path, treating them as tentative. If the prediction is correct (which happens 95-99% of the time), the speculative results are committed as normal --- no time wasted. If incorrect, all speculative results are discarded (flushed), and execution restarts from the correct path --- this is the misprediction penalty. Speculative execution requires: the ability to track speculative vs. committed state (reorder buffer), register renaming (so speculative writes don't corrupt committed state), and memory ordering (speculative stores must not be visible until committed). Security note: speculative execution led to Spectre-class vulnerabilities.
Q104 What is the misprediction penalty and how is it calculated? ▸
The misprediction penalty is the number of cycles wasted when a branch is mispredicted. It equals the number of pipeline stages between the fetch stage and the stage where the branch is resolved. In a 5-stage pipeline where branches resolve in EX (stage 3), the penalty is 2 cycles (instructions in IF and ID are wasted). In a 15-stage pipeline with branch resolution in stage 10, the penalty is 9 cycles. The performance impact is: CPI_branch = Branch_frequency × Misprediction_rate × Penalty_cycles. Example: with 20% branches, 5% misprediction rate, and 15-cycle penalty: CPI_branch = 0.20 × 0.05 × 15 = 0.15 additional CPI. Reducing any of these three factors improves performance.
Q105 What is the difference between global and local branch prediction? ▸
Global prediction uses the outcomes of the most recent N branches (from anywhere in the program) stored in a single Global History Register (GHR). It captures correlations between different branches (e.g., if branch A is taken, branch B is likely not taken). It works well when branches are correlated with each other. Local prediction maintains a separate history register for each branch (or set of branches), capturing the behavior pattern of individual branches. It works well for branches with repetitive individual patterns (e.g., inner loop counters). Global excels at inter-branch correlations; local excels at intra-branch patterns. Tournament predictors combine both for the best of both worlds.
Q106 What is TAGE branch prediction? ▸
TAGE (TAgged GEometric history length) is one of the most accurate branch prediction algorithms, developed by André Seznec. It uses multiple tables indexed by different lengths of global branch history, with geometric spacing between history lengths (e.g., 2, 4, 8, 16, 32, 64, 128 bits). Each table entry contains a tag (partial PC), a prediction counter, and a useful counter. Prediction uses the longest matching history. The geometric history lengths allow TAGE to efficiently capture both short and very long branch correlations. TAGE achieves very high accuracy and is the basis for the predictors used in most modern high-performance processors (Intel, AMD, ARM). It was the winner of multiple CBP (Championship Branch Prediction) competitions.
Q107 How does branch prediction accuracy affect overall processor performance? ▸
Branch prediction accuracy has an outsized impact on performance because: (1) With 20% branch frequency and a 15-cycle misprediction penalty, going from 90% to 99% accuracy reduces CPI_branch from 0.30 to 0.03 --- a 10x improvement in branch-related stalls. (2) Mispredictions waste all speculative work done along the wrong path, including energy. (3) Misprediction flushes disrupt out-of-order execution windows, reducing effective ILP. (4) In deep pipelines, the penalty is severe. (5) Performance is highly sensitive to the last few percent of accuracy --- improving from 97% to 98% (halving mispredictions) can yield 5-10% overall speedup. This is why modern predictors use enormous hardware budgets for branch prediction.
Q108 What is branch target prediction vs branch direction prediction? ▸
Branch direction prediction answers: 'Will this branch be taken or not taken?' This determines whether the processor continues fetching sequentially or jumps to a different location. It uses prediction tables (2-bit counters, GShare, TAGE, etc.). Branch target prediction answers: 'If the branch is taken, what is the target address?' This is provided by the Branch Target Buffer (BTB), which caches recently used target addresses. For direct branches, the target is encoded in the instruction, but it is still faster to use the BTB than to decode the instruction. For indirect branches (target from a register), prediction is harder and uses indirect branch predictors (a table of predicted targets indexed by history). Both are needed for efficient speculative fetching.
Q109 What is an indirect branch and how is it predicted? ▸
An indirect branch is a branch whose target address comes from a register or memory location rather than being encoded in the instruction (e.g., JMP R1, or switch statement jump tables). The target can change each time the branch executes, making prediction harder than for direct branches (which always go to the same target). Prediction approaches: (1) BTB caches the last target --- works when the target is stable. (2) Indirect Branch Target Array indexed by global branch history --- captures patterns in target sequences (e.g., virtual function dispatch where the target depends on the object type). (3) Return Address Stack for return instructions. Modern processors use history-indexed target tables that achieve good accuracy for polymorphic dispatch and switch statements.
Q110 What is the branch delay slot? ▸
A branch delay slot is the instruction position immediately following a branch instruction in architectures that use delayed branching (MIPS, SPARC). This instruction is always executed regardless of whether the branch is taken or not. The compiler fills this slot with a useful instruction (typically one that was before the branch and is independent of it), effectively hiding one cycle of branch penalty. If no useful instruction can be scheduled, a NOP is inserted. Advantages: eliminates 1 cycle of penalty without prediction hardware. Disadvantages: complicates exception handling, cannot scale to deeper pipelines or superscalar execution, makes instruction set harder to implement in new microarchitectures. Modern architectures (ARM AArch64, RISC-V) do not use branch delay slots.
Q111 What is predicated execution? ▸
Predicated execution (conditional execution) eliminates some branches entirely by making instructions execute conditionally based on a predicate register or condition flags. Instead of branching around instructions, the instructions execute but their results are committed only if the predicate is true; otherwise, they behave as NOPs. ARM's conditional execution (e.g., ADDEQ --- add only if zero flag set) is a classic example. For short if-then-else blocks, predication converts control flow into dataflow, eliminating the branch and its potential misprediction. The tradeoff is that both paths are executed, wasting work on the path that won't be committed. Predication is beneficial when the branch is hard to predict and the code blocks are short.
Q112 How do Spectre and Meltdown attacks exploit branch prediction? ▸
Spectre exploits branch misprediction to trick the CPU into speculatively executing code that accesses secret data. Even though the speculative execution is eventually rolled back (results not committed), the secret data leaves observable traces in the cache (side channel). The attacker then uses cache timing analysis to infer the secret values. Meltdown exploits out-of-order execution and delayed exception handling --- the processor speculatively reads kernel memory before the permission check completes, and the data affects the cache. Mitigations include retpoline (indirect branch protection), IBRS/IBPB (indirect branch prediction barriers), STIBP, microcode updates, kernel page-table isolation (KPTI), and architectural changes in newer processors. These attacks fundamentally challenged the assumption that speculative execution has no architecturally visible effects.
Q113 What is a loop predictor? ▸
A loop predictor is a specialized branch predictor designed for loop-ending branches (backward conditional branches that are taken for N-1 iterations and not taken once). It counts loop iterations and predicts the branch as taken until the counter reaches the learned trip count, then predicts not-taken for the exit. This achieves perfect prediction for loops with constant trip counts. The loop predictor works alongside the main direction predictor (TAGE, GShare) and overrides it when a loop pattern is detected. Without a loop predictor, the main predictor typically mispredicts the loop exit, costing one misprediction per loop execution. Loop predictors are standard in modern high-performance processors and are particularly valuable for short loops where one misprediction per loop is a significant fraction of total iterations.
Q114 What is the Bimodal predictor? ▸
The Bimodal predictor (also called the BHT or Branch History Table) is one of the simplest dynamic branch predictors. It uses a table of 2-bit saturating counters, indexed by the lower bits of the branch instruction's PC (the branch address). Each counter has four states: Strongly Not Taken (00), Weakly Not Taken (01), Weakly Taken (10), and Strongly Taken (11). The prediction is taken if the counter value is >= 2 (states 10 or 11). After the branch resolves, the counter is incremented on taken and decremented on not-taken, saturating at 00 and 11. The Bimodal predictor achieves about 85-90% accuracy on typical programs and serves as the baseline for more complex predictors.
Q115 What is a Branch Target Address Cache (BTAC)? ▸
A Branch Target Address Cache (BTAC) is similar to a BTB but is accessed during the instruction fetch stage, before the instruction is even decoded. This allows the processor to redirect fetch to the branch target with zero delay for predicted-taken branches. The BTAC is indexed by the fetch address and stores the target address along with the prediction. Some implementations combine the BTAC with a direction predictor. The advantage over a traditional BTB (accessed after decode) is that the fetch can be redirected one cycle earlier, reducing the effective branch penalty. The tradeoff is that the BTAC may produce false positives (non-branch instructions matching an entry), causing unnecessary redirections that must be corrected after decode.
Q116–Q127 Instruction Formats & Basic Addressing Modes
Q116 What is an instruction format? ▸
An instruction format defines the layout of an instruction in binary --- how the bits are organized into fields for the opcode, register specifiers, immediate values, and other information. The format specifies the position and size of each field. RISC architectures typically have a small number of fixed formats (MIPS has R, I, and J types; RISC-V has R, I, S, B, U, J types), all of the same total length. CISC architectures like x86 have complex, variable-length formats with optional prefixes, ModR/M bytes, SIB bytes, and displacement/immediate fields. The instruction format significantly impacts decoder complexity, code density, and pipeline efficiency.
Q117 What are the MIPS R-type, I-type, and J-type instruction formats? ▸
MIPS uses three 32-bit instruction formats: R-type (Register): opcode(6) | rs(5) | rt(5) | rd(5) | shamt(5) | funct(6). Used for register-to-register ALU operations. The opcode is 000000; the specific operation is in funct. Example: ADD rd, rs, rt. I-type (Immediate): opcode(6) | rs(5) | rt(5) | immediate(16). Used for operations with a constant, loads/stores, and branches. The 16-bit immediate is sign-extended. Example: ADDI rt, rs, imm; LW rt, offset(rs). J-type (Jump): opcode(6) | target(26). Used for unconditional jumps. The 26-bit target is combined with the upper 4 bits of the PC to form the jump address. Example: J target.
Q118 What is an addressing mode? ▸
An addressing mode is the method by which an instruction specifies the location of its operand(s). It determines how the processor interprets the address field in the instruction to find the actual data. Different addressing modes provide flexibility in accessing data stored in registers, memory at fixed addresses, memory at computed addresses, and as constants. The choice of addressing modes in an ISA affects instruction encoding complexity, the number of memory accesses per instruction, and the expressiveness of the instruction set. RISC architectures typically support few modes (register, immediate, displacement); CISC architectures support many (including indexed, indirect, auto-increment, etc.).
Q119 Explain Immediate addressing mode. ▸
In immediate addressing, the operand value is encoded directly within the instruction itself as a constant. The data is immediately available without any memory access. Example: ADDI R1, R2, #5 --- the value 5 is part of the instruction encoding. Advantages: no memory access needed (fastest), useful for constants, loop counters, and small literal values. Disadvantages: limited range (constrained by the number of bits available in the instruction format --- e.g., 16 bits in MIPS I-type allows -32768 to 32767). Immediate addressing is used in virtually all architectures and is one of the most frequently used addressing modes for arithmetic/logic operations involving constants.
Q120 Explain Register (Direct) addressing mode. ▸
In register addressing, the operand is located in a CPU register specified by a register number field in the instruction. The register number acts as the address of the operand within the register file. Example: ADD R1, R2, R3 --- operands are in R2 and R3, result goes to R1. Advantages: fastest data access (no memory needed), small address field (log2 of register count --- 5 bits for 32 registers), supports the fastest computation. Disadvantages: limited number of registers (must manage allocation carefully), register contents are volatile and must be saved/restored during context switches and function calls. Register addressing is the dominant mode for ALU operations in all modern architectures.
Q121 Explain Register Indirect addressing mode. ▸
In register indirect addressing, the operand is in memory at the address held in a register. The register contains a pointer to the data, not the data itself. Example: LW R1, (R2) --- load the word at memory address stored in R2 into R1. This is equivalent to base/displacement addressing with a zero offset. Advantages: enables pointer-based data access, dynamic addressing, and data structure traversal (linked lists, trees). Disadvantages: requires an extra memory access (register provides address, then memory is accessed), and an extra instruction may be needed to set up the pointer. In MIPS, this is expressed as LW R1, 0(R2). This mode is essential for accessing heap-allocated data and implementing pointers.
Q122 Explain Base + Displacement (Offset) addressing mode. ▸
In base/displacement (or base+offset) addressing, the effective memory address is calculated by adding a constant displacement (offset) encoded in the instruction to the contents of a base register. Effective Address = Register + Offset. Example: LW R1, 100(R2) --- loads from memory address R2+100. This is the primary memory addressing mode in RISC architectures. It is extremely versatile: it handles local variables (base = stack/frame pointer, offset = variable position), structure/object field access (base = structure pointer, offset = field position), array elements with known indices, and global variable access (base = global pointer). The displacement is typically 12-16 bits, sign-extended.
Q123 Explain Indexed addressing mode. ▸
In indexed addressing, the effective address is computed by adding the contents of two registers: a base register and an index register. Effective Address = Base_Register + Index_Register. Some architectures also support scaled indexing where the index is multiplied by the element size: Effective Address = Base + Index × Scale (x86 supports scale factors of 1, 2, 4, 8). This is particularly useful for array access: the base register holds the array start address, and the index register holds the element offset. Example in x86: MOV EAX, [RBX + RCX*4] --- accesses array[index] where each element is 4 bytes. RISC architectures may emulate this with a separate shift/add instruction before a base+offset load.
Q124 Explain PC-relative addressing mode. ▸
In PC-relative addressing, the effective address is computed by adding a displacement (offset) to the current Program Counter value. Effective Address = PC + Offset. This mode is used primarily for branch instructions and for position-independent code (PIC). Example: BEQ R1, R2, +16 --- if R1=R2, branch to PC+16. Advantages: (1) Branch targets near the current instruction can be reached with small offsets. (2) Code is position-independent --- it works correctly regardless of where in memory it is loaded, which is essential for shared libraries and ASLR (Address Space Layout Randomization). In RISC-V, the AUIPC instruction forms a PC-relative address using a 20-bit upper immediate, and JAL uses a 21-bit PC-relative offset.
Q125 Explain Direct (Absolute) addressing mode. ▸
In direct (absolute) addressing, the instruction contains the complete memory address of the operand. Effective Address = Address_field_in_instruction. Example: LOAD R1, [0x1000] --- loads from absolute memory address 0x1000. Advantages: simple address computation. Disadvantages: (1) The full address must fit in the instruction, consuming many bits and limiting address range. (2) Code is position-dependent. (3) Not commonly used in modern 64-bit architectures because 64-bit addresses would dominate instruction encoding. MIPS J-type uses a 26-bit target combined with the upper 4 PC bits. x86 still supports absolute addressing. RISC architectures generally avoid direct addressing, preferring PC-relative and base+displacement modes.
Q126 Explain Indirect addressing mode. ▸
In indirect addressing, the instruction specifies a memory address that contains the address of the actual operand (a pointer in memory). Effective Address = Memory[Address_in_instruction]. This is essentially dereferencing a pointer stored in memory. Example: LOAD R1, @[0x1000] --- first reads address A from memory location 0x1000, then loads the operand from address A. Advantages: enables dynamic indirection, pointer-to-pointer structures, and dispatch tables. Disadvantages: requires two memory accesses (one for the pointer, one for the data), which is slow. Modern RISC architectures do not support memory indirect addressing in hardware --- it is implemented with two instructions (load the pointer, then load through the pointer). Some CISC architectures like VAX supported it directly.
Q127 Explain Auto-increment and Auto-decrement addressing modes. ▸
Auto-increment mode accesses memory at the address in a register and then automatically increments the register by the data size. Auto-decrement decrements the register first, then accesses memory at the new address. Example: LW R1, (R2)+ means load from address R2, then R2 = R2 + 4 (for words). Example: LW R1, -(R2) means R2 = R2 - 4, then load from new R2. These modes are useful for stepping through arrays (auto-increment), implementing stacks (auto-decrement for push, auto-increment for pop), and string operations. They reduce instruction count by combining memory access and pointer update. Common in CISC (VAX, 68000) and ARM (pre/post-indexed with writeback: LDR R1, [R2], #4). Not available in MIPS or basic RISC-V.
Q128–Q139 Advanced Addressing Modes & Instruction Encoding
Q128 What is the difference between big-immediate and small-immediate instructions? ▸
Small-immediate instructions encode a small constant within the standard instruction format. For example, MIPS I-type has a 16-bit immediate, and RISC-V I-type has a 12-bit immediate. These handle most common constants. Big-immediate (or wide-immediate) instructions handle larger constants that don't fit in standard formats. MIPS uses LUI (Load Upper Immediate) to load a 16-bit value into the upper half of a register, followed by ORI to set the lower 16 bits --- two instructions to form a 32-bit constant. RISC-V uses LUI (20-bit upper immediate) + ADDI (12-bit lower). ARM uses flexible second operand (8-bit immediate with 4-bit rotation) or MOVW/MOVT pairs for 32-bit constants. These design choices balance instruction encoding efficiency with constant range.
Q129 What is the effective address and how is it calculated? ▸
The effective address (EA) is the final memory address used to access an operand, computed from the addressing mode specified by the instruction. Calculations for common modes: Immediate: no EA (operand is in instruction). Register: no memory EA (operand is in register). Direct: EA = address field. Register Indirect: EA = contents of register. Base+Displacement: EA = register + offset. Indexed: EA = register1 + register2. Scaled Indexed: EA = base + index × scale. PC-Relative: EA = PC + offset. Indirect: EA = Memory[address field]. The EA calculation is performed in the execute stage of the pipeline (or address generation unit). Complex addressing modes require additional adders or shifters for EA calculation.
Q130 How does the x86 ModR/M byte work in instruction encoding? ▸
The ModR/M byte is a crucial part of x86 instruction encoding that specifies the operand addressing mode. It contains three fields: Mod (2 bits) --- specifies the addressing mode (00: indirect, 01: indirect+8-bit displacement, 10: indirect+32-bit displacement, 11: register direct). Reg/Opcode (3 bits) --- specifies a register operand or extends the opcode. R/M (3 bits) --- specifies a register or memory operand. When R/M=100 and Mod≠11, a SIB (Scale-Index-Base) byte follows, providing scaled-index addressing: Address = Base + Index × Scale + Displacement. The SIB byte has Scale (2 bits: 1/2/4/8), Index (3 bits), Base (3 bits) fields. This complex encoding enables x86's rich addressing modes but makes instruction decoding hardware-intensive.
Q131 What are RISC-V instruction formats? ▸
RISC-V defines six base instruction formats, all 32 bits wide: (1) R-type: register-register operations. Fields: funct7|rs2|rs1|funct3|rd|opcode. (2) I-type: register-immediate operations, loads. Fields: imm[11:0]|rs1|funct3|rd|opcode. (3) S-type: stores. Fields: imm[11:5]|rs2|rs1|funct3|imm[4:0]|opcode. (4) B-type: conditional branches. Like S-type but immediate encodes a branch offset with different bit arrangement. (5) U-type: upper immediate (LUI, AUIPC). Fields: imm[31:12]|rd|opcode. (6) J-type: unconditional jumps (JAL). Fields: imm[20|10:1|11|19:12]|rd|opcode. Key design principle: source registers (rs1, rs2) and destination register (rd) are always in the same bit positions across formats, simplifying decode.
Q132 What is the concept of orthogonality in instruction set design? ▸
Orthogonality in ISA design means that any operation can be applied to any data type, register, and addressing mode independently. In a perfectly orthogonal ISA, you can combine any opcode with any addressing mode for any operand --- the choices are independent. The VAX architecture was highly orthogonal: any instruction could use any addressing mode for any operand. Advantages: regular, predictable instruction set that is easy for compilers to target. Disadvantages: complex hardware implementation since every combination must work. RISC architectures sacrifice some orthogonality for simplicity --- for example, only load/store access memory, and ALU operations only work on registers. Modern x86 has moderate orthogonality with many restrictions on which operand combinations are valid.
Q133 What is the difference between 2-address, 3-address, and 0-address instruction formats? ▸
3-address: specifies two source operands and one destination. Example: ADD R1, R2, R3 (R1=R2+R3). Most RISC architectures use this, providing maximum flexibility with no implicit operand destruction. 2-address: specifies two operands where one serves as both source and destination. Example: ADD R1, R2 means R1=R1+R2. x86 uses this format, which is more compact but overwrites one source. 1-address: uses an implicit accumulator. Example: ADD X means Accumulator=Accumulator+Memory[X]. Used in early architectures. 0-address: all operands are implicit on the stack. Example: ADD pops two values, pushes the sum. Used in stack machines and JVM bytecode. More addresses mean longer instructions but fewer instructions per program.
Q134 How does ARM's flexible second operand (barrel shifter) work? ▸
ARM's data processing instructions allow the second source operand to be optionally shifted or rotated before use, implemented via a barrel shifter in the ALU input path. The second operand can be: (1) A register shifted by a constant: ADD R1, R2, R3, LSL #2 (R1 = R2 + R3<<2, useful for array indexing). (2) A register shifted by another register: ADD R1, R2, R3, LSR R4. (3) An 8-bit immediate rotated by an even amount: MOV R1, #0xFF00 (255 rotated right by 24). Available shift operations: LSL (logical shift left), LSR (logical shift right), ASR (arithmetic shift right), ROR (rotate right). This effectively provides many addressing and arithmetic capabilities in a single instruction, increasing code density and reducing instruction count.
Q135 What is position-independent code (PIC) and how do addressing modes support it? ▸
Position-independent code (PIC) executes correctly regardless of where in memory it is loaded. This is essential for shared libraries, ASLR, and relocatable executables. PIC is supported by PC-relative addressing --- all branches and data references are expressed as offsets from the current PC, not absolute addresses. For local data: PC-relative loads (RISC-V: AUIPC + LW). For global data: a Global Offset Table (GOT) is accessed PC-relatively; it contains absolute addresses filled in at load time. For function calls: a Procedure Linkage Table (PLT) provides indirect calls through the GOT. x86-64 natively supports RIP-relative addressing (any instruction can use [RIP + offset]). ARM and RISC-V use ADRP/ADD and AUIPC/ADDI sequences for PC-relative addressing.
Q136 What is instruction alignment and why does it matter? ▸
Instruction alignment refers to the requirement that instructions start at memory addresses that are multiples of their size. For a 32-bit (4-byte) instruction, aligned access means the instruction starts at an address divisible by 4. Alignment matters because: (1) Memory systems are optimized for aligned access --- a misaligned fetch may cross a cache line boundary, requiring two memory accesses. (2) Fixed-alignment (as in RISC) simplifies instruction fetch logic --- the next instruction is always at PC+4. (3) Superscalar decode can easily identify instruction boundaries when alignment is fixed. Variable-length instructions (x86) don't have alignment requirements but need complex decode hardware to find instruction boundaries. RISC-V's compressed (C) extension uses 16-bit instructions, so alignment is to 2-byte boundaries.
Q137 What is a zero-operand (stack) instruction format? ▸
A zero-operand instruction format has no explicit operand fields --- all operands are implicit on the operand stack. Operations pop their input operands from the top of the stack, perform the operation, and push the result back. Example: to compute A+B, execute PUSH A, PUSH B, ADD. The ADD instruction has no operand fields --- it implicitly pops two values and pushes one. Advantages: very compact instruction encoding (just an opcode), simple code generation using reverse Polish notation. Disadvantages: significant stack manipulation overhead, poor match for pipelined hardware, and difficulty exploiting ILP since all data flows through the stack. Java bytecode and PostScript use stack-based formats. Hardware implementations include the Burroughs B5000 and some Forth processors.
Q138 What is the SIB byte in x86 encoding? ▸
The SIB (Scale-Index-Base) byte provides scaled-index addressing in x86 instructions. It follows the ModR/M byte when the ModR/M byte's R/M field is 100 (binary) and Mod is not 11. The SIB byte has three fields: Scale (2 bits, values 1/2/4/8), Index (3 bits, specifies the index register), and Base (3 bits, specifies the base register). The effective address is computed as: EA = Base_Register + (Index_Register × Scale) + Displacement. Example: MOV EAX, [EBX + ECX*4 + 8] uses SIB with Base=EBX, Index=ECX, Scale=4, and an 8-bit displacement. This is particularly useful for array access where Scale matches the element size. The SIB byte adds flexibility but complexity to x86 decode logic.
Q139 What is the concept of instruction encoding density? ▸
Instruction encoding density (or code density) measures how compactly a program is represented in binary. It is typically measured in bytes per dynamic instruction or total code size for a benchmark. Higher density means smaller program binaries. CISC architectures (x86 with variable-length 1-15 byte instructions) generally have better code density than fixed-length RISC architectures (32-bit instructions). Good code density matters because: (1) It reduces instruction cache pressure and miss rates. (2) It decreases memory bandwidth for instruction fetch. (3) It reduces program storage size (important in embedded systems). RISC-V's C extension adds 16-bit compressed instructions, improving density by ~25-30%. ARM Thumb-2 similarly mixes 16-bit and 32-bit instructions.
Q140–Q145 Where Performance Metrics Begin — CPI & IPC
Q140 What is CPI (Cycles Per Instruction)? ▸
CPI (Cycles Per Instruction) measures the average number of clock cycles the processor takes to execute one instruction. It is a fundamental metric of processor performance. CPI = Total_Clock_Cycles / Instruction_Count. A lower CPI means better performance. For an ideal scalar pipeline, CPI = 1 (one instruction completed per cycle). In practice, CPI > 1 due to pipeline stalls, cache misses, and branch mispredictions. For superscalar processors, CPI can be less than 1 (e.g., a 4-wide superscalar might achieve CPI = 0.5, meaning 2 instructions per cycle). The inverse of CPI is IPC (Instructions Per Cycle), which is often used for superscalar processors.
Q141 What is the CPU performance equation? ▸
The CPU performance equation relates execution time to three key factors: CPU Time = Instruction_Count × CPI × Clock_Cycle_Time. Equivalently: CPU Time = (Instruction_Count × CPI) / Clock_Frequency. This equation shows three independent ways to improve performance: (1) Reduce instruction count --- better algorithms, compiler optimization, more powerful ISA instructions. (2) Reduce CPI --- better pipeline design, forwarding, branch prediction, cache design. (3) Reduce cycle time (increase clock frequency) --- better circuit design, deeper pipeline, advanced fabrication technology. These factors are interdependent: a CISC ISA reduces instruction count but may increase CPI; a deeper pipeline reduces cycle time but may increase CPI due to higher branch penalty.
Q142 What is IPC (Instructions Per Cycle)? ▸
IPC (Instructions Per Cycle) is the reciprocal of CPI: IPC = 1/CPI = Instruction_Count / Total_Cycles. It measures how many instructions the processor completes on average each clock cycle. For scalar pipelines, IPC ≤ 1. For superscalar processors, IPC can exceed 1 (e.g., a 4-wide superscalar might achieve IPC of 2-3 in favorable code). IPC is preferred over CPI when discussing superscalar performance because higher IPC = better performance, which is more intuitive. Typical IPC values: simple in-order pipeline 0.5-0.8, out-of-order superscalar 1.5-4, theoretical maximum of a 6-wide superscalar is 6 (rarely achieved). IPC depends heavily on the workload --- integer-heavy code may differ from floating-point-heavy code.
Q143 How do you calculate the effective CPI considering stalls? ▸
Effective CPI accounts for all sources of pipeline stalls: CPI_effective = CPI_ideal + CPI_stall_data + CPI_stall_control + CPI_stall_structural + CPI_stall_memory. For a scalar pipeline, CPI_ideal = 1. CPI_stall_data = fraction of instructions with unresolvable data hazards × stall cycles per hazard. CPI_stall_control = branch frequency × misprediction rate × misprediction penalty. CPI_stall_memory = memory access frequency × miss rate × miss penalty (for each cache level). Example: CPI = 1 + (0.05 × 1) + (0.20 × 0.05 × 10) + 0 + (0.30 × 0.02 × 100) = 1 + 0.05 + 0.10 + 0 + 0.60 = 1.75. This shows memory stalls often dominate.
Q144 What is throughput in computer architecture? ▸
Throughput is the amount of work completed per unit time. In processor architecture, it can be measured as: (1) Instruction throughput --- instructions completed per second (IPC × clock frequency). (2) Data throughput --- bytes processed per second. (3) Task throughput --- programs or transactions completed per second. Throughput differs from latency: a pipelined processor has higher throughput (one instruction per cycle in steady state) than a non-pipelined processor, even though each individual instruction takes the same total time (latency). Throughput can be improved by pipelining, superscalar execution, multithreading, and multicore processing. For I/O and memory, throughput is measured in bytes/second or transfers/second.
Q145 What is the difference between latency and throughput? ▸
Latency is the time to complete a single operation from start to finish. Throughput is the number of operations completed per unit time. They are related but distinct. Example: a 10-stage pipeline takes 10 cycles for one instruction (latency = 10 cycles) but completes one instruction every cycle when full (throughput = 1 per cycle). Improving throughput may not improve latency (deeper pipelines increase throughput via shorter cycles but increase instruction latency). Some optimizations improve both (faster hardware), some improve throughput at the cost of latency (pipelining, batching), and some improve latency at the cost of throughput (bypassing queues). For interactive applications, latency matters more; for batch processing, throughput matters more.
Prep Tips for Freshers & Experienced Engineers
For Freshers
- Start with static vs dynamic prediction and the 2-bit saturating counter (Q92–Q95) — these are asked far more often than TAGE or perceptron predictors.
- Practice explaining a BTB and a BHT with a diagram — interviewers often ask you to sketch how they work together to predict both direction and target.
- For addressing modes, memorize one instruction example per mode (immediate, register, register indirect, base+displacement, indexed, PC-relative) — abstract definitions alone rarely satisfy interviewers here.
For Experienced Engineers
- Be ready to discuss Spectre/Meltdown at a conceptual level (Q112) if you're interviewing for a security-adjacent or high-performance core design role.
- Interviewers may ask you to compare GShare, tournament, and TAGE predictors and justify which you'd choose for a given workload — have a structured answer ready.
- For instruction encoding, be prepared to discuss orthogonality and encoding density trade-offs (Q132, Q139) — these come up when comparing RISC-V, ARM, and x86 design philosophies.
Avoid Common Mistakes
- Explaining branch prediction only in terms of direction (taken/not-taken) and forgetting target prediction, which is what the BTB actually solves.
- Confusing a Branch History Register (per-branch or global taken/not-taken history) with a Branch History Table (per-address prediction state) — these are different structures with related names.
- Not being able to explain why a 2-bit saturating counter outperforms a 1-bit predictor (it tolerates a single anomalous branch outcome without flipping its prediction).
- Treating addressing modes as pure memorization instead of connecting each mode to the kind of data access pattern it's optimized for (arrays → indexed, structs → base+displacement, etc.).
FAQ Frequently Asked Questions
Why are branch prediction and addressing modes grouped into one article?
They're both dense, encoding-and-prediction-heavy topics that tend to be interviewed back-to-back once hazards are covered, and together they round out the instruction execution and instruction encoding picture of a processor.
Do I need to know TAGE predictors for a fresher interview?
Usually not in depth — TAGE (Q106) is more relevant for senior or research-oriented roles. Freshers should be solid on static/dynamic prediction, 2-bit counters, and the BTB/BHT.
How much detail do I need on Spectre and Meltdown?
A conceptual explanation of how speculative execution can leak data through microarchitectural side channels is usually sufficient unless the role is specifically security-focused.
Which addressing modes are asked most often?
Immediate, register direct, register indirect, base+displacement, and PC-relative (Q119–Q124) are the most frequently asked. Auto-increment/decrement and the x86 ModR/M and SIB bytes are common senior-level follow-ups.
Why does this section include a few CPI/IPC questions at the end?
Q140–Q145 mark the transition into performance metrics, which is covered in full in Part 5 — they're included here since they naturally follow once instruction encoding is covered.
Wrap-up Conclusion
Branch prediction and instruction encoding are dense but highly rewarding topics to master — they're where interviews test both conceptual depth (speculative execution, prediction accuracy) and precision (addressing modes, encoding formats). With this covered, Part 5 wraps up the series with performance metrics and advanced cross-cutting topics: CPI, memory hierarchy, out-of-order execution, and modern multicore and GPU architecture.
Ready for the next round?
Keep the momentum going — work through all five parts back to back, or jump straight to the topic your next interview is focused on.
Part 5: Continue Learning
Comments
Post a Comment