Chapter 5 - COMPSCI 2GA3

What is the principle of locality in memory access?

Programs access a small portion of their address space frequently, enabling effective caching.

What is temporal locality?

Recently accessed data is likely to be accessed again soon.

What is spatial locality?

Data near recently accessed addresses is likely to be accessed soon.

What is the purpose of a memory hierarchy?

To improve performance by storing frequently accessed data in smaller, faster memory levels.

What is a cache hit?

When data is found in the current memory level (cache), avoiding access to slower memory.

What is a cache miss?

When data is not in the cache and must be fetched from a lower, slower level of memory.

How is miss penalty defined?

The time required to fetch a block from a lower level in the memory hierarchy.

What does hit ratio represent?

The percentage of memory accesses that result in a cache hit.

What is the function of SRAM in the memory hierarchy?

Used for caches due to its speed but is more expensive and less dense than DRAM.

What is the function of DRAM in memory hierarchy?

Used for main memory due to its higher density and lower cost.

What is burst mode in DRAM?

It allows consecutive words from a row to be accessed quickly after the initial access.

What is DDR DRAM?

Double Data Rate DRAM transfers data on both rising and falling clock edges for higher bandwidth.

Why is DRAM refreshed periodically?

It stores data as charge in capacitors which leak over time.

What is NAND flash used for?

High-density storage like USB drives and SSDs, with block-based access.

What is NOR flash used for?

Fast random access memory in embedded systems, such as firmware storage.

Why is flash memory not suitable for RAM replacement?

It wears out after many write cycles and has slower write performance.

What is the main performance metric for hard drives?

Access latency, which includes seek time and rotational delay.

What is seek time in a hard disk?

The time to move the disk arm to the desired track.

What is rotational latency?

The time waiting for the desired sector to rotate under the read/write head.

What is average I/O time in disk performance?

Sum of access latency, transfer time, and controller overhead.

What is the average latency formula for a 7200 RPM disk?

Average latency = 60 / (2 × RPM) = 4.17ms.

Why do modern disk controllers include caches?

To prefetch and buffer data, reducing perceived latency for the CPU.

What is the role of prefetching in disk caching?

To load likely-needed sectors in advance to reduce future access times.

What is the difference between capacity and speed in memory hierarchy?

Lower levels (like disks) have high capacity but lower speed

Why are multiple levels of cache used?

To balance access speed and size, reducing overall memory access time.

What is a cache in memory systems?

A small, fast storage that holds frequently accessed data from slower memory levels.

Why does caching work effectively in programs?

Because of temporal and spatial locality in data access patterns.

What is a direct-mapped cache?

A cache where each memory block maps to exactly one location.

What is a fully associative cache?

A cache where a memory block can be placed in any cache line.

What is a set-associative cache?

A cache where each block maps to a set and can go in any line within that set.

How is a block located in a direct-mapped cache?

By using the block address modulo the number of blocks in the cache.

What is a tag in cache memory?

A portion of the address stored with data to identify which memory block is cached.

What does the valid bit in a cache line indicate?

Whether the cache line contains valid (usable) data or not.

Why do caches use block sizes larger than one word?

To take advantage of spatial locality and reduce miss rates.

What is a cache miss?

An event where requested data is not found in the current cache level.

What happens on a cache hit?

The CPU proceeds with the data already available in cache without delay.

What are the three types of cache misses?

Compulsory, capacity, and conflict misses.

What is a compulsory miss?

A miss that occurs the first time a block is accessed.

What is a capacity miss?

A miss that happens because the cache cannot contain all needed blocks.

What is a conflict miss?

A miss caused by multiple blocks mapping to the same cache location in direct-mapped or set-associative caches.

What is write-through in cache management?

A policy where data is written to both the cache and main memory on a write.

What is the downside of write-through policy?

It increases memory traffic and write latency.

What is write-back cache?

A policy where data is written to cache only and to memory later when the block is replaced.

What does the dirty bit in a write-back cache indicate?

Whether the cached block has been modified and needs to be written back to memory.

What is write allocation?

A policy where on a write miss, the block is loaded into cache before writing.

What is write-around?

A policy where the block is not loaded into cache on a write miss.

Why are write buffers used in caches?

To hold data waiting to be written to memory, allowing the CPU to continue execution.

What is early restart in memory access?

A strategy where the CPU resumes as soon as the required word is returned, not the entire block.

What is critical-word-first strategy?

It fetches the needed word first in a cache miss before loading the rest of the block.

Why are larger cache blocks not always better?

They can increase miss penalty and cause cache pollution despite better spatial locality.

What is cache pollution?

When unnecessary or rarely used data fills up the cache, evicting useful blocks.

What is the average memory access time (AMAT) formula?

AMAT = Hit time + (Miss rate × Miss penalty).

What does CPI stand for in CPU performance?

Cycles Per Instruction.

How do cache misses affect CPI?

They increase memory stall cycles, raising the effective CPI.

What is the effect of increasing clock rate on cache misses?

It increases the relative cost of a miss due to a higher miss penalty.

What is a typical hit time for L1 cache?

Around 1 CPU cycle.

What is a multilevel cache?

A hierarchy of caches (L1, L2, sometimes L3) to balance speed and capacity.

Why is L1 cache small and fast?

To minimize hit time and keep the CPU running efficiently.

What is the role of L2 cache?

It reduces the miss rate from L1 cache by storing more data, though with higher latency.

What is the trade-off in multilevel cache design?

Larger caches reduce miss rate but have higher hit time.

How do you calculate overall CPI with cache misses?

CPI = Base CPI + Miss penalty × Miss rate × Memory access per instruction.

What is the benefit of set-associative caches over direct-mapped?

They reduce conflict misses by allowing more placement options per block.

What is Least Recently Used (LRU) policy?

A replacement strategy that evicts the block that hasn't been used for the longest time.

Why is LRU not practical for high associativity caches?

It becomes too complex and expensive to implement beyond 4-way associativity.

What is a random replacement policy in caching?

A strategy where a block is randomly selected for replacement on a cache miss.

Why does increasing associativity yield diminishing returns?

Because each increase adds cost and complexity while only slightly reducing miss rate.

What is a replacement policy?

A rule for deciding which block to evict from cache on a miss.

How does a 2-way set-associative cache work?

Each block maps to one set and can be stored in either of two slots within that set.

What is the main advantage of associative caches?

Flexibility in placing data reduces conflict misses.

What is the cost of increased associativity?

More comparators and complexity in cache lookup logic.

Why do CPU designers favor smaller L1 block sizes?

To reduce cache pollution and lower hit latency.

What is the impact of data cache miss on loads?

It stalls the pipeline until the requested data is fetched from lower memory.

How does a CPU handle instruction cache misses?

It restarts instruction fetch once the block is loaded into cache.

How can compiler optimizations help cache performance?

By reordering code and data access patterns to improve locality.

What is cache blocking (tiling)?

A technique to divide data into chunks that fit in cache, improving reuse and locality.

What is DGEMM in computing?

Double-precision General Matrix Multiply, a benchmark for floating-point performance.

How does cache blocking help DGEMM performance?

It increases data reuse in cache by operating on sub-blocks that fit in cache.

What is the BLOCKSIZE in a blocked DGEMM implementation?

It defines the size of submatrices to be multiplied, optimized to fit in cache.

What arrays are commonly accessed in DGEMM?

A, B, and C matrices used in matrix multiplication.

Why is loop order important in matrix multiplication?

Different loop orders affect memory access patterns and cache efficiency.

What is dependability in computing systems?

The ability of a system to perform correctly and handle faults effectively.

What is MTTF?

Mean Time To Failure — the average time a system operates before failing.

What is MTTR?

Mean Time To Repair — the average time to restore a failed system to operation.

How is Availability calculated?

Availability = MTTF / (MTTF + MTTR)

What does the Hamming distance measure?

The number of differing bits between two binary strings.

What is the minimum Hamming distance for SEC?

3 — allows single error correction and double error detection.

What does SEC/DED stand for?

Single Error Correction / Double Error Detection — a common ECC technique.

What is a parity bit?

A bit added to data to make the number of 1’s either even or odd, used for error detection.

What happens if SEC parity bits are 0000?

No error is detected in the data.

What does a 2-bit error do in SEC/DED?

It is detected but not correctable.

Why is ECC important in memory systems?

To detect and correct errors, ensuring data integrity.

What is virtual memory?

A technique that allows programs to use more memory than physically available by paging to disk.

What is a virtual machine (VM)?

A software-emulated system that runs guest OSes on a host machine.

What are advantages of virtual machines?

Isolation, resource sharing, security, and legacy software support.

What is an example of an early virtual machine?

IBM VM/370 from the 1970s.

What is modern virtualization software?

Tools like VMWare or Microsoft Virtual PC that emulate entire systems.

Does virtualization affect performance?

Yes, but modern CPUs have support to minimize the overhead.

What is the role of the host OS in virtualization?

It manages resources and provides an environment for guest systems.

Why is virtualization important in cloud computing?

It enables efficient use of hardware by running multiple virtual systems on a single machine.

What is wear leveling in flash memory?

A technique to evenly distribute write/erase cycles to prevent premature failure of cells.