[컴퓨터구조] #16. Cache(2)

 

Lec 16. Cache_2 (Large and Fast: Exploiting Memory Hierarchy)

 

- Performance
  Execution time = CPU execution cycles + memory stall cycles
  (실행 시간) = (CPU가 의미있게 돌아가는 시간) + (메모리에 접근하느라 멈춰있는 시간)

  CPU time = #insts × CPI(=명령어 당 사이클 수) × T = clock cycles(=총 소요되는 사이클 수) x T
                  = (CPU execution clock cycles + Memory-stall clock cycles) x T        

  *가정 : cache hit does not require any extra CPU cycle for execution.
          MA stage takes 1 cycle upon a hit (cache hit이면 memory access동작을 해당 cycle안에 모두 완료 가능) 

  Memory stall clock cycles = Read-stall cycles + Write-stall cycles
                                             = (memory accesses/program) x (miss rate) x (miss penalty)
                                             => 총 메모리 접근대비 miss비율(=프로그램의 miss개수) * miss 1회당 패널티
  

- Impacts of Misses on Performance

 

  - Average Memory Access Time (AMAT) 평균 메모리 접근 시간
    AMAT = Hit time + Miss rate x Miss penalty

---

- Improving Cache Performance
  캐시 성능 높이기
  : 단순히 캐시 사이즈를 키운다? -> miss⬇ 이지만 캐시 너무 커지면 접근시간⬆

   AMAT⬇ = Hit time + Miss rate⬇ x Miss penalty⬇
  1) reduces the miss rate
  2) reduces the miss penalty

 

---

 

- Reducing Cache Miss Rates (#1)
  ▪ Direct mapped cache : maps a memory block to exactly one location in cache
                                          메인메모리의 특정한 한 block은 정확하게 cache의 한 block으로만 갈 수 있음.
  ▪ Fully associative cache : a memory block to be mapped to any cache block
                                            메인메모리 block이 cache의 어디든지 갈 수 있음. 
  ▪ n-way set associative cache :
                                      divides the cache into sets, each of which consists of n different locations (ways).
                                            메인메모리 block이 unique한 set로만 갈 수 있음. set 1개가 n개의 block 가짐.
                                            (n개의 way중에서는 어디든지 갈 수 있음)
                                            A memory block is mapped to a unique set (specified by the index field) and
                                            can be placed in any way of that set (so, there are n choices)        
  * associativity : 공동, 연대 (하나의 set가 가질 수 있는 way를 여러개 둠)

Associative Cache Example / Spectrum of Associativity

 

- 4-Way Set Associative Cache

 

예시) cache with 4 oneword blocks, CPU generates 8-bit address to cach

  cache block개수가 동일할 때, set가 줄어들수록 (way가 늘어날수록) miss적어지고 hit 많아짐

 

- Benefits of Set Associative Caches

   무조건 fully associative 가 좋은건 아님. way 많아질수록 하드웨어 cost 증가함.

- Range of Set Associative Caches
  For a fixed size cache, the increase by a factor of 2 in associativity (associativity 2배)
  -> doubles the number of blocks per set (the number of ways) and
      halves the number of sets (way 2배, set 1/2배)
  ex) associativity 4 ways -> 8 ways : size of the index  -1 bit, size of the tag +1 bit

   Block offset : block 안의 word 순서를 나타냄
   Byte offset : word 안의 byte 순서를 나타냄

 

- Replacement Policy
  : 누구를 방출(evict)할 것인지에 대한 정책
   -> Least-recently used(LRU) 또는 Random 하게 방출

  associativity가 작으면 LRU방식을, 크면 Random 방식을 주로 이용함.
  Valid bit 와 Dirty bit 는 way마다 필요하지만 LRU 는 set 마다 필요함.

 

---

 

- Reducing Cache Miss Penalty (#2)
  miss가 이미 발생했을 때, 패널티 줄이기 위해 cache를 multiple level로 나눔.

  L1에서는 structure hazard (instruction fetch&memory access 동시에) 를 막기위해 나눴음.
  L2와 L3는 instruction과 data를 위한 메모리를 따로 나누지않고 통합했음.
  ∵instruction과 data의 비중이 동적으로 바뀔 수 있는 프로그램의 성격을 모른 채로 용량을 나누어버리면
    용량 낭비가 심할 수 있음. 각 cache의 용량을 잘 쓰려면 unified가 좋음.

Core i7 Example

 

- Multilevel Cache Performance Example

  L1만 있을 때보다 L2까지 있을 떄 CPI가 더 작음.

- Multilevel Cache Design Considerations
  AMAT = Hit time + Miss rate x Miss penalty
  ▪ L1 should focus on minimizing hit time in support of a shorter clock cycle
    : L1 is smaller (i.e., faster) but have higher miss rate
  ▪ L2 (L3) should focus on reducing miss rate and reducing L1 miss penalty
    : High associativity and large cache size. (conflict miss 줄이기 위해)
      For the L2 (L3) cache, hit time(매인메모리보다 좋기만하면 됨) is less important than miss rate.
      Miss penalty of L1 cache is significantly reduced by the presence of L2 and L3 caches

Two Machines’ Cache Parameters

 

---

 

- Software Techniques
  : To avoid the cache misses, try to exploit the cache structure in programming to reduce the miss rate 
  -> code optimizations (Loop interchange, Loop blocking)

- Cache-friendly Code 
  row-major ordering 일때, 아래의 코드가 더 효율적임.

Loop Interchange