Intro to Computer Systems Final
4.1
Card 1: Front: What is the principle of locality? Back: The principle of locality is a key concept that enables effective use of a memory hierarchy. It reflects the tendency for programs to access memory locations non-uniformly, with clusters of frequently accessed locations that change slowly over time.
Card 2: Front: What are the two main types of locality? Back:
Temporal locality: Recently referenced items are likely to be referenced again in the near future.
Spatial locality: Items with nearby addresses to a recently referenced item are likely to be referenced soon.
Card 3: Front: What does temporal locality result from? Back: Temporal locality arises from common program features like looping constructs, temporary variables, stacks, and frequently called subroutines. These cause the same data locations to be accessed repeatedly over a short period of time.
Card 4: Front: What does spatial locality reflect? Back: Spatial locality reflects the tendency for programs to access instructions sequentially and access data items stored close together, such as elements of an array or fields of a record. Nearby memory locations are likely to be referenced close together in time.
Card 5: Front: How do locality properties enable the memory hierarchy to improve performance? Back: Locality allows the memory hierarchy to store frequently accessed instructions and data in smaller, faster memories closer to the processor (like caches). This reduces the overall access time compared to always accessing slower main memory.
Card 6: Front: What observation did Denning make about locality based on memory references? Back: Denning observed that locality is based on the assertion that memory references made in the near future are likely to be to locations that were recently referenced or locations near recently referenced items. The likelihood of a reference to a location depends on the distance from current time to the previous reference to that location.
4.2
Card 1: Front: What are the main characteristics used to categorize memory systems? Back: Computer memory systems can be categorized according to several key characteristics:
Location (internal vs external)
Capacity (amount of data stored)
Unit of transfer (size of data moved between levels)
Access method (how data is accessed)
Performance metrics
Physical type (underlying technology)
Physical characteristics (volatility, erasability, etc.)
Card 2: Front: What is the difference between internal and external memory? Back:
Internal memory is located within the processor itself or very close to it. This includes registers, cache, and main memory. It is directly accessible by the processor.
External memory is located further from the processor and accessed via I/O controllers. This includes solid-state drives, hard disk drives, optical discs, magnetic tape, etc.
Card 3: Front: What units are used to measure memory capacity? Back: Memory capacity is usually measured in bytes (B) or words. For example, a memory chip might store 4 GB (gigabytes) or 1 million 64-bit words.
Card 4: Front: What is the unit of transfer in a memory hierarchy? Back: The unit of transfer is the amount of data moved between levels of the hierarchy in a single operation. This could be:
Small, like a word (e.g. 64 bits), for transfers between registers and cache
Medium, like a block or line (e.g. 64 bytes), for transfers between cache and main memory
Large, like a page (e.g. 4 KB), for transfers between main memory and disk
Card 5: Front: What are the different access methods used by memory systems? Back:
Random access: Any location can be accessed directly by providing its address. This is used by registers, caches, and main memory (RAM).
Sequential access: Data must be accessed in a specific linear order, like on magnetic tape.
Direct access: Data is accessed directly by address, but may require sequential searching to get to the right location, like on a hard disk.
Card 6: Front: What key metrics are used to measure memory performance? Back:
Access time (latency): Time to retrieve the first word accessed
Cycle time: Minimum time delay between issuing two independent accesses
Transfer rate (bandwidth): Amount of data moved per unit time, once an access has started
Latency determines how quickly a single access can be made, while bandwidth determines the overall data transfer speed for a sequence of accesses.
Card 7: Front: What are the common physical types of memory? Back:
Semiconductor: Based on integrated circuits, like SRAM and DRAM chips
Magnetic: Recording data by magnetizing regions of a material, like in hard disks and tape
Optical: Using light to record and read data, like CDs and DVDs
Each has different trade-offs in speed, density, cost, and reliability.
Card 8: Front: What physical characteristics are used to categorize memories? Back: Key physical characteristics include:
Volatility: Volatile memory loses data when power is removed (SRAM, DRAM), while non-volatile memory retains it (Flash, ROM, disks).
Erasability: Some memories can only be written once (ROM), while others allow erasing and rewriting (SRAM, DRAM, Flash).
Writes: Read-write memory allows fast updates (SRAM, DRAM), while read-only memory either cannot be updated or requires a slow erase operation first (ROM, Flash).
4.3
Card 1: Front: What is the fundamental challenge in designing memory for a computer system? Back: The key challenge is the trade-off between capacity, speed, and cost. Ideally, we want a memory system that:
Is large enough to hold all the data and instructions needed
Can be accessed very quickly to keep up with the processor
Is affordable to implement
However, in practice there is no single memory technology that is optimal in all three dimensions. Larger memories tend to be slower and more expensive per bit than smaller ones.
Card 2: Front: How does the memory hierarchy help address this challenge? Back: The memory hierarchy divides the memory system into multiple levels, each optimized for a different point in the capacity/speed/cost trade-off space:
Small, fast, expensive memories are placed closer to the processor. These serve as caches to hold frequently-used data and instructions.
Larger, slower, cheaper memories are placed further away. These provide bulk data storage.
The goal is to create an overall memory system that approaches the speed of the fastest memory and the cost per bit of the cheapest memory.
Card 3: Front: What are the typical levels in a memory hierarchy and their characteristics? Back: From smallest/fastest to largest/slowest:
CPU registers: ~100 bytes, sub-nanosecond access, on CPU chip
L1 cache: ~64 KB, ~1 ns access, on CPU chip
L2 cache: ~256 KB, ~5 ns access, on CPU chip
L3 cache: ~8 MB, ~20 ns access, on CPU chip or separate chip
Main memory (DRAM): ~16 GB, ~100 ns access, separate memory module
Solid-state drive: ~1 TB, ~50-100 μs access, separate storage device
Hard disk drive: ~10 TB, ~5-10 ms access, separate storage device
Each successive level is larger and cheaper per bit than the previous one, but also slower to access.
Card 4: Front: What are the key ideas that make the memory hierarchy work? Back:
Temporal locality: Recently accessed items are likely to be accessed again soon.
Spatial locality: Items with addresses close to recently accessed items are likely to be accessed soon.
Smaller memory at level k serves as a cache for larger memory at level k+1.
On a memory access, check successively larger levels until the data is found, then copy it back to faster levels for future use.
By exploiting locality, the memory hierarchy can provide the illusion of a large, fast, and cheap memory to programs.
Card 5: Front: How does the cost per bit and access time change as we move up the memory hierarchy from level k+1 to level k? Back: Let c(k) be the cost per bit and t(k) be the access time for level k. Then:
c(k) > c(k+1): Level k memory is more expensive per bit than level k+1 memory
t(k) < t(k+1): Level k memory is faster to access than level k+1 memory
For example, SRAM used in caches is more expensive per bit but faster to access than DRAM used in main memory. This is what allows us to build a cost-effective hierarchy.
Card 6: Front: How big should each level of the hierarchy be? Back: The size of each level is a trade-off between cost and performance:
Larger memories at level k can capture more of the working set and reduce misses to the slower level k+1. This improves performance.
But larger memories are also more expensive and take up more space.
In practice, sizes are chosen to balance these factors based on the intended application and cost targets. For example:
L1 caches are kept small (e.g. 64 KB) to be very fast and not take up too much chip area.
L2 and L3 caches are made larger (e.g. 256 KB to 8 MB) to capture more of the working set while still being reasonably fast and cheap.
Main memory is sized to be cost-effective for the overall system (e.g. 16 GB).
Card 7: Front: What happens on a memory access in the memory hierarchy? Back: On a memory access:
The processor first checks the smallest/fastest level (e.g. L1 cache).
If the data is found, it's a hit. The processor reads the data and continues.
If the data is not found, it's a miss. The processor checks the next level.
This process repeats for each successively larger/slower level until the data is found.
When the data is found at level k, it's copied back to all the faster levels (L1 to L(k-1)) for future use.
If the data isn't in any cache, it's fetched from the slowest level (main memory or disk).
The key idea is that by the principle of locality, most accesses will be satisfied by the faster cache levels most of the time. This gives the illusion of a large, fast memory.
Card 8: Front: How is data exchanged between levels of the memory hierarchy? Back: Data is moved between adjacent levels in blocks, also called cache lines:
When level k is accessed and the data is found in level k+1, a whole block containing the requested data is copied from k+1 to k.
The block size is typically larger for lower levels (e.g. 64 bytes for L1, 256 bytes for L2).
Larger blocks can better exploit spatial locality by prefetching nearby data that's likely to be used soon.
But larger blocks also take longer to transfer and fill up more of the limited space in the faster level.
4.4
Card 1: Front: What is a cache miss and why do they happen? Back: A cache miss occurs when the processor requests data from the cache, but the data is not there. The cache then has to fetch the data from a slower level of the memory hierarchy (which could be a lower-level cache or main memory).
Misses happen because of the fundamental trade-off in cache design:
We want caches to be large to hold more data and reduce misses.
But larger caches are also slower and more expensive.
So caches are designed to be just large enough to capture most of the working set and benefit from locality, but not so large that they become slow and costly.
Card 2: Front: How do cache misses affect performance? Back: Cache misses are expensive because they require accessing a slower level of memory. This stalls the processor as it waits for the data to be fetched.
The impact of a miss depends on:
The miss penalty: This is the time to fetch the data from the slower level. It's much larger than the normal cache hit time.
The miss rate: This is the fraction of cache accesses that result in a miss. A higher miss rate means more of the expensive miss penalties.
So our goal in designing a cache is to minimize the Average Memory Access Time (AMAT), which accounts for both hits and misses:
AMAT = Hit time + Miss rate × Miss penalty
Card 3: Front: What are the different types of cache misses? Back: To understand and improve cache performance, it's helpful to classify misses into three categories (The 3 C's):
Compulsory misses: These are caused by the first access to a block of data. The data has never been brought into the cache, so the miss is unavoidable. Also called cold start misses.
Capacity misses: These happen when the working set size (the data actively being used) is larger than the cache size. The cache can't hold all the data, so blocks are continually evicted and later retrieved.
Conflict misses: In non-fully associative caches, these occur when multiple blocks compete for the same set, even if the cache isn't full. Depends on the cache's mapping function.
Each type of miss requires a different optimization strategy.
Card 4: Front: How do cache size, block size, and associativity affect miss rate? Back: The miss rate is determined by the interplay of several cache design parameters:
Cache size: A larger cache can hold more of the working set, reducing capacity and conflict misses. But it's more expensive and has a slower access time.
Block size: Larger blocks can exploit spatial locality to reduce compulsory misses. But they also take up more space, potentially increasing capacity and conflict misses.
Associativity: Higher associativity allows more flexibility in block placement, reducing conflict misses. But it also makes the cache more complex and slower.
The optimal values depend on the characteristics of the workload (the data access patterns). There's no one-size-fits-all solution - it's about finding the right trade-offs for a given application and system constraints.
Card 5: Front: What are the key ideas behind multilevel caches? Back: The concept of multilevel caches extends the same locality principles of a single cache level to a hierarchy of caches:
The fastest and smallest cache (L1) is accessed first.
If the data is there (a hit), great! The processor continues.
If not (a miss), we check the next level cache.
This continues for each successively larger and slower level, until the data is found or we reach main memory.
On a miss, the data is copied into all the higher (faster) cache levels. This ensures future accesses to the same data will be hits.
The key idea is that by having multiple levels with increasing size, we can capture both temporal and spatial locality at different scales:
The small L1 cache captures the most frequently used data with fast access times.
The larger lower-level caches (L2, L3, etc.) hold a bigger working set to reduce capacity misses, at the cost of slightly slower access times.
This allows us to approach the performance of a large, fast cache at a fraction of the cost.
Card 6: Front: How do we measure the performance of a multilevel cache system? Back: The main metric is still the Average Memory Access Time (AMAT), but now we need to account for hits and misses at each level.
For a two-level cache: AMAT = L1 hit time + L1 miss rate × (L2 hit time + L2 miss rate × Memory access time)
And more generally for an N-level cache: AMAT = L1 hit time + L1 miss rate × (L2 hit time + L2 miss rate × (... (LN hit time + LN miss rate × Memory access time)...))
The goal is to minimize AMAT by optimizing the hit rates and access times at each level. This involves careful choices of cache size, block size, and associativity for each level based on the expected workload.
Card 7: Front: What's the bottom line for multilevel cache design? Back: The key takeaways are:
Caches work by exploiting temporal and spatial locality in data access patterns. They hold recently used data to avoid slow memory accesses.
But caches are limited in size, leading to misses. Misses are expensive and impact performance.
Different types of misses (compulsory, capacity, conflict) require different optimizations.
Multilevel caches provide a hierarchy of sizes and speeds to capture locality at different scales. This is a cost-effective way to approximate a large, fast cache.
The performance of a multilevel cache depends on the hit rates and access times at each level. These are determined by design choices like cache size, block size, and associativity.
Optimal design requires understanding the memory access patterns of the expected workload and making informed trade-offs. There's no one-size-fits-all solution.
5.1
Card 1: Front: What is cache size and how does it affect performance? Back: Cache size refers to the total amount of data the cache can hold. It's usually measured in bytes or words.
A larger cache can hold more of the working set, reducing capacity misses. This is good for workloads with large data structures or complex control flow.
But a larger cache is also slower (longer access time) and more expensive (more chip area and power).
The optimal size depends on the locality characteristics of the expected workloads and the available chip resources. Too small and you'll have frequent misses; too large and you'll waste resources and slow down all accesses.
Card 2: Front: What is the cache mapping function and what are the main types? Back: The mapping function determines where in the cache a given block of memory can be placed. It's a key design choice that affects both hit rate and hardware complexity.
The main types of mapping functions are:
Direct mapped: Each memory block has only one possible location in the cache, determined by its address. Simple but inflexible.
Fully associative: A block can go anywhere in the cache. Maximizes flexibility but requires complex comparison hardware.
Set associative: The cache is divided into sets, each of which consists of a number of blocks. A memory block can go anywhere within a specific set determined by its address. A good compromise.
The choice of mapping function is a trade-off between hit rate (favored by associativity) and simplicity (favored by direct mapping).
Card 3: Front: What is the cache replacement policy and why is it important? Back: The replacement policy decides which existing block to evict when a new block needs to be brought into a full cache. It's important because it affects both the hit rate and the implementation complexity.
Some common replacement policies are:
Least Recently Used (LRU): Evicts the block that was accessed furthest in the past. Good for workloads with temporal locality.
First In First Out (FIFO): Evicts the block that was brought in earliest. Simple but doesn't consider usage.
Least Frequently Used (LFU): Evicts the block that was used least often. Good for workloads with frequently accessed "hot" blocks.
Random: Evicts a random block. Very simple but can evict important blocks.
The best policy depends on the access patterns of the expected workloads. LRU and its variants are popular because they provide a good balance of hit rate and simplicity for many common cases.
Card 4: Front: What are the main cache write strategies and their trade-offs? Back: The write strategy determines what happens when the processor writes to a block that's in the cache. It affects both the hit rate and the consistency between the cache and main memory.
The two main strategies are:
Write through: Every write is immediately propagated to main memory. Ensures consistency but generates a lot of memory traffic.
Can be paired with a write buffer to hide the latency of the memory writes.
Write back: Writes are only done in the cache, and the modified block is written back to memory when it's evicted. Reduces memory traffic but risks inconsistency.
Needs a "dirty bit" to track which blocks have been modified.
Write through is simpler but write back is more efficient for most workloads. The choice depends on the balance between write frequency, memory bandwidth, and the need for consistency.
Card 5: Front: What is the line or block size and how does it affect performance? Back: The line or block size is the unit of data transfer between the cache and main memory. It's usually larger than the word size to exploit spatial locality.
A larger block size means more data is brought in on a miss, potentially avoiding future misses (compulsory and capacity). This is good for workloads with spatial locality, like sequential array accesses.
But a larger block size also means more data is transferred on each miss, using more memory bandwidth and potentially evicting other useful blocks (conflict misses).
The optimal size depends on the spatial locality characteristics of the expected workloads and the memory system parameters. A common choice is 32-128 bytes.
Card 6: Front: What are the main cache performance metrics? Back: To evaluate and optimize cache designs, we need quantitative performance metrics. The main ones are:
Hit time: The time to access data in the cache, including the time to determine if it's a hit.
Affected by cache size and associativity.
Miss penalty: The additional time required on a miss to fetch data from a lower level of the hierarchy and install it in the cache.
Affected by block size and memory latency.
Miss rate: The fraction of accesses that result in a miss.
Affected by cache size, associativity, block size, and replacement policy.
These metrics combine to give the Average Memory Access Time (AMAT): AMAT = Hit time + Miss rate × Miss penalty
The goal of cache design is to minimize AMAT for the expected workloads by balancing the individual metrics. This requires understanding the workloads' locality characteristics and the hardware implementation trade-offs.
Card 7: Front: What are the key takeaways for cache design? Back: Cache design is all about making the right trade-offs to maximize performance for a given workload and system constraints. The key principles are:
Exploit temporal and spatial locality to minimize misses.
Temporal locality suggests keeping recently accessed data in the cache (favors larger size and smarter replacement).
Spatial locality suggests using larger block sizes to prefetch nearby data.
Balance hit rate and hit time.
Higher associativity and smarter replacement policies improve hit rate but increase hit time.
Direct mapping is fastest but most prone to conflict misses.
Minimize miss penalty.
Larger block sizes reduce compulsory misses but increase transfer time.
Write back reduces memory traffic but requires consistency management.
Tailor to expected workloads and system constraints.
Different applications have different locality characteristics and performance needs.
Hardware budgets limit cache size, associativity, and features.
5.2
Card 1: Front: What is the purpose of the cache mapping function? Back: The cache mapping function determines where in the cache a given block of memory can be placed. It's a crucial design choice because it affects both the cache hit rate (how often the processor finds the data it needs in the cache) and the complexity of the cache hardware.
Card 2: Front: What are the three main types of cache mapping functions? Back: The three primary cache mapping techniques are:
Direct mapped
Fully associative
Set associative
Each represents a different point in the trade-off between flexibility (which improves hit rate) and simplicity (which reduces hardware cost and access time).
Card 3: Front: How does direct mapped cache work? Back: In a direct mapped cache, each memory block has only one possible location in the cache where it can be placed. This location is determined by the block's memory address.
Specifically, the cache location is usually calculated by taking the least significant bits of the block address modulo the number of blocks in the cache.
For example, in a 4KB direct mapped cache with 64B blocks, the 6 least significant bits of the block address would determine which of the 64 cache blocks it maps to.
Card 4: Front: What are the advantages and disadvantages of direct mapped cache? Back: Advantages:
Simple to implement in hardware (only need to check one location on each access)
Fast access time (no need to search multiple locations)
Disadvantages:
Inflexible placement (if multiple frequently used blocks map to the same cache block, they'll constantly evict each other causing conflict misses)
Lower hit rate compared to more flexible schemes
Direct mapped caches are a good choice when simplicity and speed are more important than hit rate. They're commonly used for small, fast caches like the L1.
Card 5: Front: How does fully associative cache work? Back: In a fully associative cache, a memory block can be placed anywhere in the cache. The cache hardware searches all locations in parallel to find the requested block.
This requires each cache entry to store the full memory address of the block it contains (not just the tag bits). On each access, this full address is compared against the requested address simultaneously for all cache entries.
Card 6: Front: What are the advantages and disadvantages of fully associative cache? Back: Advantages:
Most flexible placement (any memory block can go anywhere in the cache)
Highest hit rate (no conflict misses)
Disadvantages:
Complex and expensive hardware (need to search all locations simultaneously on every access)
Slower access time (due to the complexity of the parallel search)
Higher power consumption (all those parallel comparisons take energy)
Fully associative caches provide the best hit rate but at a high cost in terms of hardware complexity, access latency, and power. They're typically only used for small, specialized caches where the hit rate is critical, like the translation lookaside buffer (TLB).
Card 7: Front: How does set associative cache work? Back: Set associative cache is a compromise between the simplicity of direct mapped and the flexibility of fully associative.
In an N-way set associative cache, the cache is divided into sets, each of which consists of N blocks. A memory block can be placed anywhere within a specific set determined by its address (like in direct mapped), but it can be in any of the N blocks within that set (providing some flexibility).
For example, in a 4-way set associative cache, each set contains 4 blocks. The memory address is used to determine which set a block belongs to, and then the block can be placed in any of the 4 locations within that set.
Card 8: Front: What are the advantages and disadvantages of set associative cache? Back: Advantages:
Good compromise between hit rate and simplicity
More flexible placement than direct mapped (reduces conflict misses)
Simpler hardware than fully associative (only need to search N locations per set)
Disadvantages:
More complex hardware than direct mapped (need to search multiple locations and implement a replacement policy)
Slower access time than direct mapped (due to the need to search multiple locations)
The choice of N (the associativity) allows the designer to balance hit rate and complexity. Higher N means better hit rate but more hardware and slower access.
2-way and 4-way set associative caches are common choices for L1 and L2 caches as they provide a good balance for many workloads.
Card 9: Front: How is the cache organized in a set associative scheme? Back: In a set associative cache, the cache is organized as a 2D array of sets and ways (blocks per set).
The number of sets is determined by the cache size and the block size. For a cache with C blocks and an associativity of N, there are C/N sets.
Each set contains N blocks (the associativity).
The memory address is divided into the tag, set index, and block offset bits.
The set index bits determine which set the block belongs to.
The tag bits are stored in the cache to identify which memory block is in each location.
The block offset bits determine the location within the block.
On a cache access, the set index bits are used to select the correct set. Then, the tag bits are compared simultaneously for all blocks in the set to find the requested data.
Card 10: Front: What are the key factors in choosing a cache mapping function? Back: The choice of cache mapping function depends on several factors:
The size of the cache: Smaller caches tend to benefit more from the simplicity of direct mapping, while larger caches can afford the complexity of set associativity for improved hit rate.
The workload characteristics: Workloads with more temporal locality (reuse of recently accessed data) benefit from more flexible placement to avoid conflict misses. Workloads with more spatial locality (accessing nearby data) are less sensitive to the mapping function.
The performance requirements: Applications that are latency-sensitive may prefer the faster access time of direct mapped caches, while those that are more sensitive to hit rate (like many scientific applications) may prefer set associative caches.
The power and cost budget: Fully associative and high-associativity caches consume more power and chip area, which may not be acceptable for power or cost-constrained designs.
5.5
Card 1: Front: What is the main goal of cache performance optimization? Back: The main goal is to minimize the average memory access time (AMAT). This is the average time it takes for the processor to access a word of data, considering both hits and misses in the cache hierarchy.
Conceptually: AMAT = Hit time + Miss rate × Miss penalty
To minimize AMAT, we need to either:
Reduce the hit time (make hits faster)
Reduce the miss rate (make misses less frequent)
Reduce the miss penalty (make misses less expensive)
Different optimization techniques target different parts of this equation.
Card 2: Front: What factors affect cache hit time? Back: Cache hit time is the time it takes to access data in the cache, including the time to determine whether it's a hit. It's affected by:
Cache size: Larger caches have longer hit times due to the greater distance the signal needs to travel and more complex decoding logic.
Associativity: Higher associativity means more locations need to be checked in parallel, which takes more time and hardware complexity.
Technology: The underlying transistor and interconnect technology affects the speed of the cache circuits.
To reduce hit time, designers might:
Use smaller, simpler caches (like direct-mapped L1)
Pipeline the cache access over multiple cycles
Use faster, more advanced circuit technology
Card 3: Front: What is cache miss rate and what affects it? Back: Cache miss rate is the fraction of cache accesses that result in a miss (i.e., the requested data is not found in the cache). It's a key metric because misses are much more expensive than hits.
Miss rate is affected by:
Program behavior: The locality characteristics of the code (spatial vs temporal) and its working set size relative to the cache.
Cache capacity: A larger cache can hold more of the working set, reducing capacity misses.
Cache associativity: Higher associativity reduces conflict misses by providing more placement options for each block.
Block size: Larger blocks can exploit spatial locality to reduce compulsory misses, but may increase capacity and conflict misses.
Replacement policy: Smarter policies (like LRU) can better predict which blocks will be used again, reducing misses.
To reduce miss rate, designers or programmers might:
Increase cache capacity or associativity
Optimize code for better locality and working set size
Choose appropriate block sizes and replacement policies
Card 4: Front: What is miss penalty and what affects it? Back: Miss penalty is the additional time it takes to service a cache miss by fetching the data from a lower level of the memory hierarchy (which could be a lower-level cache or main memory). It's a significant component of AMAT because misses are so much slower than hits.
Miss penalty is affected by:
Memory technology: The speed of the lower-level memory (e.g., DRAM for main memory).
Memory hierarchy depth: More levels of cache mean more potential places to find the data before going to main memory.
Miss handling architecture: Techniques like out-of-order execution and non-blocking caches can hide some of the miss latency by allowing other work to proceed in parallel.
Block size: Larger blocks take more time to transfer from the lower level.
To reduce miss penalty, designers might:
Use faster memory technology
Add more levels of cache
Implement techniques to hide or overlap miss latency
Choose appropriate block sizes
Card 5: Front: What are some common cache optimization techniques? Back: There are many techniques used in modern processors to optimize cache performance. Some key ones include:
Multi-level caches: Using multiple levels of progressively larger and slower caches to balance hit time and miss rate.
Out-of-order execution: Allowing the processor to execute instructions non-sequentially to hide cache miss latency.
Non-blocking caches: Allowing the cache to continue servicing hits while waiting for a miss to be resolved.
Prefetching: Predicting which data will be needed soon and fetching it into the cache before it's requested to avoid misses.
Victim caches: A small, fully-associative cache to hold recently evicted blocks, giving them a "second chance" to avoid misses.
Cache compression: Compressing data in the cache to fit more blocks and reduce capacity misses.
Cache hierarchies: Using separate instruction and data caches, or separate caches for different types of data, to reduce interference.
The effectiveness of these techniques depends on the specific workload and system characteristics. Modern processors often use a combination of them, with complex control logic to adapt to different situations.
Card 6: Front: What is the CPU time formula and how does it relate to cache performance? Back: The CPU time formula breaks down the execution time of a program into its key components:
CPU time = (CPU clock cycles + Memory stall cycles) × Clock cycle time
where:
CPU clock cycles are the cycles spent doing useful work (executing instructions)
Memory stall cycles are the cycles wasted waiting for memory accesses (cache misses)
Clock cycle time is the duration of each clock cycle (determined by the clock frequency)
This formula shows how cache performance directly impacts overall CPU performance. Every cache miss adds stall cycles, increasing the total CPU time.
We can further expand the memory stall cycles term:
Memory stall cycles = Number of misses × Miss penalty
This shows how both the number of misses (miss rate) and the cost of each miss (miss penalty) contribute to the overall stall time.
To optimize CPU time, we need to minimize both components:
Reduce misses through cache-friendly code and cache organization
Reduce miss penalty through multi-level caches and latency-hiding techniques
Improving cache performance is one of the most effective ways to improve overall system performance, because it has a direct and significant impact on CPU time.
Card 7: Front: What is the role of cache performance models? Back: Cache performance models are analytical tools that help us understand and predict the behavior of caches. They allow us to:
Estimate cache performance metrics (hit time, miss rate, miss penalty) for a given cache configuration and workload.
Identify performance bottlenecks and optimization opportunities.
Explore the design space of possible cache configurations without having to build and test each one.
Communicate and reason about cache behavior in a precise, quantitative way.
6.1
Flashcard 1:
Q: What is the basic element of semiconductor memory?
A: The memory cell, which can represent binary 1 and 0.
Flashcard 2:
Q: What are the three functional terminals of a memory cell?
A: Select, control, and data.
Flashcard 3:
Q: What is the difference between DRAM and SRAM?
A: DRAM stores data as charge on capacitors and requires periodic refreshing, while SRAM uses flip-flop logic-gate configurations and does not require refreshing.
Flashcard 4:
Q: What are the types of ROM?
A: ROM, PROM, EPROM, EEPROM, and Flash Memory.
Flashcard 5:
Q: How are memory chips organized?
A: Memory chips are organized into arrays of memory cells.
Flashcard 6:
Q: What is the purpose of chip packaging?
A: Memory chips are mounted on packages with pins for connection.
Flashcard 7:
Q: How can memory modules be organized?
A: Memory modules can be organized to form larger memory systems, such as 256K 8-bit words organized with multiple chips.
Flashcard 8:
Q: What is interleaved memory?
A: Memory banks can be organized to allow simultaneous servicing of multiple requests, increasing memory read/write rates by a factor of the number of banks.
9.1
Flashcard 1:
Q: What are the main objectives of an operating system (OS)?
A: Convenience (making the computer easier to use) and efficiency (optimizing resource use).
Flashcard 2:
Q: What services does an OS provide as a user/computer interface?
A: Program creation, execution, I/O device access, file access, system access, error detection, and accounting.
Flashcard 3:
Q: How does an OS function as a resource manager?
A: It manages resources like the processor, memory, I/O devices, and files, directing the processor in the use of system resources.
Flashcard 4:
Q: What are the types of operating systems?
A: Batch systems, interactive systems, and multiprogramming systems.
Flashcard 5:
Q: What were the main problems with early systems?
A: Scheduling issues and setup time inefficiencies.
Flashcard 6:
Q: How did simple batch systems improve processor utilization?
A: By batching jobs together sequentially and using a monitor to control job sequencing and setup.
Flashcard 7:
Q: What is multiprogramming?
A: A technique where multiple jobs are kept in memory simultaneously, allowing the processor to switch between them to maximize utilization.
Flashcard 8:
Q: What is time-sharing in operating systems?
A: A method where multiple users interact with the system simultaneously, with the OS interleaving the execution of each user program.
9.3
Flashcard 1:
Q: What is swapping in memory management?
A: Swapping involves moving processes between main memory and a storage device to ensure that the processor is not idle.
Flashcard 2:
Q: What are the two types of partitioning in memory management?
A: Fixed-size partitions and variable-size partitions.
Flashcard 3:
Q: What is paging in memory management?
A: Paging divides memory into small fixed-size chunks called pages, and the corresponding chunks in memory are called frames.
Flashcard 4:
Q: What is virtual memory?
A: Virtual memory allows processes to execute even if they are larger than the available physical memory, using demand paging.
Flashcard 5:
Q: What is page replacement?
A: Page replacement is the process of replacing an existing page in memory with a new page when a new page needs to be loaded.
Flashcard 6:
Q: What is the Translation Lookaside Buffer (TLB)?
A: TLB is a special cache used to store recent page table entries to speed up the translation of virtual addresses to physical addresses.
Flashcard 7:
Q: What is segmentation in memory management?
A: Segmentation divides memory into segments of varying sizes, each representing a logical unit such as a function or data array.
13.1
Flashcard 1:
Q: What are the elements of a machine instruction?
A: Operation code (Opcode), Source Operand Reference, Result Operand Reference, Next Instruction Reference.
Flashcard 2:
Q: What is the purpose of the Operation Code (Opcode) in a machine instruction?
A: Specifies the operation to be performed (e.g., ADD, I/O).
Flashcard 3:
Q: What does the Source Operand Reference indicate in a machine instruction?
A: Indicates the input for the operation.
Flashcard 4:
Q: What does the Result Operand Reference specify in a machine instruction?
A: Specifies where the result of the operation should be stored.
Flashcard 5:
Q: What is the Next Instruction Reference in a machine instruction?
A: Tells the processor where to fetch the next instruction after the execution of the current instruction is complete.
Flashcard 6:
Q: What are the common types of instructions in a machine instruction set?
A: Data Processing, Data Storage, Data Movement, Control.
Flashcard 7:
Q: What are the types of data transfer instructions?
A: Register to Register, Register to Memory, Memory to Register, Memory to Memory.
Flashcard 8:
Q: What are the common arithmetic operations provided by most machines?
A: Add, Subtract, Multiply, Divide.
13.2
Flashcard 1:
Q: What are addresses in the context of machine instructions?
A: Addresses are a form of data used to reference memory locations and can be considered as unsigned integers.
Flashcard 2:
Q: What are the common types of numerical data in computers?
A: Binary integer (fixed point), binary floating point, and decimal.
Flashcard 3:
Q: What is packed decimal representation?
A: Each decimal digit is represented by a 4-bit code, with two digits stored per byte.
Flashcard 4:
Q: How are characters represented in computers?
A: Characters are represented by a sequence of bits using codes like ASCII (American Standard Code for Information Interchange) and EBCDIC (Extended Binary Coded Decimal Interchange Code).
Flashcard 5:
Q: What is logical data?
A: Logical data treats each bit of a word as an independent unit, representing binary values (0 or 1).
13.4
Flashcard 1:
Q: What are the common types of operations in machine instructions?
A: Data transfer, arithmetic, logical, conversion, I/O, system control, transfer of control.
Flashcard 2:
Q: What is involved in a data transfer operation?
A: Moving data between memory, registers, or I/O devices.
Flashcard 3:
Q: What are the basic arithmetic operations provided by most machines?
A: Add, subtract, multiply, and divide.
Flashcard 4:
Q: What are logical operations used for?
A: Manipulating individual bits of a word or other addressable units.
Flashcard 5:
Q: What is a conversion operation?
A: Changing the format or operating on the format of data, such as converting from decimal to binary.
Flashcard 6:
Q: What is the purpose of I/O operations?
A: Handling data transfer between the CPU and peripheral devices.
Flashcard 7:
Q: What are system control operations?
A: Instructions that control the operation of the CPU and manage system resources.
Flashcard 8:
Q: What is involved in transfer of control operations?
A: Changing the sequence of execution, such as jumps, calls, and returns.