17. Memory Hierarchy and Caches

생성일: 2021년 12월 4일 오후 5:04

What is a Computer?

Abstraction: Virtual vs. Physical Memory

• Programmer sees virtual memory
• The system (system software + hardware, cooperatively) maps virtual memory addresses to physical memory

이상적인 구조

Memory in a Modern System

이상적인 구조의 문제점

• 요구 사항이 서로 상반 된다
  • Bigger is slower (용량이 클수록 위치를 결정하는데 오래 걸림)
  • 빠를수록 비싸다
  • 대역폭이 높을수록 비싸다

Memory는 성능에 매우 중요

• 메모리로 인해 계산에 병목(Bottlenecked) 현상이 생김

DRAM

• Dynamic random access memory
• Capacitor charge state indicates stored value
• Capacitor leaks through the RC path
  

SRAM

• Static random access memory
• Two cross coupled inverters store a single bit

Memory Bank Organization and Operation

DRAM vs. SRAM

• DRAM
  • Slower access (capacitor)
  • Higher density (1T 1C cell)
  • Lower cost
  • Requires refresh (power, performance, circuitry)
  • Manufacturing requires putting capacitor and logic together
• SRAM
  • Faster access (no capacitor)
  • Lower density (6T cell)
  • Higher cost
  • No need for refresh
  • Manufacturing compatible with logic process (no capacitor)

How Can We Store Data?

• Flip-Flops (or Latches)
• Static RAM
• Dynamic RAM
• Other storage technology (flash memory, hard disk, tape)

Why Memory Hierarchy?

• We want both fast and large
• But we cannot achieve both with a single level of memory
• Idea : Have multiple levels of storage

Memory Hierarchy

Locality

• One’s recent past is a very good predictor of his/her near future.
• Temporal Locality (시간적 지역성) : If you just did something, it is very likely that you will do the same thing again soon
• Spatial Locality (공간적 지역성) : If you did something, it is very likely you will do something similar/related (in space)

Memory Locality

• Temporal : A program tends to reference the same memory location many times and all within a small window of time
• Spatial: A program tends to reference a cluster of memory locations at a time

Caching Basics : Exploit Temporal Locality

• Idea : Store recently accessed data in automatically managed fast memory (called cache)
• 데이터가 곧 다시 accessed 될 것이라고 예측

Caching Basics : Exploit Spatial Locality

• Idea: Store addresses adjacent to the recently accessed one in automatically managed fast memory
  • Logically divide memory into equal size blocks
  • Fetch to cache the accessed block in its entirety
• 가까운 데이터에 곧 access 할 것이라고 예측

Caching in a Pipelined Design

• The cache needs to be tightly integrated into the pipeline
• High frequency pipeline → Cannot make the cache large
• Idea : Cache hierarchy

A Modern Memory Hierarchy

Memory Hierarchy

• Processors have cycle times of ~1 ns
• Fast DRAM has a cycle time of ~100 ns
• We have to bridge this gap for pipelining to be effective!

Basic terminologies

Multilevel Memory Hierarchy

• Modern processors use multiple levels of caches
• As we move away from processor, caches get larger and slower
• 𝐸𝑀𝐴𝑇𝑖 = 𝑇𝑖 + 𝑚 ∗ 𝐸𝑀𝐴𝑇𝑖+1
  where 𝑇𝑖 is access time for level 𝑖 and 𝑚𝑖 is miss rate for level

Cache organization (캐시 구성)

1. Placement: Where do we place in the cache the data read from the memory?
2. Algorithm for lookup: How do we find something that we have placed in the cache?
3. Validity: How do we know if the data in the cache is valid?

Direct-mapped cache organization

10진수

2진수

• Cache_Index = Memory_Address mod Cache_Size (mod는 나머지 연산)

• Cache_Tag = Memory_Address/Cache_Size

Sequence of Operation

Thought Question (위의 그림에서)

Assume computer is turned on and every location in cache is zero. What can go wrong?

⇒ ADD a Bit!

• Each cache entry contains a bit indicating if the line is valid or not. Initialized to invalid

Hardware for direct mapped cache