1. Cache
• Definition: computer memory with short access time used for the storage of frequently or recently used instructions or data(i-cachhe and d-cache).
• more generally, used to optimize data transfers between system elements with different characteristics (network interface cache, I/O cache, etc.)
• Hit:
• Miss:
2. Locality: programs tend to use data and instructions with addresses near or equal to those they have used recently
• Temporal locality:
• Recentlly referenced items are likely to be referenced again in the near future.
• Spatial locality:
• Items with nearby addresses tend to be referenced close together in time
3. Cost of Cache Misses
• Huge difference between a hit and a miss
• could be 100x, if just L1 and main memory
• 99% hits is twice as good as 97%
4. Cache Performance Metrics
• Miss Rate:
• Fraction of memory references not found in cache (misses/ accesses) = 1 – hit rate
• Typical numbers(in percentage)
• 3% – 10% for L1
• Hit Time
• Time to deliver a line in the cache to the processor
• Includes time to determine whether the line is in the cache
• Typical hit times: 1 –2 clock cycles for L1
• Miss Penalty
• Additional time required because of a miss
• Typically 50 – 200 cycles
5. Memory Hierarchies
• Well-written programs tend to exhibit good locality
• These properties complement each other beautifully
• Fundamental idea of a memory hierarchy:
• Each level k serves as a cache for the larger, slower, level k+1 below
6. 
7. 
8. 
9. 
10. Optimizations for the Memory Hierarchy
• Write code that has locality
• Spatial: access data contiguously
• Temporal: make sure access to the same data is not too far apart in time
• How to achieve
• Proper choice of algorithm
• Loop transformations

【2014-11-23】《The Hardware/Software Interface》– Section 7