Chapter 5 Flashcards
Cache Memory
Define
Block
Minimum unit of transfer between cache and main memory
Define
Frame
To distinguish between the data transferred and the chunk of physical memory.
Define
Line
A portion of cache memory capable of holding one block, so-called because it is usually drawn as a horizontal object
Define
Tag
A portion of a cache line that is used for addressing purposes
Define
Line size
The number of data bytes, or block size, contained in a line
List
Elements of Cache design
Cache address (logical, physical)
Cache size
Mapping function (direct, fully associative, set associative)
Replacement algorithm
Write policy
Line size
Number of caches (single or two level, unified or split)
Define
Virtual memory
Facility that allows programs to address memory from a virtual pov, without regard to the amount of main memory physically available. When used, the address fields of machine instructions contain virtual addresses. For reads and writes from main memory, a hardware memory management unit (MMU) translates each virtual address into a physical address in main memory
Some thoughts about
Cache Size
Preferable to be small enough that overall avg cost per bit is close to that of main memory alone, but large enough that overall avg access time is close to that of cache alone
Speed decreases with size, more gates needed. Limited by amount of space on board and chip.
Optimal size depends on nature of workload
Define
Direct mapped
cache access method
Organization: sequence of m lines
Mapping: each block of main memory maps to one unique line of cache
Access: Line portion of address used to access cache line; tag portion used to check for hit on that line.
Define
Fully Associative
cache access methods
Organization: sequence of m lines
Mapping: each block of main memory can map to any line of cache
Access: tag portion of address used to check every line for hit on that line
Define
Set Associative
Organization: sequence of m lines organized as v sets of k lines each
Mapping: each block of main memory maps to one unique cache set
Access: Line portion of address used to access cache set; tag portion used to check every line in that set for hit on that line.
Compromise with strengths of direct and fully associative.
Define
Content-addressable memory
CAM
Also known as Associative storage
Is constructed of static RAM (SRAM) cells, but more expensive and less storage than regular SRAM
Designed such that when a bit string is supplied, the CAM searches its entire memory in parallel for a match. If found, returns address and sometimes data. Only takes one clock cycle
Define need for
Replacement Algorithms
When new block is brought into cache, one of the existing blocks must be replaced. Direct, don’t get a choice. For high speed, algorithm must be implemented in hardware.
List
Most common replacement algorithms
Least recently used (LRU)- most effective
FIFO
Least frequently used (LFU)
Define
Two cases to consider with write policy
If the block has not been altered then it may be overwritten with a new block without first writing out the old block.
If at least one write operation has been performed on a word in that line, main memory must be updatedby writing line of cache to block of memory before bringing new block
Define
Write through
Simplest technique, all write operations made to main memory as well as to cache.
Main disadvantage, generates substantial memory traffic and may create a bottleneck
Define
Write Back
Minimizes memory writes, updates made only in cache. Portions of main memory are invalid, hence accesses by I/O modules only allowed through cache. Complex circuitry and potential bottleneck
Define
Write miss alternatives
Write allocate: the block containing the word to be written is fetched from main memory (or next level cache) into cache and processor proceeds with the write cycle. Most common with write back
No write allocate: the block containing the word to be written is modified in mm and not loaded into the cache. Most common with write through
List
Cache coherency approaches
Bus watching write-thru
Hardware transparency
Noncacheable memory
Define
Bus watching write through
Each cache controller monitors the address lines to detect write operations to memory by other bus masters. If another master writes to a location in shared memory that also resides in cache memory, cache controller invalidates cache entry.
Depends on write through by all cache controllers
Define
Hardware transparency
Additional hardware is used to ensure that all updates to mm via cache are reflected in all caches. Modifications written to mm
Define
Noncacheable memory
Only a portion is shared by more than one processor, and this is designated as noncacheable. All accesses to shared memory are cache misses because never copied to cache. Noncacheable memory can be identified using chip select logic or high-address bits
Read about line size
Did you do it?? Does hit ratio make enough sense to even study now???!!!!
Define
Multilevel caches
As logic density has increased, it has become possible to have a cache on the same chip as the processor. The on-chip cache reduces the processor’s external bus activity and speeds up execution time and increases overall system performance. With two level cache, internal cache designated L1, external L2
Define
What determines the impact of a multilevel cache?
Depends on the hit rates in both the L1 and L2 caches
Define
Split cache
One dedicated to instructions, the other dedicated to data. Both exist at the same level, typically as two L1 caches
Define
Advantages of split cache
Eliminates cache contention between instructions fetch/decode unit and execution unit (important in pipelining
Trend is towards split caches on L1, unified for higher levels
Define
Advantages of unified cache
Higher hit rate: balances load of instructions and data fetches automatically. Only one cache needs to be designed and implemented
Trend is towards split caches on L1, unified for higher levels
Define
Inclusion policy
Dictates that a piece of data in one cache is guaranteed to also be found in all lower levels of that cache.
Advantage is that it simplifies searching for data when there are multiple processors in the computing system.
This property is useful in enforcing cache coherency
Define
Exclusive policy
Dictates that a piece of data in one cache is guaranteed not to be found in all lower levels of caches.
The advantage is it does not waste cache capacity since it does not store multiple copies of the same data in all caches.
Disadvantage is the need to search multiple levels of when invalidating or updating a block
To minimize search time, the highest-level tag sets are typically duplicated at the lowest cache level to centralize searching
Define
Cache timing model: Direct mapped cache access
The 1st operation is checking the tag field of an address against the tag value in the line designated by the line field.
If there is not a match (miss), the operation is complete.
If there is a match (hit), the cache hardware reads the data block from the line in the cache and fetches the byte or word indicated by the offset field of the address.
Allows for simple and fast speculation
Define
Non inclusive policy
A piece of data in one cache may or may not be found in lower levels of caches.
As with exclusive, the highest-level tag sets are typically duplicated at the lowest cache level to centralize searching
Define
Cache timing model: Fully associative cache
The line number is not known until the tag comparison is completed.
The hit time is the same as for direct mapped.
Because this is a content-addressable memory, the miss time is simply the tag comparison time.
Define
Cache timing model: Set associative
It is not possible to transmit bytes and compare tags in parallel as can be done with direct mapped with speculative access.
However, the circuitry can be designed so that the data block from each line in a set can be loaded then transmitted once the tag check is made.
Define
Hit Ratio
from cloudflare
A measurement of how many content requests a cache is able to fulfill successfully, compared to how many requests it receives.
