theory based RO questions

Why is a memory hierarchy used?

To combine the advantages of different memory technologies: small fast memories are placed close to the CPU while larger slower memories provide capacity at lower cost.

What is a cache?

A small, fast memory that stores copies of recently or nearby used main-memory blocks to reduce average memory-access time.

What is temporal locality?

The tendency to access recently used data or instructions again soon.

What is spatial locality?

The tendency to access memory locations near a recently accessed location.

What is a cache hit?

The requested memory block is present in the cache and can be accessed there.

What is a cache miss?

The requested memory block is not available in the cache and must be obtained from a lower level of the memory hierarchy.

What conditions are required for a cache hit?

The cache line must be valid and its stored tag must match the tag of the requested address.

What is the purpose of the valid bit?

It indicates whether a cache line currently contains usable valid data. V=0 means the contents must not be used; V=1 means the line contains a valid block.

Does V=1 automatically mean a cache hit?

No. The tag must also match the requested address.

What normally happens to the valid bit when one valid block is replaced by another?

It remains 1 because the cache line still contains a valid block; only its tag and data change.

Is the valid bit part of the memory address?

No. It is cache metadata stored alongside the tag and data.

How is a byte-addressed memory address divided for cache access?

Tag | Set Index | Byte/Block Offset.

What is the purpose of the byte offset?

It selects the particular byte within a cache block.

What is the purpose of the set index?

It determines which cache set must be searched.

What is the purpose of the tag?

It identifies which memory block is currently stored in the selected cache set.

What is a useful mental model for tag and set index?

The set index identifies the position within a round of sets; the tag identifies which round of memory blocks the address belongs to.

How are the number of offset bits calculated?

offset bits = log2(block size in bytes).

How are the number of set-index bits calculated?

set-index bits = log2(number of sets).

How are the number of tag bits calculated?

tag bits = address width - set-index bits - offset bits.

How is the memory block number calculated from a byte address?

Block number = floor(memory address / block size).

How is the set index calculated from the block number?

Set index = block number mod number of sets.

How is the tag calculated from the block number?

Tag = floor(block number / number of sets).

How can the block number be reconstructed from a tag and set index?

Block number = tag × number of sets + set index.

Every how many memory blocks does the set-index pattern repeat?

Every number-of-sets blocks.

Every how many bytes does the set-index pattern repeat?

number of sets × block size in bytes.

For a direct-mapped cache, what is the byte distance between addresses mapping to the same set?

The cache size, because number of sets × block size = cache size for a direct-mapped cache.

Does N-way associativity change which set a memory block maps to?

No. It changes how many blocks can coexist within each set, not the set-index calculation.

What does a 2-way set-associative cache mean?

Each set contains two cache lines called ways, so two different memory blocks mapping to the same set can coexist.

When must replacement occur in a 2-way set-associative cache?

When a new block maps to a set in which both ways are already occupied by valid blocks.

What is the difference between direct-mapped, set-associative, and fully associative caches?

Direct-mapped gives each block exactly one possible cache line; set-associative gives it one set with multiple possible ways; fully associative allows the block to occupy any cache line.

What is the purpose of a cache replacement strategy?

It decides which existing block in a full set should be evicted when a new block must be inserted.

What does LRU mean?

Least Recently Used. It evicts the block that has not been accessed for the longest time.

What important event updates LRU state besides a cache miss?

A cache hit. Accessing a block makes it recently used and can change which other block is the LRU block.

What principle motivates LRU?

Temporal locality: recently accessed data is considered more likely to be accessed again soon.

What is Pseudo-LRU (PLRU)?

A cheaper approximation of LRU that uses less tracking state but may occasionally choose a block that is not the true least recently used block.

Why is PLRU often preferred to exact LRU in highly associative caches?

Exact LRU requires increasingly complex hardware and state as associativity grows; PLRU provides a cheaper approximation with generally good replacement behavior.

What is a compulsory miss?

A miss caused by the first-ever access to a particular memory block; the block has never previously been brought into the cache.

Can a first access still be a compulsory miss if it replaces another block?

Yes. Miss classification concerns why the requested block is absent. A first-ever access is compulsory even if loading it causes an eviction.

What is a conflict miss?

A previously accessed block misses because another block mapping to the same set displaced it, even though the cache has sufficient overall capacity.

What is a capacity miss?

A miss caused because the cache is too small to hold all blocks needed by the working set; even a fully associative cache of the same capacity would miss.

What is the key difference between a capacity miss and a conflict miss?

A capacity miss is caused by insufficient total cache capacity; a conflict miss is caused by placement restrictions that make blocks compete for the same set.

What is a useful first question when classifying a cache miss?

Has this memory block ever been accessed before? If not, it is a compulsory miss.

Why is "this access caused an eviction" not enough to call it a conflict miss?

A new block can cause an eviction on its first access and still be a compulsory miss. Conflict describes why a previously accessed requested block is missing.

What does a 16-bit address width mean in a byte-addressed system?

There are 2^16 distinct byte addresses, so the addressable memory space is 2^16 bytes = 64 KiB.

Does address width determine cache size?

No. Address width determines the addressable memory space; cache size determines how much of that space can be cached at once.

If a block size is 16 bytes, what is the first aligned block range?

0x00 through 0x0F. The next block starts at 0x10.

Why is 0x00–0x0F a 16-byte block rather than 0x00–0x15?

Hexadecimal 0x0F is decimal 15, so the inclusive addresses 0 through 15 give exactly 16 bytes. 0x15 is decimal 21.

Which instructions normally generate data-cache accesses in basic RISC-V cache-tracing questions?

Load and store instructions such as lw, lb, lh, sw, sb, and sh. Ordinary ALU/register instructions do not access the data cache.

Why do add, addi, and similar register operations not count as data-cache accesses?

Their operands/results are handled by registers and the CPU datapath rather than by reading or writing data memory.

What is Write-Through?

A write policy in which a store updates the cached copy and main memory immediately.

What is Write-Back?

A write policy in which a store initially modifies only the cached copy; modified data is written to main memory later when necessary, such as when a dirty block is evicted.

What question does Write-Through versus Write-Back answer?

When should a cached write be propagated to main memory?

What question does Write-Allocate versus No Write-Allocate answer?

What should happen to the cache when a store misses?

What is Write-Allocate?

On a store miss, the missing block is brought into the cache and the store is then performed on the cached block.

What is No Write-Allocate?

On a store miss, the block is not brought into the cache; the store bypasses the cache and writes to main memory.

What commonly happens on a store miss with Write-Through + No Write-Allocate?

The store is a miss, no block is loaded into cache, and the new value is written directly to main memory.

If the same address is repeatedly stored with Write-Through + No Write-Allocate and nothing loads its block into cache, what happens?

Each store can remain a cache miss and write directly to main memory because store misses do not allocate the block.

What happens on a store hit with Write-Through?

The cached value is updated and main memory is updated immediately.

What commonly happens on a store miss with Write-Back + Write-Allocate?

The block is loaded into cache, the cached copy is modified, the dirty bit is set to 1, and main memory is not immediately updated.

What happens on a store hit with Write-Back?

The cached block is modified and its dirty bit is set or remains 1; main memory is not immediately updated.

What is the dirty bit?

Metadata indicating whether a cached block has been modified since it was loaded or last written back and therefore differs from main memory.

What does Dirty=0 mean?

The cached block has no modifications that need to be written back; it can normally be discarded on eviction without updating main memory.

What does Dirty=1 mean?

The cached block contains modifications not yet reflected in main memory and must be written back before it can be discarded.

Is the dirty bit part of the memory address?

No. Like the valid bit, it is cache metadata.

After a clean block is loaded from RAM, what is its dirty bit before any store modifies it?

0, because the cached copy and main-memory copy are identical.

With Write-Back + Write-Allocate, does the first store miss leave Dirty=0 until a second write occurs?

No. The block is first loaded clean, but the store immediately modifies the cached copy, so Dirty becomes 1 during that first store.

What happens to Dirty=1 when the processor performs a load from that block?

It normally remains 1. Reading the block does not synchronize its modified data with main memory.

What happens to Dirty=1 when another store modifies the same cached block?

It remains 1 because the block was already dirty and still differs from main memory.

Does a Write-Back cache necessarily update RAM when the program ends?

No. Write-back occurs when required by the cache/system, such as eviction of a dirty block; program termination itself is not the general rule for writing a block back.

Why does Write-Back generally require fewer main-memory write accesses than Write-Through?

Write-Through propagates every cached write to main memory, whereas Write-Back can combine multiple modifications and write the block back only when necessary.

Why is a dirty bit particularly useful with Write-Back?

It prevents unnecessary memory writes: a clean evicted block can simply be discarded, while only a dirty block must be written back.

Why is a dirty bit generally unnecessary for implementing ordinary Write-Through behavior?

Main memory is updated on every write, so the cached copy does not contain modifications that RAM has not already received.

What are the five classic pipeline stages?

IF (Instruction Fetch), ID (Instruction Decode/Register Read), EX (Execute), MEM (Memory Access), and WB (Write Back).

What is a pipeline data hazard?

A situation in which an instruction depends on data from an earlier instruction that is not yet available at the required pipeline stage.

What is a RAW dependency?

Read After Write: a later instruction needs to read a value that an earlier instruction must first produce/write. It is a true data dependency.

What is forwarding?

A hardware technique that sends a newly produced result directly from a later pipeline register/stage to the consumer's execution input instead of waiting for register-file writeback.

Why can forwarding solve many ALU-to-ALU RAW hazards?

An ALU result is available early enough to be forwarded to the following instruction's EX stage without waiting for WB.

Why does an immediate load-use dependency normally require a stall even with forwarding?

Load data becomes available only after the MEM stage, which is too late for the immediately following instruction's EX stage; forwarding cannot send a value backward in time.

What is the difference between a stall and a flush?

A stall delays pipeline progress and usually inserts/creates a bubble; a flush discards instructions that should not execute, typically because they were fetched from the wrong control-flow path.

What is a control hazard?

Uncertainty about which instruction should be fetched next, typically caused by branches or jumps.

Does branch prediction remove control hazards?

No. It predicts the likely path to reduce their performance penalty; an incorrect prediction still requires recovery such as flushing wrong-path instructions.

What is the difference between static and dynamic branch prediction?

Static prediction uses a fixed rule without runtime history; dynamic prediction uses previous runtime branch behavior.

What does a 1-bit branch predictor remember?

Essentially the branch's most recent outcome and predicts that direction next time.

How does a 2-bit saturating branch predictor improve on a 1-bit predictor?

It uses four states and requires stronger evidence to reverse prediction direction, so one exceptional outcome does not necessarily flip the prediction.

Why is a 2-bit predictor often better for loops?

A mostly taken loop branch may have one exceptional outcome at loop exit; a 2-bit predictor can tolerate that single contrary result without completely reversing its learned direction.

What are RAW, WAR, and WAW in out-of-order execution?

RAW = Read After Write, WAR = Write After Read, WAW = Write After Write.

Which of RAW, WAR, and WAW is a true data dependency?

RAW. WAR and WAW are name dependencies caused by reuse of architectural register names.

What is WAR?

Write After Read: a later instruction must not overwrite a register before an earlier instruction has read the old value.

What is WAW?

Write After Write: two instructions write the same destination, so their writes must not produce the wrong final architectural value.

What is the goal of out-of-order execution?

To execute independent instructions as soon as their operands and required resources are available, increasing instruction-level parallelism while preserving correct architectural behavior.

What is SIMD?

Single Instruction, Multiple Data: one instruction applies the same operation to multiple data elements in parallel.

What workloads commonly benefit from SIMD?

Workloads with the same operation repeated across many data elements, such as graphics, multimedia, vectors, and numerical processing.

What is the difference between a process and a thread?

A process is an executing program with its own process context/address space; a thread is an execution stream within a process and normally shares the process's resources/address space with other threads.

What is multithreading intended to improve at the processor/system level?

Overall throughput by allowing work from another thread to use processor resources or execute when one thread cannot make progress.

Does hardware multithreading necessarily increase ILP within one thread?

No. It exploits thread-level parallelism and can improve overall throughput without increasing the instruction-level parallelism of a single thread.

What is the fundamental difference between a single-cycle and a multicycle processor?

A single-cycle processor completes every instruction in one long clock cycle; a multicycle processor divides instruction execution across multiple shorter cycles/states and can reuse hardware between them.

In a multicycle processor, what does one FSM state generally correspond to?

One clock cycle.

Why can a multicycle processor reuse the same ALU for different purposes?

Different parts of an instruction execute in different cycles, so the same hardware can perform different operations in different FSM states.

What is the purpose of an FSM in a multicycle processor?

It sequences the control signals across clock cycles so each instruction performs the required datapath operations in the correct order.

What is the difference between ALUOp and ALUControl?

ALUOp is an internal higher-level control encoding that indicates the required class/source of ALU operation; ALUControl is the final signal selecting the exact ALU operation.