Memory Hierarchy

💡 Register < Cache (L1<L2<L3) < Main Memory (DRAM) < Disk (SSD/HDD) < Network/Cloud

가상메모리란 디스크에서 메모리로 어떻게 가져올 것? (운영체제)
메모리에서 캐시로 어떻게 가져올 것? (컴퓨터구조)

Motivated by

• Principle of Locality
• Speed vs. size vs. cost tradeoff

Locality principle

💡 최근 자주 사용되는 것들은 다시 사용될 가능성이 있다.

✔️ Spatial Locality: nearby references are likely to occur soon

• ex) arrays, program codes
• Access a block of contiguous words

✔️ Temporal Locality : the same references is likely to occur soon

• ex) loops, reuse of variables
• Keep recently accessed data to closer to the processor (Cache)

✔️ Speed vs. Size tradeoff

• Bigger memory is slower : SRAM - DRAM - Disk - Tape
• Fast memory is more expensive

---

Cache

💡 A small but fast memory located between processor and main memory

✔️ Benefits

• Reduce load latency
• Reduce store latency
• Reduce bus traffic (on-chip caches)

✔️ Cache Block Allocation (when to place)

• On a read miss
• On a write miss

✔️ Cache Block Placement (where to place)

• Fully-assosiative cache
• Direct-mapped cache
• Set-associative cache

✔️ Cache Block Replacement

• Random

  • Just pick one and replace it
  • Pseudo-random: use simple hash algorithm using address

• LRU (least recently used)

  • 과거는 미래의 거울. 가장 오랫동안 참조하지 않은 것을 쫓아낸다
  • need to keep timestamp
  • expensive due to global compare
  • Pseudo-LRU: use LFU using bit tags

• Replacement policy critical for small caches

Cache misses

✔️ Cold-start misses (or compulsory misses)

• the first access to a block is always not in the cache

✔️ Capacity misses

• if the memory blocks needed by a program is bigger than the cache size, the capacity misses will occur due to cache block replacement

✔️ Conflict misses (or collision misses)

• for direct-mapped or set-associative cache, too many blocks can be mapped to the same set

✔️ Invalidation misses (or sharing misses)

• cache blocks can be invalidated due to coherence traffic

---

🔗 Reference

[KUOCW] 최린 교수님의 운영체제 강의를 수강하고 정리한 내용입니다. 잘못된 내용이 있다면 댓글로 알려주시면 감사하겠습니다 😊