[CS] Cache, Memory Layer

seunghyunยท2023๋…„ 5์›” 7์ผ
0

๐Ÿ’ป

๋ชฉ๋ก ๋ณด๊ธฐ
6/16

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] ์ตœ๋ฆฐ ๊ต์ˆ˜๋‹˜์˜ ์šด์˜์ฒด์ œ ๊ฐ•์˜๋ฅผ ์ˆ˜๊ฐ•ํ•˜๊ณ  ์ •๋ฆฌํ•œ ๋‚ด์šฉ์ž…๋‹ˆ๋‹ค. ์ž˜๋ชป๋œ ๋‚ด์šฉ์ด ์žˆ๋‹ค๋ฉด ๋Œ“๊ธ€๋กœ ์•Œ๋ ค์ฃผ์‹œ๋ฉด ๊ฐ์‚ฌํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค ๐Ÿ˜Š

profile
๐Ÿ‘ฉ๐Ÿปโ€๐Ÿ’ป๐ŸŽฎ

0๊ฐœ์˜ ๋Œ“๊ธ€